is_string_attractor_iff_forall_min_factor_coverage
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
- fibonacci_string_attractor_iff_meets_basisFor any natural number n, assuming the inclusion-minimal factor coverages of F_n are exactly the coverages of the basis B_n…
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.
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.
constructor · rintro ⟨-, h⟩ C ⟨⟨x, hx, hxw, rfl⟩, -⟩ exact h x hx hxw
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.
· intro h refine ⟨hΓ, fun x hx hxw => ?_⟩
Γ 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.
uses
exists_min_factor_coverage_subset,Finset.inter_subset_inter_leftobtain ⟨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
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_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⟩