AFTD Auto-Formalizing Theoretical Domains

chunk_inner_token_bound_le

theoremverified

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

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.

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

    lines 4–6

    uses Nat.ceilDiv_eq_add_pred_div, Nat.div_le_div_right

      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)
  2. (⌈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⌉.

    line 7

      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.

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

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