chunk_inner_token_bound_le
For l ≤ M and natural numbers q and M, (⌈l / q⌉ - 1) + (q - 1) is at most q - 1 + ⌈M / q⌉.
Statement
theorem chunk_inner_token_bound_le (M q l : ℕ) (hl : l ≤ M) :
(l ⌈/⌉ q - 1) + (q - 1) ≤ q - 1 + M ⌈/⌉ q- Source
- arXiv:2611.15074, Lemma 3.8 proof
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- suffix_segmentation_bound_by_chunk_vocabularyFix 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…
Read back from the Lean
For all natural numbers $M$, $q$, and $l$, if $l \le M$, then $(l \lceil/\rceil q - 1) + (q - 1) \le (q - 1) + M \lceil/\rceil q$, where $\lceil/\rceil$ denotes ceiling division on natural numbers (Nat.ceilDiv) and subtraction is truncated subtraction on $\mathbb{N}$.
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 first establishes the monotonicity of ceiling division, showing that ⌈l / q⌉ ≤ ⌈M / q⌉ whenever l ≤ M. It does this by rewriting ceiling division in terms of standard integer division and applying division monotonicity. The main inequality then follows directly by linear arithmetic on natural numbers.
⌈l / q⌉ ≤ ⌈M / q⌉
Rewriting both sides with `Nat.ceilDiv_eq_add_pred_div` expresses ceiling division a ⌈/⌉ q in terms of standard natural division as (a + q - 1) / q. Because l ≤ M implies l + q - 1 ≤ M + q - 1 by linear arithmetic, `Nat.div_le_div_right` establishes that the inequality is preserved after division by q.
uses
Nat.ceilDiv_eq_add_pred_div,Nat.div_le_div_righthave h : l ⌈/⌉ q ≤ M ⌈/⌉ q := by rw [Nat.ceilDiv_eq_add_pred_div, Nat.ceilDiv_eq_add_pred_div] exact Nat.div_le_div_right (by omega)
(⌈l / q⌉ - 1) + (q - 1) ≤ q - 1 + ⌈M / q⌉
Linear integer arithmetic (`omega`) finishes the proof of the desired inequality from the intermediate bound ⌈l / q⌉ ≤ ⌈M / q⌉.
omega
Nat.ceilDiv_eq_add_pred_div- For any natural numbers a and b, the ceiling division a ⌈/⌉ b equals (a + b - 1) / b.
Nat.div_le_div_right- For natural numbers a, b, and c, if a ≤ b, then a / c ≤ b / c.
- In natural number arithmetic, subtraction truncates at zero (a - b = 0 when a ≤ b); the linear arithmetic solver `omega` automatically accounts for this truncation behavior.
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.
/-- Arithmetic inequality (⌈l / q⌉ - 1) + (q - 1) ≤ q - 1 + ⌈M / q⌉ for Case 2 of Lemma 3.8. -/theorem chunk_inner_token_bound_le (M q l : ℕ) (hl : l ≤ M) : (l ⌈/⌉ q - 1) + (q - 1) ≤ q - 1 + M ⌈/⌉ q := by have h : l ⌈/⌉ q ≤ M ⌈/⌉ q := by rw [Nat.ceilDiv_eq_add_pred_div, Nat.ceilDiv_eq_add_pred_div] exact Nat.div_le_div_right (by omega) omega