2026/07/22 by Yinfeng Zhu · 1 voice
#cs.FL
We prove the Černý conjecture for synchronizing one-cluster automata. More precisely, let a synchronizing automaton with state set Q, |Q|=n, have a letter a whose functional digraph has a unique cycle C of length m, and let ℓ be the least nonnegative integer for which a^ℓ maps Q onto C. Assume ℓ≥1. For every nonempty proper subset S⊂ C, we prove that there is a word w of length at most n such that wa^ℓ maps more than |S| states of C into S. This proves the positive-level part of a conjecture of Kisielewicz, Kowalski, and Szykuła concerning relative extending words for one-cluster automata. The resulting reset word has length at most (m-1)(n-1)+mℓ≤(n-1)2. For every n≥4, we construct a strongly connected binary example with m=2, ℓ=n-2, and reset threshold 3n-5, so the parameter-dependent bound (m-1)(n-1)+mℓ is sharp. The upper-bound proof uses finite-dimensional linear algebra; the sharpness lower bounds are combinatorial. The proof was obtained through interaction with OpenAI Codex (GPT-5.6 Sol, ultra mode) and verified by the author.