For all \(x, y \in \{ 0,1\} ^n\), coordinate-wise XOR satisfies \(x \oplus y = y \oplus x\).

For all \(x \in \{ 0,1\} ^n\), we have \(x \oplus \mathbf{0} = x\), where \(\mathbf{0}\) denotes the all-zero vector.

For all \(x \in \{ 0,1\} ^n\), we have \(x \oplus x = \mathbf{0}\), so every element is its own inverse under XOR.

For all \(x, y, z \in \{ 0,1\} ^n\), coordinate-wise XOR is associative: \((x \oplus y) \oplus z = x \oplus (y \oplus z)\).

For any \(f : \{ 0,1\} ^n \to \mathbb {R}\) and \(x \in \{ 0,1\} ^n\), the order-\(0\) Gowers product satisfies \(\mathrm{GP}(f, 0, x, \emptyset ) = f(x)\).

For any \(f\), \(k \ge 0\), \(x\), and direction vectors \(h_1,\ldots ,h_{k+1}\), the Gowers product unfolds as

For \(f : \{ 0,1\} ^n \to \mathbb {R}\), \(x, h \in \{ 0,1\} ^n\), \((\Delta _h f)(x) = \mathrm{GP}(f, 1, x, h)\).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) and \(F = (-1)^f\) is its \(\pm 1\) lift, then for every \(k\), \(x\), and \(h_1,\ldots ,h_k\), \(\mathrm{GP}(F, k, x, h_1,\ldots ,h_k) \in \{ 1, -1\} \).

The number of \(k\)-tuples of vectors in \(\{ 0,1\} ^n\) is \(|(\{ 0,1\} ^n)^k| = 2^{nk}\).

For any constant \(c \in \mathbb {R}\), \(\mathbb {E}_{h_1,\ldots ,h_k}[c] = c\).

If \(f\) has degree \(\le d\), then \(f\) also has degree \(\le d+1\).

A Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) has degree \(\le 0\) if and only if it is constant, i.e. \(f(x) = f(y)\) for all \(x, y \in \{ 0,1\} ^n\).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is \(\mathbb {F}_2\)-linear (i.e. \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x,y\)), then \(f\) has degree \(\le 1\).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) has degree \(\le 1\), then \(f\) is affine: either \(f\) is \(\mathbb {F}_2\)-linear or \(\lnot f\) (bitwise negation) is \(\mathbb {F}_2\)-linear.

\(\mathrm{RM}(d, n) \subseteq \mathrm{RM}(d+1, n)\) for every \(d\) and \(n\).

The constant-false function \(\mathbf{0} : \{ 0,1\} ^n \to \{ 0,1\} \) belongs to \(\mathrm{RM}(d, n)\) for every \(d\).

The constant-true function \(\mathbf{1} : \{ 0,1\} ^n \to \{ 0,1\} \) belongs to \(\mathrm{RM}(d, n)\) for every \(d\).

Every \(\mathbb {F}_2\)-linear function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) belongs to \(\mathrm{RM}(1, n)\).

Every \(f \in \mathrm{RM}(1, n)\) is affine: either \(f\) is \(\mathbb {F}_2\)-linear or \(\lnot f\) is \(\mathbb {F}_2\)-linear.

For a Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) and \(d \ge 0\),

For \(f : \{ 0,1\} ^n \to \mathbb {R}\), \(\| f\| _{U^2}^4 = \| f * f\| _2^2\), where \(f * f\) denotes the convolution of \(f\) with itself.

For \(f : \{ 0,1\} ^n \to \mathbb {R}\),

For every Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) and every \(k \ge 0\), \(\| (-1)^f\| _{U^k}^{2^k} \le 1\).

For \(f, g : \{ 0,1\} ^n \to \mathbb {R}\), \(\mathrm{GP}(f \cdot g, k, x, h_1,\ldots ,h_k) = \mathrm{GP}(f, k, x, h_1,\ldots ,h_k) \cdot \mathrm{GP}(g, k, x, h_1,\ldots ,h_k)\).

