gpt 6 astra ultra attempt on CS-75

Černý Conjecture on Shortest Reset Words of Synchronizing Automata

Definitions and mathematical statement

A complete deterministic finite automaton consists of a finite state set $Q$, finite alphabet $\Sigma$, and transition function $\delta:Q\times\Sigma\to Q$, extended to words by successive transitions. A word $w\in\Sigma^*$ resets the automaton if $\delta(q,w)$ is the same state for every $q\in Q$. The automaton is synchronizing if some reset word exists. For $n=|Q|$, Černý's conjecture asserts \[ \min\{|w|:w\text{ resets the automaton}\}\le(n-1)^2. \] The empty word is permitted and resets a one-state automaton. The assertion is about every synchronizing complete automaton, with no strong-connectivity or alphabet-size restriction. A polynomial algorithm finding some reset word does not prove this particular sharp quadratic length bound.

Formulation and concept references: [S1].

Short English statement

Does every synchronizing $n$-state deterministic automaton have a reset word of length at most $(n-1)^2$?

Research attempt

Scope and source audit (27 September 2026).

The automata are complete and deterministic, and every synchronizing automaton is included, whether or not it is strongly connected. The empty word handles the one-state case. Volkov's primary survey [S1] explicitly distinguishes the general conjecture from numerous solved classes; its checked text says that it reflects results as of 24 August 2026. The visible arXiv version identifier and the date printed in that evolving text are not treated as interchangeable dates. The discussion also warns that an announced general proof had an acknowledged error. No such proof is assumed here.

The attempted route is combinatorial compression. It gives a fully proved cubic bound, the conjectured quadratic bound for two explicit classes, and a general reset certificate of quadratic length for the classical example family. The gap is a global bound on the cost of successive compressions in an arbitrary automaton. A fast decision algorithm for synchronization does not fill that gap.

The subset automaton gives the exact finite optimization problem.

For a nonempty set $S\subseteq Q$ and a letter $a$, write \[ S\cdot a=\{\delta(q,a):q\in S\}. \] Extend this action to words in the same order as the original transition function. The cardinality never increases. A word resets the automaton exactly when $Q\cdot w$ is a singleton. Thus the shortest reset length is the graph distance from $Q$ to the collection of singletons in the directed graph of nonempty subsets, with one labeled edge for each letter action.

Breadth-first search in this graph finds the exact optimum or determines that no singleton is reachable. It visits at most $2^n-1$ vertices. The existence of this finite algorithm is useful for small diagnostics, but its exponential state space provides no quadratic bound on a shortest path. A shortest successful path cannot repeat a subset, so a general bound from this argument alone is only exponential. Different letters inducing the same map on $Q$ may be identified, but the number of possible maps is itself $n^n$.

The issue is not a shortage of termination arguments. It is the requirement that every synchronizing automaton have a path vastly shorter than the full subset graph permits in a general directed reachability problem.

Lemma 378.1: pair merging characterizes synchronization.

An automaton is synchronizing if and only if every pair of states can be merged by some word. If a pair can be merged, it can be merged by a word of length at most $\binom n2$.

Proof. A reset word merges every pair. Conversely start with $S=Q$. If $|S|>1$, choose different states $p,q\in S$ and a word merging them. Applying that word to all of $S$ reduces its size by at least one, since images of different states can coincide but no state creates more than one image. Repeating at most $n-1$ times reaches a singleton.

For the length claim, follow a shortest merging word in the graph of unordered pairs. Before the final step every vertex is a two-element subset. No such vertex repeats: removing the segment between two occurrences would leave a shorter word with the same final effect on that pair. There are $\binom n2$ two-element subsets, so there are at most that many steps before reaching a singleton.$\square$

Pair merging can also be tested efficiently. Build the pair-transition graph including its diagonal states, and run reverse reachability from all singletons. A pair is mergeable exactly when it reaches that set. The graph has $O(n^2)$ vertices and $O(|\Sigma|n^2)$ labeled edges. This proves polynomial-time recognition of synchronization, while the subset search is the exact length optimization.

A complete general cubic bound.

Combining the two parts of Lemma 378.1 gives \begin{equation}\label{wsref-0-61-33-37-38-3a-63-75-62-69-63} \operatorname{rt}(\mathcal A) \leq(n-1)\binom n2 =\frac{n(n-1)^2}{2}. \end{equation} Here $\operatorname{rt}$ denotes the reset threshold. Each compression is applied to the current image set, but its pair-merging word is bounded using the same full $n$-state automaton. This bound is intentionally elementary and is not presented as the best known cubic estimate in the literature.

It is not legitimate to replace $\binom n2$ at a later stage by $\binom{|S|}2$ without additional structure. The intermediate images of a pair under a word need not stay inside the starting subset $S$. Even though $|S\cdot w|\leq|S|$, its actual states can move throughout $Q$. Counting only pairs in the initial set would discard reachable pair states that matter to the shortest path.

Nor does each letter have to shrink the current image. Permutations preserve its size, and a noninjective letter can be injective on the current subset. A successful word may therefore have long intervals of movement between rank drops. The quadratic conjecture requires a better amortized control of this movement, or a construction that organizes different compressions together.

Proposition 378.2: the conjectured bound for a sink state.

Suppose that a synchronizing automaton has a state $z$ fixed by every letter. Then \[ \operatorname{rt}(\mathcal A)\leq(n-1)^2. \] Indeed a reset word must reset to $z$, because the image of $z$ under every word is $z$. Therefore each state has a directed path to $z$ in the ordinary transition graph. A shortest such path has no repeated state before arriving at $z$, so its length is at most $n-1$.

