cycle_power_inflation_parameters
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
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 2
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor every natural k at least one and natural n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th…
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover…
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$.
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.
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 \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$.
uses
Nat.mul_le_mul_righthave hq : 2 ≤ q := by by_contra hn have hmul := Nat.mul_le_mul_right (k+1) (show q ≤ 1 by omega) nlinarith
$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$.
have hNn : n ≤ q*(2*k+1) := by nlinarith
$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$.
uses
Nat.mul_le_mul_righthave 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
$(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))$.
uses
Nat.mul_le_mul_righthave hgap : (2*k+1)*n ≤ (k+1)*(q*(2*k+1)) := by have hmul := Nat.mul_le_mul_right (2*k+1) hqn nlinarith
All four inequalities hold simultaneously.
The four proven inequalities are assembled into a conjunction.
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
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 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⟩