Find a synchronizing automaton with reset threshold exceeding (n-1)^2, or extend Cerny verification to n=13
Statement
A deterministic finite automaton (DFA) with state set $Q$ ($|Q|=n$) over an input alphabet is synchronizing if some input word $w$ (a reset word) maps every state to a single state: $|Q\cdot w|=1$. The reset threshold is the length of a shortest reset word. Cerny's conjecture (1964) asserts that every synchronizing $n$-state DFA has reset threshold at most $(n-1)^2$; the Cerny automata achieve exactly $(n-1)^2$. The conjecture is verified by exhaustive search only for small $n$: all 2-letter automata with $n \le 12$ states, and all 3-letter automata with $n \le 8$ states, satisfy it. Exhibit any synchronizing DFA whose reset threshold is strictly greater than $(n-1)^2$ (a counterexample, refuting the conjecture), or extend the exhaustive verification to all 2-letter automata on 13 states.
Acceptance. FULLY RESOLVES (refutation): a synchronizing DFA - given by its transition function (an $n\times k$ table) - together with a proof that its reset threshold exceeds $(n-1)^2$. The reset threshold is machine-checkable via breadth-first search over subsets of $Q$ from the full set $Q$ to a singleton (the power automaton), computing the exact shortest reset word length; a certificate is the BFS distance plus the resulting shortest word. FULLY (verification extension): an exhaustive check that all synchronizing 2-letter 13-state DFAs have reset threshold $\le 144=(13-1)^2$, with reproducible search code and census counts. PARTIAL: a family of automata with reset thresholds close to $(n-1)^2$ not previously recorded, or verification of a nontrivial restricted class at $n=13$. Provide the transition table and a reset-threshold verifier.
Background
Cerny's conjecture is the most famous open problem in automata theory (over 60 years open). The extremal Cerny automaton $C_n$ (states $0,\dots,n-1$; letter $a$: $i\mapsto i+1 \bmod n$; letter $b$: fixes all states except $n-1\mapsto 0$) has reset threshold exactly $(n-1)^2$, so the conjectured bound is tight if true. The best general upper bound is cubic - currently $\approx 0.1654\,n^3$ (Shitov, 2019), improving the Frankl/Pin/Klyachko $(n^3-n)/6$ bound. Exhaustive computational verification reaches 2-letter automata up to $n=12$ (the $n=12$ census required about 100 core-years, ~$10^{15}$ automata) and 3-letter up to $n=8$. No automaton with reset threshold $>(n-1)^2$ has ever been found; a purported 2024 proof (Trahtman) was withdrawn. Source: Volkov, 'Synchronizing Automata and the Cerny Conjecture' (LATA 2008); the maintained survey 'List of Results on the Cerny Conjecture and Reset Thresholds for Synchronizing Automata' (arXiv:2508.15655).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | List of Results on the Cerny Conjecture and Reset Thresholds for Synchronizing Automata (2025) | link |
| REF-02 | Synchronizing word / Cerny conjecture | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.