AFTD Auto-Formalizing Theoretical Domains

op_1293_product_reset_threshold_lower_bound_attained

theoremverifiedformalization

For every nonempty finite alphabet α and positive integers k₁, k₂, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ with dfa_reset_threshold A₁ = k₁ and dfa_reset_threshold A₂ = k₂ such that the reset threshold of their direct product attains the lower bound max k₁ k₂.

Statement

theorem op_1293_product_reset_threshold_lower_bound_attained (α : Type*) [Fintype α] [Nonempty α] (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) : ∃ (σ₁ σ₂ : Type) (_ : Fintype σ₁) (_ : Fintype σ₂) (A₁ : DFA α σ₁) (A₂ : DFA α σ₂), dfa_is_synchronizable A₁ ∧ dfa_is_synchronizable A₂ ∧ dfa_reset_threshold A₁ = ↑k₁ ∧ dfa_reset_threshold A₂ = ↑k₂ ∧ dfa_reset_threshold (dfa_prod A₁ A₂) = ↑(max k₁ k₂)
Formalizes
arXiv:2611.09136 Example 3.6, Proposition 3.4
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • dfa_is_synchronizableA deterministic finite automaton A : DFA α σ is synchronizable if there exists a synchronizing word w : List α for A.
  • 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_prodThe direct product dfa_prod A₁ A₂ of two deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ over alphabet α is the DFA…
  • 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…
Used by 3

Read back from the Lean

For every finite, nonempty type α (alphabet) and all natural numbers k₁, k₂ with 1 ≤ k₁ and 1 ≤ k₂, there exist types σ₁ and σ₂ (each with a Fintype instance) and DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ such that: 1. A₁ is synchronizable, 2. A₂ is synchronizable, 3. the reset threshold of A₁ equals k₁ (as an element of WithTop ℕ), 4. the reset threshold of A₂ equals k₂ (as an element of WithTop ℕ), and 5. the reset threshold of the product automaton dfa_prod A₁ A₂ equals max k₁ k₂ (as an element of WithTop ℕ).

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

