Let \(\iota \) be a finite index type, let \(\beta \) be a finite type, and let \(P\) be a decidable predicate on \(\beta \). Then the number of functions \(f : \iota \to \beta \) such that \(P(f(i))\) holds for every \(i \in \iota \) equals \(\left\lvert \{ \, b \in \beta : P(b)\, \} \right\rvert ^{\left\lvert \iota \right\rvert }\).

Let \(\alpha \) be a finite type and \(\beta \) a finite nonempty type, let \(\mathrm{Bad} \subseteq \alpha \) be a finite set, let \(\mathrm{Fail} \subseteq \alpha \times \beta \) be a decidable relation, and let \(C\) be a natural number. Suppose that for every \(a \in \mathrm{Bad}\) we have \(\left\lvert \{ b \in \beta : \mathrm{Fail}(a,b)\} \right\rvert \cdot C \le \left\lvert \beta \right\rvert \). Then there exists a single \(b \in \beta \) such that \(\left\lvert \{ a \in \mathrm{Bad} : \mathrm{Fail}(a,b)\} \right\rvert \cdot C \le \left\lvert \mathrm{Bad}\right\rvert \).

Let \(p\) be a prime and let \(a \in \mathbb {Z}/p\) satisfy \(a \in \{ 0, 1\} \). Write \(\beta (a) \in \mathrm{Fin}\, 2\) for the booleanization of \(a\), equal to \(1\) when \(a = 1\) and to \(0\) otherwise. Then interpreting \(\beta (a)\) as a natural number and reducing it back modulo \(p\) recovers \(a\); that is, the image of \(\beta (a)\) under \(\mathrm{Fin}\, 2 \to \mathbb {N} \to \mathbb {Z}/p\) equals \(a\).

Let \(p\) be a prime and let \(a \in \mathbb {Z}/p\mathbb {Z}\). Then

That is, \(1 - a^{p-1}\) is the indicator of \(a = 0\) in the field \(\mathbb {Z}/p\mathbb {Z}\).

Let \(p\) be a prime and let \(a \in \mathbb {Z}/p\) lie in \(\{ 0, 1\} \). Then

where the right-hand side denotes the element of \(\{ 0,1\} \subseteq \mathbb {Z}/p\) obtained by casting the value \(\mathrm{bitify}(a) \in \mathrm{Fin}\, 2\) through the natural numbers into \(\mathbb {Z}/p\); that is, the expression \(1 - (1 - a)^{p-1}\) equals \(1\) when \(a = 1\) and \(0\) when \(a = 0\).

Let \(p\) be a prime and let \(v = (v_i)_{i \in \{ 1,\dots ,n\} }\) be a nonzero tuple of elements of the field \(\mathbb {Z}/p\mathbb {Z}\). Then at most half of the \(2^n\) subsets of the index set \(\{ 1,\dots ,n\} \) have vanishing subset sum; that is, twice the number of subsets \(s \subseteq \{ 1,\dots ,n\} \) for which \(\sum _{i \in s} v_i = 0\) is at most \(2^n\).

Fix a prime \(p\), and let \(P_1,\dots ,P_{\mathrm{width}}\) be polynomials in the variables \(y_1,\dots ,y_{\mathrm{vars}}\) over \(\mathbb {Z}/p\), together with subsets \(S_1,\dots ,S_\ell \) of the index set \(\{ 1,\dots ,\mathrm{width}\} \). Then for every point \(y : \{ 1,\dots ,\mathrm{vars}\} \to \mathbb {Z}/p\), evaluating the randomized OR-approximating polynomial \(1 - \prod _{k=1}^{\ell }\bigl(1 - (\sum _{i \in S_k} P_i)^{p-1}\bigr)\) at \(y\) yields the value obtained by feeding the scalars \(P_1(y),\dots ,P_{\mathrm{width}}(y)\) into the value-level OR approximator with the same subsets:

Fix a prime \(p\), and let \(v : \mathrm{Fin}\, \mathrm{width} \to \mathbb {Z}/p\) be a vector together with a family \(S_1,\dots ,S_\ell \) of subsets of \(\{ 1,\dots ,\mathrm{width}\} \). Then the value-level OR approximator built from \(v\) and \(S\) disagrees with the value-level OR detector of \(v\) if and only if \(v \neq 0\) yet \(\sum _{i \in S_k} v_i = 0\) in \(\mathbb {Z}/p\) for every index \(k\).

Fix a prime \(p\) and let \(v : \mathrm{Fin}\, \mathrm{width} \to \mathbb {Z}/p\) be a nonzero vector. Consider families \(S = (S_1,\dots ,S_\ell )\) of subsets \(S_k \subseteq \mathrm{Fin}\, \mathrm{width}\), indexed by \(\mathrm{Fin}\, \ell \), and call such a family *bad* for \(v\) if the value-level OR approximator \(1 - \prod _k\bigl(1 - (\sum _{i \in S_k} v_i)^{p-1}\bigr)\) disagrees with the value-level OR detector \(1 - \prod _k\bigl(1 - v_k^{\, p-1}\bigr)\). Then the number of bad families, multiplied by \(2^\ell \), is at most the total number of families \(S : \mathrm{Fin}\, \ell \to \mathrm{Finset}(\mathrm{Fin}\, \mathrm{width})\).

