AFTD Auto-Formalizing Theoretical Domains

op_1293_intermediate_reset_threshold

theoremverifiedformalization

Open Problem OP-1293 (arXiv:2611.09136 Sec. 7, open question 2): For every finite alphabet α with at least two symbols, any positive integers k₁ and k₂, and any integer k satisfying max k₁ k₂ ≤ k ≤ k₁ + k₂, there exist finite state types σ₁, σ₂ and synchronizable DFAs A₁ : DFA α σ₁ and A₂ : DFA α σ₂ with reset thresholds dfa_reset_threshold A₁ = k₁ and dfa_reset_threshold A₂ = k₂ such that the direct product dfa_prod A₁ A₂ has reset threshold dfa_reset_threshold (dfa_prod A₁ A₂) = k.

Statement

theorem op_1293_intermediate_reset_threshold (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (k₁ k₂ k : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) (h_lower : max k₁ k₂ ≤ k) (h_upper : k ≤ k₁ + 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
Formalizes
arXiv:2611.09136 Sec. 7, open question 2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_prod_reset_threshold_boundsFor any two deterministic finite automata A₁ and A₂ over the same alphabet, the reset threshold of their direct product satisfies…
  • 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…
  • 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…

Read back from the Lean

Let α be a finite type with at least 2 elements (2 ≤ Fintype.card α). Let k₁, k₂, and k be natural numbers such that 1 ≤ k₁, 1 ≤ k₂, max k₁ k₂ ≤ k, and k ≤ k₁ + k₂. Then there exist finite types σ₁ and σ₂ (each equipped 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₁ (coerced to WithTop ℕ); 4. the reset threshold of A₂ equals k₂ (coerced to WithTop ℕ); and 5. the reset threshold of the direct product DFA dfa_prod A₁ A₂ equals k (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.

Lean source view module on GitHub

def op_1293_intermediate_reset_threshold_step {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) :    Fin (k₂ + 1) → α → Fin (k₂ + 1) := fun q x =>  if x = b then    ⟨min (q.val + 1) k₂, Nat.lt_succ_of_le (min_le_right _ _)⟩  else if h : x = a ∧ q.val < m then    ⟨q.val + 1, by omega⟩  else    qdef op_1293_intermediate_reset_threshold_DFA {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) :    DFA α (Fin (k₂ + 1)) :=  { step := op_1293_intermediate_reset_threshold_step k₂ m a b hm, start := 0, accept := ∅ }theorem op_1293_intermediate_reset_threshold_step_b {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) (q : Fin (k₂ + 1)) :    op_1293_intermediate_reset_threshold_step k₂ m a b hm q b =    op_1293_product_reset_threshold_upper_bound_attained_letterChainStep k₂ b q b := by  dsimp [op_1293_intermediate_reset_threshold_step, op_1293_product_reset_threshold_upper_bound_attained_letterChainStep]  simptheorem op_1293_intermediate_reset_threshold_evalFrom_replicate_b {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (n : ℕ) (q : Fin (k₂ + 1)) :    (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q (List.replicate n b) =    (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b).evalFrom q (List.replicate n b) := by  induction n generalizing q with  | zero => simp [DFA.evalFrom]  | succ n ih =>    rw [List.replicate_succ, DFA.evalFrom_cons, DFA.evalFrom_cons]    have : (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).step q b =      (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₂ b).step q b :=      op_1293_intermediate_reset_threshold_step_b k₂ m a b hm q    rw [this, ih]theorem op_1293_intermediate_reset_threshold_sync_replicate_b {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) (hk₂ : 1 ≤ k₂) :    dfa_is_synchronizing (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm) (List.replicate k₂ b) := by  intro q₁ q₂  rw [op_1293_intermediate_reset_threshold_evalFrom_replicate_b, op_1293_intermediate_reset_threshold_evalFrom_replicate_b]  have hsync := (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₂ b (List.replicate k₂ b)).mpr (by simp)  exact hsync q₁ q₂theorem op_1293_intermediate_reset_threshold_step_top {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) (x : α) :    op_1293_intermediate_reset_threshold_step k₂ m a b hm ⟨k₂, Nat.lt_succ_self k₂⟩ x = ⟨k₂, Nat.lt_succ_self k₂⟩ := by  dsimp [op_1293_intermediate_reset_threshold_step]  split_ifs with h1 h2  · ext; simp  · exfalso; omega  · rfltheorem op_1293_intermediate_reset_threshold_evalFrom_top {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (w : List α) :    (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom ⟨k₂, Nat.lt_succ_self k₂⟩ w = ⟨k₂, Nat.lt_succ_self k₂⟩ := by  induction w with  | nil => simp [DFA.evalFrom]  | cons x w ih =>    rw [DFA.evalFrom_cons]    have : (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).step ⟨k₂, Nat.lt_succ_self k₂⟩ x = ⟨k₂, Nat.lt_succ_self k₂⟩ :=      op_1293_intermediate_reset_threshold_step_top k₂ m a b hm x    rw [this, ih]theorem op_1293_intermediate_reset_threshold_step_val_le_succ {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (q : Fin (k₂ + 1)) (x : α) :    (op_1293_intermediate_reset_threshold_step k₂ m a b hm q x).val ≤ q.val + 1 := by  dsimp [op_1293_intermediate_reset_threshold_step]  split_ifs with h1 h2  · exact le_trans (min_le_left _ _) le_rfl  · exact le_rfl  · omegatheorem op_1293_intermediate_reset_threshold_evalFrom_zero_le_length {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (w : List α) :    ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val ≤ w.length := by  induction w using List.reverseRecOn with  | nil => simp [DFA.evalFrom]  | append_singleton w x ih =>    rw [show (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 (w ++ [x]) =      op_1293_intermediate_reset_threshold_step k₂ m a b hm ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w) x by      simp [DFA.evalFrom, op_1293_intermediate_reset_threshold_DFA]]    have hstep := op_1293_intermediate_reset_threshold_step_val_le_succ k₂ m a b hm ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w) x    rw [List.length_append, List.length_singleton]    omegatheorem op_1293_intermediate_reset_threshold_sync_len_le {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (w : List α) (hw : dfa_is_synchronizing (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm) w) :    k₂ ≤ w.length := by  have htop := hw 0 ⟨k₂, Nat.lt_succ_self k₂⟩  rw [op_1293_intermediate_reset_threshold_evalFrom_top] at htop  have hval : ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val = k₂ := by    rw [htop]  have hlen := op_1293_intermediate_reset_threshold_evalFrom_zero_le_length k₂ m a b hm w  omegatheorem op_1293_intermediate_reset_threshold_A₂_reset_threshold {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂) (hk₂ : 1 ≤ k₂) :    dfa_reset_threshold (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm) = ↑k₂ := by  apply le_antisymm  · have hsync := op_1293_intermediate_reset_threshold_sync_replicate_b k₂ m a b hm hk₂    have hmem : (↑(List.replicate k₂ b).length : WithTop ℕ) ∈ (fun w => (↑w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm) w} := by      exact ⟨List.replicate k₂ b, hsync, rfl⟩    have hinf := sInf_le hmem    rw [List.length_replicate] at hinf    exact hinf  · apply le_sInf    rintro b_1 ⟨w, hw, rfl⟩    exact WithTop.coe_le_coe.mpr (op_1293_intermediate_reset_threshold_sync_len_le k₂ m a b hm w hw)theorem op_1293_intermediate_reset_threshold_evalFrom_zero_le_m_add_count_b {α : Type*} [DecidableEq α] (k₂ m : ℕ) (a b : α) (hm : m ≤ k₂)    (w : List α) :    ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val ≤ m + List.count b w := by  induction w using List.reverseRecOn with  | nil => simp [DFA.evalFrom]  | append_singleton w x ih =>    rw [show (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 (w ++ [x]) =      op_1293_intermediate_reset_threshold_step k₂ m a b hm ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w) x by      simp [DFA.evalFrom, op_1293_intermediate_reset_threshold_DFA]]    rw [List.count_append]    by_cases hx : x = b    · rw [hx, List.count_singleton_self]      dsimp [op_1293_intermediate_reset_threshold_step]      simp only [↓reduceIte]      have : min (((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val + 1) k₂ ≤        ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val + 1 := min_le_left _ _      change min (((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val + 1) k₂ ≤ m + (List.count b w + 1)      omega    · have hxb : List.count b [x] = 0 := by        have : (x == b) = false := beq_false_of_ne hx        simp [List.count, this]      rw [hxb]      dsimp [op_1293_intermediate_reset_threshold_step]      simp only [if_neg hx]      split_ifs with h1      · change ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val + 1 ≤ m + (List.count b w + 0)        omega      · omegatheorem op_1293_intermediate_reset_threshold_evalFrom_replicate_a_val {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b)    (k₂ m : ℕ) (hm : m ≤ k₂) (q : Fin (k₂ + 1)) (n : ℕ) :    ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q (List.replicate n a)).val = min (q.val + n) (max q.val m) := by  induction n generalizing q with  | zero => simp [DFA.evalFrom]  | succ n ih =>    rw [List.replicate_succ, DFA.evalFrom_cons]    show ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom (op_1293_intermediate_reset_threshold_step k₂ m a b hm q a) (List.replicate n a)).val = _    dsimp [op_1293_intermediate_reset_threshold_step]    rw [if_neg hab]    split_ifs with h    · rw [ih]      dsimp      omega    · rw [ih]      have : m ≤ q.val := not_lt.mp (fun hlt => h ⟨rfl, hlt⟩)      omegatheorem op_1293_intermediate_reset_threshold_evalFrom_word_eq_top {α : Type*} [DecidableEq α] {a b : α} (hab : a ≠ b)    (k₁ k₂ m : ℕ) (hm : m ≤ k₂) (hmk₁ : m ≤ k₁) (q : Fin (k₂ + 1)) :    (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q (List.replicate k₁ a ++ List.replicate (k₂ - m) b) =    ⟨k₂, Nat.lt_succ_self k₂⟩ := by  simp only [DFA.evalFrom, List.foldl_append]  have h_mid := op_1293_intermediate_reset_threshold_evalFrom_replicate_a_val hab k₂ m hm q k₁  set q' := (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q (List.replicate k₁ a)  have hq' : m ≤ q'.val := by    change m ≤ ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q (List.replicate k₁ a)).val    rw [h_mid]    omega  have h_b := op_1293_intermediate_reset_threshold_evalFrom_replicate_b k₂ m a b hm (k₂ - m) q'  change (op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom q' (List.replicate (k₂ - m) b) = ⟨k₂, Nat.lt_succ_self k₂⟩  rw [h_b]  ext  rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_evalFrom_val]  rw [List.count_replicate_self]  dsimp  omega/-- Open Problem OP-1293: Every intermediate value between max(rt(A₁), rt(A₂)) and rt(A₁) + rt(A₂) is attainable as the reset threshold of the direct product of two synchronizable DFAs over an alphabet of size at least 2. -/theorem op_1293_intermediate_reset_threshold (α : Type*) [Fintype α] (hα : 2 ≤ Fintype.card α) (k₁ k₂ k : ℕ) (hk₁ : 1 ≤ k₁) (hk₂ : 1 ≤ k₂) (h_lower : max k₁ k₂ ≤ k) (h_upper : k ≤ k₁ + 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 := by  classical  have : Nontrivial α := Fintype.one_lt_card_iff_nontrivial.mp (by omega)  obtain ⟨a, b, hab⟩ := exists_pair_ne α  have hnt : Nonempty (Fin (k₁ + 1)) := ⟨0⟩  have hnt2 : Nonempty (Fin (k₂ + 1)) := ⟨0⟩  set m := k₁ + k₂ - k  have hm : m ≤ k₂ := by omega  have hmk₁ : m ≤ k₁ := by omega  set A₁ := op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA k₁ a  set A₂ := op_1293_intermediate_reset_threshold_DFA k₂ m a b hm  set w₀ := List.replicate k₁ a ++ List.replicate (k₂ - m) b  refine ⟨Fin (k₁ + 1), Fin (k₂ + 1), inferInstance, inferInstance, A₁, A₂, ?_, ?_, ?_, ?_, ?_⟩  · 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_intermediate_reset_threshold_sync_replicate_b k₂ m a b hm hk₂⟩  · exact op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_reset_threshold k₁ hk₁ a  · exact op_1293_intermediate_reset_threshold_A₂_reset_threshold k₂ m a b hm hk₂  · apply le_antisymm    · have hcounts := op_1293_product_reset_threshold_upper_bound_attained_count_replicate_append_replicate hab k₁ (k₂ - m)      have hw₀_sync1 : dfa_is_synchronizing A₁ w₀ := by        rw [op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁ a w₀]        exact le_of_eq hcounts.left.symm      have hw₀_sync2 : dfa_is_synchronizing A₂ w₀ := by        intro q₁ q₂        rw [op_1293_intermediate_reset_threshold_evalFrom_word_eq_top hab k₁ k₂ m hm hmk₁ q₁]        rw [op_1293_intermediate_reset_threshold_evalFrom_word_eq_top hab k₁ k₂ m hm hmk₁ q₂]      have hw₀_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) w₀ := by        rw [op_1293_dfa_prod_is_synchronizing_iff]        exact ⟨hw₀_sync1, hw₀_sync2⟩      have hw₀_len : w₀.length = k := by        change (List.replicate k₁ a ++ List.replicate (k₂ - m) b).length = k        rw [hcounts.right.right]        omega      have hmem : (↑w₀.length : WithTop ℕ) ∈ (fun w => (↑w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing (dfa_prod A₁ A₂) w} :=        ⟨w₀, hw₀_sync, rfl⟩      have hinf := sInf_le hmem      rw [hw₀_len] at hinf      exact hinf    · apply le_sInf      rintro b_1 ⟨w, hw, rfl⟩      change dfa_is_synchronizing (dfa_prod A₁ A₂) w at hw      rw [op_1293_dfa_prod_is_synchronizing_iff] at hw      have hw1 := (op_1293_product_reset_threshold_upper_bound_attained_letterChainDFA_is_synchronizing_iff hk₁ a w).mp hw.left      have hw2_sync := hw.right      have htop := hw2_sync 0 ⟨k₂, Nat.lt_succ_self k₂⟩      rw [op_1293_intermediate_reset_threshold_evalFrom_top] at htop      have hval : ((op_1293_intermediate_reset_threshold_DFA k₂ m a b hm).evalFrom 0 w).val = k₂ := by        rw [htop]      have hle_m := op_1293_intermediate_reset_threshold_evalFrom_zero_le_m_add_count_b k₂ m a b hm w      rw [hval] at hle_m      have htotal := op_1293_product_reset_threshold_upper_bound_attained_count_add_count_le_length hab w      have hlen : k ≤ w.length := by omega      exact WithTop.coe_le_coe.mpr hlen
See it in the graphDiscuss this resultChallenge it