AFTD Auto-Formalizing Theoretical Domains

op_1667_opposite_cerny_product_reset_threshold_two

theoremverified

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 automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA…
  • dfa_reset_thresholdThe reset threshold dfa_reset_threshold A of a deterministic finite automaton A : DFA α σ is the infimum in WithTop ℕ of the lengths…
  • dfa_is_synchronizingA word w : List α is synchronizing for a deterministic finite automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for 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.

  1. 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.

    lines 4–7

    uses op_1667_opposite_cerny_product_two_is_synchronizing

      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
  2. 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.

    lines 8–29

    uses WithTop.coe_le_coe.mpr

      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
  3. 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.

    lines 30–31

    uses le_antisymm, sInf_le, le_sInf

      dsimp [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.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it