word_occurrence_coverage_subset
Every coverage Cov_w(x) is a set of positions of w, i.e. contained in [1, |w|].
Statement
theorem word_occurrence_coverage_subset {α : Type*} [DecidableEq α] (w x : List α) : word_occurrence_coverage w x ⊆ Finset.Icc 1 w.length
- Source
- Sanity lemma for word_occurrence_coverage (arXiv:2610.10950 (Smallest String Attractors and Minimal Coverage Certificates of Thue–Morse Words), Sec. 3.1).
- Verified
- 12 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 4
- is_string_attractor_IccThe set of all positions [1, |w|] is a string attractor of w.
- thue_morse_unhit_mean_nonnegFor all n and k, 0 ≤ thue_morse_unhit_mean n k.
- word_min_factor_coverages_subset_of_certificateLet 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.…
- thue_morse_min_factor_coverages_finset_memFor every n and every C, C belongs to thue_morse_min_factor_coverages_finset n if and only if C is an inclusion-minimal factor coverage of…
The proof, explained
To show that every position in the coverage of x in w lies in [1, |w|], we consider an arbitrary position q in the coverage and obtain an occurrence start position p ∈ [1, |w|] such that q ∈ [p, p + |x| - 1]. Taking lengths of both sides of the occurrence match equation shows that |x| ≤ |w| - (p - 1), meaning the occurrence cannot extend beyond the end of w. Linear arithmetic then immediately establishes 1 ≤ q ≤ |w|.
Every element q of the coverage belongs to an interval [p, p + |x| - 1] for some occurrence start position p ∈ [1, |w|], and it suffices to show 1 ≤ q ≤ |w|.
Let q be an arbitrary position in the coverage of x in w. By expanding the definition of coverage as the union of intervals [p, p + |x| - 1] over all p ∈ [1, |w|] satisfying take(|x|, drop(p - 1, w)) = x, we obtain a witness position p such that 1 ≤ p ≤ |w|, the occurrence equation holds, and p ≤ q ≤ p + |x| - 1. The goal reduces to showing 1 ≤ q ≤ |w|.
uses
word_occurrence_coverage,Finset.mem_biUnion,Finset.mem_filter,Finset.mem_Iccintro q hq simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc] at hq ⊢ obtain ⟨p, ⟨⟨hp1, hpw⟩, hocc⟩, hpq, hqx⟩ := hq
min(|x|, |w| - (p - 1)) = |x|
Taking the length of both sides of the occurrence equation take(|x|, drop(p - 1, w)) = x yields |take(|x|, drop(p - 1, w))| = |x|. Rewriting the left-hand side with the formulas for the length of a prefix (List.length_take) and the length of a suffix (List.length_drop) produces min(|x|, |w| - (p - 1)) = |x|.
uses
congrArg,List.length_take,List.length_drophave hlen := congrArg List.length hocc rw [List.length_take, List.length_drop] at hlen
1 ≤ q ≤ |w|
From min(|x|, |w| - (p - 1)) = |x|, we have |x| ≤ |w| - (p - 1), which implies p + |x| - 1 ≤ |w|. Combined with p ≤ q ≤ p + |x| - 1 and 1 ≤ p, this yields 1 ≤ q ≤ |w|. Linear integer arithmetic (omega) closes the goal.
omega
word_occurrence_coverage- The definition of word occurrence coverage: the union of intervals [p, p + |x| - 1] over all positions p ∈ [1, |w|] at which x occurs in w.
Finset.mem_biUnion- An element b belongs to a union of finsets ⋃_{a ∈ s} t(a) if and only if there is some a ∈ s such that b ∈ t(a).
Finset.mem_filter- An element a belongs to {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds.
Finset.mem_Icc- An element x belongs to the closed discrete interval [a, b] if and only if a ≤ x and x ≤ b.
congrArg- Equality is preserved under function application: if a₁ = a₂, then f(a₁) = f(a₂).
List.length_take- The length of the prefix obtained by taking the first i elements of a list l is min(i, |l|).
List.length_drop- The length of the suffix obtained by dropping the first i elements of a list l is |l| - i.
- Positions in the coverage are 1-based (ranging from 1 to |w|), while Lean's list operations `List.drop` and `List.take` use 0-based indexing, which accounts for the `p - 1` offsets.
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_occurrence_coverage_subset {α : Type*} [DecidableEq α] (w x : List α) : word_occurrence_coverage w x ⊆ Finset.Icc 1 w.length := by intro q hq simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc] at hq ⊢ obtain ⟨p, ⟨⟨hp1, hpw⟩, hocc⟩, hpq, hqx⟩ := hq have hlen := congrArg List.length hocc rw [List.length_take, List.length_drop] at hlen omega