AFTD Auto-Formalizing Theoretical Domains

nat_scaled_floor_lt

theoremverified

For positive natural n and N, and natural i less than n, floor(i*N/n) is less than N.

Statement

theorem nat_scaled_floor_lt
    (n N : ℕ) (hn : 0 < n) (hN : 0 < N) (i : ℕ) (hi : i < n) : i*N/n < N
Source
arXiv:2610.15635, Proposition 3.2, with induced floor embedding from Lemma 3.1 and cover restriction from Lemma 2.1. This formalizes the published upper bound serving OP-205 / RT-1; no new research result is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1
  • cycle_power_floor_map_inducedFor natural n,N,k,K with n positive, N at least n, k*N at most K*n, and (K+1)*n at most (k+1)*N, the balanced floor map from ZMod n to…

The proof, explained

To show that (i * N) / n < N for positive natural numbers n and N and an index i < n, the division inequality is first rephrased as the multiplication bound i * N < N * n. This inequality then follows directly by multiplying i < n by N and applying commutativity of multiplication.

  1. It suffices to show that i * N < N * n.

    Because n > 0 (hn), integer division (i * N) / n < N is equivalent to i * N < N * n by Nat.div_lt_iff_lt_mul. Applying the right-to-left direction reduces the goal accordingly.

    line 7

    uses Nat.div_lt_iff_lt_mul

      apply (Nat.div_lt_iff_lt_mul hn).mpr
  2. i * N < N * n, completing the proof.

    Multiplying the assumption i < n (hi) on the right by N > 0 (hN) yields i * N < n * N via Nat.mul_lt_mul_of_pos_right. Nonlinear arithmetic then finishes the goal using the commutativity of multiplication (n * N = N * n).

    lines 8–9

    uses Nat.mul_lt_mul_of_pos_right

      have hprod := Nat.mul_lt_mul_of_pos_right hi hN
      nlinarith
Nat.div_lt_iff_lt_mul
For natural numbers with k > 0, x / k < y if and only if x < y * k.
Nat.mul_lt_mul_of_pos_right
Multiplying a strict inequality of natural numbers n < m on the right by a positive natural number k > 0 preserves strict inequality, yielding n * k < m * k.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem nat_scaled_floor_lt    (n N : ℕ) (hn : 0 < n) (hN : 0 < N) (i : ℕ) (hi : i < n) : i*N/n < N := by  apply (Nat.div_lt_iff_lt_mul hn).mpr  have hprod := Nat.mul_lt_mul_of_pos_right hi hN  nlinarith
See it in the graphDiscuss this resultChallenge it