AFTD Auto-Formalizing Theoretical Domains

period_doubling_min_factor_coverages_four_card

theoremverifiedoriginal

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

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`).

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

    lines 11–25

    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_Icc

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

    lines 26–46

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

    lines 57–66

    uses period_doubling_min_factor_coverages_four_card_min_coverages, Finset.mem_filter, period_doubling_min_factor_coverages_four_card_mem_factor

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

    lines 71–73

    uses period_doubling_min_factor_coverages_finset_mem, period_doubling_min_factor_coverages_four_card_mem_min

      ext C
      rw [period_doubling_min_factor_coverages_finset_mem]
      exact period_doubling_min_factor_coverages_four_card_mem_min _ _
  5. 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`.

    lines 78–79

    uses period_doubling_min_factor_coverages_four_card_eq

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

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

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