Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

Question

It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$. For example, authors of this paper say that

... any constant depth circuit consisting of only $MOD_q$ gates, $q=p^k$ , is equivalent to a constant degree polynomial over $\mathbb{Z}_p$ and therefore cannot compute the $AND$ function at all regardless of its size.

However, the original Razborov-Smolensky polynomial argument seems to consider only the case where $q$ is a prime. How can we extend this to cover the case where $q$ is a prime power? I'm a bit embarrassed that I was not able to follow the quote above, although it appears to give the answer already...

---

Or in brief:

How to prove that $MOD_p \notin \mathrm{ACC}[q]$, where $(p,q)=1$ and $q$ is a prime power?

Answer 1

For the record, let me summarize what’s mentioned in the comments.

It is a folklore fact that if $q=p^k$, then $\mathrm{AC}^0[p]=\mathrm{AC}^0[q]$. More specifically, $\mathit{MOD}_q$ gates are computable by constant-depth, polynomial-size circuits using $\mathit{MOD}_p$ gates and bounded fan-in $\mathit{AND}$ gates (which can in turn be eliminated if $p>2$).

This can be shown by induction on $k$, using the following easily verifiable number-theoretic fact: $$p^{k+1}\mid x\iff p\mid x\mathrel\&p^k\mid\binom xp.$$ This implies $$\mathit{MOD}_{p^{k+1}}(x_1,\dots,x_n)\equiv\mathit{MOD}_p(x_1,\dots,x_n)\land \mathit{MOD}_{p^k}(\dots,x_{i_1}\land x_{i_2}\land\dots\land x_{i_p},\dots),$$ where the arguments of the $\mathit{MOD}_{p^k}$ gate on the right-hand side are all $\binom np$ possible conjunctions of $p$-element subsets of $\{x_1,\dots,x_n\}$.

It is also easy to see that a Boolean function is computable by a constant-degree polynomial over $\mathbb F_p$ iff it is computable by a constant-depth circuit using $\mathit{MOD}_p$ gates and bounded fan-in $\mathit{AND}$ gates. (Polynomial size comes for free here.)

As a consequence, if $m$ is an integer with prime factorization $m=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, we have $$\mathrm{AC}^0[m]=\mathrm{AC}^0[p_1,p_2,\dots,p_k]=\mathrm{AC}^0[\operatorname{rad}(m)],$$ where $\operatorname{rad}(m)=p_1p_2\cdots p_k$ is the square-free kernel of $m$.

Answer 2

The result appears as Theorem 7 in the following paper by Smolensky:

Smolensky, Roman. "On representations by low-degree polynomials." Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 1993. https://doi.org/10.1109/SFCS.1993.366874

The techniques in this paper are still algebraic but slightly different (and more general) than what people usually teach as the "Razborov-Smolensky polynomial argument".

Yuval Filmus has a nice set of notes on the above paper as well, with more exposition and details in some places: http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf

Update: Given that Smolensky's paper is quite terse, let me say a few words about how the implied proof proceeds. Since Filmus' notes, linked above, are fairly thorough, I won't try to be completely precise, but instead give the main technical ideas.

1) The connection between $ACC[q]$ and polynomials seems to indeed be the standard one. More precisely, if there is a constant-depth circuit computing $F$, then there exists a polynomial $P$ of polylogarithmic degree that approximates $F$, where the degree depends on the depth. Unless I'm mistaken, it is actually straightforward to see that this result works even when $q$ is a prime power. See for example section 4 in these lecture notes from MIT.

2) Then, the goal is to prove that such low-degree polynomials cannot approximate the $MOD_p$ function when $(p,q) = 1$, which shows that $MOD_p \notin ACC[q]$.

3) To prove this, Smolensky establishes in Theorem 4 a relationship between (i) the Hilbert function for the one-set of $F$, that is, the set $S = \{x \mid F(x) = 1\}$, and (ii) the ability of any low-degree polynomial $P$ to approximate $F$, where $F = MOD_p$ for this question. Theorem 4 is proved in the paper (albeit in quite a terse way, hence the pointer to Filmus' notes).

4) The final step is to analyze the Hilbert function of the one-set of $F$. Smolensky refers to his proof for Parity for the "proof" of $MOD_p$ case. What actually needs to be shown is that the Hilbert function on $S$ is as large as possible, for all degrees less than $n/2$. In his words "...we proved that over $S$ there is no linear relation among monomials of degree smaller than $n/2$. Hence for $m < n/2$, $l^a_m(S)$ are as large as possible." The reason he omits the formal proof is that it is indeed the same as the case for parity, once you have the equation (8) that he provides.

I hope this makes sense, with the omitted details being medium-hard exercises.