one_layered_binomial_bound_le_power
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- 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.
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.
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
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.
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
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).
uses
Nat.mul_le_mul_left,Nat.mul_le_mul_righthave 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
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).
uses
Nat.le_of_mul_le_mul_righthave 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
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).
uses
Nat.choose_symmlemma 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
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.
uses
Real.rpow_def_of_pos,Real.log_ne_zero_of_pos_of_ne_one,mul_div_cancel₀,Real.exp_loglemma 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]
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.
uses
Nat.cast_sub,Real.log_nonneg,Real.log_pos,div_nonneg,le_of_lttheorem 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)
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.
uses
one_layered_binomial_bound_le_power_choose_symm,one_layered_binomial_bound_le_power_choose_add_le_powhave 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
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).
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_rpowhave 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
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.
uses
Real.rpow_add,Real.rpow_onecalc (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.
- Elementary arithmetic inequalities and side conditions (such as 1 ≤ L + r, L + r ≤ r * (L + 1), and positivity of k and 2^L) are handled automatically by Lean's omega, nlinarith, and positivity tactics.
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.
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]