Fourier analysis on the Boolean cube

Remarks

The parity functions are exactly the characters of the group $\set{-1, 1}^n$, and they form an orthonormal basis for $\ip{f}{g} = 2^{-n}\sum_x f(x) g(x)$, by the basis theorem for characters. So the expansion holds and is unique, and Parseval's identity $2^{-n}\sum_x f(x)^2 = \sum_S \widehat{f}(S)^2$ holds. Up to the factor $2^{-n}$ and a change from $\set{0,1}$ to $\set{-1,1}$, the vector of coefficients is the Walsh–Hadamard transform of the table of values of $f$.

Example: for majority on three inputs, $\mathrm{Maj}(x) = \frac{1}{2}(x_1 + x_2 + x_3) - \frac{1}{2}x_1x_2x_3$. Check: at $(1, 1, 1)$ the right side is $\frac{3}{2} - \frac{1}{2} = 1$; at $(1, 1, -1)$ it is $\frac{1}{2} + \frac{1}{2} = 1$; at $(1, -1, -1)$ it is $-\frac{1}{2} - \frac{1}{2} = -1$; the other points follow by symmetry and by $\mathrm{Maj}(-x) = -\mathrm{Maj}(x)$.

Non-example: the polynomial $x_1^2 x_2$ is not multilinear, so it is not a Fourier expansion in this sense. On the cube $x_1^2 = 1$, so as a function it equals $\chi_{\set{2}}$; the expansion is unique only among multilinear polynomials.

The degree of $f$ is the largest $\abs{S}$ with $\widehat{f}(S) \ne 0$, and the influence of coordinate $i$ on $f$ with values in $\set{-1,1}$ is $\sum_{S \ni i} \widehat{f}(S)^2$.