Introduction
The Černý (1969) conjecture states that if some word maps all n n n states of an automaton to one state, then some such word has length at most ( n − 1 ) 2 (n-1)^2 ( 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.
Background
A (complete deterministic) automaton A = ( Q , Σ ) \mathcal{A}=(Q,\Sigma) A = ( Q , Σ ) has a finite nonempty set Q Q Q of n n n states and a finite nonempty alphabet Σ \Sigma Σ ; every letter maps Q Q Q to Q Q Q ; we write q . b q.b q . b for the image of a state q q q under a letter b b b , and call q → q . b q \to q.b q → q . b an edge with label b b b . The automaton is synchronizing if some word, a reset word , maps all states to one state; the least length of a reset word is the reset threshold rt ( A ) \operatorname{rt}(\mathcal{A}) rt ( A ) . In 1964 Černý [3 ] described automata C n C_n C n with n n n states, two letters and rt ( C n ) = ( n − 1 ) 2 \operatorname{rt}(C_n)=(n-1)^2 rt ( C n ) = ( n − 1 ) 2 : on Q = { 0 , … , n − 1 } Q=\{0,\ldots,n-1\} Q = { 0 , … , n − 1 } the letter a a a maps 0 0 0 to 1 1 1 and fixes every other state, and b b b maps q q q to q + 1 m o d n q+1 \bmod n q + 1 mod n (Figure 1 , right). He stated the conjecture in a talk in 1969, and it first appeared in print in [4 ] (see [14 Section 1] and, for its history, [15 Section 3.1] ). It is open in general: the best known upper bounds are cubic, from Pin and Frankl’s ( n 3 − n ) / 6 (n^3-n)/6 ( n 3 − n ) /6 [9 , 5 ] to the small improvements of Szykuła [12 ] and Shitov [10 ] . The conjecture has been proved for many special families of automata; Volkov’s list [16 ] records them, together with the families for which only a quadratic bound is known. Kari [7 ] proved r t ≤ 1 + ( n − 2 ) ( n − 1 ) r_t \le1 + (n-2)(n-1) r t ≤ 1 + ( n − 2 ) ( n − 1 ) for Eulerian automata (strongly connected, with every state entered by exactly ∣ Σ ∣ |\Sigma| ∣Σ∣ edges), and Steinberg [11 ] extended this to pseudo-Eulerian automata : strongly connected automata with positive letter weights for which every state receives total weight one. Berlinkov [1 , 2 ] introduced the following generalization.
Figure 1. Left: a witness ( E , s , p ) (E,s,p) ( E , s , p ) of degree two (Definition 1.1 ; p p p gives the letter weights). Every state of E E E other than s s s has in-weight one, every edge that starts in the set X X X of exceptional states ends in X ∪ { s } X \cup\{s\} X ∪ { s } , and edges from E E E may enter X X X (dotted); only some edges are drawn. Right: the Černý automaton C 4 C_4 C 4 (letter a a a solid, letter b b b dashed) with the witness of degree one used in Theorem 4.1 : x = 0 x=0 x = 0 , s = 1 s=1 s = 1 and E = { 1 , 2 , 3 } E=\{1,2,3\} E = { 1 , 2 , 3 } .
Definition 1.1 (Berlinkov [1 , 2 ] ; see [16 item D3] ). An automaton A = ( Q , Σ ) \mathcal{A}=(Q,\Sigma) A = ( Q , Σ ) is quasi-Eulerian of degree d d d if there are a set E ⊆ Q E\subseteq Q E ⊆ Q with ∣ E ∣ = n − d |E|=n-d ∣ E ∣ = n − d , a state s ∈ E s\in E s ∈ E and letter weights p = ( p b ) b ∈ Σ p=(p_b)_{b\in\Sigma} p = ( p b ) b ∈ Σ with p b > 0 p_b>0 p b > 0 and ∑ b p b = 1 \sum_b p_b=1 ∑ b p b = 1 such that
(a) every edge that starts in X : = Q ∖ E X:=Q\setminus E X := Q ∖ E ends in X ∪ { s } X\cup\{s\} X ∪ { s } , and
(b) every state r ∈ E ∖ { s } r\in E\setminus\{s\} r ∈ E ∖ { s } has in-weight one: ∑ b ∈ Σ p b ∣ { q ∈ Q : q . b = r } ∣ = 1 \sum_{b\in\Sigma}p_b|\{q\in Q:q.b=r\}|=1 ∑ b ∈ Σ p b ∣ { q ∈ Q : q . b = r } ∣ = 1 .
We call ( E , s , p ) (E,s,p) ( E , s , p ) a witness , X X X its exceptional states , and p p p admissible .
The Černý automata are quasi-Eulerian of degree one [1 Section 4] , [16 item D3] , so ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 is the best possible bound for this family (Figure 1). For a strongly connected synchronizing quasi-Eulerian automaton of degree d d d , Berlinkov proved r t ( A ) ≤ 2 d ( n − d + 1 ) ( n − 1 ) r_t(\mathcal{A})\le2^d(n-d+1)(n-1) r t ( A ) ≤ 2 d ( n − d + 1 ) ( n − 1 ) [2 Theorem 8] (see also [1 Theorem 2] ).
Admissible weights p p p give the row-stochastic matrix M = ∑ b p b M b M=\sum_b p_bM_b M = ∑ b p b M b , where M b M_b M b is the 0 / 1 0/1 0/1 transition matrix of the letter b b b , and a stationary vector is a nonzero vector α \alpha α with α T M = α T \alpha^{\mathsf{T}}M=\alpha^{\mathsf{T}} α T M = α T (Section 2). For a strongly connected automaton it can be taken equal to 1 on E E E and positive on the exceptional states (Lemma 5.5). In degree two we write t 1 , t 2 t_1,t_2 t 1 , t 2 for its values on the two exceptional states and call the unordered pair { t 1 , t 2 } \{t_1,t_2\} { t 1 , t 2 } the class of the witness. For binary automata (two letters, Σ = { a , b } \Sigma=\{a,b\} Σ = { a , b } ) of degree two, the configuration of the witness records where the four edges that start at the exceptional states end, and how many edges from E E E enter each exceptional state. For a strongly connected binary automaton the class is always computed with the weights ( 1 2 , 1 2 ) (\frac{1}{2},\frac{1}{2}) ( 2 1 , 2 1 ) , which are then admissible (Lemma 5.7); 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 5.8 and Table 1). The two exceptional states form a block of a congruence if every letter maps them to one state or to the pair itself (Proposition 5.6).
Results
The table compares our main results with the best results known before this paper.
Table 1.
We prove the Černý (1969) conjecture for quasi-Eulerian automata of degree one (Berlinkov’s family, Definition 1.1): every synchronizing one has r t ≤ ( n − 1 ) 2 r_t\le(n-1)^2 r t ≤ ( n − 1 ) 2 , and the Černý automata attain this bound (Theorem 4.1, proved in Section 4). The best bound before was 2 n ( n − 1 ) 2n(n-1) 2 n ( n − 1 ) , for strongly connected ones [2 ] . Strong connectivity is not assumed: if the automaton is not
strongly connected, then either every letter fixes the exceptional state or E E E is closed (no edge leaves E E E ), and in both cases Kari’s argument gives r t ≤ 1 + ( n − 2 ) ( n − 1 ) rt \le1 + (n-2)(n-1) r t ≤ 1 + ( n − 2 ) ( n − 1 ) .
We improve Berlinkov’s bound 2 n ( n − 1 ) 2n(n-1) 2 n ( n − 1 ) [1 Proposition 4] to ( n − 1 ) 2 (n-1)^2 ( 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 3.1, proved in § 3 ). This family contains every strongly connected synchronizing quasi-Eulerian automaton of degree one (by Berlinkov’s observation in the proof of [1 Theorem 2] and Lemma 4.2 ), and others (Example 3.5).
Degree two. We prove r t ≤ ( n − 1 ) 2 rt \le(n-1)^2 r t ≤ ( n − 1 ) 2 for every synchronizing quasi-Eulerian automaton of degree two that is not strongly connected (Theorem 5.1 , proved in § 5.1 ), for every one whose two exceptional states form a block of a congruence (Proposition 5.6, § 5.3 ), and for binary strongly connected ones in 46 of the 49 configurations, which include every configuration of 12 of the 14 classes (Theorem 5.9 , proved in § 5.4 ; Figure 2 ). For the three classes { 2 , 2 } \{2,2\} { 2 , 2 } , { 2 , 3 } \{2,3\} { 2 , 3 } and { 2 , 4 } \{2,4\} { 2 , 4 } and at most six states, the bound follows from the computation of Kisielewicz, Kowalski and Szykuła [8 ] , who verified the Černý conjecture for all binary automata with at most 12 states. For n ≥ 7 n \ge7 n ≥ 7 , Corollary 5.15 also gives the bound in the integer classes { 2 , k } \{2,k\} { 2 , k } (k k k a positive integer) over every alphabet. The best bound before was Berlinkov’s 4 ( n − 1 ) 2 4(n-1)^2 4 ( n − 1 ) 2 for strongly connected ones [2 Theorem 8] ; [16 item D3] lists it without that hypothesis.
Figure 2. Green squares: the bound ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 is known for all n n n ; grey squares with a question mark: it is known only for n ≤ 12 n \le12 n ≤ 12 [8 ] . The squares are the 49 configurations of Lemma 5.8 (binary strongly connected automata of degree two), in rows by class { t 1 , t 2 } \{t_1,t_2\} { t 1 , t 2 } (Table 1). Left: before this paper, the bound ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 was known for all n n n only in the class { 1 , 1 } \{1,1\} { 1 , 1 } , where the stationary vector is constant [7 , 11 ] ; Berlinkov’s bound 4 ( n − 1 ) 2 4(n-1)^2 4 ( n − 1 ) 2 [2 ] holds in all of them. Right: after this paper; each row names the results that give ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 , and the three grey squares are the configurations excluded in Theorem 5.9 .
Recently Zhu Zhu [17 ] announced a proof of the conjecture for one-cluster automata (some letter has only one cycle; [16 item D1] ). This family and the family of Theorem 4.1 are incomparable (Remark 4.4).
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 [7 ] , with letter weights as in Steinberg’s averaging trick [11 ] and with Berlinkov’s stationary vector α \alpha α as the measure of a set [1 ] , finds for a nonempty proper set K K K a word w w w of at most n − 1 n-1 n − 1 letters that raises α \alpha α : the preimage K w − 1 Kw^{-1} K w − 1 has α ( K w − 1 ) > α ( K ) \alpha(Kw^{-1}) > \alpha(K) α ( K w − 1 ) > α ( K ) . Here α ( K ) = ∑ q ∈ K α q \alpha(K)=\sum_{q\in K}\alpha_q α ( K ) = ∑ q ∈ K α q , and α \alpha α is a stationary vector of the weighted transition matrix (Lemma 2.2 ). When α \alpha α is constant off one state x x x , a raising word either enlarges the set or moves x x x from one side of the set to the other. The key observation is that such moves are short. By the orbit lemma (Lemma 2.3 ), an elementary bound on shortest paths, a shortest word that moves x x x across a set K K K has length at most ∣ K ∣ |K| ∣ K ∣ if x ∈ K x \in K x ∈ K , and at most n − ∣ K ∣ n-|K| n − ∣ K ∣ if x ∉ K x \notin K x ∈ / K . Scale α \alpha α so that α = 1 \alpha=1 α = 1 off x x x , and put t = α x t=\alpha_x t = α x . When 0 < t < 2 0<t<2 0 < t < 2 and t ≠ 1 t\ne1 t = 1 , a raising word never shrinks the set, and it keeps the size only by moving x x x across the set; and every word that moves x x x across a set changes α \alpha α , as set sizes are integers and t − 1 t-1 t − 1 is not. So a move of x x x and the step that follows it cost at most ∣ K ∣ |K| ∣ K ∣ and n − ∣ K ∣ n-|K| n − ∣ K ∣ letters (in this order if t < 1 t<1 t < 1 , in the reverse order if t > 1 t>1 t > 1 ), by the orbit lemma, and at most n n n together. After a first letter that merges two states, at most n − 2 n-2 n − 2 enlargements of at most n n n letters each give 1 + ( n − 2 ) n = ( n − 1 ) 2 1+(n-2)n=(n-1)^2 1 + ( n − 2 ) n = ( n − 1 ) 2 . Figure 3 shows these steps for the Černý automaton C 4 C_4 C 4 , where every bound is attained.
Figure 3. The extension method on the Černý automaton C 4 C_4 C 4 of Figure 1 (right), with the exceptional state x = 0 x = 0 x = 0 (thick circle). Each box shows a set of states; its members are grey; an arrow labelled c c c goes from a set K K K to its preimage K c − 1 Kc^{-1} K c − 1 . As in Remark 4.3, t = α x < 1 t = \alpha_x < 1 t = α x < 1 , and each row, read from right to left, spells its word: the merging letter a a a , then w 0 = a b b b w_0 = abbb w 0 = abbb , then w 1 = a b b b w_1 = abbb w 1 = abbb ; the reset word w 1 w 0 a = a b b b a b b b a w_1w_0a = abbb\ abbb\ a w 1 w 0 a = abbb abbb a has length 1 + ( n − 2 ) n = 9 = ( 4 − 1 ) 2 1 + (n - 2)n = 9 = (4 - 1)^2 1 + ( n − 2 ) n = 9 = ( 4 − 1 ) 2 for n = 4 n = 4 n = 4 . The braces mark the two bounds of the orbit lemma (Lemma 2.3) used in the proof of Proposition 3.3: in each extension both are attained, so it costs exactly n n n letters.
When t > 2 t>2 t > 2 is not an integer, we pair a move of x x 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 t-1 t − 1 states, and the set does not shrink before the move back, so the two moves together cost at most n − 2 n-2 n − 2 letters, and a potential-function count gives ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 . When t t t is an integer, α \alpha α takes integer values on sets, so every step raises α \alpha α by at least one, and at most n − 1 n-1 n − 1 steps of at most n − 1 n-1 n − 1 letters lead from { x } \{x\} { x } to Q Q Q (§ 3 ). Theorem 4.1 follows (§ 4 ): Lemma 4.2 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 C C : either C C C consists of exceptional states, or the restriction to C C C is quasi-Eulerian of degree one or has the all-ones stationary vector 1 \mathbf{1} 1 . The set R R R of the other states is moved into C C C by at most ∣ R ∣ 2 |R|^2 ∣ R ∣ 2 letters (Lemma 5.3 ), and ∣ R ∣ 2 + ( n − 1 − ∣ R ∣ ) 2 ≤ ( n − 1 ) 2 |R|^2+(n-1-|R|)^2\le(n-1)^2 ∣ R ∣ 2 + ( n − 1 − ∣ R ∣ ) 2 ≤ ( 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 3.1 (Proposition 5.6). In the binary case, call the cost of a set K K K the least length of a word w w w with α ( K w − 1 ) ≠ α ( K ) \alpha(Kw^{-1})\ne\alpha(K) α ( K w − 1 ) = α ( K ) , and its pattern the record of which of x 1 x_1 x 1 , x 2 x_2 x 2 and s s s it contains. The configuration determines, from the pattern alone, whether α ( K c − 1 ) − α ( K ) \alpha(Kc^{-1})-\alpha(K) α ( K c − 1 ) − α ( K ) is not an integer for some letter c c c ; then K K K costs one letter. A joint orbit of x 1 x_1 x 1 , x 2 x_2 x 2 and s s s (Lemma 5.10 ) 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, 2\} { 2 , 2 } , { 2 , 3 } \{2, 3\} { 2 , 3 } and { 2 , 4 } \{2, 4\} { 2 , 4 } of degree two we also use the tier lemma (Lemma 2.4): for 2 ≤ j ≤ n 2 \le j \le n 2 ≤ j ≤ n , at most 2 j − 2 2^j - 2 2 j − 2 nonempty proper sets have cost at least n − j + 1 n - j + 1 n − j + 1 . Its proof counts 0/1 vectors in a subspace, as in Szykuła’s improvement for Eulerian automata [13 Section 2.8.3] .
Organization
Section 2 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 3 proves Theorem 3.1 and Section 4 proves Theorem 4.1. Section 5 treats degree two, and Section 6 lists the open cases.
Preliminaries
Automata and preimages
Let A = ( Q , Σ ) \mathcal{A} = (Q, \Sigma) A = ( Q , Σ ) be an automaton with ∣ Q ∣ = n |Q| = n ∣ Q ∣ = n . Words act on the right: q . ( u v ) = ( q . u ) . v q.(uv) = (q.u).v q . ( uv ) = ( q . u ) . v . For K ⊆ Q K \subseteq Q K ⊆ Q and a word w w w , the preimage is K w − 1 = { q ∈ Q : q . w ∈ K } Kw^{-1} = \{q \in Q : q.w \in K\} K w − 1 = { q ∈ Q : q . w ∈ K } , so that
K ( u v ) − 1 = ( K v − 1 ) u − 1 . K(uv)^{-1} = (Kv^{-1})u^{-1}. K ( uv ) − 1 = ( K v − 1 ) u − 1 .
A set K K K is closed if K . b ⊆ K K.b \subseteq K K . b ⊆ K for every letter b b b ; A \mathcal{A} A is strongly connected if ∅ \varnothing ∅ and Q Q Q are its only closed sets. If K 0 ⊆ Q K_0 \subseteq Q K 0 ⊆ Q and K j + 1 = K j w j − 1 K_{j+1} = K_jw_j^{-1} K j + 1 = K j w j − 1 for j < J j < J j < J with K J = Q K_J = Q K J = Q , then K J = K 0 ( w J − 1 ⋯ w 1 w 0 ) − 1 K_J = K_0(w_{J-1} \cdots w_1w_0)^{-1} K J = K 0 ( w J − 1 ⋯ w 1 w 0 ) − 1 , that is, Q . ( w J − 1 ⋯ w 0 ) ⊆ K 0 Q.(w_{J-1} \cdots w_0) \subseteq K_0 Q . ( w J − 1 ⋯ w 0 ) ⊆ K 0 . This is the extension method: if K 0 K_0 K 0 is a singleton, w J − 1 ⋯ w 0 w_{J-1} \cdots w_0 w J − 1 ⋯ w 0 is a reset word, and if K 0 = { q } c − 1 K_0 = \{q\}c^{-1} K 0 = { q } c − 1 for a letter c c c , then w J − 1 ⋯ w 0 c w_{J-1} \cdots w_0c w J − 1 ⋯ w 0 c is one.
For a nonempty proper set K K K let ext ( K ) \operatorname{ext}(K) ext ( K ) be the least length of a word w w w with ∣ K w − 1 ∣ > ∣ K ∣ |Kw^{-1}| > |K| ∣ K w − 1 ∣ > ∣ K ∣ (infinite if there is none).
For a word w w w let M w M_w M w be the Q × Q Q \times Q Q × Q matrix with ( M w ) q , q ′ = 1 (M_w)_{q,q'} = 1 ( M w ) q , q ′ = 1 if q . w = q ′ q.w = q' q . w = q ′ and 0 otherwise. Then M u v = M u M v M_{uv} = M_uM_v M uv = M u M v , M w 1 = 1 M_w\mathbf{1} = \mathbf{1} M w 1 = 1 , and M w 1 K = 1 K w − 1 M_w\mathbf{1}_K = \mathbf{1}_{Kw^{-1}} M w 1 K = 1 K w − 1 , where 1 K \mathbf{1}_K 1 K is the indicator column vector of K K K and 1 = 1 Q \mathbf{1} = \mathbf{1}_Q 1 = 1 Q . For β ∈ R Q \beta\in\mathbb{R}^{Q} β ∈ R Q write β ( K ) = ∑ q ∈ K β q \beta(K) = \sum_{q \in K} \beta_q β ( K ) = ∑ q ∈ K β q ; then β T M w 1 K = β ( K w − 1 ) \beta^{T}M_w\mathbf{1}_K = \beta(Kw^{-1}) β T M w 1 K = β ( K w − 1 ) . For a statement P P P , we write [ P ] [P] [ P ] for the number that is 1 if P P P holds and 0 otherwise.
Letter weights and stationary vectors
Letter weights are numbers p b > 0 p_b > 0 p b > 0 (b ∈ Σ b \in\Sigma b ∈ Σ ) with ∑ b p b = 1 \sum_b p_b = 1 ∑ b p b = 1 ; they need not be rational. Put M = ∑ b p b M b M = \sum_b p_bM_b M = ∑ b p b M b , a row-stochastic matrix: the transition matrix of the random walk on Q Q Q that applies the letter b b b with probability p b p_b p b . A stationary vector is a nonzero α ∈ R Q \alpha\in\mathbb{R}^{Q} α ∈ R Q with α T M = α T \alpha^{T}M = \alpha^{T} α T M = α T ; then
∑ b p b α ( T b − 1 ) = α T M 1 T = α ( T ) for every T ⊆ Q . (1) \sum_b p_b\alpha(Tb^{-1}) = \alpha^{T}M\mathbf{1}_T = \alpha(T) \qquad\text{for every } T \subseteq Q. \tag*{(1)} b ∑ p b α ( T b − 1 ) = α T M 1 T = α ( T ) for every T ⊆ Q . (1)
We give an edge with label b b b the weight p b p_b p b . The in-weight of a state q q q is in p ( q ) = ∑ b p b ∣ { q } b − 1 ∣ \operatorname{in}p(q) = \sum_b p_b|\{q\}b^{-1}| in p ( q ) = ∑ b p b ∣ { q } b − 1 ∣ , the total weight of the edges that end at q q q ; the edges that start at a state have total weight ∑ b p b = 1 \sum_b p_b = 1 ∑ b p b = 1 , its out-weight , so the in-weights add up to n n n . So α = 1 \alpha= \mathbf{1} α = 1 is stationary if and only if every in-weight is one.
Lemma 2.1 (strong connectivity). Let A \mathcal{A} A be synchronizing , let p p p be letter weights, and let α \alpha α be a stationary vector with α q > 0 \alpha_q > 0 α q > 0 for every q q q . Then A \mathcal{A} A is strongly connected.
Proof. Let C C C be a nonempty closed set. For q ′ ∈ Q q' \in Q q ′ ∈ Q let π ( q ′ ) = ∑ b : q ′ . b ∈ C p b \pi(q') = \sum_{b:q'.b\in C}p_b π ( q ′ ) = ∑ b : q ′ . b ∈ C p b ; so π ( q ′ ) = 1 \pi(q') = 1 π ( q ′ ) = 1 for q ′ ∈ C q' \in C q ′ ∈ C . Summing the stationary equations over C C C gives α ( C ) = ∑ q ′ α q ′ π ( q ′ ) = α ( C ) + ∑ q ′ ∉ C α q ′ π ( q ′ ) \alpha(C) = \sum_{q'}\alpha_{q'}\pi(q') = \alpha(C) + \sum_{q'\notin C}\alpha_{q'}\pi(q') α ( C ) = ∑ q ′ α q ′ π ( q ′ ) = α ( C ) + ∑ q ′ ∈ / C α q ′ π ( q ′ ) , so π ( q ′ ) = 0 \pi(q') = 0 π ( q ′ ) = 0 for every q ′ ∉ C q' \notin C q ′ ∈ / C (as $\alpha > 0): no letter takes a state outside C C C into C C C , and Q ∖ C Q \setminus C Q ∖ C is closed too. A reset word maps all states to one state, which lies in C C C and in Q ∖ C Q \setminus C Q ∖ C if both are nonempty. So C = Q C = Q C = Q . □
Lemma 2.2 (the extension step; Kari [7 ] , Steinberg [11 ] , Berlinkov [1 Theorem 1] ). Let A \mathcal{A} A be synchronizing , let β ∈ R Q \beta\in\mathbb{R}^{Q} β ∈ R Q with β ( Q ) ≠ 0 \beta(Q) \ne0 β ( Q ) = 0 , and let K ⊆ Q K \subseteq Q K ⊆ Q with β ( K ) ∉ { 0 , β ( Q ) } \beta(K) \notin\{0,\beta(Q)\} β ( K ) ∈ / { 0 , β ( Q )} . Let m m m be the least length of a word w w w with β ( K w − 1 ) ≠ β ( K ) \beta(Kw^{-1}) \ne\beta(K) β ( K w − 1 ) = β ( K ) .
(a) The number m m m exists, and 1 ≤ m ≤ n − 1 1 \le m \le n - 1 1 ≤ m ≤ n − 1 .
(b) Let p p p be letter weights, and suppose that ∑ b p b β ( T b − 1 ) ≥ β ( T ) \sum_b p_b\beta(Tb^{-1}) \ge\beta(T) ∑ b p b β ( T b − 1 ) ≥ β ( T ) for every set T = K v − 1 T = Kv^{-1} T = K v − 1 with ∣ v ∣ = m − 1 |v| = m - 1 ∣ v ∣ = m − 1 . Then some word w w w of length m m m has β ( K w − 1 ) > β ( K ) \beta(Kw^{-1}) > \beta(K) β ( K w − 1 ) > β ( K ) .
In particular, if α \alpha α is a stationary vector for some letter weights, with α ( Q ) ≠ 0 \alpha(Q) \ne0 α ( Q ) = 0 and α ( K ) ∉ { 0 , α ( Q ) } \alpha(K) \notin\{0,\alpha(Q)\} α ( K ) ∈ / { 0 , α ( Q )} , then some word w w w of length at most n − 1 n - 1 n − 1 has α ( K w − 1 ) > α ( K ) \alpha(Kw^{-1}) > \alpha(K) α ( K w − 1 ) > α ( K ) , and the least such length equals the least length of a word that changes α ( K w − 1 ) \alpha(Kw^{-1}) α ( K w − 1 ) .
Proof. (a) A reset word u u u gives K u − 1 ∈ { ∅ , Q } Ku^{-1} \in\{\varnothing,Q\} K u − 1 ∈ { ∅ , Q } , so β ( K u − 1 ) ∈ { 0 , β ( Q ) } \beta(Ku^{-1}) \in\{0,\beta(Q)\} β ( K u − 1 ) ∈ { 0 , β ( Q )} differs from β ( K ) \beta(K) β ( K ) ; hence m m m exists, and m ≥ 1 m \ge1 m ≥ 1 . Put ζ K = 1 K − β ( K ) β ( Q ) 1 \zeta_K = \mathbf{1}_K - \frac{\beta(K)}{\beta(Q)}\mathbf{1} ζ K = 1 K − β ( Q ) β ( K ) 1 . Since M w 1 = 1 M_w\mathbf{1} = \mathbf{1} M w 1 = 1 , β T M w ζ K = β ( K w − 1 ) − β ( K ) \beta^{T}M_w\zeta_K = \beta(Kw^{-1}) - \beta(K) β T M w ζ K = β ( K w − 1 ) − β ( K ) . Also ζ K ≠ 0 \zeta_K \ne0 ζ K = 0 , since K ∉ { ∅ , Q } K \notin\{\varnothing,Q\} K ∈ / { ∅ , Q } . Let L i = span { M w ζ K : ∣ w ∣ ≤ i } L_i = \operatorname{span}\{M_w\zeta_K : |w| \le i\} L i = span { M w ζ K : ∣ w ∣ ≤ i } . As M b w = M b M w M_{bw} = M_bM_w M b w = M b M w , L i + 1 = L 0 + ∑ b M b L i L_{i+1} = L_0 + \sum_b M_bL_i L i + 1 = L 0 + ∑ b M b L i , so L i ⊆ L i + 1 L_i \subseteq L_{i+1} L i ⊆ L i + 1 implies L j = L i L_j = L_i L j = L i for all j ≥ i j \ge i j ≥ i . For all i ≥ 0 i \ge0 i ≥ 0 , L i L_i L i lies in the hyperplane H = { x ∈ R Q : β T x = 0 } H = \{x \in\mathbb{R}^{Q} : \beta^{T}x = 0\} H = { x ∈ R Q : β T x = 0 } , and L m L_m L m does not. So L 0 ⊂ L 1 ⊂ ⋯ ⊂ L m − 1 ⊂ H L_0 \subset L_1 \subset\cdots\subset L_{m-1} \subset H L 0 ⊂ L 1 ⊂ ⋯ ⊂ L m − 1 ⊂ H (an equality L i = L i + 1 L_i = L_{i+1} L i = L i + 1 with i ≤ m − 2 i \le m - 2 i ≤ m − 2 would give L m = L i ⊆ H L_m = L_i \subseteq H L m = L i ⊆ H ). As dim L 0 = 1 \dim L_0 = 1 dim L 0 = 1 and dim H = n − 1 \dim H = n - 1 dim H = n − 1 , we get m ≤ dim L m − 1 ≤ n − 1 m \le\dim L_{m-1} \le n - 1 m ≤ dim L m − 1 ≤ n − 1 .
(b) Take a word c v cv c v (c c c a letter, ∣ v ∣ = m − 1 |v| = m - 1 ∣ v ∣ = m − 1 ) with β ( K ( c v ) − 1 ) ≠ β ( K ) \beta(K(cv)^{-1}) \ne\beta(K) β ( K ( c v ) − 1 ) = β ( K ) , and put T = K v − 1 T = Kv^{-1} T = K v − 1 . As ∣ v ∣ < m |v| < m ∣ v ∣ < m , β ( T ) = β ( K ) \beta(T) = \beta(K) β ( T ) = β ( K ) , and β ( T c − 1 ) = β ( K ( c v ) − 1 ) ≠ β ( T ) \beta(Tc^{-1}) = \beta(K(cv)^{-1}) \ne\beta(T) β ( T c − 1 ) = β ( K ( c v ) − 1 ) = β ( T ) . The p p p -average of the numbers β ( T b − 1 ) \beta(Tb^{-1}) β ( T b − 1 ) is at least β ( T ) \beta(T) β ( T ) and one of them differs from β ( T ) \beta(T) β ( T ) ; as all p b > 0 p_b > 0 p b > 0 , some letter b b b has β ( T b − 1 ) > β ( T ) \beta(Tb^{-1}) > \beta(T) β ( T b − 1 ) > β ( T ) . The word b v bv b v has length m m m and K ( b v ) − 1 = T b − 1 K(bv)^{-1} = Tb^{-1} K ( b v ) − 1 = T b − 1 .
For the last statement, (1) gives the hypothesis of (b), with equality, for every T T T ; so by (a) and (b) some word of length m ≤ n − 1 m \le n - 1 m ≤ n − 1 raises α \alpha α , and no shorter word does, since a word that raises α \alpha α changes α ( K w − 1 ) \alpha(Kw^{-1}) α ( K w − 1 ) . □
We say that a word w w w raises α \alpha α (for K K K ) if α ( K w − 1 ) > α ( K ) \alpha(Kw^{-1}) > \alpha(K) α ( K w − 1 ) > α ( K ) . For a vector α ∈ R Q \alpha\in\mathbb{R}^{Q} α ∈ R Q with α q > 0 \alpha_q > 0 α q > 0 for every q q q and a nonempty proper set K K K , let m ( K ) m(K) m ( K ) , the cost of K K K , be the least length of a word w w w with α ( K w − 1 ) ≠ α ( K ) \alpha(Kw^{-1}) \ne\alpha(K) α ( K w − 1 ) = α ( K ) ; the vector α \alpha α will be clear from the context. As 0 < α ( K ) < α ( Q ) 0 < \alpha(K) < \alpha(Q) 0 < α ( K ) < α ( Q ) , Lemma 2.2 (a) gives 1 ≤ m ( K ) ≤ n − 1 1 \le m(K) \le n - 1 1 ≤ m ( K ) ≤ n − 1 when A \mathcal{A} A is synchronizing, and if α \alpha α is stationary, some word of length m ( K ) m(K) m ( K ) raises α \alpha α .
Lemma 2.3 (orbit lemma). Let x ∈ Q x \in Q x ∈ Q and K ⊆ Q K \subseteq Q K ⊆ Q . Say that a word w w w moves x x x across K K K if x x x lies in exactly one of the sets K K K and K w − 1 Kw^{-1} K w − 1 , that is, if [ x . w ∈ K ] ≠ [ x ∈ K ] [x.w \in K] \ne[x \in K] [ x . w ∈ K ] = [ x ∈ K ] (note that [ x ∈ K w − 1 ] = [ x . w ∈ K ] [x \in Kw^{-1}] = [x.w \in K] [ x ∈ K w − 1 ] = [ x . w ∈ K ] ). Let esc x ( K ) \operatorname{esc}_x(K) esc x ( K ) be the least length of a word that moves x x x across K K K (infinite if there is none ). If esc x ( K ) \operatorname{esc}_x(K) esc x ( K ) is finite, then esc x ( K ) ≤ ∣ K ∣ \operatorname{esc}_x(K) \le|K| esc x ( K ) ≤ ∣ K ∣ when x ∈ K x \in K x ∈ K , and esc x ( K ) ≤ n − ∣ K ∣ \operatorname{esc}_x(K) \le n - |K| esc x ( K ) ≤ n − ∣ K ∣ when x ∉ K x \notin K x ∈ / K . If A \mathcal{A} A is strongly connected and ∅ ≠ K ≠ Q \varnothing\ne K \ne Q ∅ = K = Q , then esc x ( K ) \operatorname{esc}_x(K) esc x ( K ) is finite.
Proof. Let R i = { x . w : ∣ w ∣ ≤ i } R_i = \{x.w : |w| \le i\} R i = { x . w : ∣ w ∣ ≤ i } . Then R 0 = { x } R_0 = \{x\} R 0 = { x } and R i + 1 = R i ∪ R i . Σ R_{i+1} = R_i \cup R_i.\Sigma R i + 1 = R i ∪ R i .Σ , so R i = R i + 1 R_i = R_{i+1} R i = R i + 1 implies R j = R i R_j = R_i R j = R i for all j ≥ i j \ge i j ≥ i . Let f = esc x ( K ) < ∞ f = \operatorname{esc}_x(K) < \infty f = esc x ( K ) < ∞ . If x ∈ K x \in K x ∈ K , then R f − 1 ⊆ K R_{f-1} \subseteq K R f − 1 ⊆ K and R f ⊈ K R_f \not\subseteq K R f ⊆ K , so the chain R 0 ⊊ ⋯ ⊊ R f − 1 R_0 \subsetneq\cdots\subsetneq R_{f-1} R 0 ⊊ ⋯ ⊊ R f − 1 is strict and f ≤ ∣ R f − 1 ∣ ≤ ∣ K ∣ f \le|R_{f-1}| \le|K| f ≤ ∣ R f − 1 ∣ ≤ ∣ K ∣ . If x ∉ K x \notin K x ∈ / K , the same argument in Q ∖ K Q \setminus K Q ∖ K gives f ≤ n − ∣ K ∣ f \le n - |K| f ≤ n − ∣ K ∣ . If A \mathcal{A} A is strongly connected, the set R n R_n R n of all states reachable from x x x (the chain is constant from i = n − 1 i = n - 1 i = n − 1 on) is Q Q Q , so it meets both K K K and Q ∖ K Q \setminus K Q ∖ K . □ \square □
Lemma 2.4 (tier lemma). Let A \mathcal{A} A be synchronizing and strongly connected, let α ∈ R Q \alpha\in\mathbb{R}^{Q} α ∈ R Q with α q > 0 \alpha_q > 0 α q > 0 for every q q q , and let m m m be the cost for this α \alpha α . Then for 2 ≤ j ≤ n 2 \le j \le n 2 ≤ j ≤ n , at most 2 j − 2 2^{j} - 2 2 j − 2 nonempty proper sets S S S have m ( S ) ≥ n − j + 1 m(S) \ge n - j + 1 m ( S ) ≥ n − j + 1 . In particular, at most two sets have m ( S ) = n − 1 m(S) = n - 1 m ( S ) = n − 1 , and at most six have m ( S ) ≥ n − 2 m(S) \ge n - 2 m ( S ) ≥ n − 2 .
Proof. For a letter c c c put δ c = α T M c − α T \delta_c = \alpha^{\mathsf{T}}M_c - \alpha^{\mathsf{T}} δ c = α T M c − α T , a row vector, and for k ≥ 0 k \ge0 k ≥ 0 let D k = span { δ c M v : c ∈ Σ , ∣ v ∣ ≤ k − 1 } D_k = \operatorname{span}\{\delta_c M_v : c \in\Sigma,\ |v| \le k - 1\} D k = span { δ c M v : c ∈ Σ , ∣ v ∣ ≤ k − 1 } , so D 0 = 0 D_0 = 0 D 0 = 0 . For a word w = c 1 c 2 ⋯ c l w = c_1c_2 \cdots c_l w = c 1 c 2 ⋯ c l ,
α T M w − α T = ∑ i = 1 l δ c i M c i + 1 ⋯ c l (2) \alpha^{\mathsf{T}}M_w - \alpha^{\mathsf{T}} = \sum_{i=1}^{l} \delta_{c_i}M_{c_{i+1}\cdots c_l} \tag*{(2)} α T M w − α T = i = 1 ∑ l δ c i M c i + 1 ⋯ c l (2)
since the i i i th term is α T M c i ⋯ c l − α T M c i + 1 ⋯ c l \alpha^{\mathsf{T}}M_{c_i\cdots c_l} - \alpha^{\mathsf{T}}M_{c_{i+1}\cdots c_l} α T M c i ⋯ c l − α T M c i + 1 ⋯ c l (the matrix of the empty word is I I I ). As M v 1 = 1 M_v\mathbf{1} = \mathbf{1} M v 1 = 1 , we have δ c 1 = 0 \delta_c\mathbf{1} = 0 δ c 1 = 0 and λ 1 = 0 \lambda\mathbf{1} = 0 λ 1 = 0 for every λ ∈ D k \lambda\in D_k λ ∈ D k . Recall that α T M w 1 S = α ( S w − 1 ) \alpha^{\mathsf{T}}M_w\mathbf{1}_S = \alpha(Sw^{-1}) α T M w 1 S = α ( S w − 1 ) .
(i) For a nonempty proper set S S S and k ≥ 0 k \ge0 k ≥ 0 , m ( S ) ≥ k + 1 m(S) \ge k + 1 m ( S ) ≥ k + 1 if and only if λ 1 S = 0 \lambda\mathbf{1}_S = 0 λ 1 S = 0 for every λ ∈ D k \lambda\in D_k λ ∈ D k . If λ 1 S = 0 \lambda\mathbf{1}_S = 0 λ 1 S = 0 for every λ ∈ D k \lambda\in D_k λ ∈ D k and ∣ w ∣ ≤ k |w| \le k ∣ w ∣ ≤ k , then every term of (2) lies in D k D_k D k , as its suffix c i + 1 ⋯ c l c_{i+1}\cdots c_l c i + 1 ⋯ c l has length at most k − 1 k - 1 k − 1 , so α ( S w − 1 ) = α ( S ) \alpha(Sw^{-1}) = \alpha(S) α ( S w − 1 ) = α ( S ) . Conversely, let m ( S ) ≥ k + 1 m(S) \ge k + 1 m ( S ) ≥ k + 1 , let c c c be a letter and ∣ v ∣ ≤ k − 1 |v| \le k - 1 ∣ v ∣ ≤ k − 1 . Then δ c M v 1 S = α ( S ( c v ) − 1 ) − α ( S v − 1 ) = 0 \delta_cM_v\mathbf{1}_S = \alpha(S(cv)^{-1}) - \alpha(Sv^{-1}) = 0 δ c M v 1 S = α ( S ( c v ) − 1 ) − α ( S v − 1 ) = 0 , as both words c v cv c v and v v v are shorter than m ( S ) m(S) m ( S ) .
(ii) dim D k ≥ min ( k , n − 1 ) \dim D_k \ge\min(k,n - 1) dim D k ≥ min ( k , n − 1 ) . If all δ c \delta_c δ c were 0 0 0 , then α T M w = α T \alpha^{\mathsf{T}}M_w = \alpha^{\mathsf{T}} α T M w = α T for every word w w w ; but a reset word w w w with Q . w = { r } Q.w = \{r\} Q . w = { r } has α T M w = α ( Q ) 1 { r } T ≠ α T \alpha^{\mathsf{T}}M_w = \alpha(Q)\mathbf{1}_{\{r\}}^{\mathsf{T}} \ne\alpha^{\mathsf{T}} α T M w = α ( Q ) 1 { r } T = α T , as α > 0 \alpha> 0 α > 0 and n ≥ 2 n \ge2 n ≥ 2 . So dim D 1 ≥ 1 \dim D_1 \ge1 dim D 1 ≥ 1 . A word v v v with 1 ≤ ∣ v ∣ ≤ k 1 \le|v| \le k 1 ≤ ∣ v ∣ ≤ k is either ∣ v ∣ ≤ k − 1 |v| \le k - 1 ∣ v ∣ ≤ k − 1 or ∣ v ∣ = k |v| = k ∣ v ∣ = k . Thus δ c M v = ( δ c M v ′ ) M c \delta_cM_v = (\delta_cM_{v'})M_c δ c M v = ( δ c M v ′ ) M c ; so D k + 1 = D 1 + ∑ c D k M c D_{k+1} = D_1 + \sum_c D_kM_c D k + 1 = D 1 + ∑ c D k M c . Hence D k = D k + 1 D_k = D_{k+1} D k = D k + 1 implies D k + 1 = D k + 2 D_{k+1} = D_{k+2} D k + 1 = D k + 2 , and the chain D 1 ⊆ D 2 ⊆ ⋯ D_1 \subseteq D_2 \subseteq\cdots D 1 ⊆ D 2 ⊆ ⋯ grows strictly until it becomes constant, equal to some D D D . Let ξ \xi ξ be a column vector with λ ξ = 0 \lambda\xi= 0 λ ξ = 0 for every λ ∈ D \lambda\in D λ ∈ D . By (2), α T M w ξ = α T ξ \alpha^{\mathsf{T}}M_w\xi= \alpha^{\mathsf{T}}\xi α T M w ξ = α T ξ for every word w w w . As A \mathcal{A} A is strongly connected, every state r r r is the image of Q Q Q under some word w w w (a reset word followed by a path to r r r ), and then α ( Q ) ξ r = α T ξ \alpha(Q)\xi_r = \alpha^{\mathsf{T}}\xi α ( Q ) ξ r = α T ξ . So ξ \xi ξ is a multiple of 1 \mathbf{1} 1 , and dim D = n − 1 \dim D = n - 1 dim D = n − 1 . As dim D 1 ≥ 1 \dim D_1 \ge1 dim D 1 ≥ 1 and the dimension grows by at least one at each step until it reaches n − 1 n - 1 n − 1 , (ii) follows.
(iii) Let 2 ≤ j ≤ n 2 \le j \le n 2 ≤ j ≤ n and V = { ξ : λ ξ = 0 for every λ ∈ D n − j } V = \{\xi: \lambda\xi= 0 \text{ for every } \lambda\in D_{n-j}\} V = { ξ : λ ξ = 0 for every λ ∈ D n − j } . By (ii), dim V ≤ j \dim V \le j dim V ≤ j , and by (i), 1 S ∈ V \mathbf{1}_S \in V 1 S ∈ V for every S S S with m ( S ) ≥ n − j + 1 m(S) \ge n - j + 1 m ( S ) ≥ n − j + 1 . A subspace of dimension ρ \rho ρ contains at most 2 ρ 2^\rho 2 ρ vectors with entries in { 0 , 1 } \{0,1\} { 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 } ρ \{0,1\}^{\rho} { 0 , 1 } ρ . As V V V contains 1 ∅ = 0 \mathbf{1}_{\varnothing} = 0 1 ∅ = 0 and 1 Q = 1 \mathbf{1}_Q = 1 1 Q = 1 , at most 2 j − 2 2^j - 2 2 j − 2 nonempty proper sets S S S have m ( S ) ≥ n − j + 1 m(S) \ge n - j + 1 m ( S ) ≥ n − j + 1 . The cases j = 2 , 3 j = 2,3 j = 2 , 3 give the last sentence, as m ( S ) ≤ n − 1 m(S) \le n - 1 m ( S ) ≤ n − 1 . □ \square □
Remark 2.5. The chain L i L_i L i in the proof of Lemma 2.2 (a) is Kari’s argument [7 ] ; it starts from one set. In the proof of [1 Theorem 1] , Berlinkov uses instead the chain U k + 1 = span { α T M u : ∣ u ∣ ≤ k } U_{k+1}=\operatorname{span}\{\alpha^{\mathsf T}M_u: |u|\le k\} U k + 1 = span { α T M u : ∣ u ∣ ≤ k } (in our notation), which starts from α \alpha α and so serves all sets at once. By (2) , U k + 1 = R α T ⊕ D k U_{k+1}=\mathbb{R}\alpha^{\mathsf T}\oplus D_k U k + 1 = R α T ⊕ D k (the sum is direct, since every vector of D k D_k D k has entry sum 0 and α T 1 = α ( Q ) ≠ 0 \alpha^{\mathsf T}\mathbf{1}=\alpha(Q)\ne0 α T 1 = α ( Q ) = 0 ); so D k D_k D k is Berlinkov’s chain without the line of α T \alpha^{\mathsf T} α T , and the strict growth in part (ii) of the proof of Lemma 2.4 is his argument. Bounding the number of sets that need long extending words by counting 0/1 vectors in a subspace is Szykuła’s idea [13 Section 2.8.3, Lemma 19 and Corollary 20] ; it gives r t ≤ n 2 − n log 2 n + O ( n ) rt\le n^2-n\log_2 n+O(n) r t ≤ n 2 − n log 2 n + O ( n ) for Eulerian automata, and Szykuła remarks that it can be used in weighted variants. Letter weights play no role in Lemma 2.4 ; stationarity is used only when a word of length m ( S ) m(S) m ( S ) that raises α \alpha α is needed (Lemma 2.2 ).
A stationary vector that is constant off one state
Theorem 3.1. Let A \mathcal{A} A be a synchronizing automaton with n ≥ 2 n\ge2 n ≥ 2 states. Suppose that, for some letter weights p p p , the matrix M = ∑ b p b M b M=\sum_b p_bM_b M = ∑ b p b M b has a stationary vector α \alpha α that is positive at every state and constant on Q ∖ { x } Q\setminus\{x\} Q ∖ { x } for some state x x x . Then rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A})\le(n-1)^2 rt ( A ) ≤ ( n − 1 ) 2 .
The proof is at the end of this section, after Lemma 3.2 and Proposition 3.3. Throughout this section we assume the hypothesis of Theorem 3.1. By Lemma 2.1 , A \mathcal{A} A is strongly connected. Scale α \alpha α so that α = 1 \alpha=1 α = 1 on Q ∖ { x } Q\setminus\{x\} Q ∖ { x } , and put t = α x > 0 t=\alpha_x>0 t = α x > 0 and g = t − 1 g=t-1 g = t − 1 . Then
α ( K ) = ∣ K ∣ + g [ x ∈ K ] ( K ⊆ Q ) , α ( Q ) = n − 1 + t . \alpha(K)=|K|+g[x\in K]\qquad(K\subseteq Q),\qquad\alpha(Q)=n-1+t. α ( K ) = ∣ K ∣ + g [ x ∈ K ] ( K ⊆ Q ) , α ( Q ) = n − 1 + t .
For a nonempty proper set K K K we have 0 < α ( K ) < α ( Q ) 0<\alpha(K)<\alpha(Q) 0 < α ( K ) < α ( Q ) , so Lemma 2.2 applies with β = α \beta=\alpha β = α . Let m ( K ) m(K) m ( K ) be the cost of K K K for this α \alpha α : m ( K ) ≤ n − 1 m(K)\le n-1 m ( K ) ≤ n − 1 , and some word of length m ( K ) m(K) m ( K ) raises α \alpha α . We write esc ( K ) = esc x ( K ) \operatorname{esc}(K)=\operatorname{esc}_x(K) esc ( K ) = esc x ( K ) .
Lemma 3.2 (levels). Let K , K ′ ⊆ Q K,K'\subseteq Q K , K ′ ⊆ Q , e = [ x ∈ K ] e=[x\in K] e = [ x ∈ K ] and e ′ = [ x ∈ K ′ ] e'=[x\in K'] e ′ = [ x ∈ K ′ ] .
(a) α ( K ′ ) − α ( K ) = ∣ K ′ ∣ − ∣ K ∣ + g ( e ′ − e ) \alpha(K')-\alpha(K)=|K'|-|K|+g(e'-e) α ( K ′ ) − α ( K ) = ∣ K ′ ∣ − ∣ K ∣ + g ( e ′ − e ) .
(b) If g ∉ Z g\notin\mathbb{Z} g ∈ / Z , then α ( K ′ ) = α ( K ) \alpha(K')=\alpha(K) α ( K ′ ) = α ( K ) if and only if ∣ K ′ ∣ = ∣ K ∣ |K'|=|K| ∣ K ′ ∣ = ∣ K ∣ and e ′ = e e'=e e ′ = e . So m ( K ) m(K) m ( K ) is the least length of a word that changes ∣ K w − 1 ∣ |Kw^{-1}| ∣ K w − 1 ∣ or moves x x x across K K K ; in particular m ( K ) ≤ esc ( K ) m(K)\le\operatorname{esc}(K) m ( K ) ≤ esc ( K ) , and if a word of length m ( K ) m(K) m ( K ) that raises α \alpha α moves x x x across K K K , then m ( K ) = esc ( K ) m(K)=\operatorname{esc}(K) m ( K ) = esc ( K ) .
(c) If 0 < t < 2 0<t<2 0 < t < 2 and t ≠ 1 t\ne1 t = 1 , then α ( K ′ ) > α ( K ) \alpha(K')>\alpha(K) α ( K ′ ) > α ( K ) implies ∣ K ′ ∣ ≥ ∣ K ∣ |K'|\ge|K| ∣ K ′ ∣ ≥ ∣ K ∣ , with equality only if x x x joins ( e = 0 , e ′ = 1 ) (e=0,e'=1) ( e = 0 , e ′ = 1 ) when t > 1 t>1 t > 1 , and only if x x x leaves ( e = 1 , e ′ = 0 ) (e=1,e'=0) ( e = 1 , e ′ = 0 ) when t < 1 t<1 t < 1 .
Proof. (a) is the formula for α \alpha α . (b) In (a), ∣ K ′ ∣ − ∣ K ∣ |K'|-|K| ∣ K ′ ∣ − ∣ K ∣ is an integer and g ( e ′ − e ) g(e'-e) g ( e ′ − e ) is not unless e ′ = e e'=e e ′ = e . (c) By (a), ∣ K ′ ∣ − ∣ K ∣ > g ( e − e ′ ) ≥ − ∣ g ∣ > − 1 |K'|-|K|>g(e-e')\ge-|g|>-1 ∣ K ′ ∣ − ∣ K ∣ > g ( e − e ′ ) ≥ − ∣ g ∣ > − 1 , and ∣ K ′ ∣ − ∣ K ∣ |K'|-|K| ∣ K ′ ∣ − ∣ K ∣ is an integer, so it is at least 0; it is 0 only if g ( e − e ′ ) < 0 g(e-e')<0 g ( e − e ′ ) < 0 .
In case (c) we call K K K expensive if x ∉ K x\notin K x ∈ / K (when t > 1 t>1 t > 1 ) or x ∈ K x\in K x ∈ K (when t < 1 t<1 t < 1 ), and cheap otherwise. So a raising word that keeps the size of an expensive set moves x x x across it and makes it cheap, and a raising word always enlarges a cheap set.
Proposition 3.3. If 0 < t < 2 0<t<2 0 < t < 2 and t ≠ 1 t\ne1 t = 1 , then ext ( K ) ≤ n \operatorname{ext}(K)\le n ext ( K ) ≤ n for every nonempty proper set K K K , and ext ( K ) ≤ n − 1 \operatorname{ext}(K)\le n-1 ext ( K ) ≤ n − 1 if K K K is cheap.
Proof. Let k = ∣ K ∣ k=|K| k = ∣ K ∣ , and let w 1 w_1 w 1 be a word of length m 1 = m ( K ) ≤ n − 1 m_1=m(K)\le n-1 m 1 = m ( K ) ≤ n − 1 with α ( K w 1 − 1 ) > α ( K ) \alpha(Kw_1^{-1})>\alpha(K) α ( K w 1 − 1 ) > α ( K ) ; put K 1 = K w 1 − 1 K_1=Kw_1^{-1} K 1 = K w 1 − 1 . By Lemma 3.2(c), ∣ K 1 ∣ ≥ k |K_1|\ge k ∣ K 1 ∣ ≥ k . If ∣ K 1 ∣ > k |K_1|>k ∣ K 1 ∣ > k , then ext ( K ) ≤ m 1 ≤ n − 1 \operatorname{ext}(K)\le m_1\le n-1 ext ( K ) ≤ m 1 ≤ n − 1 ; this is always the case when K K K is cheap. Otherwise K K K is expensive, x x x moved across K K K , K 1 K_1 K 1 is cheap and ∣ K 1 ∣ = k |K_1|=k ∣ K 1 ∣ = k ; by Lemma 3.2(b) (it applies, as 0 < ∣ g ∣ < 1 0<|g|<1 0 < ∣ g ∣ < 1 ) and Lemma 2.3 , m 1 = esc ( K ) ≤ k m_1=\operatorname{esc}(K)\le k m 1 = esc ( K ) ≤ k if t < 1 t<1 t < 1 (then x ∈ K x\in K x ∈ K ) and m 1 ≤ n − k m_1\le n-k m 1 ≤ n − k if t > 1 t>1 t > 1 (then x ∉ K x\notin K x ∈ / K ). Now let w 2 w_2 w 2 be a word of length m 2 = m ( K 1 ) m_2=m(K_1) m 2 = m ( K 1 ) with α ( K 1 w 2 − 1 ) > α ( K 1 ) \alpha(K_1w_2^{-1})>\alpha(K_1) α ( K 1 w 2 − 1 ) > α ( K 1 ) . As K 1 K_1 K 1 is cheap, ∣ K 1 w 2 − 1 ∣ > k |K_1w_2^{-1}|>k ∣ K 1 w 2 − 1 ∣ > k . By Lemma 3.2(b) and Lemma 2.3 (finite, as A \mathcal{A} A is strongly connected), m 2 ≤ esc ( K 1 ) ≤ n − k m_2\le\operatorname{esc}(K_1)\le n-k m 2 ≤ esc ( K 1 ) ≤ n − k if t < 1 t<1 t < 1 (then x ∉ K 1 x \notin K_1 x ∈ / K 1 ) and m 2 ≤ k m_2 \le k m 2 ≤ k if t > 1 t > 1 t > 1 (then x ∈ K 1 x \in K_1 x ∈ K 1 ). So K ( w 2 w 1 ) − 1 = K 1 w 2 − 1 K(w_2w_1)^{-1} = K_1w_2^{-1} K ( w 2 w 1 ) − 1 = K 1 w 2 − 1 is larger than K K K , and ∣ w 2 w 1 ∣ = m 1 + m 2 ≤ n |w_2w_1| = m_1 + m_2 \le n ∣ w 2 w 1 ∣ = m 1 + m 2 ≤ n .
Proof of Theorem 3.1. As A \mathcal{A} A is synchronizing and n ≥ 2 n \ge2 n ≥ 2 , some letter c c c is merging (not injective): ∣ { q } c − 1 ∣ ≥ 2 |\{q\}c^{-1}| \ge2 ∣ { q } c − 1 ∣ ≥ 2 for some state q q q .
Case t = 1 t = 1 t = 1 . Then α = 1 \alpha= 1 α = 1 , and Lemma 2.2 gives ext ( K ) ≤ n − 1 \operatorname{ext}(K) \le n - 1 ext ( K ) ≤ n − 1 for every nonempty proper K K K . Start from K 0 = { q } c − 1 K_0 = \{q\}c^{-1} K 0 = { q } c − 1 and extend at most n − 2 n - 2 n − 2 times: rt ( A ) ≤ 1 + ( n − 2 ) ( n − 1 ) \operatorname{rt}(\mathcal{A}) \le1 + (n - 2)(n - 1) rt ( A ) ≤ 1 + ( n − 2 ) ( n − 1 ) . (This is Kari’s and Steinberg’s bound [7 , 11 ] .)
Case 0 < t < 2 0 < t < 2 0 < t < 2 , t ≠ 1 t \ne1 t = 1 . Start from K 0 = { q } c − 1 K_0 = \{q\}c^{-1} K 0 = { q } c − 1 and use Proposition 3.3 at most n − 2 n - 2 n − 2 times: rt ( A ) ≤ 1 + ( n − 2 ) n = ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le1 + (n - 2)n = (n - 1)^2 rt ( A ) ≤ 1 + ( n − 2 ) n = ( n − 1 ) 2 .
Case t ≥ 2 t \ge2 t ≥ 2 an integer. Then α \alpha α takes integer values on sets. Start from K 0 = { x } K_0 = \{x\} K 0 = { x } , with α ( K 0 ) = t \alpha(K_0) = t α ( K 0 ) = t . While K j ≠ Q K_j \ne Q K j = Q , Lemma 2.2 gives a word w j w_j w j of length at most n − 1 n - 1 n − 1 with α ( K j + 1 ) ≥ α ( K j ) + 1 \alpha(K_{j+1}) \ge\alpha(K_j) + 1 α ( K j + 1 ) ≥ α ( K j ) + 1 , where K j + 1 = K j w j − 1 K_{j+1} = K_jw_j^{-1} K j + 1 = K j w j − 1 . As α ( Q ) − α ( { x } ) = n − 1 \alpha(Q) - \alpha(\{x\}) = n - 1 α ( Q ) − α ({ x }) = n − 1 , at most n − 1 n - 1 n − 1 steps reach Q Q Q , and Q . ( w J − 1 ⋯ w 0 ) ⊆ { x } Q.(w_{J-1} \cdots w_0) \subseteq\{x\} Q . ( w J − 1 ⋯ w 0 ) ⊆ { x } : rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le(n - 1)^2 rt ( A ) ≤ ( n − 1 ) 2 .
Case t > 2 t > 2 t > 2 , not an integer. Put h = ⌊ g ⌋ ≥ 1 h = \lfloor g \rfloor\ge1 h = ⌊ g ⌋ ≥ 1 . Start from K 0 = { x } K_0 = \{x\} K 0 = { x } , and while K j ≠ Q K_j \ne Q K j = Q let K j + 1 = K j w j − 1 K_{j+1} = K_jw_j^{-1} K j + 1 = K j w j − 1 for a word w j w_j w j of length m ( K j ) m(K_j) m ( K j ) that raises α \alpha α . As α \alpha α rises strictly and takes finitely many values, and α ( K ) < α ( Q ) \alpha(K) < \alpha(Q) α ( K ) < α ( Q ) for K ≠ Q K \ne Q K = Q , the process reaches Q Q Q ; every K j K_j K j is nonempty. Call a step K → K ′ K \to K' K → K ′ keep if x ∈ K ∩ K ′ x \in K \cap K' x ∈ K ∩ K ′ , free if x ∉ K ∪ K ′ x \notin K \cup K' x ∈ / K ∪ K ′ , lose if x ∈ K ∖ K ′ x \in K \setminus K' x ∈ K ∖ K ′ , and gain if x ∈ K ′ ∖ K x \in K' \setminus K x ∈ K ′ ∖ K . Put Φ ( K ) = ∣ K ∣ − h [ x ∉ K ] \Phi(K) = |K| - h[x \notin K] Φ ( K ) = ∣ K ∣ − h [ x ∈ / K ] ; so Φ ( { x } ) = 1 \Phi(\{x\}) = 1 Φ ({ x }) = 1 and Φ ( Q ) = n \Phi(Q) = n Φ ( Q ) = n . By Lemma 3.2(a), (b) and Lemma 2.3 :
keep, free: ∣ K ′ ∣ ≥ ∣ K ∣ + 1 |K'| \ge|K| + 1 ∣ K ′ ∣ ≥ ∣ K ∣ + 1 , so Φ ( K ′ ) − Φ ( K ) ≥ 1 \Phi(K') - \Phi(K) \ge1 Φ ( K ′ ) − Φ ( K ) ≥ 1 ; the step costs at most n − 1 n - 1 n − 1 ;
lose: ∣ K ′ ∣ > ∣ K ∣ + g |K'| > |K| + g ∣ K ′ ∣ > ∣ K ∣ + g , so ∣ K ′ ∣ ≥ ∣ K ∣ + h + 1 |K'| \ge|K| + h + 1 ∣ K ′ ∣ ≥ ∣ K ∣ + h + 1 and Φ ( K ′ ) − Φ ( K ) ≥ 1 \Phi(K') - \Phi(K) \ge1 Φ ( K ′ ) − Φ ( K ) ≥ 1 ; the step costs esc ( K ) ≤ ∣ K ∣ \operatorname{esc}(K) \le|K| esc ( K ) ≤ ∣ K ∣ ;
gain: ∣ K ′ ∣ > ∣ K ∣ − g |K'| > |K| - g ∣ K ′ ∣ > ∣ K ∣ − g , so ∣ K ′ ∣ ≥ ∣ K ∣ − h |K'| \ge|K| - h ∣ K ′ ∣ ≥ ∣ K ∣ − h and Φ ( K ′ ) − Φ ( K ) ≥ 0 \Phi(K') - \Phi(K) \ge0 Φ ( K ′ ) − Φ ( K ) ≥ 0 ; the step costs esc ( K ) ≤ n − ∣ K ∣ \operatorname{esc}(K) \le n - |K| esc ( K ) ≤ n − ∣ K ∣ .
Since x ∈ K 0 x \in K_0 x ∈ K 0 and x ∈ Q x \in Q x ∈ 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 k_L k L , it ends at a set of size at least k L + h + 1 k_L + h + 1 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 ≥ k L + h + 1 k_G \ge k_L + h + 1 k G ≥ k L + h + 1 . The pair costs at most k L + n − k G ≤ n − 1 − h ≤ n − 2 k_L + n - k_G \le n - 1 - h \le n - 2 k L + n − k G ≤ n − 1 − h ≤ n − 2 , and raises Φ \Phi Φ by at least one. So every keep step, every free step and every pair costs at most n − 1 n - 1 n − 1 times its increase of Φ \Phi Φ , and the total length is at most ( n − 1 ) ( Φ ( Q ) − Φ ( { x } ) ) = ( n − 1 ) 2 (n - 1)(\Phi(Q) - \Phi(\{x\})) = (n - 1)^2 ( n − 1 ) ( Φ ( Q ) − Φ ({ x })) = ( n − 1 ) 2 . As Q . ( w J − 1 ⋯ w 0 ) ⊆ { x } Q.(w_{J-1} \cdots w_0) \subseteq\{x\} Q . ( w J − 1 ⋯ w 0 ) ⊆ { x } , rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le(n - 1)^2 rt ( A ) ≤ ( n − 1 ) 2 .
These cases cover every t > 0 t > 0 t > 0 . Rationality of p p p or t t t is not used. □
Remark 3.4. When the stationary vector is rational (for example, for rational weights), Berlinkov’s Corollary 1 in [1 ] gives 1 + ( n − 1 ) ( Λ − 2 ) 1 + (n - 1)(\Lambda- 2) 1 + ( n − 1 ) ( Λ − 2 ) , where Λ \Lambda Λ is the least common multiple of the denominators of the normalized stationary vector α / α ( Q ) \alpha/\alpha(Q) α / α ( Q ) ; under the hypothesis of Theorem 3.1 with an integer t t t , Λ = n − 1 + t \Lambda= n - 1 + t Λ = n − 1 + t , so this is 1 + ( n − 1 ) ( n + t − 3 ) 1 + (n - 1)(n + t - 3) 1 + ( n − 1 ) ( n + t − 3 ) . Kari’s bound at t = 1 t = 1 t = 1 , ( n − 1 ) 2 + 1 (n - 1)^2 + 1 ( n − 1 ) 2 + 1 at t = 2 t = 2 t = 2 , and more for larger t t t . Berlinkov’s bound comes from a level count : the integer vector Λ α / α ( Q ) \Lambda\alpha/\alpha(Q) Λ α / α ( Q ) takes integer values on sets, the preimage of a state under a merging letter has value at least 2 2 2 , Q Q Q has value Λ \Lambda Λ , and each extension step of at most n − 1 n - 1 n − 1 letters raises the value by at least one. The integer case of the proof above is this level count started from { x } \{x\} { x } instead of from a merging letter. For strongly connected automata with rational weights, Gusev and Pribavkina [6 Corollary 18] proved rt ≤ W 2 − 3 W + 3 \operatorname{rt} \le W^2 - 3W + 3 rt ≤ W 2 − 3 W + 3 , where W W 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 ) 1 + (n - 1)(W - 2) 1 + ( n − 1 ) ( W − 2 ) , is Berlinkov’s Corollary 1 above, as W = Λ W = \Lambda W = Λ . Under the hypothesis of Theorem 3.1 with t = i / j t = i/j t = i / j in lowest terms, W = ( n − 1 ) j + i W = (n - 1)j + i W = ( n − 1 ) j + i ; so W = n W = n W = n only for t = 1 t=1 t = 1 , and otherwise W ≥ n + 1 W \ge n+1 W ≥ n + 1 and W 2 − 3 W + 3 ≥ n 2 − n + 1 > ( n − 1 ) 2 W^2-3W+3 \ge n^2-n+1 > (n-1)^2 W 2 − 3 W + 3 ≥ n 2 − n + 1 > ( n − 1 ) 2 . For irrational t t t their bound does not apply.
Example 3.5 (a larger family). Let Q = { 0 , 1 , 2 , 3 , 4 } Q=\{0,1,2,3,4\} Q = { 0 , 1 , 2 , 3 , 4 } and let the letters a , b a,b a , b map 0 , 1 , 2 , 3 , 4 0,1,2,3,4 0 , 1 , 2 , 3 , 4 to 2 , 4 , 3 , 4 , 0 2,4,3,4,0 2 , 4 , 3 , 4 , 0 and to 4 , 2 , 4 , 3 , 1 4,2,4,3,1 4 , 2 , 4 , 3 , 1 , respectively. With p = ( 1 2 , 1 2 ) p=\left(\frac{1}{2},\frac{1}{2}\right) p = ( 2 1 , 2 1 ) the vector α = ( 1 , 1 , 1 , 1 , 2 ) \alpha=(1,1,1,1,2) α = ( 1 , 1 , 1 , 1 , 2 ) is stationary: the states 0 and 1 are entered only from 4 (respectively by a a a and b b b ), the states 2 and 3 by two edges from { 0 , 1 , 2 , 3 } \{0,1,2,3\} { 0 , 1 , 2 , 3 } each, and 4 by four such edges. So Theorem 3.1 applies with x = 4 x=4 x = 4 and t = 2 t=2 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 ∖ { s } ⊆ { 2 , 3 } E\setminus\{s\}\subseteq\{2,3\} E ∖ { s } ⊆ { 2 , 3 } and d ≥ 2 d\ge2 d ≥ 2 , and for d = 2 d=2 d = 2 the set X X X contains 0 or 1, whose edges 0. a = 2 0.a=2 0. a = 2 and 1. b = 2 1.b=2 1. b = 2 leave X ∪ { s } = { 0 , 1 , 4 } X\cup\{s\}=\{0,1,4\} X ∪ { s } = { 0 , 1 , 4 } . The automaton is synchronizing, as Q . ( a b a a b ) = { 4 } Q.(abaab)=\{4\} Q . ( abaab ) = { 4 } .
Example 3.6 (irrational weights). Let Q = { 0 , 1 , 2 } Q=\{0,1,2\} Q = { 0 , 1 , 2 } , let a a a map every state to 0, and let b b b map 0 , 1 , 2 0,1,2 0 , 1 , 2 to 1 , 2 , 1 1,2,1 1 , 2 , 1 . A stationary vector equal to 1 off the state 2 and to t t t at 2 exists exactly when p a ( 2 + t ) = 1 p_a(2+t)=1 p a ( 2 + t ) = 1 and p b ( 1 + t ) = 1 p_b(1+t)=1 p b ( 1 + t ) = 1 , that is, when t 2 + t − 1 = 0 t^2+t-1=0 t 2 + t − 1 = 0 ; so t = ( 5 − 1 ) / 2 t=(\sqrt{5}-1)/2 t = ( 5 − 1 ) /2 and p a = ( 3 − 5 ) / 2 p_a=(3-\sqrt{5})/2 p a = ( 3 − 5 ) /2 . With the state 1 in the role of x x x one gets t = 2 t=\sqrt{2} t = 2 and p b = 1 / 2 p_b=1/\sqrt{2} p b = 1/ 2 , and the state 0 admits no such weights. So for this (trivially synchronizing) automaton every choice of x x x needs irrational weights.
Quasi-Eulerian automata of degree one
Theorem 4.1. Every synchronizing quasi-Eulerian automaton of degree one with n ≥ 2 n\ge2 n ≥ 2 states has a reset word of length at most ( n − 1 ) 2 (n-1)^2 ( n − 1 ) 2 . The Černý automata C n C_n C n attain this bound.
The proof follows Lemma 4.2 . Let ( E , s , p ) (E,s,p) ( E , s , p ) be a witness of degree one, X = { x } X=\{x\} X = { x } . By Definition 1.1 (a), every edge that starts at x x x ends at x x x or at s s s . Put
z = ∑ b : x . b = x p b , y = ∑ b p b ∣ { q ∈ E : q . b = x } ∣ , z=\sum_{b:x.b=x}p_b,\qquad y=\sum_b p_b\left|\{q\in E:q.b=x\}\right|, z = b : x . b = x ∑ p b , y = b ∑ p b ∣ { q ∈ E : q . b = x } ∣ ,
the weight of the loops at x x x and of the edges from E E E into x x x . So in p ( x ) = y + z \operatorname{in}_p(x)=y+z in p ( x ) = y + z , and as the in-weights add up to n n n , in p ( s ) = 2 − y − z \operatorname{in}_p(s)=2-y-z in p ( s ) = 2 − y − z .
Lemma 4.2. If z < 1 z<1 z < 1 , then the vector α \alpha α with α = 1 \alpha=1 α = 1 on E E E and α x = t : = y / ( 1 − z ) \alpha_x=t:=y/(1-z) α x = t := y / ( 1 − z ) is stationary.
Proof. We check ( α T M ) q = α q (\alpha^{\mathsf{T}}M)_q=\alpha_q ( α T M ) q = α q . For q ∈ E ∖ { s } q\in E\setminus\{s\} q ∈ E ∖ { s } , every edge into q q q starts in E E E , so ( α T M ) q = in p ( q ) = 1 (\alpha^{\mathsf{T}}M)_q=\operatorname{in}_p(q)=1 ( α T M ) q = in p ( q ) = 1 . For q = x q=x q = x : ( α T M ) x = y + z t = t ( 1 − z ) + z t = t (\alpha^{\mathsf{T}}M)_x=y+zt=t(1-z)+zt=t ( α T M ) x = y + z t = t ( 1 − z ) + z t = t . The entries of α T M \alpha^{\mathsf{T}}M α T M and of α \alpha α have the same sum, as M 1 = 1 M\mathbf{1}=\mathbf{1} M 1 = 1 ; so the entry at s s s agrees too. □
Proof of Theorem 4.1. Case z < 1 z<1 z < 1 and y > 0 y>0 y > 0 . Then t > 0 t>0 t > 0 , and α \alpha α of Lemma 4.2 is positive and constant on Q ∖ { x } Q\setminus\{x\} Q ∖ { x } : Theorem 3.1 gives rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A})\le(n-1)^2 rt ( A ) ≤ ( n − 1 ) 2 . By Lemma 2.1 , every automaton in this case is strongly connected. Conversely, if A \mathcal{A} A is strongly connected, then the set { x } \{x\} { x } is not closed, so z < 1 z<1 z < 1 , and E E E is not closed, so some edge from E E E enters x x x and y > 0 y>0 y > 0 . So the two cases below are exactly the automata of the family that are not strongly connected.
Case z = 1 z=1 z = 1 . Every letter fixes x x x . If y = 0 y=0 y = 0 , then E E E and { x } \{x\} { x } are both closed, which is impossible in a synchronizing automaton; so y > 0 y>0 y > 0 , and some letter c c c maps a state of E E E to x x x , so that ∣ { x } c − 1 ∣ ≥ 2 |\{x\}c^{-1}|\ge2 ∣ { x } c − 1 ∣ ≥ 2 . Here in p ( x ) = 1 + y \operatorname{in}_p(x)=1+y in p ( x ) = 1 + y and in p ( s ) = 1 − y \operatorname{in}_p(s)=1-y in p ( s ) = 1 − y , so for every set T T T with x ∈ T x\in T x ∈ T ,
∑ b p b ∣ T b − 1 ∣ = ∑ q ∈ Q in p ( q ) = [ T ] + y ( 1 − [ s ∈ T ] ) ≥ [ T ] . \sum_b p_b|Tb^{-1}|=\sum_{q\in Q}\operatorname{in}_p(q)=[T]+y(1-[s\in T])\ge[T]. b ∑ p b ∣ T b − 1 ∣ = q ∈ Q ∑ in p ( q ) = [ T ] + y ( 1 − [ s ∈ T ]) ≥ [ T ] .
Let K K K be a nonempty proper set with x ∈ K x\in K x ∈ K . Apply Lemma 2.2 with β = 1 \beta=1 β = 1 : every set T = K v − 1 T=Kv^{-1} T = K v − 1 contains x x x (as x . v = x x.v=x x . v = x ), so some word of length at most n − 1 n-1 n − 1 enlarges K K K . Every set { x } w − 1 \{x\}w^{-1} { x } w − 1 contains x x x ; start from { x } c − 1 \{x\}c^{-1} { x } c − 1 and extend at most n − 2 n-2 n − 2 times: rt ( A ) ≤ 1 + ( n − 2 ) ( n − 1 ) \operatorname{rt}(\mathcal{A})\le1+(n-2)(n-1) rt ( A ) ≤ 1 + ( n − 2 ) ( n − 1 ) . Case z < 1 z<1 z < 1 and y = 0 y=0 y = 0 . No edge enters x x x from E E E , so E E E is closed. The automaton B \mathcal{B} B obtained by restricting the letters to E E E has n − 1 n-1 n − 1 states, and every state of E E E has in-weight one in B \mathcal{B} B : for r ∈ E ∖ { s } r\in E\setminus\{s\} r ∈ E ∖ { s } all edges into r r r start in E E E , and the in-weight of s s s in B \mathcal{B} B is in p ( s ) − ( 1 − z ) = ( 2 − z ) − ( 1 − z ) = 1 \operatorname{in}_{p}(s)-(1-z)=(2-z)-(1-z)=1 in p ( s ) − ( 1 − z ) = ( 2 − z ) − ( 1 − z ) = 1 . A reset word of A \mathcal{A} A resets B \mathcal{B} B . As z < 1 z<1 z < 1 , some letter c c c has x . c = s x.c=s x . c = s ; as E E E is closed, Q . c ⊆ E Q.c\subseteq E Q . c ⊆ E . If n = 2 n=2 n = 2 then E = { s } E=\{s\} E = { s } , and c c c is a reset word. If n ≥ 3 n\ge3 n ≥ 3 , the case t = 1 t=1 t = 1 of the proof of Theorem 3.1 (with α = 1 \alpha=1 α = 1 ) gives rt ( B ) ≤ 1 + ( n − 3 ) ( n − 2 ) \operatorname{rt}(\mathcal{B})\le1+(n-3)(n-2) rt ( B ) ≤ 1 + ( n − 3 ) ( n − 2 ) ; as Q . c ⊆ E Q.c\subseteq E Q . c ⊆ E , the letter c c c followed by a reset word of B \mathcal{B} B resets A \mathcal{A} A , so rt ( A ) ≤ 2 + ( n − 3 ) ( n − 2 ) ≤ 1 + ( n − 2 ) ( n − 1 ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A})\le2+(n-3)(n-2)\le1+(n-2)(n-1)\le(n-1)^2 rt ( A ) ≤ 2 + ( n − 3 ) ( n − 2 ) ≤ 1 + ( n − 2 ) ( n − 1 ) ≤ ( n − 1 ) 2 , where the middle inequality holds because 2 n − 5 ≥ 0 2n-5\ge0 2 n − 5 ≥ 0 .
The bound is attained. In C n C_n C n (with 0. a = 1 0.a=1 0. a = 1 , q . a = q q.a=q q . a = q for 0 < q < n 0<q<n 0 < q < n , and q . b = q + 1 ( m o d n ) q.b=q+1\pmod n q . b = q + 1 ( mod n ) ) take E = { 1 , … , n − 1 } E=\{1,\ldots,n-1\} E = { 1 , … , n − 1 } , s = 1 s=1 s = 1 , x = 0 x=0 x = 0 and any weights p a , p b > 0 p_a,p_b>0 p a , p b > 0 with sum one: both edges from 0 0 0 end at 1 1 1 , every r ∈ { 2 , … , n − 1 } r\in\{2,\ldots,n-1\} r ∈ { 2 , … , n − 1 } is entered exactly by r . a = r r.a=r r . a = r and ( r − 1 ) . b = r (r-1).b=r ( r − 1 ) . b = r , so in p ( r ) = 1 \operatorname{in}_{p}(r)=1 in p ( r ) = 1 . Černý proved rt ( C n ) = ( n − 1 ) 2 \operatorname{rt}(C_n)=(n-1)^2 rt ( C n ) = ( n − 1 ) 2 [3 ] . □
Remark 4.3. For C n C_n C n we have z = 0 z=0 z = 0 , y = p b y=p_b y = p b and t = p b ∈ ( 0 , 1 ) t=p_b\in(0,1) t = p b ∈ ( 0 , 1 ) , the case of Proposition 3.3. The bound 1 + ( n − 2 ) n 1+(n-2)n 1 + ( n − 2 ) n of that case is attained. Let K 0 = { 1 } a − 1 = { 0 , 1 } K_0=\{1\}a^{-1}=\{0,1\} K 0 = { 1 } a − 1 = { 0 , 1 } , and let K j + 1 = K j w j − 1 K_{j+1}=K_jw_j^{-1} K j + 1 = K j w j − 1 , where w j w_j w j is a word of length ext ( K j ) \operatorname{ext}(K_j) ext ( K j ) with ∣ K j w j − 1 ∣ > ∣ K j ∣ \lvert K_jw_j^{-1}\rvert>\lvert K_j\rvert ∣ K j w j − 1 ∣ > ∣ K j ∣ , until K J = Q K_J=Q K J = Q ; then w J − 1 ⋯ w 0 a w_{J-1}\cdots w_0a w J − 1 ⋯ w 0 a is a reset word. Each step adds at least one state, so J ≤ n − 2 J\le n-2 J ≤ n − 2 , and ∣ w j ∣ ≤ n \lvert w_j\rvert\le n ∣ w j ∣ ≤ n by Proposition 3.3. As rt ( C n ) = ( n − 1 ) 2 = 1 + ( n − 2 ) n \operatorname{rt}(C_n)=(n-1)^2=1+(n-2)n rt ( C n ) = ( n − 1 ) 2 = 1 + ( n − 2 ) n , it follows that J = n − 2 J=n-2 J = n − 2 and that every step has length exactly n n n and adds exactly one state (Figure 3 shows the chain for n = 4 n=4 n = 4 ). The conclusion of Proposition 3.3 does not extend to t = 2 t=2 t = 2 : a single extension may need more than n n n letters, and the proof uses the level count of the integer case instead. For example, for Q = { 0 , 1 , 2 , 3 } Q=\{0,1,2,3\} Q = { 0 , 1 , 2 , 3 } , a = ( 0 , 0 , 1 , 3 ) a=(0,0,1,3) a = ( 0 , 0 , 1 , 3 ) and b = ( 3 , 1 , 3 , 2 ) b=(3,1,3,2) b = ( 3 , 1 , 3 , 2 ) (the images of 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 ), the witness E = { 0 , 1 , 2 } E=\{0,1,2\} E = { 0 , 1 , 2 } , s = 2 s=2 s = 2 , x = 3 x=3 x = 3 , p = ( 1 2 , 1 2 ) p=(\frac{1}{2},\frac{1}{2}) p = ( 2 1 , 2 1 ) has z = 1 2 z=\frac{1}{2} z = 2 1 , y = 1 y=1 y = 1 , t = 2 t=2 t = 2 , and ext ( { 0 , 1 , 2 } ) = 5 > n \operatorname{ext}(\{0,1,2\})=5>n ext ({ 0 , 1 , 2 }) = 5 > n : a word w w w enlarges this set exactly when Q . w ⊆ { 0 , 1 , 2 } Q.w\subseteq\{0,1,2\} Q . w ⊆ { 0 , 1 , 2 } ; the word a a b a b aabab aabab has Q . ( a a b a b ) = { 1 , 2 } Q.(aabab)=\{1,2\} Q . ( aabab ) = { 1 , 2 } , and for every word w w w of length at most four the set Q . w Q.w Q . w is one of Q Q Q , { 0 , 1 , 3 } \{0,1,3\} { 0 , 1 , 3 } , { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } , { 0 , 3 } \{0,3\} { 0 , 3 } , { 2 , 3 } \{2,3\} { 2 , 3 } and { 1 , 3 } \{1,3\} { 1 , 3 } , so it contains the state 3 3 3 . The automaton is synchronizing (for example, Q . ( a a b a b a a ) = { 0 } Q.(aababaa)=\{0\} Q . ( aababaa ) = { 0 } ).
Remark 4.4. The family of Theorem 4.1 and the one-cluster automata (some letter has only one cycle) are incomparable. The automaton of Example 3.5 is one-cluster (its letter a a a has the single cycle 0 → 2 → 3 → 4 → 0 0\to2\to3\to4\to0 0 → 2 → 3 → 4 → 0 ) but not quasi-Eulerian of degree one. The automaton on { 0 , 1 , 2 , 3 } \{0,1,2,3\} { 0 , 1 , 2 , 3 } with a = ( 0 , 2 , 1 , 0 ) a=(0,2,1,0) a = ( 0 , 2 , 1 , 0 ) and b = ( 1 , 3 , 2 , 0 ) b=(1,3,2,0) b = ( 1 , 3 , 2 , 0 ) (the lists give the images of 0 , 1 , 2 , 3 0,1,2,3 0 , 1 , 2 , 3 ) is synchronizing and quasi-Eulerian of degree one with X = { 3 } X=\{3\} X = { 3 } and s = 0 s=0 s = 0 (both edges from 3 3 3 end at 0 0 0 , and each of the states 1 1 1 and 2 2 2 is entered once by each letter), and the word a b b a b b a abbabba abbabba resets it; but each of its letters has two cycles: a a a has the cycles ( 0 ) (0) ( 0 ) and ( 12 ) (12) ( 12 ) , and b b b has ( 013 ) (013) ( 013 ) and ( 2 ) (2) ( 2 ) .
Degree two
Automata that are not strongly connected
Theorem 5.1. Let A \mathcal{A} A be a synchronizing automaton with n ≥ 3 n\ge3 n ≥ 3 states that is quasi-Eulerian of degree at most two and not strongly connected. Then rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A})\le(n-1)^2 rt ( A ) ≤ ( n − 1 ) 2 .
The proof follows Lemmas 5.2 and 5.3. Let ( E , s , p ) (E,s,p) ( E , s , p ) be a witness and X = Q ∖ E X=Q\setminus E X = Q ∖ E , ∣ X ∣ ≤ 2 \lvert X\rvert\le2 ∣ X ∣ ≤ 2 . Every state has out-weight ∑ b p b = 1 \sum_b p_b=1 ∑ b p 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 A \mathcal{A} A has exactly one minimal nonempty closed set C C C . The restriction A ∣ C \mathcal{A}|_C A ∣ C is strongly connected (by the minimality of C C C ) and synchronizing, and every state reaches C C C (a reset word maps every state to one state, which lies in C C C because C C C is closed). Put R = Q ∖ C R=Q\setminus C R = Q ∖ C ; it is nonempty as A \mathcal{A} A is not strongly connected. Let rt ( A ∣ C ) = 0 \operatorname{rt}(\mathcal{A}|_C)=0 rt ( A ∣ C ) = 0 if ∣ C ∣ = 1 \lvert C\rvert=1 ∣ C ∣ = 1 .
Lemma 5.2 (weight count). Let T T T be a nonempty subset of E ∖ { s } E \setminus\{s\} E ∖ { s } such that every edge that ends in T T T starts in T T T . Then T T T is closed.
Proof. The in-weights on T T T are one, so the edges that end in T T T carry total weight ∣ T ∣ |T| ∣ T ∣ ; they all start in T T T . The edges that start in T T T also carry total weight ∣ T ∣ |T| ∣ T ∣ . So the edges from T T T to Q ∖ T Q \setminus T Q ∖ T carry weight 0 0 0 , and as all p b > 0 p_b > 0 p b > 0 there are none. □
Lemma 5.3 (push). rt ( A ) ≤ ∣ R ∣ 2 + rt ( A ∣ C ) \operatorname{rt}(A) \le|R|^2 + \operatorname{rt}(A|_C) rt ( A ) ≤ ∣ R ∣ 2 + rt ( A ∣ C ) .
Proof. Let S S S be the current image, starting with S = Q S = Q S = Q . While S S S meets R R R , take q ∈ S ∖ C q \in S \setminus C q ∈ S ∖ C and a shortest word u u u with q . u ∈ C q.u \in C q . u ∈ C ; its path visits distinct states of R R R before it enters C C C , so ∣ u ∣ ≤ ∣ R ∣ |u| \le|R| ∣ u ∣ ≤ ∣ R ∣ . As C C C is closed, S . u ∖ C ⊆ ( S ∖ C ) . u ∖ C S.u \setminus C \subseteq(S \setminus C).u \setminus C S . u ∖ C ⊆ ( S ∖ C ) . u ∖ C ; the set ( S ∖ C ) . u (S \setminus C).u ( S ∖ C ) . u has at most ∣ S ∖ C ∣ |S \setminus C| ∣ S ∖ C ∣ elements, and one of them, q . u q.u q . u , lies in C C C ; so ∣ S . u ∖ C ∣ ≤ ∣ S ∖ C ∣ − 1 |S.u \setminus C| \le|S \setminus C| - 1 ∣ S . u ∖ C ∣ ≤ ∣ S ∖ C ∣ − 1 . After at most ∣ R ∣ |R| ∣ R ∣ such words, of total length at most ∣ R ∣ 2 |R|^2 ∣ R ∣ 2 , the image lies in C C C , and a reset word of A ∣ C A|_C A ∣ C maps it to one state. □
Proof of Theorem 5.1. Case s ∈ C s \in C s ∈ C . Let T = R ∩ ( E ∖ { s } ) T = R \cap(E \setminus\{s\}) T = R ∩ ( E ∖ { s }) . An edge that ends in T T T starts in R R R (as C C C is closed), not in X X X (edges from X X X end in X ∪ { s } X \cup\{s\} X ∪ { s } ), and not at s s s (as s ∈ C s \in C s ∈ C ); so it starts in T T T . By Lemma 5.2, T T T is closed if it is nonempty; then it contains a minimal nonempty closed set other than C C C , which is impossible. So T = ∅ T = \varnothing T = ∅ and R ⊆ X R \subseteq X R ⊆ X ; so ∣ R ∣ ∈ { 1 , 2 } |R| \in\{1, 2\} ∣ R ∣ ∈ { 1 , 2 } and E ⊆ C E \subseteq C E ⊆ C ; put ℓ = ∣ C ∣ = n − ∣ R ∣ \ell= |C| = n - |R| ℓ = ∣ C ∣ = n − ∣ R ∣ . In A ∣ C A|_C A ∣ C every state of E ∖ { s } E \setminus\{s\} E ∖ { s } keeps in-weight one (all its in-edges start in E ⊆ C E \subseteq C E ⊆ C ), and every edge from X ∩ C X \cap C X ∩ C ends in ( X ∩ C ) ∪ { s } (X \cap C) \cup\{s\} ( X ∩ C ) ∪ { s } . If ℓ = 1 \ell= 1 ℓ = 1 , rt ( A ∣ C ) = 0 \operatorname{rt}(A|_C) = 0 rt ( A ∣ C ) = 0 . If X ∩ C = { x ′ } X \cap C = \{x'\} X ∩ C = { x ′ } and ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 , A ∣ C A|_C A ∣ C is quasi-Eulerian of degree one, and Theorem 4.1 gives rt ( A ∣ C ) ≤ ( ℓ − 1 ) 2 \operatorname{rt}(A|_C) \le(\ell- 1)^2 rt ( A ∣ C ) ≤ ( ℓ − 1 ) 2 . If X ∩ C = ∅ X \cap C = \varnothing X ∩ C = ∅ and ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 , then C = E C = E C = E ; the in-weights of A ∣ C A|_C A ∣ C add up to ℓ \ell ℓ and equal one on E ∖ { s } E \setminus\{s\} E ∖ { s } , so they equal one at s s s too, 1 1 1 is a positive stationary vector of A ∣ C A|_C A ∣ C , and Theorem 3.1 gives rt ( A ∣ C ) ≤ ( ℓ − 1 ) 2 \operatorname{rt}(A|_C) \le(\ell- 1)^2 rt ( A ∣ C ) ≤ ( ℓ − 1 ) 2 . By Lemma 5.3,
rt ( A ) ≤ ∣ R ∣ 2 + ( n − 1 − ∣ R ∣ ) 2 ≤ ( n − 1 ) 2 \operatorname{rt}(A) \le|R|^2 + (n - 1 - |R|)^2 \le(n - 1)^2 rt ( A ) ≤ ∣ R ∣ 2 + ( n − 1 − ∣ R ∣ ) 2 ≤ ( n − 1 ) 2
since ( n − 1 ) 2 − ( n − 1 − j ) 2 = j ( 2 n − 2 − j ) ≥ j 2 (n - 1)^2 - (n - 1 - j)^2 = j(2n - 2 - j) \ge j^2 ( n − 1 ) 2 − ( n − 1 − j ) 2 = j ( 2 n − 2 − j ) ≥ j 2 for 1 ≤ j ≤ n − 1 1 \le j \le n - 1 1 ≤ j ≤ n − 1 , here with j = ∣ R ∣ j = |R| j = ∣ R ∣ .
Case s ∈ R s \in R s ∈ R . If some x ∈ X x \in X x ∈ X lies in C C C , its edges end in X ∪ { s } X \cup\{s\} X ∪ { s } and in C C C , hence in X ∩ C X \cap C X ∩ C ; so X ∩ C X \cap C X ∩ C is closed, and by minimality C = X ∩ C ⊆ X C = X \cap C \subseteq X C = X ∩ C ⊆ X . If X ∩ C = ∅ X \cap C = \varnothing X ∩ C = ∅ , then C ⊆ E ∖ { s } C \subseteq E \setminus\{s\} C ⊆ E ∖ { s } . The edges that end in C C C carry total weight ∣ C ∣ |C| ∣ C ∣ , and the edges from C C C (all of which end in C C C ) already carry weight ∣ C ∣ |C| ∣ C ∣ ; so no edge enters C C C from R R R , which is impossible as every state reaches C C C . So C ⊆ X C \subseteq X C ⊆ X . If ∣ C ∣ = 1 |C| = 1 ∣ C ∣ = 1 , Lemma 5.3 gives rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(A) \le(n - 1)^2 rt ( A ) ≤ ( n − 1 ) 2 . If C = X C = X C = X , then rt ( A ∣ C ) = 1 \operatorname{rt}(A|_C) = 1 rt ( A ∣ C ) = 1 (a synchronizing automaton with two states) and rt ( A ) ≤ ( n − 2 ) 2 + 1 ≤ ( n − 1 ) 2 \operatorname{rt}(A) \le(n - 2)^2 + 1 \le(n - 1)^2 rt ( A ) ≤ ( n − 2 ) 2 + 1 ≤ ( n − 1 ) 2 . □
Remark 5.4. Lemma 5.3 and the proof above that R ⊆ X R \subseteq X R ⊆ X or C ⊆ X C \subseteq X C ⊆ X do not use d = 2 d = 2 d = 2 . So for a synchronizing quasi-Eulerian automaton of any degree d d d that is not strongly connected, either C ⊆ X C \subseteq X C ⊆ X , or R ⊆ X R \subseteq X R ⊆ X and the strongly connected automaton A ∣ C A|_C A ∣ C , with n − ∣ R ∣ n - |R| n − ∣ R ∣ states, is quasi-Eulerian of degree d − ∣ R ∣ d - |R| d − ∣ R ∣ or has the positive stationary vector 1 1 1 ; in each case rt ( A ) ≤ ∣ R ∣ 2 + rt ( A ∣ C ) \operatorname{rt}(A) \le|R|^2 + \operatorname{rt}(A|_C) rt ( A ) ≤ ∣ R ∣ 2 + rt ( A ∣ C ) . As j 2 + ( n − 1 − j ) 2 ≤ ( n − 1 ) 2 j^2 + (n - 1 - j)^2 \le(n - 1)^2 j 2 + ( n − 1 − j ) 2 ≤ ( n − 1 ) 2 for 1 ≤ j ≤ n − 1 1 \le j \le n - 1 1 ≤ j ≤ n − 1 , the Černý bound for automata of degree d d d that are not strongly connected reduces to Theorem 3.1, the bound for strongly connected automata of degree at most d − 1 d - 1 d − 1 , and the bound for automata with at most d d d states; for d ≤ 2 d \le2 d ≤ 2 all three hold (Theorems 3.1 and 4.1, and automata with at most two states), and this gives Theorem 5.1.
The stationary vector of a strongly connected automaton
Berlinkov observed in the proof of [1 Theorem 2] that the stationary vector is constant on E E E ; the next lemma gives it explicitly.
Lemma 5.5. Let A A A be strongly connected and quasi-Eulerian of degree d ≥ 1 d \ge1 d ≥ 1 with witness ( E , s , p ) (E,s,p) ( E , s , p ) , X = Q ∖ E X = Q \setminus E X = Q ∖ E . Let Z Z Z be the X × X X \times X X × X matrix with Z x x ′ = ∑ b : x . b = x ′ p b Z_{xx'} = \sum_{b:x.b=x'} p_b Z x x ′ = ∑ b : x . b = x ′ p b , and y ∈ R X y \in\mathbb{R}^{X} y ∈ R X the
row vector with y x = ∑ b p b ∣ { q ∈ E : q . b = x } ∣ y_x = \sum_b p_b|\{q \in E : q.b = x\}| y x = ∑ b p b ∣ { q ∈ E : q . b = x } ∣ . Then I − Z I-Z I − Z is invertible, and the vector α \alpha α with α = 1 \alpha=1 α = 1 on E E E and α ∣ X = t : = y ( I − Z ) − 1 \alpha|_X=t:=y(I-Z)^{-1} α ∣ X = t := y ( I − Z ) − 1 (a row vector) is a stationary vector with α q > 0 \alpha_q>0 α q > 0 for every q q q .
Proof. The matrix Z Z Z is nonnegative with row sums at most one. If I − Z I-Z I − Z were singular, then 1 1 1 would be an eigenvalue of Z Z Z , and as the spectral radius of Z Z Z is at most its largest row sum, it would be one; by the Perron–Frobenius theorem Z η = η Z\eta=\eta Z η = η for some η ≥ 0 \eta\geq0 η ≥ 0 , η ≠ 0 \eta\neq0 η = 0 . Let Y Y Y be the set of x ∈ X x\in X x ∈ X with η x = max η > 0 \eta_x=\max\eta>0 η x = max η > 0 . For x ∈ Y x\in Y x ∈ Y , η x = ∑ x ′ Z x x ′ η x ′ ≤ max η ∑ x ′ Z x x ′ ≤ max η \eta_x=\sum_{x'}Z_{xx'}\eta_{x'}\leq\max\eta\sum_{x'}Z_{xx'}\leq\max\eta η x = ∑ x ′ Z x x ′ η x ′ ≤ max η ∑ x ′ Z x x ′ ≤ max η ; equality forces ∑ x ′ Z x x ′ = 1 \sum_{x'}Z_{xx'}=1 ∑ x ′ Z x x ′ = 1 and Z x x ′ = 0 Z_{xx'}=0 Z x x ′ = 0 for x ′ ∉ Y x'\notin Y x ′ ∈ / Y , so every letter maps x x x into Y Y Y . Then Y Y Y is a nonempty closed set other than Q Q Q (as s ∉ Y s\notin Y s ∈ / Y ), which is impossible. So I − Z I-Z I − Z is invertible and t t t is defined. For r ∈ E ∖ { s } r\in E\setminus\{s\} r ∈ E ∖ { s } all edges into r r r start in E E E , so ( α T M ) r = in p ( r ) = 1 (\alpha^{\mathsf T}M)_r=\operatorname{in}_p(r)=1 ( α T M ) r = in p ( r ) = 1 ; for x ∈ X x\in X x ∈ X , ( α T M ) x = y x + ( t Z ) x = t x (\alpha^{\mathsf T}M)_x=y_x+(tZ)_x=t_x ( α T M ) x = y x + ( tZ ) x = t x ; the entry at s s s agrees as both vectors have the same sum. As A A A is strongly connected and p > 0 p>0 p > 0 , M M M is irreducible, and its stationary vectors are the multiples of one positive vector; α \alpha α is one of them, and α = 1 \alpha=1 α = 1 on E ≠ ∅ E\neq\varnothing E = ∅ , so α > 0 \alpha>0 α > 0 . □
A congruence
Proposition 5.6. Let A A A be synchronizing and quasi-Eulerian of degree two with witness ( E , s , p ) (E,s,p) ( E , s , p ) and X = { x 1 , x 2 } X=\{x_1,x_2\} X = { x 1 , x 2 } . Suppose that for every letter b b b , either x 1 . b = x 2 . b x_1.b=x_2.b x 1 . b = x 2 . b or { x 1 . b , x 2 . b } = X \{x_1.b,x_2.b\}=X { x 1 . b , x 2 . b } = X . Then rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(A)\leq(n-1)^2 rt ( A ) ≤ ( n − 1 ) 2 , and if A A A is strongly connected, rt ( A ) ≤ ( n − 2 ) 2 + 1 \operatorname{rt}(A)\leq(n-2)^2+1 rt ( A ) ≤ ( n − 2 ) 2 + 1 .
Proof. If A A A is not strongly connected, Theorem 5.1 applies. Let it be strongly connected, and let α \alpha α be the vector of Lemma 5.5. The partition of Q Q Q into X X X and singletons is a congruence by the hypothesis; let A ′ A' A ′ be the quotient automaton, with n − 1 ≥ 2 n-1\geq2 n − 1 ≥ 2 states. It is synchronizing (every reset word of A A A resets it). Some letter c 0 c_0 c 0 has x 1 . c 0 = x 2 . c 0 x_1.c_0=x_2.c_0 x 1 . c 0 = x 2 . c 0 , since otherwise X X X would be closed. If w w w resets A ′ A' A ′ , then Q . w Q.w Q . w lies in one block of the partition, and Q . ( w c 0 ) Q.(wc_0) Q . ( w c 0 ) is a single state; so rt ( A ) ≤ rt ( A ′ ) + 1 \operatorname{rt}(A)\leq\operatorname{rt}(A')+1 rt ( A ) ≤ rt ( A ′ ) + 1 . Let α ′ \alpha' α ′ be the lumped vector: α ′ = 1 \alpha'=1 α ′ = 1 on E E E and α X ′ = t 1 + t 2 > 0 \alpha'_X=t_1+t_2>0 α X ′ = t 1 + t 2 > 0 .
For a block D D D of the partition, [ q . b ∈ D ] [q.b\in D] [ q . b ∈ D ] is the same for all states q q q of any one block, so
( α ′ T M ′ ) D = ∑ B α B ′ ∑ b p b [ B . b ⊆ D ] = ∑ q α q ∑ b p b [ q . b ∈ D ] = ∑ q ′ ∈ D ( α T M ) q ′ = α ( D ) = α D ′ , (\alpha'^{\mathsf T}M')_D=\sum_B\alpha'_B\sum_b p_b[B.b\subseteq D]=\sum_q\alpha_q\sum_b p_b[q.b\in D]=\sum_{q'\in D}(\alpha^{\mathsf T}M)_{q'}=\alpha(D)=\alpha'_D, ( α ′ T M ′ ) D = B ∑ α B ′ b ∑ p b [ B . b ⊆ D ] = q ∑ α q b ∑ p b [ q . b ∈ D ] = q ′ ∈ D ∑ ( α T M ) q ′ = α ( D ) = α D ′ ,
where B B B runs over the blocks, α B ′ = α ( B ) \alpha'_B=\alpha(B) α B ′ = α ( B ) , and M ′ M' M ′ is the weighted matrix of A ′ A' A ′ with the same weights. So α ′ \alpha' α ′ is positive, stationary and constant off one state of A ′ A' A ′ , and Theorem 3.1 gives rt ( A ′ ) ≤ ( n − 2 ) 2 \operatorname{rt}(A')\leq(n-2)^2 rt ( A ′ ) ≤ ( n − 2 ) 2 . □
Binary automata
From now on Σ = { a , b } \Sigma=\{a,b\} Σ = { a , b } , A A A is strongly connected and synchronizing with n ≥ 4 n\geq4 n ≥ 4 states, and ( E , s , p ) (E,s,p) ( E , s , p ) is a witness of degree two with X = { x 1 , x 2 } X=\{x_1,x_2\} X = { x 1 , x 2 } . (For n ≤ 3 n\leq3 n ≤ 3 every synchronizing automaton has rt ≤ ( n 3 − n ) / 6 ≤ ( n − 1 ) 2 \operatorname{rt}\leq(n^3-n)/6\leq(n-1)^2 rt ≤ ( n 3 − n ) /6 ≤ ( n − 1 ) 2 [9 , 5 ] .)
Lemma 5.7. (a) The weights p = ( 1 2 , 1 2 ) p=\left(\frac12,\frac12\right) p = ( 2 1 , 2 1 ) are admissible for ( E , s ) (E,s) ( E , s ) .
(b) With these weights, exactly two edges lead from E E E into X ∪ { s } X\cup\{s\} X ∪ { s } (the boundary edges), and the vector t t t of Lemma 5.5 depends only on the configuration
( x 1 . a , x 1 . b , x 2 . a , x 2 . b ; ν 1 , ν 2 ) , x i . c ∈ { x 1 , x 2 , s } , (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\}, ( x 1 . a , x 1 . b , x 2 . a , x 2 . b ; ν 1 , ν 2 ) , x i . c ∈ { x 1 , x 2 , s } ,
where ν i \nu_i ν i is the number of boundary edges that end at x i x_i x i : Z i j = 1 2 ∣ { c : x i . c = x j } ∣ Z_{ij}=\frac12|\{c:x_i.c=x_j\}| Z ij = 2 1 ∣ { c : x i . c = x j } ∣ and y i = ν i 2 y_i=\frac{\nu_i}{2} y i = 2 ν i .
Proof. (a) For r ∈ E ∖ { s } r\in E\setminus\{s\} r ∈ E ∖ { s } let i c ( r ) = ∣ { r } c − 1 ∣ i_c(r)=|\{r\}c^{-1}| i c ( r ) = ∣ { r } c − 1 ∣ , and call ( i a ( r ) , i b ( r ) ) (i_a(r),i_b(r)) ( i a ( r ) , i b ( r )) the type of r r r . In-weight one means p a i a ( r ) + p b i b ( r ) = 1 p_ai_a(r)+p_bi_b(r)=1 p a i a ( r ) + p b i b ( r ) = 1 . If i a ( r ) = i b ( r ) i_a(r)=i_b(r) i a ( r ) = i b ( r ) , this forces i a ( r ) = i b ( r ) = 1 i_a(r)=i_b(r)=1 i a ( r ) = i b ( r ) = 1 and holds for all p p p . Otherwise it reads p a ( i a ( r ) − i b ( r ) ) = 1 − i b ( r ) p_a(i_a(r)-i_b(r))=1-i_b(r) p a ( i a ( r ) − i b ( r )) = 1 − i b ( r ) and forces p a p_a p a to one value; as p a < p a < 1 p_a<p_a<1 p a < p a < 1 , the case i b ( r ) = 1 i_b(r)=1 i b ( r ) = 1 is impossible and would give i a ( r ) = 1 i_a(r)=1 i a ( r ) = 1 , i b ( r ) > 2 i_b(r)>2 i b ( r ) > 2 forces i a ( r ) = 0 i_a(r)=0 i a ( r ) = 0 (as p a = ( i b ( r ) − 1 ) / ( i b ( r ) − i a ( r ) ) < 1 p_a=(i_b(r)-1)/(i_b(r)-i_a(r))<1 p a = ( i b ( r ) − 1 ) / ( i b ( r ) − i a ( r )) < 1 ), and i b ( r ) = 0 i_b(r)=0 i b ( r ) = 0 forces i a ( r ) ≥ 2 i_a(r)\geq2 i a ( r ) ≥ 2 (as p a = 1 / i a ( r ) < 1 p_a=1/i_a(r)<1 p a = 1/ i a ( r ) < 1 ); so this happens only for ( i a , i b ) = ( k , 0 ) (i_a,i_b)=(k,0) ( i a , i b ) = ( k , 0 ) , p a = 1 / k p_a=1/k p a = 1/ k , or ( 0 , k ) (0,k) ( 0 , k ) , p b = 1 / k p_b=1/k p b = 1/ k , with k ≥ 2 k\geq2 k ≥ 2 . Suppose some r r r has type ( k , 0 ) (k,0) ( k , 0 ) with k ≥ 3 k\geq3 k ≥ 3 , and let N ≥ 1 N\geq1 N ≥ 1 be the number of such states. No state then has type ( 0 , j ) (0,j) ( 0 , j ) with j ≥ 2 j \ge2 j ≥ 2 (it would force p a = 1 − 1 / j ≥ 1 / 2 p_a=1-1/j \ge1/2 p a = 1 − 1/ j ≥ 1/2 , but p a = 1 / k ≤ 1 / 3 p_a=1/k \le1/3 p a = 1/ k ≤ 1/3 ) or type ( k ′ , 0 ) (k',0) ( k ′ , 0 ) with k ′ ≠ k k' \ne k k ′ = k (it would force p a = 1 / k ′ ≠ 1 / k p_a=1/k' \ne1/k p a = 1/ k ′ = 1/ k ), so the other states of E ∖ { s } E \setminus\{s\} E ∖ { s } have type ( 1 , 1 ) (1,1) ( 1 , 1 ) . Count the n n n edges labeled a a a : those ending in the n − 3 n-3 n − 3 states of E ∖ { s } E \setminus\{s\} E ∖ { s } number ( n − 3 − N ) + N k (n-3-N)+Nk ( n − 3 − N ) + N k , and the two a a a -edges that start in X X X end in X ∪ { s } X \cup\{s\} X ∪ { s } . So n ≥ ( n − 3 − N ) + N k + 2 = n − 1 + N ( k − 1 ) ≥ n + 1 n \ge(n-3-N)+Nk+2=n-1+N(k-1)\ge n+1 n ≥ ( n − 3 − N ) + N k + 2 = n − 1 + N ( k − 1 ) ≥ n + 1 , which is impossible. The case ( 0 , k ) (0,k) ( 0 , k ) is symmetric. So every forced value is 1 / 2 1/2 1/2 , and p = ( 1 / 2 , 1 / 2 ) p=(1/2,1/2) p = ( 1/2 , 1/2 ) is admissible.
(b) With p = ( 1 / 2 , 1 / 2 ) p=(1/2,1/2) p = ( 1/2 , 1/2 ) an in-weight equals half the in-degree. The in-degrees add up to 2 n 2n 2 n , and E ∖ { s } E \setminus\{s\} E ∖ { s } receives 2 ( n − 3 ) 2(n-3) 2 ( n − 3 ) edges; so X ∪ { s } X \cup\{s\} X ∪ { s } receives six. The four edges that start in X X X end in X ∪ { s } X \cup\{s\} X ∪ { s } , so exactly two of the six come from E E E . Hence y y y and Z Z Z are as stated, and t = y ( I − Z ) − 1 t=y(I-Z)^{-1} t = y ( I − Z ) − 1 by Lemma 5.5 . □
There are 3 4 ⋅ 5 = 405 3^4 \cdot5=405 3 4 ⋅ 5 = 405 choices of the four targets and of the pair ( ν 1 , ν 2 ) (\nu_1,\nu_2) ( ν 1 , ν 2 ) , with ν 1 + ν 2 ≤ 2 \nu_1+\nu_2 \le2 ν 1 + ν 2 ≤ 2 and ( ν 1 , ν 2 ) ≠ ( 0 , 0 ) (\nu_1,\nu_2)\ne(0,0) ( ν 1 , ν 2 ) = ( 0 , 0 ) (if no edge enters X X X from E E E , then E E E is closed and A \mathcal{A} A is not strongly connected). We list configurations up to renaming x 1 ↔ x 2 x_1 \leftrightarrow x_2 x 1 ↔ x 2 and a ↔ b a \leftrightarrow b a ↔ b .
Lemma 5.8. Exactly 179 of the 405 configurations have det ( I − Z ) ≠ 0 \det(I-Z)\ne0 det ( I − Z ) = 0 and t 1 , t 2 > 0 t_1,t_2>0 t 1 , t 2 > 0 ; up to renaming they form 49 configurations, and their classes { t 1 , t 2 } \{t_1,t_2\} { t 1 , t 2 } are exactly the 14 of Table 1.
Proof. For a configuration, Z Z Z and y y y are given by the formulas of Lemma 5.7(b)}: Z = 1 2 G Z=\frac{1}{2}G Z = 2 1 G , where G i j G_{ij} G ij is the number of letters that map x i x_i x i to x j x_j x j , and y = 1 2 ( ν 1 , ν 2 ) y=\frac{1}{2}(\nu_1,\nu_2) y = 2 1 ( ν 1 , ν 2 ) . Let Δ = det ( 2 I − G ) = 4 det ( I − Z ) \Delta=\det(2I-G)=4\det(I-Z) Δ = det ( 2 I − G ) = 4 det ( I − Z ) . When Δ ≠ 0 \Delta\ne0 Δ = 0 , the vector t = y ( I − Z ) − 1 = ( ν 1 , ν 2 ) ( 2 I − G ) − 1 t=y(I-Z)^{-1}=(\nu_1,\nu_2)(2I-G)^{-1} t = y ( I − Z ) − 1 = ( ν 1 , ν 2 ) ( 2 I − G ) − 1 is
t 1 = ( 2 − G 22 ) ν 1 + G 21 ν 2 Δ , t 2 = G 12 ν 1 + ( 2 − G 11 ) ν 2 Δ . t_1=\frac{(2-G_{22})\nu_1+G_{21}\nu_2}{\Delta},\qquad t_2=\frac{G_{12}\nu_1+(2-G_{11})\nu_2}{\Delta}. t 1 = Δ ( 2 − G 22 ) ν 1 + G 21 ν 2 , t 2 = Δ G 12 ν 1 + ( 2 − G 11 ) ν 2 . Evaluating Δ \Delta Δ , t 1 t_1 t 1 and t 2 t_2 t 2 for the 3 4 3^4 3 4 choices of the four targets and the five pairs ( ν 1 , ν 2 ) (\nu_1,\nu_2) ( ν 1 , ν 2 ) leaves exactly 179 configurations with Δ ≠ 0 \Delta\ne0 Δ = 0 and t 1 , t 2 > 0 t_1,t_2>0 t 1 , t 2 > 0 . Each row of G G G sums to at most 2; so Δ = ( 2 − G 11 ) ( 2 − G 22 ) − G 12 G 21 ≥ 0 \Delta=(2-G_{11})(2-G_{22})-G_{12}G_{21}\ge0 Δ = ( 2 − G 11 ) ( 2 − G 22 ) − G 12 G 21 ≥ 0 , with equality if and only if { x 1 } \{x_1\} { x 1 } , { x 2 } \{x_2\} { x 2 } or X X X is closed (G 11 = 2 G_{11}=2 G 11 = 2 , or G 22 = 2 G_{22}=2 G 22 = 2 , or both rows sum to 2), which excludes 26 of the 81 choices of the four targets. For the other 55, G 11 < 2 G_{11}<2 G 11 < 2 and G 22 < 2 G_{22}<2 G 22 < 2 ; so by the formula t 1 > 0 t_1>0 t 1 > 0 if and only if ν 1 > 0 \nu_1>0 ν 1 > 0 , or ν 2 > 0 \nu_2>0 ν 2 > 0 and G 21 > 0 G_{21}>0 G 21 > 0 , and likewise for t 2 t_2 t 2 , with G 12 G_{12} G 12 . As 31 of the 55 have G 12 > 0 G_{12}>0 G 12 > 0 and 31 have G 21 > 0 G_{21}>0 G 21 > 0 , the pair ( 1 , 1 ) (1,1) ( 1 , 1 ) gives 55 configurations and each of the other four pairs gives 31: 55 + 4 ⋅ 31 = 179 55+4\cdot31=179 55 + 4 ⋅ 31 = 179 . The two renamings generate a group of order four, which permutes these 179 configurations and preserves the class. It has one orbit of size one, seven orbits of size two and 41 orbits of size four, and 1 + 7 ⋅ 2 + 41 ⋅ 4 = 179 1+7\cdot2+41\cdot4=179 1 + 7 ⋅ 2 + 41 ⋅ 4 = 179 ; so there are 1 + 7 + 41 = 49 1+7+41=49 1 + 7 + 41 = 49 configurations up to renaming. Table 2 lists one configuration of each orbit, with its class; the classes that occur are the 14 of Table 1. □
The 49 configurations of Lemma 5.8, by class, up to renaming x 1 ↔ x 2 x_1 \leftrightarrow x_2 x 1 ↔ x 2 and a ↔ b a \leftrightarrow b a ↔ b . A configuration is written ( x 1 . a , x 1 . b , x 2 . a , x 2 . b ; ν 1 , ν 2 ) (x_1.a,x_1.b,x_2.a,x_2.b;\nu_1,\nu_2) ( x 1 . a , x 1 . b , x 2 . a , x 2 . b ; ν 1 , ν 2 ) , where ν i \nu_i ν i is the number of edges from E E E that end at x i x_i x i .
Table 2.
By Lemma 5.5 the configuration of every witness of degree two of a strongly connected binary automaton is among these 49.
Theorem 5.9. Let A \mathcal{A} A be a binary, strongly connected, synchronizing automaton that is quasi-Eulerian of degree two. Suppose that some witness of A \mathcal{A} A has a configuration other than the following three (up to renaming, in the notation of Table 2 ): ( s , x 1 , x 1 , s ; 0 , 1 ) (s,x_1,x_1,s;0,1) ( s , x 1 , x 1 , s ; 0 , 1 ) and ( s , s , x 1 , x 1 ; 0 , 1 ) (s,s,x_1,x_1;0,1) ( s , s , x 1 , x 1 ; 0 , 1 ) in the class { 1 / 2 , 1 / 2 } \{1/2,1/2\} { 1/2 , 1/2 } , and ( s , x 1 , x 1 , s ; 1 , 1 ) (s,x_1,x_1,s;1,1) ( s , x 1 , x 1 , s ; 1 , 1 ) in the class { 1 / 2 , 2 / 3 } \{1/2,2/3\} { 1/2 , 2/3 } . Then rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A})\le(n-1)^2 rt ( A ) ≤ ( n − 1 ) 2 .
Proof of Theorem 5.9. For n ≤ 3 n\le3 n ≤ 3 see the start of this subsection. For n ≥ 4 n\ge4 n ≥ 4 the bound follows from Theorem 3.1 in the classes { 1 , 1 } \{1,1\} { 1 , 1 } , { 1 / 2 , 1 } \{1/2,1\} { 1/2 , 1 } and { 1 , 2 } \{1,2\} { 1 , 2 } , since one of t 1 , t 2 t_1,t_2 t 1 , t 2 equals 1, and from Proposition 5.6 in the block configurations; in Table 2 , those outside these three classes are, up to renaming, ( s , s , s , s ; 1 , 1 ) (s,s,s,s;1,1) ( s , s , s , s ; 1 , 1 ) and ( s , x 1 , s , x 1 ; 0 , 1 ) (s,x_1,s,x_1;0,1) ( s , x 1 , s , x 1 ; 0 , 1 ) in { 1 / 2 , 1 / 2 } \{1/2,1/2\} { 1/2 , 1/2 } , ( s , x 2 , s , x 1 ; 0 , 1 ) (s,x_2,s,x_1;0,1) ( s , x 2 , s , x 1 ; 0 , 1 ) in { 1 / 3 , 2 / 3 } \{1/3,2/3\} { 1/3 , 2/3 } , ( s , x 2 , s , x 1 ; 0 , 2 ) (s,x_2,s,x_1;0,2) ( s , x 2 , s , x 1 ; 0 , 2 ) and ( s , x 1 , s , x 1 ; 1 , 1 ) (s,x_1,s,x_1;1,1) ( s , x 1 , s , x 1 ; 1 , 1 ) in { 1 / 3 , 1 / 3 } \{1/3,1/3\} { 1/3 , 1/3 } . The remaining six configurations are treated in Propositions 5.11–5.13 , and the nine configurations of the integer classes { 2 , 2 } \{2,2\} { 2 , 2 } , { 2 , 3 } \{2,3\} { 2 , 3 } , { 2 , 4 } \{2,4\} { 2 , 4 } in Proposition 5.14, with the tier lemma (Lemma 2.4). These propositions are proved below, after the definitions they use. □
The 14 classes { t 1 , t 2 } \{t_1,t_2\} { 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 ≤ ( n − 1 ) 2 \operatorname{rt} \le(n-1)^2 rt ≤ ( n − 1 ) 2 . A block configuration satisfies the hypothesis of Proposition 5.6.
Table 1 (PDF p. 15).
For the rest of this section we replace p p p by the weights ( 1 2 , 1 2 ) \left(\frac{1}{2},\frac{1}{2}\right) ( 2 1 , 2 1 ) , admissible by Lemma 5.7(a), and fix the stationary vector α \alpha α of Lemma 5.5 for them (α = 1 \alpha=1 α = 1 on E E E , α x i = t i > 0 \alpha_{x_i}=t_i>0 α x i = t i > 0 ); the class { t 1 , t 2 } \{t_1,t_2\} { t 1 , t 2 } of the witness always refers to these weights. Put g i = t i − 1 g_i=t_i-1 g i = t i − 1 . For a set K K K let e i ( K ) = [ x i ∈ K ] e_i(K)=[x_i\in K] e i ( K ) = [ x i ∈ K ] , e s ( K ) = [ s ∈ K ] e_s(K)=[s\in K] e s ( K ) = [ s ∈ K ] , and call P ( K ) = ( e 1 ( K ) , e 2 ( K ) , e s ( K ) ) P(K)=(e_1(K),e_2(K),e_s(K)) P ( K ) = ( e 1 ( K ) , e 2 ( K ) , e s ( K )) the pattern of K K K and ( e 1 ( K ) , e 2 ( K ) ) (e_1(K),e_2(K)) ( e 1 ( K ) , e 2 ( K )) its X X X -part; then α ( K ) = ∣ K ∣ + g 1 e 1 ( K ) + g 2 e 2 ( K ) \alpha(K)=|K|+g_1e_1(K)+g_2e_2(K) α ( K ) = ∣ K ∣ + g 1 e 1 ( K ) + g 2 e 2 ( K ) . For a nonempty proper K K K let m ( K ) m(K) m ( K ) be the cost of K K K for this α \alpha α ; by Lemma 2.2, m ( K ) ≤ n − 1 m(K)\le n-1 m ( K ) ≤ n − 1 and some word of length m ( K ) m(K) m ( K ) raises α \alpha α . For a state q q q let esc q ( K ) \operatorname{esc}_q(K) esc q ( K ) be the least length of a word that moves q q q across K K K , as in Lemma 2.3. We use the following extension process. From a nonempty proper set K 0 K_0 K 0 , replace K K K by K w − 1 K w^{-1} K w − 1 for a word w w w of length m ( K ) m(K) m ( K ) that raises α \alpha α , until Q Q Q is reached. The values α ( K ) \alpha(K) α ( K ) of the visited sets increase strictly; so no set is visited twice, every visited set is nonempty (as α ( K ) ≥ α ( K 0 ) > 0 \alpha(K) \ge\alpha(K_0) > 0 α ( K ) ≥ α ( K 0 ) > 0 ), and the process reaches Q Q Q . Each value is carried by at most one visited set. The words, read from the last to the first, map Q Q Q into K 0 K_0 K 0 . So if K 0 K_0 K 0 is a singleton, or K 0 = { q } c − 1 K_0 = \{q\}c^{-1} K 0 = { q } c − 1 for a letter c c c , then rt ( A ) \operatorname{rt}(\mathcal{A}) rt ( A ) is at most ∑ m ( K ) \sum m(K) ∑ m ( K ) over the visited proper sets K K K , plus 0 0 0 , or plus 1 1 1 , respectively.
For a letter c c c , e i ( K c − 1 ) = [ x i . c ∈ K ] e_i(Kc^{-1}) = [x_i.c \in K] e i ( K c − 1 ) = [ x i . c ∈ K ] with x i . c ∈ X ∪ { s } x_i.c \in X \cup\{s\} x i . c ∈ X ∪ { s } ; so the change of ( e 1 , e 2 ) (e_1,e_2) ( e 1 , e 2 ) under c c c depends only on P ( K ) P(K) P ( K ) . Call a pattern good if for some letter c c c and some (equivalently, every) set K K K with this pattern the number g 1 ( e 1 ( K c − 1 ) − e 1 ( K ) ) + g 2 ( e 2 ( K c − 1 ) − e 2 ( K ) ) g_1(e_1(Kc^{-1}) - e_1(K)) + g_2(e_2(Kc^{-1}) - e_2(K)) g 1 ( e 1 ( K c − 1 ) − e 1 ( K )) + g 2 ( e 2 ( K c − 1 ) − e 2 ( K )) is not an integer. Then α ( K c − 1 ) − α ( K ) \alpha(Kc^{-1}) - \alpha(K) α ( K c − 1 ) − α ( K ) is an integer plus a non-integer, so m ( K ) = 1 m(K) = 1 m ( K ) = 1 for every set K K K with a good pattern. The patterns ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) and ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) are called aligned ; they are never good: for them X ∪ { s } X \cup\{s\} X ∪ { s } lies in K K K or is disjoint from K K K , and both letters map x 1 x_1 x 1 and x 2 x_2 x 2 into X ∪ { s } X \cup\{s\} X ∪ { s } , so no letter changes e 1 e_1 e 1 or e 2 e_2 e 2 .
Lemma 5.10 (joint orbit). Let K K K be a nonempty proper set, and k = ∣ K ∣ k = |K| k = ∣ K ∣ . Suppose first that P ( K ) = ( 1 , 1 , 1 ) P(K) = (1,1,1) P ( K ) = ( 1 , 1 , 1 ) . Then esc s ( K ) ≤ k − 2 \operatorname{esc}_s(K) \le k - 2 esc s ( K ) ≤ k − 2 , and x 1 . w , x 2 . w ∈ K x_1.w,x_2.w \in K x 1 . w , x 2 . w ∈ K for every word w w w with ∣ w ∣ ≤ esc s ( K ) |w| \le\operatorname{esc}_s(K) ∣ w ∣ ≤ esc s ( K ) . If the pattern ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) is good, then m ( K ) ≤ k − 1 m(K) \le k-1 m ( K ) ≤ k − 1 . Symmetrically, if P ( K ) = ( 0 , 0 , 0 ) P(K) = (0,0,0) P ( K ) = ( 0 , 0 , 0 ) , then esc s ( K ) ≤ n − k − 2 \operatorname{esc}_s(K) \le n-k-2 esc s ( K ) ≤ n − k − 2 , and if ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) is good, then m ( K ) ≤ n − k − 1 m(K) \le n-k-1 m ( K ) ≤ n − k − 1 .
Proof. Let f f f be the least length of a word w w w with q . w ∉ K q.w \notin K q . w ∈ / K for some q ∈ { x 1 , x 2 , s } q \in\{x_1,x_2,s\} q ∈ { x 1 , x 2 , s } ; it is finite as A \mathcal{A} A is strongly connected. If it were attained at q = x i q = x_i q = x i with w = c w ′ w = cw' w = c w ′ , then q . c ∈ X ∪ { s } q.c \in X \cup\{s\} q . c ∈ X ∪ { s } and ( q . c ) . w ′ ∉ K (q.c).w' \notin K ( q . c ) . w ′ ∈ / K with ∣ w ′ ∣ = f − 1 |w'| = f-1 ∣ w ′ ∣ = f − 1 , a contradiction. So f = esc s ( K ) f = \operatorname{esc}_s(K) f = esc s ( K ) , and x 1 . w , x 2 . w ∈ K x_1.w,x_2.w \in K x 1 . w , x 2 . w ∈ K whenever ∣ w ∣ ≤ f |w| \le f ∣ w ∣ ≤ f . Let R j = { q . w : q ∈ { x 1 , x 2 , s } , ∣ w ∣ ≤ j } R_j = \{q.w : q \in\{x_1,x_2,s\}, |w| \le j\} R j = { q . w : q ∈ { x 1 , x 2 , s } , ∣ w ∣ ≤ j } . Then R f − 1 ⊆ K R_{f-1} \subseteq K R f − 1 ⊆ K , and the chain R 0 ⊊ R 1 ⊊ ⋯ ⊊ R f − 1 R_0 \subsetneq R_1 \subsetneq\cdots\subsetneq R_{f-1} R 0 ⊊ R 1 ⊊ ⋯ ⊊ R f − 1 is strict, since R j = R j + 1 R_j = R_{j+1} R j = R j + 1 would make R j ⊆ K R_j \subseteq K R j ⊆ K a closed proper subset. As ∣ R 0 ∣ = 3 |R_0| = 3 ∣ R 0 ∣ = 3 , f + 2 ≤ k f+2 \le k f + 2 ≤ k . Let w w w have length f f f with s . w ∉ K s.w \notin K s . w ∈ / K ; then P ( K w − 1 ) = ( 1 , 1 , 0 ) P(Kw^{-1}) = (1,1,0) P ( K w − 1 ) = ( 1 , 1 , 0 ) , and P ( K v − 1 ) = ( 1 , 1 , 1 ) P(Kv^{-1}) = (1,1,1) P ( K v − 1 ) = ( 1 , 1 , 1 ) for ∣ v ∣ < f |v| < f ∣ v ∣ < f . If α \alpha α changes under a word of length at most f f f , then m ( K ) ≤ f m(K) \le f m ( K ) ≤ f . Otherwise α ( K w − 1 ) = α ( K ) \alpha(Kw^{-1}) = \alpha(K) α ( K w − 1 ) = α ( K ) , and as ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) is good, a letter c c c has α ( K ( c w ) − 1 ) = α ( ( K w − 1 ) c − 1 ) ≠ α ( K w − 1 ) = α ( K ) \alpha(K(cw)^{-1}) = \alpha((Kw^{-1})c^{-1}) \ne\alpha(Kw^{-1}) = \alpha(K) α ( K ( c w ) − 1 ) = α (( K w − 1 ) c − 1 ) = α ( K w − 1 ) = α ( K ) ; so m ( K ) ≤ f + 1 ≤ k − 1 m(K) \le f+1 \le k-1 m ( K ) ≤ f + 1 ≤ k − 1 . For P ( K ) = ( 0 , 0 , 0 ) P(K) = (0,0,0) P ( K ) = ( 0 , 0 , 0 ) apply this to Q ∖ K Q \setminus K Q ∖ K , which has pattern ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) , using α ( ( Q ∖ K ) w ) = α ( Q ) − α ( K w − 1 ) \alpha((Q \setminus K)w) = \alpha(Q) - \alpha(Kw^{-1}) α (( Q ∖ K ) w ) = α ( Q ) − α ( K w − 1 ) ; the pattern ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) is good because ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) is, as passing to the complement changes the sign of every change of e 1 e_1 e 1 and e 2 e_2 e 2 .
Proposition 5.11. If the witness has class { 1 2 , 3 4 } \left\{\frac{1}{2},\frac{3}{4}\right\} { 2 1 , 4 3 } or { 1 4 , 1 2 } \left\{\frac{1}{4},\frac{1}{2}\right\} { 4 1 , 2 1 } , then rt ( A ) ≤ 1 + ( n − 2 ) n = ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le1+(n-2)n = (n-1)^2 rt ( A ) ≤ 1 + ( n − 2 ) n = ( n − 1 ) 2 .
Proof. Each of these two classes contains exactly one configuration (Lemma 5.8 and Table 1); after renaming, x 1 . a = x 1 . b = x 2 . a = s x_1.a = x_1.b = x_2.a = s x 1 . a = x 1 . b = x 2 . a = s and x 2 . b = x 1 x_2.b = x_1 x 2 . b = x 1 . In { 1 2 , 3 4 } \left\{\frac{1}{2},\frac{3}{4}\right\} { 2 1 , 4 3 } one boundary edge ends at each x i x_i x i , and ( t 1 , t 2 ) = ( 3 4 , 1 2 ) (t_1,t_2) = \left(\frac{3}{4},\frac{1}{2}\right) ( t 1 , t 2 ) = ( 4 3 , 2 1 ) ; in { 1 4 , 1 2 } \left\{\frac{1}{4},\frac{1}{2}\right\} { 4 1 , 2 1 } one boundary edge ends at x 2 x_2 x 2 and one at s s s , and ( t 1 , t 2 ) = ( 1 4 , 1 2 ) (t_1,t_2) = \left(\frac{1}{4},\frac{1}{2}\right) ( t 1 , t 2 ) = ( 4 1 , 2 1 ) . In both, g 1 , g 2 ∈ ( − 1 , 0 ) g_1,g_2 \in(-1,0) g 1 , g 2 ∈ ( − 1 , 0 ) , and none of g 1 , g 2 , g 1 + g 2 , g 1 − g 2 g_1,g_2,g_1+g_2,g_1-g_2 g 1 , g 2 , g 1 + g 2 , g 1 − g 2 is an integer.
First, every pattern that is not aligned is good. Under b b b , e 1 e_1 e 1 becomes e s e_s e s and e 2 e_2 e 2 becomes e 1 e_1 e 1 , so the change of α \alpha α is an integer plus g 1 ( e s − e 1 ) + g 2 ( e 1 − e 2 ) g_1(e_s-e_1)+g_2(e_1-e_2) g 1 ( e s − e 1 ) + g 2 ( e 1 − e 2 ) . If e s ≠ e 1 e_s \ne e_1 e s = e 1 , this is ± g 1 \pm g_1 ± g 1 or ± ( g 1 − g 2 ) \pm(g_1-g_2) ± ( g 1 − g 2 ) ; if e s = e 1 ≠ e 2 e_s = e_1 \ne e_2 e s = e 1 = e 2 , it is ± g 2 \pm g_2 ± g 2 . None is an integer.
Second, the process visits at most one set of each size with each X X X -part: two such sets would have the same value α ( K ) = ∣ K ∣ + g 1 e 1 ( K ) + g 2 e 2 ( K ) \alpha(K)=|K|+g_1e_1(K)+g_2e_2(K) α ( K ) = ∣ K ∣ + g 1 e 1 ( K ) + g 2 e 2 ( K ) , but the values of the visited sets increase strictly.
Third, we choose the starting set. In { 1 2 , 3 4 } \left\{\frac{1}{2},\frac{3}{4}\right\} { 2 1 , 4 3 } start from K 0 = { q } c − 1 K_0 = \{q\}c^{-1} K 0 = { q } c − 1 for a merging letter c c c ; then α ( K 0 ) ≥ 2 + g 1 + g 2 = 5 4 \alpha(K_0) \ge2+g_1+g_2 = \frac{5}{4} α ( K 0 ) ≥ 2 + g 1 + g 2 = 4 5 . In { 1 4 , 1 2 } \left\{\frac{1}{4},\frac{1}{2}\right\} { 4 1 , 2 1 } , the state s s s is entered exactly by x 1 . a , x 1 . b , x 2 . a x_1.a,x_1.b,x_2.a x 1 . a , x 1 . b , x 2 . a and one boundary edge r . c ′ r.c' r . c ′ ; so { s } a − 1 \{s\}a^{-1} { s } a − 1 and { s } b − 1 \{s\}b^{-1} { s } b − 1 are { x 1 , x 2 , r } \{x_1,x_2,r\} { x 1 , x 2 , r } and { x 1 } \{x_1\} { x 1 } if c ′ = a c'=a c ′ = a , and { x 1 , x 2 } \{x_1,x_2\} { x 1 , x 2 } and { x 1 , r } \{x_1,r\} { x 1 , r } if c ′ = b c'=b c ′ = b . Start from { x 1 , x 2 , r } \{x_1,x_2,r\} { x 1 , x 2 , r } (α = 7 4 \alpha= \frac{7}{4} α = 4 7 ) or { x 1 , r } \{x_1,r\} { x 1 , r } (α = 5 4 \alpha= \frac{5}{4} α = 4 5 ), respectively. (A merging letter alone would not do: { s } a − 1 \{s\}a^{-1} { s } a − 1 may be X X X , with α ( X ) = 3 4 < 1 \alpha(X)=\frac{3}{4}<1 α ( X ) = 4 3 < 1 .) In both classes α ( K 0 ) > 1 ≥ α ( { q } ) \alpha(K_0)>1\ge\alpha(\{q\}) α ( K 0 ) > 1 ≥ α ({ q }) for every state q q q , so every visited set has size between 2 and n − 1 n-1 n − 1 .
Finally, we bound the cost of the visited sets of each size. Let 2 ≤ k ≤ n − 1 2\le k\le n-1 2 ≤ k ≤ n − 1 . A visited set of size k k k with X X X -part ( 1 , 1 ) (1,1) ( 1 , 1 ) costs at most k − 1 k-1 k − 1 if it contains s s s (Lemma 5.10; the pattern ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) is good) and 1 otherwise; one with X X X -part ( 0 , 0 ) (0,0) ( 0 , 0 ) costs at most n − k − 1 n-k-1 n − k − 1 if it avoids s s s and 1 otherwise, and it does not exist for k = n − 1 k=n-1 k = n − 1 ; the other two cost 1. So the visited sets of size k k k cost at most n n n in total, and rt ( A ) ≤ 1 + ∑ k = 2 n − 1 n = 1 + ( n − 2 ) n \operatorname{rt}(A)\le1+\sum_{k=2}^{n-1}n=1+(n-2)n rt ( A ) ≤ 1 + ∑ k = 2 n − 1 n = 1 + ( n − 2 ) n .
Proposition 5.12. If the witness has, up to renaming, the configuration ( s , x 2 , x 1 , s ; 0 , 1 ) (s,x_2,x_1,s;0,1) ( s , x 2 , x 1 , s ; 0 , 1 ) (class { 1 3 , 2 3 } \{\frac{1}{3},\frac{2}{3}\} { 3 1 , 3 2 } ) or ( s , x 2 , x 1 , s ; 0 , 2 ) (s,x_2,x_1,s;0,2) ( s , x 2 , x 1 , s ; 0 , 2 ) (class { 2 3 , 1 3 } \{\frac{2}{3},\frac{1}{3}\} { 3 2 , 3 1 } ), that is, x 1 . a = s x_1.a=s x 1 . a = s , x 1 . b = x 2 x_1.b=x_2 x 1 . b = x 2 , x 2 . a = x 1 x_2.a=x_1 x 2 . a = x 1 , x 2 . b = s x_2.b=s x 2 . b = s , then rt ( A ) ≤ n 2 − 3 n + 5 ≤ ( n − 1 ) 2 \operatorname{rt}(A)\le n^2-3n+5\le(n-1)^2 rt ( A ) ≤ n 2 − 3 n + 5 ≤ ( n − 1 ) 2 .
Proof. Here one ({ 1 3 , 2 3 } \{\frac{1}{3},\frac{2}{3}\} { 3 1 , 3 2 } ) or two ({ 2 3 , 4 3 } \{\frac{2}{3},\frac{4}{3}\} { 3 2 , 3 4 } ) boundary edges end at x 2 x_2 x 2 (in { 1 3 , 2 3 } \{\frac{1}{3},\frac{2}{3}\} { 3 1 , 3 2 } the other one ends at s s s ), and ( g 1 , g 2 ) = ( − 2 3 , − 1 3 ) (g_1,g_2)=(-\frac{2}{3},-\frac{1}{3}) ( g 1 , g 2 ) = ( − 3 2 , − 3 1 ) , resp. ( − 1 3 , 1 3 ) (-\frac{1}{3},\frac{1}{3}) ( − 3 1 , 3 1 ) . Under a a a , e 1 e_1 e 1 becomes e s e_s e s and e 2 e_2 e 2 becomes e 1 e_1 e 1 . For the six patterns that are not aligned, the change of ( e 1 , e 2 ) (e_1,e_2) ( e 1 , e 2 ) under a a a is ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) , ( 0 , − 1 ) (0,-1) ( 0 , − 1 ) , ( 1 , 0 ) (1,0) ( 1 , 0 ) , ( − 1 , 0 ) (-1,0) ( − 1 , 0 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) or ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) , and g 1 g_1 g 1 , g 2 g_2 g 2 and g 1 − g 2 g_1-g_2 g 1 − g 2 are not integers; so every pattern that is not aligned is good. Moreover g 1 + g 2 g_1+g_2 g 1 + g 2 is an integer (− 1 -1 − 1 , resp. 0 0 0 ): the X X X -parts ( 1 , 1 ) (1,1) ( 1 , 1 ) and ( 0 , 0 ) (0,0) ( 0 , 0 ) give integer values of α \alpha α , and ( 1 , 0 ) (1,0) ( 1 , 0 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) give non-integer values; a set with a non-integer value has a pattern that is not aligned and costs 1.
The class { 2 3 , 4 3 } \{\frac{2}{3},\frac{4}{3}\} { 3 2 , 3 4 } . Here α ( K ) = ∣ K ∣ \alpha(K)=|K| α ( K ) = ∣ K ∣ for the X X X -parts ( 1 , 1 ) (1,1) ( 1 , 1 ) and ( 0 , 0 ) (0,0) ( 0 , 0 ) , and α ( Q ) = n \alpha(Q)=n α ( Q ) = n . Start from K 0 = { q } c − 1 K_0=\{q\}c^{-1} K 0 = { q } c − 1 for a merging letter c c c ; α ( K 0 ) ≥ 2 + g 1 = 5 3 \alpha(K_0)\ge2+g_1=\frac{5}{3} α ( K 0 ) ≥ 2 + g 1 = 3 5 . An integer value N ∈ { 2 , … , n − 1 } N\in\{2,\ldots,n-1\} N ∈ { 2 , … , n − 1 } is carried by a set of size N N N ; it costs at most max ( N − 1 , n − N − 1 ) \max(N-1,n-N-1) max ( N − 1 , n − N − 1 ) by Lemma 5.10 if it is aligned, and 1 otherwise. With j = N − 1 j=N-1 j = N − 1 and ℓ = n − 2 \ell=n-2 ℓ = n − 2 , ∑ j = 1 ℓ max ( j , ℓ − j ) ≤ ( ℓ − 1 ) 2 + ℓ \sum_{j=1}^{\ell}\max(j,\ell-j)\le(\ell-1)^2+\ell ∑ j = 1 ℓ max ( j , ℓ − j ) ≤ ( ℓ − 1 ) 2 + ℓ , since every term except j = ℓ j=\ell j = ℓ is at most ℓ − 1 \ell-1 ℓ − 1 . The non-integer values in [ 5 3 , n ) [\frac{5}{3},n) [ 3 5 , n ) are k ± 1 3 k\pm\frac{1}{3} k ± 3 1 with 2 ≤ k ≤ n − 1 2\le k\le n-1 2 ≤ k ≤ n − 1 (a set with X X X -part ( 1 , 0 ) (1,0) ( 1 , 0 ) or ( 0 , 1 ) (0,1) ( 0 , 1 ) has at most n − 1 n-1 n − 1 states); there are 2 ( n − 2 ) 2(n-2) 2 ( n − 2 ) of them. So rt ( A ) ≤ 1 + ( n − 3 ) 2 + ( n − 2 ) + 2 ( n − 2 ) = n 2 − 3 n + 4 \operatorname{rt}(A)\le1+(n-3)^2+(n-2)+2(n-2)=n^2-3n+4 rt ( A ) ≤ 1 + ( n − 3 ) 2 + ( n − 2 ) + 2 ( n − 2 ) = n 2 − 3 n + 4 .
The class { 1 3 , 2 3 } \{\frac{1}{3},\frac{2}{3}\} { 3 1 , 3 2 } . Here α ( K ) = ∣ K ∣ − 1 \alpha(K)=|K|-1 α ( K ) = ∣ K ∣ − 1 for the X X X -part ( 1 , 1 ) (1,1) ( 1 , 1 ) , α ( K ) = ∣ K ∣ \alpha(K)=|K| α ( K ) = ∣ K ∣ for ( 0 , 0 ) (0,0) ( 0 , 0 ) , and α ( Q ) = n − 1 \alpha(Q)=n-1 α ( Q ) = n − 1 . Start from K 0 = { q } c − 1 K_0=\{q\}c^{-1} K 0 = { q } c − 1 for a merging letter c c c ; α ( K 0 ) ≥ 2 + g 1 + g 2 = 1 \alpha(K_0)\ge2+g_1+g_2=1 α ( K 0 ) ≥ 2 + g 1 + g 2 = 1 . An integer value N ∈ { 1 , … , n − 2 } N\in\{1,\ldots,n-2\} N ∈ { 1 , … , n − 2 } is carried by a set of size N + 1 N+1 N + 1 with X X X -part ( 1 , 1 ) (1,1) ( 1 , 1 ) , which costs at most N N N if it contains s s s (Lemma 5.10) and 1 otherwise, or by a set of size N N N with X X X -part ( 0 , 0 ) (0,0) ( 0 , 0 ) , which costs at most n − N − 1 n-N-1 n − N − 1 if it avoids s s s and 1 otherwise. For N = 1 N=1 N = 1 the first set is X X X itself (cost 1), and for N = 2 N=2 N = 2 the second set is E E E , which contains s s s (cost 1); so the value N N N costs at most n − 2 n-2 n − 2 for N ∈ { 1 , n − 2 } N\in\{1,n-2\} N ∈ { 1 , n − 2 } and at most n − 3 n-3 n − 3 otherwise. The non-integer values in [ 1 , n − 1 ) [1,n-1) [ 1 , n − 1 ) number at most 2 ( n − 2 ) 2(n-2) 2 ( n − 2 ) . So rt ( A ) ≤ 1 + 2 ( n − 2 ) + ( n − 4 ) ( n − 3 ) + 2 ( n − 2 ) = n 2 − 3 n + 5 \operatorname{rt}(A)\le1+2(n-2)+(n-4)(n-3)+2(n-2)=n^2-3n+5 rt ( A ) ≤ 1 + 2 ( n − 2 ) + ( n − 4 ) ( n − 3 ) + 2 ( n − 2 ) = n 2 − 3 n + 5 .
Proposition 5.13. If the witness has class { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } or { 3 2 , 2 } \{\frac{3}{2},2\} { 2 3 , 2 } , then rt ( A ) ≤ n 2 − 3 n + 5 ≤ ( n − 1 ) 2 \operatorname{rt}(A)\le n^2-3n+5\le(n-1)^2 rt ( A ) ≤ n 2 − 3 n + 5 ≤ ( n − 1 ) 2 .
Proof. Each of these two classes contains exactly one configuration (Lemma 5.8 and Table 2): after renaming, it is ( s , x 1 , x 1 , x 1 ; 1 , 1 ) (s,x_1,x_1,x_1;1,1) ( s , x 1 , x 1 , x 1 ; 1 , 1 ) in { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } and ( s , x 2 , x 1 , x 1 ; 1 , 1 ) (s,x_2,x_1,x_1;1,1) ( s , x 2 , x 1 , x 1 ; 1 , 1 ) in { 3 2 , 2 } \{\frac{3}{2},2\} { 2 3 , 2 } . That is, x 2 . a = x 2 . b = x 1 x_2.a=x_2.b=x_1 x 2 . a = x 2 . b = x 1 , and each edge ends at x 1 x_1 x 1 and one at x 2 x_2 x 2 , x 1 . a = s x_1.a=s x 1 . a = s and x 1 . b = x 1 x_1.b=x_1 x 1 . b = x 1 in { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } , x 1 . b = x 2 x_1.b=x_2 x 1 . b = x 2 in { 3 2 , 2 } \{\frac{3}{2},2\} { 2 3 , 2 } . By the formula in the proof of Lemma 5.8, ( t 1 , t 2 ) = ( 2 , 1 2 ) (t_1,t_2)=(2,\frac{1}{2}) ( t 1 , t 2 ) = ( 2 , 2 1 ) , resp. ( 2 , 2 3 ) (2,\frac{2}{3}) ( 2 , 3 2 ) ; so g 1 = 1 g_1=1 g 1 = 1 , and α ( K ) = ∣ K ∣ + e 1 ( K ) + g 2 e 2 ( K ) \alpha(K)=|K|+e_1(K)+g_2e_2(K) α ( K ) = ∣ K ∣ + e 1 ( K ) + g 2 e 2 ( K ) with g 2 = − 1 2 g_2=-\frac{1}{2} g 2 = − 2 1 , resp. 1 2 \frac{1}{2} 2 1 .
(i) As g 1 = 1 g_1=1 g 1 = 1 is an integer and g 2 g_2 g 2 is not, α \alpha α changes whenever x 2 x_2 x 2 moves across K K K : m ( K ) ≤ esc x 2 ( K ) m(K)\le\operatorname{esc}_{x_2}(K) m ( K ) ≤ esc x 2 ( K ) .
(ii) Under either letter, e 2 e_2 e 2 becomes e 1 e_1 e 1 ; so a pattern is good if and only if e 1 ≠ e 2 e_1\ne e_2 e 1 = e 2 .
(iii) Let e 1 ( K ) = e 2 ( K ) e_1(K)=e_2(K) e 1 ( K ) = e 2 ( K ) . As both letters map x 2 x_2 x 2 to x 1 x_1 x 1 , esc x 2 ( K ) = 1 + esc x 1 ( K ) \operatorname{esc}_{x_2}(K)=1+\operatorname{esc}_{x_1}(K) esc x 2 ( K ) = 1 + esc x 1 ( K ) . If e s ( K ) = e 1 ( K ) e_s(K)=e_1(K) e s ( K ) = e 1 ( K ) , then esc x 1 ( K ) = 1 \operatorname{esc}_{x_1}(K)=1 esc x 1 ( K ) = 1 (by the letter a a a ), so m ( K ) ≤ 2 m(K)\le2 m ( K ) ≤ 2 . If K K K is aligned, then esc x 1 ( K ) = 1 + esc ( K ) \operatorname{esc}_{x_1}(K)=1+\operatorname{esc}(K) esc x 1 ( K ) = 1 + esc ( K ) : in { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } a word moves x 1 x_1 x 1 across K K K only after it has left x 1 x_1 x 1 through the edge to s s s (the letter b b b fixes x 1 x_1 x 1 , and x 1 . a = s x_1.a=s x 1 . a = s ); in { 3 2 , 2 } \{\frac{3}{2},2\} { 2 3 , 2 } , esc x 1 ( K ) = 1 + min ( esc s ( K ) , esc x 2 ( K ) ) \operatorname{esc}_{x_1}(K)=1+\min(\operatorname{esc}_s(K),\operatorname{esc}_{x_2}(K)) esc x 1 ( K ) = 1 + min ( esc s ( K ) , esc x 2 ( K )) , and the minimum is esc s ( K ) \operatorname{esc}_s(K) esc s ( K ) , since otherwise esc x 1 ( K ) = 1 + esc x 2 ( K ) = 2 + esc x 1 ( K ) \operatorname{esc}_{x_1}(K)=1+\operatorname{esc}_{x_2}(K)=2+\operatorname{esc}_{x_1}(K) esc x 1 ( K ) = 1 + esc x 2 ( K ) = 2 + esc x 1 ( K ) . So
m ( K ) ≤ 2 + esc s ( K ) m(K) \le2 + \operatorname{esc}_{s}(K) m ( K ) ≤ 2 + esc s ( K ) , which is at most ∣ K ∣ |K| ∣ K ∣ if P ( K ) = ( 1 , 1 , 1 ) P(K) = (1,1,1) P ( K ) = ( 1 , 1 , 1 ) and at most n − ∣ K ∣ n - |K| n − ∣ K ∣ if P ( K ) = ( 0 , 0 , 0 ) P(K) = (0,0,0) P ( K ) = ( 0 , 0 , 0 ) , by Lemma 5.10 .
Start from K 0 = { x 1 } K_0 = \{x_1\} K 0 = { x 1 } , with α ( K 0 ) = 2 \alpha(K_0) = 2 α ( 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 α ( Q ) \alpha(Q) α ( Q ) we list the sets that can carry it and bound their costs by (ii) and (iii); Table 3 collects them.
Table 3. The count in the proof of Proposition 5.13: for each value of α \alpha α above 2 and below α ( Q ) \alpha(Q) α ( Q ) , the sets K K K that can carry it, by their size and X X X -part ( e 1 ( K ) , e 2 ( K ) ) (e_1(K),e_2(K)) ( e 1 ( K ) , e 2 ( K )) , and the bound on the cost m ( K ) m(K) m ( K ) . A set is aligned if its pattern is ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) or ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) .
The class { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } . Here α ( K ) = ∣ K ∣ + e 1 − 1 2 e 2 \alpha(K)=|K|+e_1-\frac{1}{2}e_2 α ( K ) = ∣ K ∣ + e 1 − 2 1 e 2 and α ( Q ) = n + 1 2 \alpha(Q)=n+\frac{1}{2} α ( Q ) = n + 2 1 . An integer value N N N (so e 2 = 0 e_2=0 e 2 = 0 ) is carried by a set of size N N N with X X X -part ( 0 , 0 ) (0,0) ( 0 , 0 ) , which costs at most n − N n-N n − N if it is aligned (such a set misses x 1 x_1 x 1 , x 2 x_2 x 2 and s s s , so N ≤ n − 3 N \le n-3 N ≤ n − 3 ) and at most 2 otherwise, or by a set of size N − 1 N-1 N − 1 with X X X -part ( 1 , 0 ) (1,0) ( 1 , 0 ) (cost 1). A value N + 1 2 N+\frac{1}{2} N + 2 1 is carried by a set of size N N N with X X X -part ( 1 , 1 ) (1,1) ( 1 , 1 ) , which costs at most N N N if it is aligned (such a set contains x 1 x_1 x 1 , x 2 x_2 x 2 and s s s , so N ≥ 3 N \ge3 N ≥ 3 ) and at most 2 otherwise, or by a set of size N + 1 N+1 N + 1 with X X X -part ( 0 , 1 ) (0,1) ( 0 , 1 ) (cost 1). The values above 2 and below n + 1 2 n+\frac{1}{2} n + 2 1 are the integers 3 , … , n 3,\ldots,n 3 , … , n and N + 1 2 N+\frac{1}{2} N + 2 1 for 2 ≤ N ≤ n − 1 2 \le N \le n-1 2 ≤ N ≤ n − 1 . So the total cost is at most 1 (the start), plus n − N n-N n − N for 3 ≤ N ≤ n − 3 3 \le N \le n-3 3 ≤ N ≤ n − 3 , 2 for N = n − 2 N=n-2 N = n − 2 and 1 for each of N = n − 1 , n N=n-1,n N = n − 1 , n (a set with X X X -part ( 0 , 0 ) (0,0) ( 0 , 0 ) has at most n − 2 n-2 n − 2 states), plus 2 for the value 5 2 \frac{5}{2} 2 5 and N N N for N + 1 2 N+\frac{1}{2} N + 2 1 , 3 ≤ N ≤ n − 1 3 \le N \le n-1 3 ≤ N ≤ n − 1 :
rt ( A ) ≤ 1 + ( 4 + ∑ j = 3 n − 3 j ) + ( 2 + ∑ N = 3 n − 1 N ) = n 2 − 3 n + 4 ( n ≥ 6 ) ; \operatorname{rt}(\mathcal{A}) \le1+\left(4+\sum_{j=3}^{n-3}j\right)+\left(2+\sum_{N=3}^{n-1}N\right)=n^2-3n+4 \qquad(n\ge6); rt ( A ) ≤ 1 + ( 4 + j = 3 ∑ n − 3 j ) + ( 2 + N = 3 ∑ n − 1 N ) = n 2 − 3 n + 4 ( n ≥ 6 ) ;
the same count gives 8 for n = 4 n=4 n = 4 and 14 for n = 5 n=5 n = 5 , so rt ( A ) ≤ n 2 − 3 n + 4 \operatorname{rt}(\mathcal{A})\le n^2-3n+4 rt ( A ) ≤ n 2 − 3 n + 4 for every n ≥ 4 n\ge4 n ≥ 4 .
The class { 3 2 , 2 } \{\frac{3}{2},2\} { 2 3 , 2 } . Here α ( K ) = ∣ K ∣ + e 1 + 1 2 e 2 \alpha(K)=|K|+e_1+\frac{1}{2}e_2 α ( K ) = ∣ K ∣ + e 1 + 2 1 e 2 and α ( Q ) = n + 3 2 \alpha(Q)=n+\frac{3}{2} α ( Q ) = n + 2 3 . An integer value needs e 2 = 0 e_2=0 e 2 = 0 , so for a proper set it is at most ( n − 1 ) + 1 = n (n-1)+1=n ( n − 1 ) + 1 = n . An integer value N N N is carried by a set of size N N N with X X X -part ( 0 , 0 ) (0,0) ( 0 , 0 ) , which costs at most n − N n-N n − N if it is aligned (such a set misses x 1 x_1 x 1 , x 2 x_2 x 2 and s s s , so N ≤ n − 3 N \le n-3 N ≤ n − 3 ) and at most 2 otherwise, or by a set of size N − 1 N-1 N − 1 with X X X -part ( 1 , 0 ) (1,0) ( 1 , 0 ) (cost 1). A value N + 1 2 N+\frac{1}{2} N + 2 1 with 2 ≤ N ≤ n 2 \le N \le n 2 ≤ N ≤ n is carried by a set of size N N N with X X X -part ( 0 , 1 ) (0,1) ( 0 , 1 ) (cost 1), or, if N ≥ 3 N \ge3 N ≥ 3 , by a set of size N − 1 N-1 N − 1 with X X X -part ( 1 , 1 ) (1,1) ( 1 , 1 ) , which costs at most N − 1 N-1 N − 1 if it is aligned (such a set contains x 1 x_1 x 1 , x 2 x_2 x 2 and s s s , so N ≥ 4 N \ge4 N ≥ 4 ) and at most 2 otherwise. So the total cost is at most 1 (the start), plus 4 + ∑ j = 3 n − 3 j 4+\sum_{j=3}^{n-3}j 4 + ∑ j = 3 n − 3 j for the integer values, as in { 1 2 , 2 } \{\frac{1}{2},2\} { 2 1 , 2 } , plus 1 for the value 5 2 \frac{5}{2} 2 5 , 2 for 7 2 \frac{7}{2} 2 7 and N − 1 N-1 N − 1 for N + 1 2 N+\frac{1}{2} N + 2 1 , 4 ≤ N ≤ n 4 \le N \le n 4 ≤ N ≤ n :
rt ( A ) ≤ 1 + ( 4 + ∑ j = 3 n − 3 j ) + ( 1 + 2 + ∑ j = 3 n − 1 j ) = n 2 − 3 n + 5 ( n ≥ 6 ) ; \operatorname{rt}(\mathcal{A}) \le1+\left(4+\sum_{j=3}^{n-3}j\right)+\left(1+2+\sum_{j=3}^{n-1}j\right)=n^2-3n+5 \qquad(n\ge6); rt ( A ) ≤ 1 + ( 4 + j = 3 ∑ n − 3 j ) + ( 1 + 2 + j = 3 ∑ n − 1 j ) = n 2 − 3 n + 5 ( n ≥ 6 ) ;
the same count gives 9 for n = 4 n = 4 n = 4 and 15 for n = 5 n = 5 n = 5 , so rt ( A ) ≤ n 2 − 3 n + 5 \operatorname{rt}(\mathcal{A}) \le n^2 - 3n + 5 rt ( A ) ≤ n 2 − 3 n + 5 for every n ≥ 4 n \ge4 n ≥ 4 . In both classes the bound is at most ( n − 1 ) 2 (n - 1)^2 ( n − 1 ) 2 .
Proposition 5.14. Let A \mathcal{A} A be a binary, strongly connected, synchronizing automaton with n ≥ 4 n \ge4 n ≥ 4 states that has a witness of degree two in the class { 2 , 2 } \{2, 2\} { 2 , 2 } , { 2 , 3 } \{2, 3\} { 2 , 3 } or { 2 , 4 } \{2, 4\} { 2 , 4 } . Then rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le(n - 1)^2 rt ( A ) ≤ ( n − 1 ) 2 , and rt ( A ) ≤ n 2 − 3 n + 8 \operatorname{rt}(\mathcal{A}) \le n^2 - 3n + 8 rt ( A ) ≤ n 2 − 3 n + 8 if n ≥ 7 n \ge7 n ≥ 7 .
Proof. Here t 1 t_1 t 1 and t 2 t_2 t 2 are integers and min ( t 1 , t 2 ) = 2 \min(t_1,t_2)=2 min ( t 1 , t 2 ) = 2 , so α \alpha α takes integer values on sets. Let x ∗ x_* x ∗ be an exceptional state with t ∗ : = α x ∗ = max ( t 1 , t 2 ) t_* := \alpha_{x_*} = \max(t_1,t_2) t ∗ := α x ∗ = max ( t 1 , t 2 ) ; then α ( Q ) = n − 2 + t 1 + t 2 = n + t ∗ \alpha(Q) = n - 2 + t_1 + t_2 = n + t_* α ( Q ) = n − 2 + t 1 + t 2 = n + t ∗ .
Case n ≥ 7 n \ge7 n ≥ 7 . Start the process from K 0 = { x ∗ } K_0 = \{x_*\} K 0 = { x ∗ } , with α ( K 0 ) = t ∗ \alpha(K_0) = t_* α ( K 0 ) = t ∗ . The visited proper sets K 0 , … , K J − 1 K_0,\ldots,K_{J-1} K 0 , … , K J − 1 have strictly increasing integer values α ( K i ) \alpha(K_i) α ( K i ) in [ t ∗ , α ( Q ) − 1 ] = [ t ∗ , n + t ∗ − 1 ] [t_*,\alpha(Q)-1]=[t_*,n+t_*-1] [ t ∗ , α ( Q ) − 1 ] = [ t ∗ , n + t ∗ − 1 ] ; so they are distinct, and J ≤ n J \le n J ≤ n . Let μ 1 ≥ μ 2 ≥ ⋯ ≥ μ J \mu_1 \ge\mu_2 \ge\cdots\ge\mu_J μ 1 ≥ μ 2 ≥ ⋯ ≥ μ J be their costs m ( K i ) m(K_i) m ( K i ) in decreasing order. By Lemma 2.2 , μ i ≤ n − 1 \mu_i \le n - 1 μ i ≤ n − 1 ; by Lemma 2.4 , at most two of the sets cost n − 1 n - 1 n − 1 and at most six cost n − 2 n - 2 n − 2 or more, so μ 3 ≤ n − 2 \mu_3 \le n - 2 μ 3 ≤ n − 2 and μ 7 ≤ n − 3 \mu_7 \le n - 3 μ 7 ≤ n − 3 . Put κ 1 = κ 2 = n − 1 \kappa_1 = \kappa_2 = n - 1 κ 1 = κ 2 = n − 1 , κ 3 = ⋯ = κ 6 = n − 2 \kappa_3 = \cdots= \kappa_6 = n - 2 κ 3 = ⋯ = κ 6 = n − 2 and κ i = n − 3 \kappa_i = n - 3 κ i = n − 3 for 7 ≤ i ≤ n 7 \le i \le n 7 ≤ i ≤ n . Then μ i ≤ κ i \mu_i \le\kappa_i μ i ≤ κ i for i ≤ J i \le J i ≤ J , and every κ i ≥ 1 \kappa_i \ge1 κ i ≥ 1 ; as K 0 K_0 K 0 is a singleton,
rt ( A ) ≤ ∑ i = 1 J μ i ≤ ∑ i = 1 n κ i = 2 ( n − 1 ) + 4 ( n − 2 ) + ( n − 6 ) ( n − 3 ) = n 2 − 3 n + 8 ≤ ( n − 1 ) 2 , \operatorname{rt}(\mathcal{A}) \le\sum_{i=1}^{J}\mu_i \le\sum_{i=1}^{n}\kappa_i = 2(n - 1) + 4(n - 2) + (n - 6)(n - 3) = n^2 - 3n + 8 \le(n - 1)^2, rt ( A ) ≤ i = 1 ∑ J μ i ≤ i = 1 ∑ n κ i = 2 ( n − 1 ) + 4 ( n − 2 ) + ( n − 6 ) ( n − 3 ) = n 2 − 3 n + 8 ≤ ( n − 1 ) 2 ,
where the last inequality holds because n ≥ 7 n \ge7 n ≥ 7 .
Case 4 ≤ n ≤ 6 4 \le n \le6 4 ≤ n ≤ 6 . The automaton A \mathcal{A} A is binary and has at most six states, so rt ( A ) ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le(n - 1)^2 rt ( A ) ≤ ( n − 1 ) 2 by the computation of Kisielewicz, Kowalski and Szykuła [8 ] , who verified the Černý conjecture for all binary automata with at most 12 states.
For comparison, Berlinkov’s Corollary 1 in [1 ] gives 1 + ( n − 1 ) ( n + t 1 + t 2 − 4 ) 1 + (n - 1)(n + t_1 + t_2 - 4) 1 + ( n − 1 ) ( n + t 1 + t 2 − 4 ) in these three classes, that is, n 2 − n + 1 n^2 - n + 1 n 2 − n + 1 , n 2 n^2 n 2 and n 2 + n − 1 n^2 + n - 1 n 2 + n − 1 ; the level count alone, with every step costing at most n − 1 n - 1 n − 1 , gives n ( n − 1 ) n(n - 1) n ( n − 1 ) . The argument for n ≥ 7 n \ge7 n ≥ 7 in the proof above applies more generally.
Corollary 5.15. Let A \mathcal{A} A be a synchronizing automaton with n ≥ 7 n \ge7 n ≥ 7 states, over any alphabet. Suppose that, for some letter weights p p p , the matrix M = ∑ b p b M b M = \sum_b p_b M_b M = ∑ b p b M b has a stationary vector α \alpha α whose entries are positive integers with α ( Q ) − max q α q ≤ n \alpha(Q) - \max_q \alpha_q \le n α ( Q ) − max q α q ≤ n . Then rt ( A ) ≤ n 2 − 3 n + 8 ≤ ( n − 1 ) 2 \operatorname{rt}(\mathcal{A}) \le n^2 - 3n + 8 \le(n - 1)^2 rt ( A ) ≤ n 2 − 3 n + 8 ≤ ( n − 1 ) 2 . In particular, this holds for every synchronizing strongly connected automaton with n ≥ 7 n \ge7 n ≥ 7 states that has a witness of degree two in an integer class { 2 , k } \{2,k\} { 2 , k } , k k k a positive integer.
Proof. By Lemma 2.1 , A \mathcal{A} A is strongly connected. Let x ∗ x_* x ∗ be a state with α x ∗ = max q α q \alpha_{x_*} = \max_q \alpha_q α x ∗ = max q α q . The case n ≥ 7 n \ge7 n ≥ 7 of the proof of Proposition 5.14, with the extension process and the costs taken for this α \alpha α , uses only that A \mathcal{A} 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 [ α x ∗ , α ( Q ) − 1 ] [\alpha_{x_*},\alpha(Q)-1] [ α x ∗ , α ( Q ) − 1 ] , so again J ≤ α ( Q ) − α x ∗ ≤ n J \le\alpha(Q)-\alpha_{x_*} \le n J ≤ α ( Q ) − α x ∗ ≤ n , and the bound follows. For the last statement, the vector α \alpha α of Lemma 5.5 has the integer entries 1 1 1 , 2 2 2 and k k k , and α ( Q ) − max q α q = n + k − max ( 2 , k ) ≤ n \alpha(Q)-\max_q\alpha_q = n+k-\max(2,k) \le n α ( Q ) − max q α q = n + k − max ( 2 , k ) ≤ n .
Open cases
For three families of quasi-Eulerian automata it remains open whether every member satisfies the Černý bound: (a) binary strongly connected automata of degree two all of whose witnesses have one of the three configurations excluded in Theorem 5.9 ; (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 1 1 in its class or, for n ≥ 7 n \ge7 n ≥ 7 , a class { 2 , k } \{2,k\} { 2 , k } with k k k an integer (Proposition 5.6, Theorem 3.1, Corollary 5.15); (c) automata of degree d ≥ 3 d \ge3 d ≥ 3 .
In (a), only n ≥ 13 n \ge13 n ≥ 13 is open: the computation of [8 ] covers all binary automata with at most 12 states. For these three configurations, Lemma 5.10 still bounds the cost of the aligned sets; what is missing is a bound, sharper than the general n − 1 n - 1 n − 1 , for the cost of the sets whose pattern is neither aligned nor good. For strongly connected automata of degree d ≥ 3 d \ge3 d ≥ 3 , the bound 2 d ( n − d + 1 ) ( n − 1 ) 2^d(n-d+1)(n-1) 2 d ( n − d + 1 ) ( n − 1 ) of [2 ] is the best bound recorded in [16 item D3] for fixed d d d and large n n n ; for d d d close to n n n the general cubic bounds are smaller, since every automaton with n ≥ 2 n \ge2 n ≥ 2 states is quasi-Eulerian of degree n − 1 n-1 n − 1 (with E = { s } E=\{s\} E = { s } ).
Question 6.1. Does every synchronizing quasi-Eulerian automaton of degree two satisfy r t ≤ ( n − 1 ) 2 rt \le(n-1)^2 r t ≤ ( n − 1 ) 2 ? Does every synchronizing automaton with a positive stationary vector, for some letter weights, that takes only two values satisfy it?
Theorem 3.1 answers the second question when one of the two values is taken at a single state.
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.
References