Razborov-Smolensky and the Limits of Modulo Gates

The switching lemma stops at parity. Every attempt to push a constant-depth lower bound past a circuit that can compute XOR runs into the same obstruction: a parity gate on free variables has no bounded-width CNF or DNF, so the restriction argument has nothing to collapse. The class $\mathrm{AC}^0[p]$ — constant depth, unbounded fan-in AND and OR, plus gates computing the sum of their inputs modulo a prime $p$ — is where the obstacle first appears, and the technique that clears it is algebraic rather than combinatorial.

Replacing gates by polynomials

The polynomial method changes the representation. Instead of simplifying a circuit under a restriction, it replaces each gate with a polynomial over a finite field and tracks the degree.

Fix a prime $p$ and work over $\mathbb{F}_p$. A MOD-$p$ gate on $k$ inputs is by definition the polynomial $\sum_i x_i$ evaluated in the field, a linear object. An AND gate is the product $\prod_i x_i$, degree $k$. An OR gate is harder: over $\mathbb{F}_p$, the disjunction of $k$ bits is not a low-degree polynomial, because it must vanish on the all-zero input and be nonzero on $2^k - 1$ others.

That last problem is solved by approximation rather than exact representation. The identity

$$\mathrm{OR}(x_1, \ldots, x_k) = 1 - \prod_i (1 - x_i)$$

holds over the integers but has degree $k$. Fermat’s little theorem rescues the degree: for $x \in {0,1}$, the value $x^{p-1}$ equals $x$ when $x = 1$ and is undefined-looking but equal to 0 when $x = 0$, since $0^{p-1} = 0$. So over $\mathbb{F}_p$ the OR of $k$ bits is

$$\mathrm{OR}(x) = 1 - \prod_i (1 - x_i)^{p-1},$$

still degree $k(p-1)$, which does not help. The actual construction is probabilistic and approximate: there exists a polynomial of degree $O(\log k)$ that agrees with OR on all but a $1/k$ fraction of inputs, obtained by sampling a random subset of the inputs and applying a symmetric polynomial. The error is what the method tolerates, and it accumulates across the circuit’s gates.

The degree bound

The central lemma says: if a function is computed by a depth-$d$, size-$s$ circuit over the basis ${\wedge, \vee, \mathrm{MOD}_p}$ with unbounded fan-in, then it is computed by a polynomial over $\mathbb{F}_p$ of degree at most $O(\log s)^{d}$ — the exact constant in the exponent depends on the depth and on the approximation error tolerated at each gate.

The induction is over depth. A MOD-$p$ gate is linear, degree 1. An AND or OR gate of fan-in $k$ is replaced by the approximate polynomial of degree $O(\log k)$, and since $k \le s$, the degree contributed per level is $O(\log s)$. Composing $d$ levels multiplies the degrees, giving $(\log s)^{d}$ up to constants. Composition is where the approximation error compounds: each gate’s replacement is correct on all but a small fraction of inputs, and the fraction of inputs on which the composed polynomial deviates is bounded by the sum of the per-gate error rates via a union bound over the circuit’s gates. Choosing the error rate per gate as $1/(4s)$ keeps the total below $1/4$, which is enough for the contradiction that follows.

# Degree accounting, not an implementation: each level of the circuit
# multiplies the polynomial degree by the cost of simulating one wide gate.
def degree_bound(size, depth, log_factor=1):
    import math
    per_level = log_factor * math.log2(max(size, 2))
    return per_level ** depth

# For size n^c and depth 3, the bound is O((c log n)^3): polylogarithmic,
# which is what makes it incomparable with a linear-degree requirement.

Why MOD-q resists a MOD-p circuit

The lower bound follows from a degree gap. Over $\mathbb{F}_p$, the function MOD-$q$ on $n$ bits — output 1 when the number of ones is divisible by $q$ — requires a polynomial of degree $\Omega(n)$ when $q \ne p$.

The reason is a counting argument on the polynomial’s values. Suppose a polynomial $P$ of degree $D$ agrees with MOD-$q$ on all $2^n$ inputs. Consider the $q$-th roots of unity in an extension field of $\mathbb{F}_p$; since $q \ne p$, the extension contains a primitive $q$-th root $\omega$, and the function $\omega^{\sum x_i}$ takes the value 1 exactly when the sum is divisible by $q$. Symmetrising, MOD-$q$ is a linear combination of the characters $\omega^{j \sum x_i}$ for $j = 0, \ldots, q-1$. Each character is a product of independent terms, and a polynomial that computes a product of $n$ independent nonconstant factors must have degree at least $n$ in the worst case — more precisely, the space of functions spanned by low-degree polynomials cannot contain a function whose Fourier expansion has full support on the cube in the relevant basis. The formal statement, due to Smolensky, is that any polynomial over $\mathbb{F}_p$ computing MOD-$q$ exactly has degree $\Omega(n)$, and even approximating it within $1/3$ requires degree $\Omega(n)$.

