period_doubling_min_factor_coverages_three_card
The cardinality of the set of inclusion-minimal factor coverages of the third period-doubling word w_3, period_doubling_min_factor_coverages_finset 3, is equal to 6.
Statement
theorem period_doubling_min_factor_coverages_three_card :
(period_doubling_min_factor_coverages_finset 3).card = 6- Related work
- 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)…
- word_min_factor_coverages_subsetEvery inclusion-minimal factor coverage is a factor coverage: H_min(w) ⊆ H(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_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
- 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_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of w.
Read back from the Lean
The cardinality of the finset period_doubling_min_factor_coverages_finset 3 is equal to 6. In other words, there are exactly 6 subsets of $\{1, \dots, \text{length}(w_3)\}$ that are minimal (with respect to set inclusion) factor coverages of the 3rd period-doubling word.
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 establishes that the cardinality of the set of inclusion-minimal factor coverages of the third period-doubling word w_3 is equal to 6. Because the original definition of minimal factor coverages uses a noncomputable filter over the powerset of word positions, the proof first develops an equivalent, computable representation that constructs all factor coverages by indexing sublists by start position and length, then filters for inclusion-minimality. Once the set-theoretic definition is shown to equal this computable finite set on w_3, Lean's decision procedure evaluates the cardinality directly by computation.
Every factor coverage of w belongs to the computable finite set of factor coverages of w
We prove the forward direction of period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff. By definition of word_factor_coverages, C is the coverage of some non-empty factor x of w, so w = s ++ x ++ t for some lists s and t, and x has length at least 1. We witness that C belongs to the computable finite set by selecting the start index i = |s| and factor length k = |x|. The bounds i < |w| and 1 ≤ k ≤ |w| - i hold by linear arithmetic (omega) since |x| ≥ 1. Dropping the first |s| elements from s ++ x ++ t and taking the first |x| elements reconstructs x via list associativity, drop_left, and take_left, confirming that the corresponding coverage set is C.
uses
period_doubling_min_factor_coverages_three_card_factor_coverages_finset,Finset.mem_biUnion,Finset.mem_range,length_append,Finset.mem_image,Finset.mem_Icc,append_assoc,drop_left,take_leftconstructor · rintro ⟨x, hx, hinf, rfl⟩ rcases hinf with ⟨s, t, rfl⟩ have hlen : 1 ≤ x.length := by cases x · contradiction · simp rw [period_doubling_min_factor_coverages_three_card_factor_coverages_finset, Finset.mem_biUnion] refine ⟨s.length, ?_, ?_⟩ · rw [Finset.mem_range, length_append, length_append]; omega · rw [Finset.mem_image] refine ⟨x.length, ?_, ?_⟩ · rw [Finset.mem_Icc, length_append, length_append]; omega · rw [append_assoc, drop_left, take_left]
Every element of the computable finite set of factor coverages of w is a factor coverage of w
We prove the reverse direction of period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff. An element C in the computable finite set is the coverage of the sublist x = (w.drop i).take k for some starting position i < |w| and length 1 ≤ k ≤ |w| - i. To show C ∈ word_factor_coverages w, we show x is non-empty and is a factor of w. If x were empty, its length would be 0; but |x| = min(k, |w| - i) by length_take and length_drop, which cannot be 0 since k ≥ 1 and i < |w|, reaching a contradiction via omega. Finally, x is a prefix of w.drop i by take_prefix, and w.drop i is a suffix of w by drop_suffix, so x is a factor of w by transitivity of the infix relation.
uses
period_doubling_min_factor_coverages_three_card_factor_coverages_finset,Finset.mem_biUnion,Finset.mem_range,Finset.mem_image,Finset.mem_Icc,length_nil,length_take,length_drop,take_prefix,drop_suffix· rw [period_doubling_min_factor_coverages_three_card_factor_coverages_finset, Finset.mem_biUnion] rintro ⟨i, hi, hC⟩ rw [Finset.mem_range] at hi rw [Finset.mem_image] at hC rcases hC with ⟨k, hk, rfl⟩ rw [Finset.mem_Icc] at hk refine ⟨(w.drop i).take k, ?_, ?_, rfl⟩ · intro hnil have : ((w.drop i).take k).length = 0 := by rw [hnil, length_nil] rw [length_take, length_drop] at this; omega · have h1 : (w.drop i).take k <+: w.drop i := take_prefix k (w.drop i) have h2 : w.drop i <:+ w := drop_suffix i w exact h1.isInfix.trans h2.isInfix
A coverage set is inclusion-minimal among all factor coverages of w if and only if it is inclusion-minimal in the computable finite set of factor coverages
We prove period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff. Unfolding the definitions of word_min_factor_coverages and the computable minimal coverages finset, both require C to be a factor coverage and satisfy ∀ D, D ⊆ C → D = C for all factor coverages D. Since factor coverages of w are in bijection with elements of the computable finset by the previous lemma, the two minimality conditions are logically equivalent: any candidate sub-coverage D in one domain translates to the other, where the minimality assumption forces D = C.
uses
Finset.mem_filter,period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iffdsimp [word_min_factor_coverages, period_doubling_min_factor_coverages_three_card_min_factor_coverages_computable] rw [Finset.mem_filter] rw [period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] constructor · rintro ⟨hC, hmin⟩ refine ⟨hC, ?_⟩ intro D hD hsub apply hmin D · rwa [period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] · exact hsub · rintro ⟨hC, hmin⟩ refine ⟨hC, ?_⟩ intro D hD hsub apply hmin D · rwa [← period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] · exact hsub
The set of minimal factor coverages of w_3 equals the computable finite set of minimal factor coverages
We prove period_doubling_min_factor_coverages_three_card_eq by set extensionality on any coverage C. Unfolding the definition of period_doubling_min_factor_coverages_finset 3, an element C must satisfy C ⊆ {1, ..., |w_3|} and C ∈ word_min_factor_coverages w_3. By the previous equivalence, the second condition is membership in the computable minimal coverages finset. The forward direction is immediate from this conjunction. In the reverse direction, if C is in the computable minimal finset, then C ∈ word_min_factor_coverages w_3; by word_min_factor_coverages_subset, C is a factor coverage of some factor x, and by word_occurrence_coverage_subset, every occurrence coverage is indeed a subset of {1, ..., |w_3|}.
uses
Finset.mem_filter,Finset.mem_powerset,decide_eq_true_eq,period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff,word_min_factor_coverages_subset,word_occurrence_coverage_subsetclassical ext C dsimp [period_doubling_min_factor_coverages_finset] rw [Finset.mem_filter, Finset.mem_powerset, decide_eq_true_eq] rw [period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff] constructor · intro h exact h.2 · intro h refine ⟨?_, h⟩ have hC : C ∈ word_min_factor_coverages (period_doubling_word 3) := by rwa [period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff] have hcov := word_min_factor_coverages_subset (period_doubling_word 3) hC rcases hcov with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (period_doubling_word 3) x
The cardinality of the set of minimal factor coverages of w_3 is equal to 6 automation
Rewriting by period_doubling_min_factor_coverages_three_card_eq replaces the set-theoretic definition of minimal factor coverages with the computable finite set evaluated on the 8-letter word w_3 = period_doubling_word 3. The kernel decision procedure decide then executes this finite computation directly, constructing all factor coverages, filtering the inclusion-minimal ones, and counting the resulting set to obtain 6.
uses
period_doubling_min_factor_coverages_three_card_eqrw [period_doubling_min_factor_coverages_three_card_eq] decide
append_assoc- concatenation of lists is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs)
decide_eq_true_eq- the boolean decision (decide p) = true is equivalent to the proposition p
drop_left- dropping the first |l₁| elements from the concatenation l₁ ++ l₂ leaves l₂
drop_suffix- dropping the first i elements of a list l produces a suffix of l
Finset.mem_filter- an element a belongs to the filtered set {x ∈ s | p x} if and only if a ∈ s and p a holds
Finset.mem_image- an element b belongs to the image f(s) if and only if there exists a ∈ s such that f a = b
Finset.mem_Icc- an element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b
Finset.mem_powerset- an element s belongs to the powerset of t if and only if s ⊆ t
Finset.mem_range- a natural number m belongs to {0, ..., n - 1} if and only if m < n
Finset.mem_biUnion- an element b belongs to ⋃ (a ∈ s), t a if and only if there exists some a ∈ s with b ∈ t a
length_append- the length of the concatenation of two lists is the sum of their lengths: |as ++ bs| = |as| + |bs|
length_drop- the length of the suffix obtained by dropping i elements from a list l is |l| - i
length_nil- the empty list has length zero: |[]| = 0
length_take- the length of the prefix obtained by taking i elements of a list l is min(i, |l|)
period_doubling_min_factor_coverages_three_card_factor_coverages_finset- the finite set of all factor coverages of a word w, obtained by collecting the coverage of the sublist starting at index i of length k for all 0 ≤ i < |w| and 1 ≤ k ≤ |w| - i
period_doubling_min_factor_coverages_three_card_eq- the set of minimal factor coverages of the third period-doubling word w_3 equals the computable finite set of its minimal factor coverages
period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff- a set C is a factor coverage of w if and only if C belongs to the computable finite set of factor coverages of w
period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff- a set C is an inclusion-minimal factor coverage of w if and only if C belongs to the computable finite set of minimal factor coverages of w
take_left- taking the first |l₁| elements from the concatenation l₁ ++ l₂ leaves l₁
take_prefix- taking the first i elements of a list l produces a prefix of l
word_min_factor_coverages_subset- every inclusion-minimal factor coverage of a word w is, in particular, a factor coverage of w
word_occurrence_coverage_subset- the set of positions covered by occurrences of any factor x in a word w is a subset of {1, ..., |w|}
- The final step evaluates the cardinality of the minimal factor coverages set for w_3 via Lean's decide tactic, which computes the result entirely inside the kernel without exposing intermediate steps.
- The three intermediate lemmas serve to bridge the noncomputable, set-theoretic definitions of factor coverages and minimal factor coverages with explicitly computable finite-set algorithms amenable to decide.
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.
open Listdef period_doubling_min_factor_coverages_three_card_factor_coverages_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 ((w.drop i).take k))))lemma period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff {α : Type*} [DecidableEq α] (w : List α) (C : Finset ℕ) : C ∈ word_factor_coverages w ↔ C ∈ period_doubling_min_factor_coverages_three_card_factor_coverages_finset w := by constructor · rintro ⟨x, hx, hinf, rfl⟩ rcases hinf with ⟨s, t, rfl⟩ have hlen : 1 ≤ x.length := by cases x · contradiction · simp rw [period_doubling_min_factor_coverages_three_card_factor_coverages_finset, Finset.mem_biUnion] refine ⟨s.length, ?_, ?_⟩ · rw [Finset.mem_range, length_append, length_append]; omega · rw [Finset.mem_image] refine ⟨x.length, ?_, ?_⟩ · rw [Finset.mem_Icc, length_append, length_append]; omega · rw [append_assoc, drop_left, take_left] · rw [period_doubling_min_factor_coverages_three_card_factor_coverages_finset, Finset.mem_biUnion] rintro ⟨i, hi, hC⟩ rw [Finset.mem_range] at hi rw [Finset.mem_image] at hC rcases hC with ⟨k, hk, rfl⟩ rw [Finset.mem_Icc] at hk refine ⟨(w.drop i).take k, ?_, ?_, rfl⟩ · intro hnil have : ((w.drop i).take k).length = 0 := by rw [hnil, length_nil] rw [length_take, length_drop] at this; omega · have h1 : (w.drop i).take k <+: w.drop i := take_prefix k (w.drop i) have h2 : w.drop i <:+ w := drop_suffix i w exact h1.isInfix.trans h2.isInfixdef period_doubling_min_factor_coverages_three_card_min_factor_coverages_computable {α : Type*} [DecidableEq α] (w : List α) : Finset (Finset ℕ) := let H := period_doubling_min_factor_coverages_three_card_factor_coverages_finset w H.filter (fun C => ∀ D ∈ H, D ⊆ C → D = C)lemma period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff {α : Type*} [DecidableEq α] (w : List α) (C : Finset ℕ) : C ∈ word_min_factor_coverages w ↔ C ∈ period_doubling_min_factor_coverages_three_card_min_factor_coverages_computable w := by dsimp [word_min_factor_coverages, period_doubling_min_factor_coverages_three_card_min_factor_coverages_computable] rw [Finset.mem_filter] rw [period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] constructor · rintro ⟨hC, hmin⟩ refine ⟨hC, ?_⟩ intro D hD hsub apply hmin D · rwa [period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] · exact hsub · rintro ⟨hC, hmin⟩ refine ⟨hC, ?_⟩ intro D hD hsub apply hmin D · rwa [← period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff] · exact hsublemma period_doubling_min_factor_coverages_three_card_eq : period_doubling_min_factor_coverages_finset 3 = period_doubling_min_factor_coverages_three_card_min_factor_coverages_computable (period_doubling_word 3) := by classical ext C dsimp [period_doubling_min_factor_coverages_finset] rw [Finset.mem_filter, Finset.mem_powerset, decide_eq_true_eq] rw [period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff] constructor · intro h exact h.2 · intro h refine ⟨?_, h⟩ have hC : C ∈ word_min_factor_coverages (period_doubling_word 3) := by rwa [period_doubling_min_factor_coverages_three_card_mem_word_min_factor_coverages_iff] have hcov := word_min_factor_coverages_subset (period_doubling_word 3) hC rcases hcov with ⟨x, _, _, rfl⟩ exact word_occurrence_coverage_subset (period_doubling_word 3) x/-- The number of inclusion-minimal factor coverages of the 3rd period-doubling word w_3 is 6. -/theorem period_doubling_min_factor_coverages_three_card : (period_doubling_min_factor_coverages_finset 3).card = 6 := by rw [period_doubling_min_factor_coverages_three_card_eq] decide