AFTD Auto-Formalizing Theoretical Domains

op_193_cubic_threshold_edge_gap

theoremverified

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

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.

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

    lines 4–6

    uses sub_nonneg.mpr

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

    lines 7–9

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

    lines 10–11

      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

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