Bonami.sum_boolCube_succ
Splitting a sum over the hypercube on its last coordinate. Let $n$ be a natural number and let $\varphi \colon \{0,1\}^{n+1} \to \bbr$ be a real-valued function on the Boolean hypercube of dimension $n+1$. Then the sum of $\varphi$ over all points of the cube splits according to the value of the final coordinate: \[ \sum_{x \in \{0,1\}^{n+1}} \varphi(x) \;=\; \sum_{y \in \{0,1\}^{n}} \varphi\bigl((y,\mathrm{false})\bigr) \;+\; \sum_{y \in \{0,1\}^{n}} \varphi\bigl((y,\mathrm{true})\bigr), \] where $(y,b)$ denotes the point of $\{0,1\}^{n+1}$ obtained by appending the bit $b$ to $y \in \{0,1\}^{n}$ as its last coordinate.
Statement
open BooleanAnalysis in lemma Bonami.sum_boolCube_succ {n : ℕ} (φ : BoolCube (n + 1) → ℝ) : ∑ x : BoolCube (n + 1), φ x = ∑ x : BoolCube n, φ (Fin.snoc x false) + ∑ x : BoolCube n, φ (Fin.snoc x true)
- Source
- TCSlib, `Bonami.sum_boolCube_succ`
- Lean proof
- By Owen McGinty (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.sum_boolCube_succ← Bonami.sum_boolCube_succ (TCSlib/BooleanAnalysis/Hypercontractivity/Decomposition.lean:59): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- Used by 3
- 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.expect_succ_eqExpectation splits over the last coordinate. Let $\varphi : \{0,1\}^{n+1} \to \bbr$ be a Boolean function on $n+1$ variables, and for a…
- 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…
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 BooleanAnalysis in/-- Splits a sum over an `(n + 1)`-dimensional Boolean cube by its final coordinate. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.sum_boolCube_succ {n : ℕ} (φ : BoolCube (n + 1) → ℝ) : ∑ x : BoolCube (n + 1), φ x = ∑ x : BoolCube n, φ (Fin.snoc x false) + ∑ x : BoolCube n, φ (Fin.snoc x true) := by have h_split : ∑ x : BoolCube (n + 1), φ x = ∑ x : BoolCube n × Bool, φ (Fin.snoc x.1 x.2) := by apply Finset.sum_bij (fun x _ => (Fin.init x, x (Fin.last n))) · simp +zetaDelta at * · simp +contextual [funext_iff] exact fun a₁ a₂ h₁ h₂ x => by cases x using Fin.lastCases <;> simp_all +decide [Fin.init] · intro b hb use Fin.snoc b.1 b.2 aesop · aesop simp_all +decide [← Finset.sum_add_distrib] erw [Finset.sum_product] exact Finset.sum_congr rfl fun _ _ => by rw [Finset.sum_eq_add] <;> aesop