To show that the reset threshold of the direct product of two DFAs can attain the lower bound max(k₁, k₂), we construct for each integer k ≥ 1 a chain DFA on {0, …, k} whose transitions advance states towards the absorbing sink k. A word synchronizes this DFA if and only if its length is at least k, so its reset threshold is exactly k. Because a word synchronizes the direct product of two DFAs if and only if it synchronizes both factor DFAs simultaneously, synchronizing the product of the two chain DFAs requires length at least max(k₁, k₂). Hence the product reset threshold is exactly max(k₁, k₂), showing that the lower bound is attained.

  1. The chain DFA of parameter k is well-defined with transitions min(q + 1, k) on Fin(k + 1).

    For any state q ∈ {0, …, k} and input symbol, the transition advances the state to min(q.val + 1, k). This state is valid because min(q.val + 1, k) ≤ k < k + 1, which Lean establishes via Nat.lt_succ_of_le and Nat.min_le_right.

    lines 1–7

    uses Nat.lt_succ_of_le, Nat.min_le_right

    def op_1293_chainDFA (α : Type*) (k : ℕ) : DFA α (Fin (k + 1)) where
      step q _ := ⟨min (q.val + 1) k, by
        apply Nat.lt_succ_of_le
        exact Nat.min_le_right _ _⟩
      start := 0
      accept := ∅
    
  2. Evaluating the chain DFA from state q on word w reaches state min(q + |w|, k).

    We proceed by induction on w from the right using List.reverseRecOn. For the empty word, the automaton stays at q, and min(q + 0, k) = q since q ≤ k. For w ++ [a], the prefix w brings the automaton to min(q + |w|, k) by the induction hypothesis; taking one step on symbol a yields min(min(q + |w|, k) + 1, k) by DFA.evalFrom_append_singleton and op_1293_chainDFA_step_val, which linear integer arithmetic (omega) simplifies to min(q + (|w| + 1), k).

    lines 11–19

    uses List.reverseRecOn, DFA.evalFrom_nil, List.length_nil, add_zero, DFA.evalFrom_append_singleton, op_1293_chainDFA_step_val, List.length_append, List.length_singleton

    lemma op_1293_chainDFA_evalFrom_val (α : Type*) (k : ℕ) (q : Fin (k + 1)) (w : List α) :
        ((op_1293_chainDFA α k).evalFrom q w).val = min (q.val + w.length) k := by
      induction' w using List.reverseRecOn with w a ih
      · simp only [DFA.evalFrom_nil, List.length_nil, add_zero]
        omega
      · rw [DFA.evalFrom_append_singleton, op_1293_chainDFA_step_val, ih]
        simp only [List.length_append, List.length_singleton]
        omega
    
  3. A word w synchronizes the chain DFA if and only if |w| ≥ k.

    For the forward implication, if w synchronizes the DFA, evaluating w from state 0 and from state k must reach identical states. Projecting to natural values via Fin.val and rewriting with op_1293_chainDFA_evalFrom_val gives min(|w|, k) = min(k + |w|, k) = k, which implies |w| ≥ k. For the reverse implication, if |w| ≥ k, then for every pair of states q₁, q₂, min(q₁ + |w|, k) = k = min(q₂ + |w|, k), so both evaluations reach state k, which proves equality via Fin.ext.

    lines 20–33

    uses Fin.val, op_1293_chainDFA_evalFrom_val, Fin.ext

    lemma op_1293_chainDFA_is_synchronizing_iff (α : Type*) {k : ℕ} (hk : 1 ≤ k) (w : List α) :
        dfa_is_synchronizing (op_1293_chainDFA α k) w ↔ k ≤ w.length := by
      constructor
      · intro h
        have hq := h ⟨0, by omega⟩ ⟨k, by omega⟩
        apply_fun Fin.val at hq
        rw [op_1293_chainDFA_evalFrom_val, op_1293_chainDFA_evalFrom_val] at hq
        dsimp only at hq
        omega
      · intro h q₁ q₂
        apply Fin.ext
        rw [op_1293_chainDFA_evalFrom_val, op_1293_chainDFA_evalFrom_val]
        omega
    
  4. The reset threshold of the chain DFA of size k is k.

    The reset threshold is the infimum of the lengths of all synchronizing words. We show equality using le_antisymm. For the upper bound, pick any symbol x ∈ α; the word consisting of x repeated k times has length k and is synchronizing by op_1293_chainDFA_is_synchronizing_iff, so k is in the set of synchronizing lengths and inf ≤ k by sInf_le. For the lower bound, any synchronizing word w has |w| ≥ k, meaning k is a lower bound for every element of the set, so k ≤ inf by le_sInf and WithTop.coe_le_coe.mpr.

    lines 34–50

    uses le_antisymm, op_1293_chainDFA_is_synchronizing_iff, sInf_le, le_sInf, WithTop.coe_le_coe.mpr

    lemma op_1293_chainDFA_reset_threshold (α : Type*) [Nonempty α] (k : ℕ) (hk : 1 ≤ k) :
        dfa_reset_threshold (op_1293_chainDFA α k) = ↑k := by
      unfold dfa_reset_threshold
      apply le_antisymm
      · obtain ⟨x⟩ := (inferInstance : Nonempty α)
        have hw : dfa_is_synchronizing (op_1293_chainDFA α k) (List.replicate k x) := by
          rw [op_1293_chainDFA_is_synchronizing_iff α hk]
          simp
        have hmem : (k : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing (op_1293_chainDFA α k) w } := by
          exact ⟨List.replicate k x, hw, by simp⟩
        exact sInf_le hmem
      · apply le_sInf
        rintro _ ⟨w, hw, rfl⟩
        have : dfa_is_synchronizing (op_1293_chainDFA α k) w := hw
        rw [op_1293_chainDFA_is_synchronizing_iff α hk] at this
        exact WithTop.coe_le_coe.mpr this
    
  5. Evaluating the direct product DFA decomposes into componentwise evaluation.

    By induction on w from the right using List.reverseRecOn, evaluating the product DFA from (q₁, q₂) on w gives (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w). The base case of the empty list is immediate by DFA.evalFrom_nil, and the inductive step follows by rewriting with DFA.evalFrom_append_singleton on each component.

    lines 51–58

    uses List.reverseRecOn, DFA.evalFrom_nil, DFA.evalFrom_append_singleton

    lemma op_1293_dfa_prod_evalFrom {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂)
        (q₁ : σ₁) (q₂ : σ₂) (w : List α) :
        (dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) := by
      induction' w using List.reverseRecOn with w a ih
      · simp [DFA.evalFrom_nil]
      · rw [DFA.evalFrom_append_singleton, DFA.evalFrom_append_singleton, DFA.evalFrom_append_singleton, ih]
        rfl
    
  6. A word synchronizes the direct product DFA if and only if it synchronizes both component DFAs.

    If w synchronizes the product, fix witness states s₁ and s₂ in the nonempty state types. Evaluating the product on (q₁, s₂) and (q₂, s₂) produces equal outputs; extracting the first component via Prod.ext_iff.mp shows that A₁ is synchronized. Symmetrically, pairing with s₁ on the left shows that A₂ is synchronized. Conversely, if w synchronizes both A₁ and A₂, then for any two state pairs (p₁, p₂) and (q₁, q₂), the component evaluations agree, so the product evaluations are equal by Prod.ext.

    lines 59–78

    uses op_1293_dfa_prod_evalFrom, Prod.ext_iff.mp, Prod.ext

    lemma op_1293_dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} [Nonempty σ₁] [Nonempty σ₂]
        (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) :
        dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := by
      constructor
      · intro h
        obtain ⟨s₁⟩ := (inferInstance : Nonempty σ₁)
        obtain ⟨s₂⟩ := (inferInstance : Nonempty σ₂)
        constructor
        · intro q₁ q₂
          have := h (q₁, s₂) (q₂, s₂)
          rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom] at this
          exact (Prod.ext_iff.mp this).1
        · intro q₁ q₂
          have := h (s₁, q₁) (s₁, q₂)
          rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom] at this
          exact (Prod.ext_iff.mp this).2
      · rintro ⟨h₁, h₂⟩ ⟨p₁, p₂⟩ ⟨q₁, q₂⟩
        rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom]
        exact Prod.ext (h₁ p₁ q₁) (h₂ p₂ q₂)
    
  7. The reset threshold of the direct product of two chain DFAs of sizes k₁ and k₂ is max k₁ k₂.

    By op_1293_dfa_prod_is_synchronizing_iff and op_1293_chainDFA_is_synchronizing_iff, a word synchronizes the product DFA if and only if |w| ≥ k₁ and |w| ≥ k₂, which is equivalent to |w| ≥ max k₁ k₂. Using le_antisymm, the upper bound is witnessed by repeating any letter max k₁ k₂ times via sInf_le, and the lower bound follows via le_sInf and WithTop.coe_le_coe.mpr since every synchronizing word has length at least max k₁ k₂.

    lines 79–98

    uses le_antisymm, op_1293_dfa_prod_is_synchronizing_iff, op_1293_chainDFA_is_synchronizing_iff, sInf_le, le_sInf, WithTop.coe_le_coe.mpr

    lemma op_1293_chainDFA_prod_reset_threshold (α : Type*) [Nonempty α] (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) :
        dfa_reset_threshold (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) = ↑(max k₁ k₂) := by
      have : Nonempty (Fin (k₁ + 1)) := ⟨0⟩
      have : Nonempty (Fin (k₂ + 1)) := ⟨0⟩
      unfold dfa_reset_threshold
      apply le_antisymm
      · obtain ⟨x⟩ := (inferInstance : Nonempty α)
        have hw : dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) (List.replicate (max k₁ k₂) x) := by
          rw [op_1293_dfa_prod_is_synchronizing_iff, op_1293_chainDFA_is_synchronizing_iff α hk₁, op_1293_chainDFA_is_synchronizing_iff α hk₂]
          simp
        have hmem : (↑(max k₁ k₂) : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) w } := by
          exact ⟨List.replicate (max k₁ k₂) x, hw, by simp⟩
        exact sInf_le hmem
      · apply le_sInf
        rintro _ ⟨w, hw, rfl⟩
        have : dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) w := hw
        rw [op_1293_dfa_prod_is_synchronizing_iff, op_1293_chainDFA_is_synchronizing_iff α hk₁, op_1293_chainDFA_is_synchronizing_iff α hk₂] at this
        have : max k₁ k₂ ≤ w.length := by omega
        exact WithTop.coe_le_coe.mpr this
    
  8. There exist synchronizable DFAs with reset thresholds k₁ and k₂ whose product reset threshold is max k₁ k₂.

    We choose σ₁ = Fin(k₁ + 1), σ₂ = Fin(k₂ + 1), and A₁, A₂ to be the chain DFAs for k₁ and k₂. Each is synchronizable because the constant word x^{kᵢ} synchronizes it by op_1293_chainDFA_is_synchronizing_iff. Their reset thresholds are k₁ and k₂ by op_1293_chainDFA_reset_threshold, and the reset threshold of their product equals max k₁ k₂ by op_1293_chainDFA_prod_reset_threshold.

    lines 99–108

    uses op_1293_chainDFA_is_synchronizing_iff, op_1293_chainDFA_reset_threshold, op_1293_chainDFA_prod_reset_threshold

    /-- The lower bound max(rt(A₁), rt(A₂)) for the product reset threshold is attained. -/
    theorem op_1293_product_reset_threshold_lower_bound_attained (α : Type*) [Fintype α] [Nonempty α] (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) : ∃ (σ₁ σ₂ : Type) (_ : Fintype σ₁) (_ : Fintype σ₂) (A₁ : DFA α σ₁) (A₂ : DFA α σ₂), dfa_is_synchronizable A₁ ∧ dfa_is_synchronizable A₂ ∧ dfa_reset_threshold A₁ = ↑k₁ ∧ dfa_reset_threshold A₂ = ↑k₂ ∧ dfa_reset_threshold (dfa_prod A₁ A₂) = ↑(max k₁ k₂) := by
      refine ⟨Fin (k₁ + 1), Fin (k₂ + 1), inferInstance, inferInstance, op_1293_chainDFA α k₁, op_1293_chainDFA α k₂, ?_, ?_, ?_, ?_, ?_⟩
      · obtain ⟨x⟩ := (inferInstance : Nonempty α)
        exact ⟨List.replicate k₁ x, (op_1293_chainDFA_is_synchronizing_iff α hk₁ _).mpr (by simp)⟩
      · obtain ⟨x⟩ := (inferInstance : Nonempty α)
        exact ⟨List.replicate k₂ x, (op_1293_chainDFA_is_synchronizing_iff α hk₂ _).mpr (by simp)⟩
      · exact op_1293_chainDFA_reset_threshold α k₁ hk₁
      · exact op_1293_chainDFA_reset_threshold α k₂ hk₂
      · exact op_1293_chainDFA_prod_reset_threshold α k₁ k₂ hk₁ hk₂