For natural numbers \(\mathrm{width}\) and \(\ell \), the number of \(\ell \)-tuples of subsets of an \(\mathrm{width}\)-element set equals \(2^{\mathrm{width}\cdot \ell }\); that is, the set of functions assigning to each index \(i \in \{ 0,\dots ,\ell -1\} \) a subset of \(\{ 0,\dots ,\mathrm{width}-1\} \) has exactly \(2^{\mathrm{width}\cdot \ell }\) elements.

Fix a prime \(p\) and natural numbers \(w\) and \(\ell \), and let \(v = (v_1,\dots ,v_w)\) be an arbitrary vector in \((\mathbb {Z}/p)^w\) (no coordinate is assumed nonzero). Call a *seed* a tuple \(S = (S_1,\dots ,S_\ell )\) of subsets of \(\{ 1,\dots ,w\} \), and call it *bad* when the value-level OR approximator determined by \(v\) and \(S\) differs from the value-level OR detector of \(v\). Then, writing \(N = (2^{w})^{\ell }\) for the total number of seeds, the number of bad seeds satisfies

Fix a prime \(p\) and, for a given width \(\mathrm{width}\) and seed length \(\ell \), a family of polynomials \(P_1,\dots ,P_{\mathrm{width}}\) over \(\mathbb {Z}/p\) in a fixed number of variables. Form the list whose entries are the OR-approximating polynomials, one for each random seed — a seed being a tuple \((S_1,\dots ,S_\ell )\) of \(\ell \) subsets of the index set \(\{ 1,\dots ,\mathrm{width}\} \), listed with multiplicity. Then this list has length \(2^{\mathrm{width}\cdot \ell }\), the number of such seeds.

Fix a prime \(p\) and, for natural numbers \(\mathrm{vars}\), \(\mathrm{width}\), and \(\ell \), let \(P_1,\dots ,P_{\mathrm{width}}\) be polynomials in \(\mathrm{vars}\) variables over \(\mathbb {Z}/p\). A random seed is a tuple \((S_1,\dots ,S_\ell )\) of subsets of the width positions \(\{ 1,\dots ,\mathrm{width}\} \), of which there are \((2^{\mathrm{width}})^{\ell } = 2^{\mathrm{width}\cdot \ell }\). The list obtained by recording the AND-approximating polynomial of \(P_1,\dots ,P_{\mathrm{width}}\) for every such seed therefore has length \(2^{\mathrm{width}\cdot \ell }\).

Let \(p\) be a prime, and let \(\mathrm{op}\) be a gate operation belonging to the \(\mathrm{AC}^0[p]\) gate set over the alphabet \(\mathrm{Fin}\, 2\). Then \(\mathrm{op}\) is one of exactly four kinds of gate: the identity gate \(x \mapsto x_0\) on a single input, the NOT gate \(x \mapsto 1 - x_0\) on a single input, the unbounded fan-in AND gate \(x \mapsto \prod _{i} x_i\) for some arity \(n\), or the unbounded \(\mathrm{MOD}_p\) gate for some arity \(n\).

Let \(p\) be a prime and let \(\mathrm{inputs}_0, \dots , \mathrm{inputs}_{w-1}\) be elements of \(\mathbb {Z}/p\), each lying in \(\{ 0,1\} \). Then

where the right-hand side is the output of the unbounded \(\mathrm{MOD}_p\) gate on the booleanizations of the inputs — equal to \(1\) when \(\sum _i \mathrm{inputs}_i = 0\) in \(\mathbb {Z}/p\) and to \(0\) otherwise — regarded as an element of \(\{ 0,1\} \subseteq \mathbb {Z}/p\).

Let \(p\) be a prime, and let \(x_0,\dots ,x_{w-1}\) be elements of \(\mathbb {Z}/p\), each lying in \(\{ 0,1\} \). Then

where \(\beta \) is the booleanization \(\mathbb {Z}/p \to \mathrm{Fin}\, 2\) (sending \(1\) to \(1\) and everything else to \(0\)). The left-hand product is taken in \(\mathbb {Z}/p\); on the right, the product of the \(\beta (x_i)\) is formed in \(\mathrm{Fin}\, 2\), and its value—the natural number \(0\) or \(1\)—is cast into \(\mathbb {Z}/p\). Thus the Fermat-power expression on the left evaluates to the Boolean AND of the inputs.

Let \(p\) be a prime, and fix natural numbers \(n\) and \(\ell \). Let \(\mathrm{op}\) be a gate operation from the \(\mathrm{AC}^0[p]\) gate set, and for each input wire \(i\) of \(\mathrm{op}\) let \(P_i\) be a polynomial in \(\mathbb {Z}/p[X_1,\dots ,X_n]\). Then there exist a nonempty finite index set \(\mathrm{Seed}\) with decidable equality and a family of polynomials \((P_s)_{s\in \mathrm{Seed}}\) in \(\mathbb {Z}/p[X_1,\dots ,X_n]\) with the following two properties. First, each \(P_s\) has total degree at most \((p-1)\, \ell \, \sup _i \deg (P_i)\). Second, for every Boolean assignment \(x\in \{ 0,1\} ^n\), write \(y\in (\mathbb {Z}/p)^n\) for the coordinatewise image of \(x\) under the inclusion \(\mathrm{Fin}\, 2\hookrightarrow \mathbb {Z}/p\); then, provided every value \(P_i(y)\) lies in \(\{ 0,1\} \), the number of seeds \(s\in \mathrm{Seed}\) for which \(P_s(y)\) differs from the gate output \(\mathrm{op}\bigl(i\mapsto \mathrm{bitify}(P_i(y))\bigr)\), multiplied by \(2^\ell \), is at most \(\left\lvert \mathrm{Seed}\right\rvert \).