op_1293_product_reset_threshold_lower_bound_attained
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 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…
- dfa_is_synchronizableA deterministic finite automaton
- Used by 3
- 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_product_reset_threshold_upper_bound_attainedFor every finite alphabet α with at least two symbols and positive integers k₁, k₂, there exist finite state types σ₁, σ₂ and…
- 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
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.
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.
uses
Nat.lt_succ_of_le,Nat.min_le_rightdef 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 := ∅
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).
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_singletonlemma 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
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.
uses
Fin.val,op_1293_chainDFA_evalFrom_val,Fin.extlemma 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
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.
uses
le_antisymm,op_1293_chainDFA_is_synchronizing_iff,sInf_le,le_sInf,WithTop.coe_le_coe.mprlemma 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
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.
uses
List.reverseRecOn,DFA.evalFrom_nil,DFA.evalFrom_append_singletonlemma 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
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.
uses
op_1293_dfa_prod_evalFrom,Prod.ext_iff.mp,Prod.extlemma 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₂)
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₂.
uses
le_antisymm,op_1293_dfa_prod_is_synchronizing_iff,op_1293_chainDFA_is_synchronizing_iff,sInf_le,le_sInf,WithTop.coe_le_coe.mprlemma 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
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.
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₂.
- The reset threshold is defined with values in `WithTop ℕ` (natural numbers extended with $+\infty$), representing the infimum of the lengths of synchronizing words. When synchronizing words exist, this infimum is a finite natural number.
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.
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₂