Fix a prime \(p\), and let \((P_s)_{s \in S}\) be a family of polynomials in \((\mathbb {Z}/p)[X_1,\dots ,X_n]\) indexed by a nonempty finite set \(S\) of seeds, let \(f : \{ 0,1\} ^n \to \mathbb {Z}/p\) be a target function, and let \(\ell \) and \(B\) be natural numbers. For a Boolean input \(x \in \{ 0,1\} ^n\), write \(\bar{x} \in (\mathbb {Z}/p)^n\) for its coordinatewise image under the inclusion \(\{ 0,1\} \hookrightarrow \mathbb {Z}/p\). Suppose that for every Boolean input \(x\),

Then there exists a seed \(s \in S\) for which the number of Boolean inputs \(x \in \{ 0,1\} ^n\) with \(P_s(\bar{x}) \neq f(x)\), multiplied by \(2^{\ell }\), is at most \(B \cdot 2^{n}\).

Let \(p\) be a prime, let \(n\in \mathbb {N}\), and let \(F\) be a feedforward circuit over the alphabet \(\{ 0,1\} \) with input type \(\mathrm{Fin}\, n\), a unique output node, and finitely many nodes in each layer, every one of whose gates is drawn from the \(\mathrm{AC}^0[p]\) gate set (the identity, NOT, and unbounded fan-in AND gates, together with the unbounded \(\mathrm{MOD}_p\) gates). Write \(g\colon \{ 0,1\} ^n\to \mathbb {Z}/p\) for the function computed by \(F\), namely its single output value cast into \(\mathbb {Z}/p\). Then for every \(\ell \in \mathbb {N}\) there exists a polynomial \(P\in (\mathbb {Z}/p)[X_1,\dots ,X_n]\) of total degree at most \(\bigl((p-1)\ell \bigr)^{\operatorname {depth}(F)}\) such that the number \(b\) of Boolean inputs \(x\in \{ 0,1\} ^n\) at which \(P\), evaluated at the point of \((\mathbb {Z}/p)^n\) whose \(i\)-th coordinate is the image of \(x_i\) in \(\mathbb {Z}/p\), differs from \(g(x)\) satisfies

where \(\operatorname {size}(F)\) is the number of non-input nodes of \(F\).

Let \(p\) and \(q\) be primes, and let \(F\) be a feedforward circuit over the alphabet \(\{ 0,1\} \) with input coordinates indexed by \(\mathrm{Fin}\, n\), finitely many nodes in each layer, and a single output node. Suppose every gate of \(F\) belongs to the \(\mathrm{AC}^0[p]\) gate set (identity, NOT, unbounded fan-in AND, and unbounded \(\mathrm{MOD}_p\) gates of every arity), and that \(F\) computes the \(\mathrm{MOD}_q\) function on every Boolean input \(x \in \{ 0,1\} ^n\). Let \(\ell , E \in \mathbb {N}\), and suppose the low-degree bad-count lower bound holds for \(\mathrm{MOD}_q\) (viewed as a function into \(\mathbb {Z}/p\)) with degree budget \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\) and count \(E\); that is, every polynomial in \((\mathbb {Z}/p)[X_1,\dots ,X_n]\) of total degree at most \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\) disagrees with \(\mathrm{MOD}_q\) on at least \(E\) points of the Boolean cube. Then

where \(\left\lvert F\right\rvert \) is the number of non-input nodes of \(F\).

Let \(p\) and \(q\) be primes, and let \(F\) be a layered feedforward circuit over the Boolean alphabet with input coordinates \(\mathrm{Fin}\, n\) and a single output, each of whose layers is finite. Suppose \(F\) uses only \(\mathrm{AC}^0[p]\) gates (the identity gate, the NOT gate, unbounded fan-in AND gates, and unbounded \(\mathrm{MOD}_p\) gates), and that \(F\) computes the \(\mathrm{MOD}_q\) function on its \(n\) Boolean inputs. Fix \(\ell , \delta \in \mathbb {N}\), and assume the relative low-degree bad-count bound: every polynomial \(P \in (\mathbb {Z}/p)[X_1,\dots ,X_n]\) of total degree at most \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\) disagrees with the \(\mathrm{MOD}_q\) target (viewed in \(\mathbb {Z}/p\)) on at least \(\delta \cdot 2^{n}\) of the \(2^{n}\) Boolean inputs. Then the size of \(F\) satisfies \(\delta \cdot 2^{\ell } \le \left\lvert F\right\rvert \).

Let \(p\) and \(q\) be distinct prime numbers, and let \(\mathbb {F}_{p^{q-1}}\) denote the finite field with \(p^{q-1}\) elements. Then the multiplicative group \(\mathbb {F}_{p^{q-1}}^{\times }\) contains a unit \(u\) whose order is exactly \(q\).

Let \(p\) and \(q\) be distinct primes. Then the field \(\mathbb {F}_{p^{q-1}}\) contains an element \(\omega \neq 1\) satisfying \(\omega ^{q} = 1\); that is, a nontrivial \(q\)-th root of unity.

Let \(K\) be a field, let \(\omega \in K\), and let \(n\) be a natural number. Write \(\{ 1,\omega \} ^n\) for the root cube, the set of vectors \(x = (x_1,\dots ,x_n) \in K^n\) with \(x_i \in \{ 1,\omega \} \) for every \(i\). Then for every function \(f : \{ 1,\omega \} ^n \to K\) there exists a polynomial \(P \in K[X_1,\dots ,X_n]\) such that \(P(x_1,\dots ,x_n) = f(x)\) for all \(x\) in the cube.

Let \(K\) be a field, let \(n\) be a natural number, and let \(s \subseteq \mathrm{Fin}\, n\). For every point \(x : \mathrm{Fin}\, n \to K\), the squarefree monomial \(\prod _{i \in s} X_i\) evaluated at \(x\) equals \(\prod _{i \in s} x_i\).

Let \(K\) be a field, let \(\omega \in K\) be a nonzero element, and let \(x \in \{ 1,\omega \} ^n\), so that each coordinate \(x_i\) equals either \(1\) or \(\omega \). Then for every coordinate \(i\),

Fix a field \(K\) and let \(s \subseteq \{ 0,1,\dots ,n-1\} \) be a set of variable indices. The total degree of the squarefree monomial \(\prod _{i \in s} X_i\) in the polynomial ring \(K[X_0,\dots ,X_{n-1}]\) is at most \(\left\lvert s\right\rvert \).

Let \(K\) be a field and let \(\omega \in K\) with \(\omega \neq 0\). If \(x \in \{ 1,\omega \} ^n\), that is, \(x\) is a vector in \(K^n\) each of whose coordinates equals either \(1\) or \(\omega \), then every coordinate is nonzero: \(x_i \neq 0\) for each index \(i\).

Let \(K\) be a field, let \(\omega \in K\) be nonzero, and let \(x \in \{ 1,\omega \} ^n\), that is, a vector \(x \colon \mathrm{Fin}\, n \to K\) each of whose coordinates equals \(1\) or \(\omega \). Then for every subset \(s \subseteq \mathrm{Fin}\, n\),

where the first product runs over all coordinates and \(s^{c}\) denotes the complement of \(s\).

Let \(K\) be a field, let \(\omega \in K\) be nonzero, and let \((c_S)_{S \subseteq \mathrm{Fin}\, n}\) be a family of coefficients in \(K\) indexed by the subsets of \(\mathrm{Fin}\, n\). Then there exist polynomials \(P_1, P_2 \in K[X_i : i \in \mathrm{Fin}\, n]\), each of total degree at most \(\lfloor n/2 \rfloor \), such that for every point \(x \in \{ 1,\omega \} ^n\) (that is, every \(x\) with \(x_i \in \{ 1,\omega \} \) for all \(i\)),

Let \(K\) be a field, let \(\omega \in K\), let \(n\) be a natural number, and let \(i \in \{ 0,\dots ,n-1\} \) index one of the \(n\) coordinates. Then for every point \(x = (x_0,\dots ,x_{n-1}) \in K^n\), evaluating the affine inverse coordinate polynomial \(1 + \omega ^{-1} - \omega ^{-1} X_i\) at \(x\) yields

Let \(K\) be a field, fix an element \(\omega \in K\), and let \(n\) be a natural number with a distinguished coordinate index \(i \in \{ 0,\dots ,n-1\} \). The polynomial \(1 + \omega ^{-1} - \omega ^{-1} X_i\) in the polynomial ring \(K[X_0,\dots ,X_{n-1}]\) has total degree at most \(1\).

Let \(K\) be a field, let \(\omega \in K\), and fix \(n \in \mathbb {N}\). For a subset \(s \subseteq \{ 1,\dots ,n\} \), form the polynomial \(\prod _{i \in s}\bigl(1 + \omega ^{-1} - \omega ^{-1} X_i\bigr) \in K[X_1,\dots ,X_n]\). Then for every point \(x \colon \{ 1,\dots ,n\} \to K\), this polynomial evaluates at \(x\) to

Let \(K\) be a field, let \(\omega \in K\), and fix \(n \in \mathbb {N}\) together with a subset \(s \subseteq \{ 0, 1, \dots , n-1\} \). Then the total degree of the affine-substituted squarefree monomial \(\prod _{i \in s}\bigl(1 + \omega ^{-1} - \omega ^{-1} X_i\bigr)\), viewed as a polynomial in \(K[X_0, \dots , X_{n-1}]\), is at most \(\left\lvert s\right\rvert \).

Let \(K\) be a field, fix a scalar \(\omega \in K\) with \(\omega \neq 0\), and let \(n\) be a natural number. For any family of coefficients \((c_S)\) indexed by the subsets \(S \subseteq \{ 1,\dots ,n\} \), form the multilinear polynomial \(F = \sum _{S} c_S \prod _{i \in S} X_i\) in \(K[X_1,\dots ,X_n]\). Then there exist polynomials \(P_1, R \in K[X_1,\dots ,X_n]\), each of total degree at most \(\lfloor n/2 \rfloor \), such that for every point \(x \in \{ 1,\omega \} ^n\) (that is, every \(x\) with each coordinate \(x_i\) equal to \(1\) or to \(\omega \)) one has

Let \(\alpha \), \(\beta \), and \(\mathrm{Cand}\) be finite sets, and assign to each candidate \(c \in \mathrm{Cand}\) a function \(\mathrm{center}(c) \colon \alpha \to \beta \). For a radius \(e \in \mathbb {N}\), write the Hamming ball of radius \(e\) about \(c\) for the set of functions \(f \colon \alpha \to \beta \) that differ from \(\mathrm{center}(c)\) in at most \(e\) coordinates, that is, with \(\left\lvert \{ a \in \alpha : \mathrm{center}(c)(a) \neq f(a)\} \right\rvert \le e\). Suppose that every such ball contains at most \(B\) functions, and that every \(f \colon \alpha \to \beta \) lies in the ball about at least one candidate. Then

Let \(K\) be a finite field, fix an element \(\omega \in K\), and let \(n, D, e, B\) be natural numbers. Write \(\{ 1,\omega \} ^n\) for the cube of vectors in \(\mathrm{Fin}\, n \to K\) whose every coordinate equals \(1\) or \(\omega \). Suppose a finite index set \(\mathrm{Cand}\) is equipped with a map assigning to each candidate \(c\) a polynomial \(P_c \in K[X_1,\dots ,X_n]\), and that the following hold: (i) every polynomial \(Q\) of total degree at most \(D\) agrees, at every point of \(\{ 1,\omega \} ^n\), with \(P_c\) for some candidate \(c\); (ii) for each candidate \(c\), the Hamming ball of radius \(e\) centered at the function \(x \mapsto P_c(x)\) contains at most \(B\) functions \(\{ 1,\omega \} ^n \to K\); and (iii) \(\left\lvert \{ 1,\omega \} ^n \to K\right\rvert \gt \left\lvert \mathrm{Cand}\right\rvert \cdot B\). Then it is not the case that every function \(f : \{ 1,\omega \} ^n \to K\) admits a polynomial \(Q\) of total degree at most \(D\) differing from \(f\) on at most \(e\) points of the cube.

