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