AFTD Auto-Formalizing Theoretical Domains

Bonami.restrictLast_true_eq

theoremverifiedimported Lean

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

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