What was already known
Glushkov posed the diameter problem in 1968. Earlier work established quadratic bounds and the leading term . Chervov and collaborators conjectured the exact even and odd formulas and reported exhaustive computations through .
AI involvement
The authors report that their agent workflow produced the proof chiefly with GPT-6 Astra, including through OpenAI Codex. The authors mainly coordinated the workflow and made minor edits. They used Claude Opus 5.5 for limited checking and editing.
- Uskov and coauthors’ paper and AI disclosureProvenance statement and paper section 1.2
Importance
The theorem resolves the exact diameter conjecture for these two generators. It determines both the worst-case number of moves and its dependence on parity, beyond the previously known leading term.
Technical verification
The pinned Lean 4 release reports a successful build, an axiom audit, and Comparator checks against a separately stated all-pairs diameter theorem and bounded-routing theorem. The formal statements use literal unit-cost L and X moves and cover every . The release reports only standard Lean axioms.
Formal checking
The pinned Lean 4 release reports a successful build, an axiom audit, and Comparator checks against a separately stated all-pairs diameter theorem and bounded-routing theorem. The formal statements use literal unit-cost L and X moves and cover every . The release reports only standard Lean axioms.
- Checker
- Lean 4 kernel and Comparator, reported by the authors
- Scope
- Exact all-pairs directed diameter and sharp route bound for with literal L and X moves
- Basis
- Reported by the linked checker
- Lean 4 release and verification resultsRelease verification and exactDiameter statement
Human understanding
The authors explain the move model and their workflow. They report understanding some parts of the work and say they have yet to understand the proof in detail. The paper’s detailed proof exposition is model-generated.
Correction and publication history
Newly source-reviewed proof of the exact directed diameter, with documented central AI work and a checked Lean release.
Read this published revision