AFTD Auto-Formalizing Theoretical Domains

cycle_power_inflation_parameters

theoremverified

For natural k at least one and natural n at least both 2*k+2 and 2*k squared, put q=floor((n+k)/(k+1)). Then q is at least two, n is at most q*(2*k+1), q*(2*k+1) is at most 2*n, and (2*k+1)*n is at most (k+1)*q*(2*k+1).

Statement

theorem cycle_power_inflation_parameters
    (n k : ℕ) (hk : 1 ≤ k) (hn₀ : 2*k+2 ≤ n) (hn₂ : 2*k^2 ≤ n) :
    let q := (n+k)/(k+1)
    2 ≤ q ∧ n ≤ q*(2*k+1) ∧ q*(2*k+1) ≤ 2*n ∧
      (2*k+1)*n ≤ (k+1)*(q*(2*k+1))
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 2

The proof, explained

The proof establishes four bounding inequalities for the integer quotient $q = \lfloor (n+k)/(k+1) \rfloor$ under the hypotheses $k \ge 1$, $n \ge 2k+2$, and $n \ge 2k^2$. Using the division-with-remainder identity, $q(k+1)$ is first trapped between $n$ and $n+k$. The inequalities $2 \le q$, $n \le q(2k+1)$, and $(2k+1)n \le (k+1)q(2k+1)$ then follow by scaling these bounds and using $k \ge 1$. Finally, $q(2k+1) \le 2n$ is proved by contradiction: assuming the opposite and scaling by $k+1$ forces $n < 2k^2$, contradicting the assumption $2k^2 \le n$.

  1. The quotient $q = \lfloor(n+k)/(k+1)\rfloor$ satisfies $n \le q(k+1) \le n+k$.

    By division with remainder (`Nat.div_add_mod'`), $(n+k) = q(k+1) + r$ where the remainder $r = (n+k) \bmod (k+1)$ is strictly less than $k+1$ (`Nat.mod_lt`). Since $r \le k$, we have $q(k+1) = (n+k) - r \ge n$. Furthermore, since $r \ge 0$, we have $q(k+1) \le n+k$. Both inequalities follow by linear arithmetic.

    lines 10–15

    uses Nat.mod_lt, Nat.div_add_mod'

      let q := (n+k)/(k+1)
      have hmod := Nat.mod_lt (n+k) (by omega : 0 < k+1)
      have hdiv := Nat.div_add_mod' (n+k) (k+1)
      change q*(k+1)+(n+k)%(k+1) = n+k at hdiv
      have hqn : n ≤ q*(k+1) := by omega
      have hqupper : q*(k+1) ≤ n+k := by omega
  2. $2 \le q$.

    Suppose, for contradiction, that $q < 2$, so $q \le 1$. Multiplying by $k+1$ via `Nat.mul_le_mul_right` gives $q(k+1) \le k+1$. Combined with $n \le q(k+1)$, this implies $n \le k+1$. But this contradicts the hypothesis $2k+2 \le n$ because $k \ge 1$.

    lines 16–19

    uses Nat.mul_le_mul_right

      have hq : 2 ≤ q := by
        by_contra hn
        have hmul := Nat.mul_le_mul_right (k+1) (show q ≤ 1 by omega)
        nlinarith
  3. $n \le q(2k+1)$. automation

    Since $k \ge 1$, we have $k+1 \le 2k+1$. Nonlinear arithmetic derives $n \le q(2k+1)$ directly from $n \le q(k+1)$ and $k+1 \le 2k+1$.

    line 20

      have hNn : n ≤ q*(2*k+1) := by nlinarith
  4. $q(2k+1) \le 2n$.

    Suppose, for contradiction, that $q(2k+1) > 2n$, meaning $2n+1 \le q(2k+1)$. Multiplying this inequality by $k+1$ via `Nat.mul_le_mul_right` gives $(2n+1)(k+1) \le q(2k+1)(k+1)$. Multiplying the known bound $q(k+1) \le n+k$ by $2k+1$ via `Nat.mul_le_mul_right` gives $q(k+1)(2k+1) \le (n+k)(2k+1)$. Chaining these yields $(2n+1)(k+1) \le (n+k)(2k+1)$, which expands to $2nk + 2n + k + 1 \le 2nk + n + 2k^2 + k$, or $n+1 \le 2k^2$. This contradicts the hypothesis $2k^2 \le n$.

    lines 21–25

    uses Nat.mul_le_mul_right

      have hN2 : q*(2*k+1) ≤ 2*n := by
        by_contra hn
        have hmul := Nat.mul_le_mul_right (k+1) (show 2*n+1 ≤ q*(2*k+1) by omega)
        have hqu := Nat.mul_le_mul_right (2*k+1) hqupper
        nlinarith
  5. $(2k+1)n \le (k+1)q(2k+1)$.

    Multiplying the inequality $n \le q(k+1)$ on the right by $2k+1$ via `Nat.mul_le_mul_right` yields $n(2k+1) \le q(k+1)(2k+1)$. Rearranging the products gives $(2k+1)n \le (k+1)(q(2k+1))$.

    lines 26–28

    uses Nat.mul_le_mul_right

      have hgap : (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) := by
        have hmul := Nat.mul_le_mul_right (2*k+1) hqn
        nlinarith
  6. All four inequalities hold simultaneously.

    The four proven inequalities are assembled into a conjunction.

    line 29

      exact ⟨hq, hNn, hN2, hgap⟩
Nat.mod_lt
For any natural numbers $x$ and $y$ with $0 < y$, the remainder satisfies $x \bmod y < y$.
Nat.div_add_mod'
For any natural numbers $a$ and $b$, $(a / b) \cdot b + a \bmod b = a$.
Nat.mul_le_mul_right
If $n \le m$, then $n \cdot k \le m \cdot k$ for any natural number $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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_inflation_parameters    (n k : ℕ) (hk : 1 ≤ k) (hn₀ : 2*k+2 ≤ n) (hn₂ : 2*k^2 ≤ n) :    let q := (n+k)/(k+1)    2 ≤ q ∧ n ≤ q*(2*k+1) ∧ q*(2*k+1) ≤ 2*n ∧      (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) := by  let q := (n+k)/(k+1)  have hmod := Nat.mod_lt (n+k) (by omega : 0 < k+1)  have hdiv := Nat.div_add_mod' (n+k) (k+1)  change q*(k+1)+(n+k)%(k+1) = n+k at hdiv  have hqn : n ≤ q*(k+1) := by omega  have hqupper : q*(k+1) ≤ n+k := by omega  have hq : 2 ≤ q := by    by_contra hn    have hmul := Nat.mul_le_mul_right (k+1) (show q ≤ 1 by omega)    nlinarith  have hNn : n ≤ q*(2*k+1) := by nlinarith  have hN2 : q*(2*k+1) ≤ 2*n := by    by_contra hn    have hmul := Nat.mul_le_mul_right (k+1) (show 2*n+1 ≤ q*(2*k+1) by omega)    have hqu := Nat.mul_le_mul_right (2*k+1) hqupper    nlinarith  have hgap : (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) := by    have hmul := Nat.mul_le_mul_right (2*k+1) hqn    nlinarith  exact ⟨hq, hNn, hN2, hgap⟩
See it in the graphDiscuss this resultChallenge it