word_occurrence_coverage_nonempty
The coverage of a nonempty factor of w is nonempty.
Statement
theorem word_occurrence_coverage_nonempty {α : Type*} [DecidableEq α] {w x : List α} (hx : x ≠ []) (hxw : x <:+: w) : (word_occurrence_coverage w x).Nonempty
- 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 1
- is_string_attractor_IccThe set of all positions [1, |w|] is a string attractor of w.
The proof, explained
To show that the coverage of a nonempty factor $x$ in $w$ is nonempty, we decompose $w$ as $s ++ x ++ t$ using the factor assumption. We then exhibit the 1-based starting position $|s| + 1$ as an element of the coverage set. Since $|x| > 0$, this position satisfies the index bounds for an occurrence of $x$, and the factor starting at $|s| + 1$ is identically $x$.
Decomposing $w = s ++ x ++ t$, it suffices to show that the starting index $|s| + 1$ belongs to the coverage of $x$, where $|x| > 0$.
Since $x$ is an infix (factor) of $w$ ($x <:+: w$), we can write $w = s ++ x ++ t$ for some prefix $s$ and suffix $t$. To show that the coverage of $x$ is nonempty, it suffices to exhibit an element in it; we choose the 1-based position $|s| + 1$ where this occurrence of $x$ begins. Furthermore, since $x$ is nonempty ($x \neq []$), its length is strictly positive by `List.length_pos_iff.2`.
uses
List.length_pos_iff.2obtain ⟨s, t, rfl⟩ := hxw refine ⟨s.length + 1, ?_⟩ have hlen : 0 < x.length := List.length_pos_iff.2 hx
Membership of $|s| + 1$ in the coverage set reduces to finding an occurrence of $x$ that covers $|s| + 1$.
Unfolding `word_occurrence_coverage` and rewriting Finset membership with `Finset.mem_biUnion`, `Finset.mem_filter`, `Finset.mem_Icc`, and `List.length_append`, the goal becomes finding a valid starting position $a \in [1, |s| + |x| + |t|]$ where the factor of length $|x|$ is $x$, such that $|s| + 1 \in [a, a + |x| - 1]$.
uses
word_occurrence_coverage,Finset.mem_biUnion,Finset.mem_filter,Finset.mem_Icc,List.length_appendsimp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc, List.length_append]The occurrence at index $a = |s| + 1$ is valid and covers the index $|s| + 1$.
We instantiate the occurrence position $a$ with $|s| + 1$. The inequalities $1 \le |s| + 1 \le |s| + |x| + |t|$ and $|s| + 1 \le (|s| + 1) + |x| - 1$ follow by linear arithmetic (`omega`) using $|x| > 0$, while $|s| + 1 \le |s| + 1$ holds by reflexivity (`le_rfl`). Finally, dropping $|s|$ elements from $s ++ x ++ t$ leaves $x ++ t$, and taking the first $|x|$ elements yields $x$, which is verified by list simplification (`simp`).
uses
le_rflrefine ⟨s.length + 1, ⟨⟨by omega, by omega⟩, ?_⟩, le_rfl, by omega⟩ simp
List.length_pos_iff.2- A list has strictly positive length if it is nonempty.
word_occurrence_coverage- The set of indices covered by occurrences of a factor in a word, defined as the union of intervals $[p, p + |x| - 1]$ over all positions $p$ where $x$ occurs.
Finset.mem_biUnion- An element belongs to a indexed union of finsets if and only if it belongs to the component finset for some index in the base finset.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_Icc- An element belongs to the closed interval $[a, b]$ if and only if it is between $a$ and $b$ inclusive.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
le_rfl- The partial order relation $\le$ is reflexive: $a \le a$.
- Indices in `word_occurrence_coverage` are 1-based, running from 1 to the word's length.
- The arithmetic inequalities verifying that the starting index $|s| + 1$ is within the valid range are discharged by `omega`, and the list slice equality is closed by `simp`.
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_nonempty {α : Type*} [DecidableEq α] {w x : List α} (hx : x ≠ []) (hxw : x <:+: w) : (word_occurrence_coverage w x).Nonempty := by obtain ⟨s, t, rfl⟩ := hxw refine ⟨s.length + 1, ?_⟩ have hlen : 0 < x.length := List.length_pos_iff.2 hx simp only [word_occurrence_coverage, Finset.mem_biUnion, Finset.mem_filter, Finset.mem_Icc, List.length_append] refine ⟨s.length + 1, ⟨⟨by omega, by omega⟩, ?_⟩, le_rfl, by omega⟩ simp