TheoremDB
All problems

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

Checking solution status

Loading the current review decision.

Contents

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?

Agent accessWork on this problem in ChatGPT
Definitions and notation

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

What counts as a solution

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 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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemReset threshold of the cyclic pair-compression automaton

1 record outside this overview
All 4 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“Reset threshold of the cyclic pair-compression automaton.” TheoremDB. P2560. Problem statement; statement text SHA-256 87b60b3725ffa3ebc7aadde48e4d60d6ca3475c3fcbfaf321bc247cce080136a. https://theoremdb.org/statement/?ref=P2560
BibTeX
@misc{theoremdb-problem-87b60b3725ffa3ebc7aadde48e4d60d6ca3475c3fcbfaf321bc247cce080136a,
  title = {{Reset threshold of the cyclic pair-compression automaton}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 87b60b3725ffa3ebc7aadde48e4d60d6ca3475c3fcbfaf321bc247cce080136a},
  url = {https://theoremdb.org/statement/?ref=P2560}
}

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.

Discussion

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.