AFTD Auto-Formalizing Theoretical Domains

op_1670_opposite_cerny_product_reset_threshold_two_three

theoremverified

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 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…
  • 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 automaton A : DFA α σ if A.evalFrom q₁ w = A.evalFrom q₂ w for 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.

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

    lines 4–7

    uses op_1670_opposite_cerny_product_two_three_is_synchronizing

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

    lines 8–44

    uses WithTop.coe_le_coe.mpr

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

    lines 45–46

    uses le_antisymm, sInf_le, le_sInf

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

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