For every natural number \(n\), the Boolean hypercube \(\{ 0,1\} ^n\) has exactly \(2^n\) elements.

Under the embedding \(\mathrm{BoolToPM1} : \mathrm{Bool} \to \mathbb {R}\) that sends \(\mathtt{false}\) to \(1\) and \(\mathtt{true}\) to \(-1\), the average of its two values is zero:

For every Boolean value \(b\), the image \(\mathrm{BoolToPM1}(b)\) under the map sending \(\mathtt{false}\) to \(1\) and \(\mathtt{true}\) to \(-1\) satisfies \(\mathrm{BoolToPM1}(b)\cdot \mathrm{BoolToPM1}(b) = 1\); that is, this \(\pm 1\)-valued quantity squares to \(1\).

Let \(\mathrm{BoolToPM1} : \mathrm{Bool} \to \mathbb {R}\) be the Bool-to-\(\pm 1\) embedding, which sends \(\mathtt{false}\) to \(1\) and \(\mathtt{true}\) to \(-1\). Then for every Boolean value \(b\), negating \(b\) flips the sign of its image:

Let \(\mathrm{BoolToPM1} : \mathrm{Bool} \to \mathbb {R}\) be the map sending \(\mathtt{false}\) to \(1\) and \(\mathtt{true}\) to \(-1\). Then for all Booleans \(a\) and \(b\),

so the exclusive-or \(a \oplus b\) is carried to the ordinary product in \(\{ -1,1\} \subset \mathbb {R}\).

Let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be given coordinatewise, so that for each index \(i \in \{ 0,\dots ,n-1\} \) we have a function \(g_i : \{ 0,1\} \to \mathbb {R}\), and let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be the product function \(f(x) = \prod _{i} g_i(x_i)\). Then its uniform expectation over the Boolean hypercube factorises as

Let \(n\) be a natural number and let \(S \subseteq [n]\). Evaluating the Walsh character \(\chi _S : \{ 0,1\} ^n \to \mathbb {R}\) at the all-zeros point \(\mathbf{0}\) (the vector whose every coordinate is \(\mathtt{false}\)) gives

Let \(n\) be a natural number, let \(S \subseteq [n]\), and let \(x \in \{ 0,1\} ^n\). Then the Walsh–Fourier character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) satisfies

Let \(n\) be a natural number. The Walsh character \(\chi _\emptyset \) associated to the empty subset of \([n]\) is the constant function equal to \(1\) on the Boolean hypercube; that is, \(\chi _\emptyset (x) = 1\) for every \(x \in \{ 0,1\} ^n\).

For any two subsets \(S, T \subseteq [n]\) and any point \(x \in \{ 0,1\} ^n\),

where \(\chi _S\) denotes the Walsh–Fourier character of \(S\) and \(S \mathbin {\triangle } T\) is the symmetric difference of \(S\) and \(T\).

Fix \(n \in \mathbb {N}\), and for each subset \(S \subseteq [n]\) let \(\chi _S \colon \{ 0,1\} ^n \to \mathbb {R}\) denote the Walsh–Fourier character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\). Writing \(\mathbf{0}\) for the all-zeros point of \(\{ 0,1\} ^n\), summing these characters evaluated at \(\mathbf{0}\) over all \(2^n\) subsets of \([n]\) gives

the number of points of the Boolean hypercube.

Fix \(n\in \mathbb {N}\) and a point \(x\in \{ 0,1\} ^n\), and for each subset \(S\subseteq [n]\) let \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) be the Walsh–Fourier character. If \(x\) is not the all-zeros point, then

the sum ranging over all \(2^n\) subsets of \([n]\).

For every \(n \in \mathbb {N}\), the Walsh character \(\chi _\emptyset \) associated to the empty subset of \([n]\) has uniform expectation equal to one:

Let \(n\) be a natural number and let \(S \subseteq [n]\) be a nonempty set of coordinates. Then the Walsh–Fourier character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) has vanishing uniform expectation over the Boolean hypercube \(\{ 0,1\} ^n\):

Let \(n\) be a natural number and let \(S \subseteq [n]\). Then the Walsh–Fourier character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) satisfies

where the inner product is the uniform expectation of the pointwise product.

Fix \(n \in \mathbb {N}\), and let \(S, T \subseteq [n]\) be two distinct subsets. Then the Walsh–Fourier characters \(\chi _S\) and \(\chi _T\) are orthogonal with respect to the uniform inner product on \(\{ 0,1\} ^n\):

