150 Boolean Analysis — Razborov Smolensky
150.1 Overview
This module completes the Razborov–Smolensky lower bound by transferring the root-cube inapproximability result back to the Boolean \(\mathrm{MOD}_q\) function. Padding by \(q-1\) extra input bits recovers every residue class of the Hamming weight from the zero-residue \(\mathrm{MOD}_q\) predicate; an affine change of variables converts a low-degree approximant of padded \(\mathrm{MOD}_q\) over \(\mathbb {Z}/p\) into low-degree approximants of the residue indicators on the cube \(\{ 1,\omega \} ^n\) over \(\mathbb {F}_{p^{q-1}}\), and a union bound recombines these into an approximant of the root product \(\prod _i x_i\). Combined with the counting lower bound for the root product and the circuit-approximation theorem, this yields Smolensky’s low-degree lower bound for \(\mathrm{MOD}_q\) and the quantitative theorem \(\mathrm{MOD}_q \notin \mathrm{AC}^0[p]\).
150.2 Declarations
Let \(K\) be a field and \(\omega \in K\). A Boolean input \(x \in \{ 0,1\} ^n\) is embedded as the point of the cube \(\{ 1,\omega \} ^n\) whose \(i\)-th coordinate is \(1\) if \(x_i = 0\) and \(\omega \) if \(x_i = 1\).
Let \(K\) be a field, \(\omega \in K\), and let \(x \in \{ 0,1\} ^n\) be a Boolean input. The product of the coordinates of the point of \(\{ 1,\omega \} ^n\) obtained from \(x\) by the embedding \(0 \mapsto 1\), \(1 \mapsto \omega \) equals \(\omega ^{\left\lvert x\right\rvert }\), where \(\left\lvert x\right\rvert = \sum _i x_i\) is the Hamming weight of \(x\).
Let \(K\) be a field and \(\omega \in K\). The \(\omega \)-weight of a point \(x \in \{ 1,\omega \} ^n\) is the number of indices \(i\) with \(x_i = \omega \). Under the Boolean embedding \(0 \mapsto 1\), \(1 \mapsto \omega \), this is the Boolean Hamming weight.
Let \(K\) be a field, \(\omega \in K\), and let \(q\) be a positive natural number. For a residue \(r \in \{ 0,\dots ,q-1\} \), the residue-\(r\) indicator is the \(K\)-valued function on the cube \(\{ 1,\omega \} ^n\) that takes the value \(1\) at \(x\) when the \(\omega \)-weight of \(x\) is congruent to \(r\) modulo \(q\), and \(0\) otherwise.
The Hamming weight of a Boolean input \(x \in \{ 0,1\} ^n\), i.e. the natural number \(\sum _{i} x_i\).
Let \(K\) be a field and let \(q\) be a positive natural number. For a residue \(r \in \{ 0,\dots ,q-1\} \), the Boolean residue-\(r\) indicator is the \(K\)-valued function on Boolean inputs \(x \in \{ 0,1\} ^n\) that is \(1\) when the Hamming weight of \(x\) is congruent to \(r\) modulo \(q\), and \(0\) otherwise.
Let \(K\) be a field and \(\omega \in K\). The \(i\)-th decoded bit of a point \(x \in \{ 1,\omega \} ^n\) is the Boolean value that is \(0\) if \(x_i = 1\) and \(1\) otherwise. When \(\omega \neq 1\) this inverts the Boolean embedding, sending the coordinate value \(1\) to the bit \(0\) and the value \(\omega \) to the bit \(1\).
Let \(q\) be a positive natural number. For a residue \(r \in \{ 0,\dots ,q-1\} \), the number of padding \(1\)-bits needed to shift Hamming-weight residue \(r\) to residue \(0\) modulo \(q\), namely \((q - r) \bmod q\): this is \(0\) when \(r = 0\) and \(q - r\) when \(r \gt 0\).
Let \(K\) be a field, \(\omega \in K\), let \(q\) be a positive natural number, let \(r \in \{ 0,\dots ,q-1\} \), and let \(x \in \{ 1,\omega \} ^n\). The associated padded Boolean input on \(n + (q-1)\) bits has as its first \(n\) bits the decoded bits of \(x\) (bit \(0\) where \(x_i = 1\), bit \(1\) elsewhere), while its final \(q-1\) bits consist of \((q - r) \bmod q\) ones followed by zeros.
Let \(K\) be a field and \(\omega \in K\). For a variable index \(i \in \{ 1,\dots ,n\} \), the affine polynomial \((\omega - 1)^{-1}\, (X_i - 1)\) in \(n\) variables over \(K\). When \(\omega \neq 1\) it decodes a root-cube coordinate as a Boolean value, sending \(1 \mapsto 0\) and \(\omega \mapsto 1\).
Let \(K\) be a field, \(\omega \in K\), and let \(i\) be a variable index. The affine decoder polynomial \((\omega - 1)^{-1}\, (X_i - 1)\) has total degree at most \(1\).
Let \(p\) and \(q\) be primes, let \(K = \mathbb {F}_{p^{q-1}}\), let \(\omega \in K\), and let \(r \in \{ 0,\dots ,q-1\} \). The residue-\(r\) substitution assigns to each of the \(n + (q-1)\) variables a polynomial in \(n\) variables over \(K\): a variable \(X_j\) with \(j \lt n\) is sent to the affine decoder \((\omega - 1)^{-1}\, (X_j - 1)\), while the \(k\)-th padding variable (with \(k = j - n\)) is sent to the constant \(1\) if \(k \lt (q - r) \bmod q\) and to the constant \(0\) otherwise.
Let \(p\) and \(q\) be primes, let \(K = \mathbb {F}_{p^{q-1}}\), let \(\omega \in K\), let \(r \in \{ 0,\dots ,q-1\} \), and let \(P\) be a polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\). The residue-\(r\) restriction of \(P\) is the polynomial in \(n\) variables over \(K\) obtained by extending the coefficients of \(P\) along the canonical embedding \(\mathbb {Z}/p \to K\) and then substituting each variable according to the residue-\(r\) substitution: the first \(n\) variables become the affine root-cube decoders and the padding variables are fixed to the constants encoding residue \(r\).
Let \(p\) and \(q\) be primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\), and let \(r \in \{ 0,\dots ,q-1\} \). For every polynomial \(P\) in \(n + (q-1)\) variables over \(\mathbb {Z}/p\), the residue-\(r\) restriction of \(P\) (a polynomial in \(n\) variables over \(\mathbb {F}_{p^{q-1}}\)) has total degree at most the total degree of \(P\).
Let \(p\) and \(q\) be primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\) with \(\omega \neq 1\), let \(r \in \{ 0,\dots ,q-1\} \), let \(P\) be a polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\), and let \(x \in \{ 1,\omega \} ^n\). Evaluating the residue-\(r\) restriction of \(P\) at \(x\) gives the same value as evaluating \(P\) at the padded Boolean input associated to \((x, r)\) (with bits cast into \(\mathbb {Z}/p\)) and then mapping the result along the embedding \(\mathbb {Z}/p \to \mathbb {F}_{p^{q-1}}\).
Let \(p\) and \(q\) be primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\) with \(\omega \neq 1\), let \(r \in \{ 0,\dots ,q-1\} \), and let \(x \in \{ 1,\omega \} ^n\). Write \(\mathrm{MOD}_q\) for the \(\mathbb {Z}/p\)-valued function on Boolean inputs that is \(1\) when the Hamming weight of its input is divisible by \(q\) and \(0\) otherwise. Then the image in \(\mathbb {F}_{p^{q-1}}\) of \(\mathrm{MOD}_q\) evaluated at the padded Boolean input associated to \((x, r)\) equals the residue-\(r\) indicator of \(x\): it is \(1\) exactly when the \(\omega \)-weight of \(x\) is congruent to \(r\) modulo \(q\), and \(0\) otherwise.
Let \(p\) and \(q\) be primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\) with \(\omega \neq 1\), and fix a residue \(r \in \{ 0,\dots ,q-1\} \). The map sending a root-cube point \(x \in \{ 1,\omega \} ^n\) to its padded Boolean input on \(n + (q-1)\) bits is injective.
Let \(p\) and \(q\) be distinct primes and let \(\omega \in \mathbb {F}_{p^{q-1}}\) satisfy \(\omega ^q = 1\) and \(\omega \neq 1\). Suppose \(P\) is a polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\) of total degree at most \(d\) that disagrees with the \(\mathrm{MOD}_q\) function (the indicator, in \(\mathbb {Z}/p\), that the Hamming weight is divisible by \(q\)) on fewer than \(E\) Boolean inputs of length \(n + (q-1)\). Then there is a family \((R_r)_{r \in \{ 0,\dots ,q-1\} }\) of polynomials in \(n\) variables over \(\mathbb {F}_{p^{q-1}}\) such that each \(R_r\) has total degree at most \(d\) and disagrees with the residue-\(r\) indicator on at most \(E\) points of the cube \(\{ 1,\omega \} ^n\).
Let \(K\) be a field, let \(q\) be a prime, and let \(\omega \in K\) satisfy \(\omega ^q = 1\). For every point \(x \in \{ 1,\omega \} ^n\),
where \(w(x)\) denotes the number of coordinates of \(x\) equal to \(\omega \).
Let \(K\) be a finite field, let \(q\) be a prime, and let \(\omega \in K\) satisfy \(\omega ^q = 1\). For any family \((R_r)_{r \in \{ 0,\dots ,q-1\} }\) of polynomials in \(n\) variables over \(K\), the number of points of \(\{ 1,\omega \} ^n\) at which the combined polynomial \(\sum _{r} \omega ^{r} R_r\) differs from the root product \(\prod _i x_i\) is at most the sum over \(r\) of the number of points at which \(R_r\) differs from the residue-\(r\) indicator.
Let \(K\) be a finite field, let \(q\) be a prime, and let \(\omega \in K\) satisfy \(\omega ^q = 1\) and \(\omega \neq 1\). Given polynomials \(R_r\) in \(n\) variables over \(K\), one for each residue \(r \in \{ 0,\dots ,q-1\} \), each of total degree at most \(d\) and each disagreeing with the residue-\(r\) indicator on at most \(E\) points of \(\{ 1,\omega \} ^n\), there exists a polynomial \(Q\) in \(n\) variables over \(K\) of total degree at most \(d\) that disagrees with the root product \(x \mapsto \prod _i x_i\) on at most \(q \cdot E\) points of the cube.
Let \(p\) and \(q\) be distinct primes and let \(\omega \in \mathbb {F}_{p^{q-1}}\) satisfy \(\omega ^q = 1\) and \(\omega \neq 1\). If \(P\) is a polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\) of total degree at most \(d\) that disagrees with the \(\mathrm{MOD}_q\) function (the indicator that the Hamming weight is divisible by \(q\)) on fewer than \(E\) Boolean inputs, then there exists a polynomial \(Q\) in \(n\) variables over \(\mathbb {F}_{p^{q-1}}\) of total degree at most \(d\) that disagrees with the root product \(x \mapsto \prod _i x_i\) on at most \(q \cdot E\) points of the cube \(\{ 1,\omega \} ^n\).
Let \(p\) and \(q\) be distinct primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\) satisfy \(\omega ^q = 1\) and \(\omega \neq 1\), and let \(E\) and \(e\) be natural numbers with \(q \cdot E \le e\). If \(P\) is a polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\) of total degree at most \(d\) that disagrees with the \(\mathrm{MOD}_q\) function (the indicator that the Hamming weight is divisible by \(q\)) on fewer than \(E\) Boolean inputs, then there exists a polynomial \(Q\) in \(n\) variables over \(\mathbb {F}_{p^{q-1}}\) of total degree at most \(d\) that disagrees with the root product \(x \mapsto \prod _i x_i\) on at most \(e\) points of the cube \(\{ 1,\omega \} ^n\).
Let \(p\) and \(q\) be distinct primes, let \(\omega \in \mathbb {F}_{p^{q-1}}\) satisfy \(\omega ^q = 1\) and \(\omega \neq 1\), and let \(d, E, e\) be natural numbers with \(q \cdot E \le e\). Suppose no polynomial in \(n\) variables over \(\mathbb {F}_{p^{q-1}}\) of total degree at most \(d\) disagrees with the root product \(x \mapsto \prod _i x_i\) on at most \(e\) points of \(\{ 1,\omega \} ^n\). Then every polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\) of total degree at most \(d\) disagrees with the \(\mathrm{MOD}_q\) function (the indicator that the Hamming weight is divisible by \(q\)) on at least \(E\) Boolean inputs.
Let \(p\) and \(q\) be distinct primes, write \(K = \mathbb {F}_{p^{q-1}}\), and let \(d, E, e, B\) be natural numbers with \(q \cdot E \le e\). Assume the counting bounds
where \(N\) is the number of \(K\)-valued functions on the collection of subsets \(S \subseteq \{ 1,\dots ,n\} \) with \(\left\lvert S\right\rvert \le \lfloor n/2 \rfloor + d\). Then every polynomial in \(n + (q-1)\) variables over \(\mathbb {Z}/p\) of total degree at most \(d\) disagrees with the \(\mathrm{MOD}_q\) function (the indicator that the Hamming weight is divisible by \(q\)) on at least \(E\) Boolean inputs.
Let \(p\) and \(q\) be distinct primes and write \(K = \mathbb {F}_{p^{q-1}}\). Let \(F\) be a feed-forward Boolean circuit on \(n + (q-1)\) input bits with a single output and finitely many nodes in each layer, using only \(\mathrm{AC}^0[p]\) gate operations, and suppose that \(F\) computes the \(\mathrm{MOD}_q\) function: on every input, \(F\) outputs \(1\) exactly when the Hamming weight of the input is divisible by \(q\). Let \(\delta , \ell , e, B\) be natural numbers such that \(q \cdot \bigl(\delta \cdot 2^{\, n+(q-1)}\bigr) \le e\), such that \(\sum _{t=0}^{e} \binom {2^n}{t}\, \left\lvert K\right\rvert ^{t} \le B\), and such that \(\left\lvert K\right\rvert ^{2^n} \gt N \cdot B\), where \(N\) is the number of \(K\)-valued functions on the collection of subsets \(S \subseteq \{ 1,\dots ,n\} \) with \(\left\lvert S\right\rvert \le \lfloor n/2 \rfloor + \bigl((p-1)\ell \bigr)^{\mathrm{depth}(F)}\). Then the size of \(F\) (its number of non-input gates) satisfies \(\delta \cdot 2^{\ell } \le \mathrm{size}(F)\).