is_string_attractor_Icc
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
- 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_occurrence_coverage_subsetEvery coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
- word_occurrence_coverage_nonemptyThe coverage of a nonempty factor of w is nonempty.
- 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
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.
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).
uses
subset_rflrefine ⟨subset_rfl, fun x hx hxw => ?_⟩
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.
uses
Finset.inter_eq_right.2,word_occurrence_coverage_subset,word_occurrence_coverage_nonemptyrw [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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