Reset thresholds of media: a witness at every number of states, the six-state example corrected, and the exact maximum at three token pairs
Abstract
A medium in the sense of Eppstein and Falmagne is a deterministic finite automaton whose letters — its tokens — come in mutually reverse pairs and which satisfies three further axioms; equivalently it is the token system of a well-graded family of sets, and its transition graph is a partial cube. Eppstein and Falmagne proved that a medium on n states has a reset word of length at most n-1. Volkov's list of results on the Černý conjecture records the class as one whose Černý function is known and equal to n-1, but flags the lower half of that claim: the bound n-1 "is claimed in [Eppstein&Falmagne:2008], although an example of a medium with reset threshold n-1 is is provided only for n=6." We settle the existence question at every n, and we correct the record about the six-state example. For every n ≥ 1 the path medium — the token automaton of the family of prefixes of an (n-1)-element set — is a medium on n states with reset threshold exactly n-1, by an argument uniform in n. The six-state medium that Eppstein and Falmagne exhibit, the well-graded family of all one- and two-element subsets of a three-element set, has reset threshold 4, not 5: it is not a witness for the lower bound, and Eppstein and Falmagne never claim that it is. They produce it against a different hope, that a reset word of length τ/2 — half the number of tokens — always exists. It is that second quantity that we then measure exactly in the first case where the hope fails. Writing E(d) for the largest reset threshold of a medium with d token pairs (τ = 2d tokens), we prove E(3) = 4: every medium with three token pairs has a reset word of length 4, by exhaustion over all 256 subsets of the three-dimensional cube — hence over all media with three token pairs, modulo the equivalence of Eppstein and Falmagne, which we cite and do not reprove — and the hexagon attains 4. Computations outside the formal development, reported separately and labelled as such, place this in a wider picture: a census of all media on at most 14 states, which reproduces the eight published terms of OEIS A343163 and adds five; the observation that within that range the media attaining n-1 are exactly the tree media; and rt(C₂ₘ) = 2m-2 for the even cycles up to C₂₀, where the excess rt - τ/2 = m-2 therefore reaches 8. Every statement below is machine-checked in Lean 4 except where the text says otherwise.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
e213f982f6848e0b5fec9ffcb7dce3d2d0fe6cc7bbb6e6df291be054752eac80
Claim ledger
Stated results
MR1routine2026-09-03
For every n >= 1 there is a medium (Volkov item C5, all four axioms) on n states whose reset threshold is exactly n-1: the path medium on the prefix family of an (n-1)-element set. General in n, kernel-clean.
MR2correction2026-09-03
CORRECTION: the n = 6 medium of Eppstein-Falmagne (the well-graded family of all 1- and 2-element subsets of a 3-element set) has reset threshold exactly 4, not n-1 = 5; so it is not an example of a medium attaining the lower bound n-1, and the survey's item-C5 sentence does not hold of the example it cites.
MR3routine2026-09-03
The even-cycle media: rt(C₄) = 2 and rt(C₆) = 4 = tau - 2 for the medium of the downward- and upward-closed subsets of an m-element set (m = 2, 3), kernel-checked with the medium axioms.
MR4candidate2026-09-03
The maximum reset threshold over media with three Theta-classes (six tokens) is exactly 4: every well-graded family in the 3-cube that uses all three coordinates has a reset word of length 4 (exhaustive over all 256 subsets of the 3-cube), and the hexagon attains 4.
MR5routine2026-09-03
Negative controls: the path medium on 6 states has reset threshold neither 6 (too large) nor 4 (too small).
MR6known2026-09-03
Control that the medium hypothesis is not vacuous: Cerny's automaton C₃ has reset threshold 4 = (n-1)², twice the bound n-1 = 2 that item C5 gives for media, and it is not a medium – no letter of it has a reverse, so Volkov's first axiom already fails.
MR7candidate2026-09-03
Census of media: the number of media on n states (equivalently, of partial cubes on n vertices, up to isomorphism) is 1, 1, 1, 3, 4, 12, 25, 79, 212, 731, 2427, 9098, 34614, 140326 for n = 1..14 – five terms beyond OEIS A343163.
This ledger entry is reported in prose and is not bound to a Lean theorem.MR8candidate2026-09-03
The maximum reset threshold over media on n states is n-1 for every n <= 14, and it is attained EXACTLY by the tree media (equivalently: rt = n-1 iff every Theta-class is a single edge); the maximum over non-tree media is n-2 for 4 <= n <= 14.
This ledger entry is reported in prose and is not bound to a Lean theorem.MR9candidate2026-09-03
How far the reset threshold of a medium can exceed half its number of tokens: the even cycle C₂m is a medium with tau = 2m tokens and rt(C₂m) = 2m-2 = tau-2 for 2 <= m <= 10, so the gap rt - tau/2 = m-2 is unbounded; and the maximum reset threshold over ALL media with d Theta-classes is exactly 2d-2 for d = 2, 3, 4 (exhaustive over the d-cube).
This ledger entry is reported in prose and is not bound to a Lean theorem.MR10measurement2026-09-03
MEASUREMENT: what the finite checks cost in Lean. Breadth-first search over image sets carried as Finset (Finset (Fin d -> Bool)) is unusable (it does not finish at depth 4 on a 6-state medium); word enumeration is the affordable route and it stops at 6 letters / length 3.
This ledger entry is reported in prose and is not bound to a Lean theorem.MR11known2026-09-03
The general theorem every witness of this family rests on: for every d, the token automaton of a well-graded family of subsets of a d-element set in which every coordinate is used satisfies all four of Volkov's medium axioms C5(i)-(iv) – so every well-graded family is a medium, uniformly in d and kernel-clean (WGFamily.isMedium). This is the hypothesis-discharging step of MR1-MR4 and of the E(3) = 4 exhaustion, and is Proposition 2.3 of the v1 paper.
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Source. Mikhail V. Volkov, *List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata*, arXiv:2508.15655 v4 (13 January 2026, cs.FL), item C5†. Media; and the paper it cites for both bounds, David Eppstein and Jean-Claude Falmagne, *Algorithms for Media*, Discrete Appl. Math. 156(8):1308–1320, 2008, preprint arXiv:cs/0206033.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7