For every subset \(S \subseteq [n]\), the Fourier coefficient of the Walsh character \(\chi _S\) at the same set \(S\) equals \(1\); that is,

Let \(S, T \subseteq [n]\) be distinct subsets of coordinates. Then the Fourier coefficient of the Walsh character \(\chi _S : \{ 0,1\} ^n \to \mathbb {R}\) at \(T\) vanishes:

Let \(n\) be a natural number and let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function of arity \(n\). Then the two forms of the uniform expectation of \(f\) coincide, namely

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function of arity \(n\), and let \(S \subseteq [n]\). Then the two definitions of the Fourier–Walsh coefficient \(\hat f(S)\) coincide: both are equal to the \(L^2\) inner product of \(f\) with the Walsh character \(\chi _S\),

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function and let \(x \in \{ 0,1\} ^n\). Then \(f\) agrees pointwise with the sum of its Walsh characters weighted by its Fourier coefficients:

where the sum ranges over all subsets \(S\) of \([n]\), \(\hat f(S) = \langle f, \chi _S\rangle \) is the Fourier coefficient of \(f\) at \(S\), and \(\chi _S\) is the Walsh character of \(S\).

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a real-valued function on the Boolean hypercube, and for each subset \(S \subseteq [n]\) let \(\hat f(S) = \langle f, \chi _S\rangle \) be its Fourier coefficient, where the inner product and expectation are taken with respect to the uniform measure. Then the sum of the squared Fourier coefficients equals the squared \(L^2\) norm of \(f\):

Let \(n\) be a natural number, and let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions. Then for every subset \(S \subseteq [n]\), the Fourier coefficient of the convolution \(f * g\) at \(S\) equals the product of the Fourier coefficients of \(f\) and \(g\) at \(S\):

Fix a natural number \(n\), and let \(S \subseteq \{ 1,\dots ,n\} \) be a set of coordinates. For every point \(x\) of the Boolean hypercube \(\{ 0,1\} ^n\), the Walsh character \(\chi _S\) satisfies

Fix \(n \ge 0\), and for each subset \(S \subseteq [n]\) let \(\chi _S : \{ 0,1\} ^n \to \mathbb {R}\) be the Walsh character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\). Writing \(\mathbf{0}\) for the all-zeros point of \(\{ 0,1\} ^n\), the map sending each \(S\) to \(\chi _S(\mathbf{0})\) is the constant function equal to \(1\):

Let \(x \in \{ 0,1\} ^n\) be a point of the Boolean hypercube that differs from the all-zeros point \(\mathbf{0}\), and suppose \(i\) is a coordinate at which \(x_i = \mathtt{true}\). Then summing the Walsh–Fourier characters over all subsets \(S \subseteq [n]\), evaluated at \(x\), gives the same value as summing their negations:

Let \(n\) be a natural number and let \(S \subseteq [n]\) be a nonempty set of coordinates. Then the uniform expectation of the Walsh character \(\chi _S\) over the Boolean hypercube factorises as a product over the coordinates in \(S\):

where \(\mathrm{BoolToPM1}\) sends \(\mathtt{false}\) to \(1\) and \(\mathtt{true}\) to \(-1\).

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a real-valued function on the Boolean hypercube, and equip such functions with the uniform-measure inner product \(\langle g, h \rangle = 2^{-n}\sum _{x \in \{ 0,1\} ^n} g(x)\, h(x)\). Then the squared \(L^2\) norm of \(f\) equals the inner product of \(f\) with itself:

Let \(n\) be a natural number, let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, and let \(S \subseteq [n]\) with associated Walsh character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\). Writing \(x \oplus y\) for the componentwise XOR of \(x, y \in \{ 0,1\} ^n\), the following identity holds:

Let \(S \subseteq [n]\), let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, and suppose the interchange-of-summation identity

holds, where all sums range over \(\{ 0,1\} ^n\) and \(\oplus \) is componentwise XOR. Then for all \(x, y \in \{ 0,1\} ^n\),

where \(\chi _S\) is the Walsh–Fourier character of \(S\); that is, \(\chi _S\) is a character of the group \((\mathbb {F}_2)^n\).

Let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, let \(S \subseteq [n]\), and write \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) for the associated Walsh character, where \(\oplus \) denotes componentwise XOR. Suppose the order of summation may be interchanged in the double sum

Then for every \(y \in \{ 0,1\} ^n\), translating the argument of \(g\) by \(y\) multiplies the character-weighted sum by the factor \(\chi _S(y)\):