AI Proof WatchKeep up with AI contributions

Černý reset bounds for positive-level one-cluster automata

For synchronizing one-cluster automata of positive level, prove the relative extending-word property and a reset word of length at most (m−1)(n−1)+mℓ≤(n−1)². The refined binary target is 3n−5 with attaining examples.

Why it matters and what counts as progress

Why it matters: It tests the Černý quadratic reset bound on a substantial structured automata class, with stronger class-specific bounds and sharpness.

What counts as progress: Prove the Černý reset bound for the full positive-level one-cluster class and establish sharpness of any stronger class-specific bound.

How the problem developed

  1. 22 Jul 2026 · Reported theorem [1]

    Yinfeng Zhu, with OpenAI Codex (GPT-5.6 Sol) Claimed the Černý bound for positive-level synchronizing one-cluster automata, with reset length at most (m−1)(n−1)+mℓ ≤ (n−1)²; the author says the proof was verified by him.

AI contribution

Sources

  1. Zhu, The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent
  2. Zhu, Černý Conjecture for One-Cluster Automata
Website timeline

Publication dates and editorial changes.