AFTD Auto-Formalizing Theoretical Domains

Bonami.sum_boolCube_succ

theoremverifiedimported Lean

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.
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

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
See it in the graphDiscuss this resultChallenge it