AFTD Auto-Formalizing Theoretical Domains

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

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