# The Černý conjecture on synchronizing automata

A finite automaton is synchronizing if some sequence of inputs drives it into one and the same state wherever it starts, like a reset button for a machine whose state is unknown. Černý conjectured that for an automaton with $n$ states, a reset sequence of length $(n-1)^2$ always suffices, which would be exactly tight. More than sixty years later the best general bound is still cubic in $n$.

## Problem

A complete deterministic finite automaton consists of a finite set of states $Q$ with $|Q| = n$, a finite input alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \to Q$, extended to words letter by letter. A word $w$ is *synchronizing* (or a *reset word*) if $\delta(q, w)$ is the same state for every $q \in Q$, and the automaton is *synchronizing* if it has such a word.

**Conjecture (Černý).** Every synchronizing automaton with $n$ states has a synchronizing word of length at most $(n - 1)^2$.

## Background

Ján Černý (1964) described, for each $n$, an automaton whose shortest synchronizing word has length exactly $(n-1)^2$, and the conjecture that no automaton is worse is attributed to him in the 1960s. It is one of the best-known open problems in automata theory: easy to state, testable by computer for small $n$, and resistant to general methods. Volkov's survey describes its history and the special classes of automata for which it is known.

## What is known

- Every synchronizing automaton with $n$ states has a reset word of length at most $\alpha n^3 + o(n^3)$ for an absolute constant $\alpha$. Pin and Frankl (1982) gave $\alpha = 1/6$; Szykuła (2017) lowered it to about $0.1664$, and Shitov (2019) to $\alpha \le 0.1654$, the best bound known.
- The Černý automata show that $(n-1)^2$ cannot be lowered.
- The bound $(n-1)^2$ has been verified for small $n$ and proved for special classes, for example Eulerian, aperiodic and cyclic automata, as recorded in the formal-conjectures file. A July 2026 preprint (Zhu, unrefereed, obtained with AI assistance) claims it for one-cluster automata.

## What would count as progress

- A counterexample: an automaton with $n$ states whose shortest reset word is longer than $(n-1)^2$. Its reset threshold can be computed exactly by breadth-first search over subsets of states, so any candidate is checkable.
- A better constant in the cubic bound, or a bound of order $n^{3 - \varepsilon}$.
- Proofs of the quadratic bound for further natural classes of automata, or extended exhaustive verification for small $n$ and alphabet sizes, with published code.
- A formal proof of the Lean statement `cerny_conjecture`, or of Shitov's bound stated in the same file, [Wikipedia/CernyConjecture.lean](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/CernyConjecture.lean).

## References

1. J. Černý, [Poznámka k homogénnym experimentom s konečnými automatmi](https://dml.cz/bitstream/handle/10338.dmlcz/126647/MathSlov_14-1964-3_2.pdf), Mat.-fyz. časopis **14** (1964), 208–216.
2. M. V. Volkov, [Synchronizing automata and the Černý conjecture](https://doi.org/10.1007/978-3-540-88282-4_4), in Language and Automata Theory and Applications (LATA 2008), LNCS 5196, 11–27.
3. Y. Shitov, [An improvement to a recent upper bound for synchronizing words of finite automata](https://arxiv.org/abs/1901.06542), J. Autom. Lang. Comb. **24** (2019), 367–373.
4. Y. Zhu, [The Černý conjecture for one-cluster automata via annular spectral descent](https://arxiv.org/abs/2607.19675), arXiv:2607.19675 (2026).

## Source

Imported from [Formal Conjectures Wikipedia/CernyConjecture](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/CernyConjecture.lean), curated by Google DeepMind and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.