period_doubling_min_factor_coverages_finset_mem
For every natural number n and every set of positions C, C belongs to period_doubling_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of the n-th period-doubling word w_n.
Statement
theorem period_doubling_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) :
C ∈ period_doubling_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (period_doubling_word n)- Source
- arXiv:2610.10950; arXiv:2602.16152
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- period_doubling_min_factor_coverages_finsetFor any natural number n, period_doubling_min_factor_coverages_finset n is the finite set of inclusion-minimal factor coverages H_min(w_n)…
- period_doubling_wordThe sequence of finite period-doubling words w_n over Bool, defined by w_0 = [false] and w_{n+1} obtained by simultaneously replacing…
- word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
- 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_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_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of w.
- Used by 2
- period_doubling_min_factor_coverages_four_cardThe cardinality of the set of inclusion-minimal factor coverages of the fourth period-doubling word w_4,…
- period_doubling_string_attractor_iff_forall_min_factor_coverageFor every natural number n and every set of positions Γ ⊆ [1, (period_doubling_word n).length], Γ is a string attractor of the n-th…
Read back from the Lean
For every natural number $n$ and every finite set of natural numbers $C$, $C$ is an element of the finite set period_doubling_min_factor_coverages_finset n if and only if $C$ is in word_min_factor_coverages (period_doubling_word n).
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 states that a finset of positions $C$ belongs to `period_doubling_min_factor_coverages_finset n` if and only if $C$ is an inclusion-minimal factor coverage of the $n$-th period-doubling word $w_n$. By definition, the finset is formed by filtering the powerset of valid positions $\{1, \dots, |w_n|\}$ by the minimal factor coverage condition. The forward implication takes the filtered condition directly, and the backward implication holds because every minimal factor coverage is the occurrence coverage of some factor, which consists entirely of positions in $\{1, \dots, |w_n|\}$.
$C \in \text{period\_doubling\_min\_factor\_coverages\_finset}(n)$ is equivalent to $C \subseteq \{1, \dots, |w_n|\}$ and $C \in \text{word\_min\_factor\_coverages}(w_n)$.
Unfold the definition of `period_doubling_min_factor_coverages_finset`, which is defined by filtering the powerset of the index interval $\{1, \dots, |w_n|\}$ by the minimal factor coverage predicate. Rewriting with `Finset.mem_filter` and `Finset.mem_powerset` expresses membership as being a subset of $\{1, \dots, |w_n|\}$ with the decidability condition evaluating to true, which simplifies via `decide_eq_true_eq` to the conjunction of the two conditions.
uses
Finset.mem_filter,Finset.mem_powerset,decide_eq_true_eqdsimp [period_doubling_min_factor_coverages_finset] rw [Finset.mem_filter, Finset.mem_powerset] simp only [decide_eq_true_eq]
In the forward direction, if $C \subseteq \{1, \dots, |w_n|\} \land C \in \text{word\_min\_factor\_coverages}(w_n)$, then $C \in \text{word\_min\_factor\_coverages}(w_n)$.
Split the bi-implication with `constructor`. Assuming the conjunction $h$, its second component immediately supplies the required membership.
constructor · intro h exact h.2
In the backward direction, if $C \in \text{word\_min\_factor\_coverages}(w_n)$, then $C \subseteq \{1, \dots, |w_n|\}$ (and hence $C$ belongs to the finset).
Assuming $C$ is a minimal factor coverage of $w_n$, we need only verify the first conjunct, $C \subseteq \{1, \dots, |w_n|\}$. By `word_min_factor_coverages_subset`, $C$ is a factor coverage, which means it is the occurrence coverage of some nonempty factor $x$ of $w_n$. By `word_occurrence_coverage_subset`, the coverage of any factor is contained in $\{1, \dots, |w_n|\}$.
uses
word_min_factor_coverages_subset,word_occurrence_coverage_subset· intro h refine ⟨?_, h⟩ have hC := word_min_factor_coverages_subset (period_doubling_word n) h rcases hC with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (period_doubling_word n) x
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base finite set and satisfies the predicate.
Finset.mem_powerset- A finite set belongs to the powerset of $t$ if and only if it is a subset of $t$.
decide_eq_true_eq- The boolean decision `decide p` is `true` if and only if the proposition $p$ holds.
word_min_factor_coverages_subset- Every inclusion-minimal factor coverage of a word is, in particular, a factor coverage of that word.
word_occurrence_coverage_subset- The set of positions covered by occurrences of a factor $x$ in a word $w$ is a subset of the index range $\{1, \dots, |w|\}$.
- In Lean, `period_doubling_min_factor_coverages_finset` is constructed as a `Finset` by filtering the powerset of positions $\{1, \dots, |w_n|\}$ to obtain a finite type, whereas mathematically, factor coverages are already defined as subsets of valid positions within 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.
/-- A set C belongs to period_doubling_min_factor_coverages_finset n iff C is an inclusion-minimal factor coverage of w_n. -/theorem period_doubling_min_factor_coverages_finset_mem (n : ℕ) (C : Finset ℕ) : C ∈ period_doubling_min_factor_coverages_finset n ↔ C ∈ word_min_factor_coverages (period_doubling_word n) := by dsimp [period_doubling_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 (period_doubling_word n) h rcases hC with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (period_doubling_word n) x