AFTD Auto-Formalizing Theoretical Domains

chunk_token_bound_le

theoremverified

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

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.

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

    lines 4–6

    uses le_smul_ceilDiv

      have hqpos : 0 < q := by omega
      have h1 : M ≤ q * (M ⌈/⌉ q) := by
        simpa using le_smul_ceilDiv (a := q) (b := M) hqpos
  2. 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⌉.

    lines 7–9

    uses Nat.le_of_mul_le_mul_left

      have hc : 1 ≤ M ⌈/⌉ q := by
        have : q * 1 ≤ q * (M ⌈/⌉ q) := by omega
        exact Nat.le_of_mul_le_mul_left this hqpos
  3. 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⌉.

    lines 10–11

    uses Nat.sub_add_cancel, Nat.add_le_add_left

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

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