Let \(P\) be a family of polynomials over \(\mathbb {Z}/p\) indexed by a nonempty finite seed type. If for every Boolean input \(x\) the number of seeds \(s\) with \((P_s)(\mathrm{boolInput}(x)) \neq f(x)\), times \(2^{\ell }\), is at most \(B\cdot \left\lvert \mathrm{Seed}\right\rvert \), then some seed \(s\) satisfies \(\mathrm{badInputCount}(f, P_s)\cdot 2^{\ell } \le B\cdot 2^{n}\).

Let \(F\) be a feed-forward circuit with a unique output that only uses \(\mathrm{AC}^0[p]\) gate operations. Then there exists a polynomial \(P\) over \(\mathbb {Z}/p\) with \(\deg P \le \mathrm{circuitDegreeBound}\, p\, \ell \, (\mathrm{depth}\, F)\) whose bad-input count against the function computed by \(F\) satisfies \(\mathrm{badInputCount}\cdot 2^{\ell } \le \left\lvert F\right\rvert \cdot 2^{n}\), where \(\left\lvert F\right\rvert \) is the circuit size.

If a feed-forward circuit \(F\) over the \(\mathrm{AC}^0[p]\) gate set computes \(\mathrm{MOD}_q\) on all Boolean inputs, and if \(\mathrm{MOD}_q\) (viewed in \(\mathbb {Z}/p\)) admits the lower bound \(\mathrm{LowDegreeBadCountLB}\) with parameters \((\mathrm{circuitDegreeBound}\, p\, \ell \, (\mathrm{depth}\, F), E)\), then \(E \cdot 2^{\ell } \le \left\lvert F\right\rvert \cdot 2^{n}\).

Same hypotheses as the previous theorem, but with the bad-count bound taken in the relative form \(E = \delta \cdot 2^{n}\); the conclusion is then the clean size bound \(\delta \cdot 2^{\ell } \le \left\lvert F\right\rvert \).

If \(p \neq q\) are primes, then the unit group of \(\mathbb {F}_{p^{q-1}}\) contains an element \(u\) with \(\mathrm{ord}(u) = q\).

If \(p \neq q\) are primes, then there is \(\omega \in \mathbb {F}_{p^{q-1}}\) with \(\omega ^{q} = 1\) and \(\omega \neq 1\).

Every function \(f : \{ 1,\omega \} ^n \to K\) agrees on the cube with the evaluation of some polynomial \(P \in K[X_1,\dots ,X_n]\), i.e. \(P(x) = f(x)\) for all \(x\) in the cube.

For any \(x : \mathrm{Fin}\, n \to K\), the monomial indexed by \(s\) evaluates to \(\prod _{i \in s} x_i\).

If \(\omega \neq 0\) and \(x\) lies in \(\{ 1,\omega \} ^n\), then for every coordinate \(i\),

The total degree of \(\prod _{i \in s} X_i\) is at most \(\left\lvert s\right\rvert \).

If \(\omega \neq 0\) and \(x \in \{ 1,\omega \} ^n\), then \(x_i \neq 0\) for every \(i\).

For \(\omega \neq 0\), \(x \in \{ 1,\omega \} ^n\) and \(s \subseteq \mathrm{Fin}\, n\),

Let \(\omega \neq 0\) and let \(c\) be a coefficient family. Then there are polynomials \(P_1, P_2\) of total degree at most \(n/2\) such that for every \(x \in \{ 1,\omega \} ^n\),

For any \(x : \mathrm{Fin}\, n \to K\), the polynomial \(\mathrm{affineInvPoly}\, \omega \, i\) evaluates to \(1 + \omega ^{-1} - \omega ^{-1} x_i\).

The total degree of \(\mathrm{affineInvPoly}\, \omega \, i\) is at most \(1\).

For any \(x : \mathrm{Fin}\, n \to K\), the affine squarefree monomial indexed by \(s\) evaluates to \(\prod _{i \in s} (1 + \omega ^{-1} - \omega ^{-1} x_i)\).

The total degree of \(\mathrm{affineSquarefreeMonomial}\, \omega \, s\) is at most \(\left\lvert s\right\rvert \).

Let \(\omega \neq 0\) and let \(c\) be a coefficient family. Then there are polynomials \(P_1, R\) of total degree at most \(n/2\) such that for every \(x \in \{ 1,\omega \} ^n\),

so that the second factor is already evaluated at \(x\) itself rather than at the affine substitution.

Let \(\alpha , \beta , \mathrm{Cand}\) be finite and let \(\mathrm{center} : \mathrm{Cand} \to (\alpha \to \beta )\). If every ball \(\{ f : \left\lvert \{ a : \mathrm{center}\, c\, a \neq f(a)\} \right\rvert \le e\} \) has at most \(B\) elements, and every \(f : \alpha \to \beta \) lies in one of these balls, then \(\left\lvert \alpha \to \beta \right\rvert \le \left\lvert \mathrm{Cand}\right\rvert \cdot B\).

Suppose a finite family \((\mathrm{poly}\, c)_{c \in \mathrm{Cand}}\) represents, on the cube, every polynomial of total degree at most \(D\); suppose each Hamming ball of radius \(e\) around such a candidate has at most \(B\) elements; and suppose \(\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 on the cube has a degree-\(\le D\) approximant with at most \(e\) bad points.

Assume \(\omega \neq 0\) and that every function on \(\{ 1,\omega \} ^n\) is represented on the cube by a squarefree polynomial. If \(P\) has total degree at most \(d\) and approximates the top monomial \(x \mapsto \prod _i x_i\) with at most \(e\) bad points, then every function \(f\) on the cube has a polynomial \(Q\) with \(\deg Q \le n/2 + d\) and at most \(e\) bad points.

Assume \(\omega \neq 0\), that every function on \(\{ 1,\omega \} ^n\) has a squarefree representative, and the counting hypothesis that not every function on the cube admits a degree-\(\le n/2 + d\) approximant with at most \(e\) bad points. Then no polynomial of total degree at most \(d\) approximates the top monomial \(x \mapsto \prod _i x_i\) within \(e\) bad points.

The same conclusion as the previous theorem, with the abstract counting hypothesis replaced by explicit data: a finite candidate family representing all degree-\(\le n/2 + d\) polynomials on the cube, a bound \(B\) on the size of each Hamming ball of radius \(e\), and the strict inequality \(\left\lvert \{ 1,\omega \} ^n \to K\right\rvert \gt \left\lvert \mathrm{Cand}\right\rvert \cdot B\).