dfa_prod_attains_lower_bound_of_subsingleton
Proposition 3.13 of arXiv:2611.09136: For any two DFAs A₁ and A₂ over a subsingleton (unary) alphabet, their direct product always attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) on its reset threshold.
Statement
theorem dfa_prod_attains_lower_bound_of_subsingleton {α σ₁ σ₂ : Type*} [Subsingleton α] (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : dfa_prod_attains_lower_bound A₁ A₂
- Formalizes
- arXiv:2611.09136 Proposition 3.13
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- dfa_prod_attains_lower_boundA pair of DFAs
A₁andA₂over the same alphabet attains the lower bound of Proposition 3.4 if the reset threshold of their direct… - dfa_reset_thresholdThe reset threshold
dfa_reset_threshold Aof a deterministic finite automatonA : DFA α σis the infimum inWithTop ℕof the lengths… - dfa_prod_reset_threshold_boundsFor any two deterministic finite automata
A₁andA₂over the same alphabet, the reset threshold of their direct product satisfies… - 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_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all…
- dfa_prod_attains_lower_boundA pair of DFAs
Read back from the Lean
For any types α, σ₁, and σ₂ where α is a subsingleton (i.e. an alphabet with at most one symbol), and for any DFAs A₁ (with state type σ₁ over alphabet α) and A₂ (with state type σ₂ over alphabet α), the reset threshold of their product DFA dfa_prod A₁ A₂ equals the maximum 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 lower bound max(threshold(A₁), threshold(A₂)) ≤ threshold(A₁ × A₂) holds in general for direct products of DFAs. Over a subsingleton (unary) alphabet, any word at least as long as a synchronizing word is also synchronizing, because any longer word is formed simply by appending a suffix. If either automaton cannot be synchronized, both sides equal ∞. Otherwise, choosing minimal synchronizing words w₁ for A₁ and w₂ for A₂, the longer of the two synchronizes both automata simultaneously, yielding a synchronizing word for the product automaton of length max(|w₁|, |w₂|) and matching the lower bound.
Appending any suffix to a synchronizing word yields another synchronizing word.
For any two states q₁ and q₂, evaluating the DFA on w ++ v decomposes by `DFA.evalFrom_of_append` into evaluating w to reach intermediate states, followed by v. Since w synchronizes the DFA, the two intermediate states are identical, and running v from the same state produces the same final state.
uses
DFA.evalFrom_of_appendintro q₁ q₂ simp only [DFA.evalFrom_of_append] rw [hw q₁ q₂]
Over a subsingleton alphabet, any word l₂ with |l₁| ≤ |l₂| equals l₁ concatenated with the suffix of l₂ after the first |l₁| elements.
The prefix of l₂ of length |l₁| has length |l₁| by `List.length_take` and matches l₁ elementwise by `Subsingleton.elim` because the alphabet has at most one element, so `List.ext_get` identifies this prefix with l₁. Substituting this into the list partition identity `List.take_append_drop` proves the equality.
uses
List.ext_get,Subsingleton.elim,List.length_take,List.take_append_drophave htake : l₂.take l₁.length = l₁ := by refine List.ext_get ?_ (fun n h₁ h₂ => Subsingleton.elim _ _) simp [List.length_take, h] conv_lhs => rw [← List.take_append_drop l₁.length l₂] rw [htake]
Over a subsingleton alphabet, if l₁ is synchronizing and |l₁| ≤ |l₂|, then l₂ is also synchronizing.
By `dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop`, l₂ decomposes as l₁ followed by a suffix. Since l₁ synchronizes the DFA, appending this suffix also yields a synchronizing word by `dfa_prod_attains_lower_bound_of_subsingleton_append_right`.
uses
dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop,dfa_prod_attains_lower_bound_of_subsingleton_append_rightrw [dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop l₁ l₂ h] exact dfa_prod_attains_lower_bound_of_subsingleton_append_right A l₁ (l₂.drop l₁.length) hw
Unfolding definitions, it suffices to prove equality of thresholds, and the lower bound max(threshold(A₁), threshold(A₂)) ≤ threshold(A₁ × A₂) already holds.
The definition `dfa_prod_attains_lower_bound` is simplified to equality between the product threshold and the maximum of the component thresholds. The general lower bound on the direct product reset threshold is provided by `dfa_prod_reset_threshold_bounds`.
uses
dfa_prod_reset_threshold_boundsdsimp [dfa_prod_attains_lower_bound] have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1
If threshold(A₁) = ⊤, the product DFA also has reset threshold ⊤, satisfying the equality.
When threshold(A₁) = ⊤, the lower bound max(threshold(A₁), threshold(A₂)) simplifies to ⊤ by `max_top_left`. Since ⊤ ≤ threshold(A₁ × A₂), `top_le_iff.mp` forces the product threshold to be ⊤.
uses
max_top_left,top_le_iff.mpby_cases h₁ : dfa_reset_threshold A₁ = ⊤ · rw [h₁, max_top_left] at h_bound ⊢ exact top_le_iff.mp h_bound
If threshold(A₂) = ⊤, the product DFA also has reset threshold ⊤, satisfying the equality.
Similarly, if threshold(A₂) = ⊤, the lower bound simplifies to ⊤ by `max_top_right`, which implies threshold(A₁ × A₂) = ⊤ by `top_le_iff.mp`.
uses
max_top_right,top_le_iff.mpby_cases h₂ : dfa_reset_threshold A₂ = ⊤ · rw [h₂, max_top_right] at h_bound ⊢ exact top_le_iff.mp h_bound
The set of lengths of synchronizing words for A₁ is nonempty.
If this set were empty, its infimum in WithTop ℕ would be ⊤ by `WithTop.sInf_empty` (via `Set.not_nonempty_iff_eq_empty`), contradicting the assumption that threshold(A₁) ≠ ⊤.
uses
Set.not_nonempty_iff_eq_empty,WithTop.sInf_emptyhave h_ne₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty := by dsimp [dfa_reset_threshold] at h₁ by_contra he rw [Set.not_nonempty_iff_eq_empty] at he rw [he, WithTop.sInf_empty] at h₁ exact h₁ rfl
The set of lengths of synchronizing words for A₂ is nonempty.
Identically, if the set of lengths of synchronizing words for A₂ were empty, its infimum would be ⊤, contradicting threshold(A₂) ≠ ⊤.
uses
Set.not_nonempty_iff_eq_empty,WithTop.sInf_emptyhave h_ne₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty := by dsimp [dfa_reset_threshold] at h₂ by_contra he rw [Set.not_nonempty_iff_eq_empty] at he rw [he, WithTop.sInf_empty] at h₂ exact h₂ rfl
There exist minimal synchronizing words w₁ for A₁ and w₂ for A₂ realizing the respective thresholds, and it suffices to show threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).
By `csInf_mem`, nonempty sets in ℕ attain their infimum, yielding synchronizing words w₁ and w₂ of lengths equal to threshold(A₁) and threshold(A₂). Combined with the existing lower bound, antisymmetry (`le_antisymm`) reduces the problem to establishing the upper bound threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).
uses
csInf_mem,le_antisymmobtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h_ne₁ obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h_ne₂ dsimp only at heq₁ heq₂ apply le_antisymm _ h_bound
In the case |w₁| ≤ |w₂|, threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|).
Comparing lengths using `le_total`, assume |w₁| ≤ |w₂|. Since w₁ synchronizes A₁, the longer word w₂ also synchronizes A₁ by `dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le`. Since w₂ synchronizes both A₁ and A₂, it synchronizes the product A₁ × A₂ by `dfa_prod_is_synchronizing_iff`. By `sInf_le`, the product threshold is at most |w₂|, which is at most max(threshold(A₁), threshold(A₂)) by `le_max_right`, completing this branch via `le_trans`.
uses
dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le,dfa_prod_is_synchronizing_iff,le_max_right,le_total,le_trans,sInf_lercases le_total w₁.length w₂.length with hle | hle · have hsync₁ : dfa_is_synchronizing A₁ w₂ := dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₁ w₁ w₂ hw₁ hle have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₂ := (dfa_prod_is_synchronizing_iff A₁ A₂ w₂).mpr ⟨hsync₁, hw₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₂.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w₂, hprod, rfl⟩ have hmax : (w₂.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by rw [heq₂] exact le_max_right _ _ exact le_trans h_le hmax
In the case |w₂| ≤ |w₁|, threshold(A₁ × A₂) ≤ max(|w₁|, |w₂|), completing the proof.
Symmetrically, when |w₂| ≤ |w₁|, w₁ synchronizes A₂ by `dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le`, so w₁ synchronizes A₁ × A₂ by `dfa_prod_is_synchronizing_iff`. Then threshold(A₁ × A₂) ≤ |w₁| by `sInf_le`, and |w₁| ≤ max(threshold(A₁), threshold(A₂)) by `le_max_left`, completing the proof via `le_trans`.
uses
dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le,dfa_prod_is_synchronizing_iff,le_max_left,le_trans,sInf_le· have hsync₂ : dfa_is_synchronizing A₂ w₁ := dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₂ w₂ w₁ hw₂ hle have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₁ := (dfa_prod_is_synchronizing_iff A₁ A₂ w₁).mpr ⟨hw₁, hsync₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₁.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w₁, hprod, rfl⟩ have hmax : (w₁.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by rw [heq₁] exact le_max_left _ _ exact le_trans h_le hmax
DFA.evalFrom_of_append- Evaluating a DFA from a state on the concatenation w ++ v is equal to evaluating on v from the state reached after w.
List.ext_get- Two lists are equal if they have the same length and their elements at each position are equal.
List.length_take- Taking i elements from a list yields a prefix of length min(i, length of list).
List.take_append_drop- A list is equal to its prefix of length i concatenated with its suffix after index i.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
WithTop.sInf_empty- In ℕ ∪ {∞}, the infimum of the empty set is ⊤.
csInf_mem- Any nonempty set of natural numbers contains its infimum (the infimum is attained).
dfa_prod_attains_lower_bound_of_subsingleton_append_right- Appending any suffix to a synchronizing word for a DFA yields another synchronizing word.
dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop- Over a subsingleton alphabet, if |l₁| ≤ |l₂|, then l₂ equals l₁ concatenated with the suffix of l₂ after the first |l₁| elements.
dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le- Over a subsingleton alphabet, if l₁ is synchronizing and |l₁| ≤ |l₂|, then l₂ is also synchronizing.
dfa_prod_is_synchronizing_iff- A word synchronizes a direct product DFA if and only if it synchronizes both factor DFAs.
dfa_prod_reset_threshold_bounds- The reset threshold of a direct product DFA is at least the maximum of the thresholds of its factors and at most their sum.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
le_max_left- In a linear order, a ≤ max(a, b).
le_max_right- In a linear order, b ≤ max(a, b).
le_total- In a linear order, any two elements are comparable: a ≤ b or b ≤ a.
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
max_top_left- The maximum of ⊤ and any element a is ⊤.
max_top_right- The maximum of any element a and ⊤ is ⊤.
sInf_le- The infimum of a set is less than or equal to any element in the set.
Set.not_nonempty_iff_eq_empty- A set is not nonempty if and only if it is empty.
top_le_iff.mp- In an order with a greatest element ⊤, if ⊤ ≤ x then x = ⊤.
- In Lean, reset thresholds take values in `WithTop ℕ`, which includes an infinite element $\top$ representing that no synchronizing word exists. The proof explicitly handles the infinite cases first to ensure the sets of synchronizing word lengths are nonempty and achieve their infima.
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.
lemma dfa_prod_attains_lower_bound_of_subsingleton_append_right {α σ : Type*} (A : DFA α σ) (w v : List α) (hw : dfa_is_synchronizing A w) : dfa_is_synchronizing A (w ++ v) := by intro q₁ q₂ simp only [DFA.evalFrom_of_append] rw [hw q₁ q₂]lemma dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop {α : Type*} [Subsingleton α] (l₁ l₂ : List α) (h : l₁.length ≤ l₂.length) : l₂ = l₁ ++ l₂.drop l₁.length := by have htake : l₂.take l₁.length = l₁ := by refine List.ext_get ?_ (fun n h₁ h₂ => Subsingleton.elim _ _) simp [List.length_take, h] conv_lhs => rw [← List.take_append_drop l₁.length l₂] rw [htake]lemma dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le {α σ : Type*} [Subsingleton α] (A : DFA α σ) (l₁ l₂ : List α) (hw : dfa_is_synchronizing A l₁) (h : l₁.length ≤ l₂.length) : dfa_is_synchronizing A l₂ := by rw [dfa_prod_attains_lower_bound_of_subsingleton_eq_append_drop l₁ l₂ h] exact dfa_prod_attains_lower_bound_of_subsingleton_append_right A l₁ (l₂.drop l₁.length) hw/-- Direct products of DFAs over a subsingleton alphabet always attain the lower bound on the reset threshold. -/theorem dfa_prod_attains_lower_bound_of_subsingleton {α σ₁ σ₂ : Type*} [Subsingleton α] (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) : dfa_prod_attains_lower_bound A₁ A₂ := by dsimp [dfa_prod_attains_lower_bound] have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1 by_cases h₁ : dfa_reset_threshold A₁ = ⊤ · rw [h₁, max_top_left] at h_bound ⊢ exact top_le_iff.mp h_bound by_cases h₂ : dfa_reset_threshold A₂ = ⊤ · rw [h₂, max_top_right] at h_bound ⊢ exact top_le_iff.mp h_bound have h_ne₁ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₁ w}).Nonempty := by dsimp [dfa_reset_threshold] at h₁ by_contra he rw [Set.not_nonempty_iff_eq_empty] at he rw [he, WithTop.sInf_empty] at h₁ exact h₁ rfl have h_ne₂ : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing A₂ w}).Nonempty := by dsimp [dfa_reset_threshold] at h₂ by_contra he rw [Set.not_nonempty_iff_eq_empty] at he rw [he, WithTop.sInf_empty] at h₂ exact h₂ rfl obtain ⟨w₁, hw₁, heq₁⟩ := csInf_mem h_ne₁ obtain ⟨w₂, hw₂, heq₂⟩ := csInf_mem h_ne₂ dsimp only at heq₁ heq₂ apply le_antisymm _ h_bound rcases le_total w₁.length w₂.length with hle | hle · have hsync₁ : dfa_is_synchronizing A₁ w₂ := dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₁ w₁ w₂ hw₁ hle have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₂ := (dfa_prod_is_synchronizing_iff A₁ A₂ w₂).mpr ⟨hsync₁, hw₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₂.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w₂, hprod, rfl⟩ have hmax : (w₂.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by rw [heq₂] exact le_max_right _ _ exact le_trans h_le hmax · have hsync₂ : dfa_is_synchronizing A₂ w₁ := dfa_prod_attains_lower_bound_of_subsingleton_sync_of_le A₂ w₂ w₁ hw₂ hle have hprod : dfa_is_synchronizing (dfa_prod A₁ A₂) w₁ := (dfa_prod_is_synchronizing_iff A₁ A₂ w₁).mpr ⟨hw₁, hsync₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w₁.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w₁, hprod, rfl⟩ have hmax : (w₁.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := by rw [heq₁] exact le_max_left _ _ exact le_trans h_le hmax