TheoremDB
All problems

[#P2560] Reset threshold of the cyclic pair-compression automaton

Work on this problem in ChatGPT
A neutral state and word schematic for Reset threshold of the cyclic pair-compression automaton.A code-rendered placeholder showing only the mathematical setup.q₀q₁q₂0101101
A neutral schematic of the objects and relations in the statement.

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

5 records

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow
How the records connect to the problem

ProblemReset threshold of the cyclic pair-compression automaton

1 record with no typed link to the problem

2See also

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-threshold

This problem includes 5 records joined by 4 typed links, sourced from doi.org[1], current as of July 24, 2026.

1References

  1. 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.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.