AFTD Auto-Formalizing Theoretical Domains

word_min_factor_coverages_subset_of_certificate

theoremverifiedformalization

Let F ⊆ H(w) be a family of factor coverages such that for every Γ ⊆ [1, |w|], Γ is a string attractor of w iff Γ meets every member of F. Then H_min(w) ⊆ F: every exact certificate contains all inclusion-minimal coverages.

Statement

theorem word_min_factor_coverages_subset_of_certificate {α : Type*} [DecidableEq α]
    (w : List α) (F : Set (Finset ℕ)) (hF : F ⊆ word_factor_coverages w)
    (hcert : ∀ Γ ⊆ Finset.Icc 1 w.length,
      is_string_attractor w Γ ↔ ∀ C ∈ F, (Γ ∩ C).Nonempty) :
    word_min_factor_coverages w ⊆ F
Formalizes
arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Lemma 6.9 (canonical irredundancy). The proof here takes Γ = [1,|w|] \ C instead of one chosen point per member of F.
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • is_string_attractorA set Γ ⊆ [1, |w|] of positions is a string attractor of the finite word w if Γ ∩ Cov_w(x) ≠ ∅ for every nonempty factor x of w.
  • word_min_factor_coveragesH_min(w): the inclusion-minimal members of H(w), the family of factor coverages of w.
  • word_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
  • word_factor_coveragesH(w): the family of coverages Cov_w(x) of the nonempty factors x of 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…

The proof, explained

We prove the inclusion by contradiction: suppose an inclusion-minimal factor coverage C of a factor x is not in F. Consider the complement Γ = [1, |w|] \ C. For every coverage D ∈ F, the minimality of C implies that D cannot be a subset of C, so D contains a position outside C, meaning Γ ∩ D is non-empty. By the certificate property of F, this makes Γ a string attractor of w. However, as an attractor, Γ must intersect the coverage C of x, which contradicts Γ = [1, |w|] \ C.

  1. Assume for contradiction that some minimal factor coverage C is not in F, and define the candidate string attractor Γ = [1, |w|] \ C.

    We proceed by contradiction: suppose C ∈ word_min_factor_coverages w, but C ∉ F. By definition of minimal factor coverages, C is the occurrence coverage of some non-empty factor x of w, and any factor coverage contained in C equals C. We define Γ as the complement [1, |w|] \ C, which is a subset of [1, |w|] by Finset.sdiff_subset.

    lines 6–9

    uses Finset.sdiff_subset

      intro C hC
      by_contra hCF
      obtain ⟨⟨x, hx, hxw, hxC⟩, hmin⟩ := hC
      have hΓ : Finset.Icc 1 w.length \ C ⊆ Finset.Icc 1 w.length := Finset.sdiff_subset
  2. To show that Γ is a string attractor of w, it suffices to show that Γ intersects the coverage of every factor whose coverage belongs to F.

    We verify that Γ is a string attractor of w. Since Γ ⊆ [1, |w|], the certificate hypothesis hcert states that Γ is a string attractor if and only if Γ intersects every D ∈ F. Taking an arbitrary D ∈ F, the hypothesis hF implies that D is the occurrence coverage of some non-empty factor y of w.

    lines 10–13

      have hatt : is_string_attractor w (Finset.Icc 1 w.length \ C) := by
        rw [hcert _ hΓ]
        intro D hD
        obtain ⟨y, hy, hyw, rfl⟩ := hF hD
  3. The factor coverage D of y is not contained in C.

    Suppose for contradiction that the coverage of y were a subset of C. Since C is inclusion-minimal among all factor coverages (hmin), any factor coverage contained in C must be equal to C. This would imply D = C, and since D ∈ F, it would follow that C ∈ F, contradicting C ∉ F.

    lines 14–17

        have hnot : ¬ word_occurrence_coverage w y ⊆ C := by
          intro hsub
          have := hmin _ ⟨y, hy, hyw, rfl⟩ hsub
          exact hCF (this ▸ hD)
  4. Γ intersects D, establishing that Γ is a string attractor of w.

    Because D is not a subset of C, there is a position p ∈ D that is not in C (by Finset.not_subset.1). Since every position in a factor coverage belongs to [1, |w|] (by word_occurrence_coverage_subset), p ∈ [1, |w|] \ C = Γ. Hence p ∈ Γ ∩ D (by Finset.mem_inter.2 and Finset.mem_sdiff.2), showing that Γ intersects D. As D ∈ F was arbitrary, Γ meets every member of F, so Γ is a string attractor of w.

    lines 18–20

    uses Finset.not_subset.1, Finset.mem_inter.2, Finset.mem_sdiff.2, word_occurrence_coverage_subset

        obtain ⟨p, hpD, hpC⟩ := Finset.not_subset.1 hnot
        exact ⟨p, Finset.mem_inter.2
          ⟨Finset.mem_sdiff.2 ⟨word_occurrence_coverage_subset w y hpD, hpC⟩, hpD⟩⟩
  5. Derive a contradiction from the string attractor condition applied to x.

    Since Γ is a string attractor of w, it must intersect the occurrence coverage of every non-empty factor of w, including x. Thus there exists a position p ∈ Γ ∩ word_occurrence_coverage w x. But word_occurrence_coverage w x = C, and Γ = [1, |w|] \ C. Rewriting with Finset.mem_inter and Finset.mem_sdiff, p must satisfy both p ∉ C and p ∈ C, which is a contradiction.

    lines 21–23

    uses Finset.mem_inter, Finset.mem_sdiff

      obtain ⟨p, hp⟩ := hatt.2 x hx hxw
      rw [hxC, Finset.mem_inter, Finset.mem_sdiff] at hp
      exact hp.1.2 hp.2
