betaFeedback

WorksComputer Science

Quadratic reset bounds for finite maximal prefix codes

Abstract

Let CC be a finite maximal prefix code of maximum codeword length k≥2k\ge2. We prove that, whenever the literal decoder of CC is synchronizing, it has a reset word of length at most (k−1)(4k−5)(k-1)(4k-5). The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth k−1k-1, is either identically zero or nonzero on a word of length at most 2k−32k-3. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are k−1k-1 and kk, we prove the sharper bound 2(k−1)2−12(k-1)^2-1 and characterize equality. The binary code with the single short word ak−1a^{k-1} attains this bound for every k≥2k\ge2; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

Introduction

A prefix code can be decoded as soon as a complete codeword has been read. If the starting position is unknown, however, different parsings may persist. A reset word removes this uncertainty: after reading it, every possible state of the decoder is the same. For the code {a,ba,bb}\{a, ba, bb\}, the letter aa is a reset word. The decoder is either at the root or has just read bb, and in both cases aa completes a codeword. For the code {aa,ab,ba,bb}\{aa, ab, ba, bb\}, no word resets the decoder, since the two possible depth parities remain different.

We ask how long a shortest reset word can be when all codewords have length at most kk. This parameter measures the depth of the prefix tree. It can be much smaller than the number of states: a full tree on dd letters can have 1+d+⋯+dk−11+d+\cdots+d^{k-1} internal vertices. Thus even a polynomial bound in the number of states need not give a polynomial bound in kk.

Throughout, Σ\Sigma is a finite alphabet with at least two letters, and C⊆Σ+C \subseteq\Sigma^+ is a finite nonempty maximal prefix code. Its literal decoder has as states the proper prefixes of the codewords, including ε\varepsilon. A transition extends the current prefix by one letter, except that completing a codeword returns the decoder to ε\varepsilon. Maximality makes every transition defined. Write

k=max⁡c∈C∣c∣,s(C)=min⁡{∣w∣:w resets the literal decoder of C},k=\max_{c\in C}|c|,\qquad s(C)=\min\{|w|:w\text{ resets the literal decoder of }C\},

where the second quantity is used only when a reset word exists.

Theorem 1.1. If k≥2k \ge2 and the literal decoder of CC is synchronizing, then

s(C)≤(k−1)(4k−5).(1)s(C)\le(k-1)(4k-5). \tag*{(1)}

A reset word satisfying this bound can be constructed in time polynomial in the explicitly listed code and alphabet.

The next result treats all full prefix trees with leaves at two consecutive depths. For r≥1r \ge1 and ∅≠A⊊Σr\varnothing\ne A \subsetneq\Sigma^r, set

C(A)=A∪(Σr+1∖AΣ).(2)C(A)=A\cup(\Sigma^{r+1}\setminus A\Sigma). \tag*{(2)}

Thus each word at depth rr is either a leaf in AA or has all its children as leaves at depth r+1r+1.

Theorem 1.2. The code C(A)C(A) is maximal, has height r+1r+1, and is synchronizing. Moreover,

s(C(A))≤2r2−1,(3)s(C(A))\le2r^2-1, \tag*{(3)}

with equality if and only if A=TrA=T^r for some nonempty proper subalphabet T⊊ΣT\subsetneq\Sigma. A reset word satisfying (1.3) can be constructed in polynomial time in the explicit input size.

The equality cases reduce, by identifying letters, to the following binary family.

Theorem 1.3. For every k≥2k\ge2, the binary code

Ck={ak−1}∪({a,b}k∖ak−1{a,b})C_k=\{a^{k-1}\}\cup(\{a,b\}^k\setminus a^{k-1}\{a,b\})

has reset threshold s(Ck)=2(k−1)2−1s(C_k)=2(k-1)^2-1. The word

ak−1(bk−1ak−1)k−2a^{k-1}(b^{k-1}a^{k-1})^{k-2}

is a shortest reset word. Inverse images under surjective letter maps give the same threshold over every finite alphabet with at least two letters.

Let sd(k)s_d(k) denote the largest reset threshold among synchronizing finite maximal prefix codes of height kk on a fixed dd-letter alphabet. There are only finitely many such codes, and Theorem 1.3 ensures that the class is nonempty.

Corollary 1.4. For every d≥2d\ge2 and k≥2k\ge2,

2(k−1)2−1≤sd(k)≤(k−1)(4k−5).2(k-1)^2-1\le s_d(k)\le(k-1)(4k-5).

In particular, sd(k)=Θ(k2)s_d(k)=\Theta(k^2).

Earlier work. Synchronization of prefix codes is part of the classical theory of codes; Schützenberger’s work [8] studies synchronizing properties of a particular family of prefix codes. The shortest-reset-word problem for finite automata goes back to Černý [4]. Pin [6] develops the approach of bounding the length needed to reduce the image of a subset. The complementary approach enlarges preimages. Rystsov [7] uses this construction with linear algebra and averaging for regular automata; Steinberg [9] gives a general averaging lemma. Our universal bound combines preimage expansion with a word-length estimate specific to prefix trees.

Carpi and D’Alessandro [3] explicitly study synchronization in terms of maximum word length. They relate bounds for synchronizing pairs of complete finite codes to bounds for incompletable words of finite languages. Their result is a conditional route to a quadratic bound in this parameter.

State bounds for prefix-code decoders also follow from results on one-cluster automata: automata in which repeated use of one letter leads every state to the same cycle. Béal, Berlinkov, and Perrin [1] prove a quadratic state bound for this class and apply it to finite prefix codes. Berlinkov, Ferens, Ryzhikov, and Szykuła [2] obtain an O(Nlog⁡3N)O(\sqrt{N}\log^3 N) reset bound for literal automata of finite prefix codes, where NN is the number of states. Theorem 1.1 gives a bound directly in the height of a complete literal decoder.

The distinction between the automata matters. Here a reset word must merge every proper-prefix state, without minimizing the decoder. The related theorem on uncompletable words and matrix mortality [5] concerns incomplete codes. A finite maximal prefix code has no uncompletable word: every input can be extended on the right to a concatenation of codewords. Its reset problem therefore requires a different argument.

The proofs. For the general bound, repeated use of one letter first sends the decoder into a cycle of at most kk states. We then construct a reset word backwards, enlarging the preimage of a chosen state. Cyclic averaging supplies an enlargement as soon as some short word changes a preimage’s cardinality. § 3 carries out this construction using the short-detection theorem proved in § 4. The latter replaces a bound depending on the dimension of a state space by one depending only on tree depth.

For consecutive depths, the next codeword boundary is a nondecreasing function of the current boundary. § 5 uses this order to advance the least remaining offset between two parsings. A closure property of the short codewords describes the only obstruction to the simplest advance. § 6 proves the exact binary lower bound by assigning a potential to sets of possible ages. § 7 gives the algorithms. Appendix § 9 contains the arc calculations, and Appendix § 10 describes the formal verification.

The literal decoder

Words act on states on the right. Thus q⋅uv=(q⋅u)⋅vq \cdot uv = (q \cdot u) \cdot v. For a set SS of states, write S⋅w={q⋅w:q∈S}S \cdot w = \{q \cdot w : q \in S\}. A word ww is a reset word if ∣Q⋅w∣=1|Q \cdot w| = 1.

Let

Q={q∈Σ∗:q is a proper prefix of a word of C}.Q = \{q \in\Sigma^* : q\text{ is a proper prefix of a word of }C\}.

The prefix tree of a finite nonempty prefix code is full if and only if the code is maximal. Indeed, a missing child of an internal vertex could be added as a codeword. Conversely, in a full finite tree, every word either meets a leaf or ends at a vertex having a leaf below it, so it is comparable with a codeword. Consequently, for q∈Qq \in Q and b∈Σb \in\Sigma, exactly one of qb∈Qqb \in Q and qb∈Cqb \in C holds, and

