[#P2560] Reset threshold of the cyclic pair-compression automaton
Problem. For \(n\ge 3\), define a binary automaton \(A_n\) on states \(\{0,\ldots,n-1\}\) by \(a(i)=i+1\pmod n\), while \(b(i)=i\) for even \(i\) and \(b(i)=i-1\) for odd \(i\). Is \(A_n\) synchronizing exactly when \(n\) is odd, with reset threshold \(n(n-1)/2\) in every odd case?
1Context
The claim couples a structural parity obstruction with an exact word-length formula, so subset states and failed potentials can be stored canonically.
2Definitions
Definition 1. A reset word maps every state to one state.
Definition 2. The reset threshold is the minimum reset-word length.
3What counts as a solution
- Prove the stated classification and exact threshold, or provide a contrary n with a certified shortest reset word or invariant.
1Status
Current status (The candidate odd threshold is n(n-1)/2). Exact search proves the formula through n=19; a general matching lower bound remains open in this record.[1]
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-24. For odd n, an explicit word of length n(n-1)/2 synchronizes the automaton. The checked sources do not settle the full acceptance condition.
- The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
- The strongest recorded neighboring result is: For odd n, an explicit word of length n(n-1)/2 synchronizes the automaton.
- The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. For n=5 a shortest reset word has length 10. For n=7 the threshold is 21.
Computational notes
- Exact breadth-first search of the power automaton was run for every 3 <= n <= 16. Even n had no reachable singleton. Odd thresholds were 3,10,21,36,55,78,105 for n=3,5,7,9,11,13,15, agreeing with n(n-1)/2.
How the 5 records connect
ProblemReset threshold of the cyclic pair-compression automaton
- Computation 1The candidate odd threshold is n(n-1)/2in this packetReproduced
- Computation 2Every odd order has a quadratic reset wordsupportsReproduced
- Artifact 1Exact subset-automaton sweep and weighted lower checkstestsReproduced
- Route 1Focused literature search found neighboring classesinformsInconclusive
1 record with no typed link to the problem
2See also
- Logarithmic DFA separation of binary wordsautomata theory
- Polynomial determinization of two-way finite automataautomata theory
- Least uniform modulus of an abelian-square-free morphism on four lettersformal languages
How to cite
TheoremDB contributors, “Reset threshold of the cyclic pair-compression automaton,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/cyclic-pair-compression-reset-thresholdThis page as plain text: cyclic-pair-compression-reset-threshold.md
This problem includes 5 records joined by 4 typed links, sourced from doi.org[1], current as of July 24, 2026.
1References
- Packet source. Mikhail V. Volkov, “Synchronization of finite automata,” Russian Mathematical Surveys 77(5) (2022), 819-891. DOI 10.4213/rm10005e. Mikhail V. Volkov, Synchronization of finite automata, Russian Mathematical Surveys 77:5 (2022), 819-891; Mikhail V. Volkov, Slowly synchronizing automata with idempotent letters of low rank, arXiv:1807.07048 and International Journal of Foundations of Computer Science 30 (2019), 1043-1063. ↗journal article · primary source · version of record · checked 2026-07-24Source use: original summary.Focused literature search found neighboring classes. The exact two-letter family was not located; surveys place it near one-cluster automata and automata with low-rank idempotent letters.Also cited at survey sections on synchronization, reset thresholds, and the Černý conjecture.Also cited at Exact subset-automaton checks through n=19 in cpcrt-artifact-exact-sweep; general upper bound and fiber lower bound proved in this record.Also cited at Direct active-set calculation in this record; construction checked through odd n=101 in cpcrt-artifact-exact-sweep.Also cited at Elementary two-state invariant proved in this record.Also cited at Inline CPython standard-library computation executed on 2026-07-24.For Reset threshold of the cyclic pair-compression automaton, this source supplies the neighboring synchronizing-automata bounds and does not settle the packet's cyclic pair-compression target.Source named by the research packet.
Original automaton family whose parity split and quadratic threshold were found computationally.