If \(g\) has degree \(\le d\), then for any \(f\), \(\mathrm{GP}(f \cdot g, d{+}1, x, h_1,\ldots ,h_{d+1}) = \mathrm{GP}(f, d{+}1, x, h_1,\ldots ,h_{d+1})\): multiplying by a low-degree function does not change the \((d{+}1)\)-fold Gowers product.

If \(g\) has degree \(\le d\), then \(\| f \cdot g\| _{U^{d+1}}^{2^{d+1}} = \| f\| _{U^{d+1}}^{2^{d+1}}\).

For every Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \),

If \(\deg (f) \le d\), then the degree-\(d\) test accepts \(f\) with probability \(1\).

If \(\deg (f) \gt d\), then the degree-\(d\) test accepts \(f\) with probability strictly less than \(1\).

For every \(S \subseteq [n]\), the Fourier character \(\chi _S\) has degree \(\le 1\).

For every \(S \subseteq [n]\), the function \(-\chi _S\) has degree \(\le 1\).

For every \(S \subseteq [n]\) and \(d \ge 1\), the character \(\chi _S\) has degree \(\le d\).

For every \(S \subseteq [n]\) and \(d \ge 1\), the function \(-\chi _S\) has degree \(\le d\).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from every degree-\(\le d\) Boolean function, then for every \(S \subseteq [n]\), \(\hat{f}(S) \le 1 - 2\varepsilon \).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then for every \(S \subseteq [n]\), \(-\hat{f}(S) \le 1 - 2\varepsilon \) (equivalently, \(\hat{f}(S) \ge -(1-2\varepsilon )\)).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then for every \(S \subseteq [n]\), \(|\hat{f}(S)| \le 1 - 2\varepsilon \).

For every Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \), \(\sum _{S \subseteq [n]} \hat{f}(S)^2 = 1\).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then \(\| (-1)^f\| _{U^2}^4 \le (1 - 2\varepsilon )^2\).

For \(\varepsilon \in [0, \tfrac {1}{2}]\), \((1 - 2\varepsilon )^2 \le 1 - 2\varepsilon \).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then \(\varepsilon \le 1/2\).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then \(\| (-1)^f\| _{U^2}^4 \le 1 - 2\varepsilon \).

If \(d' \le d\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then \(f\) is also \(\varepsilon \)-far from degree \(\le d'\).

If \(d \ge 2\) and \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is \(\varepsilon \)-far from degree \(\le d\), then there exists \(\delta \ge \varepsilon \) such that for every \(h \in \{ 0,1\} ^n\) there exists a Boolean function \(g\) of degree \(\le d{-}1\) with \(\operatorname{dist}(\Delta _h f, g) \ge \delta \). Intuitively, the multiplicative derivative \(\Delta _h f(x) = f(x) \oplus f(x \oplus h)\) is on average far from degree \(\le d{-}1\).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from degree \(\le d\), then there exists a constant \(c \gt 0\) such that \(\| (-1)^f\| _{U^{d+1}}^{2^{d+1}} \le 1 - c\varepsilon \). For \(d = 1\) one may take \(c = 2\); the case \(d \ge 2\) follows by induction using the derivative distance lemma (BKSSZ 2010).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from every degree-\(\le d\) function, then \(\Pr [\text{degree test accepts } f] \le 1 - \varepsilon \).

Every codeword \(f \in \mathrm{RM}(d, n)\) is accepted by the degree-\(d\) test with probability \(1\).

If \(d \ge 1\) and \(f\) is \(\varepsilon \)-far from every codeword of \(\mathrm{RM}(d, n)\), then the Reed–Muller test accepts \(f\) with probability at most \(1 - \varepsilon \), i.e. it rejects with probability at least \(\varepsilon \).