q⋅b={qb,qb∈Q,ε,qb∈C.(4)q \cdot b = \begin{cases} qb, & qb \in Q,\\ \varepsilon, & qb \in C. \end{cases} \tag*{(4)}

Figure 1 shows the passage from the tree to the decoder.

Prefix tree and literal decoder for the code {a, ba, bb}

Figure 1. The code {a,ba,bb}\{a, ba, bb\}. Rectangles are leaves. Each transition into a leaf becomes a return to ε\varepsilon; the letter aa sends both decoder states to ε\varepsilon.

Lemma 2.1. Every state has depth at most k−1k-1. Starting from a state qq, every input of length k−∣q∣k-|q| completes a codeword. If at least one completion occurs while reading ww, the final state is the suffix of ww after the last completion and has length at most ∣w∣−1|w|-1.

Proof. A path of length k−∣q∣k-|q| from qq that avoids all leaves would end at an internal vertex of depth kk, which is impossible. At the last completion the decoder returns to ε\varepsilon. Every subsequent letter extends the current prefix, since otherwise a later completion would occur. Those letters are therefore exactly the final state.

Lemma 2.2. If ∣u∣=k−1|u|=k-1, every state in Q⋅uQ \cdot u is a suffix of uu, and ∣Q⋅u∣≤k|Q \cdot u| \le k. If uu begins with a codeword, then ∣Q⋅u∣≤k−1|Q \cdot u| \le k-1.

Proof. Every nonroot initial state completes a codeword during uu, by Lemma 2.1. The root either does the same or ends at the state uu. Thus all outputs are suffixes of uu, one for each possible length in {0,…,k−1}\{0,\ldots,k-1\}. If uu begins with a codeword, every initial state completes at least once, so all output lengths are at most k−2k-2.

Reading from the root gives a unique factorization of any input into complete codewords followed by a proper prefix. This follows directly from (4): the returns to ε\varepsilon mark the codeword boundaries. In particular, extending the final prefix to a leaf extends the input to a word of C∗C^\ast.

If all leaves have depth kk, fullness gives C=ΣkC=\Sigma^k. Every letter then increases depth by one modulo kk, so states of different depths cannot merge. For k≥2k\geq2, a synchronizing code must therefore contain a shorter leaf. At height one, C=ΣC=\Sigma and the decoder has only the state ε\varepsilon; its reset threshold is zero.

A cycle reached by one repeated letter

Fix a∈Σa\in\Sigma. Following the aa-path from the root meets a unique leaf ara^r, where 1≤r≤k1\leq r\leq k. The states

Z={ε,a,…,ar−1}Z=\{\varepsilon,a,\ldots,a^{r-1}\}

form a cycle under aa. Identify ZZ with Z/rZ\mathbb{Z}/r\mathbb{Z}, and let ρ\rho be the rotation i↦i+1i\mapsto i+1. Set h0=k−1h_0=k-1 and define

π(q)=q⋅ah0,Tw(z)=z⋅wah0(z∈Z).(5)\pi(q)=q\cdot a^{h_0},\qquad T_w(z)=z\cdot wa^{h_0}\quad(z\in Z). \tag*{(5)}

The map π\pi takes QQ into ZZ. The root already lies on the cycle, and every other state completes a codeword within h0h_0 letters, after which all remaining letters are aa's.

For later use, record the composition rules

Tuah0v=Tv∘Tu,Twaj=ρj∘Tw,Tε=ρh0.(6)T_{ua^{h_0}v}=T_v\circ T_u,\qquad T_{wa^j}=\rho^j\circ T_w,\qquad T_\varepsilon=\rho^{h_0}. \tag*{(6)}

The first follows by writing the input as uah0vah0ua^{h_0}va^{h_0}. For the second, interchange the adjacent powers aja^j and ah0a^{h_0} and use the action of aa on ZZ. In particular, TεT_\varepsilon is a permutation.

A universal bound from preimage expansion

We first explain how the decoder's height enters the reset construction. The only algebraic input is the following theorem, whose proof occupies § 4.

Theorem 3.1 (Short detection). Let KK be a field and k≥2k\geq2. Suppose λ,ν:Q→K\lambda,\nu:Q\to K, with ν\nu constant on the states of depth k−1k-1. Put

f(w)=∑q∈Qλ(q)ν(q⋅w).f(w)=\sum_{q\in Q}\lambda(q)\nu(q\cdot w).

If ff is not identically zero, then f(w)≠0f(w)\ne0 for some ∣w∣≤2k−3|w|\leq2k-3.

To use this statement, take the cycle ZZ and the maps TwT_w from (5). We need to enlarge the preimage of any proper nonempty subset SS of ZZ. It is enough first to find a word ww for which ∣Tw−1(S)∣≠∣S∣|T_w^{-1}(S)|\ne|S|. Call such a word unbalancing for SS.

Lemma 3.2. Assume that the decoder is synchronizing and r≥2r\geq2. For every ∅≠S⊊Z\varnothing\ne S\subsetneq Z, there is a word ww of length at most 2k−32k-3 such that

∣Tw−1(S)∣≠∣S∣.|T_w^{-1}(S)|\ne|S|.

Proof. Work over Q\mathbb{Q} and set

λ(q)=1Z(q),ν(q)=r1S(π(q))−∣S∣.\lambda(q)=1_Z(q),\qquad\nu(q)=r1_S(\pi(q))-|S|.

A state of depth k−1k-1 returns to ε\varepsilon on its next letter. Thus every such state has the same image ε⋅ak−2\varepsilon\cdot a^{k-2} under π\pi, and ν\nu satisfies the hypothesis of Theorem 3.1. Its observation is

f(w)=r(∣Tw−1(S)∣−∣S∣).f(w)=r\left(|T_w^{-1}(S)|-|S|\right).

If zz resets the decoder, TzT_z is constant. Its preimage of SS has size either 00 or rr, so f(z)≠0f(z)\ne0. Short detection gives the required ww.

Lemma 3.3 (Cyclic averaging). For any map T:Z→ZT:Z\to Z and subset S⊆ZS\subseteq Z,

∑j=0r−1∣T−1(ρ−jS)∣=r∣S∣.(7)\sum_{j=0}^{r-1}\left|T^{-1}(\rho^{-j}S)\right|=r|S|. \tag*{(7)}

If ∣T−1(S)∣≠∣S∣|T^{-1}(S)|\ne|S|, some 0≤j<r0\le j<r satisfies ∣(ρj∘T)−1(S)∣>∣S∣|(\rho^j\circ T)^{-1}(S)|>|S|.

Proof. Each point T(z)T(z) belongs to exactly ∣S∣|S| of the rr rotations of SS. Counting over z∈Zz\in Z proves (7). The summands have average ∣S∣|S|. If one differs from that average, one must exceed it.

This is the averaging principle in the form needed here [9]. In view of (6), the rotation is realized by appending at most r−1r-1 letters aa. The first step can avoid this cost: a map that changes a singleton’s preimage size is not a permutation, and hence has some fiber of size at least two.

Proposition 3.4. Suppose that r≥2r\ge2 and every proper nonempty S⊂ZS\subset Z is unbalanced by some word of length at most LL. Then the decoder has a reset word of length at most

(k−1)+(r−1)(L+k+r−3).(8)(k-1)+(r-1)(L+k+r-3). \tag*{(8)}

Proof. Choose an unbalancing word w0w_0 for a singleton. Since Tw0T_{w_0} is not a permutation, choose z0z_0 with at least two preimages, and put

S0={z0},u0=w0,S1=Tu0−1(S0).S_0=\{z_0\},\qquad u_0=w_0,\qquad S_1=T_{u_0}^{-1}(S_0).

While Si≠ZS_i\ne Z, choose ∣wi∣≤L|w_i|\le L unbalancing SiS_i. Lemma 3.3 gives 0≤ji<r0\le j_i<r such that, with ui=wiajiu_i=w_i a^{j_i},

Si+1=Tui−1(Si),∣Si+1∣>∣Si∣.S_{i+1}=T_{u_i}^{-1}(S_i),\qquad|S_{i+1}|>|S_i|.

These sets need not be nested; only their cardinalities increase. After m≤r−1m\le r-1 steps, Sm=ZS_m=Z.

The word

W=ak−1um−1ak−1um−2⋯ak−1u0ak−1(9)W=a^{k-1}u_{m-1}a^{k-1}u_{m-2}\cdots a^{k-1}u_0a^{k-1} \tag*{(9)}

resets the decoder. Its initial power of aa sends QQ into ZZ. The rest acts there as Tu0∘⋯∘Tum−1T_{u_0}\circ\cdots\circ T_{u_{m-1}}, which sends SmS_m into S0S_0. Notice that the maps are applied in the reverse order to their construction.

There are m+1m+1 copies of ak−1a^{k-1}. Also ∣u0∣≤L|u_0|\le L and ∣ui∣≤L+r−1|u_i|\le L+r-1 for i≥1i\ge1. Hence

∣W∣≤(m+1)(k−1)+mL+(m−1)(r−1)≤k−r+(r−1)(L+k+r−2)=(k−1)+(r−1)(L+k+r−3).\begin{aligned} |W|&\le(m+1)(k-1)+mL+(m-1)(r-1)\\ &\le k-r+(r-1)(L+k+r-2)\\ &=(k-1)+(r-1)(L+k+r-3). \end{aligned}
Construction of the reset word

Figure 2. The reset word reads from left to right. Its construction runs backwards: each Si+1S_{i+1} is the full preimage of SiS_i under TuiT_{u_i}, and has larger cardinality.

Proof of Theorem 1.1. If r=1r=1, ak−1a^{k-1} already resets QQ. Otherwise Lemma 3.2 permits L=2k−3L=2k-3 in Proposition 3.4, giving

s(C)≤(k−1)+(r−1)(3k+r−6).s(C) \le(k-1)+(r-1)(3k+r-6).

For 2≤r≤k2\le r\le k, the product on the right increases with rr: both factors are nonnegative and increasing. Substituting r=kr=k gives (1). The algorithmic assertion is proved in Section 7. □

Corollary 3.5. If the decoder is synchronizing, k≥3k\ge3, and some pure-letter codeword ara^r satisfies 2r≤k+12r\le k+1, then s(C)≤2(k−1)2−1s(C)\le2(k-1)^2-1.

Proof. The case r=1r=1 is immediate. Otherwise put t=k−1t=k-1 and u=r−1≤t/2u=r-1\le t/2. The preceding estimate gives

s(C)≤t+u(3t+u−2)≤74t2≤2t2−1,s(C)\le t+u(3t+u-2)\le\frac{7}{4}t^2\le2t^2-1,

where the last inequality uses t≥2t\ge2. □

Short detection from the height of the tree

We now prove Theorem 3.1. A first-return decomposition expresses every decoder observation using four word polynomials of degrees controlled by kk. The difficulty is that these polynomials do not commute. We retain word order by embedding the free algebra in a division ring, where a finite linear system supplies a common right denominator. One further cancellation saves a degree and gives 2k−32k-3.

Keeping the order of letters

Write K⟨Σ⟩K\langle\Sigma\rangle for the free associative algebra on Σ\Sigma. Its elements are finite KK-linear combinations of words, and multiplication is concatenation. Its completion K⟨⟨Σ⟩⟩K\langle\langle\Sigma\rangle\rangle consists of all formal word series. Products are well-defined because a word has only finitely many factorizations into two words.

Lemma 4.1. There is a division ring D\mathcal{D}, with KK central, and an injective KK-algebra homomorphism ι:K⟨Σ⟩→D\iota:K\langle\Sigma\rangle\to\mathcal{D}. If RnR_n is the homogeneous component of degree nn of a word series RR, then

R⟼R^(t)=∑n≥0ι(Rn)tnR\longmapsto\widehat{R}(t)=\sum_{n\ge0}\iota(R_n)t^n

is an injective multiplicative map into D[[t]]\mathcal{D}[[t]], where tt is central. Its order is the least length of a word with nonzero coefficient in RR.

Proof. Let E=K(xb,i:b∈Σ, i∈Z)E=K(x_{b,i}:b\in\Sigma,\ i\in\mathbb{Z}) be a rational function field in commuting algebraically independent variables. The assignment τ(xb,i)=xb,i+1\tau(x_{b,i})=x_{b,i+1} defines an automorphism of EE fixing KK. Form the skew Laurent-series ring

D=E((z;τ)),zf=τ(f)z(f∈E).\mathcal{D}=E((z;\tau)),\qquad zf=\tau(f)z\quad(f\in E).

Its series have exponents bounded below. Each coefficient of a product is therefore a finite sum. Every nonzero series has an invertible lowest term fNzNf_N z^N. Factoring out that term leaves 1+h1+h with hh of positive order, whose inverse is the well-defined series ∑j≥0(−h)j\sum_{j\geq0}(-h)^j. Thus D\mathcal{D} is a division ring, and KK is central in it.

Send bb to xb,0zx_{b,0}z. Then

ι(b1⋯bn)=xb1,0xb2,1⋯xbn,n−1zn\iota(b_1\cdots b_n)=x_{b_1,0}x_{b_2,1}\cdots x_{b_n,n-1}z^n

Distinct words of the same length give distinct monomials in the position-indexed variables. These monomials are linearly independent over KK; different lengths have different powers of zz. This proves injectivity. The additional variable tt records homogeneous degree. Multiplicativity follows by homogeneous convolution, and injectivity and the order assertion follow degree by degree.

Lemma 4.2 (Common right denominator). Let D,M∈D[t]D,M\in\mathcal{D}[t], with D≠0D\ne0, deg⁡D≤p\deg D\leq p, and deg⁡M≤m\deg M\leq m. There are polynomials U,VU,V such that

DU=MV,V≠0,deg⁡U≤m,deg⁡V≤p.(10)DU=MV,\qquad V\ne0,\qquad\deg U\leq m,\qquad\deg V\leq p. \tag*{(10)}

Proof. Write U=∑i=0muitiU=\sum_{i=0}^{m}u_i t^i and V=∑j=0pvjtjV=\sum_{j=0}^{p}v_j t^j. Equating coefficients in DU−MV=0DU-MV=0 gives at most m+p+1m+p+1 homogeneous equations in m+p+2m+p+2 unknowns. This is a linear system over the right vector space Dm+p+2\mathcal{D}^{m+p+2}: all fixed coefficients multiply the unknowns on the left. It has a nonzero solution. If V=0V=0, then DU=0DU=0, forcing U=0U=0, since the product of the leading coefficients of two nonzero polynomials is nonzero. Hence V≠0V\ne0.

The side of multiplication in (10) is essential. It gives D−1MV=UD^{-1}MV=U with precisely the order needed below.

The first completion

For each q∈Qq\in Q, define

Pq=∑s: qs∈Cs,Mq=∑s: qs∈Qν(qs)s,Fq=∑w∈Σ∗ν(q⋅w)w.P_q=\sum_{s: \, qs\in C}s,\qquad M_q=\sum_{s: \, qs\in Q}\nu(qs)s,\qquad\mathcal{F}_q=\sum_{w\in\Sigma^*}\nu(q\cdot w)w.

The empty suffix contributes ν(q)\nu(q) to MqM_q. A word read from qq either completes no codeword or has a unique first completion. In the first case it contributes to MqM_q. In the second it consists of a suffix counted by PqP_q, followed by an input read from the root. Hence

Fq=Mq+PqFε.(11)\mathcal{F}_q=M_q+P_q\mathcal{F}_\varepsilon. \tag*{(11)}

Set P=PεP=P_\varepsilon, M=MεM=M_\varepsilon, and D=1−PD=1-P. Since PP has no constant term, D−1=∑j≥0PjD^{-1}=\sum_{j\geq0}P^j exists as a formal word series. Taking q=εq=\varepsilon in (11) gives Fε=D−1M\mathcal{F}_\varepsilon=D^{-1}M. Thus the observation series is

F:=∑wf(w)w=A+BD−1M,(12)F:=\sum_w f(w)w=A+BD^{-1}M, \tag*{(12)}

where

A=∑q≠ελ(q)Mq,B=λ(ε)+∑q≠ελ(q)Pq.A=\sum_{q\ne\varepsilon}\lambda(q)M_q,\qquad B=\lambda(\varepsilon)+\sum_{q\ne\varepsilon}\lambda(q)P_q.

The tree gives the degree bounds

deg⁡D≤k,deg⁡M≤k−1,deg⁡A≤k−2,deg⁡B≤k−1.(13)\deg D\leq k,\qquad\deg M\leq k-1,\qquad\deg A\leq k-2,\qquad\deg B\leq k-1. \tag*{(13)}

For example, a suffix in MqM_q has length at most k−1−∣q∣k-1-|q|, and AA uses only nonroot states. A suffix in PqP_q has length at most k−∣q∣k-|q|.

Cancellation of the highest coefficient

Proof of Theorem 3.1. Use Lemma 4.1 to encode the polynomials and series by a central variable tt, retaining their names. Lemma 4.2 gives

DU=MV,V≠0,deg⁡U≤k−1,deg⁡V≤k.DU = MV,\qquad V \ne0,\qquad\deg U \le k-1,\qquad\deg V \le k.

The constant coefficient of DD is 1, so it is invertible in D[[t]]\mathcal{D}[[t]]. Multiplying (12) on the right by VV gives

FV=AV+BU=:N.(14)FV = AV + BU =: N. \tag*{(14)}

By (13), deg⁡N≤2k−2\deg N \le2k-2. We show that its coefficient of degree 2k−22k-2 vanishes. Let ω\omega be the common value of ν\nu at depth k−1k-1. Before encoding, put

σ=∑b∈Σb,J=∑q∈Q∣q∣=k−1q,H=∑q∈Q∣q∣=1λ(q)∑s∈Qqs∈Q∣s∣=k−2s.\sigma= \sum_{b \in\Sigma} b,\qquad J = \sum_{\substack{q \in Q\\ |q|=k-1}} q,\qquad H = \sum_{\substack{q \in Q\\ |q|=1}} \lambda(q)\sum_{\substack{s \in Q\\ qs \in Q\\ |s|=k-2}} s.

There is a leaf at depth kk, so J≠0J \ne0. Every child of a state counted by JJ is a leaf. Consequently the highest homogeneous components satisfy

Dk=−Jσ,Mk−1=ωJ,Ak−2=ωH,Bk−1=Hσ.(15)D_k = -J\sigma,\qquad M_{k-1} = \omega J,\qquad A_{k-2} = \omega H,\qquad B_{k-1} = H\sigma. \tag*{(15)}

The last two equalities use the same paths: a nonroot initial state can contribute at those degrees only if it has depth one. The relevant path ends at a deepest internal vertex for AA, and takes one additional letter for BB. This also covers k=2k=2, when the path contributing to HH is empty.

Now read (15) as equalities in D\mathcal{D}. The coefficient of degree 2k−12k-1 in DU=MVDU=MV is

−JσUk−1=ωJVk.-J\sigma U_{k-1} = \omega J V_k.

Since ω\omega is central, cancelling JJ on the left yields

σUk−1+ωVk=0.\sigma U_{k-1} + \omega V_k = 0.

Therefore the coefficient of degree 2k−22k-2 in NN is

ωHVk+HσUk−1=H(ωVk+σUk−1)=0.\omega H V_k + H\sigma U_{k-1} = H(\omega V_k + \sigma U_{k-1}) = 0.

We have proved deg⁡N≤2k−3\deg N \le2k-3.

If F≠0F \ne0, then N=FV≠0N=FV \ne0. Orders of nonzero power series over a division ring add, because the product of their first nonzero coefficients is nonzero. Hence

ord⁡tF+ord⁡tV=ord⁡tN≤deg⁡N≤2k−3.\operatorname{ord}_t F + \operatorname{ord}_t V = \operatorname{ord}_t N \le\deg N \le2k-3.

As ord⁡tV≥0\operatorname{ord}_t V \ge0, the first nonzero homogeneous part of FF has degree at most 2k−32k-3. Injectivity of the encoding gives an actual word of that length with f(w)≠0f(w) \ne0.

The terminal-depth condition is used exactly in (15). It makes both highest terminal coefficients scalar multiples of the corresponding path sums, allowing the cancellation. The conclusion concerns a linear observation; the extra compression and rotation costs in § 3 are needed to turn it into a reset word.

Codes with two consecutive lengths

Fix r≥1r \ge1 and ∅≠A⊊Σ\varnothing\ne A \subsetneq\Sigma. The tree of C(A)C(A) in (2) is full: every word of length rr either belongs to AA or has all its children as leaves. Nonemptiness and properness ensure that both lengths rr and r+1r+1 occur.

The direct construction in this section uses a property special to these two lengths. Along a fixed input, later codeword boundaries cannot have earlier next boundaries. We first describe this order and then show how to advance all surviving offsets between two parsings.

Order of parsing boundaries

Consider an infinite input x0x1⋯x_0x_1\cdots. At a possible boundary jj, set

ej=1A(xj⋯xj+r−1).e_j = 1_A(x_j\cdots x_{j+r-1}).

The codeword starting there has length r+1−ejr+1-e_j, so its next boundary is

F(j)=j+r+1−ej.(16)F(j) = j+r+1-e_j. \tag*{(16)}

Since

F(j+1)−F(j)=1+ej−ej+1∈{0,1,2},F(j+1)-F(j)=1+e_j-e_{j+1}\in\{0,1,2\},

the map FF and all its iterates are nondecreasing. Let p0,p1,…p_0,p_1,\ldots be the boundaries of a reference parsing, so pi+1=F(pi)p_{i+1}=F(p_i). If pi<q<pi+1p_i<q<p_{i+1} is an alternative boundary, then

pi+1≤F(q)≤pi+2.p_{i+1}\le F(q)\le p_{i+2}.

Equality at either endpoint means that the two parsings meet and agree thereafter. Otherwise the alternative boundary remains inside the next reference word. If its offset is j=q−pij=q-p_i, the current reference word has length ℓ\ell, and the alternative word has length λj\lambda_j, the next offset is

j′=j+λj−ℓ.(17)j'=j+\lambda_j-\ell. \tag*{(17)}

In particular, when the reference word is short, the offset stays fixed or increases by one.

Diagram showing an alternative boundary between consecutive reference boundaries

Figure 3. For lengths rr and r+1r+1, monotonicity keeps an alternative boundary between the next two reference boundaries. A boundary reaching either endpoint has joined the reference parsing.

When every splice remains short

Use zero-based slices: u[x:r]u[x:r] is the suffix of a word u∈Σru\in\Sigma^r after position xx, and u[0:x]u[0:x] is its prefix of length xx. For 1≤x<r1\le x<r, call AA closed at x if

u[x:r]v[0:x]∈Afor all u,v∈A.(18)u[x:r]v[0:x]\in A \qquad\text{for all }u,v\in A. \tag*{(18)}

This is precisely the situation in which every length-rr window at offset xx across two short reference words is itself short.

Lemma 5.1. If AA is closed at xx and g=gcd⁡(x,r)g=\gcd(x,r), then

A=Dr/gA=D^{r/g}

for a nonempty proper subset D⊊ΣgD\subsetneq\Sigma^g. Conversely, such a product is closed at every offset divisible by gg.

Proof. Taking u=vu=v in (18) shows that rotation by xx maps AA into itself. Since AA is finite, it is invariant under this rotation and its inverse. The rotations generated by xx modulo rr are exactly the multiples of gg, so rotation by gg also preserves AA.

Rotating the splice in (18) back by xx gives

v[0:x]u[x:r]∈A.v[0:x]u[x:r] \in A.

Thus the first xx coordinates of one word can be copied independently into another word of AA. Say that a set of coordinates SS is replaceable if every word formed from one member of AA on SS and another on its complement still belongs to AA. Replaceable sets are closed under complement by interchanging the two words. They are closed under intersection as well: first copy uu into SS of vv, then copy the resulting word into TT of a fresh copy of vv. The final word uses uu exactly on S∩TS \cap T.

Partition the coordinates into m=r/gm=r/g consecutive blocks of length gg, and put ℓ=x/g\ell=x/g. The first ℓ\ell blocks are replaceable. Rotation invariance makes every cyclic interval of ℓ\ell blocks replaceable. These intervals separate distinct blocks: the incidence patterns of two distinct positions in all proper, nonempty cyclic intervals of a fixed length are different. One way to see this is that the indicator of a single proper cyclic interval has exactly one change from 0 to 1; it cannot be invariant under a nonzero rotation. Therefore the Boolean algebra generated by the intervals contains each individual block. Each block is replaceable.

Let DiD_i be the projection of AA onto block ii. Replacing one block at a time shows that all choices from the projections are independent, so A=D1×⋯×DmA=D_1 \times\cdots\times D_m. Rotation by gg permutes the blocks and preserves AA, forcing all DiD_i to be the same set DD. Since AA is nonempty and proper, so is DD. The converse follows because a splice at a multiple of gg joins whole blocks belonging to DD.

Advancing the least remaining offset

At the end of a round, the last reference word is a short word c∈Ac \in A. Any parsing that has not met the reference has its most recent boundary at an interior offset of cc. We append two codewords, the last of which is again short, and follow these boundaries through two applications of FF.

Lemma 5.2. Suppose the least surviving offset in c∈Ac \in A is xx, where 1≤x<r1 \le x < r. There are two codewords, the second short, whose concatenation has length at most 2r+12r+1 and leaves every surviving offset at least x+1x+1. If AA is not closed at xx, the length is at most 2r2r.

Proof. Suppose first that closure fails. Choose u,v∈Au,v \in A with u[x:r]v[0:x]∉Au[x:r]v[0:x] \notin A, and append uvuv. In moving from cc to uu, an offset xx either increases or stays fixed, by (17). If it increases, the next transition cannot decrease it, since uu is short. If it stays fixed, the window at offset xx across u,vu,v lies outside AA, so the alternative word has length r+1r+1 and its offset increases at the next transition. An endpoint is removed as soon as it meets the reference. Monotonicity of F2F^2 gives the same lower bound for all larger surviving offsets. The cost is 2r2r.

Now suppose closure holds. By Lemma 5.1, write

g=gcd⁡(x,r),m=r/g,ℓ=x/g,A=Dm.g=\gcd(x,r), \qquad m=r/g, \qquad\ell=x/g, \qquad A=D^m.

Choose p∈Dp \in D, q∈Σg∖Dq \in\Sigma^g \setminus D, and y∈Σy \in\Sigma. Form

L=qpℓ−1yqpm−ℓ−1.(19)L=q p^{\ell-1}y q p^{m-\ell-1}. \tag*{(19)}

Its length is r+1r+1, and its first length-gg block is q∉Dq \notin D, so its length-rr prefix is outside AA. Thus L∈C(A)L \in C(A). Append LL followed by any d∈Ad \in A. Place cc, LL, and dd on the half-open intervals [−r,0)[-r,0), [0,r+1)[0,r+1), and [r+1,2r+1)[r+1,2r+1), respectively. The boundary at −r+x-r+x sees the length-rr window

c[x:r]L[0:x]=c[x:r]qpℓ−1.c[x:r]L[0:x]=c[x:r]q p^{\ell-1}.

It contains the forbidden block qq at an aligned block position, and hence lies outside AA. The alternative word is long, ending at x+1x+1 inside LL. Its next window is

L[x+1:r+1]d[0:x]=qpm−ℓ−1d[0:x],L[x+1:r+1]d[0:x]=q p^{m-\ell-1}d[0:x],

which again contains an aligned forbidden block. The next alternative word is long too, and ends at r+x+2r+x+2, at offset x+1x+1 in dd. If x+1=rx+1=r, it meets the right endpoint of dd. Monotonicity of F2F^2 controls the larger offsets. The appended length is 2r+12r+1.

The long–short round

Figure 4. The long–short round. The two copies of q∉Dq \notin D force two long alternative codewords. Their boundaries advance from offset xx in cc to offset x+1x+1 in dd. Positions are schematic; the displayed coordinates give the exact lengths.

Proof of the upper bound in Theorem 1.2. If r=1r=1, any letter in AA resets the decoder, and the threshold is one because AA is proper and the decoder has a nonroot state.

Let r≥2r\ge2. Begin with any c∈Ac\in A. Every initial state completes a codeword during these rr letters, so Lemma 2.1 shows that every output is a suffix of cc of length at most r−1r-1. The root’s parsing ends at the root and serves as the reference. Every other output corresponds to a boundary at an interior offset in cc.

Apply Lemma 5.2 to the least surviving offset. Its conclusion raises that offset by at least one and leaves the last reference word short. Repeat until no offset remains. This takes at most r−1r-1 rounds, since the possible offsets are 1,…,r−11,\ldots,r-1. At each round end, an alternative parsing either has met the reference or has its last boundary in the last short word: its next word has length at least rr, so it cannot complete again strictly inside that word. Thus the same representation applies at every round. When all alternatives have met the reference, the input resets to ε\varepsilon.

The total length is at most

r+(r−1)(2r+1)=2r2−1.r+(r-1)(2r+1)=2r^2-1.

All windows used in the construction lie in the chosen words. An arbitrary infinite continuation used to define FF cannot affect them. Polynomial-time implementation is discussed in § 7.

Equality and changes of alphabet

Lemma 5.3. Let θ:Σ↠Γ\theta:\Sigma\twoheadrightarrow\Gamma be a surjective letter map, let C′⊆Γ+C'\subseteq\Gamma^+ be a finite maximal prefix code, and set C=θ−1(C′)C=\theta^{-1}(C'). Then CC is a finite maximal prefix code. A word ww resets its literal decoder if and only if θ(w)\theta(w) resets the decoder of C′C'. Consequently the thresholds agree whenever the decoders synchronize.

