op_1293_product_reset_threshold_upper_bound_attained
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 wordw : List αforA. - dfa_reset_thresholdThe reset threshold
dfa_reset_threshold Aof a deterministic finite automatonA : DFA α σis the infimum inWithTop ℕof the lengths… - 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… - 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…
- dfa_is_synchronizableA deterministic finite automaton
- Used by 2
- op_1293_intermediate_reset_thresholdOpen Problem OP-1293 (arXiv:2611.09136 Sec. 7, open question 2): For every finite alphabet α with at least two symbols, any positive…
- op_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_oneFor every finite alphabet α with at least two symbols and k ∈ {1, 2}, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ :…
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₂.
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.
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
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.
uses
DFA.evalFrom_nil,DFA.evalFrom_constheorem 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]
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.
uses
op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_valtheorem 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
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.
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_antisymmtheorem 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
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.
uses
beq_iff_eqtheorem 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
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.
uses
beq_eq_false_iff_ne.mpr,Ne.symmtheorem 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]
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.
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.mprtheorem 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
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.
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_thresholdtheorem 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
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.
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₂