string_overlap_len_sanity
ov(123,234) = 23, ov(11,11) = 1, ov(12,12) is empty.
Statement
theorem string_overlap_len_sanity :
string_overlap_len [1, 2, 3] [2, 3, 4] = 2 ∧ string_overlap_len [1, 1] [1, 1] = 1 ∧
string_overlap_len [1, 2] [1, 2] = 0- Source
- Sanity check of string_overlap_len (arXiv:2611.16573)
- Verified
- 14 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- string_overlap_lenFor two lists x, y : List Γ over an arbitrary alphabet type Γ with decidable equality (strings are lists of letters, not Lean Strings),…
The proof, explained
The theorem verifies three concrete evaluations of the string overlap length function on short integer lists. Because the function is defined as a bounded search over finite lists with decidable equality, the entire proposition is decidable by finite evaluation. The proof delegates the calculation directly to the `decide` tactic.
The overlap length is 2 for [1, 2, 3] and [2, 3, 4], 1 for [1, 1] and [1, 1], and 0 for [1, 2] and [1, 2]. automation
The function `string_overlap_len x y` searches for the largest integer k < min(|x|, |y|) such that the suffix of x of length k equals the prefix of y of length k. For these explicit lists, checking the condition requires testing only k ∈ {0, 1, 2}: - For [1, 2, 3] and [2, 3, 4], the suffix [2, 3] equals the prefix [2, 3], giving overlap 2. - For [1, 1] and [1, 1], the strict inequality restricts to k < 2, and the length-1 suffix [1] matches the length-1 prefix [1], giving overlap 1. - For [1, 2] and [1, 2], k < 2 requires checking k = 1 where [2] ≠ [1], leaving only the empty overlap k = 0. The `decide` tactic evaluates this bounded search directly by computation to close the goal.
string_overlap_len [1, 2] [1, 2] = 0 := by decide
- The definition of `string_overlap_len` enforces strict inequalities k < |x| and k < |y|, searching only for proper overlaps. Hence, a list compared with itself does not have an overlap equal to its total length: [1, 1] with itself has overlap length 1, and [1, 2] with itself has overlap length 0.
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 string_overlap_len_sanity : string_overlap_len [1, 2, 3] [2, 3, 4] = 2 ∧ string_overlap_len [1, 1] [1, 1] = 1 ∧ string_overlap_len [1, 2] [1, 2] = 0 := by decide