126 Boolean Analysis — A Cp Gates
126.1 Overview
This file sets up the gate sets \(\mathrm{AC}^0\) and \(\mathrm{AC}^0[p]\) over the Boolean alphabet \(\mathrm{Fin}\, 2\), and the polynomial machinery used in the Razborov–Smolensky argument: Razborov’s randomized low-degree approximations of unbounded fan-in \(\mathrm{OR}\) and \(\mathrm{AND}\) over the field \(\mathbb {Z}/p\), together with the exact \(\mathrm{MOD}_p\) polynomial. The main outputs are total-degree bounds of the form \((p-1)\ell \) per gate and pointwise counting bounds showing that, for each fixed input, at most a \(2^{-\ell }\) fraction of the random seeds produce a wrong value.
126.2 Declarations
The set of plain \(\mathrm{AC}^0\) gate operations on the alphabet \(\mathrm{Fin}\, 2\): the identity gate, the NOT gate \(x \mapsto 1 - x_0\), and, for every arity \(n\), the unbounded fan-in AND gate \(x \mapsto \prod _{i} x_i\).
For a finite index type \(\iota \), a finite type \(\beta \) and a decidable predicate \(P\) on \(\beta \), the number of functions \(f : \iota \to \beta \) with \(P(f(i))\) for all \(i\) equals \(\left\lvert \{ b : P(b)\} \right\rvert ^{\left\lvert \iota \right\rvert }\).
Let \(\mathrm{Bad}\) be a finite set of elements of \(\alpha \), let \(\mathrm{Fail} : \alpha \to \beta \to \mathrm{Prop}\) be decidable with \(\beta \) finite and nonempty, and let \(C\) be a natural number. If for every \(a \in \mathrm{Bad}\) we have \(\left\lvert \{ b : \mathrm{Fail}(a,b)\} \right\rvert \cdot C \le \left\lvert \beta \right\rvert \), then there exists a single \(b \in \beta \) with \(\left\lvert \{ a \in \mathrm{Bad} : \mathrm{Fail}(a,b)\} \right\rvert \cdot C \le \left\lvert \mathrm{Bad}\right\rvert \).
The map \(\mathbb {Z}/p \to \mathrm{Fin}\, 2\) sending \(a\) to \(1\) if \(a = 1\) and to \(0\) otherwise. It is intended to be applied only to values lying in \(\{ 0,1\} \).
If \(a \in \{ 0,1\} \subseteq \mathbb {Z}/p\), then casting \(\texttt{ACP.bitify}\, (a)\) back into \(\mathbb {Z}/p\) through \(\mathbb {N}\) recovers \(a\).
For every \(a \in \mathbb {Z}/p\) with \(p\) prime,
If \(a \in \{ 0,1\} \subseteq \mathbb {Z}/p\), then \(1 - (1-a)^{p-1}\) equals the cast of \(\texttt{ACP.bitify}\, (a)\) into \(\mathbb {Z}/p\).
The gate operation of arity width on Boolean inputs that outputs \(1\) when the sum of its inputs, cast into \(\mathbb {Z}/p\), is \(0\), and outputs \(0\) otherwise.
The \(\mathrm{AC}^0[p]\) gate set: the \(\mathrm{AC}^0\) gates (identity, NOT, unbounded AND) together with the unbounded \(\mathrm{MOD}_p\) gate of every arity.
Given polynomials \(P_1,\dots ,P_{\mathrm{width}}\) over \(\mathbb {Z}/p\) and a random seed consisting of \(\ell \) subsets \(S_1,\dots ,S_\ell \) of the input positions, the approximator is
The polynomial \(1 - \bigl(\sum _i P_i\bigr)^{p-1}\) over \(\mathbb {Z}/p\), which computes the \(\mathrm{MOD}_p\) predicate exactly on Boolean values.
The value-level analogue of the randomized OR approximator: for \(v : \mathrm{Fin}\, \mathrm{width} \to \mathbb {Z}/p\) and subsets \(S_1,\dots ,S_\ell \),
For \(v : \mathrm{Fin}\, \mathrm{width} \to \mathbb {Z}/p\), the quantity \(1 - \prod _{k}\bigl(1 - v_k^{\, p-1}\bigr)\), which detects whether some coordinate of \(v\) is nonzero.
The total degree of \(\texttt{ACP.approxOr}\) applied to \(P_1,\dots ,P_{\mathrm{width}}\) and a seed \(S\) is at most \((p-1)\, \ell \cdot \sup _i \deg (P_i)\).
The total degree of \(\texttt{ACP.exactMod}\) applied to \(P_1,\dots ,P_{\mathrm{width}}\) is at most \((p-1)\cdot \sup _i \deg (P_i)\).
For a nonzero vector \(v : \mathrm{Fin}\, n \to \mathbb {Z}/p\), the number of subsets \(s \subseteq \mathrm{Fin}\, n\) with \(\sum _{i \in s} v_i = 0\) is at most half of all \(2^n\) subsets; formally, twice that count is at most the total number of subsets.
Evaluating \(\texttt{ACP.approxOr}\, (P, S)\) at a point \(y\) gives the same result as applying the value-level approximator \(\texttt{ACP.approxOr\_ val}\) to the evaluated inputs \(i \mapsto P_i(y)\) with the same seed \(S\).
For \(v : \mathrm{Fin}\, \mathrm{width} \to \mathbb {Z}/p\) and a seed \(S\), the value-level approximator differs from the OR detector if and only if \(v \ne 0\) and every seed subset has vanishing sum, i.e. \(\sum _{i \in S_k} v_i = 0\) for all \(k\).
For a nonzero \(v\), the number of seeds \(S : \mathrm{Fin}\, \ell \to \mathrm{Finset} (\mathrm{Fin}\, \mathrm{width})\) on which the value-level approximator disagrees with the OR detector, multiplied by \(2^\ell \), is at most the total number of seeds.
The type of seeds \(\mathrm{Fin}\, \ell \to \mathrm{Finset}(\mathrm{Fin}\, \mathrm{width})\), i.e. \(\ell \) independent subset choices, has cardinality \(2^{\mathrm{width}\cdot \ell }\).
Without any nonvanishing hypothesis on \(v\): the number of seeds on which the value-level approximator disagrees with the OR detector, multiplied by \(2^\ell \), is at most the total number of seeds.
The list of all polynomials \(\texttt{ACP.approxOr}\, (P,S)\), one entry per random seed \(S\). It is a list rather than a set, so a polynomial arising from several seeds appears with the corresponding multiplicity.
The list \(\texttt{ACP.approxOrPolyList}\) has length \(2^{\mathrm{width}\cdot \ell }\).
Fix an evaluation point \(y\). The number of seeds \(S\) for which \(\texttt{ACP.approxOr}\, (P,S)\) evaluated at \(y\) differs from \(1 - \prod _k \bigl(1 - P_k(y)^{p-1}\bigr)\), multiplied by \(2^\ell \), is at most \(2^{\mathrm{width}\cdot \ell }\); that is, at most a \(2^{-\ell }\) fraction of seeds fail at \(y\).
There is a list \(Ps\) of polynomials, namely \(\texttt{ACP.approxOrPolyList}\, (P)\), of length \(2^{\mathrm{width}\cdot \ell }\), every entry of which has total degree at most \((p-1)\ell \cdot \sup _i \deg (P_i)\), and such that for every evaluation point \(y\) the number of seeds failing to compute the OR value at \(y\), times \(2^\ell \), is at most the length of \(Ps\).
The De Morgan dual of the OR approximator: \(1 - \texttt{ACP.approxOr}\, (1 - P, S)\), where the approximator is applied to the negated inputs \(i \mapsto 1 - P_i\).
The total degree of \(\texttt{ACP.approxAnd}\, (P,S)\) is at most \((p-1)\, \ell \cdot \sup _i \deg (P_i)\), the same bound as for the OR approximator.
The list of all polynomials \(\texttt{ACP.approxAnd}\, (P,S)\), one entry per random seed \(S\).
The list \(\texttt{ACP.approxAndPolyList}\) has length \(2^{\mathrm{width}\cdot \ell }\).
Fix an evaluation point \(y\). The number of seeds \(S\) for which \(\texttt{ACP.approxAnd}\, (P,S)\) evaluated at \(y\) differs from \(\prod _k \bigl(1 - (1 - P_k(y))^{p-1}\bigr)\), multiplied by \(2^\ell \), is at most \(2^{\mathrm{width}\cdot \ell }\).
There is a list \(Ps\) of polynomials, namely \(\texttt{ACP.approxAndPolyList}\, (P)\), of length \(2^{\mathrm{width}\cdot \ell }\), every entry of which has total degree at most \((p-1)\ell \cdot \sup _i \deg (P_i)\), and such that for every evaluation point \(y\) the number of seeds failing to compute the AND value at \(y\), times \(2^\ell \), is at most the length of \(Ps\).
Every gate operation in \(\texttt{ACP.ACp\_ GateOps}\) is one of the following: the identity gate on a single input, the NOT gate \(x \mapsto 1 - x_0\), an unbounded AND gate \(x \mapsto \prod _i x_i\) of some arity \(n\), or a \(\texttt{ACP.modGateOp}\) of some arity \(n\).
If all values \(\mathrm{inputs}_i\) lie in \(\{ 0,1\} \subseteq \mathbb {Z}/p\), then \(1 - \bigl(\sum _i \mathrm{inputs}_i\bigr)^{p-1}\) equals the cast into \(\mathbb {Z}/p\) of the output of the \(\mathrm{MOD}_p\) gate applied to the booleanized inputs \(i \mapsto \texttt{ACP.bitify}\, (\mathrm{inputs}_i)\).
If all values \(\mathrm{inputs}_i\) lie in \(\{ 0,1\} \subseteq \mathbb {Z}/p\), then \(\prod _i \bigl(1 - (1 - \mathrm{inputs}_i)^{p-1}\bigr)\) equals the cast into \(\mathbb {Z}/p\) of \(\prod _i \texttt{ACP.bitify}\, (\mathrm{inputs}_i)\), the Boolean AND of the booleanized inputs.
Let \(\mathrm{op}\) be a gate in \(\texttt{ACP.ACp\_ GateOps}\) and let \(P_i\) be polynomials over \(\mathbb {Z}/p\) computing its inputs. Then there exist a nonempty finite seed type \(\mathrm{Seed}\) with decidable equality and a family \(P : \mathrm{Seed} \to \mathrm{MvPolynomial}(\mathrm{Fin}\, n, \mathbb {Z}/p)\) such that every \(P(s)\) has total degree at most \((p-1)\ell \cdot \sup _i \deg (P_i)\), and for every Boolean input \(x\), writing \(y_j = x_j\) cast into \(\mathbb {Z}/p\) and \(\mathrm{inputs}_i = P_i(y)\), if all \(\mathrm{inputs}_i\) lie in \(\{ 0,1\} \) then the number of seeds \(s\) with \(P(s)(y)\) different from the gate value \(\mathrm{op}.\mathrm{func}(i \mapsto \texttt{ACP.bitify}(\mathrm{inputs}_i))\), multiplied by \(2^\ell \), is at most \(\left\lvert \mathrm{Seed}\right\rvert \).