Start with the image set $Q$, which contains $z$. As long as another state remains, choose one and apply a shortest path sending it to $z$. The image of $z$ stays $z$, so the current image set loses at least one state. There are at most $n-1$ rounds, each of length at most $n-1$. This proves the displayed bound without any assumption of strong connectivity. In fact a nontrivial strongly connected automaton cannot have a sink, so this class specifically checks part of the scope that a strong-connectivity restriction would omit.

The proof uses a fixed state that survives every subsequent word. A state that happens to be the image of one compression need not remain fixed later. Replacing the sink by an arbitrary chosen state would lose precisely the invariant that makes this argument work.

Proposition 378.3: the conjectured bound for order-preserving letters.

Suppose $Q=\{1,\ldots,n\}$ and every letter preserves this linear order. Compositions preserve it as well. If a word merges states $1$ and $n$, then the image of every state lies between the images of these two endpoints, so all images are equal. Hence a word merging that one pair resets the automaton.

If the automaton is synchronizing, Lemma 378.1 gives such a word of length at most $\binom n2$. For $n\geq2$, \[ \binom n2\leq(n-1)^2, \] and the one-state case is immediate. This proves the selected bound throughout this class. The proof gives a sufficient upper bound, not the optimal known estimate for every order-preserving subclass.

The order must be common to all letters. Each individual transformation may look simple or admit an ordering of its own while their compositions fail to preserve any one order. The endpoint argument is then unavailable. It also concerns a linear order; a cyclic-order condition is a different hypothesis requiring a separate proof.

The classical quadratic-length family, with an explicit certificate.

For $n\geq2$, define an automaton on $\{0,\ldots,n-1\}$ with \[ a(q)=q+1\pmod n,\qquad b(n-1)=0,\qquad b(q)=q\quad(0\leq q<n-1). \] The word \begin{equation}\label{wsref-0-61-33-37-38-3a-63-65-72-6e-79-77-6f-72-64} b(a^{n-1}b)^{n-2} \end{equation} resets it and has length $1+n(n-2)=(n-1)^2$.

Here is the complete image computation. The first $b$ maps $Q$ to $\{0,\ldots,n-2\}$. If the current set is $\{0,\ldots,k\}$ with $1\leq k\leq n-2$, then $a^{n-1}$ shifts it one step backward, giving $\{n-1,0,\ldots,k-1\}$. The following $b$ maps this to $\{0,\ldots,k-1\}$. After $n-2$ such blocks the image is $\{0\}$. For $n=2$ the repeated block is empty and $b$ alone resets.

The family is the classical sharp family discussed in [S1]. Its general lower-bound theorem is attributed there, not inferred from the preceding upper certificate. The companion breadth-first search independently verifies equality with $(n-1)^2$ for the finite range $2\leq n\leq10$. This finite verification does not replace a proof of sharpness at every $n$, and no such lower-bound proof is claimed as part of the elementary argument here.

The example already refutes an especially short proposed route: repeating a rank-reducing letter need not keep reducing rank. The letter $b$ is idempotent, so $Q\cdot b^j=Q\cdot b$ for every $j\geq1$. The intervening rotations in (a378:cernyword) are essential to that certificate. Knowing that one letter has rank $n-1$ does not give a reset word by just applying it $n-1$ times.

A precise rank-profile reformulation of the missing step.

For a current image set $S$ with $|S|>1$, let \[ c(S)=\min\{|u|:|S\cdot u|<|S|\}. \] Every such $c(S)$ is finite in a synchronizing automaton and at most $\binom n2$ by merging a pair. If a chain of words produces images \[ Q=S_0\longrightarrow S_1\longrightarrow\cdots\longrightarrow S_m, \qquad |S_{j+1}|<|S_j|,\quad |S_m|=1, \] then the concatenated length is the sum of the word lengths used along that particular chain. The challenge is to select a chain whose total cost is at most $(n-1)^2$. Local minimization of $c(S_j)$ does not automatically optimize that total, because different shortest compressions can produce different next subsets with different future costs.

A bound depending only on rank would suffice if it were strong enough after summation, but no such sharp universal bound is proved here. In particular the pair graph tracks two states while the actual optimization tracks the interaction of all current states. A proof that disregards the resulting subset can spend its budget repeatedly resolving the same kind of alignment problem.

The sink proof bypasses that issue by retaining one fixed image. The order-preserving proof bypasses it by reducing all constraints to two endpoints. An arbitrary automaton is not shown to have either organizing feature. This identifies the missing structural assertion rather than merely suggesting another breadth-first search.

Exact finite verification.

The diagnostic enumerates all ordered pairs of transition maps for complete two-letter automata on at most four states. For each it compares pair-graph recognition with reachability of a singleton in the full subset graph. For every synchronizing case in that finite census, the exact shortest reset word has length at most $(n-1)^2$. The maximal thresholds and witness automata are recorded rather than estimated by a heuristic word search.

The same program independently constructs (a378:cernyword), applies it to every state, and computes exact shortest lengths for its family up to ten states. It checks the sink and common-linear-order hypotheses directly on finite examples before testing the corresponding bounds. These finite procedures verify implementation and small cases. They do not exhaust all alphabet sizes or all state counts, and the mathematical proofs of the two complete classes above do not rely on extrapolating the census.

Outcome.

UNRESOLVED. The attempt proves synchronization via pair merging, an explicit general cubic estimate, and the conjectured bound in the sink and common-order classes. It supplies an exact quadratic reset certificate for the classical family and locates the failure of naive repeated compression. The first missing general step is a uniform quadratic bound on the total cost of a suitably chosen sequence of image reductions. Neither the finite census nor efficient synchronization recognition establishes it.

Sources

• S1 Mikhail V. Volkov, "List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata," arXiv:2508.15655 (2025, updated August 2026). https://arxiv.org/html/2508.15655. Formulation source.