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 Qaℓ=C, then its reset threshold is at most (m−1)(n−1)+mℓ≤(n−1)2.
Assumptions
The automaton must be synchronizing; ℓ is the least level, not an arbitrary positive exponent. Other letters may act differently.
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.
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 Qaℓ=C, then its reset threshold is at most (m−1)(n−1)+mℓ≤(n−1)2.
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.
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.
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.
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.