period_doubling_min_factor_coverages_four_card
The cardinality of the set of inclusion-minimal factor coverages of the fourth period-doubling word w_4, period_doubling_min_factor_coverages_finset 4, is equal to 8.
Statement
theorem period_doubling_min_factor_coverages_four_card :
(period_doubling_min_factor_coverages_finset 4).card = 8- Related work
- arXiv:2610.10950; arXiv:2602.16152
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- period_doubling_min_factor_coverages_finset_memFor 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…
- 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.
- word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
Read back from the Lean
The number of minimal factor coverages of the 4th period-doubling word (restricted to subsets of indices from 1 to the word's length) is equal to 8.
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 compute the cardinality of the inclusion-minimal factor coverages of the fourth period-doubling word w_4, the proof replaces the set-theoretic definition of factor coverages with an equivalent computable finite set indexed by factor start positions and lengths. It then shows that filtering this computable set for inclusion-minimal elements characterizes the minimal factor coverages. Finally, it rewrites the cardinality goal into this computable form on w_4 (a word of length 16) and concludes that the cardinality is 8 by kernel evaluation (`decide`).
Every factor coverage of a word w belongs to the computable finite set `period_doubling_min_factor_coverages_four_card_factor_finset w`.
Suppose C is the coverage of a non-empty factor x of w, so w = s ++ x ++ t. The total length of w is |s| + |x| + |t| (by `List.length_append`), and |x| > 0 because x is non-empty (by `List.length_pos_iff.mpr`). Dropping |s| elements from w and taking |x| elements retrieves x (using `List.append_assoc`, `List.drop_left`, and `List.take_left`). In the computable finite set, choosing start position i = |s| (which is strictly less than |w| by linear arithmetic, `Finset.mem_range`) and length k = |x| (which lies in [1, |w| - |s|] by `Finset.mem_Icc`) produces the coverage of x, showing C is in the big union over indices and lengths (`Finset.mem_biUnion`, `Finset.mem_image`).
uses
List.length_append,List.length_pos_iff.mpr,List.append_assoc,List.drop_left,List.take_left,period_doubling_min_factor_coverages_four_card_factor_finset,Finset.mem_biUnion,Finset.mem_range,Finset.mem_image,Finset.mem_Iccconstructor · rintro ⟨x, hxne, ⟨s, t, hst⟩, hcov⟩ subst hcov have hwlen : w.length = s.length + x.length + t.length := by rw [← hst, List.length_append, List.length_append] have hxpos : 0 < x.length := List.length_pos_iff.mpr hxne have htd : List.take x.length (List.drop s.length w) = x := by rw [← hst, List.append_assoc, List.drop_left, List.take_left] rw [period_doubling_min_factor_coverages_four_card_factor_finset, Finset.mem_biUnion] refine ⟨s.length, ?_, ?_⟩ · rw [Finset.mem_range]; omega · rw [Finset.mem_image] refine ⟨x.length, ?_, ?_⟩ · rw [Finset.mem_Icc]; omega · rw [htd]
Every element of `period_doubling_min_factor_coverages_four_card_factor_finset w` is a factor coverage of w.
Given an element C in the computable finite set, unpacking `Finset.mem_biUnion` and `Finset.mem_image` gives a start position i < |w| (from `Finset.mem_range`) and a length 1 ≤ k ≤ |w| - i (from `Finset.mem_Icc`) such that C is the coverage of x = List.take k (List.drop i w). The list x is non-empty because k ≠ 0 and List.drop i w is non-empty (its length |w| - i is at least k ≥ 1 by `List.length_drop`), using `ne_eq`, `List.take_eq_nil_iff`, and `not_or`. Furthermore, x is a factor of w since decomposing w as (List.take i w) ++ x ++ (List.drop k (List.drop i w)) reconstructs w by `List.append_assoc` and `List.take_append_drop`. Hence C is the coverage of a valid non-empty factor.
uses
period_doubling_min_factor_coverages_four_card_factor_finset,Finset.mem_biUnion,Finset.mem_image,Finset.mem_range,Finset.mem_Icc,ne_eq,List.take_eq_nil_iff,not_or,List.length_drop,List.append_assoc,List.take_append_drop· intro hC rw [period_doubling_min_factor_coverages_four_card_factor_finset, Finset.mem_biUnion] at hC obtain ⟨i, hi, hC⟩ := hC rw [Finset.mem_image] at hC obtain ⟨k, hk, rfl⟩ := hC rw [Finset.mem_range] at hi rw [Finset.mem_Icc] at hk obtain ⟨hk1, hk2⟩ := hk refine ⟨List.take k (List.drop i w), ?_, ?_, rfl⟩ · simp only [ne_eq, List.take_eq_nil_iff, not_or] refine ⟨by omega, ?_⟩ intro h have hlen : (List.drop i w).length = 0 := by rw [h]; rfl rw [List.length_drop] at hlen omega · refine ⟨List.take i w, List.drop k (List.drop i w), ?_⟩ calc List.take i w ++ List.take k (List.drop i w) ++ List.drop k (List.drop i w) = List.take i w ++ (List.take k (List.drop i w) ++ List.drop k (List.drop i w)) := List.append_assoc _ _ _ _ = List.take i w ++ List.drop i w := by rw [List.take_append_drop] _ = w := List.take_append_drop i w
A coverage C is an inclusion-minimal factor coverage of w if and only if C belongs to `period_doubling_min_factor_coverages_four_card_min_coverages w`.
By definition and `Finset.mem_filter`, `period_doubling_min_factor_coverages_four_card_min_coverages w` filters the computable factor coverage set for elements C such that any subset D in the same set must equal C. For the forward direction, if C is a minimal factor coverage, then C is in the factor finset by `period_doubling_min_factor_coverages_four_card_mem_factor`, and any subcoverage D in that finset is also a factor coverage, so D = C by minimality. The reverse direction is identical, transferring membership of C and any D between the abstract set and the computable finset via `period_doubling_min_factor_coverages_four_card_mem_factor`.
uses
period_doubling_min_factor_coverages_four_card_min_coverages,Finset.mem_filter,period_doubling_min_factor_coverages_four_card_mem_factorrw [period_doubling_min_factor_coverages_four_card_min_coverages, Finset.mem_filter] constructor · rintro ⟨hC, hmin⟩ refine ⟨(period_doubling_min_factor_coverages_four_card_mem_factor w C).mp hC, ?_⟩ intro D hD hsub exact hmin D ((period_doubling_min_factor_coverages_four_card_mem_factor w D).mpr hD) hsub · rintro ⟨hC, hmin⟩ refine ⟨(period_doubling_min_factor_coverages_four_card_mem_factor w C).mpr hC, ?_⟩ intro D hD hsub exact hmin D ((period_doubling_min_factor_coverages_four_card_mem_factor w D).mp hD) hsub
The set `period_doubling_min_factor_coverages_finset 4` equals the computable set `period_doubling_min_factor_coverages_four_card_min_coverages (period_doubling_word 4)`.
By extensionality on C, membership in `period_doubling_min_factor_coverages_finset 4` is equivalent via `period_doubling_min_factor_coverages_finset_mem` to being an inclusion-minimal factor coverage of the fourth period-doubling word w_4. By `period_doubling_min_factor_coverages_four_card_mem_min`, this is equivalent to membership in the computable minimal coverage set for w_4.
uses
period_doubling_min_factor_coverages_finset_mem,period_doubling_min_factor_coverages_four_card_mem_minext C rw [period_doubling_min_factor_coverages_finset_mem] exact period_doubling_min_factor_coverages_four_card_mem_min _ _
The number of inclusion-minimal factor coverages of the fourth period-doubling word w_4 is 8. automation
Rewriting with `period_doubling_min_factor_coverages_four_card_eq` transforms the goal into computing the cardinality of `period_doubling_min_factor_coverages_four_card_min_coverages (period_doubling_word 4)`. Because this set is fully computable and w_4 has concrete length 16, Lean evaluates the cardinality to 8 by computational reflection using `decide`.
uses
period_doubling_min_factor_coverages_four_card_eqrw [period_doubling_min_factor_coverages_four_card_eq] decide
List.append_assoc- Concatenation of lists is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
List.drop_left- Dropping the length of the first list from a concatenated list yields the second list.
Finset.mem_filter- An element is in a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_image- An element is in the image of a function on a finite set if and only if it is the image of some element in that set.
Finset.mem_Icc- An element x is in the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_biUnion- An element belongs to a indexed union of finite sets if and only if it belongs to one of the components.
Finset.mem_range- A natural number m belongs to range n if and only if m < n.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_drop- Dropping i elements from a list gives a list whose length is the original length minus i.
List.length_pos_iff.mpr- A list is non-empty if and only if its length is strictly positive.
List.take_append_drop- Concatenating the prefix of length i of a list with the suffix after dropping i elements yields the original list.
List.take_eq_nil_iff- Taking k elements from a list gives the empty list if and only if k = 0 or the list is empty.
List.take_left- Taking the length of the first list from a concatenated list yields the first list.
ne_eq- The inequality a ≠ b is defined as the negation of equality ¬(a = b).
not_or- The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
period_doubling_min_factor_coverages_four_card_factor_finset- The computable finite set of factor coverages of a word w, obtained by taking occurrences of non-empty factors indexed by start position and length.
period_doubling_min_factor_coverages_four_card_mem_factor- A set of indices is a factor coverage of a word w if and only if it belongs to the computable finite set of factor coverages of w.
period_doubling_min_factor_coverages_four_card_min_coverages- The computable finite set of inclusion-minimal elements in the computable set of factor coverages of w.
period_doubling_min_factor_coverages_four_card_mem_min- A set of indices is an inclusion-minimal factor coverage of w if and only if it belongs to the computable set of minimal factor coverages of w.
period_doubling_min_factor_coverages_four_card_eq- The finite set of minimal factor coverages of the fourth period-doubling word equals the computable set of minimal coverages of that word.
period_doubling_min_factor_coverages_finset_mem- A set of indices belongs to the finite set of minimal factor coverages of the n-th period-doubling word if and only if it is an inclusion-minimal factor coverage.
- The final cardinality evaluation on line 79 relies entirely on computational reflection (`decide`) in Lean's kernel, which exhaustively checks the 83 factor coverages of the 16-character word w_4 and determines that exactly 8 are inclusion-minimal.
- The finite set definitions `period_doubling_min_factor_coverages_four_card_factor_finset` and `period_doubling_min_factor_coverages_four_card_min_coverages` are introduced solely to make the set of factor coverages computable, allowing `decide` to run.
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.
private def period_doubling_min_factor_coverages_four_card_factor_finset {α : Type*} [DecidableEq α] (w : List α) : Finset (Finset ℕ) := (Finset.range w.length).biUnion fun i => (Finset.Icc 1 (w.length - i)).image fun k => word_occurrence_coverage w (List.take k (List.drop i w))private lemma period_doubling_min_factor_coverages_four_card_mem_factor {α : Type*} [DecidableEq α] (w : List α) (C : Finset ℕ) : C ∈ word_factor_coverages w ↔ C ∈ period_doubling_min_factor_coverages_four_card_factor_finset w := by constructor · rintro ⟨x, hxne, ⟨s, t, hst⟩, hcov⟩ subst hcov have hwlen : w.length = s.length + x.length + t.length := by rw [← hst, List.length_append, List.length_append] have hxpos : 0 < x.length := List.length_pos_iff.mpr hxne have htd : List.take x.length (List.drop s.length w) = x := by rw [← hst, List.append_assoc, List.drop_left, List.take_left] rw [period_doubling_min_factor_coverages_four_card_factor_finset, Finset.mem_biUnion] refine ⟨s.length, ?_, ?_⟩ · rw [Finset.mem_range]; omega · rw [Finset.mem_image] refine ⟨x.length, ?_, ?_⟩ · rw [Finset.mem_Icc]; omega · rw [htd] · intro hC rw [period_doubling_min_factor_coverages_four_card_factor_finset, Finset.mem_biUnion] at hC obtain ⟨i, hi, hC⟩ := hC rw [Finset.mem_image] at hC obtain ⟨k, hk, rfl⟩ := hC rw [Finset.mem_range] at hi rw [Finset.mem_Icc] at hk obtain ⟨hk1, hk2⟩ := hk refine ⟨List.take k (List.drop i w), ?_, ?_, rfl⟩ · simp only [ne_eq, List.take_eq_nil_iff, not_or] refine ⟨by omega, ?_⟩ intro h have hlen : (List.drop i w).length = 0 := by rw [h]; rfl rw [List.length_drop] at hlen omega · refine ⟨List.take i w, List.drop k (List.drop i w), ?_⟩ calc List.take i w ++ List.take k (List.drop i w) ++ List.drop k (List.drop i w) = List.take i w ++ (List.take k (List.drop i w) ++ List.drop k (List.drop i w)) := List.append_assoc _ _ _ _ = List.take i w ++ List.drop i w := by rw [List.take_append_drop] _ = w := List.take_append_drop i wprivate def period_doubling_min_factor_coverages_four_card_min_coverages {α : Type*} [DecidableEq α] (w : List α) : Finset (Finset ℕ) := (period_doubling_min_factor_coverages_four_card_factor_finset w).filter fun C => ∀ D ∈ period_doubling_min_factor_coverages_four_card_factor_finset w, D ⊆ C → D = Cprivate lemma period_doubling_min_factor_coverages_four_card_mem_min {α : Type*} [DecidableEq α] (w : List α) (C : Finset ℕ) : C ∈ word_min_factor_coverages w ↔ C ∈ period_doubling_min_factor_coverages_four_card_min_coverages w := by rw [period_doubling_min_factor_coverages_four_card_min_coverages, Finset.mem_filter] constructor · rintro ⟨hC, hmin⟩ refine ⟨(period_doubling_min_factor_coverages_four_card_mem_factor w C).mp hC, ?_⟩ intro D hD hsub exact hmin D ((period_doubling_min_factor_coverages_four_card_mem_factor w D).mpr hD) hsub · rintro ⟨hC, hmin⟩ refine ⟨(period_doubling_min_factor_coverages_four_card_mem_factor w C).mpr hC, ?_⟩ intro D hD hsub exact hmin D ((period_doubling_min_factor_coverages_four_card_mem_factor w D).mp hD) hsubprivate lemma period_doubling_min_factor_coverages_four_card_eq : period_doubling_min_factor_coverages_finset 4 = period_doubling_min_factor_coverages_four_card_min_coverages (period_doubling_word 4) := by ext C rw [period_doubling_min_factor_coverages_finset_mem] exact period_doubling_min_factor_coverages_four_card_mem_min _ _/-- The number of inclusion-minimal factor coverages of the 4th period-doubling word w_4 is 8. -/theorem period_doubling_min_factor_coverages_four_card : (period_doubling_min_factor_coverages_finset 4).card = 8 := by rw [period_doubling_min_factor_coverages_four_card_eq] decide