For all \(x, y \in \{ 0,1\} ^n\), the componentwise XOR is symmetric: the vectors with \(i\)-th coordinates \(x_i \oplus y_i\) and \(y_i \oplus x_i\) coincide, so \(x \oplus y = y \oplus x\).

For every \(x \in \{ 0,1\} ^n\), the componentwise XOR of \(x\) with the all-zeros vector \(\mathbf{0}\) equals \(x\); that is, \(x \oplus \mathbf{0} = x\). Equivalently, \(\mathbf{0}\) is a right identity for the group operation on \((\mathbb {F}_2)^n\).

For every \(x \in \{ 0,1\} ^n\), the componentwise XOR of \(x\) with itself is the all-zeros vector: \(x \oplus x = \mathbf{0}\).

For all \(x, y, z \in \{ 0,1\} ^n\), the componentwise XOR is associative: writing \(x \oplus y\) for the vector with \(i\)th coordinate \(x_i \oplus y_i\),

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function and let \(x \in \{ 0,1\} ^n\). With no direction vectors supplied, the order-\(0\) Gowers product equals the value of \(f\) at \(x\):

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function, let \(k \ge 0\), let \(x \in \{ 0,1\} ^n\) be a base point, and let \(h_1, \ldots , h_{k+1} \in \{ 0,1\} ^n\) be direction vectors. Then the order-\((k{+}1)\) Gowers product splits along its last direction as

where \(x \oplus h_{k+1}\) denotes the componentwise XOR.

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function, and let \(x, h \in \{ 0,1\} ^n\). Then the multiplicative derivative of \(f\) in direction \(h\), evaluated at \(x\), coincides with the order-\(1\) Gowers product of \(f\) at base point \(x\) with the single direction vector \(h\); that is,

where \(\oplus \) denotes componentwise XOR.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and let \(F : \{ 0,1\} ^n \to \mathbb {R}\), \(F(x) = (-1)^{f(x)}\), be its \(\pm 1\) lift. Then for every order \(k \ge 0\), every base point \(x \in \{ 0,1\} ^n\), and all direction vectors \(h_1, \ldots , h_k \in \{ 0,1\} ^n\), the order-\(k\) Gowers product satisfies

Fix natural numbers \(n\) and \(k\), and let \(\{ 0,1\} ^n\) denote the Boolean hypercube of dimension \(n\). The set of \(k\)-tuples of points of \(\{ 0,1\} ^n\), that is \(\left(\{ 0,1\} ^n\right)^k\), has exactly \(2^{nk}\) elements.

For any constant \(c \in \mathbb {R}\) and any \(k\), the uniform average over \(k\) points \(h_1,\ldots ,h_k\) of the Boolean hypercube \(\{ 0,1\} ^n\) of the constant function equal to \(c\) is itself \(c\):

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\), and recall that \(f\) has degree \(\le d\) when all of its \((d{+}1)\)-fold multiplicative derivatives vanish, i.e. the Gowers product \(\mathrm{GP}(f, d{+}1, x, h_1,\ldots ,h_{d+1}) = 1\) for every base point \(x \in \{ 0,1\} ^n\) and all directions \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\). If \(f\) has degree \(\le d\), then \(f\) also has degree \(\le d+1\); that is, \(\mathrm{GP}(f, d{+}2, x, h_1,\ldots ,h_{d+2}) = 1\) for every \(x\) and all directions \(h_1,\ldots ,h_{d+2} \in \{ 0,1\} ^n\).

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

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be linear, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) denotes componentwise XOR. Then \(f\) has degree \(\le 1\): its \(\pm 1\) lift \((-1)^f\) has vanishing multiplicative derivatives of order two, so that for every base point \(x \in \{ 0,1\} ^n\) and every pair of directions \(h_1, h_2 \in \{ 0,1\} ^n\) the order-\(2\) Gowers product of \((-1)^f\) over the combinatorial square \(x + \operatorname {span}\{ h_1, h_2\} \) equals \(1\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function of degree at most \(1\); that is, its \(\pm 1\) lift \(x \mapsto (-1)^{f(x)}\) has degree at most \(1\), meaning every second-order multiplicative derivative is trivial: for all \(x, h_1, h_2 \in \{ 0,1\} ^n\) the order-\(2\) Gowers product of \((-1)^f\) at \(x\) in directions \(h_1, h_2\) equals \(1\). Then \(f\) is affine over \(\mathbb {F}_2\): either \(f\) itself is linear, satisfying \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y\), or its pointwise negation \(x \mapsto \lnot f(x)\) is linear.

