123 Boolean Analysis — Circuit Size
123.1 Overview
This file identifies the layerwise gate count \(\mathrm{gateCountBefore}\) accumulated by the Razborov–Smolensky induction with the total circuit size \(F.\mathrm{size}\) of a feed-forward circuit, by writing both as the sum of the cardinalities of the non-input layers. The identification is then used to restate the polynomial-approximation existence theorems of the previous chapter with their error bounds phrased directly in terms of the number of gates.
123.2 Declarations
For a feed-forward circuit \(F\), a bound \(d \le F.\mathrm{depth}\) and an index \(j : \mathrm{Fin}\, d\), the layer index \(\mathrm{gateLayerIdx}\, F\, h_d\, j \in \mathrm{Fin}(F.\mathrm{depth}+1)\) is \(j+1\), i.e. the \((j+1)\)-st node layer of \(F\). It packages the non-input layers \(1, \dots , d\) as indices into \(F.\mathrm{nodes}\) so that they can be summed over.
Let \(F\) be a Boolean feed-forward circuit (alphabet \(\mathbb {F}_2\), input type \(\mathrm{Fin}\, n\)) all of whose node layers are finite, and write \(\mathrm{depth}(F)\) for its depth. For a natural number \(d\) with \(d \le \mathrm{depth}(F)\), the number of non-input gates in the first \(d\) layers equals the total number of nodes across layers \(1,\dots ,d\):
where \(L_i\) denotes the set of nodes in the \(i\)-th layer of \(F\).
Let \(F\) be a layered feedforward circuit over the Boolean alphabet \(\mathbb {F}_2 = \{ 0,1\} \) with input type \(\mathrm{Fin}\, n\), and suppose every node layer of \(F\) is finite. Then the size of \(F\) equals the sum of the cardinalities of its non-input layers:
that is, the total number of non-input nodes is obtained by adding up the numbers of nodes in layers \(1, \dots , \mathrm{depth}(F)\).
Let \(F\) be a feedforward circuit over the alphabet \(\mathbb {F}_2\) with input type \(\mathrm{Fin}\, n\), and suppose each of its node layers is finite. Counting the non-input nodes layer by layer through all of the layers \(1,\dots ,\mathrm{depth}(F)\), and accumulating these counts over the full depth of \(F\), yields exactly the size of \(F\), that is, its total number of non-input nodes.
Let \(p\) be a prime and let \(F\) be a feedforward circuit over the Boolean alphabet \(\{ 0,1\} \) with inputs indexed by \(\{ 1,\dots ,n\} \) and a finite set of outputs, in which every layer has only finitely many nodes and every gate belongs to the \(\mathrm{AC}^0[p]\) gate set. Then for every \(\ell \in \mathbb {N}\) there exist a finite, nonempty seed set \(\mathrm{Seed}\) and, for each seed \(s \in \mathrm{Seed}\) and each output \(o\), a polynomial \(P_{s,o} \in \mathbb {Z}/p[X_1,\dots ,X_n]\) of total degree at most \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\), such that for every Boolean input \(x \in \{ 0,1\} ^n\) the seeds that err on \(x\) satisfy
where \(\bar x \in (\mathbb {Z}/p)^n\) and \(\overline{F(x)(o)} \in \mathbb {Z}/p\) denote the images under \(\{ 0,1\} \to \mathbb {Z}/p\) of the Boolean vector \(x\) and of the circuit’s output at \(o\) on input \(x\), respectively.
Let \(p\) be a prime, and let \(F\) be a feedforward circuit over the Boolean alphabet \(\mathrm{Fin}\, 2\) with input coordinates indexed by \(\mathrm{Fin}\, n\) and a single output node, in which every layer has finitely many nodes and every gate operation belongs to the \(\mathrm{AC}^0[p]\) gate set (the identity gate, the NOT gate, the unbounded fan-in AND gate of every arity, and the \(\mathrm{MOD}_p\) gate of every arity). For a Boolean input \(x : \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\), write \(\bar{x} \in (\mathbb {Z}/p)^n\) for the point whose \(i\)-th coordinate is the residue of \(x_i\) modulo \(p\), and let \(c(x) \in \mathbb {Z}/p\) be the residue of the single Boolean value that \(F\) computes on \(x\). Then for every \(\ell \in \mathbb {N}\) there exist a finite nonempty index set \(\mathrm{Seed}\) and a family of polynomials \((P_s)_{s \in \mathrm{Seed}}\) in \(\mathbb {Z}/p[X_1,\dots ,X_n]\), each of total degree at most \(\bigl((p-1)\ell \bigr)^{d}\), where \(d\) is the depth of \(F\), such that for every Boolean input \(x\),
where \(\operatorname {size}(F)\) denotes the number of non-input nodes of \(F\).
Let \(p\) be a prime and let \(F\) be a feedforward circuit over the alphabet \(\mathrm{Fin}\, 2\) with \(n\) Boolean input variables, finitely many nodes in each layer, and a single output node, every gate of which belongs to the \(\mathrm{AC}^0[p]\) gate set. Then for each \(\ell \in \mathbb {N}\) there exists a nonempty list of polynomials \(P_1, \dots , P_m \in (\mathbb {Z}/p)[X_1, \dots , X_n]\), each of total degree at most \(\bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\), with the following property. Given a Boolean input \(x \colon \mathrm{Fin}\, n \to \mathrm{Fin}\, 2\), let \(\hat{x} \colon \mathrm{Fin}\, n \to \mathbb {Z}/p\) denote \(x\) cast coordinatewise into \(\mathbb {Z}/p\), and let \(b(x) \in \mathbb {Z}/p\) denote the image of the single output bit that \(F\) computes on \(x\). Then for every such \(x\) the number of indices \(j\) at which the polynomial disagrees with the circuit satisfies
where \(\mathrm{size}(F)\) is the number of non-input nodes of \(F\) and \(m\) is the length of the list.