BoolFourier.BoolFun
abbrevimported Lean
A Boolean function of arity $n$ is an element of type $\{0,1\}^n \to \mathbb{R}$,
defined as an abbreviation for BooleanAnalysis.BooleanFunc $n$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BooleanAnalysis in abbrev BoolFourier.BoolFun (n : ℕ)
- Defined in
- TCSlib, `BoolFourier.BoolFun`
- Lean proof
- By Prastik Mohanraj, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Prastik Mohanraj. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.BoolFourier.BoolFun← BoolFourier.BoolFun (TCSlib/BooleanAnalysis/BLR/BoolFourier.lean:55): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- Used by 18
- 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…
- BoolFourier.expectationFor $f : \{0,1\}^n \to \mathbb{R}$, the uniform expectation is \[ \mathbb{E}[f] = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} f(x). \]
- BoolFourier.parseval_identity_aux_hL2$L^2$ norm squared as a self inner product. Let $f : \{0,1\}^n \to \bbr$ be a real-valued function on the Boolean hypercube, and equip…
- BoolFourier.fourier_coeff_eqAgreement of two Fourier coefficient definitions. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function of arity $n$, and let…
- BoolFourier.char_SFor a set $S \subseteq [n]$, the Walsh character $\chi_S : \{0,1\}^n \to \mathbb{R}$ is \[ \chi_S(x) = \prod_{i \in S} (-1)^{x_i}, \]…
- BoolFourier.convolutionThe convolution of $f, g : \{0,1\}^n \to \mathbb{R}$ is the function \[ (f * g)(x) = \mathbb{E}_{y}\bigl[f(y)\,g(x \oplus y)\bigr]. \]
- BoolFourier.L2_norm_sqThe squared $L^2$ norm of $f : \{0,1\}^n \to \mathbb{R}$ is \[ \|f\|_2^2 = \mathbb{E}[f^2] = \frac{1}{2^n}\sum_{x} f(x)^2. \]
- BoolFourier.expectation_eq_expectAgreement of two definitions of the uniform expectation. Let $n$ be a natural number and let $f : \{0,1\}^n \to \bbr$ be a Boolean…
- BoolFourier.fourier_coeff_convolution_aux_h_fubiniInterchange of summation in the convolution coefficient. Let $n$ be a natural number, let $f, g : \{0,1\}^n \to \bbr$ be Boolean…
- 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…
- BoolFourier.fourier_coeff_convolutionConvolution theorem on the Boolean cube. Let $n$ be a natural number, and let $f, g : \{0,1\}^n \to \bbr$ be Boolean functions. Then for…
- BoolFourier.fourier_coeffThe Fourier coefficient of $f : \{0,1\}^n \to \mathbb{R}$ at $S \subseteq [n]$ is \[ \hat f(S) = \langle f, \chi_S \rangle. \]
- BoolFourier.fourier_expansionFourier–Walsh expansion. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function and let $x \in \{0,1\}^n$. Then $f$ agrees pointwise with the…
- BoolFourier.fourier_coeff_convolution_aux_h_charShift rule for character-weighted sums. Let $f, g : \{0,1\}^n \to \bbr$ be Boolean functions, let $S \subseteq [n]$, and write…
- BoolFourier.inner_productThe inner product of $f, g : \{0,1\}^n \to \mathbb{R}$ is…
- BoolFourier.fourier_coeff_convolution_aux_h_splitMultiplicative splitting of a Walsh character along XOR. Let $S \subseteq [n]$, let $f, g : \{0,1\}^n \to \bbr$ be Boolean functions, and…
- BoolBLR.lift_pm1Given $f : \{0,1\}^n \to \{0,1\}$, its $\pm 1$ lift $\texttt{BoolBLR.lift\_pm1}\,f : \{0,1\}^n \to \mathbb{R}$ is defined by…
- BoolFourier.parseval_identityParseval's identity for the Walsh–Fourier expansion. Let $f : \{0,1\}^n \to \bbr$ be a real-valued function on the Boolean hypercube, and…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Finset BooleanAnalysis in /-- Names real-valued functions on the `n`-dimensional Boolean hypercube. **Source:** [OD14, §1.3]. -/ abbrev BoolFourier.BoolFun (n : ℕ) := BooleanFunc n