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.BooleanAnalysis.has_degree_at_most← BooleanAnalysis.has_degree_at_most (TCSlib/BooleanAnalysis/Basic.lean:320): adapted
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
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- 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