AFTD Auto-Formalizing Theoretical Domains

period_doubling_min_factor_coverages_finset_mem

theoremverified

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
Used by 2

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|\}$.

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

    lines 4–6

    uses Finset.mem_filter, Finset.mem_powerset, decide_eq_true_eq

      dsimp [period_doubling_min_factor_coverages_finset]
      rw [Finset.mem_filter, Finset.mem_powerset]
      simp only [decide_eq_true_eq]
  2. 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.

    lines 7–9

      constructor
      · intro h
        exact h.2
  3. 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|\}$.

    lines 10–14

    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|\}$.

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

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