op_193_cubic_threshold_edge_gap
The edge-count gap in the clique-free anchor argument is strictly positive at and beyond the cubic threshold.
Statement
theorem op_193_cubic_threshold_edge_gap (k m : ℝ) (hk : 3 ≤ k)
(hm : k * ((k-1)^2 + 1) ≤ m) :
0 < m^2 - 3*m*(k-1) - (m-2*k+2)*k*(k-1)^2- Source
- Arithmetic component of the clique-free reduction for arXiv:2610.17884 Section 3; experiment 23319.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_193_cubic_cycle_anchor_avoidanceOn any cycle of length at least k times ((k-1)^2+1), every family of m-2k+2 subsets of size at most k admits a stable k-set meeting each…
The proof, explained
The edge-count gap is shown to be strictly positive by reparameterizing $m$ in terms of the slack variable $\delta = m - k((k-1)^2 + 1) \ge 0$. By an algebraic identity verified with `ring`, the expression decomposes into $k(k-2)^2 + \delta(k^2(k-2) + 3) + \delta^2$. Since $k \ge 3$, the leading term $k(k-2)^2$ is strictly positive and the remaining terms are products of non-negative quantities, so the entire sum is strictly positive.
$k > 0$, $k - 2 > 0$, and the slack $\delta = m - k((k-1)^2 + 1)$ is non-negative
From the condition $k \ge 3$, linear arithmetic establishes that both $k$ and $k - 2$ are strictly positive. Moving $k((k-1)^2 + 1)$ to the right-hand side of the threshold hypothesis $k((k-1)^2 + 1) \le m$ via `sub_nonneg.mpr` yields $0 \le m - k((k-1)^2 + 1)$.
uses
sub_nonneg.mprhave hkpos : 0 < k := by linarith have hkm : 0 < k-2 := by linarith have hdelta : 0 ≤ m-k*((k-1)^2+1) := sub_nonneg.mpr hm
The edge-count expression decomposes as $k(k-2)^2 + \delta(k^2(k-2)+3) + \delta^2$, where $\delta = m - k((k-1)^2+1)$
Expanding both sides as polynomials in $m$ and $k$ confirms they are algebraically equivalent. The `ring` tactic verifies this identity.
have hid : m^2 - 3*m*(k-1) - (m-2*k+2)*k*(k-1)^2 = k*(k-2)^2 + (m-k*((k-1)^2+1))*(k^2*(k-2)+3) + (m-k*((k-1)^2+1))^2 := by ring
The edge-count gap $m^2 - 3m(k-1) - (m-2k+2)k(k-1)^2$ is strictly positive
Rewriting the goal with the algebraic identity `hid` replaces the gap by $k(k-2)^2 + \delta(k^2(k-2)+3) + \delta^2$. The `positivity` tactic confirms that this sum is strictly positive: the leading term $k(k-2)^2$ is strictly positive since $k > 0$ and $k - 2 > 0$, while the remaining terms are products and powers of non-negative quantities ($\delta \ge 0$, $k^2 \ge 0$, and $k - 2 > 0$).
rw [hid] positivity
sub_nonneg.mpr- if $a \le b$, then $0 \le b - a$
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.
theorem op_193_cubic_threshold_edge_gap (k m : ℝ) (hk : 3 ≤ k) (hm : k * ((k-1)^2 + 1) ≤ m) : 0 < m^2 - 3*m*(k-1) - (m-2*k+2)*k*(k-1)^2 := by have hkpos : 0 < k := by linarith have hkm : 0 < k-2 := by linarith have hdelta : 0 ≤ m-k*((k-1)^2+1) := sub_nonneg.mpr hm have hid : m^2 - 3*m*(k-1) - (m-2*k+2)*k*(k-1)^2 = k*(k-2)^2 + (m-k*((k-1)^2+1))*(k^2*(k-2)+3) + (m-k*((k-1)^2+1))^2 := by ring rw [hid] positivity