AFTD Auto-Formalizing Theoretical Domains

p3_ramsey_arithmetic_bound

theoremverified

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

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.

  1. 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`.

    lines 4–5

    uses Nat.even_or_odd

      have hden : 0 < 2 * b := by omega
      rcases Nat.even_or_odd N with ⟨k, hk⟩ | ⟨k, hk⟩
  2. 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.

    lines 6–13

    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]
  3. 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`).

    lines 14–16

        by_cases hk0 : k = 0
        · subst k
          simp
  4. 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`.

    lines 17–22

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

    lines 23–42

    uses Nat.add_le_add_right, Nat.sub_add_cancel

          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]
  6. 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.

    lines 43–46

    uses Nat.le_div_iff_mul_le

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

    lines 47–51

          constructor <;> intro h
          · have : k*(2*b) = 2*b*k := by ring
            omega
          · have : k*(2*b) = 2*b*k := by ring
            omega
  8. 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.

    lines 52–61

    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]
  9. 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.

    lines 62–68

    uses Nat.le_div_iff_mul_le

        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
  10. 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`.

    lines 69–74

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

    lines 75–84

    uses Nat.add_le_add_right

          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]
  12. 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.

    lines 85–88

    uses Nat.le_div_iff_mul_le

          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]
  13. 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.

    lines 89–93

          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.

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

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