Nat.lt_succ_of_le
If n ≤ m, then n < m + 1.
Nat.min_le_right
The minimum of two natural numbers is at most the second: min(a, b) ≤ b.
List.reverseRecOn
Right-induction on lists: a property holds for all lists if it holds for the empty list and is preserved under appending a single element to the end.
DFA.evalFrom_nil
Evaluating an automaton from state s on the empty word leaves the state unchanged at s.
List.length_nil
The length of the empty list is 0.
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
DFA.evalFrom_append_singleton
Evaluating an automaton on w ++ [a] equals taking a single transition on symbol a from the state reached after w.
op_1293_chainDFA_step_val
In the chain DFA with parameter k, the value of the next state from q on any input is min(q.val + 1, k).
List.length_append
The length of the concatenation of two lists is the sum of their lengths: |as ++ bs| = |as| + |bs|.
List.length_singleton
A singleton list [a] has length 1.
Fin.val
The projection from Fin n to its underlying natural number.
op_1293_chainDFA_evalFrom_val
Evaluating the chain DFA from state q on word w yields a state with value min(q.val + |w|, k).
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
op_1293_chainDFA_is_synchronizing_iff
A word w synchronizes the chain DFA of size k ≥ 1 if and only if its length is at least k.
sInf_le
The infimum of a set is at most any element belonging to that set.
le_sInf
If a is less than or equal to every element in a set, then a is at most the infimum of the set.
WithTop.coe_le_coe.mpr
An inequality between natural numbers a ≤ b implies the corresponding inequality ↑a ≤ ↑b in WithTop ℕ.
op_1293_dfa_prod_evalFrom
Evaluating the direct product DFA from pair state (q₁, q₂) on word w produces the pair of individual evaluations (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w).
Prod.ext_iff.mp
If two pairs are equal, their first components are equal and their second components are equal.
Prod.ext
Two pairs are equal if their corresponding first and second components are equal.
op_1293_chainDFA_reset_threshold
The reset threshold of the chain DFA of size k ≥ 1 over a nonempty alphabet equals k.
op_1293_chainDFA_prod_reset_threshold
The reset threshold of the direct product of two chain DFAs of sizes k₁, k₂ ≥ 1 equals max k₁ k₂.

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

