AFTD Auto-Formalizing Theoretical Domains

op_1293_product_reset_threshold_upper_bound_attained

theoremverifiedformalization

For every finite alphabet α with at least two symbols 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 upper bound k₁ + k₂.

Statement

theorem op_1293_product_reset_threshold_upper_bound_attained (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (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₂) = ↑(k₁ + k₂)
Formalizes
arXiv:2611.09136 Example 3.7, Proposition 3.4
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • op_1293_product_reset_threshold_lower_bound_attainedFor every nonempty finite alphabet α and positive integers k₁, k₂, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ : DFA…
Used by 2

Read back from the Lean

Let $α$ be a finite type with at least 2 elements (2 ≤ Fintype.card α), and let $k_1, k_2 \in \mathbb{N}$ be natural numbers with $1 \le k_1$ and $1 \le k_2$. Then there exist types $σ_1, σ_2 : \mathrm{Type}$ with finite type instances on each, and DFAs $A_1 : \mathrm{DFA}\ α\ σ_1$ and $A_2 : \mathrm{DFA}\ α\ σ_2$, such that: 1. $A_1$ is synchronizable (it has a synchronizing word), 2. $A_2$ is synchronizable (it has a synchronizing word), 3. the reset threshold of $A_1$ is $k_1$ (coerced to WithTop ℕ), 4. the reset threshold of $A_2$ is $k_2$ (coerced to WithTop ℕ), and 5. the reset threshold of the direct product DFA dfa_prod A₁ A₂ is $k_1 + k_2$ (coerced to 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

For any two positive integers k₁, k₂ and an alphabet with at least two distinct symbols a ≠ b, we construct two DFAs: A₁ counts occurrences of a up to k₁, and A₂ counts occurrences of b up to k₂. Each DFA Aᵢ has reset threshold kᵢ because it synchronizes precisely on words containing at least kᵢ occurrences of its designated letter. A word synchronizes their direct product if and only if it contains both at least k₁ occurrences of a and at least k₂ occurrences of b; since a and b are distinct, any such word must have length at least k₁ + k₂, and the word a^{k₁} b^{k₂} achieves this minimum, showing that the product reset threshold reaches the theoretical upper bound k₁ + k₂.

  1. The transition step stays within Fin (k + 1) automation

    When the input matches the target letter, the state counter is incremented by 1 up to k; min (q + 1) k is bounded by k, which is strictly less than k + 1 by linear arithmetic.

    lines 3–6

    def op_1293_product_reset_threshold_upper_bound_attained_letterChainStep
        {α : Type*} [DecidableEq α] (k : ℕ) (a : α) (q : Fin (k + 1)) (x : α) : Fin (k + 1) :=
      if x = a then ⟨min (q.val + 1) k, by omega⟩ else q
    
  2. Running the letter-chain DFA on word w from state q reaches min (q + count a w) k

    By induction on the word w. For the empty word, the count is 0 and q < k + 1 implies min q k = q. For a prepended letter x, evaluating the DFA advances one step; by the induction hypothesis and case analysis on whether x = a, the state value increases by 1 if x = a and stays the same otherwise, matching the update in the letter count.

    lines 13–33

    uses DFA.evalFrom_nil, DFA.evalFrom_cons

    theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val
        {α : Type*} [DecidableEq α] (k : ℕ) (a : α) (q : Fin (k + 1)) (w : List α) :
        ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom q w).val =
          min (q.val + w.count a) k := by
      induction w generalizing q with
      | nil =>
        rw [DFA.evalFrom_nil]
        simp only [List.count_nil, add_zero]
        have := q.is_lt
        omega
      | cons x xs ih =>
        rw [DFA.evalFrom_cons]
        change ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom
          (op_1293_product_reset_threshold_upper_bound_attained_letterChainStep k a q x) xs).val = _
        rw [ih]
        dsimp [op_1293_product_reset_threshold_upper_bound_attained_letterChainStep]
        split_ifs with hx
        · simp [hx]
          omega
        · simp [hx]
    
  3. A word synchronizes the letter-chain DFA if and only if it contains at least k occurrences of the designated letter a

    If w synchronizes the DFA, evaluating from state 0 and state k must yield the same state, so min (count a w) k = min (k + count a w) k = k, implying count a w ≥ k. Conversely, if count a w ≥ k, then for any two starting states q₁ and q₂, q₁ + count a w ≥ k and q₂ + count a w ≥ k, so both evaluate to k.

    lines 34–53

    uses op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val

    theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff
        {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (a : α) (w : List α) :
        dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) w ↔
          k ≤ w.count a := by
      constructor
      · intro h
        have hq := h ⟨0, by omega⟩ ⟨k, by omega⟩
        have h1 := op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val k a ⟨0, by omega⟩ w
        have h2 := op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val k a ⟨k, by omega⟩ w
        have heq : ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom ⟨0, by omega⟩ w).val =
                   ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom ⟨k, by omega⟩ w).val := by rw [hq]
        rw [h1, h2] at heq
        dsimp at heq
        omega
      · intro h q₁ q₂
        ext
        rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val,
            op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val]
        omega
    
  4. The reset threshold of the letter-chain DFA is k

    By antisymmetry. The word consisting of k copies of a synchronizes the DFA and has length k, showing the threshold is at most k. Conversely, any synchronizing word w has count a w ≥ k, and since count a w ≤ length w, the length of any synchronizing word is at least k, showing the threshold is at least k.

    lines 54–71

    uses op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff, sInf_le, le_sInf, List.count_le_length, WithTop.coe_le_coe.mpr, le_antisymm

    theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold
        {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k) (a : α) :
        dfa_reset_threshold (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) = ↑k := by
      apply le_antisymm
      · have hw : dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) (List.replicate k a) := by
          rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk]
          simp
        have hmem : (k : WithTop ℕ) ∈ (fun w => (w.length : WithTop ℕ)) ''
            {w | dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) w} := by
          exact ⟨List.replicate k a, hw, by simp⟩
        exact sInf_le hmem
      · apply le_sInf
        rintro b ⟨w, hw, rfl⟩
        dsimp at hw
        rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk] at hw
        have hlen : k ≤ w.length := hw.trans List.count_le_length
        exact WithTop.coe_le_coe.mpr hlen
    
  5. For distinct letters a and b, the sum of their counts in any word is at most the word's length

    By induction on the word w. For the empty word both counts and length are 0. For a prepended letter x, it cannot equal both a and b because a ≠ b, so at most one count increases by 1, while the length increases by 1.

    lines 72–85

    uses beq_iff_eq

    theorem op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length
        {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b) (w : List α) :
        w.count a + w.count b ≤ w.length := by
      induction w with
      | nil => simp
      | cons x xs ih =>
        simp only [List.count_cons, List.length_cons]
        split_ifs with h1 h2
        · rw [beq_iff_eq] at h1 h2
          subst h1 h2; contradiction
        · omega
        · omega
        · omega
    
  6. The concatenated word a^{k₁} b^{k₂} has k₁ occurrences of a, k₂ occurrences of b, and length k₁ + k₂

    Since a ≠ b, the counts of a and b in each block do not interfere: count a (b^{k₂}) = 0 and count b (a^{k₁}) = 0. Simplifying the counts and lengths of replicate blocks yields the result.

    lines 86–94

    uses beq_eq_false_iff_ne.mpr, Ne.symm

    theorem op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate
        {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b) (k₁ k₂ : ℕ) :
        (List.replicate k₁ a ++ List.replicate k₂ b).count a = k₁ ∧
        (List.replicate k₁ a ++ List.replicate k₂ b).count b = k₂ ∧
        (List.replicate k₁ a ++ List.replicate k₂ b).length = k₁ + k₂ := by
      have h_ne1 : (b == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm hab)
      have h_ne2 : (a == b) = false := beq_eq_false_iff_ne.mpr hab
      simp [List.count_append, List.count_replicate, h_ne1, h_ne2]
    
  7. The direct product of two letter-chain DFAs on distinct letters has reset threshold k₁ + k₂

    By antisymmetry. The word a^{k₁} b^{k₂} has k₁ copies of a and k₂ copies of b, so it synchronizes both DFAs and thus their direct product; its length is k₁ + k₂, giving the upper bound. Conversely, any word synchronizing the direct product must synchronize both component DFAs, so it contains at least k₁ copies of a and at least k₂ copies of b; since a ≠ b, its length is at least the sum of these counts, which is at least k₁ + k₂, giving the lower bound.

    lines 95–130

    uses le_antisymm, op_1293_dfa_prod_is_synchronizing_iff, op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff, op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate, sInf_le, le_sInf, add_le_add, op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length, WithTop.coe_le_coe.mpr

    theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_prod_reset_threshold
        {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b)
        (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) :
        dfa_reset_threshold (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)
                                      (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b)) = ↑(k₁ + k₂) := by
      have : Nonempty (Fin (k₁ + 1)) := ⟨0⟩
      have : Nonempty (Fin (k₂ + 1)) := ⟨0⟩
      apply le_antisymm
      · have hsync : dfa_is_synchronizing (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)
                                                    (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b))
            (List.replicate k₁ a ++ List.replicate k₂ b) := by
          rw [op_1293_dfa_prod_is_synchronizing_iff]
          rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁]
          rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂]
          have hcounts := op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate hab k₁ k₂
          exact ⟨le_of_eq hcounts.1.symm, le_of_eq hcounts.2.1.symm⟩
        have hlen : (List.replicate k₁ a ++ List.replicate k₂ b).length = k₁ + k₂ :=
          (op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate hab k₁ k₂).2.2
        have hmem : ((k₁ + k₂ : ℕ) : WithTop ℕ) ∈
            (fun w => (w.length : WithTop ℕ)) ''
              {w | dfa_is_synchronizing (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)
                                                  (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b)) w} := by
          refine ⟨List.replicate k₁ a ++ List.replicate k₂ b, hsync, ?_⟩
          dsimp
          rw [hlen]
        exact sInf_le hmem
      · apply le_sInf
        rintro b ⟨w, hw, rfl⟩
        dsimp at hw
        rw [op_1293_dfa_prod_is_synchronizing_iff] at hw
        rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁] at hw
        rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂] at hw
        have hsum : k₁ + k₂ ≤ w.count a + w.count b := add_le_add hw.1 hw.2
        have htotal := hsum.trans (op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length hab w)
        exact WithTop.coe_le_coe.mpr htotal
    
  8. There exist synchronizable DFAs achieving the upper bound k₁ + k₂ on their product reset threshold

    Since |α| ≥ 2, α is nontrivial, so there exist distinct letters a ≠ b. We instantiate A₁ as the letter-chain DFA of parameter k₁ on letter a, and A₂ as the letter-chain DFA of parameter k₂ on letter b. Both are synchronizable (by a^{k₁} and b^{k₂} respectively), have reset thresholds k₁ and k₂, and their product has reset threshold k₁ + k₂ by the preceding lemmas.

    lines 132–143

    uses Fintype.one_lt_card_iff_nontrivial, exists_pair_ne, op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff, op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold, op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_prod_reset_threshold

    theorem op_1293_product_reset_threshold_upper_bound_attained (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (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₂) = ↑(k₁ + k₂) := by
      classical
      have : Nontrivial α := Fintype.one_lt_card_iff_nontrivial.mp (by omega)
      obtain ⟨a, b, hab⟩ := exists_pair_ne α
      refine ⟨Fin (k₁ + 1), Fin (k₂ + 1), inferInstance, inferInstance,
              op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a,
              op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b, ?_, ?_, ?_, ?_, ?_⟩
      · exact ⟨List.replicate k₁ a, (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁ a _).mpr (by simp)⟩
      · exact ⟨List.replicate k₂ b, (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂ b _).mpr (by simp)⟩
      · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold k₁ hk₁ a
      · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold k₂ hk₂ b
      · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_prod_reset_threshold hab k₁ k₂ hk₁ hk₂
exists_pair_ne
Two elements of a nontrivial type can be chosen distinct
Fintype.one_lt_card_iff_nontrivial
The cardinality of a type is greater than 1 if and only if the type is nontrivial
op_1293_dfa_prod_is_synchronizing_iff
A word synchronizes a direct product of two DFAs if and only if it synchronizes both components
List.count_le_length
The number of occurrences of an element in a list is at most the list's length

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

open Listdef op_1293_product_reset_threshold_upper_bound_attained_letterChainStep    {α : Type*} [DecidableEq α] (k : ℕ) (a : α) (q : Fin (k + 1)) (x : α) : Fin (k + 1) :=  if x = a then ⟨min (q.val + 1) k, by omega⟩ else qdef op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA    {α : Type*} [DecidableEq α] (k : ℕ) (a : α) : DFA α (Fin (k + 1)) where  step := op_1293_product_reset_threshold_upper_bound_attained_letterChainStep k a  start := 0  accept := ∅theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val    {α : Type*} [DecidableEq α] (k : ℕ) (a : α) (q : Fin (k + 1)) (w : List α) :    ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom q w).val =      min (q.val + w.count a) k := by  induction w generalizing q with  | nil =>    rw [DFA.evalFrom_nil]    simp only [List.count_nil, add_zero]    have := q.is_lt    omega  | cons x xs ih =>    rw [DFA.evalFrom_cons]    change ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom      (op_1293_product_reset_threshold_upper_bound_attained_letterChainStep k a q x) xs).val = _    rw [ih]    dsimp [op_1293_product_reset_threshold_upper_bound_attained_letterChainStep]    split_ifs with hx    · simp [hx]      omega    · simp [hx]theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff    {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (a : α) (w : List α) :    dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) w ↔      k ≤ w.count a := by  constructor  · intro h    have hq := h ⟨0, by omega⟩ ⟨k, by omega⟩    have h1 := op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val k a ⟨0, by omega⟩ w    have h2 := op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val k a ⟨k, by omega⟩ w    have heq : ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom ⟨0, by omega⟩ w).val =               ((op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a).evalFrom ⟨k, by omega⟩ w).val := by rw [hq]    rw [h1, h2] at heq    dsimp at heq    omega  · intro h q₁ q₂    ext    rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val,        op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val]    omegatheorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold    {α : Type*} [DecidableEq α] (k : ℕ) (hk : 1 ≤ k) (a : α) :    dfa_reset_threshold (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) = ↑k := by  apply le_antisymm  · have hw : dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) (List.replicate k a) := by      rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk]      simp    have hmem : (k : WithTop ℕ) ∈ (fun w => (w.length : WithTop ℕ)) ''        {w | dfa_is_synchronizing (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k a) w} := by      exact ⟨List.replicate k a, hw, by simp⟩    exact sInf_le hmem  · apply le_sInf    rintro b ⟨w, hw, rfl⟩    dsimp at hw    rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk] at hw    have hlen : k ≤ w.length := hw.trans List.count_le_length    exact WithTop.coe_le_coe.mpr hlentheorem op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length    {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b) (w : List α) :    w.count a + w.count b ≤ w.length := by  induction w with  | nil => simp  | cons x xs ih =>    simp only [List.count_cons, List.length_cons]    split_ifs with h1 h2    · rw [beq_iff_eq] at h1 h2      subst h1 h2; contradiction    · omega    · omega    · omegatheorem op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate    {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b) (k₁ k₂ : ℕ) :    (List.replicate k₁ a ++ List.replicate k₂ b).count a = k₁ ∧    (List.replicate k₁ a ++ List.replicate k₂ b).count b = k₂ ∧    (List.replicate k₁ a ++ List.replicate k₂ b).length = k₁ + k₂ := by  have h_ne1 : (b == a) = false := beq_eq_false_iff_ne.mpr (Ne.symm hab)  have h_ne2 : (a == b) = false := beq_eq_false_iff_ne.mpr hab  simp [List.count_append, List.count_replicate, h_ne1, h_ne2]theorem op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_prod_reset_threshold    {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b)    (k₁ k₂ : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) :    dfa_reset_threshold (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)                                  (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b)) = ↑(k₁ + k₂) := by  have : Nonempty (Fin (k₁ + 1)) := ⟨0⟩  have : Nonempty (Fin (k₂ + 1)) := ⟨0⟩  apply le_antisymm  · have hsync : dfa_is_synchronizing (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)                                                (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b))        (List.replicate k₁ a ++ List.replicate k₂ b) := by      rw [op_1293_dfa_prod_is_synchronizing_iff]      rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁]      rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂]      have hcounts := op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate hab k₁ k₂      exact ⟨le_of_eq hcounts.1.symm, le_of_eq hcounts.2.1.symm⟩    have hlen : (List.replicate k₁ a ++ List.replicate k₂ b).length = k₁ + k₂ :=      (op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate hab k₁ k₂).2.2    have hmem : ((k₁ + k₂ : ℕ) : WithTop ℕ) ∈        (fun w => (w.length : WithTop ℕ)) ''          {w | dfa_is_synchronizing (dfa_prod (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a)                                              (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b)) w} := by      refine ⟨List.replicate k₁ a ++ List.replicate k₂ b, hsync, ?_⟩      dsimp      rw [hlen]    exact sInf_le hmem  · apply le_sInf    rintro b ⟨w, hw, rfl⟩    dsimp at hw    rw [op_1293_dfa_prod_is_synchronizing_iff] at hw    rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁] at hw    rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂] at hw    have hsum : k₁ + k₂ ≤ w.count a + w.count b := add_le_add hw.1 hw.2    have htotal := hsum.trans (op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length hab w)    exact WithTop.coe_le_coe.mpr htotal/-- The upper bound rt(A₁) + rt(A₂) for the product reset threshold is attained. -/theorem op_1293_product_reset_threshold_upper_bound_attained (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (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₂) = ↑(k₁ + k₂) := by  classical  have : Nontrivial α := Fintype.one_lt_card_iff_nontrivial.mp (by omega)  obtain ⟨a, b, hab⟩ := exists_pair_ne α  refine ⟨Fin (k₁ + 1), Fin (k₂ + 1), inferInstance, inferInstance,          op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a,          op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b, ?_, ?_, ?_, ?_, ?_⟩  · exact ⟨List.replicate k₁ a, (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁ a _).mpr (by simp)⟩  · exact ⟨List.replicate k₂ b, (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂ b _).mpr (by simp)⟩  · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold k₁ hk₁ a  · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold k₂ hk₂ b  · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_prod_reset_threshold hab k₁ k₂ hk₁ hk₂
See it in the graphDiscuss this resultChallenge it