nat_scaled_floor_strict
For positive natural n and natural N at least n, the map i to floor(i*N/n) is strictly increasing on the natural numbers.
Statement
theorem nat_scaled_floor_strict
(n N : ℕ) (hn : 0 < n) (hN : n ≤ N) (i j : ℕ) (hij : i < j) :
i*N/n < j*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
Quot.soundpropext- 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
The proof proceeds by contradiction. If the strict inequality ⌊i * N / n⌋ < ⌊j * N / n⌋ fails, then weak monotonicity forces the two integer quotients to be equal. Writing both i * N and j * N in quotient-remainder form shows that their difference j * N - i * N equals the difference of their remainders, which is strictly less than n. But since i < j, we also have j * N - i * N ≥ N ≥ n, producing a contradiction.
(i * N) / n ≤ (j * N) / n
Since i < j, we have i ≤ j. Multiplying both sides by N preserves the inequality, giving i * N ≤ j * N, and dividing both sides by n preserves weak inequalities, yielding (i * N) / n ≤ (j * N) / n.
uses
Nat.div_le_div_right,Nat.mul_le_mul_righthave hle : i*N/n ≤ j*N/n := Nat.div_le_div_right (Nat.mul_le_mul_right N hij.le)Under the assumption that strict inequality fails, (i * N) / n = (j * N) / n.
Assume for contradiction that (i * N) / n < (j * N) / n does not hold. Because (i * N) / n ≤ (j * N) / n was already established, linear arithmetic forces the two quotients to be equal.
by_contra hnlt have heq : i*N/n = j*N/n := by omega
The Euclidean division identities and remainder bounds for i * N and j * N hold.
By the division algorithm, i * N = ((i * N) / n) * n + (i * N % n) and j * N = ((j * N) / n) * n + (j * N % n). Because n > 0, both remainders i * N % n and j * N % n are strictly less than n.
uses
Nat.div_add_mod',Nat.mod_lthave hi := Nat.div_add_mod' (i*N) n have hj := Nat.div_add_mod' (j*N) n have hri := Nat.mod_lt (i*N) hn have hrj := Nat.mod_lt (j*N) hn
i * N + N ≤ j * N, and ((j * N) / n) * n + (i * N % n) = i * N.
Because i < j, we have i + 1 ≤ j, so multiplying by N gives (i + 1) * N ≤ j * N, which expands to i * N + N ≤ j * N. Furthermore, substituting the equality of quotients into the division formula for i * N expresses i * N using the quotient of j * N.
uses
Nat.mul_le_mul_right,Nat.add_mul,Nat.one_mulhave hprod := Nat.mul_le_mul_right N (show i+1 ≤ j by omega) rw [heq] at hi simp only [Nat.add_mul, Nat.one_mul] at hprod
Contradiction.
Subtracting the two division identities shows that the difference j * N - i * N equals the difference of the remainders, which is strictly less than n. However, j * N - i * N ≥ N ≥ n, creating a contradiction that linear integer arithmetic recognizes to close the proof.
omega
Nat.div_le_div_right- Integer division by a fixed divisor preserves weak inequalities: if a ≤ b, then a / c ≤ b / c.
Nat.mul_le_mul_right- Multiplication by a fixed factor on the right preserves weak inequalities: if n ≤ m, then n * k ≤ m * k.
Nat.div_add_mod'- The quotient-remainder identity: for natural numbers a and b, (a / b) * b + a % b = a.
Nat.mod_lt- The remainder of natural division x % y is strictly less than y, provided 0 < y.
Nat.add_mul- Multiplication distributes over addition on the right: (n + m) * k = n * k + m * k.
Nat.one_mul- One is the left identity for multiplication: 1 * n = n.
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_strict (n N : ℕ) (hn : 0 < n) (hN : n ≤ N) (i j : ℕ) (hij : i < j) : i*N/n < j*N/n := by have hle : i*N/n ≤ j*N/n := Nat.div_le_div_right (Nat.mul_le_mul_right N hij.le) by_contra hnlt have heq : i*N/n = j*N/n := by omega have hi := Nat.div_add_mod' (i*N) n have hj := Nat.div_add_mod' (j*N) n have hri := Nat.mod_lt (i*N) hn have hrj := Nat.mod_lt (j*N) hn have hprod := Nat.mul_le_mul_right N (show i+1 ≤ j by omega) rw [heq] at hi simp only [Nat.add_mul, Nat.one_mul] at hprod omega