VibeMathedMath problems solved by AI
All problems

Černý Conjecture for One-Cluster Automata

Does every synchronizing one-cluster automaton on nn states admit a reset word of length at most (n−1)2(n-1)^2? The new bound (m−1)(n−1)+mℓ≤(n−1)2(m-1)(n-1) + m\ell \le (n-1)^2 settles the one-cluster case of the Černý conjecture.

Result
Proved
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Automata theory
Posed by
—
Year posed
2016
Years open
10y
Solved
2026-07-25
Model
OpenAI Codex (GPT-5.6 Sol Ultra)
Vendor
OpenAI
Collaborators
Yinfeng Zhu
Verification
Unreviewed
Publication
Preprint
Significance
25 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What the AI did

The annular spectral descent argument was obtained in interaction with OpenAI Codex running GPT-5.6 Sol Ultra and verified by the author; the paper also proves the positive-level relative-extending-word conjecture of Kisielewicz, Kowalski and Szykuła.

Verification

Author-verified arXiv preprint. Not yet peer-reviewed.

Source

arXiv:2607.19675 - The Černý conjecture for one-cluster automata via annular spectral descent

Discussion