Proof of Lemma 3.2 (Section 4.3) —
ProvedAbelianCayleyHDX.binomial_boundsbinomial-coefficientscombinatoricsp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every integer ,
and with and ,
These are the last two inequalities of the chain in the proof of Lemma 3.2 (the first one is Proposition 4.6).
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace AbelianCayleyHDX
/-- **Proof of Lemma 3.2 (Section 4.3): the binomial bounds** (Mao, *Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree*, arXiv:2609.08937 (held version, sha256 6f5b0daa…75ba), proof of Lemma 3.2,
Section 4.3, p.18). For every `k ≥ 0`, `\binom{3k}{k} ≥ (27/4)^k / (3k + 1)`; and with
`t = 2g + 1` and `k = ⌊g/4⌋`, `(27/4)^k / (3k + 1) ≥ 2^{t/3}` for all sufficiently large `g`. -/
theorem binomial_bounds :
(∀ k : ℕ, (27 / 4 : ℝ) ^ k / (3 * (k : ℝ) + 1) ≤ ((Nat.choose (3 * k) k : ℕ) : ℝ)) ∧
∃ g₀ : ℕ, ∀ g : ℕ, g₀ ≤ g →
(2 : ℝ) ^ (((2 * g + 1 : ℕ) : ℝ) / 3) ≤ (27 / 4 : ℝ) ^ (g / 4) / (3 * ((g / 4 : ℕ) : ℝ) + 1) := by sorry
end AbelianCayleyHDX
Source
Songtao Mao, Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree, arXiv:2609.08937 (held version, sha256 6f5b0daa…75ba), proof of Lemma 3.2, Section 4.3, p.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.