127 Boolean Analysis — Circuit Degree
127.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.
127.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\).
For every bit \(b : \mathrm{Fin}\, 2\) the element \(\mathrm{boolVal}_p(b)\) lies in the subset \(\{ 0,1\} \) of \(\mathbb {Z}/p\).
Applying \(\mathrm{bitify}_p\) to \(\mathrm{boolVal}_p(b)\) returns the original bit \(b\), for every \(b : \mathrm{Fin}\, 2\).
For a feed-forward circuit \(F\), a layer index \(d\), a node \(u\) at layer \(d+1\) and an input \(x\), the value of \(u\) is obtained by applying the gate operation attached to \(u\) to the values of its input nodes at layer \(d\).
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\).
\(\mathrm{gateCountBefore}\, F\, 0 = 0\): the input layer contributes no gates.
\(\mathrm{gateCountBefore}\, F\, (d+1)\) equals \(\mathrm{gateCountBefore}\, F\, d\) plus the cardinality of the node set at layer \(d+1\).
For finite types \(\alpha ,\beta \) and a decidable predicate \(P\) on \(\alpha \), the number of pairs \(z \in \alpha \times \beta \) with \(P(z_1)\) equals \(\left\lvert \{ a : P(a)\} \right\rvert \cdot \left\lvert \beta \right\rvert \).
Let \(P\) be a predicate on \(\alpha \), \(Q\) a predicate on \(\alpha \times \beta \), and \(C, B\) natural numbers such that for every \(a\) with \(P(a)\) the fiber count 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.
Fix a coordinate \(i\) and a decidable predicate \(\mathrm{Bad}\) on \(\beta _i\), and suppose \(\left\lvert \{ b : \mathrm{Bad}(b)\} \right\rvert \cdot C \le \left\lvert \beta _i\right\rvert \). Then the number of dependent functions \(f\) with \(\mathrm{Bad}(f_i)\) satisfies
Given for each coordinate \(i\) a decidable predicate \(\mathrm{Bad}_i\) on \(\beta _i\) with \(\left\lvert \{ b : \mathrm{Bad}_i(b)\} \right\rvert \cdot C \le \left\lvert \beta _i\right\rvert \), the number of dependent functions bad at some coordinate obeys
For a list \(l\), a map \(f\) and a decidable predicate \(P\), the length of the filter of \(l.\mathrm{map}\, f\) by \(P\) equals the length of the filter of \(l\) by the pulled-back predicate \(a \mapsto P(f(a))\).
For a finset \(s\) and a decidable predicate \(q\), the length of the filtered list \(s.\mathrm{toList}\) by \(q\) equals the cardinality of the filtered finset \(s\) by \(q\).
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.
For every \(n\), every error parameter \(\ell \), and every gate operation \(\mathrm{op}\) belonging to the \(\mathrm{AC}^0[p]\) gate set, there exists a GatePolyFamily \(p\, n\, \ell \, \mathrm{op}\).
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 \(F\) be a feed-forward circuit over \(\mathrm{Fin}\, 2\) with finite node sets, finite output type \(\mathrm{out}\), using only \(\mathrm{AC}^0[p]\) gates, and let \(\ell \) be an error parameter. Then there is a nonempty finite seed type and a family \(P\) of polynomials \(P(s,o)\) over \(\mathbb {Z}/p\) such that every \(P(s,o)\) has total degree at most \(\mathrm{circuitDegreeBound}(p,\ell ,F.\mathrm{depth})\) and, for each Boolean input \(x\),
The same statement for a circuit with a unique output node: there is a nonempty finite seed type and polynomials \(P(s)\) of total degree at most \(\mathrm{circuitDegreeBound}(p,\ell ,F.\mathrm{depth})\) such that for every Boolean input \(x\),
The single-output theorem restated with the seed distribution presented as a nonempty list \(Ps\) of polynomials with multiplicity, one entry per seed: every \(P \in Ps\) has total degree at most \(\mathrm{circuitDegreeBound}(p,\ell ,F.\mathrm{depth})\), and for every Boolean input \(x\) the number of entries of \(Ps\) disagreeing with \(F.\mathrm{eval}_1\, x\), multiplied by \(2^{\ell }\), is at most \(\mathrm{gateCountBefore}\, F\, F.\mathrm{depth} \cdot \left\lvert Ps\right\rvert \).