Open
General Černý conjecture remains open ↗
All complete synchronizing deterministic finite automata.
Source dated Jul 22, 2026 · Observed Oct 14, 2026
Conjecture · version 1
The general quadratic reset-word conjecture
Statement
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)²
Evidence
Source reports
Connections
In this problem · publication v1 · Selected context
Černý synchronization conjecture →
Primary formulation · Open
Related statements
The positive-level one-cluster theorem reaches the conjectured bound within its restricted class.
It does not settle automata with no one-cluster letter.
Details & sources
The general quadratic reset-word conjecture →
Open · version 1
Every complete synchronizing deterministic finite automaton on n ≥ 2 states has a reset word of length at most .
- No one-cluster or positive-level assumption is imposed on the general conjecture.
Scope: No one-cluster or positive-level assumption is imposed on the general conjecture.
The bound for positive-level one-cluster automata →
Proved · version 1
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 .
- The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
Scope: The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
Relationship not independently reviewed.
Connection in Černý synchronization conjecture →Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v4
Černý synchronization conjecture →
Primary formulation · Open
Related statements
The positive-level one-cluster theorem reaches the conjectured bound within its restricted class.
It does not settle automata with no one-cluster letter.
Details & sources
The general quadratic reset-word conjecture →
Open · version 1
Every complete synchronizing deterministic finite automaton on n ≥ 2 states has a reset word of length at most .
- No one-cluster or positive-level assumption is imposed on the general conjecture.
Scope: No one-cluster or positive-level assumption is imposed on the general conjecture.
The bound for positive-level one-cluster automata →
Proved · version 1
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 .
- The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
Scope: The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
Relationship not independently reviewed.
Connection in Černý synchronization conjecture →Relationship not independently reviewed. This concerns its use in this problem.
Sources
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent →
- Introduction; definitions of synchronization and one-cluster level → · Original passage ↗
Recorded wording
The general quadratic conjecture is distinct from a result for a letter whose functional graph has exactly one cycle. Level is the least power mapping the state set onto that cycle.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
- Main theorem and relative-extending-word result → · Original passage ↗
Recorded wording
For a synchronizing one-cluster automaton with n states, cycle length m and least level ℓ ≥ 1, the source proves the bound (m−1)(n−1)+mℓ ≤ (n−1)² and the stated relative-extension property.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
Yinfeng Zhu · Preprint · Publication date Jul 22, 2026
Source-reported results and external checks are separate from independent OpenMath assessment.
Revision & attribution
Source revision: v1. Observed Oct 14, 2026.
Zhu reports obtaining the proof through interaction with OpenAI Codex using GPT-5.6 Sol in ultra mode and verifying the argument himself.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Open
General Černý conjecture remains open ↗
All complete synchronizing deterministic finite automata.
Source dated Jul 22, 2026 · Observed Oct 14, 2026 · Source passage →
Record details
- Claim ID
- claim-cerny-quadratic-bound
- Statement version
- 1
- SHA-256
- 8b1b756ad839fcbadb8915335eb82d75d3abc816c9e1a95f430cd05ea02e60b7