Bonami.bonami_lemma
theoremverifiedformalizationimported Lean
Bonami's hypercontractivity lemma for low-degree functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function whose Fourier expansion has degree at most $k$; that is, every nonzero Fourier coefficient $\hat f(S)$ is supported on a set $S$ with $\abs{S} \le k$. When $\{0,1\}^n$ is equipped with the uniform probability measure, $f$ is $9^k$-reasonable: its fourth moment is controlled by the square of its second moment via \[ \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_lemma {n : ℕ} (k : ℕ) (f : BooleanFunc n) (hf : has_degree_at_most f k) : IsBReasonable f (uniformMeasure n) ((9 : ℝ) ^ k)
- Formalizes
- Bonami's hypercontractivity lemma for low-degree functions, as formalized in TCSlib (`Bonami.bonami_lemma`)
- 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_lemma← Bonami.bonami_lemma (TCSlib/BooleanAnalysis/Hypercontractivity/Bonami.lean:174): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- Bonami.uniformMeasureThe canonical uniform probability measure on the Boolean hypercube $\{0,1\}^n$.
- Bonami.uniformMeasure_applyUniform measure of a single point of the hypercube. Let $n$ be a natural number and let $x$ be a point of the Boolean hypercube…
- 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.moment_eq_expectMoments equal expectations under the uniform law. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function of arity $n$, let $p$ be a natural…
- 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…
- Bonami.instIsProbabilityMeasureBoolCubeUniformMeasureBonami.instIsProbabilityMeasureBoolCubeUniformMeasure
- 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…
- Bonami.IsBReasonableA real random variable $X$ on a measurable space $\Omega$ with measure $P$ is $B$-reasonable when its fourth moment is controlled…
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/-- Shows that a degree-`k` Boolean function is `9^k`-reasonable under the uniform measure. This is the uniform-bit specialization of the stated corollary. **Source:** [OD14, Cor. 9.6]. -/lemma Bonami.bonami_lemma {n : ℕ} (k : ℕ) (f : BooleanFunc n) (hf : has_degree_at_most f k) : IsBReasonable f (uniformMeasure n) ((9 : ℝ) ^ k) := (by refine ⟨inferInstance, one_le_pow₀ (by norm_num), MemLp.of_discrete, ?_⟩ rw [moment_eq_expect f 4 (uniformMeasure n) uniformMeasure_apply] rw [moment_eq_expect f 2 (uniformMeasure n) uniformMeasure_apply] exact bonami_expect k f hf)