Bonami.bonami_expect
theoremverifiedimported Lean
Bonami inequality in expectation form. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function of degree at most $k$, meaning that every nonzero Fourier coefficient $\hat f(S)$ is supported on a set $S$ with $|S| \le k$. Writing $\E$ for the expectation under the uniform measure on $\{0,1\}^n$, we then have \[ \E[f^4] \;\le\; 9^{k}\,\bigl(\E[f^2]\bigr)^2. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in open MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real in variable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in lemma Bonami.bonami_expect {n : ℕ} (k : ℕ) (f : BooleanFunc n) (hf : has_degree_at_most f k) : expect (fun x ↦ f x ^ 4) ≤ (9 : ℝ) ^ k * (expect (fun x ↦ f x ^ 2)) ^ 2
- Source
- TCSlib, `Bonami.bonami_expect`
- Lean proof
- By Owen McGinty, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.Bonami.bonami_expect← Bonami.bonami_expect (TCSlib/BooleanAnalysis/Hypercontractivity/Bonami.lean:80): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 21
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.expectThe expectation of $f$ under the uniform measure: \[ \E[f] \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x). \]
- Bonami.diffLastThe half-difference $\mathrm{diffLast}\,f$ of $f$ over its last coordinate is the function on $n$ variables given by…
- Bonami.degree_avgLastAveraging over a coordinate preserves the degree bound. Let $f\colon\{0,1\}^{n+1}\to\bbr$ be a Boolean function on $n+1$ variables, and…
- Bonami.degree_zero_fourth_momentFourth moment of a degree-zero Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of degree at most $0$, meaning that every…
- BooleanAnalysis.has_degree_at_mostA Boolean function $f$ has degree at most $k$ if every nonzero Fourier coefficient is supported on a set of size at most $k$: for…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BooleanAnalysis.instModuleRealBooleanFuncBooleanAnalysis.instModuleRealBooleanFunc
- Bonami.second_moment_decompSecond-moment decomposition over the last coordinate. Let $f : \{0,1\}^{n+1} \to \bbr$ be a Boolean function on $n+1$ variables. Define…
- Bonami.expect_sq_nonnegNonnegativity of the mean square. For every Boolean function $f : \{0,1\}^n \to \bbr$, the expectation of $f^2$ under the uniform measure…
- Bonami.avgLastThe average $\mathrm{avgLast}\,f$ of $f$ over its last coordinate is the function on $n$ variables given by…
- Bonami.degree_diffLastDegree bound for the half-difference over the last coordinate. Let $f\colon\{0,1\}^{n+1}\to\bbr$ be a Boolean function of degree at most…
- Bonami.expect_sq_nonneg_prodNonnegativity of the expectation of a product of squares. For any two Boolean functions $g, h : \{0,1\}^n \to \bbr$, the expectation of…
- Bonami.fourth_moment_decompFourth-moment decomposition over the last coordinate. Let $f : \{0,1\}^{n+1} \to \bbr$ be a Boolean function on $n+1$ variables, and let…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- Bonami.expect_fourth_nonnegNonnegativity of the fourth moment. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function on the Boolean hypercube. Then its fourth moment…
- Bonami.bonami_algebraAlgebraic inductive step for the Bonami lemma. Fix a natural number $m$, and let $a, b, B, C$ be nonnegative real numbers and $A$ a real…
- BooleanAnalysis.instAddCommGroupBooleanFuncBoolean functions form an
ℝ-vector space. - BooleanAnalysis.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- Bonami.expect_cs_sqCauchy–Schwarz for the uniform expectation. Let $g, h : \{0,1\}^n \to \bbr$ be Boolean functions, and let $\E[\,\cdot\,]$ denote the…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- Used by 1
- Bonami.bonami_lemmaBonami's hypercontractivity lemma for low-degree functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function whose Fourier expansion has…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in open MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real in variable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in /-- Bounds the fourth moment of a degree-`k` Boolean function by `9^k` times its squared second moment. This is the uniform-bit specialization of the stated corollary. **Source:** [OD14, Cor. 9.6]. -/ lemma Bonami.bonami_expect {n : ℕ} (k : ℕ) (f : BooleanFunc n) (hf : has_degree_at_most f k) : expect (fun x ↦ f x ^ 4) ≤ (9 : ℝ) ^ k * (expect (fun x ↦ f x ^ 2)) ^ 2 := by induction n generalizing k with | zero => -- BoolCube 0 has one element, everything reduces to f(default) unfold expect; norm_num [ Finset.card_univ ] ; ring_nf ; norm_cast; norm_num; unfold uniformWeight; norm_num; ring_nf; norm_cast; norm_num; exact le_mul_of_one_le_right ( by positivity ) ( one_le_pow₀ ( by norm_num ) ) | succ n ih => by_cases hk : k = 0 · -- k = 0: f is constant subst hk simp only [pow_zero, one_mul] exact le_of_eq (degree_zero_fourth_moment f hf) · -- k ≥ 1: write k = m + 1 obtain ⟨m, rfl⟩ : ∃ m, k = m + 1 := Nat.exists_eq_succ_of_ne_zero hk -- Define g = avgLast f, h = diffLast f set g := avgLast f set hh := diffLast f -- Apply the decompositions rw [fourth_moment_decomp f, second_moment_decomp f] -- Get degree bounds have hg_deg : has_degree_at_most g (m + 1) := degree_avgLast f (m + 1) hf have hh_deg : has_degree_at_most hh m := by have := degree_diffLast f (m + 1) hf simp at this exact this -- Apply IH have hg_bound := ih (m + 1) g hg_deg have hh_bound := ih m hh hh_deg -- Get non-negativity have ha := expect_sq_nonneg g have hb := expect_sq_nonneg hh have hA := expect_fourth_nonneg g have hB := expect_fourth_nonneg hh -- Get Cauchy-Schwarz have hCS := expect_cs_sq g hh -- Apply the algebraic lemma set a := expect (fun x => g x ^ 2) set b := expect (fun x => hh x ^ 2) set A := expect (fun x => g x ^ 4) set B := expect (fun x => hh x ^ 4) set C := expect (fun x => g x ^ 2 * hh x ^ 2) have hC_nn : 0 ≤ C := expect_sq_nonneg_prod g hh exact bonami_algebra ha hb hB hC_nn hg_bound hh_bound hCS