suffix_segmentation_bound_by_chunk_vocabulary
Fix q in {2, ..., M}. For every alphabet and every nonempty word w of length at most M, there exists a vocabulary V_w of substrings of w of length at least 2 with size at most q such that every nonempty suffix y of w can be segmented into at most q - 1 + ⌈M / q⌉ tokens from V_w and singletons.
Statement
theorem suffix_segmentation_bound_by_chunk_vocabulary {α : Type*} (M q : ℕ) (hq : 2 ≤ q) (hqM : q ≤ M) (w : List α) (hw : w ≠ []) (hl : w.length ≤ M) : ∃ V_w : Finset (List α), (∀ u ∈ V_w, u ∈ word_substrings w) ∧ V_w.card ≤ q ∧ ∀ y ∈ word_suffixes w, ∃ tokens : List (List α), is_token_segmentation (↑V_w) y tokens ∧ tokens.length ≤ q - 1 + M ⌈/⌉ q
- Formalizes
- arXiv:2611.15074 Lemma 3.8 -- Tokenization: Hardness and Bicriteria Approximation Algorithms
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- word_substringsThe set Sub(w) of substrings of a word w of length at least 2.
- word_suffixesThe set Suf(w) of nonempty suffixes of a word w.
- is_token_segmentationA list of tokens forms a valid segmentation of a word y over vocabulary V and single-character alphabet if their concatenation is y and…
- chunk_token_bound_leFor 2 ≤ q ≤ M, the number of chunks q is at most q - 1 + ⌈M / q⌉.
- chunk_inner_token_bound_leFor l ≤ M and natural numbers q and M, (⌈l / q⌉ - 1) + (q - 1) is at most q - 1 + ⌈M / q⌉.
Read back from the Lean
For any type α, any natural numbers M and q with 2 ≤ q and q ≤ M, and any non-empty list w : List α of length at most M, there exists a finite set V_w of lists over α such that:
1. Every element u ∈ V_w is an infix (contiguous substring) of w with length at least 2;
2. The cardinality of V_w is at most q; and
3. For every non-empty suffix y of w, there exists a list tokens : List (List α) such that:
- The concatenation (flatten) of tokens equals y;
- Every token t ∈ tokens either belongs to V_w or has length 1; and
- The number of tokens (tokens.length) is at most q - 1 + M ⌈/⌉ q (where ⌈/⌉ is natural ceiling division).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof sets the chunk size to r = ⌈|w| / q⌉ and establishes by induction on q that any word of length at most q * r admits a vocabulary V of at most q substrings of length at least 2 satisfying a dual bound: suffixes aligned with the chunk grid (offset a multiple of r) use at most q tokens, while unaligned suffixes use at most (r - 1) + (q - 1) tokens. In the inductive step, the word is split into an initial chunk c of length r and remainder rest, and c is added to the vocabulary produced for rest by the induction hypothesis; an unaligned suffix starting inside c segments its prefix using at most r - 1 singletons and then uses the aligned segmentation of rest. Finally, substituting r = ⌈|w| / q⌉ and using |w| ≤ M bounds both cases by q - 1 + ⌈M / q⌉.
Flattening a list of singletons recovers the original list.
By induction on the list l: the empty list case is immediate by definition; for a cons cell a :: t, the flattened list simplifies to a :: flatten(map(t)), which reduces to a :: t by the induction hypothesis.
induction l with | nil => simp | cons a t ih => simp [ih]
Every list has a valid token segmentation into singletons under any vocabulary.
Unfolding the definition of a token segmentation, flattening the list of singletons of y yields y by `suffix_segmentation_bound_by_chunk_vocabulary_singletons`, and every token in the list has length 1, satisfying the valid token condition via `Or.inr`.
uses
suffix_segmentation_bound_by_chunk_vocabulary_singletons,Or.inrunfold is_token_segmentation constructor · rw [suffix_segmentation_bound_by_chunk_vocabulary_singletons] · intro t ht simp only [List.mem_map] at ht obtain ⟨a, _, rfl⟩ := ht exact Or.inr (by simp)
Concatenating valid token segmentations of two lists produces a valid token segmentation of their concatenation.
Unfolding the definition of token segmentation, the concatenation ta ++ tb flattens to a ++ b by `List.flatten_append`, and each token belongs to either ta or tb, inheriting validity from the respective hypotheses.
uses
List.flatten_appendunfold is_token_segmentation at * obtain ⟨h1, h2⟩ := ha obtain ⟨h3, h4⟩ := hb constructor · rw [List.flatten_append, h1, h3] · intro t ht simp only [List.mem_append] at ht rcases ht with h | h · exact h2 t h · exact h4 t h
Token segmentations are monotonic with respect to vocabulary inclusion.
If V ⊆ W, any token in a segmentation using V that belongs to V also belongs to W, while singleton tokens remain length 1, so the segmentation is valid using W.
unfold is_token_segmentation at * exact ⟨h.1, fun u hu => (h.2 u hu).imp (fun hv => hVW hv) id⟩
For the base case q = 1 on a word w of length at most r, there exists a vocabulary V of size at most 1 consisting only of substrings of w of length at least 2.
Define V = {w} if |w| ≥ 2 and V = ∅ otherwise. If |w| ≥ 2, the only element w is an infix of itself by `List.infix_refl` and has length at least 2; otherwise V is empty. In both cases, the cardinality of V is at most 1.
uses
List.infix_reflclassical let V : Finset (List α) := if 2 ≤ w.length then {w} else ∅ refine ⟨V, ?_, ?_, ?_⟩ · intro u hu by_cases h2 : 2 ≤ w.length · simp only [V, h2, if_true, Finset.mem_singleton] at hu rw [hu] exact ⟨List.infix_refl w, h2⟩ · simp [V, h2] at hu · simp only [V] by_cases h2 : 2 ≤ w.length <;> simp [h2]
In the base case q = 1, any nonempty suffix y = w.drop m with m % r = 0 can be segmented into at most 1 token.
Since y is nonempty, m < |w| ≤ r (using `List.drop_eq_nil_of_le` and `List.length_drop`). Since m < r, m % r = m by `Nat.mod_eq_of_lt`, so m % r = 0 implies m = 0 and y = w by `List.drop_zero`. Segmenting y as the single token [w] gives length 1 ≤ 1: if |w| ≥ 2 then w ∈ V, and if |w| < 2 then |w| = 1 since w is nonempty, making [w] a valid singleton.
uses
List.drop_eq_nil_of_le,List.length_drop,Nat.mod_eq_of_lt,List.drop_zero· rw [suffix_segmentation_bound_by_chunk_vocabulary_prop] intro m y hmy hyne have hmlt : m < w.length := by by_contra h push Not at h exact hyne (by rw [← hmy]; exact List.drop_eq_nil_of_le h) have hwr : w.length ≤ r := by simpa using hw have hmr : m < r := by omega have hleny : y.length = w.length - m := by rw [← hmy, List.length_drop] constructor · intro hm0 have hm0' : m = 0 := by have := Nat.mod_eq_of_lt hmr omega have hyw : y = w := by rw [← hmy, hm0', List.drop_zero] refine ⟨[w], ?_, by simp⟩ rw [hyw] unfold is_token_segmentation constructor · simp · intro t ht simp only [List.mem_singleton] at ht rw [ht] by_cases h2 : 2 ≤ w.length · left simp [V, h2] · right have h1 : w.length < 2 := by omega omega
In the base case q = 1, any nonempty suffix y = w.drop m with m % r ≠ 0 can be segmented into at most r - 1 tokens.
Since m % r ≠ 0 and 0 % r = 0 by `Nat.zero_mod`, we have m ≥ 1. Segmenting y into singletons via `suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons` gives |y| tokens, where |y| = |w| - m by `List.length_map`. Since |w| ≤ r and 1 ≤ m, bounds `Nat.sub_le_sub_right` and `Nat.sub_le_sub_left` yield |w| - m ≤ r - 1 = (r - 1) + (1 - 1).
uses
suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons,List.length_map,Nat.zero_mod,Nat.sub_le_sub_right,Nat.sub_le_sub_left· intro hm0 refine ⟨y.map (fun a => [a]), suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ y, ?_⟩ rw [List.length_map, hleny] have hmne : m ≠ 0 := by intro hc; exact hm0 (by rw [hc, Nat.zero_mod]) have hm1 : 1 ≤ m := by omega have hle : w.length - m ≤ r - 1 := (Nat.sub_le_sub_right hwr m).trans (Nat.sub_le_sub_left hm1 r) simpa using hle
In the inductive step for q + 1, split w = c ++ rest and construct vocabulary V by adding c to the vocabulary obtained from rest.
Split w into prefix chunk c = w.take r and suffix rest = w.drop r, so w = c ++ rest by `List.take_append_drop`. Using `List.length_drop` and `Nat.succ_mul`, |rest| = |w| - r ≤ q * r. By induction hypothesis on rest, we obtain vocabulary Vr of size at most q. We then define V = insert c Vr if |c| ≥ 2 else Vr, which satisfies Vr ⊆ V via `Finset.mem_coe` and `Finset.mem_insert_of_mem`. Both c and rest are infixes of w (using `List.nil_append`).
uses
List.take_append_drop,List.length_drop,Nat.succ_mul,Finset.mem_coe,Finset.mem_insert_of_mem,List.nil_appendclassical let c : List α := w.take r let rest : List α := w.drop r have hwdecomp : w = c ++ rest := (List.take_append_drop r w).symm have hrest : rest.length ≤ q * r := by have hlen : rest.length = w.length - r := by show (w.drop r).length = _; rw [List.length_drop] rw [Nat.succ_mul] at hw rw [hlen] omega obtain ⟨Vr, hmemr, hcardr, hpropr⟩ := ih rest hrest let V : Finset (List α) := if 2 ≤ c.length then insert c Vr else Vr have hsub : (↑Vr : Set (List α)) ⊆ (↑V : Set (List α)) := by intro x hx rw [Finset.mem_coe] at hx ⊢ by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true]; exact Finset.mem_insert_of_mem hx · simp only [V, h2, if_false]; exact hx have hcinfix : c <:+: w := ⟨[], rest, by rw [List.nil_append]; exact List.take_append_drop r w⟩ have hrestsuffix : rest <:+ w := ⟨c, List.take_append_drop r w⟩ refine ⟨V, ?_, ?_, ?_⟩
The vocabulary V consists of substrings of w of length at least 2 and has cardinality at most q + 1.
Every element of V is either c (which is an infix of w of length at least 2) or an element of Vr (which is an infix of rest and hence of w, of length at least 2). By `Finset.card_insert_le`, |V| ≤ |Vr| + 1 ≤ q + 1.
uses
Finset.card_insert_le· intro u hu by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true, Finset.mem_insert] at hu rcases hu with rfl | hu · exact ⟨hcinfix, h2⟩ · obtain ⟨hinf, hlen⟩ := hmemr u hu exact ⟨hinf.trans hrestsuffix.isInfix, hlen⟩ · simp only [V, h2, if_false] at hu obtain ⟨hinf, hlen⟩ := hmemr u hu exact ⟨hinf.trans hrestsuffix.isInfix, hlen⟩ · by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true] calc (insert c Vr).card ≤ Vr.card + 1 := Finset.card_insert_le _ _ _ ≤ q + 1 := by omega · simp only [V, h2, if_false]; omega
In the inductive step, any suffix y = w.drop m with m % r = 0 and m < r can be segmented into at most q + 1 tokens.
Since m < r and m % r = 0, `Nat.mod_eq_of_lt` implies m = 0, so y = w = c ++ rest by `List.drop_zero`. The chunk c is segmented as [c], valid because either |c| ≥ 2 and c ∈ V by `Finset.mem_insert_self`, or |c| = 1 is a singleton (using `Nat.lt_of_le_of_lt`, `Nat.zero_le`, `List.length_take`, and `Nat.lt_min.mpr`). If rest is empty, y = c by `List.append_nil` and [c] has length 1 ≤ q + 1. If rest is nonempty, rest at offset 0 (0 % r = 0 by `Nat.zero_mod`) has a segmentation tr of length at most q by the induction hypothesis on rest. Appending [c] and tr via `suffix_segmentation_bound_by_chunk_vocabulary_seg_append` and `suffix_segmentation_bound_by_chunk_vocabulary_seg_mono` gives a segmentation of w of length 1 + |tr| ≤ q + 1 by `List.length_append` and `List.length_singleton`.
uses
Nat.mod_eq_of_lt,List.drop_zero,Nat.lt_of_le_of_lt,Nat.zero_le,List.length_take,Nat.lt_min.mpr,Finset.mem_coe,Finset.mem_insert_self,List.append_nil,Nat.zero_mod,suffix_segmentation_bound_by_chunk_vocabulary_seg_append,suffix_segmentation_bound_by_chunk_vocabulary_seg_mono,List.length_append,List.length_singleton· rw [suffix_segmentation_bound_by_chunk_vocabulary_prop] intro m y hmy hyne have hmlt : m < w.length := by by_contra h push Not at h exact hyne (by rw [← hmy]; exact List.drop_eq_nil_of_le h) constructor · intro hmr0 by_cases hmltr : m < r · have hm0 : m = 0 := by have hh : m % r = m := Nat.mod_eq_of_lt hmltr rw [hh] at hmr0 exact hmr0 have hyw : y = w := by rw [← hmy, hm0, List.drop_zero] have hwpos : 0 < w.length := Nat.lt_of_le_of_lt (Nat.zero_le m) hmlt have hclen : 0 < c.length := by rw [show c = w.take r from rfl, List.length_take] exact Nat.lt_min.mpr ⟨by omega, hwpos⟩ have hsegc : is_token_segmentation (↑V : Set (List α)) c [c] := by unfold is_token_segmentation refine ⟨by simp, ?_⟩ intro t ht simp only [List.mem_singleton] at ht rw [ht] by_cases h2 : 2 ≤ c.length · left rw [Finset.mem_coe] simp only [V, h2, if_true] exact Finset.mem_insert_self c Vr · right; omega by_cases hrestne : rest = [] · have hyc : y = c := by rw [hyw, hwdecomp, hrestne, List.append_nil] refine ⟨[c], ?_, by simp⟩ rw [hyc]; exact hsegc · obtain ⟨tr, hsegr, hlenr⟩ := (hpropr 0 rest List.drop_zero hrestne).1 (Nat.zero_mod r) refine ⟨[c] ++ tr, ?_, ?_⟩ · rw [hyw, hwdecomp] exact suffix_segmentation_bound_by_chunk_vocabulary_seg_append _ _ _ _ _ hsegc (suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hsegr) · rw [List.length_append, List.length_singleton]; omega
In the inductive step, any suffix y = w.drop m with m % r = 0 and m ≥ r can be segmented into at most q + 1 tokens.
Since m ≥ r, y = rest.drop (m - r) by `List.drop_drop`. By `Nat.add_mod_right`, (m - r) % r = m % r = 0. The induction hypothesis on rest provides a segmentation of y of length at most q ≤ q + 1, which remains valid for V by monotonicity `suffix_segmentation_bound_by_chunk_vocabulary_seg_mono`.
uses
Nat.add_mod_right,List.drop_drop,suffix_segmentation_bound_by_chunk_vocabulary_seg_mono· have hmod : (m - r) % r = m % r := by conv_rhs => rw [show m = (m - r) + r by omega] rw [Nat.add_mod_right] have hdrop : rest.drop (m - r) = y := by rw [show rest = w.drop r from rfl, List.drop_drop, show r + (m - r) = m by omega, hmy] obtain ⟨tokens, hseg, hlen⟩ := (hpropr (m - r) y hdrop hyne).1 (by rw [hmod]; exact hmr0) exact ⟨tokens, suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hseg, by omega⟩
In the inductive step, any suffix y = w.drop m with m % r ≠ 0 and m < r can be segmented into at most (r - 1) + q tokens.
Because m % r ≠ 0, m ≥ 1 by `Nat.zero_mod`. Also m < |c| by `List.length_take` and `Nat.lt_min.mpr`. By `List.drop_append` and `List.drop_zero`, y splits as (c.drop m) ++ rest. The remainder c.drop m has length at most r - 1 (using `List.length_drop`, `min_le_left`, `Nat.sub_le_sub_right`, and `Nat.sub_le_sub_left`) and is segmented into at most r - 1 singletons by `suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons` and `List.length_map`. If rest is empty, these singletons suffice by `List.append_nil`. If rest is nonempty, rest at offset 0 (using `Nat.zero_mod`) has a segmentation tr of length at most q by the induction hypothesis on rest. Combining the singletons and tr via `suffix_segmentation_bound_by_chunk_vocabulary_seg_append` and `suffix_segmentation_bound_by_chunk_vocabulary_seg_mono` yields at most (r - 1) + q tokens by `List.length_append`.
uses
Nat.zero_mod,List.length_take,Nat.lt_min.mpr,List.drop_append,List.drop_zero,List.length_drop,min_le_left,Nat.sub_le_sub_right,Nat.sub_le_sub_left,List.append_nil,suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons,List.length_map,suffix_segmentation_bound_by_chunk_vocabulary_seg_append,suffix_segmentation_bound_by_chunk_vocabulary_seg_mono,List.length_append· intro hmr0 by_cases hmltr : m < r · have hm1 : 1 ≤ m := by have hmne : m ≠ 0 := by intro hc; exact hmr0 (by rw [hc, Nat.zero_mod]) omega have hcmlen : m < c.length := by rw [show c = w.take r from rfl, List.length_take] exact Nat.lt_min.mpr ⟨hmltr, hmlt⟩ have hy : y = c.drop m ++ rest := by rw [← hmy, show w = c ++ rest from hwdecomp, List.drop_append] have hzero : m - c.length = 0 := by omega rw [hzero, List.drop_zero] have hlen1 : (c.drop m).length ≤ r - 1 := by rw [List.length_drop] have hc_le : c.length ≤ r := by rw [show c = w.take r from rfl, List.length_take]; exact min_le_left _ _ exact (Nat.sub_le_sub_right hc_le m).trans (Nat.sub_le_sub_left hm1 r) by_cases hrestne : rest = [] · have hy' : y = c.drop m := by rw [hy, hrestne, List.append_nil] refine ⟨(c.drop m).map (fun a => [a]), ?_, ?_⟩ · rw [hy']; exact suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ _ · rw [List.length_map]; omega · obtain ⟨tr, hsegr, hlenr⟩ := (hpropr 0 rest List.drop_zero hrestne).1 (Nat.zero_mod r) refine ⟨(c.drop m).map (fun a => [a]) ++ tr, ?_, ?_⟩ · rw [hy] exact suffix_segmentation_bound_by_chunk_vocabulary_seg_append _ _ _ _ _ (suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ _) (suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hsegr) · rw [List.length_append, List.length_map]; omega
In the inductive step, any suffix y = w.drop m with m % r ≠ 0 and m ≥ r can be segmented into at most (r - 1) + q tokens.
Since m ≥ r, y = rest.drop (m - r) by `List.drop_drop`. By `Nat.add_mod_right`, (m - r) % r = m % r ≠ 0. The induction hypothesis on rest provides a segmentation of y of length at most (r - 1) + (q - 1) ≤ (r - 1) + q, which is valid over V by monotonicity `suffix_segmentation_bound_by_chunk_vocabulary_seg_mono`.
uses
Nat.add_mod_right,List.drop_drop,suffix_segmentation_bound_by_chunk_vocabulary_seg_mono· have hmod : (m - r) % r = m % r := by conv_rhs => rw [show m = (m - r) + r by omega] rw [Nat.add_mod_right] have hdrop : rest.drop (m - r) = y := by rw [show rest = w.drop r from rfl, List.drop_drop, show r + (m - r) = m by omega, hmy] obtain ⟨tokens, hseg, hlen⟩ := (hpropr (m - r) y hdrop hyne).2 (by rw [hmod]; exact hmr0) exact ⟨tokens, suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hseg, by omega⟩
By induction on q ≥ 1, the chunk segmentation property holds for all q ≥ 1 and words of length at most q * r.
We proceed by mathematical induction on q ≥ 1 using `Nat.le_induction`. The base case q = 1 is established by `suffix_segmentation_bound_by_chunk_vocabulary_base`, and the induction step from q to q + 1 is established by `suffix_segmentation_bound_by_chunk_vocabulary_step`.
uses
Nat.le_induction,suffix_segmentation_bound_by_chunk_vocabulary_base,suffix_segmentation_bound_by_chunk_vocabulary_stepintro q hq induction q, hq using Nat.le_induction with | base => intro w hw; exact suffix_segmentation_bound_by_chunk_vocabulary_base r w hw | succ q hq ih => intro w hw exact suffix_segmentation_bound_by_chunk_vocabulary_step r q hr hq w hw ih
For the main theorem, choose chunk size r = ⌈|w| / q⌉ and obtain a vocabulary V_w of size at most q consisting of substrings of w of length at least 2.
Define r = ⌈|w| / q⌉. Because w is nonempty, |w| > 0 by `List.length_pos_iff.mpr`, so r ≥ 1 by `Nat.ceilDiv_eq_add_pred_div` and `Nat.div_pos`. Moreover, |w| ≤ q * r by `le_smul_ceilDiv`. Applying `suffix_segmentation_bound_by_chunk_vocabulary_aux` produces a vocabulary V of size at most q satisfying the chunk suffix segmentation property, whose elements are substrings of w of length at least 2.
uses
Nat.ceilDiv_eq_add_pred_div,Nat.div_pos,List.length_pos_iff.mpr,le_smul_ceilDiv,suffix_segmentation_bound_by_chunk_vocabulary_auxclassical set r : ℕ := w.length ⌈/⌉ q with hrdef have hr : 1 ≤ r := by rw [hrdef, Nat.ceilDiv_eq_add_pred_div] apply Nat.div_pos · have : 0 < w.length := List.length_pos_iff.mpr hw omega · omega have hbound : w.length ≤ q * r := by rw [hrdef] have := le_smul_ceilDiv (a := q) (b := w.length) (by omega : (0:ℕ) < q) simpa using this obtain ⟨V, hmem, hcard, hprop⟩ := suffix_segmentation_bound_by_chunk_vocabulary_aux r hr q (by omega) w hbound refine ⟨V, ?_, hcard, ?_⟩ · intro u hu simpa only [word_substrings, Set.mem_setOf_eq] using hmem u hu
Every nonempty suffix of w can be segmented into at most q - 1 + ⌈M / q⌉ tokens from V_w and singletons.
Any nonempty suffix y of w is written as y = w.drop |p| where w = p ++ y by `List.drop_append`. The chunk property gives two cases: if |p| % r = 0, y is segmented into at most q tokens, which is at most q - 1 + ⌈M / q⌉ by `chunk_token_bound_le`; if |p| % r ≠ 0, y is segmented into at most (r - 1) + (q - 1) = (⌈|w| / q⌉ - 1) + (q - 1) tokens, which is at most q - 1 + ⌈M / q⌉ by `chunk_inner_token_bound_le` since |w| ≤ M.
uses
List.drop_append,chunk_token_bound_le,chunk_inner_token_bound_le· intro y hy rw [word_suffixes] at hy simp only [Set.mem_setOf_eq] at hy obtain ⟨hsuf, hyne⟩ := hy obtain ⟨p, hp⟩ := hsuf have hdrop : w.drop p.length = y := by rw [← hp, List.drop_append] simp obtain ⟨hb0, hb1⟩ := hprop p.length y hdrop hyne by_cases hm0 : p.length % r = 0 · obtain ⟨tokens, hseg, hlen⟩ := hb0 hm0 exact ⟨tokens, hseg, hlen.trans (chunk_token_bound_le M q hq hqM)⟩ · obtain ⟨tokens, hseg, hlen⟩ := hb1 hm0 refine ⟨tokens, hseg, ?_⟩ have hreq : r - 1 = w.length ⌈/⌉ q - 1 := by rw [hrdef] rw [hreq] at hlen exact hlen.trans (chunk_inner_token_bound_le M q w.length hl)
List.flatten_append- The concatenation of two lists of lists has flattening equal to the concatenation of their individual flattenings.
suffix_segmentation_bound_by_chunk_vocabulary_singletons- Flattening the list of singletons of elements of l recovers the list l.
Or.inr- From a proof of B, deduce the disjunction A ∨ B.
List.infix_refl- Every list is an infix (substring) of itself.
List.drop_eq_nil_of_le- Dropping at least as many elements as the length of a list results in the empty list.
List.length_drop- The length of drop i l is the length of l minus i.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
List.drop_zero- Dropping zero elements leaves the list unchanged.
suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons- Segmenting any list into singleton tokens is a valid token segmentation under any vocabulary.
List.length_map- Mapping a function over a list preserves its length.
Nat.zero_mod- 0 % b = 0 for any natural number b.
Nat.sub_le_sub_right- Subtracting a fixed number preserves inequality: if n ≤ m, then n - k ≤ m - k.
Nat.sub_le_sub_left- Subtracting from a fixed number reverses inequality: if n ≤ m, then k - m ≤ k - n.
List.take_append_drop- Taking i elements and appending the remaining elements recovers the original list.
Nat.succ_mul- (n + 1) * m = n * m + m for natural numbers.
Finset.mem_coe- An element is in a coerced finset if and only if it is in the finset.
Finset.mem_insert_of_mem- An element in a finset remains in the finset after inserting another element.
List.nil_append- Prepending the empty list leaves a list unchanged.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Nat.lt_of_le_of_lt- If n ≤ m and m < k, then n < k.
Nat.zero_le- 0 ≤ n for every natural number n.
List.length_take- The length of take i l is min(i, |l|).
Nat.lt_min.mpr- If c < a and c < b, then c < min(a, b).
Finset.mem_insert_self- An element belongs to the finset formed by inserting it into any finset.
List.append_nil- Appending the empty list leaves a list unchanged.
suffix_segmentation_bound_by_chunk_vocabulary_seg_append- Concatenating valid token segmentations of two lists yields a valid token segmentation of their concatenation.
suffix_segmentation_bound_by_chunk_vocabulary_seg_mono- If V ⊆ W, any token segmentation valid for V is also valid for W.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_singleton- A singleton list has length 1.
Nat.add_mod_right- (x + z) % z = x % z for natural numbers.
List.drop_drop- Dropping i elements after dropping j elements is equivalent to dropping j + i elements.
List.drop_append- Dropping i elements from l₁ ++ l₂ drops i from l₁ concatenated with dropping i - |l₁| from l₂.
min_le_left- min(a, b) ≤ a for natural numbers.
Nat.le_induction- Principle of induction on natural numbers starting at a base value m.
suffix_segmentation_bound_by_chunk_vocabulary_base- Base case: every word of length at most r admits a vocabulary of size at most 1 satisfying the chunk suffix segmentation property for q = 1.
suffix_segmentation_bound_by_chunk_vocabulary_step- Inductive step: extending the chunk suffix segmentation property from q to q + 1.
Nat.ceilDiv_eq_add_pred_div- Ceiling division ⌈a / b⌉ equals (a + b - 1) / b.
Nat.div_pos- If 0 < b ≤ a, then 0 < a / b.
List.length_pos_iff.mpr- A nonempty list has strictly positive length.
le_smul_ceilDiv- For positive a, b ≤ a * ⌈b / a⌉.
suffix_segmentation_bound_by_chunk_vocabulary_aux- For any r ≥ 1 and q ≥ 1, words of length at most q * r admit a vocabulary of size at most q satisfying the suffix segmentation bound.
chunk_token_bound_le- q ≤ q - 1 + ⌈M / q⌉ whenever 2 ≤ q ≤ M.
chunk_inner_token_bound_le- (⌈l / q⌉ - 1) + (q - 1) ≤ q - 1 + ⌈M / q⌉ whenever l ≤ M.
- Single-character tokens (singletons) are permitted in token segmentations without belonging to the vocabulary V_w, which only contains substrings of length at least 2. In Lean, this is formalized by the disjunction in `is_token_segmentation`, where each token must either be in V or have length 1.
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.
private def suffix_segmentation_bound_by_chunk_vocabulary_prop {α : Type*} (r q : ℕ) (V : Finset (List α)) (w : List α) : Prop := ∀ (m : ℕ) (y : List α), w.drop m = y → y ≠ [] → ((m % r = 0 → ∃ tokens : List (List α), is_token_segmentation (↑V : Set (List α)) y tokens ∧ tokens.length ≤ q) ∧ (m % r ≠ 0 → ∃ tokens : List (List α), is_token_segmentation (↑V : Set (List α)) y tokens ∧ tokens.length ≤ (r - 1) + (q - 1)))private lemma suffix_segmentation_bound_by_chunk_vocabulary_singletons {α : Type*} (l : List α) : (l.map (fun a => [a])).flatten = l := by induction l with | nil => simp | cons a t ih => simp [ih]private lemma suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons {α : Type*} (V : Set (List α)) (y : List α) : is_token_segmentation V y (y.map (fun a => [a])) := by unfold is_token_segmentation constructor · rw [suffix_segmentation_bound_by_chunk_vocabulary_singletons] · intro t ht simp only [List.mem_map] at ht obtain ⟨a, _, rfl⟩ := ht exact Or.inr (by simp)private lemma suffix_segmentation_bound_by_chunk_vocabulary_seg_append {α : Type*} (V : Set (List α)) (a b : List α) (ta tb : List (List α)) (ha : is_token_segmentation V a ta) (hb : is_token_segmentation V b tb) : is_token_segmentation V (a ++ b) (ta ++ tb) := by unfold is_token_segmentation at * obtain ⟨h1, h2⟩ := ha obtain ⟨h3, h4⟩ := hb constructor · rw [List.flatten_append, h1, h3] · intro t ht simp only [List.mem_append] at ht rcases ht with h | h · exact h2 t h · exact h4 t hprivate lemma suffix_segmentation_bound_by_chunk_vocabulary_seg_mono {α : Type*} (V W : Set (List α)) (hVW : V ⊆ W) (y : List α) (t : List (List α)) (h : is_token_segmentation V y t) : is_token_segmentation W y t := by unfold is_token_segmentation at * exact ⟨h.1, fun u hu => (h.2 u hu).imp (fun hv => hVW hv) id⟩private theorem suffix_segmentation_bound_by_chunk_vocabulary_base {α : Type*} (r : ℕ) (w : List α) (hw : w.length ≤ 1 * r) : ∃ V : Finset (List α), (∀ u ∈ V, u <:+: w ∧ 2 ≤ u.length) ∧ V.card ≤ 1 ∧ suffix_segmentation_bound_by_chunk_vocabulary_prop r 1 V w := by classical let V : Finset (List α) := if 2 ≤ w.length then {w} else ∅ refine ⟨V, ?_, ?_, ?_⟩ · intro u hu by_cases h2 : 2 ≤ w.length · simp only [V, h2, if_true, Finset.mem_singleton] at hu rw [hu] exact ⟨List.infix_refl w, h2⟩ · simp [V, h2] at hu · simp only [V] by_cases h2 : 2 ≤ w.length <;> simp [h2] · rw [suffix_segmentation_bound_by_chunk_vocabulary_prop] intro m y hmy hyne have hmlt : m < w.length := by by_contra h push Not at h exact hyne (by rw [← hmy]; exact List.drop_eq_nil_of_le h) have hwr : w.length ≤ r := by simpa using hw have hmr : m < r := by omega have hleny : y.length = w.length - m := by rw [← hmy, List.length_drop] constructor · intro hm0 have hm0' : m = 0 := by have := Nat.mod_eq_of_lt hmr omega have hyw : y = w := by rw [← hmy, hm0', List.drop_zero] refine ⟨[w], ?_, by simp⟩ rw [hyw] unfold is_token_segmentation constructor · simp · intro t ht simp only [List.mem_singleton] at ht rw [ht] by_cases h2 : 2 ≤ w.length · left simp [V, h2] · right have h1 : w.length < 2 := by omega omega · intro hm0 refine ⟨y.map (fun a => [a]), suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ y, ?_⟩ rw [List.length_map, hleny] have hmne : m ≠ 0 := by intro hc; exact hm0 (by rw [hc, Nat.zero_mod]) have hm1 : 1 ≤ m := by omega have hle : w.length - m ≤ r - 1 := (Nat.sub_le_sub_right hwr m).trans (Nat.sub_le_sub_left hm1 r) simpa using hleprivate theorem suffix_segmentation_bound_by_chunk_vocabulary_step {α : Type*} (r q : ℕ) (hr : 1 ≤ r) (hq : 1 ≤ q) (w : List α) (hw : w.length ≤ (q + 1) * r) (ih : ∀ (w' : List α), w'.length ≤ q * r → ∃ V : Finset (List α), (∀ u ∈ V, u <:+: w' ∧ 2 ≤ u.length) ∧ V.card ≤ q ∧ suffix_segmentation_bound_by_chunk_vocabulary_prop r q V w') : ∃ V : Finset (List α), (∀ u ∈ V, u <:+: w ∧ 2 ≤ u.length) ∧ V.card ≤ q + 1 ∧ suffix_segmentation_bound_by_chunk_vocabulary_prop r (q + 1) V w := by classical let c : List α := w.take r let rest : List α := w.drop r have hwdecomp : w = c ++ rest := (List.take_append_drop r w).symm have hrest : rest.length ≤ q * r := by have hlen : rest.length = w.length - r := by show (w.drop r).length = _; rw [List.length_drop] rw [Nat.succ_mul] at hw rw [hlen] omega obtain ⟨Vr, hmemr, hcardr, hpropr⟩ := ih rest hrest let V : Finset (List α) := if 2 ≤ c.length then insert c Vr else Vr have hsub : (↑Vr : Set (List α)) ⊆ (↑V : Set (List α)) := by intro x hx rw [Finset.mem_coe] at hx ⊢ by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true]; exact Finset.mem_insert_of_mem hx · simp only [V, h2, if_false]; exact hx have hcinfix : c <:+: w := ⟨[], rest, by rw [List.nil_append]; exact List.take_append_drop r w⟩ have hrestsuffix : rest <:+ w := ⟨c, List.take_append_drop r w⟩ refine ⟨V, ?_, ?_, ?_⟩ · intro u hu by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true, Finset.mem_insert] at hu rcases hu with rfl | hu · exact ⟨hcinfix, h2⟩ · obtain ⟨hinf, hlen⟩ := hmemr u hu exact ⟨hinf.trans hrestsuffix.isInfix, hlen⟩ · simp only [V, h2, if_false] at hu obtain ⟨hinf, hlen⟩ := hmemr u hu exact ⟨hinf.trans hrestsuffix.isInfix, hlen⟩ · by_cases h2 : 2 ≤ c.length · simp only [V, h2, if_true] calc (insert c Vr).card ≤ Vr.card + 1 := Finset.card_insert_le _ _ _ ≤ q + 1 := by omega · simp only [V, h2, if_false]; omega · rw [suffix_segmentation_bound_by_chunk_vocabulary_prop] intro m y hmy hyne have hmlt : m < w.length := by by_contra h push Not at h exact hyne (by rw [← hmy]; exact List.drop_eq_nil_of_le h) constructor · intro hmr0 by_cases hmltr : m < r · have hm0 : m = 0 := by have hh : m % r = m := Nat.mod_eq_of_lt hmltr rw [hh] at hmr0 exact hmr0 have hyw : y = w := by rw [← hmy, hm0, List.drop_zero] have hwpos : 0 < w.length := Nat.lt_of_le_of_lt (Nat.zero_le m) hmlt have hclen : 0 < c.length := by rw [show c = w.take r from rfl, List.length_take] exact Nat.lt_min.mpr ⟨by omega, hwpos⟩ have hsegc : is_token_segmentation (↑V : Set (List α)) c [c] := by unfold is_token_segmentation refine ⟨by simp, ?_⟩ intro t ht simp only [List.mem_singleton] at ht rw [ht] by_cases h2 : 2 ≤ c.length · left rw [Finset.mem_coe] simp only [V, h2, if_true] exact Finset.mem_insert_self c Vr · right; omega by_cases hrestne : rest = [] · have hyc : y = c := by rw [hyw, hwdecomp, hrestne, List.append_nil] refine ⟨[c], ?_, by simp⟩ rw [hyc]; exact hsegc · obtain ⟨tr, hsegr, hlenr⟩ := (hpropr 0 rest List.drop_zero hrestne).1 (Nat.zero_mod r) refine ⟨[c] ++ tr, ?_, ?_⟩ · rw [hyw, hwdecomp] exact suffix_segmentation_bound_by_chunk_vocabulary_seg_append _ _ _ _ _ hsegc (suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hsegr) · rw [List.length_append, List.length_singleton]; omega · have hmod : (m - r) % r = m % r := by conv_rhs => rw [show m = (m - r) + r by omega] rw [Nat.add_mod_right] have hdrop : rest.drop (m - r) = y := by rw [show rest = w.drop r from rfl, List.drop_drop, show r + (m - r) = m by omega, hmy] obtain ⟨tokens, hseg, hlen⟩ := (hpropr (m - r) y hdrop hyne).1 (by rw [hmod]; exact hmr0) exact ⟨tokens, suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hseg, by omega⟩ · intro hmr0 by_cases hmltr : m < r · have hm1 : 1 ≤ m := by have hmne : m ≠ 0 := by intro hc; exact hmr0 (by rw [hc, Nat.zero_mod]) omega have hcmlen : m < c.length := by rw [show c = w.take r from rfl, List.length_take] exact Nat.lt_min.mpr ⟨hmltr, hmlt⟩ have hy : y = c.drop m ++ rest := by rw [← hmy, show w = c ++ rest from hwdecomp, List.drop_append] have hzero : m - c.length = 0 := by omega rw [hzero, List.drop_zero] have hlen1 : (c.drop m).length ≤ r - 1 := by rw [List.length_drop] have hc_le : c.length ≤ r := by rw [show c = w.take r from rfl, List.length_take]; exact min_le_left _ _ exact (Nat.sub_le_sub_right hc_le m).trans (Nat.sub_le_sub_left hm1 r) by_cases hrestne : rest = [] · have hy' : y = c.drop m := by rw [hy, hrestne, List.append_nil] refine ⟨(c.drop m).map (fun a => [a]), ?_, ?_⟩ · rw [hy']; exact suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ _ · rw [List.length_map]; omega · obtain ⟨tr, hsegr, hlenr⟩ := (hpropr 0 rest List.drop_zero hrestne).1 (Nat.zero_mod r) refine ⟨(c.drop m).map (fun a => [a]) ++ tr, ?_, ?_⟩ · rw [hy] exact suffix_segmentation_bound_by_chunk_vocabulary_seg_append _ _ _ _ _ (suffix_segmentation_bound_by_chunk_vocabulary_seg_singletons _ _) (suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hsegr) · rw [List.length_append, List.length_map]; omega · have hmod : (m - r) % r = m % r := by conv_rhs => rw [show m = (m - r) + r by omega] rw [Nat.add_mod_right] have hdrop : rest.drop (m - r) = y := by rw [show rest = w.drop r from rfl, List.drop_drop, show r + (m - r) = m by omega, hmy] obtain ⟨tokens, hseg, hlen⟩ := (hpropr (m - r) y hdrop hyne).2 (by rw [hmod]; exact hmr0) exact ⟨tokens, suffix_segmentation_bound_by_chunk_vocabulary_seg_mono _ _ hsub _ _ hseg, by omega⟩private theorem suffix_segmentation_bound_by_chunk_vocabulary_aux {α : Type*} (r : ℕ) (hr : 1 ≤ r) : ∀ q : ℕ, 1 ≤ q → ∀ w : List α, w.length ≤ q * r → ∃ V : Finset (List α), (∀ u ∈ V, u <:+: w ∧ 2 ≤ u.length) ∧ V.card ≤ q ∧ suffix_segmentation_bound_by_chunk_vocabulary_prop r q V w := by intro q hq induction q, hq using Nat.le_induction with | base => intro w hw; exact suffix_segmentation_bound_by_chunk_vocabulary_base r w hw | succ q hq ih => intro w hw exact suffix_segmentation_bound_by_chunk_vocabulary_step r q hr hq w hw ih/-- arXiv:2611.15074 Lemma 3.8: Suffix segmentation bound by chunk vocabulary. -/theorem suffix_segmentation_bound_by_chunk_vocabulary {α : Type*} (M q : ℕ) (hq : 2 ≤ q) (hqM : q ≤ M) (w : List α) (hw : w ≠ []) (hl : w.length ≤ M) : ∃ V_w : Finset (List α), (∀ u ∈ V_w, u ∈ word_substrings w) ∧ V_w.card ≤ q ∧ ∀ y ∈ word_suffixes w, ∃ tokens : List (List α), is_token_segmentation (↑V_w) y tokens ∧ tokens.length ≤ q - 1 + M ⌈/⌉ q := by classical set r : ℕ := w.length ⌈/⌉ q with hrdef have hr : 1 ≤ r := by rw [hrdef, Nat.ceilDiv_eq_add_pred_div] apply Nat.div_pos · have : 0 < w.length := List.length_pos_iff.mpr hw omega · omega have hbound : w.length ≤ q * r := by rw [hrdef] have := le_smul_ceilDiv (a := q) (b := w.length) (by omega : (0:ℕ) < q) simpa using this obtain ⟨V, hmem, hcard, hprop⟩ := suffix_segmentation_bound_by_chunk_vocabulary_aux r hr q (by omega) w hbound refine ⟨V, ?_, hcard, ?_⟩ · intro u hu simpa only [word_substrings, Set.mem_setOf_eq] using hmem u hu · intro y hy rw [word_suffixes] at hy simp only [Set.mem_setOf_eq] at hy obtain ⟨hsuf, hyne⟩ := hy obtain ⟨p, hp⟩ := hsuf have hdrop : w.drop p.length = y := by rw [← hp, List.drop_append] simp obtain ⟨hb0, hb1⟩ := hprop p.length y hdrop hyne by_cases hm0 : p.length % r = 0 · obtain ⟨tokens, hseg, hlen⟩ := hb0 hm0 exact ⟨tokens, hseg, hlen.trans (chunk_token_bound_le M q hq hqM)⟩ · obtain ⟨tokens, hseg, hlen⟩ := hb1 hm0 refine ⟨tokens, hseg, ?_⟩ have hreq : r - 1 = w.length ⌈/⌉ q - 1 := by rw [hrdef] rw [hreq] at hlen exact hlen.trans (chunk_inner_token_bound_le M q w.length hl)