AFTD Auto-Formalizing Theoretical Domains

suffix_segmentation_bound_by_chunk_vocabulary

theoremverifiedformalization

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⌉.

  1. 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.

    lines 11–13

      induction l with
      | nil => simp
      | cons a t ih => simp [ih]
  2. 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`.

    lines 18–24

    uses suffix_segmentation_bound_by_chunk_vocabulary_singletons, Or.inr

      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)
  3. 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.

    lines 30–39

    uses List.flatten_append

      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 h
  4. 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.

    lines 44–45

      unfold is_token_segmentation at *
      exact ⟨h.1, fun u hu => (h.2 u hu).imp (fun hv => hVW hv) id⟩
  5. 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.

    lines 52–62

    uses List.infix_refl

      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]
  6. 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.

    lines 63–91

    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
  7. 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).

    lines 92–99

    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
  8. 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`).

    lines 110–130

    uses List.take_append_drop, List.length_drop, Nat.succ_mul, Finset.mem_coe, Finset.mem_insert_of_mem, List.nil_append

      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, ?_, ?_, ?_⟩
  9. 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.

    lines 131–145

    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
  10. 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`.

    lines 146–185

    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
  11. 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`.

    lines 186–195

    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⟩
  12. 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`.

    lines 196–224

    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
  13. 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`.

    lines 225–234

    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⟩
  14. 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`.

    lines 241–246

    uses Nat.le_induction, suffix_segmentation_bound_by_chunk_vocabulary_base, suffix_segmentation_bound_by_chunk_vocabulary_step

      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
  15. 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.

    lines 258–274

    uses Nat.ceilDiv_eq_add_pred_div, Nat.div_pos, List.length_pos_iff.mpr, le_smul_ceilDiv, suffix_segmentation_bound_by_chunk_vocabulary_aux

      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
  16. 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.

    lines 275–291

    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.

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

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)
See it in the graphDiscuss this resultChallenge it