Let \(f\colon \{ 0,1\} ^{n+1}\to \mathbb {R}\), and let \(x\) be a point of the \(n\)-dimensional Boolean hypercube. Then the restriction of \(f\) obtained by fixing its last coordinate to \(\mathrm{false}\) equals the sum of the average and the half-difference of \(f\) over that coordinate:

Let \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\) be a Boolean function on \(n+1\) variables. For a bit \(b\), write \(f_b : \{ 0,1\} ^n \to \mathbb {R}\) for the restriction \(x \mapsto f(x,b)\) that fixes the last coordinate to \(b\), and let its average and half-difference over the last coordinate be the functions \(\tfrac 12(f_0 + f_1)\) and \(\tfrac 12(f_0 - f_1)\). Then for every point \(x \in \{ 0,1\} ^n\), the restriction fixing the last coordinate to \(\mathrm{true}\) equals the average minus the half-difference at that point:

Let \(n\) be a natural number and let \(\varphi \colon \{ 0,1\} ^{n+1} \to \mathbb {R}\) be a real-valued function on the Boolean hypercube of dimension \(n+1\). Then the sum of \(\varphi \) over all points of the cube splits according to the value of the final coordinate:

where \((y,b)\) denotes the point of \(\{ 0,1\} ^{n+1}\) obtained by appending the bit \(b\) to \(y \in \{ 0,1\} ^{n}\) as its last coordinate.

For every natural number \(n\), the uniform weight \(2^{-n}\) assigned to each point of \(\{ 0,1\} ^n\) satisfies

so that the uniform weight on the cube of one higher dimension is half the uniform weight on the original cube.

Let \(f\colon \{ 0,1\} ^{n+1}\to \mathbb {R}\), let \(g\) be the average of \(f\) over its last coordinate — the Boolean function of arity \(n\) given by \(g(x) = \tfrac 12\bigl(f(x,\text{false}) + f(x,\text{true})\bigr)\) — and let \(S \subseteq [n]\) be a set of coordinates among the first \(n\). Write \(\iota \colon [n] \hookrightarrow [n+1]\) for the inclusion sending each of the first \(n\) coordinates to itself and omitting the last, so that \(\iota (S)\) is \(S\) viewed as a subset of \([n+1]\) that avoids the coordinate \(n+1\). Then the Fourier–Walsh coefficient of \(g\) at frequency \(S\) equals the Fourier–Walsh coefficient of \(f\) at frequency \(\iota (S)\):

Let \(f\colon \{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function on \(n+1\) variables, and let \(g\colon \{ 0,1\} ^{n}\to \mathbb {R}\) be its half-difference over the last coordinate, given by \(g(x)=\tfrac 12\bigl(f(x,0)-f(x,1)\bigr)\). For every frequency set \(S\subseteq \{ 1,\dots ,n\} \), the Fourier–Walsh coefficient of \(g\) at \(S\) equals the Fourier–Walsh coefficient of \(f\) at the frequency set obtained by regarding \(S\) as a subset of the first \(n\) coordinates of \(\{ 1,\dots ,n+1\} \) and adjoining the last coordinate:

Let \(\varphi : \{ 0,1\} ^{n+1} \to \mathbb {R}\) be a Boolean function on \(n+1\) variables, and for a bit \(b \in \{ 0,1\} \) let \(\varphi _b : \{ 0,1\} ^n \to \mathbb {R}\), \(\varphi _b(x) = \varphi (x, b)\), be its restriction obtained by fixing the last coordinate to \(b\). Then the expectation of \(\varphi \) under the uniform measure on \(\{ 0,1\} ^{n+1}\) is the average of the expectations of its two restrictions:

For all real numbers \(a\) and \(b\), the sum of the fourth powers of \(a+b\) and \(a-b\) satisfies

For all real numbers \(a\) and \(b\), the identity

holds.

Let \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\) be a Boolean function on \(n+1\) variables, and let \(g\) and \(h\) be the average and the half-difference of \(f\) over its last coordinate, so that \(g(x) = \tfrac 12\bigl(f(x,0) + f(x,1)\bigr)\) and \(h(x) = \tfrac 12\bigl(f(x,0) - f(x,1)\bigr)\) for \(x \in \{ 0,1\} ^n\). Then, with all expectations taken under the uniform measure, the fourth moment of \(f\) decomposes as

Let \(f : \{ 0,1\} ^{n+1} \to \mathbb {R}\) be a Boolean function on \(n+1\) variables. Define its average and half-difference over the last coordinate as the functions on \(n\) variables

Then, with the expectation on the left taken under the uniform measure on \(\{ 0,1\} ^{n+1}\) and those on the right under the uniform measure on \(\{ 0,1\} ^n\), the second moment of \(f\) decomposes as

Let \(g, h : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, and let \(\mathbb {E}[\, \cdot \, ]\) denote the expectation under the uniform measure on the hypercube \(\{ 0,1\} ^n\). Then

For every Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\), the expectation of \(f^2\) under the uniform measure is nonnegative: \(0 \le \mathbb {E}[f^2]\), where \(\mathbb {E}[f^2] = 2^{-n}\sum _{x\in \{ 0,1\} ^n} f(x)^2\).

For any two Boolean functions \(g, h : \{ 0,1\} ^n \to \mathbb {R}\), the expectation of the product of their squares under the uniform measure is nonnegative:

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function on the Boolean hypercube. Then its fourth moment under the uniform measure is nonnegative:

Let \(f\colon \{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function on \(n+1\) variables, and suppose \(f\) has degree at most \(k\); that is, every set \(S\) with nonzero Fourier coefficient \(\hat f(S)\ne 0\) satisfies \(\left\lvert S\right\rvert \le k\). Form the average of \(f\) over its last coordinate, the function on \(n\) variables obtained by fixing that coordinate to each of its two values and averaging,

Then this averaged function also has degree at most \(k\): each set \(S\) with a nonzero Fourier coefficient of the average satisfies \(\left\lvert S\right\rvert \le k\).

Let \(f\colon \{ 0,1\} ^{n+1}\to \mathbb {R}\) be a Boolean function of degree at most \(k\), meaning that every frequency set \(S\) with nonzero Fourier–Walsh coefficient \(\hat f(S)\ne 0\) satisfies \(\left\lvert S\right\rvert \le k\). Write \(f_0\) and \(f_1\) for the two restrictions of \(f\) to \(\{ 0,1\} ^{n}\) obtained by fixing its last coordinate to \(0\) and to \(1\) respectively, and let \(g=\tfrac 12(f_0-f_1)\) be the half-difference of \(f\) over that coordinate. Then \(g\) is a Boolean function on \(\{ 0,1\} ^{n}\) of degree at most \(k-1\), with \(k-1\) interpreted as \(0\) when \(k=0\).