Bonami.restrictLast_true_eq
Recovering the true-restriction from average and half-difference. Let $f : \{0,1\}^{n+1} \to \bbr$ be a Boolean function on $n+1$ variables. For a bit $b$, write $f_b : \{0,1\}^n \to \bbr$ for the restriction $x \mapsto f(x,b)$ that fixes the last coordinate to $b$, and let its average and half-difference over the last coordinate be the functions $\tfrac12(f_0 + f_1)$ and $\tfrac12(f_0 - f_1)$. Then for every point $x \in \{0,1\}^n$, the restriction fixing the last coordinate to $\mathrm{true}$ equals the average minus the half-difference at that point: \[ f_1(x) \;=\; \tfrac12\bigl(f_0(x) + f_1(x)\bigr) \;-\; \tfrac12\bigl(f_0(x) - f_1(x)\bigr). \]
Statement
open BooleanAnalysis in lemma Bonami.restrictLast_true_eq {n : ℕ} (f : BooleanFunc (n + 1)) (x : BoolCube n) : restrictLast f true x = avgLast f x - diffLast f x
- Source
- TCSlib, `Bonami.restrictLast_true_eq`
- 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.restrictLast_true_eq← Bonami.restrictLast_true_eq (TCSlib/BooleanAnalysis/Hypercontractivity/Decomposition.lean:51): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- Bonami.diffLastThe half-difference $\mathrm{diffLast}\,f$ of $f$ over its last coordinate is the function on $n$ variables given by…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- Bonami.avgLastThe average $\mathrm{avgLast}\,f$ of $f$ over its last coordinate is the function on $n$ variables given by…
- Bonami.restrictLastGiven a Boolean function $f$ on $n+1$ variables and a bit $b$, the restriction $\mathrm{restrictLast}\,f\,b$ is the function on $n$…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- Used by 1
- 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/-- States that the `true` restriction is the average minus the half-difference part. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.restrictLast_true_eq {n : ℕ} (f : BooleanFunc (n + 1)) (x : BoolCube n) : restrictLast f true x = avgLast f x - diffLast f x := by simp [restrictLast, avgLast, diffLast] ring