The two bounds do not meet. A depth-$d$ circuit over ${\wedge, \vee, \mathrm{MOD}_p}$ yields a polynomial of degree $(\log s)^{O(d)}$, which for polynomial size and constant depth is polylogarithmic in $n$. MOD-$q$ needs linear degree. No polynomial-size constant-depth circuit over the $p$-basis computes MOD-$q$, for any two distinct primes.

What this establishes about ACC0

The class $\mathrm{ACC}^0$ is $\mathrm{AC}^0$ with MOD-$m$ gates for a fixed modulus $m$. The Razborov-Smolensky theorem separates $\mathrm{AC}^0[p]$ from $\mathrm{AC}^0[q]$ for distinct primes, which means that adding a modulo gate to a constant-depth circuit genuinely increases its power, and that the resulting classes form a family rather than a single level.

Two structural consequences follow and are used elsewhere. $\mathrm{ACC}^0$ is contained in $\mathrm{TC}^0$, since a MOD-$m$ gate can be computed by a constant-depth circuit of majority gates — count the ones with a threshold tree, then test divisibility by a fixed $m$ with a finite lookup, both of constant depth and polynomial size. And $\mathrm{ACC}^0$ is not contained in $\mathrm{AC}^0$, since parity alone is in the first and outside the second by the switching lemma. The chain $\mathrm{AC}^0 \subsetneq \mathrm{ACC}^0 \subseteq \mathrm{TC}^0 \subseteq \mathrm{NC}^1$ is the current state of the bottom of the depth hierarchy, with the middle inclusion unresolved.

The method’s blind spot is the composite modulus. When $m$ has at least two distinct prime factors, MOD-$m$ is not a linear function over any single field: by the Chinese remainder theorem it decomposes into a tuple of modular conditions, and a gate that tests all of them at once is not the linear map that the degree analysis needs. Exact polynomial representations still exist over a ring, but the approximation argument depends on field structure to bound the number of inputs on which a low-degree polynomial can deviate, and that bound has no ring analogue. No polynomial-method bound is known for $\mathrm{ACC}^0$ with a composite modulus, and that gap is exactly where Williams’ later result operates from the other direction.

Where the algebraic argument sits relative to the combinatorial one

The two methods are not interchangeable, and comparing their reach clarifies what each one measures.

The switching lemma bounds the width of a formula after restriction. It applies to gates whose output is determined by a small set of inputs, and it fails on any gate that depends on all its inputs at once. The polynomial method bounds the degree of a polynomial. It applies to gates that are low-degree over some field, which includes MOD-$p$ and excludes MOD-$q$ for $q \ne p$ — the exclusion is the theorem, not a limitation of the proof.

Neither method reaches $\mathrm{TC}^0$ in its general form. The degree bound says little about threshold circuits built from majority gates, and the combinatorial argument has no analogue of the switching step for a gate whose value depends on the exact count of its inputs rather than on any single one. Finding a technique that separates $\mathrm{TC}^0$ from $\mathrm{NC}^1$ is an open problem, and the two methods here are the standard illustrations of why the known toolkit does not supply one.

There is a further constraint on the algebraic method that the natural proofs barrier makes precise. The property “cannot be approximated by a low-degree polynomial over $\mathbb{F}_p$” is large — a random function has high degree with overwhelming probability — and it is constructive, since the degree of a function can be computed from its truth table by linear algebra over the field in time exponential in $n$ but polynomial in $2^n$. A property of that shape is exactly what the barrier rules out as a route to general circuit lower bounds, and the Razborov-Smolensky theorem escapes only because it targets a restricted class: the argument never claims anything about circuits with negations at every gate, and the low-degree property is not useful against general polynomial-size circuits.

The degree, stated as a resource

For a circuit of size $s$ and depth $d$ over ${\wedge, \vee, \mathrm{MOD}_p}$, the polynomial degree is at most $O(\log s)^{d}$. Three readings of that expression are worth keeping.

Doubling the size squares the logarithm, so size is exponentially more valuable than depth for this measure. A circuit with $s = 2^{\sqrt{n}}$ and constant depth reaches degree $n^{\Theta(1)}$, which is enough to compute MOD-$q$ and explains why the lower bound is a statement about polynomial size and not about size in general.

Increasing depth from $d$ to $d+1$ multiplies the exponent by $\log s$, so a depth increase of one can lift a polylogarithmic degree to a polynomial one. This is the algebraic counterpart of the $n^{1/(d-1)}$ degradation in the switching lemma, and it is why both methods produce hierarchies rather than single separations.

And the degree bound is tight for the gates it covers: a MOD-$p$ gate is exactly linear, so a circuit consisting only of modulo gates has degree 1 regardless of size or depth, and the bound’s dependence on $s$ comes entirely from the AND and OR gates in between. Removing those gates removes the bound’s content, which is another way of saying that the theorem is about the interaction between wide Boolean gates and modular counting, not about modular counting alone.