word_min_factor_coverages_subset_of_certificate
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.
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.
uses
Finset.sdiff_subsetintro 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
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.
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
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.
have hnot : ¬ word_occurrence_coverage w y ⊆ C := by intro hsub have := hmin _ ⟨y, hy, hyw, rfl⟩ hsub exact hCF (this ▸ hD)
Γ 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.
uses
Finset.not_subset.1,Finset.mem_inter.2,Finset.mem_sdiff.2,word_occurrence_coverage_subsetobtain ⟨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⟩⟩
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.
uses
Finset.mem_inter,Finset.mem_sdiffobtain ⟨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
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 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