Proof. The state set is Q=θ−1(Q′)Q=\theta^{-1}(Q'), and the induced map Q→Q′Q\to Q' is onto and respects transitions. Prefix-freeness and fullness are preserved, so CC is a finite maximal prefix code. A reset word projects to a reset word.

Conversely, if θ(w)\theta(w) resets, all states in Q⋅wQ\cdot w have the same image, and thus the same length hh. If one initial state completes a codeword while reading ww, Lemma 2.1 gives h<∣w∣h<|w|. Any thread that completes none would end at length ∣q∣+∣w∣≥∣w∣|q|+|w|\ge|w|, a contradiction. Hence all threads complete, and all outputs are the same length-hh suffix of ww.

If no thread completes, all output lengths are ∣q∣+∣w∣|q|+|w|. They cannot be equal when QQ contains both the root and a nonroot state. The remaining case Q={ε}Q=\{\varepsilon\} is immediate. This proves the converse. Every word over Γ\Gamma has a lift of the same length, giving equality of thresholds.

Proof of the equality assertion in Theorem 1.2. Suppose r≥2r\ge2 and AA is not a subalphabet power. Then AA is not closed at r−1r-1: otherwise Lemma 5.1, with gcd⁡(r−1,r)=1\gcd(r-1,r)=1, would give A=TrA=T^r.

If the construction uses r−1r-1 rounds, their least offsets must be 1,2,…,r−11,2,\ldots,r-1. The last round costs at most 2r2r, saving one letter from the bound. If it uses fewer rounds, the saving is larger. Thus

s(C(A))≤2r2−2.s(C(A))\le2r^2-2.

Conversely, if A=TrA=T^r, send the letters of TT to aa and all remaining letters to bb. Then C(A)C(A) is the inverse image of Cr+1C_{r+1}. Lemma 5.3 and Theorem 1.3, proved in the next section, give s(C(A))=2r2−1s(C(A))=2r^2-1. For r=1r=1, every nonempty proper AA is itself a subalphabet, and the threshold is one.

An exact extremal family

Put n=k−1≥1n=k-1\ge1 and consider

Ck={an}∪({a,b}n+1∖an{a,b}).C_k=\{a^n\}\cup\left(\{a,b\}^{n+1}\setminus a^n\{a,b\}\right).

The states of its decoder are

Q={q∈{a,b}∗:∣q∣≤n}∖{an}.Q=\{q\in\{a,b\}^* : |q|\le n\}\setminus\{a^n\}.

Every word of length less than nn is an internal vertex; at depth nn, only ana^n is a leaf. Thus

q⋅x={ε,∣q∣=n or (q=an−1 and x=a),qx,otherwise.(20)q\cdot x= \begin{cases} \varepsilon, & |q|=n\text{ or }(q=a^{n-1}\text{ and }x=a),\\ qx, & \text{otherwise}. \end{cases} \tag*{(20)}

A reset word of length 2n2−12n^2-1

Lemma 6.1. The word W=an(bn+1an)n−1W=a^n(b^{n+1}a^n)^{n-1} resets QQ to ε\varepsilon.

Proof. Let Z={ε,a,…,an−1}Z=\{\varepsilon,a,\ldots,a^{n-1}\}. Reading ana^n fixes each state of ZZ. From a state containing bb, of length jj, the first n+1−jn+1-j letters complete a long codeword and the remaining j−1j-1 letters leave aj−1a^{j-1}. Hence Q⋅an=ZQ\cdot a^n=Z.

For 0≤i<n0\le i<n, reading bn+1b^{n+1} from aia^i completes a long word after n+1−in+1-i letters and leaves bib^i. Reading ana^n from bib^i then leaves ai−1a^{i-1} if i≥1i\ge1, and leaves ε\varepsilon if i=0i=0. The block V=bn+1anV=b^{n+1}a^n therefore acts on ZZ by

ai⋅V=amax⁡(i−1,0).a^i\cdot V=a^{\max(i-1,0)}.

After n−1n-1 copies, every state reaches ε\varepsilon. The length is n+(n−1)(2n+1)=2n2−1n+(n-1)(2n+1)=2n^2-1.

For the converse, a reset word may end at any state. We must bound all such words, not just those returning to ε\varepsilon. Once the states are suffixes of a common input, their lengths determine them. We use these lengths to follow every possible reset word.

Ages and the first short completion

Call the length of a suffix state its age. Ages lie in {0,…,n}\{0,\ldots,n\}. On this set define

σ(g)=g+1(modn+1),φ(g)={g+1,0≤g≤n−2,0,g=n−1 or g=n.\sigma(g)=g+1 \pmod{n+1},\qquad \varphi(g)= \begin{cases} g+1, & 0\le g\le n-2,\\ 0, & g=n-1\text{ or }g=n. \end{cases}

On the smaller circle {0,…,n−1}\{0,\ldots,n-1\}, let ρ(g)=g+1(modn)\rho(g)=g+1 \pmod n.

Suppose the current states are suffixes of a common word PP of length at least nn. Let c(P)c(P) be the trailing run of a’s, capped at nn. A letter bb acts on ages by σ\sigma and sets the counter to zero. A letter aa acts by σ\sigma if the prior counter is at most n−2n-2, and by φ\varphi if it is at least n−1n-1. In the latter case the counter becomes nn. Call such an aa a special letter.

These rules are exact. Age nn always returns to zero on the next letter. Age n−1n-1 returns to zero on aa exactly when its suffix is an−1a^{n-1}, which is equivalent to the common input having at least n−1n-1 trailing a’s. Every other transition increases age by one. In each case the new state is the suffix of the enlarged input of the new age. Distinct ages represent distinct states.

Two initial state sets fit this description:

Z={ε,a,…,an−1},Zb={ε,b,…,bn}.Z=\{\varepsilon,a,\ldots,a^{n-1}\},\qquad Z_b=\{\varepsilon,b,\ldots,b^n\}.

For ZZ, take the common context ana^n, all small-circle ages, and counter nn. For ZbZ_b, take the context bn+1b^{n+1}, all big-circle ages, and counter zero. These contexts represent the sets; they are not charged as part of a subsequent input.

Let d(Z)d(Z) be the minimum length needed to send ZZ to a singleton. It is finite by Lemma 6.1.

Lemma 6.2. The reset threshold satisfies s(Ck)=n+d(Z)s(C_k)=n+d(Z).

Proof. Since Q⋅an=ZQ\cdot a^n=Z, we have s(Ck)≤n+d(Z)s(C_k)\le n+d(Z). Conversely, let ww reset QQ. It also resets Zb⊆QZ_b\subseteq Q. Until the first special letter, the age action on ZbZ_b is a permutation of all n+1n+1 ages. A special letter must therefore occur.

Let tt be the number of letters consumed up to and including that first special letter. Because the initial counter is zero, the consumed prefix ends with ana^n, so t≥nt\ge n. Immediately after this letter, the age set is exactly {0,…,n−1}\{0,\ldots,n-1\} and the counter is nn. The actual states are the corresponding suffixes of ana^n, namely ZZ. The remaining suffix of ww must synchronize ZZ, and has length at least d(Z)d(Z). Thus ∣w∣≥t+d(Z)≥n+d(Z)|w|\ge t+d(Z)\ge n+d(Z). □\square

For n=1n=1, Z={ε}Z=\{\varepsilon\} and d(Z)=0d(Z)=0, so the threshold is one. Assume from now on that n≥2n\ge2.

Excursions away from the small circle

After a special letter the ages lie on the small circle and the counter equals nn. Further special letters are a’s, acting as ρ\rho. To leave such a run requires a bb. Before the next special letter there must be n−1n-1 ordinary a’s after the last bb. Thus the intervening block BB of nonspecial letters starts with bb, ends with ban−1ba^{n-1}, and has length j≥nj\ge n.

Suppose this block is followed by e≥1e\ge1 special letters. Put τ=j mod (n+1)\tau=j\bmod(n+1). Let ι\iota include the small circle in the big one, and let π\pi fix 0,…,n−10,\ldots,n-1 and send nn to n−1n-1. Since φ=ρ∘π\varphi=\rho\circ\pi, the whole excursion acts on small-circle ages as

ρe∘π∘σj∘ι.\rho^e\circ\pi\circ\sigma^j\circ\iota.

For 0≤m≤n−20\le m\le n-2, define

Xm(g)={g−m(modn),0≤g≤m,g−m−1(modn),m+1≤g≤n−1.(21)X_m(g)= \begin{cases} g-m \pmod n, & 0\le g\le m,\\ g-m-1 \pmod n, & m+1\le g\le n-1. \end{cases} \tag*{(21)}

The only nontrivial fiber of XmX_m is {m,m+1}\{m,m+1\}, which maps to zero. Its image omits hm=n−m−1h_m=n-m-1. Splitting gg according to whether g+τg+\tau crosses nn or n+1n+1 gives the following three possibilities:

Figure 5. The slip X1X_1 on five ages. The ages 1 and 2 merge at 0, and age 3 is omitted. The target circle is cut immediately after 3 and displayed in the order 4, 0, 1, 2, 3. This makes the increasing lift used in Appendix § 9 visible.

τ\tauExcursion mapNecessary length
0ρe\rho^{e}j+e≥n+1+ej+e \ge n+1+e
nnρe−1\rho^{e-1}j+e≥n+ej+e \ge n+e
1≤τ≤n−11 \le\tau\le n-1ρe−1∘Xn−1−τ\rho^{e-1}\circ X_{n-1-\tau}j+e≥n+1+τ+ej+e \ge n+1+\tau+e

Table 6.

For completeness, in the middle range put m=n−1−τm=n-1-\tau. If g<mg<m, the big-circle age g+τg+\tau is at most n−2n-2 and the first special letter sends it to g+τ+1=g−m+ng+\tau+1=g-m+n. If g=mg=m or m+1m+1, it sends it to zero. If g>m+1g>m+1, reduction modulo n+1n+1 occurs before applying φ\varphi, and the result is g−m−1g-m-1. These are exactly (21). The remaining e−1e-1 letters rotate. The cases τ=0,n\tau=0,n follow directly from φι=ρ\varphi\iota=\rho and φσnι=id⁡\varphi\sigma^{n}\iota=\operatorname{id}.

Assign cost 1 to ρ\rho and cost 2n+1−m2n+1-m to XmX_m. Each excursion can be replaced by these operations at no greater cost. The first two rows require only ee or e−1e-1 rotations. In the third row,

(2n+1−m)+(e−1)=n+1+τ+e≤j+e,m=n−1−τ.(22)(2n+1-m)+(e-1)=n+1+\tau+e\le j+e,\qquad m=n-1-\tau. \tag*{(22)}

Here j≥nj\ge n and 1≤τ<n1\le\tau<n imply j≥n+1+τj\ge n+1+\tau.

An initial run of special letters is already a sequence of rotations. A final unfinished block of nonspecial letters acts by a power of σ\sigma, so it cannot change cardinality and can be discarded when testing synchronization. Consequently, if Dslip(G)D_{\mathrm{slip}}(G) is the minimum total cost of rotations and slips sending GG to a singleton, then

d(Z)≥Dslip(Z/nZ).(23)d(Z)\ge D_{\mathrm{slip}(\mathbb{Z}/n\mathbb{Z}).} \tag*{(23)}

We only need this direction: allowing additional sequences of slips can lower the minimum, which is harmless for (23).

A potential on circular arcs

Cardinality alone does not give the sharp cost: slips at different positions have different prices. We also keep track of where a shortest covering arc starts.

For 1≤p≤n1\le p\le n and 1−p≤α≤n−p1-p\le\alpha\le n-p, let

I(α,p)={α,α+1,…,α+p−1}(modn),Ψ(α,p)=(p−1)(2n+1)−α.I(\alpha,p)=\{\alpha,\alpha+1,\ldots,\alpha+p-1\}\pmod n,\qquad\Psi(\alpha,p)=(p-1)(2n+1)-\alpha.

For p<np<n, this range selects a unique integer representative of the starting point of each arc. For p=np=n, all starts describe the full circle, and the least value occurs at α=0\alpha=0.

For a nonempty subset GG of the circle, put

Φ(G)={0,∣G∣=1,min⁡{Ψ(α,p):2≤p≤n, G⊆I(α,p), 1−p≤α≤n−p},∣G∣≥2.(24)\Phi(G)= \begin{cases} 0, & |G|=1,\\ \min\{\Psi(\alpha,p):2\le p\le n,\ G\subseteq I(\alpha,p),\ 1-p\le\alpha\le n-p\}, & |G|\ge2. \end{cases} \tag*{(24)}

In particular,

Φ(Z/nZ)=(n−1)(2n+1).(25)\Phi(\mathbb{Z}/n\mathbb{Z})=(n-1)(2n+1). \tag*{(25)}

Lemma 6.3. An arc of smaller size has smaller Ψ\Psi than every arc of larger size. For 2≤∣G∣<n2 \le|G| < n, the minimum in (24) selects a unique covering arc of minimum size. Its size is at most n−1n-1, and both its endpoints lie in GG.

Proof. At size pp, the maximum possible value is (p−1)(2n+2)(p-1)(2n+2). The minimum at size p+1p+1 is p(2n+1)−(n−p−1)p(2n+1)-(n-p-1), larger by n+3n+3. Iterating gives the first assertion. A proper subset is covered by an arc of size n−1n-1, obtained by omitting a point outside it. Among the minimum-size covers, different canonical starts give different potentials, so one is selected uniquely. If an endpoint were absent from GG, deleting it would give a smaller cover. The only possible reduction to a singleton would contradict ∣G∣≥2|G| \ge2.

Write hull⁡(G)\operatorname{hull}(G) for this selected arc. The word “selected” matters: a set may have several shortest covering arcs, and Ψ\Psi resolves that choice.

Lemma 6.4. For ∣G∣≥2|G| \ge2 and 0≤m≤n−20 \le m \le n-2,

Φ(G)≤1+Φ(ρG),(26)\Phi(G) \le1+\Phi(\rho G), \tag*{(26)}
Φ(G)≤2n+1−m+Φ(XmG).(27)\Phi(G) \le2n+1-m+\Phi(X_mG). \tag*{(27)}

Proof. For rotation, the full circle is immediate. Otherwise reverse-rotate hull⁡(ρG)=I(α,p)\operatorname{hull}(\rho G)=I(\alpha,p). If α>1−p\alpha>1-p, its canonical start decreases by one and its potential increases by one. At α=1−p\alpha=1-p, the new canonical start is n−pn-p, and the potential changes by 1−n1-n. The reverse-rotated arc covers GG, proving (26).

If XmGX_mG is a singleton, the only possible GG is {m,m+1}\{m,m+1\}. This is the arc I(m,2)I(m,2) and has potential 2n+1−m2n+1-m, including the case n=2n=2, m=0m=0 of the full circle. Thus (27) holds with equality.

Suppose ∣XmG∣≥2|X_mG| \ge2. Its image omits h=n−m−1h=n-m-1, so its selected covering arc I0=hull⁡(XmG)I_0=\operatorname{hull}(X_mG) is proper. Neither endpoint is hh, by Lemma 6.3. The preimage P=Xm−1(I0)P=X_m^{-1}(I_0) is a circular arc of size at least two, and

Ψ(P)−Ψ(I0)≤2n+1−m.(28)\Psi(P)-\Psi(I_0) \le2n+1-m. \tag*{(28)}

The calculation is given in Appendix § 9. It uses the increasing lift of XmX_m obtained by cutting the target circle at its omitted point. An interval avoiding that point lifts to an interval; one crossing it has preimage formed by the two end intervals, which together give a wrapping arc. Since PP covers GG, inequality (28) proves (27).

Proof of Theorem 1.3. The case n=1n=1 follows from Lemma 6.2. For n≥2n \ge2, take any sequence of rotations and slips from the full small circle to its first singleton. At each step Lemma 6.4 bounds the decrease of Φ\Phi by the cost of that step. Summing gives total cost at least

Φ(Z/nZ)−0=(n−1)(2n+1).\Phi(\mathbb{Z}/n\mathbb{Z})-0=(n-1)(2n+1).

By (23) and Lemma 6.2,

s(Ck)=n+d(Z)≥n+(n−1)(2n+1)=2n2−1.s(C_k)=n+d(\mathbb{Z}) \ge n+(n-1)(2n+1)=2n^2-1.

Lemma 6.1 gives equality. For any alphabet with at least two letters, a surjective map onto {a,b}\{a,b\} and Lemma 5.3 transfer the exact threshold.

Proof of Corollary 1.4. Theorem 1.1 gives the upper bound. The lifted binary family gives the lower bound at every weight over each fixed alphabet. Both are quadratic with positive leading coefficient.

Constructing the reset words

Both proofs give algorithms on an explicit prefix tree. The short-detection proof uses infinite series only to establish the length bound; the algorithm itself uses finite rational linear algebra.

A basis of short observations

Let N=∣Q∣N = |Q|, d=∣Σ∣d = |\Sigma|, and h=2k−3h = 2k - 3. For each letter bb, let BbB_b be the deterministic transition matrix, with (Bb)pq=1(B_b)_{pq} = 1 when p⋅b=qp \cdot b = q. Set Bw=Bb1⋯BbtB_w = B_{b_1} \cdots B_{b_t} for w=b1⋯btw = b_1 \cdots b_t, and let α\alpha be the row vector that is one on ZZ and zero elsewhere. For ∅≠S⊊Z\varnothing\ne S \subsetneq Z, define the column vector

νS(q)=r1S(π(q))−∣S∣.\nu_S(q) = r1_S(\pi(q)) - |S|.

Then

αBwνS=r(∣Tw−1(S)∣−∣S∣).(29)\alpha B_w\nu_S = r\left(|T_w^{-1}(S)| - |S|\right). \tag*{(29)}

We can test all words of length at most hh by testing a basis of their row vectors.

Lemma 7.1. There is an algorithm that constructs at most NN words B⊆Σ≤h\mathcal{B} \subseteq\Sigma^{\le h} such that the rows αBw\alpha B_w, w∈Bw \in\mathcal{B}, form a basis of

Vh=span⁡Q{αBw:∣w∣≤h}.V_h = \operatorname{span}_{\mathbb{Q}}\{\alpha B_w : |w| \le h\}.

It tests at most 1+dN1 + dN candidate rows for independence.

Proof. Start with α\alpha, represented by ε\varepsilon. Process retained rows in nondecreasing word length. For each retained word ww with ∣w∣<h|w| < h, test the rows represented by wbwb, b∈Σb \in\Sigma, retaining just those independent of the rows already retained. At most NN rows can be retained, and each has at most dd tested extensions.

To check that discarding a row loses nothing, induct on length. Suppose every row represented by a word of length at most tt lies in the span of retained rows whose represented lengths are at most tt. Multiplying such an expression by BbB_b expresses each length-(t+1)(t+1) row in terms of extensions of those retained rows. These extensions are tested by depth t+1t+1 and either retained or expressed in previously retained rows of at most that depth. This proves the assertion up to the cutoff hh. □

Theorem 7.2. Given an explicitly listed finite maximal prefix code of height k≥2k \ge2 and its alphabet, one can decide synchronization and, when it holds, construct a reset word of length at most (k−1)(4k−5)(k - 1)(4k - 5) in polynomial bit complexity.

Proof. Construct the tree and transition table, choose a letter aa, and find its pure leaf ara^r. If r=1r = 1, output ak−1a^{k-1}. Otherwise compute the basis B\mathcal{B} of Lemma 7.1 once.

For each set SS encountered in the preimage construction, evaluate αBwνS\alpha B_w\nu_S for w∈Bw \in\mathcal{B}. If all values vanish, then (29) vanishes for every word of length at most hh. Theorem 3.1 makes it vanish for all words. A reset word would give a nonzero value, as in Lemma 3.2, so this certifies nonsynchronization.

Otherwise a basis word supplies the required short unbalancing word. For the first singleton test, choose a fiber of size at least two. At later steps, test the rr rotations to find a larger preimage. There are at most r−1r - 1 expansions. If the procedure does not return a nonsynchronization certificate, it outputs (9). Proposition 3.4 proves that this word resets and satisfies the length bound. Thus both answers are sound, and the procedure terminates on every input.

For the bit bound, entries of αBw\alpha B_w count the images of rr starting states, so they are integers between 0 and rr. There are at most 1+dN1 + dN candidate rows of dimension NN. Rational Gaussian elimination can be implemented with intermediate coordinates given by ratios of minors of the integer input matrix. A minor of order s≤Ns \le N has absolute value at most (rs)s(r\sqrt{s})^s by Hadamard’s inequality. Numerators and denominators therefore have O(Nlog⁡(Nr+1))O(N\log(Nr+1)) bits; the same polynomial estimate applies to the actual residual and normalized pivot coordinates. Integer arithmetic and reduction of fractions then take polynomial time. The number of arithmetic operations, row evaluations, rotations, and transition simulations is polynomial in NN, dd, kk. The output has O(k2)O(k^2) letters. All these parameters are bounded by the explicit alphabet and code listing size. □\square

At height one the decoder is a singleton and the algorithm returns ε\varepsilon. The procedure constructs a reset word within the bound; it does not compute a shortest reset word in general.

The consecutive-depth construction

Lemma 5.2 can be implemented directly. Test closure at xx by examining the pairs u,v∈Au,v\in A. A failed test supplies the short–short round. If closure holds, compute g=gcd⁡(x,r)g=\gcd(x,r) and project AA onto a block of length gg to obtain DD. Choose p∈Dp\in D and enumerate Σg\Sigma^g to find q∉Dq\notin D. The long–short round is then given by (19).

These searches are polynomial in the input size. Indeed,

∣Σ∣g≤∣Σ∣r≤∣C(A)∣,|\Sigma|^g \leq|\Sigma|^r \leq|C(A)|,

since every word of length rr contributes either one short leaf or dd long leaves. There are at most r−1r-1 rounds, and all decoder images and offsets can be updated by direct simulation.

An equivalent implementation avoids computing DD: enumerate pairs (u,v)∈C(A)×A(u,v)\in C(A)\times A and test whether the pair advances all currently eligible offsets. The forcing lemma guarantees a successful pair of total length at most 2r+12r+1. When closure fails, short–short pairs already suffice. This is the finite-search formulation used by the verified implementation.

The remaining gap

Does every synchronizing finite maximal prefix code of height k≥2k\geq2 satisfy

s(C)≤2(k−1)2−1?s(C)\leq2(k-1)^2-1?

The consecutive-depth theorem and the binary family show that this would be the exact bound over every alphabet with at least two letters. Corollary 3.5 also proves it when a sufficiently short pure-letter codeword is present, under the synchronization hypothesis.

The two upper-bound proofs indicate where the gap arises. In the general construction, each preimage enlargement requires a short unbalancing word, a return to the pure-letter cycle, and possibly a rotation. In the consecutive-depth construction, order along the input lets one control all alternative parsings by the least surviving offset. This avoids the repeated cycle-compression cost.

That order need not hold in an arbitrary prefix tree. If the next codeword length at position jj is ℓj\ell_j, then

F(j+1)−F(j)=1+ℓj+1−ℓj,F(j+1)-F(j)=1+\ell_{j+1}-\ell_j,

which can be negative. Thus the proof for two lengths cannot simply be applied after replacing the other lengths by consecutive ones. A sharper general bound would need either a cheaper preimage construction or a way to control parsings without this monotonicity.

Example 8.1. For k=3k=3, the extremal code is

C3={aa,aba,abb,baa,bab,bba,bbb},C_3=\{aa,aba,abb,baa,bab,bba,bbb\},

and aa bbb aaaa\,bbb\,aa is a shortest reset word, of length seven. In contrast, A={aa,ab}A=\{aa,ab\} gives

C(A)={aa,ab,baa,bab,bba,bbb}.C(A)=\{aa,ab,baa,bab,bba,bbb\}.

Here AA is not a subalphabet square, so Theorem 1.2 gives the strict upper bound s(C(A))≤6s(C(A))\leq6.

Preimages of arcs under a slip

We prove (28), completing Lemma 6.4. Fix 0≤m≤n−20 \le m \le n - 2 and let h=n−m−1h = n - m - 1. Let I0=I(α0,p0)I_0 = I(\alpha_0,p_0) be a proper arc with 2≤p0≤n−12 \le p_0 \le n - 1, neither endpoint equal to hh. The increasing lift

X^m:{0,…,n−1}⟶L={−m,−m+1,…,n−m−2}\widehat{X}_m:\{0,\ldots,n-1\}\longrightarrow L=\{-m,-m+1,\ldots,n-m-2\}

is defined by

X^m(g)={g−m,g≤m,g−m−1,g≥m+1.\widehat{X}_m(g)= \begin{cases} g-m, & g\le m,\\ g-m-1, & g\ge m+1. \end{cases}

It takes every value in LL once except zero, which has preimage {m,m+1}\{m,m+1\}. Reduction modulo nn gives XmX_m. The single missing residue is hh.

The arc avoids hh. There is a unique lift [u,u+p0−1]⊆L[u,u+p_0-1]\subseteq L of I0I_0. Its preimage is an ordinary integer interval. The three possible positions of this interval relative to zero give Table 1. All displayed starts of PP are canonical. In the first row the start of I0I_0 is uu; in the second it is also uu; in the third it is u+nu+n. Substitution into Ψ(α,p)=(p−1)(2n+1)−α\Psi(\alpha,p)=(p-1)(2n+1)-\alpha gives the stated differences. If the first row gives p0+1=np_0+1=n, the preimage is the full circle and its displayed start is necessarily zero.

Position of the lifted intervalP=Xm−1(I0)P=X_m^{-1}(I_0)Ψ(P)−Ψ(I0)\Psi(P)-\Psi(I_0)
u≤0≤u+p0−1u\le0\le u+p_0-1I(u+m,p0+1)I(u+m,p_0+1)2n+1−m2n+1-m
u≥1u\ge1I(u+m+1,p0)I(u+m+1,p_0)−m−1-m-1
u+p0−1≤−1u+p_0-1\le-1I(u+m,p0)I(u+m,p_0)n−mn-m

Table 1. The preimage of an arc avoiding the omitted point. The first case gains one point by containing the doubled fiber.

The arc contains hh. Since hh is not an endpoint, write

I0={h−t,…,h,…,h+s}(modn),t,s≥1,p0=t+s+1≤n−1.I_0=\{h-t,\ldots,h,\ldots,h+s\}\pmod n,\qquad t,s\ge1,\qquad p_0=t+s+1\le n-1.

The part after hh lifts to [−m,−m+s−1][-m,-m+s-1], and the part before hh lifts to [n−m−1−t,n−m−2][n-m-1-t,n-m-2]. Their preimages are an initial and a final integer interval in {0,…,n−1}\{0,\ldots,n-1\}. The gap has a nonempty preimage because p0≤n−1p_0\le n-1, so their union is a proper wrapping arc.

There are three cases, according to which lifted interval contains zero; see Table 2. The first two cannot occur together: s≥m+1s\ge m+1 and t≥ht\ge h would imply t+s+1≥n+1t+s+1\ge n+1. The implications in the first column follow from t+s+1≤n−1t+s+1\le n-1. The canonical start of I0I_0 is h−t−nh-t-n in the first row and h−th-t in the other two. The displayed starts of PP are canonical as well. These values give the potential differences in the table.

Position relative to the doubled fiberP=Xm−1(I0)P = X_m^{-1}(I_0)Ψ(P)−Ψ(I0)\Psi(P) - \Psi(I_0)
s≥m+1s \ge m + 1 (so t<ht < h)I(−t,p0)I(-t,p_0)−m−1-m-1
t≥ht \ge h (so s≤m−1s \le m - 1)I(−1−t,p0)I(-1-t,p_0)n−mn-m
s≤ms \le m, t≤h−1t \le h - 1I(−t,p0−1)I(-t,p_0-1)−n−m−2-n-m-2

Table 2. The preimage of an arc crossing the omitted point. In the last case the arc loses the point hh and contains no doubled fiber, so its size decreases by one.

The preimage has size at least two in every case. In the last row this follows from p0=t+s+1≥3p_0=t+s+1\ge3. All six differences are at most 2n+1−m2n+1-m. This proves (28).

Formal verification and reproducibility

The Lean development uses proper-prefix states and proves all four main results, including short detection, the parsing and forcing lemmas, the age reduction, and the arc-potential inequality. The main results are collected in HeightSync.Manuscript:

Paper statementLean declaration
Theorem 1.1universal
Theorem 1.2consecutive
Theorem 1.3binary
Corollary 1.4growth

Table 3.

The complete statement index is provided in MANUSCRIPT_COVERAGE.md. Short detection is formalized over arbitrary fields. For the embedding lemma, the development constructs a division ring through skew-polynomial Ore fractions; the Laurent-series construction in Lemma 4.1 is a direct alternative proof of the same embedding statement.

Both reset constructions have executable implementations with correctness proofs. The declarations VerifiedAlgorithms.universal and VerifiedAlgorithms.sharp also bound their work by fixed polynomials in the explicit input size. The cost model charges binary integer arithmetic, rational normalization, and finite list and table operations. Arithmetic bounds apply to the actual intermediate values and executed elimination stages; list and table operations receive specified conservative bulk charges. These are bounds in that model, not theorems about Lean’s compiler or elapsed machine time. The definitions and scope are documented in COST_MODEL.md.

The checked source uses Lean 4.28.0 and mathlib v4.28.0. The verification run builds all 97 source modules, checks the manuscript index against the compiled environment, runs executable checks, and audits the dependencies of all 2,970 declarations in the project namespace. The audit permits only the standard logical axioms propext, Classical.choice, and Quot.sound; there are no admitted proofs or additional axioms. From the formalization directory, the full check is

python3 checks/verify.py

The complete Lean sources, verification report, source hashes, and axiom log are included as ancillary files with the arXiv submission.

OpenAI Codex assisted with the exposition, figures, and Lean formalization.

References

  1. [1]M.-P. Bé​al, M. V. Berlinkov, and D. Perrin, A quadratic upper bound on the size of a synchronizing word in one-cluster automata, International Journal of Foundations of Computer Science 22(2) (2011), 277–288. doi:10.1142/S0129054111008039.DOI
  2. [2]M. V. Berlinkov, R. Ferens, A. Ryzhikov, and M. Szykula, Synchronization of strongly connected partial DFAs and prefix codes, Discrete Mathematics & Theoretical Computer Science 28(2), article 34 (2026). doi:10.46298/dmtcs.16465.DOI
  3. [3]A. Carpi and F. D’Alessandro, On incomplete and synchronizing finite sets, Theoretical Computer Science 664 (2017), 67–77. doi:10.1016/j.tcs.2015.08.042.
  4. [4]J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi, Matematicko-fyzikálny časopis 14(3) (1964), 208–216. DML-CZ:126647.
  5. [5]R. Chandelkar and S. S. Chadha, Quadratic bounds for uncompletable words and matrix mortality, arXiv:2609.30817v2 (2026).arxiv.org/abs/2609.30817
  6. [6]J.-É. Pin, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17 (1983), 535–548. doi:10.1016/S0304-0208(08)73432-7.DOI
  7. [7]I. K. Rystsov, Quasioptimal bound for the length of reset words for regular automata, Acta Cybernetica 12(2) (1995), 145–152. Szeged repository.
  8. [8]M. P. Schützenberger, On the synchronizing properties of certain prefix codes, Information and Control 7(1) (1964), 23–36. doi:10.1016/S0019-9958(64)90232-3.DOI
  9. [9]B. Steinberg, The averaging trick and the Černý conjecture, International Journal of Foundations of Computer Science 22(7) (2011), 1697–1706. doi:10.1142/S0129054111008970.DOI

Paper details

vlnc:W_tdewbruh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents