122 Boolean Analysis — Circuit Degree
122.1 Overview
This file carries out the Razborov–Smolensky polynomial approximation of an \(\mathrm{AC}^0[p]\) circuit: layer by layer, every gate of a feed-forward circuit is replaced by a random low-degree polynomial over \(\mathbb {Z}/p\), and the layerwise error probabilities are combined by a union bound. The end products are existence theorems producing a seed-indexed distribution (or an explicit list) of polynomials of total degree at most \(((p-1)\ell )^{\mathrm{depth}}\) that agree with the circuit at any fixed input except on a small fraction of seeds.
122.2 Declarations
For a Boolean input \(x : \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\), the map \(\mathrm{boolInput}_p(x)\) sends each coordinate \(i\) to the image of the natural number \(x_i\) in \(\mathbb {Z}/p\).
The value in \(\mathbb {Z}/p\) represented by a bit \(b : \mathrm{Fin}\, 2\), namely the image of the natural number \(b\) under the canonical map \(\mathbb {N}\to \mathbb {Z}/p\).
Let \(p\) be a prime and let \(b : \mathrm{Fin}\, 2\) be a bit. Then the element of \(\mathbb {Z}/p\) represented by \(b\) — the image of the natural number \(b\) under the canonical map \(\mathbb {N}\to \mathbb {Z}/p\) — belongs to the subset \(\{ 0,1\} \) of \(\mathbb {Z}/p\).
Let \(p\) be a prime and let \(b \in \mathrm{Fin}\, 2\) be a bit. Booleanizing the field value of \(b\) recovers \(b\): taking the element of \(\mathbb {Z}/p\) represented by \(b\) and then mapping it back to \(\mathrm{Fin}\, 2\) (sending \(1\) to \(1\) and everything else to \(0\)) yields \(b\) again.
Let \(F\) be a feedforward circuit over an alphabet \(\alpha \), let \(d\) be a layer index with \(0 \le d \lt \mathrm{depth}(F)\), let \(u\) be a node of layer \(d+1\), and let \(x\) be an assignment of alphabet values to the input nodes of \(F\). Writing \(g\) for the gate attached to \(u\), the value of \(u\) under \(x\) equals the gate operation of \(g\) applied to the tuple whose entry at each input slot \(i\) is the value under \(x\) of the layer-\(d\) node to which slot \(i\) is wired.
The degree budget for the approximating polynomials after \(d\) layers, defined as
For a circuit \(F\) with finite node sets, \(\mathrm{gateCountBefore}\, F\, d\) counts the non-input gates in layers \(1,\dots ,d\): it is \(0\) for \(d = 0\) and, recursively, the count for \(d\) plus the number of nodes at layer \(d+1\).
Let \(F\) be a layered feedforward circuit over the Boolean alphabet \(\{ 0,1\} \), whose input layer carries \(n\) nodes and each of whose layers has a finite node set. Then the number of non-input gates lying in the first \(0\) layers is zero, since the input layer contributes no gates.
Let \(F\) be a layered feedforward circuit over the Boolean alphabet \(\mathbb {F}_2\) with input type \(\mathrm{Fin}\, n\), in which every layer has finitely many nodes, and for each natural number \(k \le \mathrm{depth}(F)\) let \(g_F(k)\) denote the number of non-input gates lying in layers \(1,\dots ,k\) (so \(g_F(0) = 0\)). Then for every \(d\) with \(d + 1 \le \mathrm{depth}(F)\),
where \(\left\lvert N_{d+1}\right\rvert \) is the number of nodes in layer \(d+1\).
Let \(\alpha \) and \(\beta \) be finite types, and let \(P\) be a decidable predicate on \(\alpha \). Then the number of pairs \((a,b) \in \alpha \times \beta \) whose first component satisfies \(P\) equals the number of elements \(a \in \alpha \) satisfying \(P\), multiplied by the cardinality \(\left\lvert \beta \right\rvert \).
Let \(\alpha \) and \(\beta \) be finite types, let \(P\) be a predicate on \(\alpha \) and \(Q\) a predicate on \(\alpha \times \beta \), and let \(C, B\) be natural numbers. Suppose that for every \(a \in \alpha \) satisfying \(P(a)\), the fiber \(\{ \, b \in \beta : Q(a,b)\, \} \) satisfies \(\left\lvert \{ \, b : Q(a,b)\, \} \right\rvert \cdot C \le B\). Then
For an index \(i\) with decidable equality on the index type, the equivalence
sending a dependent function to its value at \(i\) together with its restriction to the remaining coordinates.
Let \(\iota \) be a finite index type with decidable equality, let \((\beta _j)_{j \in \iota }\) be a family of finite types, and fix a coordinate \(i \in \iota \). Let \(\mathrm{Bad}\) be a decidable predicate on \(\beta _i\), and let \(C\) be a natural number such that
Then the number of dependent functions \(f \in \prod _{j \in \iota } \beta _j\) whose value at \(i\) is bad satisfies
Let \(\iota \) be a finite index set, and for each \(i \in \iota \) let \(\beta _i\) be a finite set equipped with a predicate \(\mathrm{Bad}_i\) singling out its "bad" elements. Fix a natural number \(C\), and suppose that for every coordinate \(i\) the bad elements are sufficiently rare, in the sense that
Then, among all dependent tuples \(f\) in the product \(\prod _{i \in \iota } \beta _i\), those that are bad in at least one coordinate satisfy
Let \(l\) be a finite list with entries in a set \(\alpha \), let \(f\colon \alpha \to \beta \) be a function, and let \(P\) be a decidable predicate on \(\beta \). Then applying \(f\) to every entry of \(l\) and retaining those whose image satisfies \(P\) yields a list of the same length as retaining those entries \(a\) of \(l\) for which \(P(f(a))\) holds; that is, the sublist \(\bigl(\mathrm{map}\, f\, (l)\bigr)\) filtered by \(P\) and the sublist of \(l\) filtered by the pulled-back predicate \(a \mapsto P(f(a))\) have equal length.
Let \(s\) be a finite set of elements of a type \(\alpha \), and let \(q\) be a decidable predicate on \(\alpha \). Writing the elements of \(s\) out as a list (in any order) and discarding those that fail \(q\) produces a list whose length equals the number of elements of \(s\) that satisfy \(q\); that is, the length of the filtered list agrees with the cardinality of the subset \(\{ x \in s : q(x)\} \).
A GatePolyFamily for a gate operation \(\mathrm{op}\) packages a nonempty finite seed type together with, for each tuple of incoming polynomials and each seed, an approximating polynomial in \(n\) variables over \(\mathbb {Z}/p\) subject to two guarantees: its total degree is at most \((p-1)\ell \cdot \sup _i \deg (\text{polys}_i)\), and for every Boolean input \(x\) at which all incoming polynomials evaluate into \(\{ 0,1\} \), the number of seeds on which the approximator disagrees with the true gate value, multiplied by \(2^{\ell }\), is at most the number of seeds. Crucially the seed type depends only on the gate, not on the incoming polynomials.
Let \(p\) be a prime, and fix natural numbers \(n\) and \(\ell \). For every gate operation \(\mathrm{op}\) belonging to the \(\mathrm{AC}^0[p]\) gate set — the identity, the NOT gate, the unbounded fan-in AND gate of any arity, and the unbounded \(\mathrm{MOD}_p\) gate of any arity — there exists a gate approximator family for \(\mathrm{op}\) in \(n\) variables with parameter \(\ell \); that is, a nonempty finite seed type together with, for each tuple of incoming polynomials over \(\mathbb {Z}/p\) and each seed, an approximating polynomial in \(n\) variables whose total degree is at most \((p-1)\, \ell \) times the largest degree among the incoming polynomials, and such that for every Boolean input at which all incoming polynomials evaluate into \(\{ 0,1\} \), the number of seeds on which the approximator disagrees with the true gate value, multiplied by \(2^{\ell }\), is at most the total number of seeds.
A choice of GatePolyFamily for each \(\mathrm{AC}^0[p]\) gate operation, obtained from the preceding existence statement.
A LayerPolyFamily for a circuit \(F\) at layer \(d\) consists of a nonempty finite seed type and, for each seed, a polynomial for every node of layer \(d\), such that each polynomial has total degree at most \(\mathrm{circuitDegreeBound}(p,\ell ,d)\) and, for every Boolean input \(x\), the number of seeds for which some layer-\(d\) node is mispredicted, multiplied by \(2^{\ell }\), is at most \(\mathrm{gateCountBefore}\, F\, d\) times the number of seeds.
The LayerPolyFamily at layer \(0\): a single seed, with each input node represented exactly by the corresponding variable \(X_i\), so that no seed is ever bad.
Given a circuit \(F\) using only \(\mathrm{AC}^0[p]\) gates and a LayerPolyFamily at layer \(d\), this produces a LayerPolyFamily at layer \(d+1\). Its seed type is the product of the previous seed type with one gate seed per node of layer \(d+1\), and each node polynomial is the gate approximator applied to the layer-\(d\) polynomials of its inputs.
For a circuit using only \(\mathrm{AC}^0[p]\) gates, the LayerPolyFamily at any layer \(d \le F.\mathrm{depth}\), obtained by starting from the input layer family and iterating the layer step \(d\) times.
Let \(p\) be a prime, let \(F\) be a feedforward circuit over the alphabet \(\mathrm{Fin}\, 2\) with input type \(\mathrm{Fin}\, n\) and a finite output type, all of whose node sets are finite and which uses only \(\mathrm{AC}^0[p]\) gates, and fix an error parameter \(\ell \in \mathbb {N}\). Write \(d = \mathrm{depth}(F)\) for its depth and \(N\) for the total number of its non-input gates, that is, the sum over the layers \(1,\dots ,d\) of the number of nodes in each layer. For a bit \(b \in \mathrm{Fin}\, 2\) write \(\overline{b} \in \mathbb {Z}/p\) for the image of \(b\) regarded as a natural number, and for a Boolean input \(x : \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\) write \(\hat{x} \in (\mathbb {Z}/p)^n\) for the point whose \(i\)-th coordinate is \(\overline{x_i}\). Then there exist a nonempty finite seed type \(S\) and, for each seed \(s \in S\) and each output node \(o\), a polynomial \(P_{s,o}\) in \(n\) variables over \(\mathbb {Z}/p\), such that every \(P_{s,o}\) has total degree at most \(\bigl((p-1)\ell \bigr)^{d}\) and, for every Boolean input \(x\),
where \(F(x)(o) \in \mathrm{Fin}\, 2\) is the value the circuit \(F\) computes at output node \(o\) on input \(x\).
Let \(p\) be prime and let \(n, \ell \in \mathbb {N}\). Let \(F\) be a feedforward circuit over the alphabet \(\mathrm{Fin}\, 2\) with input type \(\mathrm{Fin}\, n\), a single output node, and a finite node set at every layer, each of whose gates is an \(\mathrm{AC}^0[p]\) gate (the identity, NOT, an unbounded fan-in AND, or an unbounded \(\mathrm{MOD}_p\) gate of some arity); write \(d\) for its depth. For a Boolean input \(x : \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\), let \(\hat{x}\) be its coordinatewise image in \(\mathbb {Z}/p\) and let \(F(x) \in \{ 0,1\} \subseteq \mathbb {Z}/p\) be the resulting single output value cast into the field. Then there exist a nonempty finite seed set \(\mathrm{Seed}\) and a family of polynomials \(P_s \in (\mathbb {Z}/p)[X_0,\dots ,X_{n-1}]\) indexed by \(s \in \mathrm{Seed}\), each of total degree at most \(\bigl((p-1)\ell \bigr)^{d}\), such that for every Boolean input \(x\),
where \(G\) is the total number of non-input gates of \(F\), that is, the total number of nodes across layers \(1,\dots ,d\).
Let \(p\) be a prime and let \(F\) be a layered feedforward circuit over the Boolean alphabet \(\mathrm{Fin}\, 2\), with inputs indexed by \(\mathrm{Fin}\, n\), finitely many nodes in every layer, and a single output node, and suppose every gate of \(F\) belongs to the \(\mathrm{AC}^0[p]\) gate set (the identity, NOT, unbounded fan-in AND, and unbounded \(\mathrm{MOD}_p\) gates of every arity). Then for every \(\ell \in \mathbb {N}\) there is a nonempty list \(P_1,\dots ,P_m\) of polynomials in the variables \(\{ X_i : i \in \mathrm{Fin}\, n\} \) over \(\mathbb {Z}/p\), each of total degree at most \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\), with the following property. For a Boolean input \(x : \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\), write \(\hat{x} \in (\mathbb {Z}/p)^n\) for the point whose \(i\)-th coordinate is the image of \(x_i\) in \(\mathbb {Z}/p\), and let \(b(x) \in \mathbb {Z}/p\) be the image of the single Boolean value output by \(F\) on \(x\). Then for every such \(x\), the number of indices \(j\) with \(P_j(\hat{x}) \neq b(x)\), multiplied by \(2^{\ell }\), is at most \(s \cdot m\), where \(s\) is the total number of non-input gates of \(F\) and \(m\) is the length of the list.