Rothvoß's Lemma 9: low entropy of the quantized row-sum shell
ProvedshannonEntropy_shellFin_leThis is Rothvoß's Lemma 9 from his exposition of Spencer's entropy method for discrepancy theory: quantizing the row sum of a random coloring into shells costs very little Shannon entropy once the shell width is a large multiple of .
Fix , a row , and . Write and let send a Boolean coloring to the (shifted, finite-alphabet) index of the width- shell containing its row sum . Then, treating as uniformly random, the Shannon entropy (base 2) of this shell-index random variable satisfies
Intuitively, for the row sum concentrates in the central shell with overwhelming probability, so the shell index carries almost no information; this is the quantitative form of that statement, and it is the key per-row estimate combined across many rows (via subadditivity of entropy) to prove Spencer's discrepancy theorem.
Formalization Note. , , and are the platform definitions of the same names; is the of Definitions.Def_DiscreteEntropy, computed with respect to the uniform measure on colorings implicit in that definition.
import Mathlib import Definitions.Def_DiscreteEntropy import Definitions.Def_shellFin open Finset
theorem shannonEntropy_shellFin_le {m : ℕ} (hm : 1 ≤ m) (a : Fin m → ℝ)
(h01 : ∀ j, a j = 0 ∨ a j = 1) (lam : ℝ) (hlam : 2 ≤ lam) :
shannonEntropy (shellFin (lam * Real.sqrt (m:ℝ)) a)
≤ (12 / Real.log 2) * Real.exp (-lam^2/4) := by sorry
Confirmed by the mission captain (proposal self-audit).