AFTD Auto-Formalizing Theoretical Domains

Bonami.degree_zero_const

theoremverifiedimported Lean

Degree-zero Boolean functions are constant. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of degree at most $0$; that is, every set $S$ with nonzero Fourier--Walsh coefficient $\hat f(S)\ne 0$ satisfies $|S|\le 0$. Then $f$ is constant: for every point $x\in\{0,1\}^n$ one has $f(x)=f(x_0)$, where $x_0$ is the all-$\mathtt{false}$ point.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open BooleanAnalysis in
open MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real in
variable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in
lemma Bonami.degree_zero_const {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) :
    ∀ x, f x = f default
Source
TCSlib, `Bonami.degree_zero_const`
Lean proof
By Owen McGinty, Hydroxyi (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_zero_const
--- TCSlib/BooleanAnalysis/Hypercontractivity/Bonami.lean:37 (Bonami.degree_zero_const)
+++ as compiled here
@@ -1,5 +1,7 @@
-/-- Shows that a Boolean function of Fourier degree zero is constant.
-
-**Source:** [OD14, Cor. 9.6 (proof)]. -/
-lemma degree_zero_const {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) :
+set_option autoImplicit true in
+set_option relaxedAutoImplicit true in
+open BooleanAnalysis in
+open MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real in
+variable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in
+lemma Bonami.degree_zero_const {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) :
     ∀ x, f x = f default := by
@@ -11,4 +13,6 @@
   refine' Finset.sum_congr rfl fun S hS => _;
-  by_cases h : BooleanAnalysis.fourierCoeff f S = 0 <;> simp +decide [ h ];
-  specialize hf S h;
-  simp_all +singlePass [ Finset.card_eq_zero ] ;
+  by_cases h : BooleanAnalysis.fourierCoeff f S = 0
+  · simp only [h, zero_mul]
+  have hS : S = ∅ := Finset.card_eq_zero.mp (Nat.le_zero.mp (hf S h))
+  subst hS
+  simp [BooleanAnalysis.chiS]
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 16
Used by 1
  • Bonami.degree_zero_fourth_momentFourth moment of a degree-zero Boolean function. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function of degree at most $0$, meaning that every…

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen BooleanAnalysis inopen MeasureTheory Set Filter ProbabilityTheory BooleanAnalysis Real invariable {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] in/-- Shows that a Boolean function of Fourier degree zero is constant. **Source:** [OD14, Cor. 9.6 (proof)]. -/lemma Bonami.degree_zero_const {n : ℕ} (f : BooleanFunc n) (hf : has_degree_at_most f 0) :    ∀ x, f x = f default := by  intro x;  -- By definition of $f$, we can write it as a sum of its Fourier coefficients.  have h_fourier : f = fun x => ∑ S : Finset (Fin n), BooleanAnalysis.fourierCoeff f S * chiS S x := by    exact funext fun x => walsh_expansion f x;  rw [ h_fourier ];  refine' Finset.sum_congr rfl fun S hS => _;  by_cases h : BooleanAnalysis.fourierCoeff f S = 0  · simp only [h, zero_mul]  have hS : S = ∅ := Finset.card_eq_zero.mp (Nat.le_zero.mp (hf S h))  subst hS  simp [BooleanAnalysis.chiS]
See it in the graphDiscuss this resultChallenge it