p3_ramsey_arithmetic_bound
For all integers a ≥ b ≥ 1 and any natural number N, b * (N choose 2) ≤ a * ⌊N / 2⌋ holds if and only if N ≤ 2 * ⌊(a + b) / (2 * b)⌋.
Statement
theorem p3_ramsey_arithmetic_bound (a b N : ℕ) (hba : b ≤ a) (hb : 1 ≤ b) :
b * N.choose 2 ≤ a * (N / 2) ↔ N ≤ 2 * ((a + b) / (2 * b))- Source
- arXiv:2611.15376 Lemma 2.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- set_coloring_ramsey_property_p3_one_thresholdFor all integers a ≥ b ≥ 1, every (a, b)-set-coloring of the complete graph on 2 * ⌊(a + b) / (2 * b)⌋ + 1 vertices contains a…
Read back from the Lean
For all natural numbers $a$, $b$, and $N$, if $b \le a$ and $1 \le b$, then $b \cdot \binom{N}{2} \le a \cdot \lfloor N / 2 \rfloor$ holds if and only if $N \le 2 \cdot \lfloor (a + b) / (2b) \rfloor$, where division denotes natural number (truncated/floor) division.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by dividing into cases based on whether N is even (N = 2 * k) or odd (N = 2 * k + 1). In each case, the binomial coefficient (N choose 2) and the floor division ⌊N / 2⌋ are evaluated algebraically, and the trivial boundary case k = 0 is verified directly. For k > 0, canceling the common factor k and adding b shifts the left-hand inequality into a linear bound on 2 * b * k (or 2 * b * (k + 1)), which matches the right-hand inequality unfolded via the universal property of integer division.
The divisor 2 * b is strictly positive, and N is either even (N = 2 * k) or odd (N = 2 * k + 1).
Since b ≥ 1, the divisor 2 * b is strictly positive (by linear arithmetic via `omega`). We then split into cases depending on whether N is even or odd using `Nat.even_or_odd`.
uses
Nat.even_or_oddhave hden : 0 < 2 * b := by omega rcases Nat.even_or_odd N with ⟨k, hk⟩ | ⟨k, hk⟩
When N = 2 * k, the theorem's equivalence reduces to b * (k * (2 * k - 1)) ≤ a * k ↔ 2 * k ≤ 2 * ⌊(a + b) / (2 * b)⌋.
Substituting N = 2 * k, the binomial coefficient (2 * k choose 2) evaluates to k * (2 * k - 1) via `Nat.choose_two_right` and `Nat.mul_div_right`, while ⌊(2 * k) / 2⌋ simplifies to k. Rewriting with these expressions yields the simplified equivalence.
uses
Nat.choose_two_right,Nat.mul_div_right· have hN : N = 2*k := by omega rw [hN] have hchoose : (2*k).choose 2 = k * (2*k - 1) := by rw [Nat.choose_two_right] have h : (2*k) * (2*k - 1) = 2 * (k * (2*k - 1)) := by ring rw [h, Nat.mul_div_right _ (by norm_num : 0 < 2)] have hdiv2 : (2*k) / 2 = k := by omega rw [hchoose, hdiv2]
The equivalence holds in the even case when k = 0.
When k = 0, both sides of the equivalence evaluate to 0 ≤ 0, which is trivially true (`simp`).
by_cases hk0 : k = 0 · subst k simp
For k > 0, the left-hand inequality b * (k * (2 * k - 1)) ≤ a * k is equivalent to b * (2 * k - 1) ≤ a.
Since k > 0, we can rewrite the products as k * (b * (2 * k - 1)) ≤ k * a and cancel the positive factor k using `Nat.mul_le_mul_left_iff`.
uses
Nat.mul_le_mul_left_iff· have hkpos : 0 < k := by omega have hL : b * (k * (2*k - 1)) ≤ a * k ↔ b * (2*k - 1) ≤ a := by have h1 : b * (k * (2*k - 1)) = k * (b*(2*k-1)) := by ring have h2 : a * k = k * a := by ring rw [h1, h2] exact Nat.mul_le_mul_left_iff hkpos
The simplified condition b * (2 * k - 1) ≤ a is equivalent to 2 * b * k ≤ a + b.
Adding b to both sides preserves the inequality (`Nat.add_le_add_right`). Since 1 ≤ 2 * k, we have (2 * k - 1) + 1 = 2 * k by `Nat.sub_add_cancel`, so b * (2 * k - 1) + b = 2 * b * k. Rewriting the goal with this identity and the previous cancellation simplifies the left condition.
uses
Nat.add_le_add_right,Nat.sub_add_cancelhave hA : b * (2*k - 1) ≤ a ↔ 2*b*k ≤ a + b := by constructor · intro h have h' : b*(2*k-1) + b ≤ a + b := Nat.add_le_add_right h b have hEq : b*(2*k-1) + b = 2*b*k := by have hsub : 1 ≤ 2*k := by omega calc b*(2*k-1) + b = b*((2*k-1)+1) := by ring _ = b*(2*k) := by rw [Nat.sub_add_cancel hsub] _ = 2*b*k := by ring omega · intro h have hsub : 1 ≤ 2*k := by omega have hEq : b*(2*k-1) + b = 2*b*k := by calc b*(2*k-1) + b = b*((2*k-1)+1) := by ring _ = b*(2*k) := by rw [Nat.sub_add_cancel hsub] _ = 2*b*k := by ring omega rw [hL, hA]
The right-hand inequality 2 * k ≤ 2 * ⌊(a + b) / (2 * b)⌋ is equivalent to k * (2 * b) ≤ a + b.
Dividing both sides by 2 gives k ≤ ⌊(a + b) / (2 * b)⌋, which by the characterization of integer division (`Nat.le_div_iff_mul_le`) is equivalent to k * (2 * b) ≤ a + b.
uses
Nat.le_div_iff_mul_lehave hR : (2*k ≤ 2*((a+b)/(2*b))) ↔ k*(2*b) ≤ a+b := by rw [show (2*k ≤ 2*((a+b)/(2*b))) ↔ k ≤ (a+b)/(2*b) by omega] rw [Nat.le_div_iff_mul_le hden] rw [hR]
The equivalence holds for even N when k > 0.
By commutativity of multiplication, 2 * b * k = k * (2 * b). The reduced left and right inequalities are therefore identical, closing the even case.
constructor <;> intro h · have : k*(2*b) = 2*b*k := by ring omega · have : k*(2*b) = 2*b*k := by ring omega
When N = 2 * k + 1, the theorem's equivalence reduces to b * (k * (2 * k + 1)) ≤ a * k ↔ 2 * k + 1 ≤ 2 * ⌊(a + b) / (2 * b)⌋.
Substituting N = 2 * k + 1, (2 * k + 1 choose 2) evaluates to k * (2 * k + 1) using `Nat.choose_two_right` and `Nat.mul_div_right`, and ⌊(2 * k + 1) / 2⌋ simplifies to k. Rewriting with both facts produces the reduced equivalence.
uses
Nat.choose_two_right,Nat.mul_div_right· have hN : N = 2*k+1 := by omega rw [hN] have hchoose : (2*k+1).choose 2 = k * (2*k+1) := by rw [Nat.choose_two_right] have hsub : 2*k+1 - 1 = 2*k := by omega rw [hsub] have h : (2*k+1) * (2*k) = 2 * (k * (2*k+1)) := by ring rw [h, Nat.mul_div_right _ (by norm_num : 0 < 2)] have hdiv2 : (2*k+1) / 2 = k := by omega rw [hchoose, hdiv2]
The equivalence holds in the odd case when k = 0 (that is, N = 1).
When k = 0, the left-hand inequality is 0 ≤ 0, which is always true. For the right-hand inequality 1 ≤ 2 * ⌊(a + b) / (2 * b)⌋, since b ≤ a and 1 ≤ b, we have 2 * b ≤ a + b, meaning 1 ≤ ⌊(a + b) / (2 * b)⌋ by `Nat.le_div_iff_mul_le`. Hence 2 * ⌊(a + b) / (2 * b)⌋ ≥ 2 ≥ 1, so the right-hand inequality is also true.
uses
Nat.le_div_iff_mul_leby_cases hk0 : k = 0 · subst k have hq : 1 ≤ (a+b)/(2*b) := by rw [Nat.le_div_iff_mul_le hden] omega norm_num omega
For k > 0, the left-hand inequality b * (k * (2 * k + 1)) ≤ a * k is equivalent to b * (2 * k + 1) ≤ a.
Since k > 0, we rewrite the inequality as k * (b * (2 * k + 1)) ≤ k * a and cancel k using `Nat.mul_le_mul_left_iff`.
uses
Nat.mul_le_mul_left_iff· have hkpos : 0 < k := by omega have hL : b * (k * (2*k+1)) ≤ a * k ↔ b * (2*k+1) ≤ a := by have h1 : b * (k * (2*k+1)) = k * (b*(2*k+1)) := by ring have h2 : a * k = k * a := by ring rw [h1, h2] exact Nat.mul_le_mul_left_iff hkpos
The simplified condition b * (2 * k + 1) ≤ a is equivalent to 2 * b * (k + 1) ≤ a + b.
Adding b to both sides preserves the inequality (`Nat.add_le_add_right`). Since b * (2 * k + 1) + b = 2 * b * (k + 1), this immediately yields the equivalence with 2 * b * (k + 1) ≤ a + b.
uses
Nat.add_le_add_righthave hA : b * (2*k+1) ≤ a ↔ 2*b*(k+1) ≤ a+b := by constructor · intro h have h' : b*(2*k+1) + b ≤ a + b := Nat.add_le_add_right h b have hEq : b*(2*k+1) + b = 2*b*(k+1) := by ring omega · intro h have hEq : b*(2*k+1) + b = 2*b*(k+1) := by ring omega rw [hL, hA]
The right-hand inequality 2 * k + 1 ≤ 2 * ⌊(a + b) / (2 * b)⌋ is equivalent to (k + 1) * (2 * b) ≤ a + b.
In natural numbers, 2 * k + 1 ≤ 2 * M is equivalent to k + 1 ≤ M. Applying this with M = ⌊(a + b) / (2 * b)⌋ and rewriting using `Nat.le_div_iff_mul_le` yields (k + 1) * (2 * b) ≤ a + b.
uses
Nat.le_div_iff_mul_lehave hR : (2*k+1 ≤ 2*((a+b)/(2*b))) ↔ (k+1)*(2*b) ≤ a+b := by rw [show (2*k+1 ≤ 2*((a+b)/(2*b))) ↔ k+1 ≤ (a+b)/(2*b) by omega] rw [Nat.le_div_iff_mul_le hden] rw [hR]
The equivalence holds for odd N when k > 0, concluding the theorem.
Because 2 * b * (k + 1) = (k + 1) * (2 * b) by ring arithmetic, the two simplified inequalities are identical, completing the proof.
constructor <;> intro h · have : 2*b*(k+1) = (k+1)*(2*b) := by ring omega · have : 2*b*(k+1) = (k+1)*(2*b) := by ring omega
Nat.even_or_odd- Every natural number is either even or odd.
Nat.choose_two_right- The binomial coefficient (n choose 2) equals n * (n - 1) / 2.
Nat.mul_div_right- For m > 0, dividing m * n by m yields n.
Nat.mul_le_mul_left_iff- For k > 0, multiplication by k preserves and reflects non-strict inequality: k * n ≤ k * m if and only if n ≤ m.
Nat.add_le_add_right- Adding a constant to both sides of an inequality preserves it: if n ≤ m, then n + k ≤ m + k.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
Nat.le_div_iff_mul_le- For k > 0, x ≤ y / k if and only if x * k ≤ y.
- The equivalences 2 * k ≤ 2 * M ↔ k ≤ M and 2 * k + 1 ≤ 2 * M ↔ k + 1 ≤ M are proved inline by `omega` using linear integer arithmetic rather than citing dedicated library lemmas.
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.
/-- Equivalence between the matching edge count bound b * choose(N, 2) ≤ a * ⌊N/2⌋ and N ≤ 2 * ⌊(a+b)/(2b)⌋. -/theorem p3_ramsey_arithmetic_bound (a b N : ℕ) (hba : b ≤ a) (hb : 1 ≤ b) : b * N.choose 2 ≤ a * (N / 2) ↔ N ≤ 2 * ((a + b) / (2 * b)) := by have hden : 0 < 2 * b := by omega rcases Nat.even_or_odd N with ⟨k, hk⟩ | ⟨k, hk⟩ · have hN : N = 2*k := by omega rw [hN] have hchoose : (2*k).choose 2 = k * (2*k - 1) := by rw [Nat.choose_two_right] have h : (2*k) * (2*k - 1) = 2 * (k * (2*k - 1)) := by ring rw [h, Nat.mul_div_right _ (by norm_num : 0 < 2)] have hdiv2 : (2*k) / 2 = k := by omega rw [hchoose, hdiv2] by_cases hk0 : k = 0 · subst k simp · have hkpos : 0 < k := by omega have hL : b * (k * (2*k - 1)) ≤ a * k ↔ b * (2*k - 1) ≤ a := by have h1 : b * (k * (2*k - 1)) = k * (b*(2*k-1)) := by ring have h2 : a * k = k * a := by ring rw [h1, h2] exact Nat.mul_le_mul_left_iff hkpos have hA : b * (2*k - 1) ≤ a ↔ 2*b*k ≤ a + b := by constructor · intro h have h' : b*(2*k-1) + b ≤ a + b := Nat.add_le_add_right h b have hEq : b*(2*k-1) + b = 2*b*k := by have hsub : 1 ≤ 2*k := by omega calc b*(2*k-1) + b = b*((2*k-1)+1) := by ring _ = b*(2*k) := by rw [Nat.sub_add_cancel hsub] _ = 2*b*k := by ring omega · intro h have hsub : 1 ≤ 2*k := by omega have hEq : b*(2*k-1) + b = 2*b*k := by calc b*(2*k-1) + b = b*((2*k-1)+1) := by ring _ = b*(2*k) := by rw [Nat.sub_add_cancel hsub] _ = 2*b*k := by ring omega rw [hL, hA] have hR : (2*k ≤ 2*((a+b)/(2*b))) ↔ k*(2*b) ≤ a+b := by rw [show (2*k ≤ 2*((a+b)/(2*b))) ↔ k ≤ (a+b)/(2*b) by omega] rw [Nat.le_div_iff_mul_le hden] rw [hR] constructor <;> intro h · have : k*(2*b) = 2*b*k := by ring omega · have : k*(2*b) = 2*b*k := by ring omega · have hN : N = 2*k+1 := by omega rw [hN] have hchoose : (2*k+1).choose 2 = k * (2*k+1) := by rw [Nat.choose_two_right] have hsub : 2*k+1 - 1 = 2*k := by omega rw [hsub] have h : (2*k+1) * (2*k) = 2 * (k * (2*k+1)) := by ring rw [h, Nat.mul_div_right _ (by norm_num : 0 < 2)] have hdiv2 : (2*k+1) / 2 = k := by omega rw [hchoose, hdiv2] by_cases hk0 : k = 0 · subst k have hq : 1 ≤ (a+b)/(2*b) := by rw [Nat.le_div_iff_mul_le hden] omega norm_num omega · have hkpos : 0 < k := by omega have hL : b * (k * (2*k+1)) ≤ a * k ↔ b * (2*k+1) ≤ a := by have h1 : b * (k * (2*k+1)) = k * (b*(2*k+1)) := by ring have h2 : a * k = k * a := by ring rw [h1, h2] exact Nat.mul_le_mul_left_iff hkpos have hA : b * (2*k+1) ≤ a ↔ 2*b*(k+1) ≤ a+b := by constructor · intro h have h' : b*(2*k+1) + b ≤ a + b := Nat.add_le_add_right h b have hEq : b*(2*k+1) + b = 2*b*(k+1) := by ring omega · intro h have hEq : b*(2*k+1) + b = 2*b*(k+1) := by ring omega rw [hL, hA] have hR : (2*k+1 ≤ 2*((a+b)/(2*b))) ↔ (k+1)*(2*b) ≤ a+b := by rw [show (2*k+1 ≤ 2*((a+b)/(2*b))) ↔ k+1 ≤ (a+b)/(2*b) by omega] rw [Nat.le_div_iff_mul_le hden] rw [hR] constructor <;> intro h · have : 2*b*(k+1) = (k+1)*(2*b) := by ring omega · have : 2*b*(k+1) = (k+1)*(2*b) := by ring omega