Bonami.degree_diffLast
theoremverifiedimported Lean
Degree bound for the half-difference over the last coordinate. Let $f\colon\{0,1\}^{n+1}\to\bbr$ be a Boolean function of degree at most $k$, meaning that every frequency set $S$ with nonzero Fourier--Walsh coefficient $\hat f(S)\ne 0$ satisfies $\abs{S}\le k$. Write $f_0$ and $f_1$ for the two restrictions of $f$ to $\{0,1\}^{n}$ obtained by fixing its last coordinate to $0$ and to $1$ respectively, and let $g=\tfrac12(f_0-f_1)$ be the half-difference of $f$ over that coordinate. Then $g$ is a Boolean function on $\{0,1\}^{n}$ of degree at most $k-1$, with $k-1$ interpreted as $0$ when $k=0$.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BooleanAnalysis in lemma Bonami.degree_diffLast {n : ℕ} (f : BooleanFunc (n + 1)) (k : ℕ) (hf : has_degree_at_most f k) : has_degree_at_most (diffLast f) (k - 1)
- Source
- TCSlib, `Bonami.degree_diffLast`
- 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.degree_diffLast← Bonami.degree_diffLast (TCSlib/BooleanAnalysis/Hypercontractivity/Decomposition.lean:283): adapted
What was changed in
Bonami.degree_diffLast--- TCSlib/BooleanAnalysis/Hypercontractivity/Decomposition.lean:283 (Bonami.degree_diffLast) +++ as compiled here @@ -1,5 +1,5 @@ -/-- Shows that the final-coordinate half-difference lowers a Fourier degree bound by one. - -**Source:** [OD14, Cor. 9.6 (proof)]. -/ -lemma degree_diffLast {n : ℕ} (f : BooleanFunc (n + 1)) (k : ℕ) +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open BooleanAnalysis in +lemma Bonami.degree_diffLast {n : ℕ} (f : BooleanFunc (n + 1)) (k : ℕ) (hf : has_degree_at_most f k) : @@ -13,3 +13,3 @@ have := hf (Finset.image Fin.castSucc S ∪ {Fin.last n}) - simp_all +decide [Finset.card_image_of_injective, Function.Injective] + simp_all +decide [Finset.card_image_of_injective _ (Fin.castSucc_injective _)] exact Nat.le_sub_one_of_lt h_card - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- Bonami.fourierCoeff_diffLastFourier coefficient of the half-difference over the last coordinate. Let $f\colon\{0,1\}^{n+1}\to\bbr$ be a Boolean function on $n+1$…
- Bonami.diffLastThe half-difference $\mathrm{diffLast}\,f$ of $f$ over its last coordinate is the function on $n$ variables given by…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.has_degree_at_mostA Boolean function $f$ has degree at most $k$ if every nonzero Fourier coefficient is supported on a set of size at most $k$: for…
- BooleanAnalysis.instModuleRealBooleanFuncBooleanAnalysis.instModuleRealBooleanFunc
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.instAddCommGroupBooleanFuncBoolean functions form an
ℝ-vector space.
- 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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen BooleanAnalysis in/-- Shows that the final-coordinate half-difference lowers a Fourier degree bound by one. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.degree_diffLast {n : ℕ} (f : BooleanFunc (n + 1)) (k : ℕ) (hf : has_degree_at_most f k) : has_degree_at_most (diffLast f) (k - 1) := by have h_fourier_coeff : ∀ S : Finset (Fin n), BooleanAnalysis.fourierCoeff (diffLast f) S = BooleanAnalysis.fourierCoeff f (Finset.image Fin.castSucc S ∪ {Fin.last n}) := by exact fourierCoeff_diffLast f intro S hS_nonzero have h_card : S.card + 1 ≤ k := by have := hf (Finset.image Fin.castSucc S ∪ {Fin.last n}) simp_all +decide [Finset.card_image_of_injective _ (Fin.castSucc_injective _)] exact Nat.le_sub_one_of_lt h_card