AFTD Auto-Formalizing Theoretical Domains

nat_scaled_floor_gap_threshold

theoremverified

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

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.

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

    lines 10–12

    uses Nat.div_le_div_right, Nat.mul_le_mul_right

      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)
  2. 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).

    lines 13–20

    uses Nat.div_add_mod', Nat.mod_lt

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

    lines 21–22

      change j-i ≤ k ↔ B-A ≤ K
      constructor
  4. 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.

    lines 23–30

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

    lines 31–38

    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

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