chunk_token_bound_le
For 2 ≤ q ≤ M, the number of chunks q is at most q - 1 + ⌈M / q⌉.
Statement
theorem chunk_token_bound_le (M q : ℕ) (hq : 2 ≤ q) (hqM : q ≤ M) :
q ≤ 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 any natural numbers $M$ and $q$, if $2 \le q$ and $q \le M$, then $q \le (q - 1) + (M ⌈/⌉ q)$, where $M ⌈/⌉ q$ denotes natural ceiling division (Nat.ceilDiv M q).
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 reduces the inequality to showing that ⌈M / q⌉ ≥ 1 and adding this bound to q - 1. Because q ≤ M ≤ q * ⌈M / q⌉ and q > 0, cancelling q establishes 1 ≤ ⌈M / q⌉. Decomposing q as (q - 1) + 1 then gives q ≤ q - 1 + ⌈M / q⌉ by monotonicity of addition.
M ≤ q * ⌈M / q⌉
Since 2 ≤ q, q is strictly positive. By the characteristic property of ceiling division (le_smul_ceilDiv), M is bounded above by q * ⌈M / q⌉.
uses
le_smul_ceilDivhave hqpos : 0 < q := by omega have h1 : M ≤ q * (M ⌈/⌉ q) := by simpa using le_smul_ceilDiv (a := q) (b := M) hqpos
1 ≤ ⌈M / q⌉
Combining q ≤ M with M ≤ q * ⌈M / q⌉ gives q * 1 ≤ q * ⌈M / q⌉ by linear arithmetic. Cancelling the positive factor q via Nat.le_of_mul_le_mul_left yields 1 ≤ ⌈M / q⌉.
uses
Nat.le_of_mul_le_mul_lefthave hc : 1 ≤ M ⌈/⌉ q := by have : q * 1 ≤ q * (M ⌈/⌉ q) := by omega exact Nat.le_of_mul_le_mul_left this hqpos
q ≤ q - 1 + ⌈M / q⌉
Since 1 ≤ q, rewriting q as (q - 1) + 1 using Nat.sub_add_cancel and adding q - 1 to both sides of 1 ≤ ⌈M / q⌉ via Nat.add_le_add_left yields q = (q - 1) + 1 ≤ q - 1 + ⌈M / q⌉.
uses
Nat.sub_add_cancel,Nat.add_le_add_leftcalc q = q - 1 + 1 := (Nat.sub_add_cancel (by omega : 1 ≤ q)).symm _ ≤ q - 1 + M ⌈/⌉ q := Nat.add_le_add_left hc _
le_smul_ceilDiv- For any positive divisor a and quantity b, b ≤ a • ⌈b / a⌉.
Nat.le_of_mul_le_mul_left- For natural numbers, if c * a ≤ c * b and 0 < c, then a ≤ b (cancelling a positive factor preserves the inequality).
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
Nat.add_le_add_left- Adding a natural number k to the left of both sides preserves an inequality: if n ≤ m, then k + n ≤ k + m.
- In natural number arithmetic (ℕ), the identity (q - 1) + 1 = q requires the side condition 1 ≤ q, which holds here since 2 ≤ q.
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 q ≤ q - 1 + ⌈M / q⌉ for Case 1 of Lemma 3.8. -/theorem chunk_token_bound_le (M q : ℕ) (hq : 2 ≤ q) (hqM : q ≤ M) : q ≤ q - 1 + M ⌈/⌉ q := by have hqpos : 0 < q := by omega have h1 : M ≤ q * (M ⌈/⌉ q) := by simpa using le_smul_ceilDiv (a := q) (b := M) hqpos have hc : 1 ≤ M ⌈/⌉ q := by have : q * 1 ≤ q * (M ⌈/⌉ q) := by omega exact Nat.le_of_mul_le_mul_left this hqpos calc q = q - 1 + 1 := (Nat.sub_add_cancel (by omega : 1 ≤ q)).symm _ ≤ q - 1 + M ⌈/⌉ q := Nat.add_le_add_left hc _