Bonami.bonami_algebra
theoremverifiedimported Lean
Algebraic 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 number satisfying $A \le 9^{m+1} a^2$, $B \le 9^m b^2$, and $C^2 \le A B$. Then \[ A + 6C + B \le 9^{m+1}\,(a+b)^2. \]
Statement
open MeasureTheory Set Filter ProbabilityTheory Real in variable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in lemma Bonami.bonami_algebra {m : ℕ} {a b A B C : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hB : 0 ≤ B) (hC : 0 ≤ C) (hA_bound : A ≤ 9 ^ (m + 1) * a ^ 2) (hB_bound : B ≤ 9 ^ m * b ^ 2) (hC_bound : C ^ 2 ≤ A * B) : A + 6 * C + B ≤ 9 ^ (m + 1) * (a + b) ^ 2
- Source
- TCSlib, `Bonami.bonami_algebra`
- 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_algebra← Bonami.bonami_algebra (TCSlib/BooleanAnalysis/Hypercontractivity/Bonami.lean:64): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- 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.
open MeasureTheory Set Filter ProbabilityTheory Real invariable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in/-- Closes the algebraic recurrence in the inductive proof of the Bonami bound. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.bonami_algebra {m : ℕ} {a b A B C : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (hB : 0 ≤ B) (hC : 0 ≤ C) (hA_bound : A ≤ 9 ^ (m + 1) * a ^ 2) (hB_bound : B ≤ 9 ^ m * b ^ 2) (hC_bound : C ^ 2 ≤ A * B) : A + 6 * C + B ≤ 9 ^ (m + 1) * (a + b) ^ 2 := by -- By combining terms, we can factor out common factors and simplify the expression. ring_nf at *; nlinarith [ show 0 ≤ 9 ^ m by positivity, show 0 ≤ a * b * 9 ^ m by positivity, sq_nonneg ( C - a * b * 9 ^ m * 3 ), mul_le_mul_of_nonneg_left hB_bound ( show 0 ≤ 9 ^ m by positivity ) ]