Binomial partial sums bounded via the binary entropy function
Provedchoose_sum_le_exp_mul_binEntropyLet be natural numbers with and , and let . Then the volume of the Hamming ball of radius in is bounded via the binary entropy function (Real.binEntropy, measured in nats) by
This is the classical volume bound on Hamming balls (equivalently, on partial sums of binomial coefficients) used throughout coding theory and combinatorics: it converts a bound on the size of a subset of the hypercube contained in (or compared against) a Hamming ball into an entropy bound, and conversely. The proof is elementary: for and , the term of the binomial expansion of is at least , so , and rearranging with gives the stated bound after converting into exponential-of-entropy form.
Formalization Note. Entropy is measured in nats (Real.binEntropy uses natural log, as in Mathlib's Analysis.SpecialFunctions.BinaryEntropy), so the bound reads rather than ; the two forms are equivalent up to the base of the logarithm. This connects Mathlib's Real.binEntropy to Nat.choose for the first time, and is the tool needed to bound the size of a 'bad' bin-pattern set by a volume-of-Hamming-ball argument in entropy-compression proofs such as Spencer's partial-colouring method and Kleitman's diameter theorem.
import Mathlib open Finset
theorem choose_sum_le_exp_mul_binEntropy (n k : ℕ) (hn : 0 < n) (hk2 : 2 * k ≤ n) :
(∑ i ∈ Finset.range (k + 1), (n.choose i : ℝ)) ≤ Real.exp (n * Real.binEntropy ((k : ℝ) / n)) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.