op_1291_extremal_reset_thresholds_characterization
Open Problem OP-1291: For any synchronizable DFAs A₁ and A₂ over a common alphabet, the direct product attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) if and only if there exists a word synchronizing both A₁ and A₂ of length at most max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂), and attains the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂ if and only if every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂.
Statement
theorem op_1291_extremal_reset_thresholds_characterization {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (h₁ : dfa_is_synchronizable A₁) (h₂ : dfa_is_synchronizable A₂) : (dfa_prod_attains_lower_bound A₁ A₂ ↔ ∃ w : List α, dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w ∧ (w.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)) ∧ (dfa_prod_attains_upper_bound A₁ A₂ ↔ ∀ w : List α, dfa_is_synchronizing A₁ w → dfa_is_synchronizing A₂ w → dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ))
- Formalizes
- arXiv:2611.09136 Sec. 7, open question 1
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_prod_attains_upper_boundA pair of DFAs
A₁andA₂over the same alphabet attains the upper bound of Proposition 3.4 if the reset threshold of their direct… - dfa_is_synchronizableA deterministic finite automaton
A : DFA α σis synchronizable if there exists a synchronizing wordw : List αforA. - 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
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_prod_reset_threshold_boundsFor any two deterministic finite automata
A₁andA₂over the same alphabet, the reset threshold of their direct product satisfies…
- dfa_prod_attains_lower_boundA pair of DFAs
Read back from the Lean
For all types α, σ₁, and σ₂, and all deterministic finite automata A₁ : DFA α σ₁ and A₂ : DFA α σ₂, assuming that A₁ is synchronizable (there exists a word synchronizing A₁) and A₂ is synchronizable (there exists a word synchronizing A₂), both of the following equivalences hold:
1. The reset threshold of the product automaton dfa_prod A₁ A₂ attains the lower bound max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) if and only if there exists a word w : List α that synchronizes both A₁ and A₂ whose length (in WithTop ℕ) is at most max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂).
2. The reset threshold of the product automaton dfa_prod A₁ A₂ attains the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂ if and only if for every word w : List α, if w synchronizes A₁ and w synchronizes A₂, then dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ).
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 theorem characterizes when the direct product A₁ × A₂ of two synchronizable DFAs achieves the extremal reset threshold bounds established in Proposition 3.4. For the lower bound max(dfa_reset_threshold A₁, dfa_reset_threshold A₂), the forward direction uses the well-foundedness of WithTop ℕ to obtain a minimal-length synchronizing word for the product, which simultaneously synchronizes both automata; the reverse direction observes that any common synchronizing word witnesses an upper bound on the infimum. For the upper bound dfa_reset_threshold A₁ + dfa_reset_threshold A₂, both directions use the fact that synchronizing the product is equivalent to synchronizing both factors, converting the equality into the condition that the threshold sum is a lower bound for every common synchronizing word.
The proof reduces to establishing the equivalence for the lower bound and the equivalence for the upper bound independently, starting with the forward implication of the lower bound.
We split the conjunction into two subgoals for the lower and upper bounds, and then split the lower-bound biconditional into forward and backward implications.
constructor · constructor
If the direct product attains the lower bound, then there exists a word synchronizing both A₁ and A₂ of length at most max(dfa_reset_threshold A₁, dfa_reset_threshold A₂).
Assuming the product attains the lower bound, we find an optimal synchronizing word for the product. Since A₁ and A₂ are synchronizable with words w₁ and w₂, the concatenation w₁ ++ w₂ synchronizes the product by `dfa_prod_is_synchronizing_append`, so the set of lengths of synchronizing words of the product is nonempty. By `csInf_mem`, the infimum of this nonempty set is attained by some word w, which synchronizes both A₁ and A₂ by `dfa_prod_is_synchronizing_iff`. Since w achieves the infimum, its length equals the product reset threshold, which by hypothesis equals max(dfa_reset_threshold A₁, dfa_reset_threshold A₂).
uses
dfa_prod_is_synchronizing_append,csInf_mem,dfa_prod_is_synchronizing_iff· intro h obtain ⟨w₁, hw₁⟩ := h₁ obtain ⟨w₂, hw₂⟩ := h₂ have h_prod_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) := dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂ have h_nonempty : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing (dfa_prod A₁ A₂) w}).Nonempty := ⟨↑(w₁ ++ w₂).length, ⟨w₁ ++ w₂, h_prod_sync, rfl⟩⟩ have h_mem := csInf_mem h_nonempty obtain ⟨w, hw, heq⟩ := h_mem have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw refine ⟨w, hw'.1, hw'.2, ?_⟩ change dfa_reset_threshold (dfa_prod A₁ A₂) = max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) at h change (w.length : WithTop ℕ) = dfa_reset_threshold (dfa_prod A₁ A₂) at heq rw [heq, h]
If there exists a word synchronizing both A₁ and A₂ of length at most max(dfa_reset_threshold A₁, dfa_reset_threshold A₂), then the direct product attains the lower bound.
Given a common synchronizing word w, it synchronizes the product by `dfa_prod_is_synchronizing_iff`. As the reset threshold is the infimum of synchronizing word lengths, dfa_reset_threshold (dfa_prod A₁ A₂) ≤ |w| by `sInf_le`. Composing this with |w| ≤ max(dfa_reset_threshold A₁, dfa_reset_threshold A₂) via `le_trans` gives dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max(dfa_reset_threshold A₁, dfa_reset_threshold A₂). Since the reverse inequality max(...) ≤ dfa_reset_threshold (dfa_prod A₁ A₂) is always valid by `dfa_prod_reset_threshold_bounds`, the two values are equal by `le_antisymm`.
uses
dfa_prod_is_synchronizing_iff,sInf_le,le_trans,dfa_prod_reset_threshold_bounds,le_antisymm· intro ⟨w, hw₁, hw₂, hw_le⟩ have h_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w, h_sync, rfl⟩ have h_trans : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := le_trans h_le hw_le have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1 exact le_antisymm h_trans h_bound
Unfolding definitions and recording the known upper bound dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂, it suffices to establish both directions of the upper-bound equivalence.
We unfold the definitions of attaining the upper bound and of reset threshold as an infimum. We extract the known bound dfa_reset_threshold (dfa_prod A₁ A₂) ≤ dfa_reset_threshold A₁ + dfa_reset_threshold A₂ from `dfa_prod_reset_threshold_bounds`, and split the equivalence into forward and backward implications.
uses
dfa_prod_reset_threshold_bounds· dsimp [dfa_prod_attains_upper_bound, dfa_reset_threshold] have h_le := (dfa_prod_reset_threshold_bounds A₁ A₂).2 dsimp [dfa_reset_threshold] at h_le constructor
If the direct product attains the upper bound, then every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂.
Assuming the product attains the upper bound, the threshold sum equals dfa_reset_threshold (dfa_prod A₁ A₂). If w synchronizes both A₁ and A₂, it synchronizes the product by `dfa_prod_is_synchronizing_iff`. Because the reset threshold is the infimum of all product synchronizing word lengths, it is at most |w| by `sInf_le`, which yields the desired lower bound on |w|.
uses
sInf_le,dfa_prod_is_synchronizing_iff· intro h w hw₁ hw₂ rw [← h] apply sInf_le exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩, rfl⟩
If every word synchronizing both A₁ and A₂ has length at least dfa_reset_threshold A₁ + dfa_reset_threshold A₂, then the direct product attains the upper bound.
Since the product reset threshold is already bounded above by the threshold sum, by `le_antisymm` it suffices to show that the sum is at most the product reset threshold. By `le_sInf_iff`, a value is less than or equal to an infimum if and only if it is bounded by every element in the set. Any element in the set is the length of some synchronizing word w for the product, which synchronizes both A₁ and A₂ by `dfa_prod_is_synchronizing_iff`. By hypothesis, the length of any such w is at least the sum of the thresholds.
uses
le_antisymm,le_sInf_iff,dfa_prod_is_synchronizing_iff· intro h apply le_antisymm h_le rw [le_sInf_iff] rintro - ⟨w, hw, rfl⟩ have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw exact h w hw'.1 hw'.2
dfa_prod_is_synchronizing_append- If w₁ synchronizes DFA A₁ and w₂ synchronizes DFA A₂, then the concatenation w₁ ++ w₂ synchronizes their direct product A₁ × A₂.
csInf_mem- In a conditionally complete linear order with a well-founded order relation, every nonempty set contains its infimum.
dfa_prod_is_synchronizing_iff- A word synchronizes the direct product A₁ × A₂ if and only if it synchronizes both A₁ and A₂.
sInf_le- The infimum of a set is less than or equal to every element of that set.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
dfa_prod_reset_threshold_bounds- For any two DFAs A₁ and A₂, the reset threshold of their direct product is at least max(reset threshold of A₁, reset threshold of A₂) and at most the sum of their reset thresholds.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
le_sInf_iff- An element a is less than or equal to the infimum of a set s if and only if a ≤ b for all b ∈ s.
- The reset threshold is defined as an infimum (`sInf`) over lengths in `WithTop ℕ`. Because the natural numbers with infinity have a well-founded order (`WellFoundedLT`), any nonempty set of lengths contains its infimum (`csInf_mem`), ensuring that whenever an automaton is synchronizable, there is an actual word whose length equals the reset threshold.
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.
/-- Characterization of when the direct product of two DFAs attains the lower and upper reset threshold bounds of Proposition 3.4. -/theorem op_1291_extremal_reset_thresholds_characterization {α σ₁ σ₂ : Type*} (A₁ : DFA α σ₁) (A₂ : DFA α σ₂) (h₁ : dfa_is_synchronizable A₁) (h₂ : dfa_is_synchronizable A₂) : (dfa_prod_attains_lower_bound A₁ A₂ ↔ ∃ w : List α, dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w ∧ (w.length : WithTop ℕ) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂)) ∧ (dfa_prod_attains_upper_bound A₁ A₂ ↔ ∀ w : List α, dfa_is_synchronizing A₁ w → dfa_is_synchronizing A₂ w → dfa_reset_threshold A₁ + dfa_reset_threshold A₂ ≤ (w.length : WithTop ℕ)) := by constructor · constructor · intro h obtain ⟨w₁, hw₁⟩ := h₁ obtain ⟨w₂, hw₂⟩ := h₂ have h_prod_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) (w₁ ++ w₂) := dfa_prod_is_synchronizing_append A₁ A₂ w₁ w₂ hw₁ hw₂ have h_nonempty : ((fun w : List α => (w.length : WithTop ℕ)) '' {w | dfa_is_synchronizing (dfa_prod A₁ A₂) w}).Nonempty := ⟨↑(w₁ ++ w₂).length, ⟨w₁ ++ w₂, h_prod_sync, rfl⟩⟩ have h_mem := csInf_mem h_nonempty obtain ⟨w, hw, heq⟩ := h_mem have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw refine ⟨w, hw'.1, hw'.2, ?_⟩ change dfa_reset_threshold (dfa_prod A₁ A₂) = max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) at h change (w.length : WithTop ℕ) = dfa_reset_threshold (dfa_prod A₁ A₂) at heq rw [heq, h] · intro ⟨w, hw₁, hw₂, hw_le⟩ have h_sync : dfa_is_synchronizing (dfa_prod A₁ A₂) w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩ have h_le : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ (w.length : WithTop ℕ) := by dsimp [dfa_reset_threshold] exact sInf_le ⟨w, h_sync, rfl⟩ have h_trans : dfa_reset_threshold (dfa_prod A₁ A₂) ≤ max (dfa_reset_threshold A₁) (dfa_reset_threshold A₂) := le_trans h_le hw_le have h_bound := (dfa_prod_reset_threshold_bounds A₁ A₂).1 exact le_antisymm h_trans h_bound · dsimp [dfa_prod_attains_upper_bound, dfa_reset_threshold] have h_le := (dfa_prod_reset_threshold_bounds A₁ A₂).2 dsimp [dfa_reset_threshold] at h_le constructor · intro h w hw₁ hw₂ rw [← h] apply sInf_le exact ⟨w, (dfa_prod_is_synchronizing_iff A₁ A₂ w).mpr ⟨hw₁, hw₂⟩, rfl⟩ · intro h apply le_antisymm h_le rw [le_sInf_iff] rintro - ⟨w, hw, rfl⟩ have hw' : dfa_is_synchronizing A₁ w ∧ dfa_is_synchronizing A₂ w := (dfa_prod_is_synchronizing_iff A₁ A₂ w).mp hw exact h w hw'.1 hw'.2