op_1667_opposite_cerny_product_reset_threshold_two
The reset threshold of the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy C_2^swap is 2.
Statement
theorem op_1667_opposite_cerny_product_reset_threshold_two :
dfa_reset_threshold (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2)) = 2- Source
- folklore
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- cerny_dfaFor an integer n > 0, the Černý automaton C_n is the deterministic finite automaton with state set {0, ..., n-1} over the binary alphabet…
- cerny_swap_dfaFor an integer n > 0, the letter-swapped Černý automaton C_n^swap is the deterministic finite automaton with state set {0, ..., n-1} where…
- dfa_prodThe direct product
dfa_prod A₁ A₂of two deterministic finite automataA₁ : DFA α σ₁andA₂ : DFA α σ₂over alphabetαis the DFA… - dfa_reset_thresholdThe reset threshold
dfa_reset_threshold Aof a deterministic finite automatonA : DFA α σis the infimum inWithTop ℕof the lengths… - dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all… - op_1667_opposite_cerny_product_two_is_synchronizingThe binary word [false, true] of length 2 synchronizes the direct product of the 2-state Černý automaton C_2 and its letter-swapped copy…
Read back from the Lean
The reset threshold (the minimum length of a synchronizing word, as an element of WithTop ℕ) of the synchronous product of the 2-state Černý automaton (cerny_dfa 2) and the 2-state swapped-alphabet Černý automaton (cerny_swap_dfa 2) is equal to 2.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The reset threshold of a finite automaton is defined as the infimum of the lengths of all synchronizing words (taking values in ℕ ∪ {∞}). The proof establishes the exact value 2 by showing matching upper and lower bounds: the word [false, true] of length 2 synchronizes the product automaton, giving an upper bound of 2, while an exhaustive check on all words of length 0 and 1 shows that none can synchronize the automaton, establishing 2 as a lower bound. The threshold equals 2 by antisymmetry of the partial order.
The length 2 belongs to the set of lengths of synchronizing words for M = C_2 × C_2^swap.
Let M be the product automaton C_2 × C_2^swap. By the previously established lemma op_1667_opposite_cerny_product_two_is_synchronizing, the word [false, true] synchronizes M. Since [false, true] has length 2, its length 2 is in the set of lengths of synchronizing words.
uses
op_1667_opposite_cerny_product_two_is_synchronizinglet M := dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2) have hmem : (2 : WithTop ℕ) ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w } := by refine ⟨[false, true], ?_, rfl⟩ exact op_1667_opposite_cerny_product_two_is_synchronizing
Every synchronizing word for M has length at least 2, making 2 a lower bound on the lengths of synchronizing words.
Let w be an arbitrary synchronizing word for M. We prove 2 ≤ |w| by case analysis on the list w: - If w = [], then initial states (0, 0) and (1, 0) remain unchanged and distinct, contradicting synchronization. - If w = [false], evaluating from (0, 0) and (1, 0) leads to distinct states, verified by computation (`decide`). - If w = [true], evaluating from (0, 0) and (0, 1) leads to distinct states, verified by computation (`decide`). - If w contains two or more elements, its length is at least 2 by list simplification. Consequently, every synchronizing word has length at least 2, and lifting this inequality to WithTop ℕ via WithTop.coe_le_coe.mpr gives 2 ≤ x for every length x in the set.
uses
WithTop.coe_le_coe.mprhave hge : ∀ x ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w }, (2 : WithTop ℕ) ≤ x := by rintro - ⟨w, hw, rfl⟩ have hlen : 2 ≤ w.length := by match w with | [] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨1, by omega⟩, ⟨0, by omega⟩) revert h decide | [false] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨1, by omega⟩, ⟨0, by omega⟩) revert h decide | [true] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩) revert h decide | _ :: _ :: _ => simp exact WithTop.coe_le_coe.mpr hlen
The reset threshold of M is 2.
By definition, the reset threshold is the infimum (sInf) of the set of lengths of synchronizing words. Because 2 belongs to this set, the infimum is at most 2 by sInf_le. Because 2 is a lower bound on all elements of the set, 2 is at most the infimum by le_sInf. By antisymmetry of ≤ (le_antisymm), the infimum equals 2.
uses
le_antisymm,sInf_le,le_sInfdsimp [dfa_reset_threshold] exact le_antisymm (sInf_le hmem) (le_sInf hge)
op_1667_opposite_cerny_product_two_is_synchronizing- The word `[false, true]` is a synchronizing word for the product automaton C_2 × C_2^swap.
WithTop.coe_le_coe.mpr- For natural numbers a and b, if a ≤ b, then a ≤ b holds after coercing both to ℕ ∪ {∞} (WithTop ℕ).
le_antisymm- In any partial order, if a ≤ b and b ≤ a, then a = b.
sInf_le- If an element a belongs to a set s, then the infimum of s is less than or equal to a.
le_sInf- If an element a is less than or equal to every element in a set s, then a is less than or equal to the infimum of s.
- The verification that the empty word and single-letter words (`[false]` and `[true]`) fail to synchronize the selected state pairs is performed by Lean's `decide` tactic via finite-state evaluation.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The reset threshold of C_2 x C_2^swap is 2. -/theorem op_1667_opposite_cerny_product_reset_threshold_two : dfa_reset_threshold (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2)) = 2 := by let M := dfa_prod (cerny_dfa 2) (cerny_swap_dfa 2) have hmem : (2 : WithTop ℕ) ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w } := by refine ⟨[false, true], ?_, rfl⟩ exact op_1667_opposite_cerny_product_two_is_synchronizing have hge : ∀ x ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w }, (2 : WithTop ℕ) ≤ x := by rintro - ⟨w, hw, rfl⟩ have hlen : 2 ≤ w.length := by match w with | [] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨1, by omega⟩, ⟨0, by omega⟩) revert h decide | [false] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨1, by omega⟩, ⟨0, by omega⟩) revert h decide | [true] => exfalso have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩) revert h decide | _ :: _ :: _ => simp exact WithTop.coe_le_coe.mpr hlen dsimp [dfa_reset_threshold] exact le_antisymm (sInf_le hmem) (le_sInf hge)