dfa_prod_reset_threshold_bounds
For any two deterministic finite automata A₁ and A₂ over the same alphabet, the reset threshold of their direct product satisfies max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) and dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂.
Statement
theorem dfa_prod_reset_threshold_bounds {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) ∧ dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂
- Formalizes
- arXiv:2611.09136 Proposition 3.4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_prod_is_synchronizing_iffA word
wis synchronizing for the direct productdfa_prod A₁ A₂of two deterministic finite automata if and only ifwis… - dfa_prod_is_synchronizing_appendIf
w₁is a synchronizing word forA₁andw₂is a synchronizing word forA₂, then the concatenated wordw₁ ++ w₂is a… - dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- dfa_reset_thresholdThe reset threshold
- Used by 3
- op_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
A₁andA₂over a common alphabet, the direct product attains the lower bound… - dfa_prod_attains_lower_bound_of_subsingletonProposition 3.13 of arXiv:2611.09136: For any two DFAs
A₁andA₂over a subsingleton (unary) alphabet, their direct product always… - 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_1291_extremal_reset_thresholds_characterizationOpen Problem OP-1291: For any synchronizable DFAs
Read back from the Lean
For any types α, σ₁, and σ₂, and any deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, the reset threshold (the length of the shortest synchronizing word in WithTop ℕ, or ⊤ if none exists) of the product automaton dfa_prod A₁ A₂ satisfies:
1. It is greater than or equal to the maximum of the reset threshold of A₁ and the reset threshold of A₂, and
2. It is less than or equal to the sum of the reset threshold of A₁ and the reset threshold of A₂.
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 establishes the lower and upper bounds on the reset threshold of a direct product automaton separately. For the lower bound, any word synchronizing A₁ × A₂ must synchronize each factor, so the set of synchronizing word lengths for the product is a subset of that for each factor, which implies the infimum threshold of the product is at least the maximum of the individual thresholds. For the upper bound, when both automata are synchronizable, concatenating minimal-length synchronizing words w₁ for A₁ and w₂ for A₂ yields a synchronizing word for A₁ × A₂ of length |w₁| + |w₂| = rt(A₁) + rt(A₂); if either automaton is not synchronizable, its threshold is +∞, making the sum +∞ and the upper bound trivial.
The lower bound max(rt(A₁), rt(A₂)) ≤ rt(A₁ × A₂) reduces to showing rt(A₁) ≤ rt(A₁ × A₂) and rt(A₂) ≤ rt(A₁ × A₂).
Splitting the main conjunction with `constructor` separates the lower bound from the upper bound. Rewriting with `max_le_iff` and unfolding the definition of reset threshold reduces the lower bound to two independent subgoals: showing that the infimum of synchronizing word lengths for each factor automaton is at most that of the direct product.
uses
max_le_iffconstructor · rw [max_le_iff] dsimp [dfa_reset_threshold] constructor
rt(A₁) ≤ rt(A₁ × A₂)
By antimonotonicity of infima (`sInf_le_sInf`), an inclusion of sets S ⊆ T implies sInf T ≤ sInf S. Any word w that synchronizes A₁ × A₂ also synchronizes A₁ by `dfa_prod_is_synchronizing_iff`, so its length belongs to the set of synchronizing lengths for A₁. Hence the set of lengths for the product is a subset of that for A₁, giving the inequality.
uses
sInf_le_sInf,dfa_prod_is_synchronizing_iff· apply sInf_le_sInf rintro - ⟨w, hw, rfl⟩ exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.1, rfl⟩
rt(A₂) ≤ rt(A₁ × A₂)
Symmetrically, any word synchronizing A₁ × A₂ synchronizes A₂ by `dfa_prod_is_synchronizing_iff`. By `sInf_le_sInf`, the infimum of synchronizing word lengths for A₂ is at most that of the product.
uses
sInf_le_sInf,dfa_prod_is_synchronizing_iff· apply sInf_le_sInf rintro - ⟨w, hw, rfl⟩ exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.2, rfl⟩
The upper bound proof splits into cases depending on whether A₁ and A₂ have synchronizing words.
We perform case analysis (`by_cases`) on whether the sets of synchronizing word lengths for A₁ and A₂ are nonempty.
· by_cases h₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty · by_cases h₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty
When both A₁ and A₂ have synchronizing words, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).
Because the sets of synchronizing lengths are nonempty subsets of ℕ ∪ {∞}, their infima are attained by elements of the sets (`csInf_mem`), giving words w₁ and w₂ that synchronize A₁ and A₂ with lengths rt(A₁) and rt(A₂). By `dfa_prod_is_synchronizing_append`, their concatenation w₁ ++ w₂ synchronizes A₁ × A₂. Its length is |w₁| + |w₂| = rt(A₁) + rt(A₂) by `List.length_append` and `Nat.cast_add`. Since sInf is bounded above by any element of the set (`sInf_le`), the upper bound follows.
uses
csInf_mem,dfa_prod_is_synchronizing_append,Nat.cast_add,List.length_append,sInf_le· obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h₁ obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h₂ have hsync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) := dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂ dsimp [dfa_reset_threshold] dsimp [dfa_reset_threshold] at heq₁ heq₂ rw [← heq₁, ← heq₂] rw [← Nat.cast_add, ← List.length_append] apply sInf_le exact ⟨w₁ ++ w₂, hsync, rfl⟩
When A₂ has no synchronizing word, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).
If A₂ has no synchronizing word, its set of synchronizing word lengths is empty (`Set.not_nonempty_iff_eq_empty`), so rt(A₂) = sInf ∅ = ⊤ (`WithTop.sInf_empty`). Since rt(A₁) + ⊤ = ⊤ (`WithTop.add_top`), the inequality rt(A₁ × A₂) ≤ ⊤ holds trivially by `le_top`.
uses
Set.not_nonempty_iff_eq_empty,WithTop.sInf_empty,WithTop.add_top,le_top· rw [Set.not_nonempty_iff_eq_empty] at h₂ dsimp [dfa_reset_threshold] rw [h₂, WithTop.sInf_empty, WithTop.add_top] exact le_top
When A₁ has no synchronizing word, rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂).
Similarly, if A₁ has no synchronizing word, its set of synchronizing lengths is empty (`Set.not_nonempty_iff_eq_empty`), giving rt(A₁) = ⊤ (`WithTop.sInf_empty`). Then ⊤ + rt(A₂) = ⊤ (`WithTop.top_add`), and the inequality holds by `le_top`.
uses
Set.not_nonempty_iff_eq_empty,WithTop.sInf_empty,WithTop.top_add,le_top· rw [Set.not_nonempty_iff_eq_empty] at h₁ dsimp [dfa_reset_threshold] rw [h₁, WithTop.sInf_empty, WithTop.top_add] exact le_top
max_le_iff- The maximum of two elements is at most c if and only if each element is at most c: max a b ≤ c ↔ a ≤ c ∧ b ≤ c.
sInf_le_sInf- If s ⊆ t, then sInf t ≤ sInf s (antimonotonicity of infima).
dfa_prod_is_synchronizing_iff- A word w synchronizes the product automaton A₁ × A₂ if and only if it synchronizes both A₁ and A₂.
csInf_mem- In a well-founded conditionally complete linear order, every nonempty set contains its infimum.
dfa_prod_is_synchronizing_append- If w₁ synchronizes A₁ and w₂ synchronizes A₂, then the concatenated word w₁ ++ w₂ synchronizes the product automaton A₁ × A₂.
Nat.cast_add- The cast from ℕ to an additive monoid with 1 preserves addition: ↑(m + n) = ↑m + ↑n.
List.length_append- The length of the concatenation of two lists is the sum of their lengths: (as ++ bs).length = as.length + bs.length.
sInf_le- An element belonging to a set is an upper bound for the set's infimum: a ∈ s → sInf s ≤ a.
Set.not_nonempty_iff_eq_empty- A set is not nonempty if and only if it is empty: ¬s.Nonempty ↔ s = ∅.
WithTop.sInf_empty- In a type with a top element ⊤, the infimum of the empty set is ⊤.
WithTop.add_top- Adding ⊤ on the right in WithTop yields ⊤: x + ⊤ = ⊤.
WithTop.top_add- Adding ⊤ on the left in WithTop yields ⊤: ⊤ + x = ⊤.
le_top- Every element is less than or equal to the top element: a ≤ ⊤.
- The reset threshold `dfa_reset_threshold` takes values in `WithTop ℕ` (natural numbers adjoined with +∞). When an automaton has no synchronizing word, the set of lengths is empty and its threshold is defined as sInf ∅ = ⊤ (+∞).
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.
/-- Reset threshold bounds for direct products of DFAs: max(rt(A₁), rt(A₂)) ≤ rt(A₁ × A₂) ≤ rt(A₁) + rt(A₂). -/theorem dfa_prod_reset_threshold_bounds {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) ∧ dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂ := by constructor · rw [max_le_iff] dsimp [dfa_reset_threshold] constructor · apply sInf_le_sInf rintro - ⟨w, hw, rfl⟩ exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.1, rfl⟩ · apply sInf_le_sInf rintro - ⟨w, hw, rfl⟩ exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw |>.2, rfl⟩ · by_cases h₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty · by_cases h₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty · obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h₁ obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h₂ have hsync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) := dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂ dsimp [dfa_reset_threshold] dsimp [dfa_reset_threshold] at heq₁ heq₂ rw [← heq₁, ← heq₂] rw [← Nat.cast_add, ← List.length_append] apply sInf_le exact ⟨w₁ ++ w₂, hsync, rfl⟩ · rw [Set.not_nonempty_iff_eq_empty] at h₂ dsimp [dfa_reset_threshold] rw [h₂, WithTop.sInf_empty, WithTop.add_top] exact le_top · rw [Set.not_nonempty_iff_eq_empty] at h₁ dsimp [dfa_reset_threshold] rw [h₁, WithTop.sInf_empty, WithTop.top_add] exact le_top