AFTD Auto-Formalizing Theoretical Domains

nat_scaled_floor_strict

theoremverified

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.

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

    line 8

    uses Nat.div_le_div_right, Nat.mul_le_mul_right

      have hle : i*N/n ≤ j*N/n := Nat.div_le_div_right (Nat.mul_le_mul_right N hij.le)
  2. 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.

    lines 9–10

      by_contra hnlt
      have heq : i*N/n = j*N/n := by omega
  3. 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.

    lines 11–14

    uses Nat.div_add_mod', Nat.mod_lt

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

    lines 15–17

    uses Nat.mul_le_mul_right, Nat.add_mul, Nat.one_mul

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

    line 18

      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

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