fourier-exp]

2026-08-26

Every Boolean function can be written uniquely as a multilinear polynomial in the functions

𝜒_{𝑆} (𝑥) = \prod_{𝑖 \in 𝑆} 𝑥_{𝑖}, 𝑆 \subseteq [𝑛] :

𝑓 (𝑥) = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} (𝑆) 𝜒_{𝑆} (𝑥),

where $\hat{𝑓} (𝑆) \in ℝ$ is the Fourier coefficient of $𝑓$ on $𝑆$ .

The $𝜒_{𝑆}$ are called parity functions. Where $𝜒_{𝑆} (𝑥) = - 1$ exactly when an odd number of the bits ${(𝑥_{𝑖})}_{𝑖 \in 𝑆}$ are $- 1$ . Importantly, they form a basis of the $2^{𝑛}$ -dimensional vector space of functions $𝑓 : {\pm 1}^{𝑛} \to ℝ$ .