nat_scaled_floor_lt
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- 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.
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.
uses
Nat.div_lt_iff_lt_mulapply (Nat.div_lt_iff_lt_mul hn).mpri * 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).
uses
Nat.mul_lt_mul_of_pos_righthave 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
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.
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