Computer science · Combinatorics · Conjecture
Černý synchronization conjecture
How long a word is needed to bring every state of a synchronizing automaton to one state?
OpenOpenMath assessment · Oct 14, 2026
- Literature: 1 preprint
- Formal: None linked
- Computation: 1 explicit witness
- Review: Not yet reviewed
Frontier 1 report →
Overview
Known
The general conjecture remains open. The cited 2026 proof covers synchronizing one-cluster automata with positive least level, with a sharper parameter-dependent bound.
Open questions
Resolve the general quadratic bound beyond the indexed one-cluster class; the older circular case is not an open gap created by the positive-level hypothesis.
Latest
The general question asks about every synchronizing automaton. The 2026 advance has a unique-cycle letter and positive least level.
Precise statement · Exact conventions and hypotheses
A complete deterministic finite automaton has n ≥ 2 states and a finite alphabet; each letter acts as a function on states. It is synchronizing if some word maps every initial state to the same state. The reset threshold is the shortest such length. Černý’s conjecture asks for a bound of (n−1)² for every synchronizing automaton. The 2026 theorem assumes a one-cluster letter with positive level.
Definitions
- Reset word
- Apply the same sequence of letters from every possible starting state. A reset word sends all those states to one common destination.
- One-cluster letter and level
- The letter’s directed graph has a unique cycle, with trees feeding into it. Its level ℓ is the maximum distance to that cycle, equivalently the least exponent with Qa^ℓ = C.
Background
Question paraphrased by OpenMath. Original wording is available in the sources.
Landscape
Figures and explorable examples. Selecting a statement opens its exact wording.
Reset thresholds, computed
Černý’s automata sit exactly on the conjectured bound; the one-cluster family Fₙ grows only linearly, meeting its own sharper bound 3n − 5.
Computed for n ≤ 12 by exhaustive search; finite checks of two families, not evidence for the conjecture. Cₙ is defined here as usually stated; the cited source credits Černý with such examples without restating them.
Visual setup
A cycle with an incoming tail
The letter a in the exact four-state family: 0 ↔ 1 is the unique cycle, and 3 → 2 → 1 feeds into it.
Reading boundary. Only the a-transition skeleton is drawn. A one-cluster skeleton alone does not establish synchronization or the general Černý conjecture.
Only the transitions of letter a are drawn; the second letter is omitted.
Results
The question 1
- OpenThe general quadratic reset-word conjecture
No one-cluster or positive-level assumption is imposed on the general conjecture.
Conjecture · Primary formulation
OpenThe general quadratic reset-word conjecture
Every complete synchronizing deterministic finite automaton on n ≥ 2 states has a reset word of length at most .Assumptions
- No one-cluster or positive-level assumption is imposed on the general conjecture.
- Automata
- Complete, deterministic and synchronizing
- One-cluster restriction
- None
- Reset-word bound
- (n−1)²
In this problem
No one-cluster or positive-level assumption is imposed on the general conjecture.
Sources
Special cases 1
- ProvedThe bound for positive-level one-cluster automata≤ (m−1)(n−1)+mℓZhu 2026
The parameter-dependent theorem reaches the conjectured quadratic bound for the specified one-cluster class.
Theorem · Special case
ProvedZhu 2026The bound for positive-level one-cluster automata
If a complete synchronizing automaton on n states has a letter a with a unique cycle C of length m, and ℓ ≥ 1 is least with , then its reset threshold is at most .Assumptions
- The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
- Automata
- Complete, deterministic and synchronizing
- One-cluster restriction
- A letter with a unique cycle and least ℓ ≥ 1
- Reset-word bound
- (m−1)(n−1)+mℓ ≤ (n−1)²
In this problem
The parameter-dependent theorem reaches the conjectured quadratic bound for the specified one-cluster class.
The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
Does not cover: The general conjecture includes synchronizing automata with no one-cluster letter.
Bound
- Reset threshold
- ≤ (m−1)(n−1)+mℓ
- Conditions
- Synchronizing one-cluster automaton; cycle length m and least level ℓ ≥ 1.
- Source date
- Jul 22, 2026
Proof outline
Extend a subset until the cycle is covered
Finite-dimensional linear algebra and annular spectral descent
The proof separates invertible cycle behavior from nilpotent off-cycle behavior, constructs short relative extending words and iterates extension to obtain the reset-word bound. The family’s matching lower bound is combinatorial.
The proof concerns positive least level. It is a manuscript argument checked by its author, not a proof-assistant execution.
Proved: Positive-level one-cluster theorem reported ↗ · source dated Jul 22, 2026 · observed Oct 14, 2026. Synchronizing, unique a-cycle, least level ℓ ≥ 1.
Depends on: Relative extending words on the unique cycle
Independent mathematical assessment of an argument remains separate from the statement’s attributed status.
Sources
Related advances 2
- ProvedA family attaining the parameter-dependent bound3n−5Zhu 2026
The example is sharp for the parameter-dependent theorem.
Theorem · Related result
ProvedZhu 2026A family attaining the parameter-dependent bound
For each integer n ≥ 4 there is a strongly connected binary synchronizing one-cluster automaton F_n with m = 2, ℓ = n−2 and reset threshold .Assumptions
- The example is sharp for the parameter-dependent theorem. It does not establish (n−1)² as the threshold for all n in this family.
In this problem
The example is sharp for the parameter-dependent theorem. It does not establish (n−1)² as the threshold for all n in this family.
Bound
- Reset threshold of F_n
- 3n−5
- Conditions
- The specific strongly connected binary family, n ≥ 4, m = 2 and ℓ = n−2.
- Source date
- Jul 22, 2026
Sources
- ProvedČerný’s examples meet the boundČerný 1964 · per Zhu 2026
Shows the conjectured bound (n−1)² cannot be lowered; it says nothing about whether every automaton meets it.
Bound · Related result
ProvedČerný 1964 · per Zhu 2026Černý’s examples meet the bound
For every n ≥ 2 there is a synchronizing deterministic finite automaton on n states whose reset threshold is exactly (n−1)².Assumptions
- Complete deterministic automata; reset threshold is the length of a shortest reset word.
In this problem
The lower-bound examples: the conjectured bound would be best possible.
Shows the conjectured bound (n−1)² cannot be lowered; it says nothing about whether every automaton meets it.
Sources
Supporting results 1
- ProvedRelative extending words on the unique cycleZhu 2026
Letters act on the right; (wa^ℓ)⁻¹ denotes a set preimage, not an inverse transition function.
Theorem · Supporting result
ProvedZhu 2026Relative extending words on the unique cycle
Under the positive-level one-cluster hypotheses, for every nonempty proper S ⊂ C there is a word w with |w| ≤ n such that .Assumptions
- Letters act on the right; (wa^ℓ)⁻¹ denotes a set preimage, not an inverse transition function. The empty and whole-cycle subsets are excluded.
In this problem
Letters act on the right; (wa^ℓ)⁻¹ denotes a set preimage, not an inverse transition function. The empty and whole-cycle subsets are excluded.
Sources
Background 1
- ProvedThe older level-zero circular caseZhu 2026
This is the level-zero case m = n, established in the older circular-automaton literature recalled by the source.
Theorem · Supporting result
ProvedZhu 2026The older level-zero circular case
A complete synchronizing automaton with a letter that cycles through all n states has a reset word of length at most (n−1)².Assumptions
- This is the level-zero case m = n, established in the older circular-automaton literature recalled by the source.
In this problem
This is the level-zero case m = n, established in the older circular-automaton literature recalled by the source.
Sources
Compare statements · 2
Each row is a separate assertion. Its assumptions determine which question it answers.
| Statement | Automata | One-cluster restriction | Reset-word bound |
|---|---|---|---|
| The general quadratic reset-word conjecture → Open Exact statement & sources | Complete, deterministic and synchronizing | None | (n−1)² |
| The bound for positive-level one-cluster automata → Proved Exact statement & sources | Complete, deterministic and synchronizing | A letter with a unique cycle and least ℓ ≥ 1 | (m−1)(n−1)+mℓ ≤ (n−1)² |
The bound for positive-level one-cluster automata →
Constructions · 1
A four-state member of the sharp family
- Letter a
- 0 → 1; 1 → 0; 2 → 1; 3 → 2
- Letter b
- 0 → 1; 1 → 2; 2 → 3; 3 → 1
- Parameters
- n = 4, m = 2, ℓ = 2; parameter bound 7 versus conjectural bound 9
- Reset word
- a²b³a² = aabbbaa; length 7
- Images after each letter
- {0,1,2,3} → {0,1,2} → {0,1} → {1,2} → {2,3} → {1,3} → {0,2} → {1}
This is the n = 4 member of Definition 10.1. Its finite trace explains synchronization; the all-n optimality theorem needs the separate lower-bound argument.
A family attaining the parameter-dependent bound →Connections
Analogues and related questions 1
General quadratic bound related to Positive-level one-cluster bound.
VariantGeneral and one-cluster automata. The positive-level one-cluster theorem reaches the conjectured bound within its restricted class.
Limit It does not settle automata with no one-cluster letter.
Sources & review
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Introduction; definitions of synchronization and one-cluster level
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Main theorem and relative-extending-word result
Independent relationship review: not recorded. Link to this connection
Consequences 1
Assuming Positive-level one-cluster boundProved
A sharper bound can have its own equality examples
Under stated assumptionsThe family F_n attains the parameter-dependent one-cluster bound 3n−5 for every n ≥ 4, even though that bound is often smaller than the universal conjectural quadratic value.
Limit Sharpness here is a claim about the specified one-cluster parameters, not a resolution of the general synchronization conjecture.
Sources & review
Supporting statements
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Section 10, Definition 10.1, Lemma 10.2 and Corollary 10.8
Source-grounded explanation · independent explanation review: pending.
Timeline
Positive-level spectral proof is publishedSpecial case proved
Zhu publishes the restricted theorem, relative-extension argument and sharp binary family.
This is a selected source-supported milestone, not an exhaustive history.
- The bound for positive-level one-cluster automataProved
- Relative extending words on the unique cycleProved
- A family attaining the parameter-dependent boundProved
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Main theorem and relative-extending-word result
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Section 10, Definition 10.1, Lemma 10.2 and Corollary 10.8
Circular automata satisfy the boundSpecial case proved
The source recalls Dubuc’s theorem for a letter acting as a full cycle.
This is a selected source-supported milestone, not an exhaustive history.
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Introduction and cited Dubuc (1998)
Černý’s reset-word questionFoundation
The source traces the quadratic synchronization conjecture to Černý’s original work.
This is a selected source-supported milestone, not an exhaustive history.
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent ↗Introduction; definitions of synchronization and one-cluster level
Evidence
| Literature | Status OpenMath assessment · Oct 14, 2026.
|
|---|---|
| Formal | None linked Reported in sources: No complete proof-assistant artifact was identified in the selected paper. The source supplies linear-algebra and combinatorial proofs; the finite example trace is explanatory. |
| Computation | |
| Review | Not yet reviewed OpenMath assessment: The general conjecture remains open. The cited 2026 proof covers synchronizing one-cluster automata with positive least level, with a sharper parameter-dependent bound. Source comparison and presentation; independent mathematical review remains pending. OpenMath pilot collection · OpenMath source curation · assessed Oct 14, 2026 · review due Jan 14, 2027 Collection last checked Oct 14, 2026. |
Sources
Choose a starting point below. Each result links to its exact statement, cited passages and checks.
Start here
- Original question
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →Understand reset words and the one-cluster restriction.
- Proof source
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →Read the exact positive-level hypotheses and spectral proof.
- Proof source
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →Inspect the sharp family, its transitions and matching lower bound.
Bibliography 1
- The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →
Yinfeng Zhu · Preprint · Jul 22, 2026
Introduction; main positive-level results; Section 10, Definition 10.1, Lemma 10.2 and Corollary 10.8.
Selected literature; source observations and coverage limits are retained in the publication details.
Contributors
Jan Černý posed the general conjecture. Yinfeng Zhu authored and checked the positive-level proof, reporting interaction with OpenAI Codex / GPT-5.6 Sol in ultra mode. Dubuc supplied the older circular case; Kisielewicz, Kowalski and Szykuła formulated the relative-extension question addressed by the new result.
Authors & roles
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →
Yinfeng Zhu
Zhu reports obtaining the proof through interaction with OpenAI Codex using GPT-5.6 Sol in ultra mode and verifying the argument himself.
These are source credits; they do not imply OpenMath accounts, endorsements or independent mathematical review.
Record details
- Record version
- 4
- Classification
- MSC2020 68Q45 / 20M35
- Prerequisite level
- undergraduate
Independent mathematical review is pending. External certificates and manuscript proofs are attributed to their sources.
Source observations & version history →