\documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern,amsmath,amssymb,amsthm,mathtools} \usepackage[margin=1.15in]{geometry} \usepackage{enumitem,booktabs,array,needspace} \usepackage{tikz} \usetikzlibrary{patterns,decorations.pathreplacing} \usepackage[colorlinks=true,urlcolor=blue,linkcolor=black,citecolor=black]{hyperref} \hypersetup{pdftitle={The \v{C}ern\'y (1969) conjecture holds for quasi-Eulerian automata of degree one},pdfauthor={Dave Goel}, pdfkeywords={synchronizing automaton, reset word, Cerny conjecture, quasi-Eulerian automaton, stationary vector}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{example}[theorem]{Example} \newtheorem{question}[theorem]{Question} \newcommand{\rt}{\operatorname{rt}} \newcommand{\ext}{\operatorname{ext}} \newcommand{\esc}{\operatorname{esc}} \newcommand{\one}{\mathbf 1} \newcommand{\ind}[1]{[#1]}\newcommand{\indv}[1]{\one_{#1}} \newcommand{\Cerny}{\v{C}ern\'y} \setlist[enumerate]{leftmargin=*,label=\textup{(\alph*)}} \raggedbottom \emergencystretch=1.5em \title{The \v{C}ern\'y (1969) conjecture holds for quasi-Eulerian automata of degree one} \author{Dave Goel} \makeatletter\def\@setdate{\@date\@addpunct.}\makeatother\date{First version: October 24, 2026. This version: November 18, 2026.} \subjclass[2020]{Primary 68Q45; Secondary 05C20, 60J10} \keywords{synchronizing automaton, reset word, \v{C}ern\'y conjecture, quasi-Eulerian automaton, stationary vector} \begin{document} \begin{abstract} An automaton with $n$ states is quasi-Eulerian of degree $d$ if there are positive letter weights summing to one, a set $X$ of $d$ exceptional states and a further state $s$ such that every state outside $X\cup\{s\}$ receives total weight one and every edge that starts in $X$ ends in $X\cup\{s\}$. Berlinkov bounded the reset threshold of strongly connected synchronizing ones by $2^d(n-d+1)(n-1)$. We prove that every synchronizing quasi-Eulerian automaton of degree one has a reset word of length at most $(n-1)^2$, so the \Cerny{} (1969) conjecture holds for this family; the \Cerny{} automata belong to it and attain the bound. The same bound holds for every synchronizing automaton whose transition matrix, weighted by some positive, possibly irrational, letter weights, has a positive stationary vector that is constant on all states but one; for this family Berlinkov's bound was $2n(n-1)$. For synchronizing quasi-Eulerian automata of degree two, the bound holds whenever the automaton is not strongly connected, whenever its two exceptional states form a block of a congruence, and, for binary strongly connected automata, in $46$ of the $49$ configurations (up to renaming) of the edges at the two exceptional states. The key step in degree one is elementary: a shortest word that takes the exceptional state out of a set $K$ of states that contains it has length at most $|K|$, and one that takes it into a set $K$ that does not contain it has length at most $n-|K|$. \unskip\footnotemark[1]\end{abstract} \maketitle \footnotetext[1]{Additionally, all results of this paper are proved in Lean~4 from Lean's three standard axioms alone, and checked with \texttt{lake comparator}:\\ \url{https://github.com/david44hello/paper_cerny-1969-conjecture-quasi-eulerian/tree/v4.50}} \section{Introduction}\label{sec:intro} The \Cerny{} (1969) conjecture states that if some word maps all $n$ states of an automaton to one state, then some such word has length at most $(n-1)^2$. We prove it for the quasi-Eulerian automata of degree one, a family introduced by Berlinkov, and for several families of quasi-Eulerian automata of degree two. \subsection*{Background} A (complete deterministic) automaton $\mathcal A=(Q,\Sigma)$ has a finite nonempty set $Q$ of $n$ states and a finite nonempty alphabet $\Sigma$; every letter maps $Q$ to $Q$; we write $q.b$ for the image of a state $q$ under a letter $b$, and call $q\to q.b$ an \emph{edge} with label $b$. The automaton is \emph{synchronizing} if some word, a \emph{reset word}, maps all states to one state; the least length of a reset word is the \emph{reset threshold} $\rt(\mathcal A)$. In 1964 \Cerny{} \cite{Cer64} described automata $C_n$ with $n$ states, two letters and $\rt(C_n)=(n-1)^2$: on $Q=\{0,\ldots,n-1\}$ the letter $a$ maps $0$ to $1$ and fixes every other state, and $b$ maps $q$ to $q+1\bmod n$ (Figure~\ref{fig:witness}, right). He stated the conjecture in a talk in 1969, and it first appeared in print in \cite{CPR71} (see \cite[Section~1]{Vol08} and, for its history, \cite[Section~3.1]{Vol22}). It is open in general: the best known upper bounds are cubic, from Pin and Frankl's $(n^3-n)/6$ \cite{Pin83,Fra82} to the small improvements of Szyku{\l}a \cite{Szy18} and Shitov \cite{Shi19}. The conjecture has been proved for many special families of automata; Volkov's list \cite{Vol26} records them, together with the families for which only a quadratic bound is known. Kari \cite{Kar03} proved $\rt\leq1+(n-2)(n-1)$ for Eulerian automata (strongly connected, with every state entered by exactly $|\Sigma|$ edges), and Steinberg \cite{Ste11} extended this to \emph{pseudo-Eulerian} automata: strongly connected automata with positive letter weights for which every state receives total weight one. Berlinkov \cite{Ber12,Ber13} introduced the following generalization. \begin{definition}[{Berlinkov \cite{Ber12,Ber13}; see \cite[item D3]{Vol26}}]\label{def:qe} An automaton $\mathcal A=(Q,\Sigma)$ is \emph{quasi-Eulerian of degree $d$} if there are a set $E\subseteq Q$ with $|E|=n-d$, a state $s\in E$ and letter weights $p=(p_b)_{b\in\Sigma}$ with $p_b>0$ and $\sum_bp_b=1$ such that \begin{enumerate} \item every edge that starts in $X:=Q\setminus E$ ends in $X\cup\{s\}$, and \item every state $r\in E\setminus\{s\}$ has in-weight one: $\sum_{b\in\Sigma}p_b\,|\{q\in Q: q.b=r\}|=1$. \end{enumerate} We call $(E,s,p)$ a \emph{witness}, $X$ its \emph{exceptional} states, and $p$ \emph{admissible}. \end{definition} The \Cerny{} automata are quasi-Eulerian of degree one \cite[Section~4]{Ber12}, \cite[item D3]{Vol26}, so $(n-1)^2$ is the best possible bound for this family (Figure~\ref{fig:witness}). For a strongly connected synchronizing quasi-Eulerian automaton of degree $d$, Berlinkov proved $\rt(\mathcal A)\leq2^d(n-d+1)(n-1)$ \cite[Theorem~8]{Ber13} (see also \cite[Theorem~2]{Ber12}). Admissible weights $p$ give the row-stochastic matrix $M=\sum_bp_bM_b$, where $M_b$ is the $0/1$ transition matrix of the letter $b$, and a \emph{stationary vector} is a nonzero vector $\alpha$ with $\alpha^{\mathsf T}M=\alpha^{\mathsf T}$ (Section~\ref{sec:prelim}). For a strongly connected automaton it can be taken equal to $1$ on $E$ and positive on the exceptional states (Lemma~\ref{lem:statd}). In degree two we write $t_1,t_2$ for its values on the two exceptional states and call the unordered pair $\{t_1,t_2\}$ the \emph{class} of the witness. For binary automata (two letters, $\Sigma=\{a,b\}$) of degree two, the \emph{configuration} of the witness records where the four edges that start at the exceptional states end, and how many edges from $E$ enter each exceptional state. For a strongly connected binary automaton the class is always computed with the weights $(\frac12,\frac12)$, which are then admissible (Lemma~\ref{lem:gadget}); the configuration of the witness is then one of $49$, up to renaming the two exceptional states and the two letters, and its class one of $14$ (Lemma~\ref{lem:classes} and Table~\ref{tab:classes}). The two exceptional states form a \emph{block of a congruence} if every letter maps them to one state or to the pair itself (Proposition~\ref{prop:block}). \subsection*{Results} The table compares our main results with the best results known before this paper. \begin{center} \footnotesize \begin{tabular}{@{}p{0.50\textwidth}@{\hspace{0.03\textwidth}}p{0.45\textwidth}@{}} \toprule Best result before this paper & New result\\ \midrule $\rt\leq2n(n-1)$ for strongly connected ones \cite[Theorem~8]{Ber13}; the \Cerny{} conjecture was open for this family \cite[item D3]{Vol26}. & Quasi-Eulerian, degree one: $\rt\leq(n-1)^2$, attained by $C_n$ (Theorem~\ref{thm:degree1}).\\ \addlinespace $\rt\leq2n(n-1)$ \cite[Proposition~4]{Ber12}. & A positive stationary vector that is constant off one state, for some positive (possibly irrational) letter weights: $\rt\leq(n-1)^2$ (Theorem~\ref{thm:constant}).\\ \addlinespace $\rt\leq4(n-1)^2$ for strongly connected ones \cite[Theorem~8]{Ber13}; \cite[item D3]{Vol26} lists it for the whole family. & Degree two, not strongly connected: $\rt\leq(n-1)^2$ (Theorem~\ref{thm:nonsc}).\\ \addlinespace $\rt\leq4(n-1)^2$ \cite[Theorem~8]{Ber13}; \mbox{$(n-1)^2$} for all $n$ only in the class $\{1,1\}$, where the stationary vector is constant (pseudo-Eulerian) \cite{Kar03,Ste11}; Volkov's list \cite{Vol26} records no other. & Degree two, binary, strongly connected: $\rt\leq(n-1)^2$ in 46 of the 49 configurations, covering every configuration of 12 of the 14 classes (Theorem~\ref{thm:binary}).\\ \bottomrule \end{tabular} \end{center} \begin{itemize}[leftmargin=*] \item \emph{We prove the \Cerny{} (1969) conjecture for quasi-Eulerian automata of degree one} (Berlinkov's family, Definition~\ref{def:qe}): every synchronizing one has $\rt\leq(n-1)^2$, and the \Cerny{} automata attain this bound (Theorem~\ref{thm:degree1}, proved in Section~\ref{sec:degree1}). The best bound before was $2n(n-1)$, for strongly connected ones \cite{Ber13}. Strong connectivity is not assumed: if the automaton is not strongly connected, then either every letter fixes the exceptional state or $E$ is closed (no edge leaves $E$), and in both cases Kari's argument gives $\rt\leq1+(n-2)(n-1)$. \item \emph{We improve Berlinkov's bound $2n(n-1)$ \cite[Proposition~4]{Ber12} to $(n-1)^2$} for every synchronizing automaton with positive letter weights whose stationary vector is positive and constant on all states but one; the weights need not be rational (Theorem~\ref{thm:constant}, proved in Section~\ref{sec:constant}). This family contains every strongly connected synchronizing quasi-Eulerian automaton of degree one (by Berlinkov's observation in the proof of \cite[Theorem~2]{Ber12} and Lemma~\ref{lem:stat1}), and others (Example~\ref{ex:degree3}). \item \emph{Degree two.} We prove $\rt\leq(n-1)^2$ for every synchronizing quasi-Eulerian automaton of degree two that is not strongly connected (Theorem~\ref{thm:nonsc}, proved in Section~\ref{ssec:nonsc}), for every one whose two exceptional states form a block of a congruence (Proposition~\ref{prop:block}, Section~\ref{ssec:block}), and for binary strongly connected ones in 46 of the 49 configurations, which include every configuration of 12 of the 14 classes (Theorem~\ref{thm:binary}, proved in Section~\ref{ssec:binary}; Figure~\ref{fig:configs}). For the three classes $\{2,2\}$, $\{2,3\}$ and $\{2,4\}$ and at most six states, the bound follows from the computation of Kisielewicz, Kowalski and Szyku{\l}a \cite{KKS16}, who verified the \Cerny{} conjecture for all binary automata with at most $12$ states. For $n\geq7$, Corollary~\ref{cor:integer} also gives the bound in the integer classes $\{2,k\}$ ($k$ a positive integer) over every alphabet. The best bound before was Berlinkov's $4(n-1)^2$ for strongly connected ones \cite[Theorem~8]{Ber13}; \cite[item D3]{Vol26} lists it without that hypothesis. \end{itemize} Recently Zhu \cite{Zhu26} announced a proof of the conjecture for one-cluster automata (some letter has only one cycle; \cite[item D1]{Vol26}). This family and the family of Theorem~\ref{thm:degree1} are incomparable (Remark~\ref{rem:onecluster}). \begin{figure}[t] \centering \input{fig_witness.tex} \caption{Left: a witness $(E,s,p)$ of degree two (Definition~\ref{def:qe}; $p$ gives the letter weights). Every state of $E$ other than $s$ has in-weight one, every edge that starts in the set $X$ of exceptional states ends in $X\cup\{s\}$, and edges from $E$ may enter $X$ (dotted); only some edges are drawn. Right: the \Cerny{} automaton $C_4$ (letter $a$ solid, letter $b$ dashed) with the witness of degree one used in Theorem~\ref{thm:degree1}: $x=0$, $s=1$ and $E=\{1,2,3\}$.}\label{fig:witness} \end{figure} \begin{figure}[t] \centering \input{fig_configs.tex} \caption{Green squares: the bound $(n-1)^2$ is known for all $n$; grey squares with a question mark: it is known only for $n\leq12$ \cite{KKS16}. The squares are the $49$ configurations of Lemma~\ref{lem:classes} (binary strongly connected automata of degree two), in rows by class $\{t_1,t_2\}$ (Table~\ref{tab:classes}). Left: before this paper, the bound $(n-1)^2$ was known for all $n$ only in the class $\{1,1\}$, where the stationary vector is constant \cite{Kar03,Ste11}; Berlinkov's bound $4(n-1)^2$ \cite{Ber13} holds in all of them. Right: after this paper; each row names the results that give $(n-1)^2$, and the three grey squares are the configurations excluded in Theorem~\ref{thm:binary}.}\label{fig:configs} \end{figure} \subsection*{Method} All proofs use the extension method: a reset word is built from right to left by enlarging preimages of a set. Kari's step \cite{Kar03}, with letter weights as in Steinberg's averaging trick \cite{Ste11} and with Berlinkov's stationary vector $\alpha$ as the measure of a set \cite{Ber12}, finds for a nonempty proper set $K$ a word $w$ of at most $n-1$ letters that \emph{raises} $\alpha$: the preimage $Kw^{-1}$ has $\alpha(Kw^{-1})>\alpha(K)$. Here $\alpha(K)=\sum_{q\in K}\alpha_q$, and $\alpha$ is a stationary vector of the weighted transition matrix (Lemma~\ref{lem:step}). When $\alpha$ is constant off one state $x$, a raising word either enlarges the set or moves $x$ from one side of the set to the other. The key observation is that such moves are short. By the \emph{orbit lemma} (Lemma~\ref{lem:orbit}), an elementary bound on shortest paths, a shortest word that moves $x$ across a set $K$ has length at most $|K|$ if $x\in K$, and at most $n-|K|$ if $x\notin K$. Scale $\alpha$ so that $\alpha=1$ off $x$, and put $t=\alpha_x$. When $01$), by the orbit lemma, and at most $n$ together. After a first letter that merges two states, at most $n-2$ enlargements of at most $n$ letters each give $1+(n-2)n=(n-1)^2$. Figure~\ref{fig:chain} shows these steps for the \Cerny{} automaton $C_4$, where every bound is attained.\input{fig_c4_chain_float} When $t>2$ is not an integer, we pair a move of $x$ out of the set with the later move that brings it back. The move out itself enlarges the set by more than $t-1$ states, and the set does not shrink before the move back, so the two moves together cost at most $n-2$ letters, and a potential-function count gives $(n-1)^2$. When $t$ is an integer, $\alpha$ takes integer values on sets, so every step raises $\alpha$ by at least one, and at most $n-1$ steps of at most $n-1$ letters lead from $\{x\}$ to $Q$ (Section~\ref{sec:constant}). Theorem~\ref{thm:degree1} follows (Section~\ref{sec:degree1}): Lemma~\ref{lem:stat1} gives such a vector when the automaton is strongly connected, and Kari's argument covers the other cases. In degree two, an automaton that is not strongly connected is reduced to its unique minimal nonempty closed set $C$: either $C$ consists of exceptional states, or the restriction to $C$ is quasi-Eulerian of degree one or has the all-ones stationary vector $\one$. The set $R$ of the other states is moved into $C$ by at most $|R|^2$ letters (Lemma~\ref{lem:push}), and $|R|^2+(n-1-|R|)^2\leq(n-1)^2$. When the automaton is strongly connected and its two exceptional states form a block of a congruence, the quotient automaton satisfies the hypothesis of Theorem~\ref{thm:constant} (Proposition~\ref{prop:block}). In the binary case, call the \emph{cost} of a set $K$ the least length of a word $w$ with $\alpha(Kw^{-1})\neq\alpha(K)$, and its \emph{pattern} the record of which of $x_1$, $x_2$ and $s$ it contains. The configuration determines, from the pattern alone, whether $\alpha(Kc^{-1})-\alpha(K)$ is not an integer for some letter $c$; then $K$ costs one letter. A joint orbit of $x_1$, $x_2$ and $s$ (Lemma~\ref{lem:joint}) helps to bound the cost of a set that contains all three of them or none of them, and the values of $\alpha$ limit how many sets of each size can occur in a chain of preimages built by the extension method. For the classes $\{2,2\}$, $\{2,3\}$ and $\{2,4\}$ of degree two we also use the \emph{tier lemma} (Lemma~\ref{lem:tier}): for $2\leq j\leq n$, at most $2^j-2$ nonempty proper sets have cost at least $n-j+1$. Its proof counts $0/1$ vectors in a subspace, as in Szyku{\l}a's improvement for Eulerian automata \cite[Section~2.8.3]{Szy26}. \subsection*{Organization} Section~\ref{sec:prelim} fixes notation and proves the general lemmas (strong connectivity from a positive stationary vector, the extension step, the orbit lemma and the tier lemma). Section~\ref{sec:constant} proves Theorem~\ref{thm:constant} and Section~\ref{sec:degree1} proves Theorem~\ref{thm:degree1}. Section~\ref{sec:degree2} treats degree two, and Section~\ref{sec:open} lists the open cases. \section{Preliminaries}\label{sec:prelim} \subsection{Automata and preimages} Let $\mathcal A=(Q,\Sigma)$ be an automaton with $|Q|=n$. Words act on the right: $q.(uv)=(q.u).v$. For $K\subseteq Q$ and a word $w$, the \emph{preimage} is $Kw^{-1}=\{q\in Q: q.w\in K\}$, so that \[K(uv)^{-1}=(Kv^{-1})u^{-1}.\] A set $K$ is \emph{closed} if $K.b\subseteq K$ for every letter $b$; $\mathcal A$ is \emph{strongly connected} if $\varnothing$ and $Q$ are its only closed sets. If $K_0\subseteq Q$ and $K_{j+1}=K_jw_j^{-1}$ for $j|K|$ (infinite if there is none). For a word $w$ let $M_w$ be the $Q\times Q$ matrix with $(M_w)_{q,q'}=1$ if $q.w=q'$ and $0$ otherwise. Then $M_{uv}=M_uM_v$, $M_w\one=\one$, and $M_w\indv K=\indv{Kw^{-1}}$, where $\indv K$ is the indicator column vector of $K$ and $\one=\indv Q$. For $\beta\in\mathbb R^Q$ write $\beta(K)=\sum_{q\in K}\beta_q$; then $\beta^{\mathsf T}M_w\indv K=\beta(Kw^{-1})$. For a statement $P$, we write $\ind P$ for the number that is $1$ if $P$ holds and $0$ otherwise. \subsection{Letter weights and stationary vectors} \emph{Letter weights} are numbers $p_b>0$ ($b\in\Sigma$) with $\sum_bp_b=1$; they need not be rational. Put $M=\sum_bp_bM_b$, a row-stochastic matrix: the transition matrix of the random walk on $Q$ that applies the letter $b$ with probability $p_b$. A \emph{stationary vector} is a nonzero $\alpha\in\mathbb R^Q$ with $\alpha^{\mathsf T}M=\alpha^{\mathsf T}$; then \begin{equation}\label{eq:average} \textstyle\sum_bp_b\,\alpha(Tb^{-1})=\alpha^{\mathsf T}M\indv T=\alpha(T)\qquad\text{for every }T\subseteq Q. \end{equation} We give an edge with label $b$ the \emph{weight} $p_b$. The \emph{in-weight} of a state $q$ is $\mathrm{in}_p(q)=\sum_bp_b|\{q\}b^{-1}|$, the total weight of the edges that end at $q$; the edges that start at a state have total weight $\sum_bp_b=1$, its \emph{out-weight}, so the in-weights add up to $n$. So $\alpha=\one$ is stationary if and only if every in-weight is one. \begin{lemma}[strong connectivity]\label{lem:positive} Let $\mathcal A$ be synchronizing, let $p$ be letter weights, and let $\alpha$ be a stationary vector with $\alpha_q>0$ for every $q$. Then $\mathcal A$ is strongly connected. \end{lemma} \begin{proof} Let $C$ be a nonempty closed set. For $q'\in Q$ let $\pi(q')=\sum_{b:\,q'.b\in C}p_b$; so $\pi(q')=1$ for $q'\in C$. Summing the stationary equations over $C$ gives $\alpha(C)=\sum_{q'}\alpha_{q'}\pi(q')=\alpha(C)+\sum_{q'\notin C}\alpha_{q'}\pi(q')$, so $\pi(q')=0$ for every $q'\notin C$ (as $\alpha>0$): no letter takes a state outside $C$ into $C$, and $Q\setminus C$ is closed too. A reset word maps all states to one state, which lies in $C$ and in $Q\setminus C$ if both are nonempty. So $C=Q$. \end{proof} \begin{lemma}[{the extension step; Kari \cite{Kar03}, Steinberg \cite{Ste11}, Berlinkov \cite[Theorem~1]{Ber12}}]\label{lem:step} Let $\mathcal A$ be synchronizing, let $\beta\in\mathbb R^Q$ with $\beta(Q)\neq0$, and let $K\subseteq Q$ with $\beta(K)\notin\{0,\beta(Q)\}$. Let $m$ be the least length of a word $w$ with $\beta(Kw^{-1})\neq\beta(K)$. \begin{enumerate} \item The number $m$ exists, and $1\leq m\leq n-1$. \item Let $p$ be letter weights, and suppose that $\sum_bp_b\beta(Tb^{-1})\geq\beta(T)$ for every set $T=Kv^{-1}$ with $|v|=m-1$. Then some word $w$ of length $m$ has $\beta(Kw^{-1})>\beta(K)$. \end{enumerate} In particular, if $\alpha$ is a stationary vector for some letter weights, with $\alpha(Q)\neq0$ and $\alpha(K)\notin\{0,\alpha(Q)\}$, then some word $w$ of length at most $n-1$ has $\alpha(Kw^{-1})>\alpha(K)$, and the least such length equals the least length of a word that changes $\alpha(Kw^{-1})$. \end{lemma} \begin{proof} (a) A reset word $u$ gives $Ku^{-1}\in\{\varnothing,Q\}$, so $\beta(Ku^{-1})\in\{0,\beta(Q)\}$ differs from $\beta(K)$; hence $m$ exists, and $m\geq1$. Put $\zeta_K=\indv K-\frac{\beta(K)}{\beta(Q)}\one$. Since $M_w\one=\one$, $\beta^{\mathsf T}M_w\zeta_K=\beta(Kw^{-1})-\beta(K)$. Also $\zeta_K\neq0$, since $K\notin\{\varnothing,Q\}$. Let $L_i=\operatorname{span}\{M_w\zeta_K:|w|\leq i\}$. As $M_{bw}=M_bM_w$, $L_{i+1}=L_0+\sum_bM_bL_i$, so $L_i=L_{i+1}$ implies $L_j=L_i$ for all $j\geq i$. For $i0$, some letter $b$ has $\beta(Tb^{-1})>\beta(T)$. The word $bv$ has length $m$ and $K(bv)^{-1}=Tb^{-1}$. For the last statement, \eqref{eq:average} gives the hypothesis of (b), with equality, for every $T$; so by (a) and (b) some word of length $m\leq n-1$ raises $\alpha$, and no shorter word does, since a word that raises $\alpha$ changes $\alpha(Kw^{-1})$. \end{proof} We say that a word $w$ \emph{raises} $\alpha$ (for $K$) if $\alpha(Kw^{-1})>\alpha(K)$. For a vector $\alpha\in\mathbb R^Q$ with $\alpha_q>0$ for every $q$ and a nonempty proper set $K$, let $m(K)$, the \emph{cost} of $K$, be the least length of a word $w$ with $\alpha(Kw^{-1})\neq\alpha(K)$; the vector $\alpha$ will be clear from the context. As $0<\alpha(K)<\alpha(Q)$, Lemma~\ref{lem:step}(a) gives $1\leq m(K)\leq n-1$ when $\mathcal A$ is synchronizing, and if $\alpha$ is stationary, some word of length $m(K)$ raises $\alpha$. \begin{lemma}[orbit lemma]\label{lem:orbit} Let $x\in Q$ and $K\subseteq Q$. Say that a word $w$ \emph{moves $x$ across $K$} if $x$ lies in exactly one of the sets $K$ and $Kw^{-1}$, that is, if $\ind{x.w\in K}\neq\ind{x\in K}$ (note that $\ind{x\in Kw^{-1}}=\ind{x.w\in K}$). Let $\esc_x(K)$ be the least length of a word that moves $x$ across $K$ (infinite if there is none). If $\esc_x(K)$ is finite, then $\esc_x(K)\leq|K|$ when $x\in K$, and $\esc_x(K)\leq n-|K|$ when $x\notin K$. If $\mathcal A$ is strongly connected and $\varnothing\neq K\neq Q$, then $\esc_x(K)$ is finite. \end{lemma} \begin{proof} Let $R_i=\{x.w:|w|\leq i\}$. Then $R_0=\{x\}$ and $R_{i+1}=R_i\cup R_i.\Sigma$, so $R_i=R_{i+1}$ implies $R_j=R_i$ for all $j\geq i$. Let $f=\esc_x(K)<\infty$. If $x\in K$, then $R_{f-1}\subseteq K$ and $R_f\not\subseteq K$, so the chain $R_0\subsetneq\cdots\subsetneq R_{f-1}$ is strict and $f\leq|R_{f-1}|\leq|K|$. If $x\notin K$, the same argument in $Q\setminus K$ gives $f\leq n-|K|$. If $\mathcal A$ is strongly connected, the set $R_{n}$ of all states reachable from $x$ (the chain is constant from $i=n-1$ on) is $Q$, so it meets both $K$ and $Q\setminus K$. \end{proof} \begin{lemma}[tier lemma]\label{lem:tier} Let $\mathcal A$ be synchronizing and strongly connected, let $\alpha\in\mathbb R^Q$ with $\alpha_q>0$ for every $q$, and let $m$ be the cost for this $\alpha$. Then for $2\leq j\leq n$, at most $2^j-2$ nonempty proper sets $S$ have $m(S)\geq n-j+1$. In particular, at most two sets have $m(S)=n-1$, and at most six have $m(S)\geq n-2$. \end{lemma} \begin{proof} For a letter $c$ put $\delta_c=\alpha^{\mathsf T}M_c-\alpha^{\mathsf T}$, a row vector, and for $k\geq0$ let $D_k=\operatorname{span}\{\delta_cM_v: c\in\Sigma,\ |v|\leq k-1\}$, so $D_0=0$. For a word $w=c_1c_2\cdots c_l$, \begin{equation}\label{eq:telescope} \textstyle\alpha^{\mathsf T}M_w-\alpha^{\mathsf T}=\sum_{i=1}^{l}\delta_{c_i}M_{c_{i+1}\cdots c_l}, \end{equation} since the $i$th term is $\alpha^{\mathsf T}M_{c_i\cdots c_l}-\alpha^{\mathsf T}M_{c_{i+1}\cdots c_l}$ (the matrix of the empty word is $I$). As $M_v\one=\one$, we have $\delta_c\one=0$ and $\lambda\one=0$ for every $\lambda\in D_k$. Recall that $\alpha^{\mathsf T}M_w\indv S=\alpha(Sw^{-1})$. (i) \emph{For a nonempty proper set $S$ and $k\geq0$, $m(S)\geq k+1$ if and only if $\lambda\indv S=0$ for every $\lambda\in D_k$.} If $\lambda\indv S=0$ for every $\lambda\in D_k$ and $|w|\leq k$, then every term of \eqref{eq:telescope} lies in $D_k$, as its suffix $c_{i+1}\cdots c_l$ has length at most $k-1$; so $\alpha(Sw^{-1})=\alpha(S)$. Conversely, let $m(S)\geq k+1$, let $c$ be a letter and $|v|\leq k-1$. Then $\delta_cM_v\indv S=\alpha(S(cv)^{-1})-\alpha(Sv^{-1})=0$, as both words $cv$ and $v$ are shorter than $m(S)$. (ii) \emph{$\dim D_k\geq\min(k,n-1)$.} If all $\delta_c$ were $0$, then $\alpha^{\mathsf T}M_w=\alpha^{\mathsf T}$ for every word $w$; but a reset word $w$ with $Q.w=\{r\}$ has $\alpha^{\mathsf T}M_w=\alpha(Q)\indv{\{r\}}^{\mathsf T}\neq\alpha^{\mathsf T}$, as $\alpha>0$ and $n\geq2$. So $\dim D_1\geq1$. A word $v$ with $1\leq|v|\leq k$ is $v'c$ with $|v'|\leq k-1$ and a letter $c$, and $\delta_{c'}M_v=(\delta_{c'}M_{v'})M_c$; so $D_{k+1}=D_1+\sum_cD_kM_c$. Hence $D_k=D_{k+1}$ implies $D_{k+1}=D_{k+2}$, and the chain $D_1\subseteq D_2\subseteq\cdots$ grows strictly until it becomes constant, equal to some $D$. Let $\xi$ be a column vector with $\lambda\xi=0$ for every $\lambda\in D$. By \eqref{eq:telescope}, $\alpha^{\mathsf T}M_w\xi=\alpha^{\mathsf T}\xi$ for every word $w$. As $\mathcal A$ is strongly connected, every state $r$ is the image of $Q$ under some word $w$ (a reset word followed by a path to $r$), and then $\alpha(Q)\xi_r=\alpha^{\mathsf T}\xi$. So $\xi$ is a multiple of $\one$, and $\dim D=n-1$. As $\dim D_1\geq1$ and the dimension grows by at least one at each step until it reaches $n-1$, (ii) follows. (iii) Let $2\leq j\leq n$ and $V=\{\xi: \lambda\xi=0\text{ for every }\lambda\in D_{n-j}\}$. By (ii), $\dim V\leq j$, and by (i), $\indv S\in V$ for every $S$ with $m(S)\geq n-j+1$. A subspace of dimension $\rho$ contains at most $2^\rho$ vectors with entries in $\{0,1\}$: at some $\rho$ coordinates the vectors of a basis form an invertible $\rho\times\rho$ matrix, so the projection to these coordinates is injective on the subspace, and it maps such vectors into $\{0,1\}^\rho$. As $V$ contains $\indv\varnothing=0$ and $\indv Q=\one$, at most $2^j-2$ nonempty proper sets $S$ have $m(S)\geq n-j+1$. The cases $j=2,3$ give the last sentence, as $m(S)\leq n-1$. \end{proof} \begin{remark}\label{rem:tier} The chain $L_i$ in the proof of Lemma~\ref{lem:step}(a) is Kari's argument \cite{Kar03}; it starts from one set. In the proof of \cite[Theorem~1]{Ber12}, Berlinkov uses instead the chain $U_{k+1}=\operatorname{span}\{\alpha^{\mathsf T}M_u:|u|\leq k\}$ (in our notation), which starts from $\alpha$ and so serves all sets at once. By \eqref{eq:telescope}, $U_{k+1}=\mathbb R\alpha^{\mathsf T}\oplus D_k$ (the sum is direct, since every vector of $D_k$ has entry sum $0$ and $\alpha^{\mathsf T}\one=\alpha(Q)\neq0$); so $D_k$ is Berlinkov's chain without the line of $\alpha^{\mathsf T}$, and the strict growth in part (ii) of the proof of Lemma~\ref{lem:tier} is his argument. Bounding the number of sets that need long extending words by counting $0/1$ vectors in a subspace is Szyku{\l}a's idea \cite[Section~2.8.3, Lemma~19 and Corollary~20]{Szy26}; it gives $\rt\leq n^2-n\log_2n+O(n)$ for Eulerian automata, and Szyku{\l}a remarks that it can be used in weighted variants. Letter weights play no role in Lemma~\ref{lem:tier}; stationarity is used only when a word of length $m(S)$ that raises $\alpha$ is needed (Lemma~\ref{lem:step}). \end{remark} \section{A stationary vector that is constant off one state}\label{sec:constant} \begin{theorem}\label{thm:constant} Let $\mathcal A$ be a synchronizing automaton with $n\geq2$ states. Suppose that, for some letter weights $p$, the matrix $M=\sum_bp_bM_b$ has a stationary vector $\alpha$ that is positive at every state and constant on $Q\setminus\{x\}$ for some state $x$. Then $\rt(\mathcal A)\leq(n-1)^2$. \end{theorem} The proof is at the end of this section, after Lemma~\ref{lem:levels} and Proposition~\ref{prop:caseA}. Throughout this section we assume the hypothesis of Theorem~\ref{thm:constant}. By Lemma~\ref{lem:positive}, $\mathcal A$ is strongly connected. Scale $\alpha$ so that $\alpha=1$ on $Q\setminus\{x\}$, and put $t=\alpha_x>0$ and $g=t-1$. Then \[\alpha(K)=|K|+g\,\ind{x\in K}\qquad(K\subseteq Q),\qquad \alpha(Q)=n-1+t.\] For a nonempty proper set $K$ we have $0<\alpha(K)<\alpha(Q)$, so Lemma~\ref{lem:step} applies with $\beta=\alpha$. Let $m(K)$ be the cost of $K$ for this $\alpha$: $m(K)\leq n-1$, and some word of length $m(K)$ raises $\alpha$. We write $\esc(K)=\esc_x(K)$. \begin{lemma}[levels]\label{lem:levels} Let $K,K'\subseteq Q$, $e=\ind{x\in K}$ and $e'=\ind{x\in K'}$. \begin{enumerate} \item $\alpha(K')-\alpha(K)=|K'|-|K|+g(e'-e)$. \item If $g\notin\mathbb Z$, then $\alpha(K')=\alpha(K)$ if and only if $|K'|=|K|$ and $e'=e$. So $m(K)$ is the least length of a word that changes $|Kw^{-1}|$ or moves $x$ across $K$; in particular $m(K)\leq\esc(K)$, and if a word of length $m(K)$ that raises $\alpha$ moves $x$ across $K$, then $m(K)=\esc(K)$. \item If $0\alpha(K)$ implies $|K'|\geq|K|$, with equality only if $x$ joins \textup{(}$e=0,e'=1$\textup{)} when $t>1$, and only if $x$ leaves \textup{(}$e=1,e'=0$\textup{)} when $t<1$. \end{enumerate} \end{lemma} \begin{proof} (a) is the formula for $\alpha$. (b) In (a), $|K'|-|K|$ is an integer and $g(e'-e)$ is not unless $e'=e$. (c) By (a), $|K'|-|K|>g(e-e')\geq-|g|>-1$, and $|K'|-|K|$ is an integer, so it is at least $0$; it is $0$ only if $g(e-e')<0$. \end{proof} In case (c) we call $K$ \emph{expensive} if $x\notin K$ (when $t>1$) or $x\in K$ (when $t<1$), and \emph{cheap} otherwise. So a raising word that keeps the size of an expensive set moves $x$ across it and makes it cheap, and a raising word always enlarges a cheap set. \begin{proposition}\label{prop:caseA} If $0\alpha(K)$; put $K_1=Kw_1^{-1}$. By Lemma~\ref{lem:levels}(c), $|K_1|\geq k$. If $|K_1|>k$, then $\ext(K)\leq m_1\leq n-1$; this is always the case when $K$ is cheap. Otherwise $K$ is expensive, $x$ moved across $K$, $K_1$ is cheap and $|K_1|=k$; by Lemma~\ref{lem:levels}(b) (it applies, as $0<|g|<1$) and Lemma~\ref{lem:orbit}, $m_1=\esc(K)\leq k$ if $t<1$ (then $x\in K$) and $m_1\leq n-k$ if $t>1$ (then $x\notin K$). Now let $w_2$ be a word of length $m_2=m(K_1)$ with $\alpha(K_1w_2^{-1})>\alpha(K_1)$. As $K_1$ is cheap, $|K_1w_2^{-1}|>k$. By Lemma~\ref{lem:levels}(b) and Lemma~\ref{lem:orbit} (finite, as $\mathcal A$ is strongly connected), $m_2\leq\esc(K_1)\leq n-k$ if $t<1$ (then $x\notin K_1$) and $m_2\leq k$ if $t>1$ (then $x\in K_1$). So $K(w_2w_1)^{-1}=K_1w_2^{-1}$ is larger than $K$, and $|w_2w_1|=m_1+m_2\leq n$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:constant}] As $\mathcal A$ is synchronizing and $n\geq2$, some letter $c$ is \emph{merging} (not injective): $|\{q\}c^{-1}|\geq2$ for some state $q$. \emph{Case $t=1$.} Then $\alpha=\one$, and Lemma~\ref{lem:step} gives $\ext(K)\leq n-1$ for every nonempty proper $K$. Start from $K_0=\{q\}c^{-1}$ and extend at most $n-2$ times: $\rt(\mathcal A)\leq1+(n-2)(n-1)$. (This is Kari's and Steinberg's bound \cite{Kar03,Ste11}.) \emph{Case $02$, not an integer.} Put $h=\lfloor g\rfloor\geq1$. Start from $K_0=\{x\}$, and while $K_j\neq Q$ let $K_{j+1}=K_jw_j^{-1}$ for a word $w_j$ of length $m(K_j)$ that raises $\alpha$. As $\alpha$ rises strictly and takes finitely many values, and $\alpha(K)<\alpha(Q)$ for $K\neq Q$, the process reaches $Q$; every $K_j$ is nonempty. Call a step $K\to K'$ \emph{keep} if $x\in K\cap K'$, \emph{free} if $x\notin K\cup K'$, \emph{lose} if $x\in K\setminus K'$, and \emph{gain} if $x\in K'\setminus K$. Put $\Phi(K)=|K|-h\,\ind{x\notin K}$; so $\Phi(\{x\})=1$ and $\Phi(Q)=n$. By Lemma~\ref{lem:levels}(a), (b) and Lemma~\ref{lem:orbit}: \begin{itemize} \item keep, free: $|K'|\geq|K|+1$, so $\Phi(K')-\Phi(K)\geq1$; the step costs at most $n-1$; \item lose: $|K'|>|K|+g$, so $|K'|\geq|K|+h+1$ and $\Phi(K')-\Phi(K)\geq1$; the step costs $\esc(K)\leq|K|$; \item gain: $|K'|>|K|-g$, so $|K'|\geq|K|-h$ and $\Phi(K')-\Phi(K)\geq0$; the step costs $\esc(K)\leq n-|K|$. \end{itemize} Since $x\in K_0$ and $x\in Q$, lose and gain steps alternate, starting with a lose step, and every lose step is followed later by a gain step. Pair each gain step with the lose step before it. If the lose step starts at a set of size $k_L$, it ends at a set of size at least $k_L+h+1$; between the two, only free steps occur, and they enlarge the set; so the gain step starts at a set of size $k_G\geq k_L+h+1$. The pair costs at most $k_L+n-k_G\leq n-1-h\leq n-2$, and raises $\Phi$ by at least one. So every keep step, every free step and every pair costs at most $n-1$ times its increase of $\Phi$, and the total length is at most $(n-1)(\Phi(Q)-\Phi(\{x\}))=(n-1)^2$. As $Q.(w_{J-1}\cdots w_0)\subseteq\{x\}$, $\rt(\mathcal A)\leq(n-1)^2$. These cases cover every $t>0$. Rationality of $p$ or $t$ is not used. \end{proof} \begin{remark}\label{rem:compare} When the stationary vector is rational (for example, for rational weights), Berlinkov's Corollary~1 in \cite{Ber12} gives $1+(n-1)(\Lambda-2)$, where $\Lambda$ is the least common multiple of the denominators of the normalized stationary vector $\alpha/\alpha(Q)$; under the hypothesis of Theorem~\ref{thm:constant} with an integer $t$, $\Lambda=n-1+t$, so this is $1+(n-1)(n+t-3)$: Kari's bound at $t=1$, $(n-1)^2+1$ at $t=2$, and more for larger $t$. Berlinkov's bound comes from a \emph{level count}: the integer vector $\Lambda\alpha/\alpha(Q)$ takes integer values on sets, the preimage of a state under a merging letter has value at least $2$, $Q$ has value $\Lambda$, and each extension step of at most $n-1$ letters raises the value by at least one. The integer case of the proof above is this level count started from $\{x\}$ instead of from a merging letter. For strongly connected automata with rational weights, Gusev and Pribavkina \cite[Corollary~18]{GP16} proved $\rt\leq W^2-3W+3$, where $W$ is the sum of the entries of the positive integer stationary vector with coprime entries; their Theorem~16, the bound $1+(n-1)(W-2)$, is Berlinkov's Corollary~1 above, as $W=\Lambda$. Under the hypothesis of Theorem~\ref{thm:constant} with $t=i/j$ in lowest terms, $W=(n-1)j+i$; so $W=n$ only for $t=1$, and otherwise $W\geq n+1$ and $W^2-3W+3\geq n^2-n+1>(n-1)^2$. For irrational $t$ their bound does not apply. \end{remark} \begin{example}[a larger family]\label{ex:degree3} Let $Q=\{0,1,2,3,4\}$ and let the letters $a,b$ map $0,1,2,3,4$ to $2,4,3,4,0$ and to $4,2,4,3,1$, respectively. With $p=(\frac12,\frac12)$ the vector $\alpha=(1,1,1,1,2)$ is stationary: the states $0$ and $1$ are entered only from $4$ (respectively by $a$ and $b$), the states $2$ and $3$ by two edges from $\{0,1,2,3\}$ each, and $4$ by four such edges. So Theorem~\ref{thm:constant} applies with $x=4$ and $t=2$. The automaton is not quasi-Eulerian of degree one or two. Indeed, the states $0$ and $1$ are entered by one edge each, and $4$ by two edges of each letter, so for no letter weights do they have in-weight one; hence $E\setminus\{s\}\subseteq\{2,3\}$ and $d\geq2$, and for $d=2$ the set $X$ contains $0$ or $1$, whose edges $0.a=2$ and $1.b=2$ leave $X\cup\{s\}=\{0,1,4\}$. The automaton is synchronizing, as $Q.(abaab)=\{4\}$. \end{example} \begin{example}[irrational weights]\label{ex:irrational} Let $Q=\{0,1,2\}$, let $a$ map every state to $0$, and let $b$ map $0,1,2$ to $1,2,1$. A stationary vector equal to $1$ off the state $2$ and to $t$ at $2$ exists exactly when $p_a(2+t)=1$ and $p_b(1+t)=1$, that is, when $t^2+t-1=0$; so $t=(\sqrt5-1)/2$ and $p_a=(3-\sqrt5)/2$. With the state $1$ in the role of $x$ one gets $t=\sqrt2$ and $p_b=1/\sqrt2$, and the state $0$ admits no such weights. So for this (trivially synchronizing) automaton every choice of $x$ needs irrational weights. \end{example} \section{Quasi-Eulerian automata of degree one}\label{sec:degree1} \begin{theorem}\label{thm:degree1} Every synchronizing quasi-Eulerian automaton of degree one with $n\geq2$ states has a reset word of length at most $(n-1)^2$. The \Cerny{} automata $C_n$ attain this bound. \end{theorem} The proof follows Lemma~\ref{lem:stat1}. Let $(E,s,p)$ be a witness of degree one, $X=\{x\}$. By Definition~\ref{def:qe}(a), every edge that starts at $x$ ends at $x$ or at $s$. Put \[z=\sum_{b:\,x.b=x}p_b,\qquad y=\sum_bp_b\,|\{q\in E: q.b=x\}|,\] the weight of the loops at $x$ and of the edges from $E$ into $x$. So $\mathrm{in}_p(x)=y+z$, and as the in-weights add up to $n$, $\mathrm{in}_p(s)=2-y-z$. \begin{lemma}\label{lem:stat1} If $z<1$, then the vector $\alpha$ with $\alpha=1$ on $E$ and $\alpha_x=t:=y/(1-z)$ is stationary. \end{lemma} \begin{proof} We check $(\alpha^{\mathsf T}M)_q=\alpha_q$. For $q\in E\setminus\{s\}$, every edge into $q$ starts in $E$, so $(\alpha^{\mathsf T}M)_q=\mathrm{in}_p(q)=1$. For $q=x$: $(\alpha^{\mathsf T}M)_x=y+zt=t(1-z)+zt=t$. The entries of $\alpha^{\mathsf T}M$ and of $\alpha$ have the same sum, as $M\one=\one$; so the entry at $s$ agrees too. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:degree1}] \emph{Case $z<1$ and $y>0$.} Then $t>0$, and $\alpha$ of Lemma~\ref{lem:stat1} is positive and constant on $Q\setminus\{x\}$: Theorem~\ref{thm:constant} gives $\rt(\mathcal A)\leq(n-1)^2$. By Lemma~\ref{lem:positive}, every automaton in this case is strongly connected. Conversely, if $\mathcal A$ is strongly connected, then the set $\{x\}$ is not closed, so $z<1$, and $E$ is not closed, so some edge from $E$ enters $x$ and $y>0$. So the two cases below are exactly the automata of the family that are not strongly connected. \emph{Case $z=1$.} Every letter fixes $x$. If $y=0$, then $E$ and $\{x\}$ are both closed, which is impossible in a synchronizing automaton; so $y>0$, and some letter $c$ maps a state of $E$ to $x$, so that $|\{x\}c^{-1}|\geq2$. Here $\mathrm{in}_p(x)=1+y$ and $\mathrm{in}_p(s)=1-y$, so for every set $T$ with $x\in T$, \[\textstyle\sum_bp_b|Tb^{-1}|=\sum_{q\in T}\mathrm{in}_p(q)=|T|+y\,(1-\ind{s\in T})\geq|T|.\] Let $K$ be a nonempty proper set with $x\in K$. Apply Lemma~\ref{lem:step} with $\beta=\one$: every set $T=Kv^{-1}$ contains $x$ (as $x.v=x$), so some word of length at most $n-1$ enlarges $K$. Every set $\{x\}w^{-1}$ contains $x$; start from $\{x\}c^{-1}$ and extend at most $n-2$ times: $\rt(\mathcal A)\leq1+(n-2)(n-1)$. \emph{Case $z<1$ and $y=0$.} No edge enters $x$ from $E$, so $E$ is closed. The automaton $\mathcal B$ obtained by restricting the letters to $E$ has $n-1$ states, and every state of $E$ has in-weight one in $\mathcal B$: for $r\in E\setminus\{s\}$ all edges into $r$ start in $E$, and the in-weight of $s$ in $\mathcal B$ is $\mathrm{in}_p(s)-(1-z)=(2-z)-(1-z)=1$. A reset word of $\mathcal A$ resets $\mathcal B$. As $z<1$, some letter $c$ has $x.c=s$; as $E$ is closed, $Q.c\subseteq E$. If $n=2$ then $E=\{s\}$, and $c$ is a reset word. If $n\geq3$, the case $t=1$ of the proof of Theorem~\ref{thm:constant} (with $\alpha=\one$) gives $\rt(\mathcal B)\leq1+(n-3)(n-2)$; as $Q.c\subseteq E$, the letter $c$ followed by a reset word of $\mathcal B$ resets $\mathcal A$, so $\rt(\mathcal A)\leq2+(n-3)(n-2)\leq1+(n-2)(n-1)\leq(n-1)^2$, where the middle inequality holds because $2n-5\geq0$. \emph{The bound is attained.} In $C_n$ (with $0.a=1$, $q.a=q$ for $00$ with sum one: both edges from $0$ end at $1$, every $r\in\{2,\ldots,n-1\}$ is entered exactly by $r.a=r$ and $(r-1).b=r$, so $\mathrm{in}_p(r)=1$. \Cerny{} proved $\rt(C_n)=(n-1)^2$ \cite{Cer64}. \end{proof} \begin{remark}\label{rem:steps} For $C_n$ we have $z=0$, $y=p_b$ and $t=p_b\in(0,1)$, the case of Proposition~\ref{prop:caseA}. The bound $1+(n-2)n$ of that case is attained. Let $K_0=\{1\}a^{-1}=\{0,1\}$, and let $K_{j+1}=K_jw_j^{-1}$, where $w_j$ is a word of length $\ext(K_j)$ with $|K_jw_j^{-1}|>|K_j|$, until $K_J=Q$; then $w_{J-1}\cdots w_0a$ is a reset word. Each step adds at least one state, so $J\leq n-2$, and $|w_j|\leq n$ by Proposition~\ref{prop:caseA}. As $\rt(C_n)=(n-1)^2=1+(n-2)n$, it follows that $J=n-2$ and that every step has length exactly $n$ and adds exactly one state (Figure~\ref{fig:chain} shows the chain for $n=4$). The conclusion of Proposition~\ref{prop:caseA} does not extend to $t=2$: a single extension may need more than $n$ letters, and the proof uses the level count of the integer case instead. For example, for $Q=\{0,1,2,3\}$, $a=(0,0,1,3)$ and $b=(3,1,3,2)$ (the images of $0,1,2,3$), the witness $E=\{0,1,2\}$, $s=2$, $x=3$, $p=(\frac12,\frac12)$ has $z=\frac12$, $y=1$, $t=2$, and $\ext(\{0,1,2\})=5>n$: a word $w$ enlarges this set exactly when $Q.w\subseteq\{0,1,2\}$; the word $aabab$ has $Q.(aabab)=\{1,2\}$, and for every word $w$ of length at most four the set $Q.w$ is one of $Q$, $\{0,1,3\}$, $\{1,2,3\}$, $\{0,3\}$, $\{2,3\}$ and $\{1,3\}$, so it contains the state $3$. The automaton is synchronizing (for example, $Q.(aababaa)=\{0\}$). \end{remark}\begin{remark}\label{rem:onecluster}The family of Theorem~\ref{thm:degree1} and the one-cluster automata (some letter has only one cycle) are incomparable. The automaton of Example~\ref{ex:degree3} is one-cluster (its letter $a$ has the single cycle $0\to2\to3\to4\to0$) but not quasi-Eulerian of degree one. The automaton on $\{0,1,2,3\}$ with $a=(0,2,1,0)$ and $b=(1,3,2,0)$ (the lists give the images of $0,1,2,3$) is synchronizing and quasi-Eulerian of degree one with $X=\{3\}$ and $s=0$ (both edges from $3$ end at $0$, and each of the states $1$ and $2$ is entered once by each letter), and the word $abbabba$ resets it; but each of its letters has two cycles: $a$ has the cycles $(0)$ and $(1\,2)$, and $b$ has $(0\,1\,3)$ and $(2)$.\end{remark} \section{Degree two}\label{sec:degree2} \subsection{Automata that are not strongly connected}\label{ssec:nonsc} \begin{theorem}\label{thm:nonsc} Let $\mathcal A$ be a synchronizing automaton with $n\geq3$ states that is quasi-Eulerian of degree at most two and not strongly connected. Then $\rt(\mathcal A)\leq(n-1)^2$. \end{theorem} The proof follows Lemmas~\ref{lem:weightcount} and~\ref{lem:push}. Let $(E,s,p)$ be a witness and $X=Q\setminus E$, $|X|\leq2$. Every state has out-weight $\sum_bp_b=1$. Two disjoint nonempty closed sets cannot exist in a synchronizing automaton (a reset word maps all states to one state), and the intersection of two closed sets is closed; so $\mathcal A$ has exactly one minimal nonempty closed set $C$. The restriction $\mathcal A|_C$ is strongly connected (by the minimality of $C$) and synchronizing, and every state reaches $C$ (a reset word maps every state to one state, which lies in $C$ because $C$ is closed). Put $R=Q\setminus C$; it is nonempty as $\mathcal A$ is not strongly connected. Let $\rt(\mathcal A|_C)=0$ if $|C|=1$. \begin{lemma}[weight count]\label{lem:weightcount} Let $T$ be a nonempty subset of $E\setminus\{s\}$ such that every edge that ends in $T$ starts in $T$. Then $T$ is closed. \end{lemma} \begin{proof} The in-weights on $T$ are one, so the edges that end in $T$ carry total weight $|T|$; they all start in $T$. The edges that start in $T$ also carry total weight $|T|$. So the edges from $T$ to $Q\setminus T$ carry weight $0$, and as all $p_b>0$ there are none. \end{proof} \begin{lemma}[push]\label{lem:push} $\rt(\mathcal A)\leq|R|^2+\rt(\mathcal A|_C)$. \end{lemma} \begin{proof} Let $S$ be the current image, starting with $S=Q$. While $S$ meets $R$, take $q\in S\setminus C$ and a shortest word $u$ with $q.u\in C$; its path visits distinct states of $R$ before it enters $C$, so $|u|\leq|R|$. As $C$ is closed, $S.u\setminus C\subseteq(S\setminus C).u\setminus C$; the set $(S\setminus C).u$ has at most $|S\setminus C|$ elements, and one of them, $q.u$, lies in $C$; so $|S.u\setminus C|\leq|S\setminus C|-1$. After at most $|R|$ such words, of total length at most $|R|^2$, the image lies in $C$, and a reset word of $\mathcal A|_C$ maps it to one state. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:nonsc}] \emph{Case $s\in C$.} Let $T=R\cap(E\setminus\{s\})$. An edge that ends in $T$ starts in $R$ (as $C$ is closed), not in $X$ (edges from $X$ end in $X\cup\{s\}$), and not at $s$ (as $s\in C$); so it starts in $T$. By Lemma~\ref{lem:weightcount}, $T$ is closed if it is nonempty; then it contains a minimal nonempty closed set other than $C$, which is impossible. So $T=\varnothing$ and $R\subseteq X$; so $|R|\in\{1,2\}$ and $E\subseteq C$; put $\ell=|C|=n-|R|$. In $\mathcal A|_C$ every state of $E\setminus\{s\}$ keeps in-weight one (all its in-edges start in $E\subseteq C$), and every edge from $X\cap C$ ends in $(X\cap C)\cup\{s\}$. If $\ell=1$, $\rt(\mathcal A|_C)=0$. If $X\cap C=\{x'\}$ and $\ell\geq2$, $\mathcal A|_C$ is quasi-Eulerian of degree one, and Theorem~\ref{thm:degree1} gives $\rt(\mathcal A|_C)\leq(\ell-1)^2$. If $X\cap C=\varnothing$ and $\ell\geq2$, then $C=E$; the in-weights of $\mathcal A|_C$ add up to $\ell$ and equal one on $E\setminus\{s\}$, so they equal one at $s$ too, $\one$ is a positive stationary vector of $\mathcal A|_C$, and Theorem~\ref{thm:constant} gives $\rt(\mathcal A|_C)\leq(\ell-1)^2$. By Lemma~\ref{lem:push}, \[\rt(\mathcal A)\leq|R|^2+(n-1-|R|)^2\leq(n-1)^2,\] since $(n-1)^2-(n-1-j)^2=j(2n-2-j)\geq j^2$ for $1\leq j\leq n-1$, here with $j=|R|$. \emph{Case $s\in R$.} If some $x\in X$ lies in $C$, its edges end in $X\cup\{s\}$ and in $C$, hence in $X\cap C$; so $X\cap C$ is closed, and by minimality $C=X\cap C\subseteq X$. If $X\cap C=\varnothing$, then $C\subseteq E\setminus\{s\}$. The edges that end in $C$ carry total weight $|C|$, and the edges from $C$ (all of which end in $C$) already carry weight $|C|$; so no edge enters $C$ from $R$, which is impossible as every state reaches $C$. So $C\subseteq X$. If $|C|=1$, Lemma~\ref{lem:push} gives $\rt(\mathcal A)\leq(n-1)^2$. If $C=X$, then $\rt(\mathcal A|_C)=1$ (a synchronizing automaton with two states) and $\rt(\mathcal A)\leq(n-2)^2+1\leq(n-1)^2$. \end{proof} \begin{remark}\label{rem:nonsc-general} Lemma~\ref{lem:push} and the proof above that $R\subseteq X$ or $C\subseteq X$ do not use $d=2$. So for a synchronizing quasi-Eulerian automaton of any degree $d$ that is not strongly connected, either $C\subseteq X$, or $R\subseteq X$ and the strongly connected automaton $\mathcal A|_C$, with $n-|R|$ states, is quasi-Eulerian of degree $d-|R|$ or has the positive stationary vector $\one$; in each case $\rt(\mathcal A)\leq|R|^2+\rt(\mathcal A|_C)$. As $j^2+(n-1-j)^2\leq(n-1)^2$ for $1\leq j\leq n-1$, the \Cerny{} bound for automata of degree $d$ that are not strongly connected reduces to Theorem~\ref{thm:constant}, the bound for strongly connected automata of degree at most $d-1$, and the bound for automata with at most $d$ states; for $d\leq2$ all three hold (Theorems~\ref{thm:constant} and~\ref{thm:degree1}, and automata with at most two states), and this gives Theorem~\ref{thm:nonsc}. \end{remark} \subsection{The stationary vector of a strongly connected automaton} Berlinkov observed in the proof of \cite[Theorem~2]{Ber12} that the stationary vector is constant on $E$; the next lemma gives it explicitly. \begin{lemma}\label{lem:statd} Let $\mathcal A$ be strongly connected and quasi-Eulerian of degree $d\geq1$ with witness $(E,s,p)$, $X=Q\setminus E$. Let $Z$ be the $X\times X$ matrix with $Z_{xx'}=\sum_{b:\,x.b=x'}p_b$, and $y\in\mathbb R^X$ the row vector with $y_x=\sum_bp_b|\{q\in E:q.b=x\}|$. Then $I-Z$ is invertible, and the vector $\alpha$ with $\alpha=1$ on $E$ and $\alpha|_X=t:=y(I-Z)^{-1}$ \textup{(}a row vector\textup{)} is a stationary vector with $\alpha_q>0$ for every $q$. \end{lemma} \begin{proof} The matrix $Z$ is nonnegative with row sums at most one. If $I-Z$ were singular, then $1$ would be an eigenvalue of $Z$, and as the spectral radius of $Z$ is at most its largest row sum, it would be one; by the Perron--Frobenius theorem $Z\eta=\eta$ for some $\eta\geq0$, $\eta\neq0$. Let $Y$ be the set of $x\in X$ with $\eta_x=\max\eta>0$. For $x\in Y$, $\eta_x=\sum_{x'}Z_{xx'}\eta_{x'}\leq\max\eta\sum_{x'}Z_{xx'}\leq\max\eta$; equality forces $\sum_{x'}Z_{xx'}=1$ and $Z_{xx'}=0$ for $x'\notin Y$, so every letter maps $x$ into $Y$. Then $Y$ is a nonempty closed set other than $Q$ (as $s\notin Y$), which is impossible. So $I-Z$ is invertible and $t$ is defined. For $r\in E\setminus\{s\}$ all edges into $r$ start in $E$, so $(\alpha^{\mathsf T}M)_r=\mathrm{in}_p(r)=1$; for $x\in X$, $(\alpha^{\mathsf T}M)_x=y_x+(tZ)_x=t_x$; the entry at $s$ agrees as both vectors have the same sum. As $\mathcal A$ is strongly connected and $p>0$, $M$ is irreducible, and its stationary vectors are the multiples of one positive vector; $\alpha$ is one of them, and $\alpha=1$ on $E\neq\varnothing$, so $\alpha>0$. \end{proof} \subsection{A congruence}\label{ssec:block} \begin{proposition}\label{prop:block} Let $\mathcal A$ be synchronizing and quasi-Eulerian of degree two with witness $(E,s,p)$ and $X=\{x_1,x_2\}$. Suppose that for every letter $b$, either $x_1.b=x_2.b$ or $\{x_1.b,x_2.b\}=X$. Then $\rt(\mathcal A)\leq(n-1)^2$, and if $\mathcal A$ is strongly connected, $\rt(\mathcal A)\leq(n-2)^2+1$. \end{proposition} \begin{proof} If $\mathcal A$ is not strongly connected, Theorem~\ref{thm:nonsc} applies. Let it be strongly connected, and let $\alpha$ be the vector of Lemma~\ref{lem:statd}. The partition of $Q$ into $X$ and singletons is a congruence by the hypothesis; let $\mathcal A'$ be the quotient automaton, with $n-1\geq2$ states. It is synchronizing (every reset word of $\mathcal A$ resets it). Some letter $c_0$ has $x_1.c_0=x_2.c_0$, since otherwise $X$ would be closed. If $w$ resets $\mathcal A'$, then $Q.w$ lies in one block of the partition, and $Q.(wc_0)$ is a single state; so $\rt(\mathcal A)\leq\rt(\mathcal A')+1$. Let $\alpha'$ be the lumped vector: $\alpha'=1$ on $E$ and $\alpha'_X=t_1+t_2>0$. For a block $D$ of the partition, $\ind{q.b\in D}$ is the same for all states $q$ of any one block, so $(\alpha'^{\mathsf T}M')_D=\sum_B\alpha'_B\sum_bp_b\ind{B.b\subseteq D}=\sum_q\alpha_q\sum_bp_b\ind{q.b\in D}=\sum_{q'\in D}(\alpha^{\mathsf T}M)_{q'}=\alpha(D)=\alpha'_D$, where $B$ runs over the blocks, $\alpha'_B=\alpha(B)$, and $M'$ is the weighted matrix of $\mathcal A'$ with the same weights. So $\alpha'$ is positive, stationary and constant off one state of $\mathcal A'$, and Theorem~\ref{thm:constant} gives $\rt(\mathcal A')\leq(n-2)^2$. \end{proof} \subsection{Binary automata}\label{ssec:binary} From now on $\Sigma=\{a,b\}$, $\mathcal A$ is strongly connected and synchronizing with $n\geq4$ states, and $(E,s,p)$ is a witness of degree two with $X=\{x_1,x_2\}$. (For $n\leq3$ every synchronizing automaton has $\rt\leq(n^3-n)/6\leq(n-1)^2$ \cite{Pin83,Fra82}.) \begin{lemma}\label{lem:gadget} \begin{enumerate} \item The weights $p=(\frac12,\frac12)$ are admissible for $(E,s)$. \item With these weights, exactly two edges lead from $E$ into $X\cup\{s\}$ \textup{(}the \emph{boundary edges}\textup{)}, and the vector $t$ of Lemma~\ref{lem:statd} depends only on the \emph{configuration} \[(x_1.a,\ x_1.b,\ x_2.a,\ x_2.b;\ \nu_1,\nu_2),\qquad x_i.c\in\{x_1,x_2,s\},\] where $\nu_i$ is the number of boundary edges that end at $x_i$: $Z_{ij}=\frac12|\{c:x_i.c=x_j\}|$ and $y_i=\frac{\nu_i}2$. \end{enumerate} \end{lemma} \begin{proof} (a) For $r\in E\setminus\{s\}$ let $i_c(r)=|\{r\}c^{-1}|$, and call $(i_a(r),i_b(r))$ the \emph{type} of $r$. In-weight one means $p_ai_a(r)+p_bi_b(r)=1$. If $i_a(r)=i_b(r)$, this forces $i_a(r)=i_b(r)=1$ and holds for all $p$. Otherwise it reads $p_a(i_a(r)-i_b(r))=1-i_b(r)$ and forces $p_a$ to one value; as $00$; up to renaming they form $49$ configurations, and their classes $\{t_1,t_2\}$ are exactly the $14$ of Table~\ref{tab:classes}. \end{lemma}\input{proof_classes} By Lemma~\ref{lem:statd} the configuration of every witness of degree two of a strongly connected binary automaton is among these $49$. \begin{table}[ht] \small \caption{The 14 classes $\{t_1,t_2\}$ of binary witnesses of degree two; for each, the number of configurations (up to renaming) and the result that gives $\rt\leq(n-1)^2$. A \emph{block} configuration satisfies the hypothesis of Proposition~\ref{prop:block}.}\label{tab:classes} \begin{tabular}{@{}lcl@{}} \toprule class $\{t_1,t_2\}$ & configurations & bound $(n-1)^2$ from\\ \midrule $\{1,1\}$ & $13$ & Kari and Steinberg \cite{Kar03,Ste11} (also Theorem~\ref{thm:constant})\\ $\{1/2,1\}$, $\{1,2\}$ & $6$, $7$ & Theorem~\ref{thm:constant} ($\alpha$ is constant off one state)\\ $\{1/4,1/2\}$, $\{1/2,3/4\}$ & $1$ each & Prop.~\ref{prop:generic}\\ $\{1/3,2/3\}$, $\{2/3,4/3\}$ & $2$ each & one block (Prop.~\ref{prop:block}), one by Prop.~\ref{prop:third}\\ $\{1/2,2\}$, $\{3/2,2\}$ & $1$ each & Prop.~\ref{prop:two}\\ $\{2,2\}$, $\{2,3\}$, $\{2,4\}$ & $5$, $2$, $2$ & Prop.~\ref{prop:integer} (tier lemma; $4\leq n\leq6$ by \cite{KKS16})\\ $\{1/2,1/2\}$ & $4$ & two blocks (Prop.~\ref{prop:block}); two open\\ $\{1/2,3/2\}$ & $2$ & one block (Prop.~\ref{prop:block}); one open\\ \bottomrule \end{tabular} \end{table}\input{tab_configs_float} \begin{theorem}\label{thm:binary} Let $\mathcal A$ be a binary, strongly connected, synchronizing automaton that is quasi-Eulerian of degree two. Suppose that some witness of $\mathcal A$ has a configuration other than the following three \textup{(}up to renaming, in the notation of Table~\ref{tab:configs}\textup{)}: $(s,x_1,x_1,s;0,1)$ and $(s,s,x_1,x_1;0,1)$ in the class $\{\frac12,\frac12\}$, and $(s,x_1,x_1,s;1,1)$ in the class $\{\frac12,\frac32\}$. Then $\rt(\mathcal A)\leq(n-1)^2$. \end{theorem} \begin{proof}[Proof of Theorem~\ref{thm:binary}] For $n\leq3$ see the start of this subsection. For $n\geq4$ the bound follows from Theorem~\ref{thm:constant} in the classes $\{1,1\}$, $\{\frac12,1\}$ and $\{1,2\}$, since one of $t_1,t_2$ equals $1$, and from Proposition~\ref{prop:block} in the block configurations; in Table~\ref{tab:configs}, those outside these three classes are, up to renaming, $(s,s,s,s;1,1)$ and $(s,x_1,s,x_1;0,1)$ in $\{\frac12,\frac12\}$, $(s,x_2,s,x_1;0,1)$ in $\{\frac13,\frac23\}$, $(s,x_2,s,x_1;0,2)$ in $\{\frac23,\frac43\}$, and $(s,x_1,s,x_1;1,1)$ in $\{\frac12,\frac32\}$. The remaining six configurations are treated in Propositions~\ref{prop:generic}--\ref{prop:two}, and the nine configurations of the integer classes $\{2,2\}$, $\{2,3\}$, $\{2,4\}$ in Proposition~\ref{prop:integer}, with the tier lemma (Lemma~\ref{lem:tier}). These propositions are proved below, after the definitions they use. \end{proof} For the rest of this section we replace $p$ by the weights $(\frac12,\frac12)$, admissible by Lemma~\ref{lem:gadget}(a), and fix the stationary vector $\alpha$ of Lemma~\ref{lem:statd} for them ($\alpha=1$ on $E$, $\alpha_{x_i}=t_i>0$); the class $\{t_1,t_2\}$ of the witness always refers to these weights. Put $g_i=t_i-1$. For a set $K$ let $e_i(K)=\ind{x_i\in K}$, $e_s(K)=\ind{s\in K}$, and call $P(K)=(e_1(K),e_2(K),e_s(K))$ the \emph{pattern} of $K$ and $(e_1(K),e_2(K))$ its \emph{$X$-part}; then $\alpha(K)=|K|+g_1e_1(K)+g_2e_2(K)$. For a nonempty proper $K$ let $m(K)$ be the cost of $K$ for this $\alpha$; by Lemma~\ref{lem:step}, $m(K)\leq n-1$ and some word of length $m(K)$ raises $\alpha$. For a state $q$ let $\esc_q(K)$ be the least length of a word that moves $q$ across $K$, as in Lemma~\ref{lem:orbit}. We use the following extension process. From a nonempty proper set $K_0$, replace $K$ by $Kw^{-1}$ for a word $w$ of length $m(K)$ that raises $\alpha$, until $Q$ is reached. The values $\alpha(K)$ of the visited sets increase strictly; so no set is visited twice, every visited set is nonempty (as $\alpha(K)\geq\alpha(K_0)>0$), and the process reaches $Q$. Each value is carried by at most one visited set. The words, read from the last to the first, map $Q$ into $K_0$. So if $K_0$ is a singleton, or $K_0=\{q\}c^{-1}$ for a letter $c$, then $\rt(\mathcal A)$ is at most $\sum m(K)$ over the visited proper sets $K$, plus $0$, or plus $1$, respectively. For a letter $c$, $e_i(Kc^{-1})=\ind{x_i.c\in K}$ with $x_i.c\in X\cup\{s\}$; so the change of $(e_1,e_2)$ under $c$ depends only on $P(K)$. Call a pattern \emph{good} if for some letter $c$ and some (equivalently, every) set $K$ with this pattern the number $g_1(e_1(Kc^{-1})-e_1(K))+g_2(e_2(Kc^{-1})-e_2(K))$ is not an integer. Then $\alpha(Kc^{-1})-\alpha(K)$ is an integer plus a non-integer, so $m(K)=1$ for every set $K$ with a good pattern. The patterns $(1,1,1)$ and $(0,0,0)$ are called \emph{aligned}; they are never good: for them $X\cup\{s\}$ lies in $K$ or is disjoint from $K$, and both letters map $x_1$ and $x_2$ into $X\cup\{s\}$, so no letter changes $e_1$ or $e_2$. \begin{lemma}[joint orbit]\label{lem:joint} Let $K$ be a nonempty proper set, and $k=|K|$. Suppose first that $P(K)=(1,1,1)$. Then $\esc_s(K)\leq k-2$, and $x_1.w,x_2.w\in K$ for every word $w$ with $|w|\leq\esc_s(K)$. If the pattern $(1,1,0)$ is good, then $m(K)\leq k-1$. Symmetrically, if $P(K)=(0,0,0)$, then $\esc_s(K)\leq n-k-2$, and if $(0,0,1)$ is good, then $m(K)\leq n-k-1$. \end{lemma} \begin{proof} Let $f$ be the least length of a word $w$ with $q.w\notin K$ for some $q\in\{x_1,x_2,s\}$; it is finite as $\mathcal A$ is strongly connected. If it were attained at $q=x_i$ with $w=cw'$, then $q.c\in X\cup\{s\}$ and $(q.c).w'\notin K$ with $|w'|=f-1$, a contradiction. So $f=\esc_s(K)$, and $x_1.w,x_2.w\in K$ whenever $|w|\leq f$. Let $R_j=\{q.w: q\in\{x_1,x_2,s\},\ |w|\leq j\}$. Then $R_{f-1}\subseteq K$, and the chain $R_0\subsetneq R_1\subsetneq\cdots\subsetneq R_{f-1}$ is strict, since $R_j=R_{j+1}$ would make $R_j\subseteq K$ a closed proper subset. As $|R_0|=3$, $f+2\leq k$. Let $w$ have length $f$ with $s.w\notin K$; then $P(Kw^{-1})=(1,1,0)$, and $P(Kv^{-1})=(1,1,1)$ for $|v|1\geq\alpha(\{q\})$ for every state $q$, so every visited set has size between $2$ and $n-1$. Finally, we bound the cost of the visited sets of each size. Let $2\leq k\leq n-1$. A visited set of size $k$ with $X$-part $(1,1)$ costs at most $k-1$ if it contains $s$ (Lemma~\ref{lem:joint}; the pattern $(1,1,0)$ is good) and $1$ otherwise; one with $X$-part $(0,0)$ costs at most $n-k-1$ if it avoids $s$ and $1$ otherwise, and it does not exist for $k=n-1$; the other two cost $1$. So the visited sets of size $k$ cost at most $n$ in total, and $\rt(\mathcal A)\leq1+\sum_{k=2}^{n-1}n=1+(n-2)n$. \end{proof} \begin{proposition}\label{prop:third} If the witness has, up to renaming, the configuration $(s,x_2,x_1,s;0,1)$ \textup{(}class $\{\frac13,\frac23\}$\textup{)} or $(s,x_2,x_1,s;0,2)$ \textup{(}class $\{\frac23,\frac43\}$\textup{)}, that is, $x_1.a=s$, $x_1.b=x_2$, $x_2.a=x_1$, $x_2.b=s$, then $\rt(\mathcal A)\leq n^2-3n+5\leq(n-1)^2$. \end{proposition} \begin{proof} Here one ($\{\frac13,\frac23\}$) or two ($\{\frac23,\frac43\}$) boundary edges end at $x_2$ (in $\{\frac13,\frac23\}$ the other one ends at $s$), and $(g_1,g_2)=(-\frac23,-\frac13)$, resp. $(-\frac13,\frac13)$. Under $a$, $e_1$ becomes $e_s$ and $e_2$ becomes $e_1$. For the six patterns that are not aligned, the change of $(e_1,e_2)$ under $a$ is $(-1,1)$, $(0,-1)$, $(1,0)$, $(-1,0)$, $(0,1)$ or $(1,-1)$, and $g_1$, $g_2$ and $g_1-g_2$ are not integers; so every pattern that is not aligned is good. Moreover $g_1+g_2$ is an integer ($-1$, resp. $0$): the $X$-parts $(1,1)$ and $(0,0)$ give integer values of $\alpha$, and $(1,0)$, $(0,1)$ give non-integer values; a set with a non-integer value has a pattern that is not aligned and costs $1$. \emph{The class $\{\frac23,\frac43\}$.} Here $\alpha(K)=|K|$ for the $X$-parts $(1,1)$ and $(0,0)$, and $\alpha(Q)=n$. Start from $K_0=\{q\}c^{-1}$ for a merging letter $c$; $\alpha(K_0)\geq2+g_1=\frac53$. An integer value $N\in\{2,\ldots,n-1\}$ is carried by a set of size $N$; it costs at most $\max(N-1,n-N-1)$ by Lemma~\ref{lem:joint} if it is aligned, and $1$ otherwise. With $j=N-1$ and $\ell=n-2$, $\sum_{j=1}^{\ell}\max(j,\ell-j)\leq(\ell-1)^2+\ell$, since every term except $j=\ell$ is at most $\ell-1$. The non-integer values in $[\frac53,n)$ are $k\pm\frac13$ with $2\leq k\leq n-1$ (a set with $X$-part $(1,0)$ or $(0,1)$ has at most $n-1$ states); there are $2(n-2)$ of them. So $\rt(\mathcal A)\leq1+(n-3)^2+(n-2)+2(n-2)=n^2-3n+4$. \emph{The class $\{\frac13,\frac23\}$.} Here $\alpha(K)=|K|-1$ for the $X$-part $(1,1)$, $\alpha(K)=|K|$ for $(0,0)$, and $\alpha(Q)=n-1$. Start from $K_0=\{q\}c^{-1}$ for a merging letter $c$; $\alpha(K_0)\geq2+g_1+g_2=1$. An integer value $N\in\{1,\ldots,n-2\}$ is carried by a set of size $N+1$ with $X$-part $(1,1)$, which costs at most $N$ if it contains $s$ (Lemma~\ref{lem:joint}) and $1$ otherwise, or by a set of size $N$ with $X$-part $(0,0)$, which costs at most $n-N-1$ if it avoids $s$ and $1$ otherwise. For $N=1$ the first set is $X$ itself (cost $1$), and for $N=n-2$ the second set is $E$, which contains $s$ (cost $1$); so the value $N$ costs at most $n-2$ for $N\in\{1,n-2\}$ and at most $n-3$ otherwise. The non-integer values in $[1,n-1)$ number at most $2(n-2)$. So $\rt(\mathcal A)\leq1+2(n-2)+(n-4)(n-3)+2(n-2)=n^2-3n+5$. \end{proof} \begin{proposition}\label{prop:two} If the witness has class $\{\frac12,2\}$ or $\{\frac32,2\}$, then $\rt(\mathcal A)\leq n^2-3n+5\leq(n-1)^2$. \end{proposition} \begin{proof} Each of these two classes contains exactly one configuration (Lemma~\ref{lem:classes} and Table~\ref{tab:configs}): after renaming, it is $(s,x_1,x_1,x_1;1,1)$ in $\{\frac12,2\}$ and $(s,x_2,x_1,x_1;1,1)$ in $\{\frac32,2\}$. That is, $x_2.a=x_2.b=x_1$, one boundary edge ends at $x_1$ and one at $x_2$, $x_1.a=s$, and $x_1.b=x_1$ in $\{\frac12,2\}$, $x_1.b=x_2$ in $\{\frac32,2\}$. By the formula in the proof of Lemma~\ref{lem:classes}, $(t_1,t_2)=(2,\frac12)$, resp. $(2,\frac32)$; so $g_1=1$, and $\alpha(K)=|K|+e_1(K)+g_2e_2(K)$ with $g_2=-\frac12$, resp. $\frac12$. (i) As $g_1=1$ is an integer and $g_2$ is not, $\alpha$ changes whenever $x_2$ moves across $K$: $m(K)\leq\esc_{x_2}(K)$. (ii) Under either letter, $e_2$ becomes $e_1$; so a pattern is good if and only if $e_1\neq e_2$. (iii) Let $e_1(K)=e_2(K)$. As both letters map $x_2$ to $x_1$, $\esc_{x_2}(K)=1+\esc_{x_1}(K)$. If $e_s(K)\neq e_1(K)$, then $\esc_{x_1}(K)=1$ (by the letter $a$), so $m(K)\leq2$. If $K$ is aligned, then $\esc_{x_1}(K)=1+\esc_s(K)$: in $\{\frac12,2\}$ a word moves $x_1$ across $K$ only after it has left $x_1$ through the edge to $s$ (the letter $b$ fixes $x_1$, and $x_1.a=s$); in $\{\frac32,2\}$, $\esc_{x_1}(K)=1+\min(\esc_s(K),\esc_{x_2}(K))$, and the minimum is $\esc_s(K)$, since otherwise $\esc_{x_1}(K)=1+\esc_{x_2}(K)=2+\esc_{x_1}(K)$. So $m(K)\leq2+\esc_s(K)$, which is at most $|K|$ if $P(K)=(1,1,1)$ and at most $n-|K|$ if $P(K)=(0,0,0)$, by Lemma~\ref{lem:joint}. Start from $K_0=\{x_1\}$, with $\alpha(K_0)=2$ and a good pattern (cost $1$). Each value of $\alpha$ is carried by at most one visited set, so for each value above $2$ and below $\alpha(Q)$ we list the sets that can carry it and bound their costs by (ii) and (iii); Table~\ref{tab:costs} collects them.\input{tab_costs_float} \emph{The class $\{\frac12,2\}$.} Here $\alpha(K)=|K|+e_1-\frac12e_2$ and $\alpha(Q)=n+\frac12$. An integer value $N$ (so $e_2=0$) is carried by a set of size $N$ with $X$-part $(0,0)$, which costs at most $n-N$ if it is aligned (such a set misses $x_1$, $x_2$ and $s$, so $N\leq n-3$) and at most $2$ otherwise, or by a set of size $N-1$ with $X$-part $(1,0)$ (cost $1$). A value $N+\frac12$ is carried by a set of size $N$ with $X$-part $(1,1)$, which costs at most $N$ if it is aligned (such a set contains $x_1$, $x_2$ and $s$, so $N\geq3$) and at most $2$ otherwise, or by a set of size $N+1$ with $X$-part $(0,1)$ (cost $1$). The values above $2$ and below $n+\frac12$ are the integers $3,\ldots,n$ and $N+\frac12$ for $2\leq N\leq n-1$. So the total cost is at most $1$ (the start), plus $n-N$ for $3\leq N\leq n-3$, $2$ for $N=n-2$ and $1$ for each of $N=n-1,n$ (a set with $X$-part $(0,0)$ has at most $n-2$ states), plus $2$ for the value $\frac52$ and $N$ for $N+\frac12$, $3\leq N\leq n-1$: \[\rt(\mathcal A)\leq1+\Bigl(4+\sum_{j=3}^{n-3}j\Bigr)+\Bigl(2+\sum_{N=3}^{n-1}N\Bigr)=n^2-3n+4\qquad(n\geq6);\] the same count gives $8$ for $n=4$ and $14$ for $n=5$, so $\rt(\mathcal A)\leq n^2-3n+4$ for every $n\geq4$. \emph{The class $\{\frac32,2\}$.} Here $\alpha(K)=|K|+e_1+\frac12e_2$ and $\alpha(Q)=n+\frac32$. An integer value needs $e_2=0$, so for a proper set it is at most $(n-1)+1=n$. An integer value $N$ is carried by a set of size $N$ with $X$-part $(0,0)$, which costs at most $n-N$ if it is aligned (such a set misses $x_1$, $x_2$ and $s$, so $N\leq n-3$) and at most $2$ otherwise, or by a set of size $N-1$ with $X$-part $(1,0)$ (cost $1$). A value $N+\frac12$ with $2\leq N\leq n$ is carried by a set of size $N$ with $X$-part $(0,1)$ (cost $1$), or, if $N\geq3$, by a set of size $N-1$ with $X$-part $(1,1)$, which costs at most $N-1$ if it is aligned (such a set contains $x_1$, $x_2$ and $s$, so $N\geq4$) and at most $2$ otherwise. So the total cost is at most $1$ (the start), plus $4+\sum_{j=3}^{n-3}j$ for the integer values, as in $\{\frac12,2\}$, plus $1$ for the value $\frac52$, $2$ for $\frac72$ and $N-1$ for $N+\frac12$, $4\leq N\leq n$: \[\rt(\mathcal A)\leq1+\Bigl(4+\sum_{j=3}^{n-3}j\Bigr)+\Bigl(1+2+\sum_{j=3}^{n-1}j\Bigr)=n^2-3n+5\qquad(n\geq6);\] the same count gives $9$ for $n=4$ and $15$ for $n=5$, so $\rt(\mathcal A)\leq n^2-3n+5$ for every $n\geq4$. In both classes the bound is at most $(n-1)^2$. \end{proof} \begin{proposition}\label{prop:integer} Let $\mathcal A$ be a binary, strongly connected, synchronizing automaton with $n\geq4$ states that has a witness of degree two in the class $\{2,2\}$, $\{2,3\}$ or $\{2,4\}$. Then $\rt(\mathcal A)\leq(n-1)^2$, and $\rt(\mathcal A)\leq n^2-3n+8$ if $n\geq7$. \end{proposition} \begin{proof} Here $t_1$ and $t_2$ are integers and $\min(t_1,t_2)=2$, so $\alpha$ takes integer values on sets. Let $x_*$ be an exceptional state with $t_*:=\alpha_{x_*}=\max(t_1,t_2)$; then $\alpha(Q)=n-2+t_1+t_2=n+t_*$. \emph{Case $n\geq7$.} Start the process from $K_0=\{x_*\}$, with $\alpha(K_0)=t_*$. The visited proper sets $K_0,\ldots,K_{J-1}$ have strictly increasing integer values $\alpha(K_i)$ in $[t_*,\alpha(Q)-1]=[t_*,n+t_*-1]$; so they are distinct, and $J\leq n$. Let $\mu_1\geq\mu_2\geq\cdots\geq\mu_J$ be their costs $m(K_i)$ in decreasing order. By Lemma~\ref{lem:step}, $\mu_i\leq n-1$; by Lemma~\ref{lem:tier}, at most two of the sets cost $n-1$ and at most six cost $n-2$ or more, so $\mu_3\leq n-2$ and $\mu_7\leq n-3$. Put $\kappa_1=\kappa_2=n-1$, $\kappa_3=\cdots=\kappa_6=n-2$ and $\kappa_i=n-3$ for $7\leq i\leq n$. Then $\mu_i\leq\kappa_i$ for $i\leq J$, and every $\kappa_i\geq1$; as $K_0$ is a singleton, \[\textstyle\rt(\mathcal A)\leq\sum_{i=1}^J\mu_i\leq\sum_{i=1}^n\kappa_i=2(n-1)+4(n-2)+(n-6)(n-3)=n^2-3n+8\leq(n-1)^2,\] where the last inequality holds because $n\geq7$. \emph{Case $4\leq n\leq6$.} The automaton $\mathcal A$ is binary and has at most six states, so $\rt(\mathcal A)\leq(n-1)^2$ by the computation of Kisielewicz, Kowalski and Szyku{\l}a \cite{KKS16}, who verified the \Cerny{} conjecture for all binary automata with at most $12$ states. \end{proof} For comparison, Berlinkov's Corollary~1 in \cite{Ber12} gives $1+(n-1)(n+t_1+t_2-4)$ in these three classes, that is, $n^2-n+1$, $n^2$ and $n^2+n-1$; the level count alone, with every step costing at most $n-1$, gives $n(n-1)$. The argument for $n\geq7$ in the proof above applies more generally. \begin{corollary}\label{cor:integer} Let $\mathcal A$ be a synchronizing automaton with $n\geq7$ states, over any alphabet. Suppose that, for some letter weights $p$, the matrix $M=\sum_bp_bM_b$ has a stationary vector $\alpha$ whose entries are positive integers with $\alpha(Q)-\max_q\alpha_q\leq n$. Then $\rt(\mathcal A)\leq n^2-3n+8\leq(n-1)^2$. In particular, this holds for every synchronizing strongly connected automaton with $n\geq7$ states that has a witness of degree two in an integer class $\{2,k\}$, $k$ a positive integer. \end{corollary} \begin{proof} By Lemma~\ref{lem:positive}, $\mathcal A$ is strongly connected. Let $x_*$ be a state with $\alpha_{x_*}=\max_q\alpha_q$. The case $n\geq7$ of the proof of Proposition~\ref{prop:integer}, with the extension process and the costs taken for this $\alpha$, uses only that $\mathcal A$ is synchronizing and strongly connected and that $\alpha$ is a positive stationary vector with integer entries; the values of the visited proper sets now lie in $[\alpha_{x_*},\alpha(Q)-1]$, so again $J\leq\alpha(Q)-\alpha_{x_*}\leq n$, and the bound follows. For the last statement, the vector $\alpha$ of Lemma~\ref{lem:statd} has the integer entries $1$, $2$ and $k$, and $\alpha(Q)-\max_q\alpha_q=n+k-\max(2,k)\leq n$. \end{proof} \section{Open cases}\label{sec:open} For three families of quasi-Eulerian automata it remains open whether every member satisfies the \Cerny{} bound: (a) binary strongly connected automata of degree two all of whose witnesses have one of the three configurations excluded in Theorem~\ref{thm:binary}; (b) strongly connected automata of degree two over at least three letters none of whose witnesses has a block of a congruence as its exceptional pair, $1$ in its class or, for $n\geq7$, a class $\{2,k\}$ with $k$ an integer (Proposition~\ref{prop:block}, Theorem~\ref{thm:constant}, Corollary~\ref{cor:integer}); (c) automata of degree $d\geq3$. In (a), only $n\geq13$ is open: the computation of \cite{KKS16} covers all binary automata with at most $12$ states. For these three configurations, Lemma~\ref{lem:joint} still bounds the cost of the aligned sets; what is missing is a bound, sharper than the general $n-1$, for the cost of the sets whose pattern is neither aligned nor good. For strongly connected automata of degree $d\geq3$, the bound $2^d(n-d+1)(n-1)$ of \cite{Ber13} is the best bound recorded in \cite[item D3]{Vol26} for fixed $d$ and large $n$; for $d$ close to $n$ the general cubic bounds are smaller, since every automaton with $n\geq2$ states is quasi-Eulerian of degree $n-1$ (with $E=\{s\}$). \begin{question} Does every synchronizing quasi-Eulerian automaton of degree two satisfy $\rt\leq(n-1)^2$? Does every synchronizing automaton with a positive stationary vector, for some letter weights, that takes only two values satisfy it? \end{question} Theorem~\ref{thm:constant} answers the second question when one of the two values is taken at a single state. \section*{Acknowledgments} This work was done overwhelmingly by AI models, steered by the author in a continuous critical dialogue, alternating between Anthropic's Claude and OpenAI's ChatGPT. The author takes full responsibility for the paper. \begin{thebibliography}{99} \bibitem{Ber12} M. V. Berlinkov, \emph{Synchronizing automata on quasi Eulerian digraph}, arXiv:1203.3402v1 (2012; statement numbers as in this version); conference version in: Implementation and Application of Automata (CIAA 2012), Lecture Notes in Comput. Sci. 7381, Springer (2012), 90--100. \bibitem{Ber13} M. V. Berlinkov, \emph{Synchronizing quasi-Eulerian and quasi-one-cluster automata}, Internat. J. Found. Comput. Sci. 24(6) (2013), 729--745. \bibitem{Cer64} J. \v{C}ern\'y, \emph{Pozn\'amka k homog\'ennym experimentom s kone\v{c}n\'ymi automatmi}, Mat.-Fyz. \v{C}asopis Sloven. Akad. Vied 14(3) (1964), 208--216; English translation: \emph{A note on homogeneous experiments with finite automata}, J. Autom. Lang. Comb. 24(2--4) (2019), 123--132. \bibitem{CPR71} J. \v{C}ern\'y, A. Pirick\'a and B. Rosenauerov\'a, \emph{On directable automata}, Kybernetika 7(4) (1971), 289--298. \bibitem{Fra82} P. Frankl, \emph{An extremal problem for two families of sets}, European J. Combin. 3(2) (1982), 125--127. \bibitem{GP16} V. V. Gusev and E. V. Pribavkina, \emph{On synchronizing colorings and the eigenvectors of digraphs}, in: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs 58 (2016), 48:1--48:14. \bibitem{Kar03} J. Kari, \emph{Synchronizing finite automata on Eulerian digraphs}, Theoret. Comput. Sci. 295(1--3) (2003), 223--232. \bibitem{KKS16} A. Kisielewicz, J. Kowalski and M. Szyku{\l}a, \emph{Experiments with synchronizing automata}, in: Implementation and Application of Automata (CIAA 2016), Lecture Notes in Comput. Sci. 9705, Springer (2016), 176--188; arXiv:1607.04025. \bibitem{Pin83} J.-E. Pin, \emph{On two combinatorial problems arising from automata theory}, Ann. Discrete Math. 17 (1983), 535--548. \bibitem{Shi19} Y. Shitov, \emph{An improvement to a recent upper bound for synchronizing words of finite automata}, J. Autom. Lang. Comb. 24(2--4) (2019), 367--373. \bibitem{Ste11} B. Steinberg, \emph{The averaging trick and the \v{C}ern\'y conjecture}, Internat. J. Found. Comput. Sci. 22(7) (2011), 1697--1706. \bibitem{Szy18} M. Szyku{\l}a, \emph{Improving the upper bound on the length of the shortest reset word}, in: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96 (2018), 56:1--56:13. \bibitem{Szy26} M. Szyku{\l}a, \emph{Synchronizing automata: open problems}, in: 17th International Conference on Automata and Formal Languages (AFL 2026), EPTCS 451 (2026), 33--47; arXiv:2608.24245. \bibitem{Vol08} M. V. Volkov, \emph{Synchronizing automata and the \v{C}ern\'y conjecture}, in: Language and Automata Theory and Applications (LATA 2008), Lecture Notes in Comput. Sci. 5196, Springer (2008), 11--27. \bibitem{Vol22} M. V. Volkov, \emph{Synchronization of finite automata}, Russian Math. Surveys 77(5) (2022), 819--891. \bibitem{Vol26} M. V. Volkov, \emph{List of results on the \v{C}ern\'y conjecture and reset thresholds for synchronizing automata}, arXiv:2508.15655v4 (2026). \bibitem{Zhu26} Y. Zhu, \emph{The \v{C}ern\'y conjecture for one-cluster automata via annular spectral descent}, arXiv:2607.19675 (2026). \end{thebibliography} \end{document}