AFTD Auto-Formalizing Theoretical Domains

op_1293_intermediate_reset_threshold_k1_eq_one_k2_eq_one

theoremverified

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 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…
  • 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…

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.

  1. 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.

    lines 3–7

    uses Fintype.card_pos_iff.mp, op_1293_product_reset_threshold_lower_bound_attained

      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⟩
  2. 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.

    lines 8–10

    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₂.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it