1 Boolean Analysis — Core Definitions
1.1 Overview
This chapter develops the Fourier–Walsh theory of Boolean functions \(f : \{ 0,1\} ^n \to \mathbb {R}\). The uniform probability measure on \(\{ 0,1\} ^n\) endows the space of Boolean functions with an \(L^2\) inner product \(\langle f, g\rangle = \mathbb {E}[fg]\). The Walsh characters \(\chi _S(x) = \prod _{i\in S}(-1)^{x_i}\), indexed by subsets \(S\subseteq [n]\), form an orthonormal basis for this space, yielding the Walsh–Fourier expansion \(f = \sum _S \hat f(S)\, \chi _S\).
The main results are:
Walsh expansion (Fourier inversion).
Parseval’s identity: \(\| f\| ^2 = \sum _S \hat f(S)^2\).
Influence via Fourier: \(\mathrm{Inf}_i[f] = \sum _{S\ni i}\hat f(S)^2\).
Total influence: \(I[f] = \sum _S |S|\, \hat f(S)^2\).
Noise operator in the Fourier domain: \(\widehat{T_\rho f}(S) = \rho ^{|S|}\hat f(S)\).
Reference: Ryan O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014.
1.2 The Boolean hypercube and functions
The Boolean hypercube of dimension \(n\) is \(\{ 0,1\} ^n\), represented as the function type \(\mathrm{Fin}\, n \to \mathrm{Bool}\).
A Boolean function of arity \(n\) is a function \(f : \{ 0,1\} ^n \to \mathbb {R}\).
1.3 Uniform measure and expectation
The uniform probability measure on \(\{ 0,1\} ^n\) assigns weight \(2^{-n}\) to each point.
The expectation of \(f\) under the uniform measure:
The \(L^2\) inner product of two Boolean functions with respect to the uniform measure:
The \(L^2\) norm of \(f\): \(\| f\| = \sqrt{\langle f,f\rangle }\).
\(\langle f, g\rangle = \langle g, f\rangle \).
\(\langle f, f\rangle \ge 0\).
\(\langle f + g, h\rangle = \langle f, h\rangle + \langle g, h\rangle \).
1.4 Walsh–Fourier characters
The sign encoding maps \(\mathrm{Bool}\) to \(\{ -1,1\} \subset \mathbb {R}\):
\(\sigma (\texttt{false}) = 1\), \(\sigma (\texttt{true}) = -1\), \(\sigma (b)^2 = 1\), and \(\sigma (\lnot b) = -\sigma (b)\).
The Walsh–Fourier character associated to \(S\subseteq [n]\) is
The family \(\{ \chi _S\} _{S\subseteq [n]}\) forms an orthonormal basis for \(L^2(\{ 0,1\} ^n,\mathrm{uniform})\).
\(\chi _\varnothing \equiv 1\).
\(\chi _{\{ i\} }(x) = \sigma (x_i)\).
\(\chi _S(x)^2 = 1\) for all \(S\) and \(x\).
If \(S\) and \(T\) are disjoint then \(\chi _{S\cup T}(x) = \chi _S(x)\cdot \chi _T(x)\).
\(\chi _S(x)\cdot \chi _T(x) = \chi _{S\mathbin {\triangle } T}(x)\), where \(\triangle \) denotes symmetric difference.
Flipping all bits multiplies the character by \((-1)^{|S|}\):
There are exactly \(2^n\) Walsh characters, matching the dimension of \(L^2(\{ 0,1\} ^n)\).
1.5 Fourier coefficients
The Fourier–Walsh coefficient of \(f\) at frequency \(S\) is
\(\hat f(\varnothing ) = \mathbb {E}[f]\).
1.6 Walsh expansion
Every Boolean function \(f:\{ 0,1\} ^n\to \mathbb {R}\) has the unique representation
This is the Fourier inversion formula for the uniform measure on \(\{ 0,1\} ^n\).
1.7 Orthonormality and Parseval’s identity
The Walsh characters form an orthonormal system:
\(\langle \chi _S, \chi _S\rangle = 1\).
The squared \(L^2\) norm of \(f\) equals the sum of squared Fourier coefficients:
1.8 Coordinate influence
The point \(x^i\in \{ 0,1\} ^n\) obtained from \(x\) by flipping the \(i\)-th coordinate.
The influence of coordinate \(i\) on \(f\) measures how often flipping bit \(i\) changes the output:
For \(\pm 1\)-valued \(f\) this equals \(\Pr [f(x)\ne f(x^i)]\).
\(I[f] = \sum _{i=1}^n \mathrm{Inf}_i[f]\).
\(\mathrm{Inf}_i[\chi _S] = [i\in S]\).
For any \(\pm 1\)-valued function and any coordinate \(i\), \(\mathrm{Inf}_i[f] \le 1\).
There exists a coordinate \(i\) with \(\mathrm{Inf}_i[f] \ge I[f]/n\).
1.9 Noise operator
The noise operator \(T_\rho \) with parameter \(\rho \in [-1,1]\), defined via the Fourier domain by
Probabilistically, \(T_\rho f(x) = \mathbb {E}_y[f(y)]\) where each bit of \(y\) agrees with \(x_i\) with probability \(\tfrac {1+\rho }{2}\) and is flipped with probability \(\tfrac {1-\rho }{2}\), independently.
1.10 Notable Boolean functions
The dictator function for coordinate \(i\) outputs the sign of the \(i\)-th bit: \(\mathrm{dict}_i(x) = (-1)^{x_i}\). Its unique nonzero Fourier coefficient is \(\widehat{\mathrm{dict}_i}(\{ i\} ) = 1\).
\(\mathrm{dict}_i = \chi _{\{ i\} }\).
The parity function \(f(x) = (-1)^{x_1+\cdots +x_n}\) satisfies \(\hat f([n]) = 1\) and \(\hat f(S) = 0\) for \(S\ne [n]\).
\(\mathrm{parity}_n = \chi _{[n]}\).
The majority function on \(\{ 0,1\} ^{2k+1}\) outputs \(1\) if more than half the inputs are \(\texttt{false}\), and \(-1\) otherwise.
1.11 Sensitivity
The sensitivity of \(f\) at \(x\) is the number of coordinates \(i\) such that flipping bit \(i\) changes \(f(x)\).
The maximum sensitivity of \(f\) over all inputs.
1.12 Properties for Arrow’s theorem
A Boolean function \(f\) is odd if \(f(\lnot x) = -f(x)\) for all \(x\). This models antisymmetry of pairwise preferences in social choice.
\(f\) is \(\pm 1\)-valued if \(f(x)\in \{ -1,1\} \) for all \(x\).
If \(f\) is odd and \(|S|\) is even, then \(\hat f(S) = 0\).
If \(f\) is \(\pm 1\)-valued then \(\langle f, f\rangle = 1\).
If \(f\) is \(\pm 1\)-valued then \(\sum _{S\subseteq [n]}\hat f(S)^2 = 1\).
The Fourier weight at level \(k\) is
1.13 Additional declarations
Let \(P\) be a probability measure on \(\{ 0,1\} ^n\) that assigns the uniform weight to each singleton. Then for any Boolean function \(f\) and \(p\in \mathbb {N}\), the \(p\)-th moment of \(f\) under \(P\) equals the uniform expectation of \(f^p\):
For any \(c : \mathrm{Fin}\, n \to \mathbb {R}\),
For points \(x, y\in \{ 0,1\} ^n\),
This is the completeness kernel underlying Fourier inversion.
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\).
Summing the sign encoding over the two Boolean values gives zero: \(\sum _{b\in \mathrm{Bool}} \sigma (b) = 0\).
Summing the character \(\chi _S\) over the whole hypercube yields
The inner product of two Boolean functions equals the sum of the products of their Fourier coefficients:
Flipping coordinate \(i\) twice returns the original point: \((x^i)^i = x\).
If \(i\ne j\) then flipping coordinate \(i\) does not change coordinate \(j\): \((x^i)_j = x_j\).
Flipping coordinate \(i\) negates \(\chi _S\) when \(i\in S\) and leaves it unchanged otherwise:
The discrete derivative of \(f\) in direction \(i\) is the Boolean function
where \(x^{i\mapsto b}\) sets coordinate \(i\) of \(x\) to \(b\).
The discrete derivative respects addition: \(D_i(f + g) = D_i f + D_i g\).
The discrete derivative commutes with scalar multiplication: \(D_i(c\cdot f) = c\cdot D_i f\) for \(c\in \mathbb {R}\).
The discrete derivative \(D_i\) packaged as an \(\mathbb {R}\)-linear map on the space of Boolean functions.
The expectation operator in direction \(i\) averages \(f\) over the two values of coordinate \(i\):
The expectation operator respects addition: \(E_i(f + g) = E_i f + E_i g\).
The expectation operator commutes with scalar multiplication: \(E_i(c\cdot f) = c\cdot E_i f\) for \(c\in \mathbb {R}\).
The expectation operator \(E_i\) packaged as an \(\mathbb {R}\)-linear map on the space of Boolean functions.
The noise operator \(T_\rho \) is self-adjoint with respect to the \(L^2\) inner product: