nat_scaled_floor_gap_threshold
Let n,N,k,K be natural numbers with n positive, k*N at most K*n, and (K+1)*n at most (k+1)*N. For natural i at most j, j-i is at most k if and only if floor(j*N/n)-floor(i*N/n) is at most K.
Statement
theorem nat_scaled_floor_gap_threshold
(n N k K : ℕ) (hn : 0 < n)
(hlo : k*N ≤ K*n) (hhi : (K+1)*n ≤ (k+1)*N)
(i j : ℕ) (hij : i ≤ j) :
j-i ≤ k ↔ j*N/n-i*N/n ≤ K- 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
The theorem establishes that when the scaling ratio N / n satisfies k * N ≤ K * n and (K + 1) * n ≤ (k + 1) * N, an index difference j - i ≤ k is equivalent to a floor difference ⌊j * N / n⌋ - ⌊i * N / n⌋ ≤ K. The proof expresses each dividend as quotient times divisor plus remainder, bounding the remainders strictly below n. Each direction of the equivalence is then proved by contradiction: assuming the inequality fails and multiplying by n or N produces an expanded system of linear inequalities that contradicts the scaling constraints.
Setting A = ⌊i * N / n⌋ and B = ⌊j * N / n⌋, we have A ≤ B.
We introduce abbreviations A and B for the integer quotients ⌊i * N / n⌋ and ⌊j * N / n⌋. Since i ≤ j, multiplying both sides by N gives i * N ≤ j * N (via Nat.mul_le_mul_right), and integer division by n preserves this inequality (via Nat.div_le_div_right), so A ≤ B.
uses
Nat.div_le_div_right,Nat.mul_le_mul_rightlet A := i*N/n let B := j*N/n have hAB : A ≤ B := Nat.div_le_div_right (Nat.mul_le_mul_right N hij)
The Euclidean division identities n * A + (i * N) % n = i * N and n * B + (j * N) % n = j * N hold, with both remainders strictly less than n.
By Euclidean division (Nat.div_add_mod'), divisor times quotient plus remainder equals the dividend, giving the exact decompositions for i * N and j * N. Because n > 0, each remainder is strictly bounded above by n (via Nat.mod_lt).
uses
Nat.div_add_mod',Nat.mod_lthave hA : n*A+(i*N)%n = i*N := by dsimp [A] nlinarith [Nat.div_add_mod' (i*N) n] have hB : n*B+(j*N)%n = j*N := by dsimp [B] nlinarith [Nat.div_add_mod' (j*N) n] have hri := Nat.mod_lt (i*N) hn have hrj := Nat.mod_lt (j*N) hn
It suffices to prove the equivalence j - i ≤ k ↔ B - A ≤ K by proving each implication separately.
We rephrase the goal in terms of the abbreviations A and B as j - i ≤ k ↔ B - A ≤ K, and split the logical equivalence into the forward and backward directions.
change j-i ≤ k ↔ B-A ≤ K constructor
If j - i ≤ k, then B - A ≤ K.
We proceed by contradiction. From j - i ≤ k we have j ≤ i + k, so multiplying by N gives j * N ≤ (i + k) * N = i * N + k * N (Nat.mul_le_mul_right). Assuming for contradiction that B - A > K, we obtain A + K + 1 ≤ B, which upon multiplying by n gives n * A + n * K + n ≤ n * B (Nat.mul_le_mul_left). After distributing products (Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one) and commuting K * n to n * K in the hypothesis k * N ≤ K * n (Nat.mul_comm), this forces n * A + n * K + n ≤ n * B ≤ j * N ≤ i * N + k * N = n * A + (i * N) % n + k * N < n * A + n + n * K, which is impossible. Linear arithmetic (omega) closes the contradiction.
uses
Nat.mul_le_mul_right,Nat.mul_le_mul_left,Nat.add_mul,Nat.mul_add,Nat.one_mul,Nat.mul_one,Nat.mul_comm· intro h have hprod := Nat.mul_le_mul_right N (show j ≤ i+k by omega) by_contra hnot have hgap : A+K+1 ≤ B := by omega have hmul := Nat.mul_le_mul_left n hgap simp only [Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one] at hprod hmul rw [Nat.mul_comm K n] at hlo omega
If B - A ≤ K, then j - i ≤ k.
Again we argue by contradiction. The assumption B - A ≤ K yields B ≤ A + K, so n * B ≤ n * A + n * K (Nat.mul_le_mul_left). Assuming for contradiction that j - i > k gives i + k + 1 ≤ j, hence (i + k + 1) * N ≤ j * N (Nat.mul_le_mul_right). Expanding products with distributivity (Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one) and commuting K * n in (K + 1) * n ≤ (k + 1) * N (Nat.mul_comm), we find that j * N = n * B + (j * N) % n < n * A + n * K + n ≤ n * A + (k + 1) * N ≤ i * N + k * N + N ≤ j * N, a contradiction detected by linear integer arithmetic (omega).
uses
Nat.mul_le_mul_right,Nat.mul_le_mul_left,Nat.add_mul,Nat.mul_add,Nat.one_mul,Nat.mul_one,Nat.mul_comm· intro h by_contra hnot have hprod := Nat.mul_le_mul_right N (show i+k+1 ≤ j by omega) have hgap : B ≤ A+K := by omega have hmul := Nat.mul_le_mul_left n hgap simp only [Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one] at hprod hmul hhi rw [Nat.mul_comm K n] at hhi omega
Nat.div_le_div_right- integer division by a positive constant preserves order: if a ≤ b, then a / c ≤ b / c
Nat.mul_le_mul_right- multiplication on the right by a natural number preserves order: if n ≤ m, then n * k ≤ m * k
Nat.div_add_mod'- the division with remainder identity: (a / b) * b + a % b = a
Nat.mod_lt- the remainder modulo a positive divisor y is strictly less than y: if 0 < y, then x % y < y
Nat.mul_le_mul_left- multiplication on the left by a natural number preserves order: if n ≤ m, then k * n ≤ k * m
Nat.add_mul- right distributivity of multiplication over addition: (n + m) * k = n * k + m * k
Nat.mul_add- left distributivity of multiplication over addition: n * (m + k) = n * m + n * k
Nat.one_mul- multiplication by 1 on the left is the identity: 1 * n = n
Nat.mul_one- multiplication by 1 on the right is the identity: n * 1 = n
Nat.mul_comm- multiplication of natural numbers is commutative: n * m = m * n
- In step 2, `nlinarith` verifies the division identity $n A + (i N \bmod n) = i N$ by combining `Nat.div_add_mod'` with the commutativity of multiplication.
- In steps 4 and 5, the final contradiction is closed by `omega` via Presburger linear integer arithmetic over $\mathbb{N}$ on the expanded inequalities and remainder bounds.
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_gap_threshold (n N k K : ℕ) (hn : 0 < n) (hlo : k*N ≤ K*n) (hhi : (K+1)*n ≤ (k+1)*N) (i j : ℕ) (hij : i ≤ j) : j-i ≤ k ↔ j*N/n-i*N/n ≤ K := by let A := i*N/n let B := j*N/n have hAB : A ≤ B := Nat.div_le_div_right (Nat.mul_le_mul_right N hij) have hA : n*A+(i*N)%n = i*N := by dsimp [A] nlinarith [Nat.div_add_mod' (i*N) n] have hB : n*B+(j*N)%n = j*N := by dsimp [B] nlinarith [Nat.div_add_mod' (j*N) n] have hri := Nat.mod_lt (i*N) hn have hrj := Nat.mod_lt (j*N) hn change j-i ≤ k ↔ B-A ≤ K constructor · intro h have hprod := Nat.mul_le_mul_right N (show j ≤ i+k by omega) by_contra hnot have hgap : A+K+1 ≤ B := by omega have hmul := Nat.mul_le_mul_left n hgap simp only [Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one] at hprod hmul rw [Nat.mul_comm K n] at hlo omega · intro h by_contra hnot have hprod := Nat.mul_le_mul_right N (show i+k+1 ≤ j by omega) have hgap : B ≤ A+K := by omega have hmul := Nat.mul_le_mul_left n hgap simp only [Nat.add_mul, Nat.mul_add, Nat.one_mul, Nat.mul_one] at hprod hmul hhi rw [Nat.mul_comm K n] at hhi omega