AFTD Auto-Formalizing Theoretical Domains

one_layered_binomial_bound_le_power

theoremverifiedformalization

For integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) is at most (m - r + 1)^(1 + log_2 r) over the real numbers.

Statement

theorem one_layered_binomial_bound_le_power (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :
    ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤
      (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2)
Formalizes
arXiv:2611.08071 Theorem 2.1
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • one_layered_family_upper_boundsFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) of a 1-layered family of r-subsets on at most m vertices satisfies…

Read back from the Lean

For all natural numbers $m$ and $r$, if $1 \le r$ and $r \le m$, then $$ (m - r + 1) \cdot \binom{\lfloor \log_2(m - r + 1) \rfloor + r - 1}{r - 1} \le (m - r + 1)^{1 + \frac{\ln r}{\ln 2}} $$ where $m - r + 1$ and the arguments to the binomial coefficient are evaluated using natural number arithmetic before being coerced to $\mathbb{R}$, $\lfloor \log_2(\cdot) \rfloor$ denotes Nat.log 2, and the right-hand side is evaluated via real exponentiation.

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

To prove that (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) ≤ (m - r + 1)^(1 + log_2 r), we set k = m - r + 1 and L = ⌊log_2 k⌋. By symmetry of binomial coefficients, choose(L + r - 1, r - 1) = choose(L + r - 1, L), which is bounded above by r^L via an induction on L. Converting bases gives r^L = (2^L)^(log_2 r) ≤ k^(log_2 r) by the definition of integer logarithm, and multiplying through by k yields the desired exponent 1 + log_2 r.

  1. For the base case L = 0, choose(0 + r - 1, 0) ≤ r^0 holds for all r ≥ 1.

    We proceed by induction on L. When L = 0, the binomial coefficient choose(r - 1, 0) equals 1, and r^0 = 1, so the inequality simplifies to 1 ≤ 1.

    lines 1–4

    lemma one_layered_binomial_bound_le_power_choose_add_le_pow (L r : ℕ) (hr : 1 ≤ r) :
        (L + r - 1).choose L ≤ r ^ L := by
      induction' L with L ih
      · simp
  2. For the inductive step, (L + r) * choose(L + r - 1, L) = choose(L + r, L + 1) * (L + 1).

    We apply the standard binomial absorption identity (n + 1) * choose(n, k) = choose(n + 1, k + 1) * (k + 1) with n = L + r - 1 and k = L. Since r ≥ 1, (L + r - 1) + 1 = L + r, giving the identity.

    lines 5–8

    uses Nat.add_one_mul_choose_eq, Nat.sub_add_cancel

      · have h1 : (L + r) * (L + r - 1).choose L = (L + r).choose (L + 1) * (L + 1) := by
          have h2 := Nat.add_one_mul_choose_eq (L + r - 1) L
          have h3 : L + r - 1 + 1 = L + r := Nat.sub_add_cancel (by omega)
          rwa [h3] at h2
  3. choose(L + r, L + 1) * (L + 1) ≤ r^(L + 1) * (L + 1).

    Using the identity from the previous step and the induction hypothesis choose(L + r - 1, L) ≤ r^L, we have choose(L + r, L + 1) * (L + 1) = (L + r) * choose(L + r - 1, L) ≤ (L + r) * r^L. Since r ≥ 1, linear arithmetic gives L + r ≤ r * (L + 1), so (L + r) * r^L ≤ r * (L + 1) * r^L = r^(L + 1) * (L + 1).

    lines 9–17

    uses Nat.mul_le_mul_left, Nat.mul_le_mul_right

        have h4 : (L + r).choose (L + 1) * (L + 1) ≤ r ^ (L + 1) * (L + 1) := by
          calc
            (L + r).choose (L + 1) * (L + 1) = (L + r) * (L + r - 1).choose L := h1.symm
            _ ≤ (L + r) * r ^ L := Nat.mul_le_mul_left _ ih
            _ ≤ (r * (L + 1)) * r ^ L := by
              apply Nat.mul_le_mul_right
              nlinarith
            _ = r ^ (L + 1) * (L + 1) := by
              ring
  4. choose(L + 1 + r - 1, L + 1) ≤ r^(L + 1), completing the induction for one_layered_binomial_bound_le_power_choose_add_le_pow.

    Rewriting L + 1 + r - 1 as L + r, we cancel the strictly positive factor L + 1 from both sides of the inequality choose(L + r, L + 1) * (L + 1) ≤ r^(L + 1) * (L + 1) to conclude choose(L + r, L + 1) ≤ r^(L + 1).

    lines 18–21

    uses Nat.le_of_mul_le_mul_right

        have hpos : 0 < L + 1 := by omega
        have h5 : (L + 1 + r - 1) = L + r := by omega
        rw [h5]
        exact Nat.le_of_mul_le_mul_right h4 hpos
  5. For r ≥ 1, choose(L + r - 1, r - 1) = choose(L + r - 1, L).

    Since r ≥ 1, we have r - 1 ≤ L + r - 1 and (L + r - 1) - (r - 1) = L. The claim then follows by the symmetry of binomial coefficients, choose(n, k) = choose(n, n - k).

    lines 23–30

    uses Nat.choose_symm

    lemma one_layered_binomial_bound_le_power_choose_symm (L r : ℕ) (hr : 1 ≤ r) :
        (L + r - 1).choose (r - 1) = (L + r - 1).choose L := by
      have hle : r - 1 ≤ L + r - 1 := by omega
      have heq : L + r - 1 - (r - 1) = L := by omega
      have := Nat.choose_symm hle
      rw [heq] at this
      exact this.symm
    
  6. For r ≥ 1, 2^(ln r / ln 2) = r over the real numbers.

    By definition of real exponentiation for positive bases, 2^(ln r / ln 2) = exp(ln 2 * (ln r / ln 2)). Since 2 > 1, ln 2 ≠ 0, so ln 2 cancels with the denominator, leaving exp(ln r) = r because r > 0.

    lines 31–41

    uses Real.rpow_def_of_pos, Real.log_ne_zero_of_pos_of_ne_one, mul_div_cancel₀, Real.exp_log

    lemma one_layered_binomial_bound_le_power_two_rpow_log_div_log (r : ℕ) (hr : 1 ≤ r) :
        (2 : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) = (r : ℝ) := by
      have h2pos : (0 : ℝ) < 2 := by norm_num
      have hrpos : (0 : ℝ) < (r : ℝ) := by positivity
      rw [Real.rpow_def_of_pos h2pos]
      have hlog2 : Real.log 2 ≠ 0 := by
        apply Real.log_ne_zero_of_pos_of_ne_one <;> norm_num
      have : Real.log 2 * (Real.log (r : ℝ) / Real.log 2) = Real.log (r : ℝ) := by
        exact mul_div_cancel₀ (Real.log (r : ℝ)) hlog2
      rw [this, Real.exp_log hrpos]
    
  7. Setting k = m - r + 1 and L = floor(log_2 k), we have k ≥ 1 (so k > 0 in ℝ) and ln r / ln 2 ≥ 0.

    From m ≥ r, the real difference m - r + 1 equals the natural number k = m - r + 1. Since k ≥ 1, k is strictly positive. Moreover, r ≥ 1 implies ln r ≥ 0, and 2 > 1 implies ln 2 > 0, so the quotient ln r / ln 2 is non-negative.

    lines 43–58

    uses Nat.cast_sub, Real.log_nonneg, Real.log_pos, div_nonneg, le_of_lt

    theorem one_layered_binomial_bound_le_power (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :
        ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤
          (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by
      have hk_cast : (m - r + 1 : ℝ) = ((m - r + 1 : ℕ) : ℝ) := by
        push_cast [Nat.cast_sub hm]; rfl
      rw [hk_cast]
      set k := m - r + 1
      set L := Nat.log 2 k
      have hk : 1 ≤ k := by omega
      have hk_pos : (0 : ℝ) < (k : ℝ) := by positivity
      have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by positivity
      have hc_nonneg : 0 ≤ Real.log (r : ℝ) / Real.log 2 := by
        have hr' : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr
        have h1 : 0 ≤ Real.log (r : ℝ) := Real.log_nonneg hr'
        have h2 : 0 < Real.log 2 := Real.log_pos (by norm_num)
        exact div_nonneg h1 (le_of_lt h2)
  8. Over the real numbers, choose(L + r - 1, r - 1) ≤ r^L.

    By the symmetry lemma, choose(L + r - 1, r - 1) = choose(L + r - 1, L). Applying the induction bound choose(L + r - 1, L) ≤ r^L and casting to the real numbers yields the result.

    lines 59–62

    uses one_layered_binomial_bound_le_power_choose_symm, one_layered_binomial_bound_le_power_choose_add_le_pow

      have hchoose : ((L + r - 1).choose (r - 1) : ℝ) ≤ (r : ℝ) ^ L := by
        rw [one_layered_binomial_bound_le_power_choose_symm L r hr]
        have := one_layered_binomial_bound_le_power_choose_add_le_pow L r hr
        exact_mod_cast this
  9. r^L ≤ k^(ln r / ln 2).

    Using the base-2 identity, r^L = (2^(ln r / ln 2))^L = (2^L)^(ln r / ln 2). By definition of the integer logarithm L = floor(log_2 k), we have 2^L ≤ k. Since 2^L ≥ 0 and the exponent ln r / ln 2 ≥ 0, monotonicity of real exponentiation implies (2^L)^(ln r / ln 2) ≤ k^(ln r / ln 2).

    lines 63–75

    uses Real.rpow_natCast_mul, mul_comm, Real.rpow_mul_natCast, one_layered_binomial_bound_le_power_two_rpow_log_div_log, Nat.pow_log_le_self, Real.rpow_le_rpow

      have hpow_le : (r : ℝ) ^ L ≤ (k : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) := by
        have h2 : (0 : ℝ) ≤ 2 := by norm_num
        have h_r_L : (r : ℝ) ^ L = ((2 ^ L : ℕ) : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) := by
          push_cast
          rw [← Real.rpow_natCast_mul h2, mul_comm, Real.rpow_mul_natCast h2]
          rw [one_layered_binomial_bound_le_power_two_rpow_log_div_log r hr]
        rw [h_r_L]
        have h2L_le_k : 2 ^ L ≤ k := by
          apply Nat.pow_log_le_self
          omega
        have h2L_le_k_real : ((2 ^ L : ℕ) : ℝ) ≤ (k : ℝ) := by exact_mod_cast h2L_le_k
        have h2L_nonneg : (0 : ℝ) ≤ ((2 ^ L : ℕ) : ℝ) := by positivity
        exact Real.rpow_le_rpow h2L_nonneg h2L_le_k_real hc_nonneg
  10. k * choose(L + r - 1, r - 1) ≤ k^(1 + ln r / ln 2).

    Combining the bounds, k * choose(L + r - 1, r - 1) ≤ k * r^L ≤ k * k^(ln r / ln 2). Since k > 0, multiplying powers of k gives k * k^(ln r / ln 2) = k^(1 + ln r / ln 2), which proves the theorem.

    lines 76–81

    uses Real.rpow_add, Real.rpow_one

      calc
        (k : ℝ) * ((L + r - 1).choose (r - 1) : ℝ)
          ≤ (k : ℝ) * ((r : ℝ) ^ L) := by gcongr
        _ ≤ (k : ℝ) * ((k : ℝ) ^ (Real.log (r : ℝ) / Real.log 2)) := by gcongr
        _ = (k : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by
          rw [Real.rpow_add hk_pos, Real.rpow_one]
Nat.add_one_mul_choose_eq
For any natural numbers n and k, (n + 1) * choose(n, k) = choose(n + 1, k + 1) * (k + 1).
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n for natural numbers.
Nat.mul_le_mul_left
Multiplying both sides of an inequality by a natural number on the left preserves the inequality.
Nat.mul_le_mul_right
Multiplying both sides of an inequality by a natural number on the right preserves the inequality.
Nat.le_of_mul_le_mul_right
If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
Nat.choose_symm
Binomial coefficients are symmetric: choose(n, n - k) = choose(n, k) when k ≤ n.
Real.rpow_def_of_pos
For a positive real number x, x^y = exp(y * ln x).
Real.log_ne_zero_of_pos_of_ne_one
The natural logarithm of a positive real number not equal to 1 is nonzero.
mul_div_cancel₀
Multiplying b by a / b yields a, provided b ≠ 0.
Real.exp_log
For a positive real number x, exp(ln x) = x.
Nat.cast_sub
For natural numbers m ≤ n, the cast of their difference into a ring equals the difference of their casts.
Real.log_nonneg
If x ≥ 1 for a real number x, then ln x ≥ 0.
Real.log_pos
If x > 1 for a real number x, then ln x > 0.
div_nonneg
The quotient of two non-negative numbers is non-negative.
le_of_lt
A strict inequality implies a non-strict inequality.
one_layered_binomial_bound_le_power_choose_symm
For r ≥ 1, choose(L + r - 1, r - 1) = choose(L + r - 1, L).
one_layered_binomial_bound_le_power_choose_add_le_pow
For r ≥ 1, choose(L + r - 1, L) ≤ r^L.
Real.rpow_natCast_mul
For x ≥ 0, x^(n * z) = (x^n)^z for natural n and real z.
mul_comm
Multiplication is commutative.
Real.rpow_mul_natCast
For x ≥ 0, x^(y * n) = (x^y)^n for real y and natural n.
one_layered_binomial_bound_le_power_two_rpow_log_div_log
For r ≥ 1, 2^(log_2 r) = r over the real numbers.
Nat.pow_log_le_self
For any non-zero natural number x, the base-b power b^(floor(log_b x)) is at most x.
Real.rpow_le_rpow
For non-negative reals x ≤ y and exponent z ≥ 0, x^z ≤ y^z.
Real.rpow_add
For a positive real number x, x^(y + z) = x^y * x^z.
Real.rpow_one
Any real number raised to the power 1 equals itself.

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

lemma one_layered_binomial_bound_le_power_choose_add_le_pow (L r : ℕ) (hr : 1 ≤ r) :    (L + r - 1).choose L ≤ r ^ L := by  induction' L with L ih  · simp  · have h1 : (L + r) * (L + r - 1).choose L = (L + r).choose (L + 1) * (L + 1) := by      have h2 := Nat.add_one_mul_choose_eq (L + r - 1) L      have h3 : L + r - 1 + 1 = L + r := Nat.sub_add_cancel (by omega)      rwa [h3] at h2    have h4 : (L + r).choose (L + 1) * (L + 1) ≤ r ^ (L + 1) * (L + 1) := by      calc        (L + r).choose (L + 1) * (L + 1) = (L + r) * (L + r - 1).choose L := h1.symm        _ ≤ (L + r) * r ^ L := Nat.mul_le_mul_left _ ih        _ ≤ (r * (L + 1)) * r ^ L := by          apply Nat.mul_le_mul_right          nlinarith        _ = r ^ (L + 1) * (L + 1) := by          ring    have hpos : 0 < L + 1 := by omega    have h5 : (L + 1 + r - 1) = L + r := by omega    rw [h5]    exact Nat.le_of_mul_le_mul_right h4 hposlemma one_layered_binomial_bound_le_power_choose_symm (L r : ℕ) (hr : 1 ≤ r) :    (L + r - 1).choose (r - 1) = (L + r - 1).choose L := by  have hle : r - 1 ≤ L + r - 1 := by omega  have heq : L + r - 1 - (r - 1) = L := by omega  have := Nat.choose_symm hle  rw [heq] at this  exact this.symmlemma one_layered_binomial_bound_le_power_two_rpow_log_div_log (r : ℕ) (hr : 1 ≤ r) :    (2 : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) = (r : ℝ) := by  have h2pos : (0 : ℝ) < 2 := by norm_num  have hrpos : (0 : ℝ) < (r : ℝ) := by positivity  rw [Real.rpow_def_of_pos h2pos]  have hlog2 : Real.log 2 ≠ 0 := by    apply Real.log_ne_zero_of_pos_of_ne_one <;> norm_num  have : Real.log 2 * (Real.log (r : ℝ) / Real.log 2) = Real.log (r : ℝ) := by    exact mul_div_cancel₀ (Real.log (r : ℝ)) hlog2  rw [this, Real.exp_log hrpos]/-- The bound κ_r(m) ≤ (m - r + 1)^(1 + log_2 r). -/theorem one_layered_binomial_bound_le_power (m r : ℕ) (hr : 1 ≤ r) (hm : r ≤ m) :    ((m - r + 1 : ℝ) * ((Nat.log 2 (m - r + 1) + r - 1).choose (r - 1) : ℝ)) ≤      (m - r + 1 : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by  have hk_cast : (m - r + 1 : ℝ) = ((m - r + 1 : ℕ) : ℝ) := by    push_cast [Nat.cast_sub hm]; rfl  rw [hk_cast]  set k := m - r + 1  set L := Nat.log 2 k  have hk : 1 ≤ k := by omega  have hk_pos : (0 : ℝ) < (k : ℝ) := by positivity  have hk_nonneg : (0 : ℝ) ≤ (k : ℝ) := by positivity  have hc_nonneg : 0 ≤ Real.log (r : ℝ) / Real.log 2 := by    have hr' : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr    have h1 : 0 ≤ Real.log (r : ℝ) := Real.log_nonneg hr'    have h2 : 0 < Real.log 2 := Real.log_pos (by norm_num)    exact div_nonneg h1 (le_of_lt h2)  have hchoose : ((L + r - 1).choose (r - 1) : ℝ) ≤ (r : ℝ) ^ L := by    rw [one_layered_binomial_bound_le_power_choose_symm L r hr]    have := one_layered_binomial_bound_le_power_choose_add_le_pow L r hr    exact_mod_cast this  have hpow_le : (r : ℝ) ^ L ≤ (k : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) := by    have h2 : (0 : ℝ) ≤ 2 := by norm_num    have h_r_L : (r : ℝ) ^ L = ((2 ^ L : ℕ) : ℝ) ^ (Real.log (r : ℝ) / Real.log 2) := by      push_cast      rw [← Real.rpow_natCast_mul h2, mul_comm, Real.rpow_mul_natCast h2]      rw [one_layered_binomial_bound_le_power_two_rpow_log_div_log r hr]    rw [h_r_L]    have h2L_le_k : 2 ^ L ≤ k := by      apply Nat.pow_log_le_self      omega    have h2L_le_k_real : ((2 ^ L : ℕ) : ℝ) ≤ (k : ℝ) := by exact_mod_cast h2L_le_k    have h2L_nonneg : (0 : ℝ) ≤ ((2 ^ L : ℕ) : ℝ) := by positivity    exact Real.rpow_le_rpow h2L_nonneg h2L_le_k_real hc_nonneg  calc    (k : ℝ) * ((L + r - 1).choose (r - 1) : ℝ)      ≤ (k : ℝ) * ((r : ℝ) ^ L) := by gcongr    _ ≤ (k : ℝ) * ((k : ℝ) ^ (Real.log (r : ℝ) / Real.log 2)) := by gcongr    _ = (k : ℝ) ^ (1 + Real.log (r : ℝ) / Real.log 2) := by      rw [Real.rpow_add hk_pos, Real.rpow_one]
See it in the graphDiscuss this resultChallenge it