Statement For each integer n ≥ 4 there is a strongly connected binary synchronizing one-cluster automaton F_n with m = 2, ℓ = n−2 and reset threshold 3 n − 5 = ( m − 1 ) ( n − 1 ) + m ℓ 3n-5=(m-1)(n-1)+m\ell 3 n − 5 = ( m − 1 ) ( n − 1 ) + m ℓ
⧉ Copy as text Assumptions The example is sharp for the parameter-dependent theorem. It does not establish (n−1)² as the threshold for all n in this family.
Explanation In Černý synchronization conjecture · publication v3
Constructions · 1 A four-state member of the sharp family
Letter a 0 → 1; 1 → 0; 2 → 1; 3 → 2
Letter b 0 → 1; 1 → 2; 2 → 3; 3 → 1
Parameters n = 4, m = 2, ℓ = 2; parameter bound 7 versus conjectural bound 9
Reset word a²b³a² = aabbbaa; length 7
Images after each letter {0,1,2,3} → {0,1,2} → {0,1} → {1,2} → {2,3} → {1,3} → {0,2} → {1} This is the n = 4 member of Definition 10.1. Its finite trace explains synchronization; the all-n optimality theorem needs the separate lower-bound argument.
A family attaining the parameter-dependent bound → Bounds & computations · 1 Compare the quantity and hypotheses within each group. A finite check, conditional theorem and proposed improvement cover different scopes.
In Černý synchronization conjecture · publication v4
Constructions · 1 A four-state member of the sharp family
Letter a 0 → 1; 1 → 0; 2 → 1; 3 → 2
Letter b 0 → 1; 1 → 2; 2 → 3; 3 → 1
Parameters n = 4, m = 2, ℓ = 2; parameter bound 7 versus conjectural bound 9
Reset word a²b³a² = aabbbaa; length 7
Images after each letter {0,1,2,3} → {0,1,2} → {0,1} → {1,2} → {2,3} → {1,3} → {0,2} → {1} This is the n = 4 member of Definition 10.1. Its finite trace explains synchronization; the all-n optimality theorem needs the separate lower-bound argument.
A family attaining the parameter-dependent bound → Bounds & computations · 1 Compare the quantity and hypotheses within each group. A finite check, conditional theorem and proposed improvement cover different scopes.
Connections In this problem · publication v3 · Selected context
Related result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v4
Related result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
History Statement versions Version 1 · Current · Viewing Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1 Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
For every n ≥ 4, rt(F_n) = 3n−5.
Source dated Jul 22, 2026 · Observed Oct 14, 2026 · Source passage →
Record details
Claim ID claim-cerny-one-cluster-sharp-family
Statement version 1
SHA-256 d61d77f67b0983aaf46c04dd8b56e77764977acf401f515c840f238626ba0362 Publication records