op_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_one
For every finite alphabet α with at least two symbols and k ∈ {1, 2}, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ with dfa_reset_threshold A₁ = 1 and dfa_reset_threshold A₂ = 1 such that the reset threshold of their direct product is k.
Statement
theorem op_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_one (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (k : ℕ) (hk : k = 1 ∨ k = 2) : ∃ (σ₁ σ₂ : Type) (_ : Fintype σ₁) (_ : Fintype σ₂) (A₁ : DFA α σ₁) (A₂ : DFA α σ₂), dfa_is_synchronizable A₁ ∧ dfa_is_synchronizable A₂ ∧ dfa_reset_threshold A₁ = 1 ∧ dfa_reset_threshold A₂ = 1 ∧ dfa_reset_threshold (dfa_prod A₁ A₂) = ↑k
- Source
- arXiv:2611.09136 Sec. 7, open question 2
- 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… - 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_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
Read back from the Lean
For every finite type α with at least 2 elements (Fintype.card α ≥ 2), and every natural number k such that k = 1 or k = 2, there exist finite types σ₁ and σ₂ (in Type 0) and deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂ such that:
1. A₁ is synchronizable (admits a synchronizing word),
2. A₂ is synchronizable (admits a synchronizing word),
3. the reset threshold of A₁ is 1 (the shortest synchronizing word for A₁ has length 1),
4. the reset threshold of A₂ is 1 (the shortest synchronizing word for A₂ has length 1), and
5. the reset threshold of the product automaton dfa_prod A₁ A₂ is k.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof splits into cases on whether k = 1 or k = 2. When k = 1, the alphabet α is nonempty because |α| ≥ 2, so the result follows from the lower bound attainment theorem setting k₁ = 1 and k₂ = 1, giving product reset threshold max(1, 1) = 1. When k = 2, the result follows from the upper bound attainment theorem setting k₁ = 1 and k₂ = 1, which gives product reset threshold 1 + 1 = 2.
The theorem holds when k = 1: there exist synchronizable DFAs A₁ and A₂ with reset threshold 1 whose product has reset threshold 1.
We perform a case split on hk (k = 1 ∨ k = 2). In the first case, k = 1. Since |α| ≥ 2, we have |α| > 0 by linear arithmetic, which implies α is nonempty via Fintype.card_pos_iff.mp. We then invoke op_1293_product_reset_threshold_lower_bound_attained with k₁ = 1 and k₂ = 1 (discharging 1 ≤ 1 by linear arithmetic). This provides synchronizable DFAs A₁ and A₂ each with reset threshold 1 whose direct product has reset threshold max(1, 1) = 1, satisfying all required conditions.
uses
Fintype.card_pos_iff.mp,op_1293_product_reset_threshold_lower_bound_attainedrcases hk with rfl | rfl · have : Nonempty α := Fintype.card_pos_iff.mp (by omega) obtain ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩ := op_1293_product_reset_threshold_lower_bound_attained α 1 1 (by omega) (by omega) exact ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩
The theorem holds when k = 2: there exist synchronizable DFAs A₁ and A₂ with reset threshold 1 whose product has reset threshold 2.
In the second case, k = 2. We invoke op_1293_product_reset_threshold_upper_bound_attained with the hypothesis |α| ≥ 2 and k₁ = 1, k₂ = 1 (again discharging 1 ≤ 1 by linear arithmetic). This provides synchronizable DFAs A₁ and A₂ each with reset threshold 1 whose direct product has reset threshold 1 + 1 = 2, completing the proof.
uses
op_1293_product_reset_threshold_upper_bound_attained· obtain ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩ := op_1293_product_reset_threshold_upper_bound_attained α hα 1 1 (by omega) (by omega) exact ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩
Fintype.card_pos_iff.mp- A finite type whose cardinality is strictly positive is nonempty.
op_1293_product_reset_threshold_lower_bound_attained- For any finite nonempty alphabet α and integers k₁, k₂ ≥ 1, there exist synchronizable DFAs A₁ and A₂ with reset thresholds k₁ and k₂ respectively whose direct product has reset threshold max(k₁, k₂).
op_1293_product_reset_threshold_upper_bound_attained- For any finite alphabet α with at least two symbols and integers k₁, k₂ ≥ 1, there exist synchronizable DFAs A₁ and A₂ with reset thresholds k₁ and k₂ respectively whose direct product has reset threshold k₁ + k₂.
- The lower bound theorem op_1293_product_reset_threshold_lower_bound_attained requires an explicit typeclass instance [Nonempty α], which is derived from 2 ≤ Fintype.card α via Fintype.card_pos_iff.mp.
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.
/-- Attainability of intermediate reset thresholds for the base case k₁ = 1, k₂ = 1. -/theorem op_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_one (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (k : ℕ) (hk : k = 1 ∨ k = 2) : ∃ (σ₁ σ₂ : Type) (_ : Fintype σ₁) (_ : Fintype σ₂) (A₁ : DFA α σ₁) (A₂ : DFA α σ₂), dfa_is_synchronizable A₁ ∧ dfa_is_synchronizable A₂ ∧ dfa_reset_threshold A₁ = 1 ∧ dfa_reset_threshold A₂ = 1 ∧ dfa_reset_threshold (dfa_prod A₁ A₂) = ↑k := by rcases hk with rfl | rfl · have : Nonempty α := Fintype.card_pos_iff.mp (by omega) obtain ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩ := op_1293_product_reset_threshold_lower_bound_attained α 1 1 (by omega) (by omega) exact ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩ · obtain ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩ := op_1293_product_reset_threshold_upper_bound_attained α hα 1 1 (by omega) (by omega) exact ⟨σ₁, σ₂, hσ₁, hσ₂, A₁, A₂, h1, h2, h3, h4, h5⟩