AFTD Auto-Formalizing Theoretical Domains

is_string_attractor_Icc

theoremverified

The set of all positions [1, |w|] is a string attractor of w.

Statement

theorem is_string_attractor_Icc {α : Type*} [DecidableEq α] (w : List α) :
    is_string_attractor w (Finset.Icc 1 w.length)
Source
Sanity lemma for is_string_attractor (arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Definition 3.1).
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

By definition, a set Γ is a string attractor of a word w if Γ ⊆ [1, |w|] and Γ intersects the set of positions covered by occurrences of every nonempty factor x of w. For Γ = [1, |w|], the inclusion condition holds reflexively. Furthermore, the occurrence coverage of any factor is entirely contained within [1, |w|], so the intersection is just the coverage itself, which is nonempty whenever x is a nonempty factor of w.

  1. To show that [1, |w|] is a string attractor of w, it suffices to show that for any nonempty factor x of w, the set [1, |w|] intersects the occurrence coverage of x.

    By definition, a set Γ is a string attractor of w if Γ ⊆ [1, |w|] and Γ intersects the occurrence coverage of every nonempty factor of w. For Γ = [1, |w|], the subset condition [1, |w|] ⊆ [1, |w|] holds reflexively by subset_rfl. We then introduce an arbitrary factor x of w (hxw) that is nonempty (hx).

    line 3

    uses subset_rfl

      refine ⟨subset_rfl, fun x hx hxw => ?_⟩
  2. The intersection [1, |w|] ∩ word_occurrence_coverage(w, x) is nonempty.

    Since all occurrences of any factor of w lie within the bounds [1, |w|], the coverage of x is a subset of [1, |w|] (by word_occurrence_coverage_subset). Therefore, their intersection simplifies to just the coverage of x itself via Finset.inter_eq_right.2. Because x is nonempty and occurs in w, its occurrence coverage is nonempty (by word_occurrence_coverage_nonempty), completing the proof.

    lines 4–5

    uses Finset.inter_eq_right.2, word_occurrence_coverage_subset, word_occurrence_coverage_nonempty

      rw [Finset.inter_eq_right.2 (word_occurrence_coverage_subset w x)]
      exact word_occurrence_coverage_nonempty hx hxw
subset_rfl
A set is a subset of itself: s ⊆ s.
Finset.inter_eq_right.2
If s ⊆ t, then t ∩ s = s.
word_occurrence_coverage_subset
The positions covered by all occurrences of a factor x in w form a subset of [1, |w|].
word_occurrence_coverage_nonempty
If x is a nonempty factor of w, the set of positions covered by its occurrences in w is nonempty.

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_Icc {α : Type*} [DecidableEq α] (w : List α) :    is_string_attractor w (Finset.Icc 1 w.length) := by  refine ⟨subset_rfl, fun x hx hxw => ?_⟩  rw [Finset.inter_eq_right.2 (word_occurrence_coverage_subset w x)]  exact word_occurrence_coverage_nonempty hx hxw
See it in the graphDiscuss this resultChallenge it