Bonami.degree_zero_fourth_moment
theoremverifiedimported Lean
Fourth 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 set $S$ with a nonzero Fourier coefficient $\hat f(S)\ne 0$ satisfies $|S|\le 0$. Then, with expectations taken under the uniform measure on $\{0,1\}^n$, \[ \E[f^4] \;=\; \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.degree_zero_fourth_moment {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) : expect (fun x => f x ^ 4) = (expect (fun x => f x ^ 2)) ^ 2
- Source
- TCSlib, `Bonami.degree_zero_fourth_moment`
- 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.degree_zero_fourth_moment← Bonami.degree_zero_fourth_moment (TCSlib/BooleanAnalysis/Hypercontractivity/Bonami.lean:52): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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). \]
- 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
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- Bonami.degree_zero_constDegree-zero Boolean functions are constant. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of degree at most $0$; that is, every set $S$…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- 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…
- Used by 1
- Bonami.bonami_expectBonami inequality in expectation form. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function of degree at most $k$, meaning that every…
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen BooleanAnalysis inopen MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real invariable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in/-- Computes the fourth moment of a degree-zero Boolean function from its second moment. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.degree_zero_fourth_moment {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) : expect (fun x => f x ^ 4) = (expect (fun x => f x ^ 2)) ^ 2 := by -- Since $f$ is constant, we have $f(x) = f(default)$ for all $x$. have h_const : ∀ x : BoolCube n, f x = f default := by exact fun x => degree_zero_const f hf x; unfold expect; simp +decide [ h_const ] ; ring_nf; unfold uniformWeight; norm_num [ pow_mul ] ; ring_nf; simp [ pow_mul' ]