Fix an ambient dimension \(n\) and a degree \(d\). Every Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) of degree at most \(d\) also has degree at most \(d+1\); equivalently, the Reed–Muller code \(\mathrm{RM}(d,n)\) is contained in \(\mathrm{RM}(d+1,n)\).

Fix \(n, d \in \mathbb {N}\). The identically-false function \(\mathbf{0} : \{ 0,1\} ^n \to \{ 0,1\} \), sending every input to \(0\), lies in the Reed–Muller code \(\mathrm{RM}(d, n)\); that is, it has degree at most \(d\).

For every \(n\) and every degree bound \(d\), the constant function \(\mathbf{1} : \{ 0,1\} ^n \to \{ 0,1\} \) taking the value \(1\) at every point lies in the Reed–Muller code \(\mathrm{RM}(d, n)\); that is, it has degree \(\le d\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a linear Boolean function, meaning that \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) denotes componentwise XOR. Then \(f\) belongs to the first-order Reed–Muller code \(\mathrm{RM}(1, n)\); that is, \(f\) has degree at most \(1\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function lying in the Reed–Muller code \(\mathrm{RM}(1,n)\), that is, a function of degree at most \(1\). Then \(f\) is affine: either \(f\) is \(\mathbb {F}_2\)-linear, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), or the complementary function \(x \mapsto \lnot f(x)\) is \(\mathbb {F}_2\)-linear.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function and let \(d\) be a nonnegative integer, and write \((-1)^f : \{ 0,1\} ^n \to \{ \pm 1\} \) for its sign lift. Then the \(2^{d+1}\)-th power of the order-\((d+1)\) Gowers uniformity norm of \((-1)^f\) equals \(1\),

if and only if \((-1)^f\) has degree at most \(d\), meaning that for every base point \(x \in \{ 0,1\} ^n\) and all direction vectors \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\) the \((d+1)\)-fold Gowers product \(\mathrm{GP}\big((-1)^f, d{+}1, x, h_1,\ldots ,h_{d+1}\big)\) equals \(1\).

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function, and write \(x \oplus y\) for the componentwise XOR of \(x, y \in \{ 0,1\} ^n\). Then the fourth power of the second Gowers uniformity norm of \(f\) equals the squared \(L^2\) norm of the self-convolution \(f * f\), where \((f * f)(x) = \mathbb {E}_{y}[f(y)\, f(x \oplus y)]\); that is,

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function, with Gowers uniformity norm \(\| f\| _{U^2}\) and Fourier coefficients \(\hat f(S) = \mathbb {E}_x[f(x)\chi _S(x)]\) indexed by the subsets \(S \subseteq [n]\). Then

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function on the hypercube, and let \(g = (-1)^f\) be its \(\pm 1\) lift, the real-valued function \(g(x) = (-1)^{f(x)} \in \{ \pm 1\} \). Then for every \(k \in \mathbb {N}\), the \(k\)-th Gowers uniformity norm of \(g\) (in power form) satisfies

Let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, fix an order \(k \ge 0\), a base point \(x \in \{ 0,1\} ^n\), and direction vectors \(h_1, \ldots , h_k \in \{ 0,1\} ^n\), and write \(f \cdot g\) for the pointwise product \((f \cdot g)(y) = f(y)\, g(y)\). Then the order-\(k\) Gowers product of the product function equals the product of the two Gowers products:

Let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions, and suppose \(g\) has degree \(\le d\), meaning that for every base point \(y \in \{ 0,1\} ^n\) and all direction vectors \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\) one has \(\mathrm{GP}(g, d{+}1, y, h_1,\ldots ,h_{d+1}) = 1\). Then for every base point \(x \in \{ 0,1\} ^n\) and all directions \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\), the order-\((d{+}1)\) Gowers product of the pointwise product \(f \cdot g\) agrees with that of \(f\) alone:

Fix \(n, d \in \mathbb {N}\) and let \(f, g : \{ 0,1\} ^n \to \mathbb {R}\) be Boolean functions. If \(g\) has degree \(\le d\)—that is, every \((d{+}1)\)-fold multiplicative derivative of \(g\) equals \(1\)—then multiplying by \(g\) leaves the \((d{+}1)\)-st Gowers uniformity norm unchanged: writing \(f \cdot g\) for the pointwise product \((f \cdot g)(x) = f(x)\, g(x)\),

Fix \(n\) and an integer \(d \ge 0\), and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function with \(\pm 1\) lift \((-1)^f : \{ 0,1\} ^n \to \{ \pm 1\} \). Then the probability that the \((d+1)\)-fold derivative low-degree test accepts \(f\) is

where \(\| (-1)^f\| _{U^{d+1}}^{2^{d+1}}\) is the \((d+1)\)-st Gowers uniformity norm of the lift raised to the power \(2^{d+1}\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function of degree at most \(d\), meaning that its \(\pm 1\) lift \((-1)^f\) has every \((d{+}1)\)-fold Gowers product equal to \(1\): for all base points \(x\) and all direction vectors \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\), one has \(\mathrm{GP}\bigl((-1)^f, d{+}1, x, h_1,\ldots ,h_{d+1}\bigr) = 1\). Then the \((d{+}1)\)-fold derivative test accepts \(f\) with probability exactly \(1\); that is,

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function that does not have degree at most \(d\), meaning that its \(\pm 1\) lift \((-1)^f\) has at least one nonvanishing \((d{+}1)\)-fold multiplicative derivative: there exist a base point \(x\) and directions \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\) with \(\mathrm{GP}\! \left((-1)^f,\, d{+}1,\, x,\, h_1,\ldots ,h_{d+1}\right) \neq 1\). Then the \((d{+}1)\)-fold derivative test accepts \(f\) with probability strictly less than \(1\).

For every subset \(S \subseteq [n]\), the Walsh–Fourier character \(\chi _S\) has degree at most \(1\): every second-order Gowers product of \(\chi _S\) equals \(1\). Explicitly, for all base points \(x \in \{ 0,1\} ^n\) and all direction vectors \(h_1, h_2 \in \{ 0,1\} ^n\),

For every subset \(S \subseteq [n]\), the negated Walsh–Fourier character \(x \mapsto -\chi _S(x)\) on \(\{ 0,1\} ^n\) has degree \(\le 1\): its second-order multiplicative derivatives all equal \(1\). Explicitly, for every base point \(x \in \{ 0,1\} ^n\) and every pair of direction vectors \(h_1, h_2 \in \{ 0,1\} ^n\), the order-\(2\) Gowers product of \(-\chi _S\) satisfies \(\mathrm{GP}(-\chi _S, 2, x, h_1, h_2) = 1\).

For every subset \(S \subseteq [n]\) and every integer \(d \ge 1\), the Walsh–Fourier character \(\chi _S\) has degree \(\le d\): for every base point \(x \in \{ 0,1\} ^n\) and all direction vectors \(h_1, \ldots , h_{d+1} \in \{ 0,1\} ^n\), the \((d{+}1)\)-fold Gowers product satisfies \(\mathrm{GP}(\chi _S,\, d{+}1,\, x,\, h_1, \ldots , h_{d+1}) = 1\).

For every subset \(S \subseteq [n]\) and every integer \(d \ge 1\), the negated Walsh character \(x \mapsto -\chi _S(x)\) has degree \(\le d\). Equivalently, all of its \((d{+}1)\)-fold multiplicative derivatives are trivial: for every base point \(x \in \{ 0,1\} ^n\) and all direction vectors \(h_1,\ldots ,h_{d+1} \in \{ 0,1\} ^n\), the order-\((d{+}1)\) Gowers product satisfies \(\mathrm{GP}(-\chi _S,\, d{+}1,\, x,\, h_1,\ldots ,h_{d+1}) = 1\).

Let \(f:\{ 0,1\} ^n\to \{ 0,1\} \) be a Boolean function, let \(d\ge 1\), and let \(\varepsilon \) satisfy \(0\le \varepsilon \le 1\). Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\); that is, \(\Pr _{x}[f(x)\ne g(x)]\ge \varepsilon \) for every Boolean function \(g:\{ 0,1\} ^n\to \{ 0,1\} \) of degree \(\le d\). Writing \((-1)^f:\{ 0,1\} ^n\to \{ \pm 1\} \) for the \(\pm 1\) lift of \(f\) and \(\widehat{(-1)^f}(S)=\mathbb {E}_x[(-1)^{f(x)}\chi _S(x)]\) for its Fourier coefficient at \(S\), we then have, for every \(S\subseteq [n]\),

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, let \(d \ge 1\), and write \(F = (-1)^f : \{ 0,1\} ^n \to \{ \pm 1\} \) for its \(\pm 1\) lift. Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\); that is, \(0 \le \varepsilon \le 1\) and every Boolean function \(g\) of degree \(\le d\) satisfies \(\Pr _{x}[f(x) \ne g(x)] \ge \varepsilon \). Then for every \(S \subseteq [n]\),

where \(\widehat{F}(S) = \mathbb {E}_x\bigl[F(x)\, \chi _S(x)\bigr]\) is the Fourier coefficient of \(F\) at \(S\); equivalently, \(\widehat{F}(S) \ge 2\varepsilon - 1\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, let \(d \ge 1\), and let \(\varepsilon \) be a real number with \(0 \le \varepsilon \le 1\). Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\), meaning that \(\operatorname{dist}(f,g) \ge \varepsilon \) for every Boolean function \(g\) of degree \(\le d\). Then, writing \(\widehat{(-1)^f}(S)\) for the Fourier coefficient at \(S\) of the \(\pm 1\) lift \(x \mapsto (-1)^{f(x)}\), we have

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be its \(\pm 1\) lift \(g(x) = (-1)^{f(x)}\). Writing \(\hat g(S) = \mathbb {E}[g\, \chi _S]\) for the Fourier coefficient of \(g\) at \(S\), where \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) and the expectation is over \(x\) uniform on \(\{ 0,1\} ^n\), one has

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, let \(d \ge 1\), and let \(\varepsilon \) satisfy \(0 \le \varepsilon \le 1\). Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\); that is, \(\operatorname{dist}(f,g) \ge \varepsilon \) for every Boolean function \(g\) of degree \(\le d\). Then the \(\pm 1\) lift \((-1)^f : \{ 0,1\} ^n \to \{ \pm 1\} \) satisfies

where \(\lVert \, \cdot \, \rVert _{U^2}^{4}\) denotes the second Gowers uniformity norm raised to the fourth power, \(\mathbb {E}_{x}\, \mathbb {E}_{h_1,h_2}\! \bigl[\mathrm{GP}\bigl((-1)^f,2,x,h_1,h_2\bigr)\bigr]\).

