op_1670_opposite_cerny_product_two_three_is_synchronizing
The binary word [false, true, true, false] synchronizes 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.
Statement
theorem op_1670_opposite_cerny_product_two_three_is_synchronizing :
dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) [false, true, true, false]- Source
- arXiv:2611.09136, Shortest Synchronizing Words on Product Automata
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- Used by 1
- op_1670_opposite_cerny_product_reset_threshold_two_threeThe 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…
Read back from the Lean
The word [false, true, true, false] is a synchronizing word for the product DFA of the 2-state Černý automaton cerny_dfa 2 and the 3-state input-swapped Černý automaton cerny_swap_dfa 3. That is, for all states q₁ and q₂ in Fin 2 × Fin 3, executing the DFA on [false, true, true, false] from q₁ and from q₂ results in the same state.
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 proof unfolds the definition of a synchronizing word to obtain a universal condition over all pairs of states in the product DFA C₂ × C₃^swap. Because the state space is finite (with only 6 states), Lean checks the condition for all pairs by exhaustive computation (`decide`).
To show that the word is synchronizing, it suffices to verify that feeding [false, true, true, false] sends every pair of states in Fin 2 × Fin 3 to the same state.
Unfolding the definition of a synchronizing word (`dfa_is_synchronizing`) reduces the claim to showing that for all states q₁, q₂ in the product automaton, four consecutive transition steps under the symbols false, true, true, false result in the same state.
uses
dfa_is_synchronizingdsimp [dfa_is_synchronizing]The word [false, true, true, false] synchronizes the product automaton. automation
Since the state space Fin 2 × Fin 3 is finite (consisting of 2 × 3 = 6 states), whether all pairs transition to the same state is a finite, decidable condition that Lean verifies by exhaustive computation.
decide
dfa_is_synchronizing- A word w is synchronizing for a DFA if feeding w into any two states leads to the exact same final state.
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 word [false, true, true, false] of length 4 synchronizes C_2 × C_3^swap (OP-1670). -/theorem op_1670_opposite_cerny_product_two_three_is_synchronizing : dfa_is_synchronizing (dfa_prod (cerny_dfa 2) (cerny_swap_dfa 3)) [false, true, true, false] := by dsimp [dfa_is_synchronizing] decide