Let \(K\) be a finite field and fix \(\omega \in K\) with \(\omega \neq 0\), and let \(n\) be a natural number. Suppose that every function \(f\colon \{ 1,\omega \} ^n \to K\) agrees, at every point of the cube \(\{ 1,\omega \} ^n\), with some squarefree polynomial \(\sum _{S \subseteq \{ 1,\dots ,n\} } c_S \prod _{i \in S} X_i\) over \(K\). If a polynomial \(P\) in \(n\) variables over \(K\) has total degree at most \(d\) and disagrees with the top monomial \(x \mapsto \prod _{i} x_i\) on at most \(e\) points of \(\{ 1,\omega \} ^n\), then every function \(f\colon \{ 1,\omega \} ^n \to K\) admits a polynomial \(Q\) of total degree at most \(\lfloor n/2 \rfloor + d\) that disagrees with \(f\) on at most \(e\) points of the cube.

Let \(K\) be a finite field, let \(\omega \in K\) be nonzero, and write \(\{ 1,\omega \} ^n\) for the set of vectors in \(K^n\) each of whose coordinates equals \(1\) or \(\omega \). Suppose that every function \(f : \{ 1,\omega \} ^n \to K\) agrees, at every point of the cube, with some multilinear polynomial \(\sum _{S \subseteq \{ 1,\dots ,n\} } c_S \prod _{i \in S} X_i\); and suppose that some function on the cube cannot be approximated to within \(e\) errors by any polynomial of total degree at most \(\lfloor n/2 \rfloor + d\) — that is, for at least one \(f\), every such polynomial disagrees with \(f\) on more than \(e\) points of the cube. Then no polynomial \(P\) of total degree at most \(d\) agrees with the top monomial \(x \mapsto \prod _{i=1}^{n} x_i\) on all but at most \(e\) points of \(\{ 1,\omega \} ^n\).

Let \(K\) be a finite field, let \(\omega \in K\) be nonzero, and fix natural numbers \(n, d, e, B\). Suppose that every function \(f : \{ 1,\omega \} ^n \to K\) agrees, at every point of the cube \(\{ 1,\omega \} ^n\), with some squarefree (multilinear) polynomial \(\sum _{S \subseteq \{ 1,\dots ,n\} } c_S \prod _{i \in S} X_i\). Suppose further that a finite family of polynomials \((P_c)_{c \in \mathrm{Cand}}\), indexed by a finite type \(\mathrm{Cand}\), is complete for total degree at most \(\lfloor n/2 \rfloor + d\), in the sense that every \(Q \in K[X_1,\dots ,X_n]\) with \(\deg Q \le \lfloor n/2 \rfloor + d\) agrees with some \(P_c\) at every point of the cube; that for each \(c\) the Hamming ball of radius \(e\) centered at the function \(x \mapsto P_c(x)\) contains at most \(B\) functions on the cube; and that the number of functions \(\{ 1,\omega \} ^n \to K\) strictly exceeds \(\left\lvert \mathrm{Cand}\right\rvert \cdot B\). Then there is no polynomial \(P\) with \(\deg P \le d\) such that \(P(x) \neq \prod _{i} x_i\) for at most \(e\) points \(x\) of the cube; that is, no polynomial of total degree at most \(d\) approximates the product \(\prod _i x_i\) on \(\{ 1,\omega \} ^n\) with at most \(e\) errors.