For any two Boolean functions \(f, g : \{ 0,1\} ^n \to \mathbb {R}\), the \(L^2\) inner product with respect to the uniform measure is symmetric:

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function of arity \(n\). Then its \(L^2\) inner product with itself is nonnegative:

Let \(n\) be a natural number and let \(f, g, h : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions. With respect to the \(L^2\) inner product under the uniform measure, \(\langle f, g\rangle = 2^{-n}\sum _{x\in \{ 0,1\} ^n} f(x)\, g(x)\), one has

where \(f + g\) denotes the pointwise sum.

Under the sign encoding \(\sigma \colon \mathrm{Bool}\to \{ -1,1\} \), the Boolean value \(\mathrm{false}\) is sent to \(1\); that is, \(\sigma (\mathrm{false}) = 1\).

Under the sign encoding \(\sigma \colon \mathrm{Bool}\to \{ -1,1\} \), which sends the truth value false to \(1\) and true to \(-1\), the truth value true is mapped to \(-1\); that is, \(\sigma (\text{true}) = -1\).

For every Boolean value \(b\), the sign encoding satisfies \(\sigma (b)^2 = 1\).

For every \(b \in \mathrm{Bool}\), the sign encoding \(\sigma (b) \in \{ -1,1\} \) satisfies \(\sigma (b)\cdot \sigma (b) = 1\); that is, \(\sigma (b)^2 = 1\).

Let \(\sigma \colon \mathrm{Bool}\to \{ -1,1\} \) be the sign encoding, so that \(\sigma (\mathrm{false})=1\) and \(\sigma (\mathrm{true})=-1\). Then for every Boolean value \(b\), negating \(b\) flips the sign of its encoding:

The Walsh–Fourier character associated to the empty subset of \([n]\) is the constant function equal to \(1\); that is, \(\chi _\emptyset (x) = 1\) for every point \(x\) of the Boolean hypercube \(\{ 0,1\} ^n\).

Fix a dimension \(n\), a coordinate \(i \in [n]\), and a point \(x\) of the Boolean hypercube \(\{ 0,1\} ^n\). Then the Walsh–Fourier character of the singleton set \(\{ i\} \), evaluated at \(x\), is the sign encoding of the \(i\)-th coordinate of \(x\):

Let \(n\) be a natural number, let \(S \subseteq [n]\), and let \(x \in \{ 0,1\} ^n\) be a point of the Boolean hypercube. Then the Walsh–Fourier character \(\chi _S\) satisfies \(\chi _S(x)^2 = 1\); that is, every character takes values in \(\{ -1, 1\} \).

Let \(n\) be a natural number, and let \(S, T \subseteq [n]\) be disjoint subsets of coordinates. Then for every point \(x\) of the Boolean hypercube \(\{ 0,1\} ^n\), the Walsh–Fourier character of the union factors as the product of the characters of the two sets:

Fix \(n\), and for a subset \(S\subseteq [n]\) let \(\chi _S\colon \{ 0,1\} ^n\to \mathbb {R}\) denote the associated Walsh–Fourier character. Then for all subsets \(S,T\subseteq [n]\) and every point \(x\in \{ 0,1\} ^n\),

where \(S\, \triangle \, T\) is the symmetric difference of \(S\) and \(T\).

Let \(n\) be a natural number, let \(S \subseteq [n]\), and let \(x \in \{ 0,1\} ^n\). Writing \(\lnot x\) for the point obtained by flipping every coordinate of \(x\), the Walsh–Fourier character \(\chi _S\) satisfies

where \(\left\lvert S\right\rvert \) is the number of elements of \(S\).

For each \(n\), the number of subsets \(S \subseteq [n]\) is exactly \(2^n\). Since the Walsh characters \(\chi _S\) are indexed by these subsets, there are precisely \(2^n\) of them, matching the dimension of \(L^2(\{ 0,1\} ^n)\).

Let \(f\colon \{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function. Then its Fourier–Walsh coefficient at the empty frequency equals its expectation under the uniform measure:

Let \(n\) be a natural number and let \(S \subseteq [n]\). Under the uniform measure on the Boolean hypercube \(\{ 0,1\} ^n\), the Walsh–Fourier character \(\chi _S\) satisfies

Fix \(n\), a coordinate \(i \in [n]\), and a set \(S \subseteq [n]\). The influence of coordinate \(i\) on the Walsh–Fourier character \(\chi _S\) is

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function taking values in \(\{ -1, 1\} \), and let \(i\) be one of its \(n\) coordinates. Then the influence of coordinate \(i\) on \(f\) satisfies

where \(x^i\) denotes the point obtained from \(x\) by flipping its \(i\)-th coordinate and the expectation is taken under the uniform measure on \(\{ 0,1\} ^n\).

Let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function on the hypercube of dimension \(n\ge 1\). Then some coordinate carries at least the average influence: there exists an index \(i\) with

where \(I[f]=\sum _{j=1}^{n}\mathrm{Inf}_j[f]\) is the total influence.

For each coordinate \(i \in [n]\), the dictator function on the Boolean hypercube \(\{ 0,1\} ^n\) coincides with the Walsh–Fourier character associated to the singleton set \(\{ i\} \); that is, \(\mathrm{dict}_i = \chi _{\{ i\} }\) as functions \(\{ 0,1\} ^n \to \mathbb {R}\).

For every \(n\), the parity function \(\mathrm{parity}_n(x) = \prod _{i=1}^{n}\sigma (x_i)\) on the Boolean hypercube \(\{ 0,1\} ^n\) coincides, as a Boolean function, with the Walsh–Fourier character \(\chi _{[n]}\) indexed by the full set \([n] = \{ 1,\dots ,n\} \); that is, \(\mathrm{parity}_n = \chi _{[n]}\).

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be an odd Boolean function, meaning \(f(\lnot x) = -f(x)\) for every \(x \in \{ 0,1\} ^n\), where \(\lnot x\) denotes the pointwise negation of \(x\). Then for every subset \(S \subseteq [n]\) of even cardinality, the Fourier–Walsh coefficient of \(f\) at \(S\) vanishes: \(\hat f(S) = 0\).

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a \(\pm 1\)-valued Boolean function, so that \(f(x) \in \{ -1, 1\} \) for every \(x \in \{ 0,1\} ^n\). Then its \(L^2\) inner product with itself, taken with respect to the uniform measure on the cube, equals \(1\):

Let \(f \colon \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function that is \(\pm 1\)-valued, meaning \(f(x) \in \{ -1,1\} \) for every \(x \in \{ 0,1\} ^n\). Then its Fourier–Walsh coefficients satisfy

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

Let \(P\) be a probability measure on the Boolean hypercube \(\{ 0,1\} ^n\) that assigns every singleton the uniform weight \(2^{-n}\). Then for any Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\) and any \(p \in \mathbb {N}\), the \(p\)-th moment of \(f\) under \(P\) equals the uniform expectation of \(f^p\):

For any real numbers \(c_0,\dots ,c_{n-1}\), indexed by \(i \in \mathrm{Fin}\, n\),

where the sum ranges over all subsets \(S\) of the index set (with the empty product equal to \(1\)).

Let \(x, y \in \{ 0,1\} ^n\) be points of the Boolean hypercube. Then the sum of the products of Walsh–Fourier characters over all subsets of \([n]\) satisfies

Let \(\sigma \colon \mathrm{Bool}\to \{ -1,1\} \) be the sign encoding, sending the value *false* to \(1\) and the value *true* to \(-1\). Summing \(\sigma \) over the two Boolean values yields

Let \(n\) be a natural number and let \(S \subseteq [n]\). Summing the Walsh–Fourier character \(\chi _S\) over the entire Boolean hypercube \(\{ 0,1\} ^n\) gives

For a point \(x\) in the Boolean hypercube \(\{ 0,1\} ^n\) and a coordinate \(i\), flipping the \(i\)-th coordinate of \(x\) twice returns the original point: \((x^i)^i = x\).

Let \(x\in \{ 0,1\} ^n\) be a point of the Boolean hypercube, and let \(i,j\) be coordinate indices with \(i\ne j\). Writing \(x^i\) for the point obtained from \(x\) by flipping the \(i\)-th coordinate, we have \((x^i)_j = x_j\); that is, flipping coordinate \(i\) leaves coordinate \(j\) unchanged.

Fix a subset \(S\subseteq [n]\) of coordinates. For every point \(x\) of the Boolean hypercube \(\{ 0,1\} ^n\) and every coordinate \(i\in [n]\), the value of the Walsh–Fourier character \(\chi _S\) at the point \(x^i\) obtained by flipping the \(i\)-th coordinate of \(x\) is

Fix an arity \(n\) and a coordinate direction \(i \in \{ 1, \dots , n\} \). For any two Boolean functions \(f, g : \{ 0,1\} ^n \to \mathbb {R}\), the discrete derivative in direction \(i\) satisfies

that is, the operator \(D_i\) is additive.

Fix an arity \(n\) and a coordinate direction \(i \in \{ 1,\dots ,n\} \). For every scalar \(c \in \mathbb {R}\) and every Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), the discrete derivative in direction \(i\) commutes with scalar multiplication:

that is, scaling \(f\) by \(c\) scales its discrete derivative by the same factor.

Fix \(n \in \mathbb {N}\) and a coordinate direction \(i \in \{ 1,\dots ,n\} \), and write \(E_i\) for the expectation operator in direction \(i\), which sends a Boolean function \(h : \{ 0,1\} ^n \to \mathbb {R}\) to the function \((E_i h)(x) = \tfrac {1}{2}\bigl(h(x^{i\mapsto 0}) + h(x^{i\mapsto 1})\bigr)\). Then \(E_i\) is additive: for all Boolean functions \(f, g : \{ 0,1\} ^n \to \mathbb {R}\),

Let \(n\) be an arity and let \(i\) be one of its coordinates. For every scalar \(c \in \mathbb {R}\) and every Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), applying the expectation operator in direction \(i\) to the scaled function \(c\, f\) yields \(c\) times the expectation operator applied to \(f\):

Fix a dimension \(n\) and let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions. For any real number \(\rho \), the noise operator \(T_\rho \) is self-adjoint with respect to the \(L^2\) inner product induced by the uniform measure on \(\{ 0,1\} ^n\):