The Černý conjecture: synchronizing words of length (n−1)²
Difficulty 75: sixty years, and the upper bound is still cubic, with only the constant improved (Pin–Frankl, then Szykuła 2018 and Shitov 2019) against a quadratic conjecture that is tight; harder than sunflowers (71), where one log factor remains, and just below deterministic prime construction (76) and diagonal Ramsey (78). Application value 8: reset sequences for finite-state devices and testing are a real, specific use. Leverage 30: the central open problem of synchronizing automata, with a large literature of special classes.
The problem
Can any n-state automaton that can be reset be reset by a word of at most (n−1)² letters?
- 1Machine in an unknown state
- 2A command word resets every state
- 3Černý machines need (n−1)² letters
- 4Best proof only gives about 0.165 n³
Finite-state machines. A deterministic finite automaton (DFA) is the simplest model of a digital controller: a finite set of states, an alphabet of input letters, and a rule that says, for each state and letter, which state comes next. You may have drawn one as a state diagram for a vending machine or a traffic light.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- The Černý conjecture: synchronizing words of length (n−1)²The problem
State of the art
Cubic upper bounds only. The classical bound (Pin and Frankl, early 1980s) stood until Szykuła (2018) and then Shitov (2019), who proved about , the best general bound. Eppstein (1990) gave an algorithm finding words of length at most and proved the conjecture for (transitions preserve a cyclic order). The conjecture is also known for several structured classes of automata. Černý's family of automata achieves exactly . The gap between quadratic and cubic has not moved in over 40 years apart from the constant.
Realistic applications
Concrete in automata engineering: a short synchronizing word resets a finite-state device (a protocol machine, a robotic part-orienter, a coded sequence decoder) from an unknown state to a known one without sensing. A quadratic bound would give tighter guarantees for such resets and for testing finite-state systems.
What counts as solved
A Lean proof of cerny_conjecture as stated for all alphabets and state types, or a Lean-checked counterexample: a finite DFA with states whose shortest synchronizing word is longer than .
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: CernyConjecture.cerny_conjecture in formal-conjectures (quoted above). Mathlib has DFA and DFA.evalFrom (Computability.DFA); the predicates DFA.IsSynchronizingWord and DFA.IsSynchronizing are defined in the corpus' DFA.lean, not in Mathlib itself, so a submission must import the corpus' definitions unchanged. A counterexample is a concrete finite DFA plus a Lean proof that no synchronizing word of length at most exists (a finite check over words or subsets of states). A proof must cover every alphabet and state type with . Judge with Comparator.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Small cases are verified by computer, but the conjecture is about all n and needs a new proof technique; the bound has not changed exponent in decades.
Bottlenecks
ranked by votes- #1TheoryCubic to quadratic gap
Linear-algebraic and extremal methods stall at a cubic bound with an improving constant (Shitov 2019); the Černý automata show quadratic is tight but no argument reaches it.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Jan 1, 2019Shitov's cubic boundsource
About 0.1654 n^3, the best general upper bound (J. Autom. Lang. Comb. 24; year only known).
- Jan 1, 1990Eppstein's algorithm and monotonic automatasource
Words of length 11n^3/48 + O(n^2) found in polynomial time; the conjecture proved for monotonic automata (SIAM J. Computing 19).
- Jan 1, 1964Černý's examplessource
A family of automata whose shortest synchronizing words have length (n-1)^2 (Mat.-fyz. časopis SAV 14).