dfa_seq_subset_sync_total_le_k_mul_simultaneous
For any family of k deterministic finite automata A and any sequential subset synchronization choice ws, the total length ∑ i, (ws i).length is at most k times the length of any simultaneously synchronizing word w_opt.
Statement
theorem dfa_seq_subset_sync_total_le_k_mul_simultaneous {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α) (h_choice : dfa_is_seq_subset_sync_choice A ws) (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) : (∑ i : Fin k, (ws i).length) ≤ k * w_opt.length
- Formalizes
- arXiv:2611.09136
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- dfa_is_simultaneously_synchronizingGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, and a family of deterministic finite automata A :…
- dfa_is_seq_subset_sync_choiceGiven an alphabet type α, a natural number k, a family of state types σ : Fin k → Type*, a family of deterministic finite automata A : (i…
- dfa_is_synchronizingA word
w : List αis synchronizing for a deterministic finite automatonA : DFA α σifA.evalFrom q₁ w = A.evalFrom q₂ wfor all… - dfa_is_subset_synchronizingA word
w : List αis subset-synchronizing for a subsetS : Set σof states of a deterministic finite automatonA : DFA α σif… - dfa_subset_reset_thresholdThe subset reset threshold
dfa_subset_reset_threshold A Sof a subsetSof states of a DFAAis the infimum inWithTop ℕof the…
- Used by 1
- op_1716_two_automata_subset_sync_le_two_optFor any two deterministic finite automata A (k = 2) and any two-stage sequential subset synchronization choice ws, the total length (ws…
Read back from the Lean
Given an alphabet type α, a natural number k, and state space types σ i for each i : Fin k:
For a collection of DFAs A i : DFA α (σ i) and a sequence of words ws i : List α for i : Fin k,
suppose that ws is chosen greedily by sequential subset synchronization: for each i : Fin k, letting S_i be the set of states in σ i reachable from any state via the concatenation of the preceding words ws 0, ..., ws (i - 1), the word ws i synchronizes S_i (maps all states in S_i to a single state) and has minimal length among all words that synchronize S_i for A i.
Suppose also that w_opt : List α is a simultaneously synchronizing word for the family A (for every i : Fin k, w_opt maps all states of A i to a single state).
Then the sum of the lengths of the words ws i over all i : Fin k is less than or equal to k * w_opt.length.
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
To bound the total length of the sequentially chosen words, the proof shows that each individual word ws i is at most as long as any simultaneously synchronizing word w_opt, and then sums this bound across all k automata. For each automaton A i, because w_opt synchronizes the entire automaton, it also synchronizes the subset S_i of states reachable after applying the previous words. Since ws i is chosen to attain the subset reset threshold (the minimum length of any word synchronizing S_i), its length cannot exceed that of w_opt; summing over all k automata completes the proof.
For each index i, the simultaneously synchronizing word w_opt synchronizes the state subset S_i reachable after applying the previous words.
Fix an automaton index i. By assumption, w_opt simultaneously synchronizes all automata, so it synchronizes the entire state space of A i. In particular, it synchronizes any subset of states of A i, including the subset S_i formed by the states reachable after applying the concatenation of the words chosen for previous automata ws 0, ..., ws (i - 1).
have h_le : ∀ i : Fin k, (ws i).length ≤ w_opt.length := by intro i have h_opt_i : dfa_is_synchronizing (A i) w_opt := h_opt i have h_sub : dfa_is_subset_synchronizing (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w_opt := by intro q₁ _ q₂ _ exact h_opt_i q₁ q₂
The subset reset threshold of S_i in A i is at most the length of w_opt (in ℕ ∪ {∞}).
Because w_opt synchronizes S_i, its length belongs to the set of lengths of all words synchronizing S_i (by Set.mem_image_of_mem). The subset reset threshold is defined as the infimum (sInf) of this set of lengths, so by sInf_le, the threshold is bounded above by the length of w_opt.
uses
Set.mem_image_of_mem,sInf_lehave h_len_eq := (h_choice i).2 have h_mem : (w_opt.length : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_subset_synchronizing (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w } := by exact Set.mem_image_of_mem _ h_sub have h_inf_le : dfa_subset_reset_threshold (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) ≤ (w_opt.length : WithTop ℕ) := by unfold dfa_subset_reset_threshold exact sInf_le h_mem
For each index i, the length of ws i is at most the length of w_opt as natural numbers.
By the definition of a sequential subset synchronization choice (h_choice), the length of ws i is equal to the subset reset threshold of S_i. Substituting this equality into the previous bound yields (ws i).length ≤ w_opt.length in WithTop ℕ, which unwraps to an inequality in ℕ via WithTop.coe_le_coe.mp.
uses
WithTop.coe_le_coe.mphave h_top : ((ws i).length : WithTop ℕ) ≤ (w_opt.length : WithTop ℕ) := by rw [h_len_eq] exact h_inf_le exact WithTop.coe_le_coe.mp h_top
The total length ∑ i, (ws i).length is at most k * w_opt.length.
Using Finset.sum_le_sum, we sum the inequality (ws i).length ≤ w_opt.length over all k indices in Fin k. The right-hand side is a sum of k identical terms of value w_opt.length, which simplifies to k * w_opt.length.
uses
Finset.sum_le_sumcalc (∑ i : Fin k, (ws i).length) _ ≤ ∑ i : Fin k, w_opt.length := Finset.sum_le_sum (fun i _ => h_le i) _ = k * w_opt.length := by simp
Set.mem_image_of_mem- If an element belongs to a set, its image under a function belongs to the image of that set.
sInf_le- The infimum of a set is at most any element in that set.
WithTop.coe_le_coe.mp- An inequality between natural numbers coerced to WithTop ℕ implies the corresponding inequality between the natural numbers themselves.
Finset.sum_le_sum- If one function is pointwise less than or equal to another on a finite set, the sum of the first function over that set is at most the sum of the second.
- The subset reset threshold takes values in `WithTop ℕ` (natural numbers adjoined with ∞) so that the infimum is formally well-defined; the proof coerces the resulting inequality back to ℕ using `WithTop.coe_le_coe.mp`.
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.
/-- The total length of words in any sequential subset synchronization choice for k automata is at most k times the length of any simultaneously synchronizing word. -/theorem dfa_seq_subset_sync_total_le_k_mul_simultaneous {α : Type*} {k : ℕ} {σ : Fin k → Type*} (A : (i : Fin k) → DFA α (σ i)) (ws : Fin k → List α) (h_choice : dfa_is_seq_subset_sync_choice A ws) (w_opt : List α) (h_opt : dfa_is_simultaneously_synchronizing A w_opt) : (∑ i : Fin k, (ws i).length) ≤ k * w_opt.length := by have h_le : ∀ i : Fin k, (ws i).length ≤ w_opt.length := by intro i have h_opt_i : dfa_is_synchronizing (A i) w_opt := h_opt i have h_sub : dfa_is_subset_synchronizing (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w_opt := by intro q₁ _ q₂ _ exact h_opt_i q₁ q₂ have h_len_eq := (h_choice i).2 have h_mem : (w_opt.length : WithTop ℕ) ∈ (fun w : List α => (w.length : WithTop ℕ)) '' { w | dfa_is_subset_synchronizing (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) w } := by exact Set.mem_image_of_mem _ h_sub have h_inf_le : dfa_subset_reset_threshold (A i) (Set.range (fun q : σ i => (A i).evalFrom q (((List.ofFn ws).take i.val).flatten))) ≤ (w_opt.length : WithTop ℕ) := by unfold dfa_subset_reset_threshold exact sInf_le h_mem have h_top : ((ws i).length : WithTop ℕ) ≤ (w_opt.length : WithTop ℕ) := by rw [h_len_eq] exact h_inf_le exact WithTop.coe_le_coe.mp h_top calc (∑ i : Fin k, (ws i).length) _ ≤ ∑ i : Fin k, w_opt.length := Finset.sum_le_sum (fun i _ => h_le i) _ = k * w_opt.length := by simp