AFTD Auto-Formalizing Theoretical Domains

period_doubling_min_factor_coverages_three_card

theoremverifiedoriginal

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

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.

  1. 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.

    lines 13–26

    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_left

      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]
  2. 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.

    lines 27–39

    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
  3. 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.

    lines 50–65

    uses Finset.mem_filter, period_doubling_min_factor_coverages_three_card_mem_word_factor_coverages_iff

      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 hsub
  4. 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|}.

    lines 70–84

    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_subset

      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
  5. 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.

    lines 89–90

    uses period_doubling_min_factor_coverages_three_card_eq

      rw [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|}

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

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
See it in the graphDiscuss this resultChallenge it