AFTD Auto-Formalizing Theoretical Domains

is_string_attractor_iff_forall_min_factor_coverage

theoremverifiedformalization

For every finite word w and every Γ ⊆ [1, |w|], Γ is a string attractor of w if and only if Γ ∩ C ≠ ∅ for every inclusion-minimal factor coverage C ∈ H_min(w).

Statement

theorem is_string_attractor_iff_forall_min_factor_coverage {α : Type*} [DecidableEq α]
    (w : List α) (Γ : Finset ℕ) (hΓ : Γ ⊆ Finset.Icc 1 w.length) :
    is_string_attractor w Γ ↔ ∀ C ∈ word_min_factor_coverages w, (Γ ∩ C).Nonempty
Formalizes
arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Proposition 3.2 (minimal-coverage reduction).
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.
  • exists_min_factor_coverage_subsetEvery factor coverage D ∈ H(w) contains some inclusion-minimal factor coverage C ∈ H_min(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…
Used by 1

The proof, explained

A set of positions Γ is a string attractor of w if and only if it intersects every minimal factor coverage in H_min(w). The forward direction holds because every minimal factor coverage is itself the occurrence coverage of some non-empty factor. The reverse direction holds because every factor coverage contains an inclusion-minimal factor coverage, so a set that intersects all minimal factor coverages automatically intersects every factor coverage.

  1. If Γ is a string attractor of w, then Γ intersects every minimal factor coverage C ∈ H_min(w).

    We split the equivalence into two implications. In the forward direction, assume Γ is a string attractor. By definition, a minimal factor coverage C is in particular a factor coverage, meaning C is the occurrence coverage of some non-empty factor x of w. The definition of a string attractor directly guarantees that Γ intersects the occurrence coverage of x, which is C.

    lines 4–6

      constructor
      · rintro ⟨-, h⟩ C ⟨⟨x, hx, hxw, rfl⟩, -⟩
        exact h x hx hxw
  2. To show that Γ is a string attractor under the hypothesis that it intersects every minimal factor coverage, it suffices to show that Γ intersects the occurrence coverage of an arbitrary non-empty factor x of w.

    In the reverse direction, we assume that Γ intersects every minimal factor coverage C. By definition, Γ is a string attractor if Γ ⊆ [1, |w|] (which is provided by hypothesis hΓ) and Γ intersects the occurrence coverage of every non-empty factor x of w. We fix an arbitrary non-empty factor x of w.

    lines 7–8

      · intro h
        refine ⟨hΓ, fun x hx hxw => ?_⟩
  3. Γ intersects the occurrence coverage of x, completing the proof.

    Because x is a non-empty factor of w, its occurrence coverage is a factor coverage. By `exists_min_factor_coverage_subset`, it contains an inclusion-minimal factor coverage C. Applying our hypothesis to C yields an element p ∈ Γ ∩ C. Since C is a subset of the occurrence coverage of x, `Finset.inter_subset_inter_left` implies p is also in Γ ∩ word_occurrence_coverage w x, showing that the intersection is non-empty.

    lines 9–11

    uses exists_min_factor_coverage_subset, Finset.inter_subset_inter_left

        obtain ⟨C, hC, hCD⟩ := exists_min_factor_coverage_subset w ⟨x, hx, hxw, rfl⟩
        obtain ⟨p, hp⟩ := h C hC
        exact ⟨p, Finset.inter_subset_inter_left hCD hp⟩
exists_min_factor_coverage_subset
Every factor coverage of a word w contains an inclusion-minimal factor coverage as a subset.
Finset.inter_subset_inter_left
If t ⊆ u, then s ∩ t ⊆ s ∩ u for any sets s, t, u.

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 is_string_attractor_iff_forall_min_factor_coverage {α : Type*} [DecidableEq α]    (w : List α) (Γ : Finset ℕ) (hΓ : Γ ⊆ Finset.Icc 1 w.length) :    is_string_attractor w Γ ↔ ∀ C ∈ word_min_factor_coverages w, (Γ ∩ C).Nonempty := by  constructor  · rintro ⟨-, h⟩ C ⟨⟨x, hx, hxw, rfl⟩, -⟩    exact h x hx hxw  · intro h    refine ⟨hΓ, fun x hx hxw => ?_⟩    obtain ⟨C, hC, hCD⟩ := exists_min_factor_coverage_subset w ⟨x, hx, hxw, rfl⟩    obtain ⟨p, hp⟩ := h C hC    exact ⟨p, Finset.inter_subset_inter_left hCD hp⟩
See it in the graphDiscuss this resultChallenge it