op_258_choose_two_mul_sq_le
For any γ ≥ 1 and m : ℕ, γ² * C(m, 2) ≤ C(γ * m, 2).
Statement
theorem op_258_choose_two_mul_sq_le (γ m : ℕ) (hγ : 1 ≤ γ) :
((γ ^ 2 * m.choose 2 : ℕ) : ℝ) ≤ ((γ * m).choose 2 : ℝ)- Source
- step towards op_258_forces_of_forces_smul_blowup
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_258_forces_of_forces_smul_blowupFor γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.
The proof, explained
To prove $\gamma^2 \binom{m}{2} \le \binom{\gamma m}{2}$ for $\gamma \ge 1$, the proof casts the inequality to the real numbers and expands the binomial coefficients $\binom{k}{2}$ as $k(k-1)/2$. It computes the algebraic difference $\binom{\gamma m}{2} - \gamma^2 \binom{m}{2} = \frac{\gamma m (\gamma - 1)}{2}$. Since $\gamma \ge 1$ and $m \ge 0$, every factor in this difference is non-negative, which implies the desired inequality.
It suffices to prove $\gamma^2 \cdot \frac{m(m - 1)}{2} \le \frac{(\gamma m)(\gamma m - 1)}{2}$ in $\mathbb{R}$.
Distribute the natural-to-real cast into the products and powers with `push_cast`, then rewrite the binomial coefficients $\binom{m}{2}$ and $\binom{\gamma m}{2}$ in terms of their algebraic formulas $m(m-1)/2$ and $(\gamma m)(\gamma m - 1)/2$ using `Nat.cast_choose_two`. A second `push_cast` simplifies the cast of $\gamma m$ into the product of casts.
uses
Nat.cast_choose_twopush_cast rw [Nat.cast_choose_two ℝ m, Nat.cast_choose_two ℝ (γ * m)] push_cast
$0 \le \gamma - 1$ in $\mathbb{R}$.
Cast the hypothesis $1 \le \gamma$ to $\mathbb{R}$ using `Nat.one_le_cast.mpr`, then deduce $0 \le \gamma - 1$ by linear arithmetic (`linarith`).
uses
Nat.one_le_cast.mprhave hγ1 : (0 : ℝ) ≤ (γ : ℝ) - 1 := by have : (1 : ℝ) ≤ (γ : ℝ) := Nat.one_le_cast.mpr hγ linarith
$\frac{(\gamma m)(\gamma m - 1)}{2} - \gamma^2 \frac{m(m - 1)}{2} = \frac{\gamma m (\gamma - 1)}{2}$.
Expanding both sides reveals that the quadratic terms in $m$ cancel, reducing the difference to $\frac{\gamma m (\gamma - 1)}{2}$. The `ring` tactic verifies this polynomial identity.
have hid : (γ : ℝ) * (m : ℝ) * ((γ : ℝ) * (m : ℝ) - 1) / 2 - (γ : ℝ) ^ 2 * ((m : ℝ) * ((m : ℝ) - 1) / 2) = (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by ring
$0 \le \frac{\gamma m (\gamma - 1)}{2}$.
Because $\gamma \ge 0$ and $m \ge 0$ as casts of natural numbers, $\gamma - 1 \ge 0$ by the earlier step, and $2 > 0$, the expression is a product and quotient of non-negative quantities. The `positivity` tactic confirms this.
have hpos : 0 ≤ (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by positivity
$\gamma^2 \binom{m}{2} \le \binom{\gamma m}{2}$ in $\mathbb{R}$.
Combining the algebraic identity for the difference with the fact that this difference is non-negative, linear arithmetic (`linarith`) completes the proof.
linarith
Nat.cast_choose_two- For any natural number $a$ and any division ring of characteristic not 2 (such as $\mathbb{R}$), the cast of $\binom{a}{2}$ equals $a(a - 1) / 2$.
Nat.one_le_cast.mpr- If $1 \le n$ holds for a natural number $n$, then $1 \le n$ holds after casting to an ordered semiring (such as $\mathbb{R}$).
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.
/-- For any γ ≥ 1 and m : ℕ, γ² * C(m, 2) ≤ C(γ * m, 2) as real numbers. -/theorem op_258_choose_two_mul_sq_le (γ m : ℕ) (hγ : 1 ≤ γ) : ((γ ^ 2 * m.choose 2 : ℕ) : ℝ) ≤ ((γ * m).choose 2 : ℝ) := by push_cast rw [Nat.cast_choose_two ℝ m, Nat.cast_choose_two ℝ (γ * m)] push_cast have hγ1 : (0 : ℝ) ≤ (γ : ℝ) - 1 := by have : (1 : ℝ) ≤ (γ : ℝ) := Nat.one_le_cast.mpr hγ linarith have hid : (γ : ℝ) * (m : ℝ) * ((γ : ℝ) * (m : ℝ) - 1) / 2 - (γ : ℝ) ^ 2 * ((m : ℝ) * ((m : ℝ) - 1) / 2) = (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by ring have hpos : 0 ≤ (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by positivity linarith