Finset.sdiff_subset
For any finite sets s and t, the set difference s \ t is a subset of s.
Finset.not_subset.1
If a finite set s is not a subset of t, then there exists an element x ∈ s such that x ∉ t.
Finset.mem_inter.2
If an element x belongs to s and to t, then x belongs to s ∩ t.
Finset.mem_sdiff.2
If an element x belongs to s and not to t, then x belongs to s \ t.
word_occurrence_coverage_subset
The occurrence coverage of any factor of w is a subset of [1, |w|].
Finset.mem_inter
An element belongs to s ∩ t if and only if it belongs to both s and t.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.

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

theorem word_min_factor_coverages_subset_of_certificate {α : Type*} [DecidableEq α]    (w : List α) (F : Set (Finset ℕ)) (hF : F ⊆ word_factor_coverages w)    (hcert : ∀ Γ ⊆ Finset.Icc 1 w.length,      is_string_attractor w Γ ↔ ∀ C ∈ F, (Γ ∩ C).Nonempty) :    word_min_factor_coverages w ⊆ F := by  intro C hC  by_contra hCF  obtain ⟨⟨x, hx, hxw, hxC⟩, hmin⟩ := hC  have hΓ : Finset.Icc 1 w.length \ C ⊆ Finset.Icc 1 w.length := Finset.sdiff_subset  have hatt : is_string_attractor w (Finset.Icc 1 w.length \ C) := by    rw [hcert _ hΓ]    intro D hD    obtain ⟨y, hy, hyw, rfl⟩ := hF hD    have hnot : ¬ word_occurrence_coverage w y ⊆ C := by      intro hsub      have := hmin _ ⟨y, hy, hyw, rfl⟩ hsub      exact hCF (this ▸ hD)    obtain ⟨p, hpD, hpC⟩ := Finset.not_subset.1 hnot    exact ⟨p, Finset.mem_inter.2      ⟨Finset.mem_sdiff.2 ⟨word_occurrence_coverage_subset w y hpD, hpC⟩, hpD⟩⟩  obtain ⟨p, hp⟩ := hatt.2 x hx hxw  rw [hxC, Finset.mem_inter, Finset.mem_sdiff] at hp  exact hp.1.2 hp.2
See it in the graphDiscuss this resultChallenge it