For every real number \(\varepsilon \) with \(0 \le \varepsilon \le \tfrac {1}{2}\), the quantity \(1 - 2\varepsilon \) lies in \([0,1]\) and hence is not increased by squaring:

Fix \(n\) and an integer \(d \ge 1\), and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function. If \(f\) is \(\varepsilon \)-far from degree \(\le d\) — that is, \(0 \le \varepsilon \le 1\) and every Boolean function \(g\) of degree \(\le d\) satisfies \(\operatorname{dist}(f,g) \ge \varepsilon \) — then \(\varepsilon \le 1/2\).

Let \(d \ge 1\) and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, and write \(F = (-1)^f\) for its \(\pm 1\) lift. Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\): that is, \(0 \le \varepsilon \le 1\), and every Boolean function \(g\) of degree \(\le d\) satisfies \(\operatorname{dist}(f,g) \ge \varepsilon \), where \(\operatorname{dist}(f,g) = \Pr _{x}[f(x) \ne g(x)]\) over a uniform \(x \in \{ 0,1\} ^n\). Then the second Gowers uniformity norm of \(F\) obeys

Fix a Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \), a real number \(\varepsilon \) with \(0 \le \varepsilon \le 1\), and natural numbers \(d' \le d\). If \(f\) is \(\varepsilon \)-far from degree \(\le d\) — that is, \(\operatorname{dist}(f, g) \ge \varepsilon \) for every Boolean function \(g\) of degree \(\le d\) — then \(f\) is also \(\varepsilon \)-far from degree \(\le d'\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function that is \(\varepsilon \)-far from degree \(\le d\), where \(d \ge 2\); in particular \(0 \le \varepsilon \le 1\). For a shift \(h \in \{ 0,1\} ^n\), write \(\partial _h f\) for the discrete derivative \(\partial _h f(x) = f(x) \oplus f(x \oplus h)\). Then there exists a real number \(\delta \ge \varepsilon \) such that for every \(h \in \{ 0,1\} ^n\) there is a Boolean function \(g : \{ 0,1\} ^n \to \{ 0,1\} \) for which, if \(g\) has degree \(\le d-1\), then \(\operatorname{dist}(\partial _h f, g) \ge \delta \).

Let \(d \ge 1\) and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function that is \(\varepsilon \)-far from degree \(\le d\), meaning \(0 \le \varepsilon \le 1\) and \(\operatorname{dist}(f, g) \ge \varepsilon \) for every Boolean function \(g\) of degree \(\le d\). Then there is a constant \(c \gt 0\) for which the \(\pm 1\) lift \((-1)^{f}\) satisfies

Fix \(d \ge 1\) and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function that is \(\varepsilon \)-far from degree \(\le d\); that is, \(0 \le \varepsilon \le 1\) and every Boolean function \(g\) of degree \(\le d\) satisfies \(\operatorname{dist}(f,g) \ge \varepsilon \). Then the \((d{+}1)\)-fold derivative test accepts \(f\) with probability at most \(1 - \varepsilon \):

where \(x\) and the direction vectors \(h_1,\ldots ,h_{d+1}\) range uniformly over \(\{ 0,1\} ^n\).

Fix a degree bound \(d\) and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function belonging to the Reed–Muller code \(\mathrm{RM}(d,n)\), that is, a function of degree at most \(d\). Then the \((d+1)\)-fold derivative test accepts \(f\) with probability exactly \(1\):

where \(x\) and the direction vectors \(h_1,\ldots ,h_{d+1}\) range uniformly over \(\{ 0,1\} ^n\).

Fix \(d \ge 1\) and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function. Suppose \(f\) is \(\varepsilon \)-far from degree \(\le d\); that is, \(0 \le \varepsilon \le 1\) and \(\operatorname{dist}(f,g) \ge \varepsilon \) for every Boolean function \(g\) of degree \(\le d\). Then the \((d{+}1)\)-fold derivative test accepts \(f\) with probability at most \(1 - \varepsilon \).