AFTD Auto-Formalizing Theoretical Domains

BooleanAnalysis.instAddCommGroupBooleanFunc

instanceimported Lean

Boolean functions form an ℝ-vector space.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
instance BooleanAnalysis.instAddCommGroupBooleanFunc : AddCommGroup (BooleanFunc n)
Defined in
TCSlib, `BooleanAnalysis.instAddCommGroupBooleanFunc`
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.
Verified
07 Oct 2026
Axioms
none listed
Built on 1
Used by 15
  • BoolBLR.fourier_coeff_le_of_far_from_linearFourier coefficient bound for functions far from linear. Let $f : \{0,1\}^n \to \{0,1\}$ be $\varepsilon$-far from linear, meaning that…
  • explicitApproximant_mem_degreeSpaceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables, the explicit approximant P_f belongs to degreeSpace (K := ℝ) (Fin…
  • 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…
  • 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…
  • BooleanAnalysis.instModuleRealBooleanFuncBooleanAnalysis.instModuleRealBooleanFunc
  • 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…
  • BoolBLR.BLR_soundness_via_fourierSum of cubed Fourier coefficients bounds distance to linearity. Let $f : \{0,1\}^n \to \{0,1\}$ be a Boolean function and let…
  • ternary_lift_realApproxDegree_leSuppose n, d : ℕ with 40 ≤ n. If f : (Fin n → Bool) → Bool, P : (Fin n → Bool) → ℝ is in degreeSpace ℝ (Fin n) d, and Z : (Fin n → Bool) →…
  • BoolBLR.fourier_coeff_le_of_dist_ge_aux_h_lift_pm1Product of $\pm 1$ lifts as a disagreement indicator. Let $f, g : \{0,1\}^n \to \{0,1\}$ be Boolean-valued functions on the hypercube, and…
  • BoolBLR.fourier_coeff_le_of_dist_geFourier coefficient bound from distance. Let $f,g:\{0,1\}^n\to\{0,1\}$ be Boolean-valued functions, let $S\subseteq[n]$, and let…
  • BoolBLR.BLR_soundnessSoundness of the BLR linearity test. Let $f : \{0,1\}^n \to \{0,1\}$ and let $\varepsilon \in \bbr$ satisfy $0 \le \varepsilon \le 1$.…
  • 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…
  • BoolBLR.BLR_soundness_via_fourier_aux_h_boundPer-coefficient cube bound for functions far from linear. Let $f : \{0,1\}^n \to \{0,1\}$ be $\varepsilon$-far from linear, meaning that…
  • 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 autoImplicit true in
set_option relaxedAutoImplicit true in
set_option maxHeartbeats 400000 in
open scoped BigOperators in
variable {n : ℕ} in
/-- Boolean functions form an `ℝ`-vector space. -/
instance BooleanAnalysis.instAddCommGroupBooleanFunc : AddCommGroup (BooleanFunc n) := Pi.addCommGroup
See it in the graphDiscuss this resultChallenge it