thue_morse_min_factor_coverages_finset_mem
For every n and every C, C belongs to thue_morse_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of t_n.
Statement
theorem thue_morse_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) :
C ∈ thue_morse_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (thue_morse_word n)- Source
- step towards thue_morse_random_attractor_lattice_gumbel
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- thue_morse_min_factor_coverages_finsetThe finite set of inclusion-minimal factor coverages H_min(t_n) of the n-th Thue-Morse word, realized as a Finset of subsets of the…
- word_min_factor_coverages_subsetEvery inclusion-minimal factor coverage is a factor coverage: H_min(w) ⊆ H(w).
- word_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
- word_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of w.
- thue_morse_wordThe n-th Thue-Morse word t_n over the alphabet {false, true}, defined recursively by t_0 = [false] and t_{n+1} obtained by replacing each…
- word_occurrence_coverageThe coverage Cov_w(x) of a word x in a finite word w: the union of the intervals [p, p+|x|−1] over all (1-based) occurrence starts p of x…
- word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
- Used by 1
- thue_morse_unhit_mean_nonnegFor all n and k, 0 ≤ thue_morse_unhit_mean n k.
The proof, explained
The finite set `thue_morse_min_factor_coverages_finset n` is defined by filtering the powerset of the index set $\{1, \dots, |t_n|\}$ by the decidability of being an inclusion-minimal factor coverage of the $n$-th Thue-Morse word $t_n$. Unfolding this definition reduces the equivalence to showing that any minimal factor coverage $C$ is automatically contained in $\{1, \dots, |t_n|\}$. This inclusion holds because minimal factor coverages are factor coverages (the coverages of occurrences of some factor), and all occurrence coverages in $t_n$ are bounded by the length of $t_n$.
Membership in `thue_morse_min_factor_coverages_finset n` is equivalent to $C \subseteq \{1, \dots, |t_n|\} \wedge C \in \text{word\_min\_factor\_coverages}(t_n)$, where $t_n$ is the $n$-th Thue-Morse word.
Unfolding the definition of `thue_morse_min_factor_coverages_finset` shows it is defined by filtering the powerset of $\{1, \dots, |t_n|\}$. Rewriting with `Finset.mem_filter` and `Finset.mem_powerset` turns membership in this filtered powerset into the subset condition $C \subseteq \{1, \dots, |t_n|\}$ paired with the boolean condition $\text{decide}(C \in \text{word\_min\_factor\_coverages}(t_n)) = \text{true}$. Simplifying with `decide_eq_true_eq` reduces the boolean check directly to the proposition $C \in \text{word\_min\_factor\_coverages}(t_n)$.
uses
Finset.mem_filter,Finset.mem_powerset,decide_eq_true_eqdsimp [thue_morse_min_factor_coverages_finset] rw [Finset.mem_filter, Finset.mem_powerset] simp only [decide_eq_true_eq]
If $C \subseteq \{1, \dots, |t_n|\}$ and $C \in \text{word\_min\_factor\_coverages}(t_n)$, then $C \in \text{word\_min\_factor\_coverages}(t_n)$.
We split the equivalence into both directions. For the forward direction, assuming the conjunction $C \subseteq \{1, \dots, |t_n|\} \wedge C \in \text{word\_min\_factor\_coverages}(t_n)$, the desired conclusion is simply the second conjunct.
constructor · intro h exact h.2
If $C \in \text{word\_min\_factor\_coverages}(t_n)$, then $C \subseteq \{1, \dots, |t_n|\}$ and $C \in \text{word\_min\_factor\_coverages}(t_n)$.
For the reverse direction, we assume $C \in \text{word\_min\_factor\_coverages}(t_n)$. Supplying this assumption discharges the second conjunct, leaving the goal to show $C \subseteq \{1, \dots, |t_n|\}$. By `word_min_factor_coverages_subset`, any minimal factor coverage is in particular a factor coverage. Unpacking the definition of factor coverage, $C$ must be the occurrence coverage of some nonempty factor $x$ of $t_n$. Finally, `word_occurrence_coverage_subset` guarantees that the occurrence coverage of any factor in $t_n$ is contained in the index range $\{1, \dots, |t_n|\}$.
uses
word_min_factor_coverages_subset,word_occurrence_coverage_subset· intro h refine ⟨?_, h⟩ have hC := word_min_factor_coverages_subset (thue_morse_word n) h rcases hC with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (thue_morse_word n) x
Finset.mem_filter- An element belongs to the filter of a finite set by a predicate if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_powerset- A finite set belongs to the powerset of another finite set if and only if it is a subset of that set.
decide_eq_true_eq- The decidable boolean evaluation `decide p` equals `true` if and only if the proposition `p` holds.
word_min_factor_coverages_subset- Every minimal factor coverage of a word is also a factor coverage of that word.
word_occurrence_coverage_subset- The occurrence coverage of any factor in a word is contained in the index range from 1 to the length of the word.
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.
/-- Membership in the Finset realization of H_min(t_n) is exactly membership in the set H_min(t_n). -/theorem thue_morse_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) : C ∈ thue_morse_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (thue_morse_word n) := by dsimp [thue_morse_min_factor_coverages_finset] rw [Finset.mem_filter, Finset.mem_powerset] simp only [decide_eq_true_eq] constructor · intro h exact h.2 · intro h refine ⟨?_, h⟩ have hC := word_min_factor_coverages_subset (thue_morse_word n) h rcases hC with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (thue_morse_word n) x