def op_1293_chainDFA (α : Type*) (k : ℕ) : DFA α (Fin (k + 1)) where  step q _ := ⟨min (q.val + 1) k, by    apply Nat.lt_succ_of_le    exact Nat.min_le_right _ _⟩  start := 0  accept := ∅lemma op_1293_chainDFA_step_val (α : Type*) (k : ℕ) (q : Fin (k + 1)) (a : α) :    ((op_1293_chainDFA α k).step q a).val = min (q.val + 1) k := rfllemma op_1293_chainDFA_evalFrom_val (α : Type*) (k : ℕ) (q : Fin (k + 1)) (w : List α) :    ((op_1293_chainDFA α k).evalFrom q w).val = min (q.val + w.length) k := by  induction' w using List.reverseRecOn with w a ih  · simp only [DFA.evalFrom_nil, List.length_nil, add_zero]    omega  · rw [DFA.evalFrom_append_singleton, op_1293_chainDFA_step_val, ih]    simp only [List.length_append, List.length_singleton]    omegalemma op_1293_chainDFA_is_synchronizing_iff (α : Type*) {k : ℕ} (hk : 1 ≤ k) (w : List α) :    dfa_is_synchronizing (op_1293_chainDFA α k) w ↔ k ≤ w.length := by  constructor  · intro h    have hq := h ⟨0, by omega⟩ ⟨k, by omega⟩    apply_fun Fin.val at hq    rw [op_1293_chainDFA_evalFrom_val, op_1293_chainDFA_evalFrom_val] at hq    dsimp only at hq    omega  · intro h q₁ q₂    apply Fin.ext    rw [op_1293_chainDFA_evalFrom_val, op_1293_chainDFA_evalFrom_val]    omegalemma op_1293_chainDFA_reset_threshold (α : Type*) [Nonempty α] (k : ℕ) (hk : 1 ≤ k) :    dfa_reset_threshold (op_1293_chainDFA α k) = ↑k := by  unfold dfa_reset_threshold  apply le_antisymm  · obtain ⟨x⟩ := (inferInstance : Nonempty α)    have hw : dfa_is_synchronizing (op_1293_chainDFA α k) (List.replicate k x) := by      rw [op_1293_chainDFA_is_synchronizing_iff α hk]      simp    have hmem : (k : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing (op_1293_chainDFA α k) w } := by      exact ⟨List.replicate k x, hw, by simp⟩    exact sInf_le hmem  · apply le_sInf    rintro _ ⟨w, hw, rfl⟩    have : dfa_is_synchronizing (op_1293_chainDFA α k) w := hw    rw [op_1293_chainDFA_is_synchronizing_iff α hk] at this    exact WithTop.coe_le_coe.mpr thislemma op_1293_dfa_prod_evalFrom {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂)    (q₁ : σ₁) (q₂ : σ₂) (w : List α) :    (dfa_prod A₁ A₂).evalFrom (q₁, q₂) w = (A₁.evalFrom q₁ w, A₂.evalFrom q₂ w) := by  induction' w using List.reverseRecOn with w a ih  · simp [DFA.evalFrom_nil]  · rw [DFA.evalFrom_append_singleton, DFA.evalFrom_append_singleton, DFA.evalFrom_append_singleton, ih]    rfllemma op_1293_dfa_prod_is_synchronizing_iff {α σ₁ σ₂ : Type*} [Nonempty σ₁] [Nonempty σ₂]    (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (w : List α) :    dfa_is_synchronizing (dfa_prod A₁ A₂) w ↔ dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := by  constructor  · intro h    obtain ⟨s₁⟩ := (inferInstance : Nonempty σ₁)    obtain ⟨s₂⟩ := (inferInstance : Nonempty σ₂)    constructor    · intro q₁ q₂      have := h (q₁, s₂) (q₂, s₂)      rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom] at this      exact (Prod.ext_iff.mp this).1    · intro q₁ q₂      have := h (s₁, q₁) (s₁, q₂)      rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom] at this      exact (Prod.ext_iff.mp this).2  · rintro ⟨h₁, h₂⟩ ⟨p₁, p₂⟩ ⟨q₁, q₂⟩    rw [op_1293_dfa_prod_evalFrom, op_1293_dfa_prod_evalFrom]    exact Prod.ext (h₁ p₁ q₁) (h₂ p₂ q₂)lemma op_1293_chainDFA_prod_reset_threshold (α : Type*) [Nonempty α] (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) :    dfa_reset_threshold (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) = ↑(max k₁ k₂) := by  have : Nonempty (Fin (k₁ + 1)) := ⟨0⟩  have : Nonempty (Fin (k₂ + 1)) := ⟨0⟩  unfold dfa_reset_threshold  apply le_antisymm  · obtain ⟨x⟩ := (inferInstance : Nonempty α)    have hw : dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) (List.replicate (max k₁ k₂) x) := by      rw [op_1293_dfa_prod_is_synchronizing_iff, op_1293_chainDFA_is_synchronizing_iff α hk₁, op_1293_chainDFA_is_synchronizing_iff α hk₂]      simp    have hmem : (↑(max k₁ k₂) : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) w } := by      exact ⟨List.replicate (max k₁ k₂) x, hw, by simp⟩    exact sInf_le hmem  · apply le_sInf    rintro _ ⟨w, hw, rfl⟩    have : dfa_is_synchronizing (dfa_prod (op_1293_chainDFA α k₁) (op_1293_chainDFA α k₂)) w := hw    rw [op_1293_dfa_prod_is_synchronizing_iff, op_1293_chainDFA_is_synchronizing_iff α hk₁, op_1293_chainDFA_is_synchronizing_iff α hk₂] at this    have : max k₁ k₂ ≤ w.length := by omega    exact WithTop.coe_le_coe.mpr this/-- The lower bound max(rt(A₁), rt(A₂)) for the product reset threshold is attained. -/theorem op_1293_product_reset_threshold_lower_bound_attained (α : Type*) [Fintype α] [Nonempty α] (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) : ∃ (σ₁ σ₂ : Type) (_ : Fintype σ₁) (_ : Fintype σ₂) (A₁ : DFA α σ₁) (A₂ : DFA α σ₂), dfa_is_synchronizable A₁ ∧ dfa_is_synchronizable A₂ ∧ dfa_reset_threshold A₁ = ↑k₁ ∧ dfa_reset_threshold A₂ = ↑k₂ ∧ dfa_reset_threshold (dfa_prod A₁ A₂) = ↑(max k₁ k₂) := by  refine ⟨Fin (k₁ + 1), Fin (k₂ + 1), inferInstance, inferInstance, op_1293_chainDFA α k₁, op_1293_chainDFA α k₂, ?_, ?_, ?_, ?_, ?_⟩  · obtain ⟨x⟩ := (inferInstance : Nonempty α)    exact ⟨List.replicate k₁ x, (op_1293_chainDFA_is_synchronizing_iff α hk₁ _).mpr (by simp)⟩  · obtain ⟨x⟩ := (inferInstance : Nonempty α)    exact ⟨List.replicate k₂ x, (op_1293_chainDFA_is_synchronizing_iff α hk₂ _).mpr (by simp)⟩  · exact op_1293_chainDFA_reset_threshold α k₁ hk₁  · exact op_1293_chainDFA_reset_threshold α k₂ hk₂  · exact op_1293_chainDFA_prod_reset_threshold α k₁ k₂ hk₁ hk₂
See it in the graphDiscuss this resultChallenge it