Černý’s examples meet the bound

Statement

For every n ≥ 2 there is a synchronizing deterministic finite automaton on n states whose reset threshold is exactly (n−1)².

Complete deterministic automata; reset threshold is the length of a shortest reset word.

Shows the conjectured bound (n−1)² cannot be lowered; it says nothing about whether every automaton meets it.

Proved

Only the exact statement and passage cited here; not an independent OpenMath assessment.

Observed Oct 21, 2026

In this problem · publication v4 · Selected context

§1, first paragraph; reference [5], Lemma 1 → · Original passage ↗
Recorded wording
The Černý conjecture asserts that every synchronizing automaton with n states has reset threshold at most (n−1)²; the classical examples of Černý (1964) show that this number would be best possible.
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.

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.

Proved

Only the exact statement and passage cited here; not an independent OpenMath assessment.

Observed Oct 21, 2026 · Source passage →

Record details