# P2560: Reset threshold of the cyclic pair-compression automaton

- ID: `P2560`
- Reference: `cyclic-pair-compression-reset-threshold`
- Page: https://theoremdb.org/statements/P2560
- Record maturity: Reviewed problem with recorded work

## 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?

### Definitions

- **Definition.** A reset word maps every state to one state.
- **Definition.** The reset threshold is the minimum reset-word length.

### What counts as a solution

- Prove the stated classification and exact threshold, or provide a contrary n with a certified shortest reset word or invariant.

## Status

Exact search proves the formula through n=19; a general matching lower bound remains open in this record. [1](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (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.

The construction in cpcrt-claim-odd-reset-upper-bound proves \(\operatorname{rt}(A_n)\leq n(n-1)/2\) for every odd \(n\). A general fiber argument gives the rigorous lower bound \(\operatorname{rt}(A_n)\geq\lceil\log_2 n\rceil\): the letter \(a\) is a permutation, every fiber of \(b\) has size at most two, and a word containing \(k\) copies of \(b\) has fibers of size at most \(2^k\). A reset word has a fiber of size \(n\). Exact breadth-first search gives equality with the quadratic upper bound at every odd \(n\leq19\). Separately weighted searches find that every reset word in this tested range uses at least \(n-1\) copies of \(b\) and at least \((n-1)(n-2)/2\) copies of \(a\). These two sharper inequalities would prove the formula in general, but this record does not supply a universal proof of them.

### Background and intake notes

The claim couples a structural parity obstruction with an exact word-length formula, so subset states and failed potentials can be stored canonically.

- Original intake status: Status unknown. No literature search was performed; cyclic automata with idempotent letters have a substantial literature.
- For even n, antipodal or parity-based pair invariants are the natural route to a nonsynchronization proof.
- For odd n, each use of b compresses alternating pairs, yet rotations needed to expose the next pair create the quadratic cost. A rank-potential lower bound must account for those rotations.

- Recorded example: For n=5 a shortest reset word has length 10. For n=7 the threshold is 21.

### Other known results

- **Computation 2** (reproduced): For odd n, an explicit word of length n(n-1)/2 synchronizes the automaton. [1](#reference-1)
- **Computation 3** (reproduced): The states 0 and 2 remain two steps apart under every word, so they can never merge. [1](#reference-1)

### Prior approaches

- **Route 1** (inconclusive): The exact two-letter family was not located; surveys place it near one-cluster automata and automata with low-rank idempotent letters. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Breadth-first search proves all thresholds through 19 and two zero-one searches recover the separate minimum counts of a and b. [1](#reference-1)

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

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `cyclic-pair-compression-reset-threshold`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Mikhail V. Volkov, “Synchronization of finite automata,” Russian Mathematical Surveys 77(5) (2022), 819-891. DOI 10.4213/rm10005e. survey sections on synchronization, reset thresholds, and the Černý conjecture https://doi.org/10.4213/rm10005e
   - 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 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
   - Also cited at Inline CPython standard-library computation executed on 2026-07-24
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - 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.