op_1670_opposite_cerny_product_reset_threshold_two_three
The reset threshold of the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý automaton and the 3-state letter-swapped Černý automaton is 4.
Statement
theorem op_1670_opposite_cerny_product_reset_threshold_two_three :
dfa_reset_threshold (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) = 4- Source
- arXiv:2611.09136, Shortest Synchronizing Words on Product Automata
- 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… - op_1670_opposite_cerny_product_two_three_is_synchronizingThe binary word [false, true, true, false] synchronizes the direct product dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) of the 2-state Černý…
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
Read back from the Lean
The reset threshold (the infimum in WithTop ℕ of the lengths of all synchronizing words) of the product DFA formed by the 2-state Černý automaton cerny_dfa 2 and the 3-state input-swapped Černý automaton cerny_swap_dfa 3 is equal to 4.
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 the product automaton C₂ × C₃^swap is shown to be 4 by finding the infimum of the lengths of its synchronizing words. For the upper bound, the explicit word `[false, true, true, false]` of length 4 is verified to be synchronizing. For the lower bound, an exhaustive check of all 15 words of length at most 3 shows that none can synchronize the automaton, refuting them against either the state pair ((0,0), (0,1)) or ((0,0), (0,2)). Combining the upper and lower bounds by order antisymmetry establishes that the reset threshold is exactly 4.
The value 4 belongs to the set of lengths of synchronizing words for M = C₂ × C₃^swap.
Let M be the product DFA of the 2-state Černý automaton and the 3-state letter-swapped Černý automaton. Lemma `op_1670_opposite_cerny_product_two_three_is_synchronizing` shows that the concrete word `[false, true, true, false]` synchronizes M. Since this word has length 4, 4 is an element of the image of the synchronizing words under the length function.
uses
op_1670_opposite_cerny_product_two_three_is_synchronizinglet M := dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) have hmem : (4 : WithTop ℕ) ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w } := by refine ⟨[false, true, true, false], ?_, rfl⟩ exact op_1670_opposite_cerny_product_two_three_is_synchronizing
Every synchronizing word for M has length at least 4.
Given an arbitrary synchronizing word w, we show 4 ≤ w.length by pattern matching over all words of length strictly less than 4. There are 15 such words in total (1 of length 0, 2 of length 1, 4 of length 2, and 8 of length 3). For 14 of these words, evaluating the DFA execution from the two initial states ((0,0), (0,1)) results in distinct final states; for the word `[true, true, false]`, evaluating from ((0,0), (0,2)) similarly produces distinct final states. Each of these non-synchronizing behaviors is refuted by finite evaluation via `decide`. Any word not matching these cases contains at least 4 symbols, so its length is at least 4. Finally, `WithTop.coe_le_coe.mpr` lifts this inequality into `WithTop ℕ`.
uses
WithTop.coe_le_coe.mprhave hge : ∀ x ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w }, (4 : WithTop ℕ) ≤ x := by rintro - ⟨w, hw, rfl⟩ have hlen : 4 ≤ w.length := by match w with | [] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, 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 | [false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨2, by omega⟩); revert h; decide | [true, true, 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 4.
Unfolding the definition of reset threshold as the infimum of the lengths of all synchronizing words, the result follows by antisymmetry: the infimum is at most 4 because 4 is in the set (`sInf_le`), and at least 4 because 4 is a lower bound on the entire set (`le_sInf`).
uses
le_antisymm,sInf_le,le_sInfdsimp [dfa_reset_threshold] exact le_antisymm (sInf_le hmem) (le_sInf hge)
op_1670_opposite_cerny_product_two_three_is_synchronizing- The word `[false, true, true, false]` is a synchronizing word for the product automaton `dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)`.
WithTop.coe_le_coe.mpr- For natural numbers a and b, if a ≤ b then the coerced values in `WithTop ℕ` satisfy a ≤ b.
le_antisymm- In a 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 sInf s is at most a.
le_sInf- If an element a is a lower bound for every element of a set s, then a is at most sInf s.
- Evaluation of the DFA transitions on all 15 candidate words of length at most 3 is performed purely by computation using the kernel decision procedure (`decide`).
- The reset threshold is defined over `WithTop ℕ` (i.e. ℕ ∪ {∞}) to allow for the case where an automaton has no synchronizing word, necessitating the use of `WithTop.coe_le_coe.mpr` to lift the natural inequality to the extended naturals.
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 × C_3^swap is 4 (OP-1670). -/theorem op_1670_opposite_cerny_product_reset_threshold_two_three : dfa_reset_threshold (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) = 4 := by let M := dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3) have hmem : (4 : WithTop ℕ) ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w } := by refine ⟨[false, true, true, false], ?_, rfl⟩ exact op_1670_opposite_cerny_product_two_three_is_synchronizing have hge : ∀ x ∈ (fun w : List Bool => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing M w }, (4 : WithTop ℕ) ≤ x := by rintro - ⟨w, hw, rfl⟩ have hlen : 4 ≤ w.length := by match w with | [] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, 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 | [false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [false, true, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, false, true] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨1, by omega⟩); revert h; decide | [true, true, false] => exfalso; have h := hw (⟨0, by omega⟩, ⟨0, by omega⟩) (⟨0, by omega⟩, ⟨2, by omega⟩); revert h; decide | [true, true, 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)