AFTD Auto-Formalizing Theoretical Domains

BooleanAnalysis.has_degree_at_most

defimported Lean

A Boolean function $f$ has degree at most $k$ if every nonzero Fourier coefficient is supported on a set of size at most $k$: for all $S$, if $\hat f(S)\ne 0$ then $|S|\le k$.

Statement

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
def BooleanAnalysis.has_degree_at_most {n : ℕ} (f : (BooleanFunc n)) (k : ℕ) : Prop
Defined in
TCSlib, `BooleanAnalysis.has_degree_at_most`
Lean proof
By Jingzhen Sha, Allan Li, Hydroxyi, Mina, 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 BooleanAnalysis.has_degree_at_most
--- TCSlib/BooleanAnalysis/Basic.lean:320 (BooleanAnalysis.has_degree_at_most)
+++ as compiled here
@@ -1,5 +1,5 @@
-/-- Defines the predicate that a Boolean function has Fourier degree at most `k`.
-
-**Source:** [OD14, §1.3]. -/
-def has_degree_at_most {n : ℕ} (f : (BooleanFunc n)) (k : ℕ) : Prop :=
-  ∀ S, f ̂( S ) ≠ 0 → S.card ≤ k
+set_option maxHeartbeats 400000 in
+open scoped BigOperators in
+variable {n : ℕ} in
+def BooleanAnalysis.has_degree_at_most {n : ℕ} (f : (BooleanFunc n)) (k : ℕ) : Prop :=
+  ∀ S, (BooleanAnalysis.fourierCoeff f S) ≠ 0 → S.card ≤ k
Verified
07 Oct 2026
Axioms
none listed
Built on 2
Used by 8
  • Bonami.degree_avgLastAveraging over a coordinate preserves the degree bound. Let $f\colon\{0,1\}^{n+1}\to\bbr$ be a Boolean function on $n+1$ variables, and…
  • DecisionTree.degree_le_depthFourier degree of a decision tree is at most its depth. Let $T$ be a decision tree on $n$ Boolean variables, and let…
  • 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…
  • 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…
  • Bonami.bonami_lemmaBonami's hypercontractivity lemma for low-degree functions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function whose Fourier expansion has…
  • DecisionTree.degree_le_dtDepthDegree bounded by decision-tree depth. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean-valued function, and let $D(f)$ denote its…
  • Bonami.degree_diffLastDegree 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…
  • Bonami.degree_zero_constDegree-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$…

Lean source view module on GitHub

set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
/-- Defines the predicate that a Boolean function has Fourier degree at most `k`. **Source:** [OD14, §1.3]. -/
def BooleanAnalysis.has_degree_at_most {n : ℕ} (f : (BooleanFunc n)) (k : ℕ) : Prop :=
  ∀ S, (BooleanAnalysis.fourierCoeff f S) ≠ 0 → S.card ≤ k
See it in the graphDiscuss this resultChallenge it