<p>For the record, let me summarize what’s mentioned in the comments.</p>

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

<p>This can be shown by induction on <span class="math-container">$k$</span>, using the following easily verifiable number-theoretic fact:
<span class="math-container">$$p^{k+1}\mid x\iff p\mid x\mathrel\&amp;p^k\mid\binom xp.$$</span>
This implies
<span class="math-container">$$\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),$$</span>
where the arguments of the <span class="math-container">$\mathit{MOD}_{p^k}$</span> gate on the right-hand side are all <span class="math-container">$\binom np$</span> possible conjunctions of <span class="math-container">$p$</span>-element subsets of <span class="math-container">$\{x_1,\dots,x_n\}$</span>.</p>

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

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

CC BY-SA 4.0
2019-06-24T17:39:11.900Z
2019-06-24T17:39:11.900Z
Emil Jeřábek
<p>The result appears as Theorem 7 in the following paper by Smolensky:</p>

<p>Smolensky, Roman. "On representations by low-degree polynomials." Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 1993. 
<a href="https://doi.org/10.1109/SFCS.1993.366874" rel="nofollow noreferrer">https://doi.org/10.1109/SFCS.1993.366874</a></p>

<p>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".</p>

<p>Yuval Filmus has a nice set of notes on the above paper as well, with more exposition and details in some places:
<a href="http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf" rel="nofollow noreferrer">http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf</a> </p>

<p><strong>Update:</strong> 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.</p>

<p>1) The connection between <span class="math-container">$ACC[q]$</span> and polynomials seems to indeed be the standard one. More precisely, if there is a constant-depth circuit computing <span class="math-container">$F$</span>, then there exists a polynomial <span class="math-container">$P$</span> of polylogarithmic degree that approximates <span class="math-container">$F$</span>, where the degree depends on the depth. Unless I'm mistaken, it is actually straightforward to see that this result works even when <span class="math-container">$q$</span> is a prime power. See for example section 4 in <a href="https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-spring-2016/lecture-notes/MIT18_405JS16_Razborov.pdf" rel="nofollow noreferrer">these lecture notes from MIT</a>.</p>

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

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

<p>4) The final step is to analyze the Hilbert function of the one-set of <span class="math-container">$F$</span>. Smolensky refers to his proof for Parity for the "proof" of <span class="math-container">$MOD_p$</span> case. What actually needs to be shown is that the Hilbert function on <span class="math-container">$S$</span> is as large as possible, for all degrees less than <span class="math-container">$n/2$</span>. In his words "...we proved that over <span class="math-container">$S$</span> there is no linear relation among monomials of degree smaller than <span class="math-container">$n/2$</span>. Hence for <span class="math-container">$m &lt; n/2$</span>, <span class="math-container">$l^a_m(S)$</span> 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.</p>

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

CC BY-SA 4.0
2019-06-21T21:03:21.150Z
But unfortunately without proof.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-06-21T22:44:28.067Z
I believe you are missing the point that from a circuit with $\textrm{MOD}_{q}$ gates where $q=p^k$ one constructs a polynomial in $\mathbf{Z}_p$ and not $\mathbf{Z}_q$. In Smolensky's original paper this conversion is left to the reader, and was at that point already a folklore construction. The OP asked for a proof of this.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-06-21T19:24:19.687Z
2019-06-21T22:32:47.027Z
2019-06-21T22:32:47.027Z
Cyrus Rashtchian
<p>It seems to be a folklore that we can "handle" <span class="math-container">$\textrm{ACC}[q]$</span> circuits not only for prime <span class="math-container">$q$</span> but prime power <span class="math-container">$q$</span>.
For example, authors of <a href="https://iuuk.mff.cuni.cz/~koucky/papers/acc.pdf" rel="noreferrer">this paper</a> say that</p>

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

<p>However, the original Razborov-Smolensky polynomial argument seems to consider only the case where <span class="math-container">$q$</span> is a prime.
How can we extend this to cover the case where <span class="math-container">$q$</span> 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...</p>

<hr>

<p>Or in brief:</p>

<blockquote>
  <p>How to prove that <span class="math-container">$MOD_p \notin \mathrm{ACC}[q]$</span>, where <span class="math-container">$(p,q)=1$</span> and <span class="math-container">$q$</span> is a prime power?</p>
</blockquote>

CC BY-SA 4.0
2019-06-02T09:42:03.650Z
@EmilJeřábek Would you be so kind to give some references, such as the title of a relevant paper?
Lwins
CC BY-SA 4.0
2019-06-04T08:33:46.587Z
See for instance Lemma 1 of [this paper](https://doi.org/10.1007/PL00001597) by Tardos and Barrington.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2019-06-04T08:37:56.203Z
The original source is probably [this paper](https://doi.org/10.1137/0213028) by Chandra, Stockmeyer and Vishin, - although just for the special case of $p=2$.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><circuit-complexity><polynomials>
Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power
Lwins
# Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

(Asked by: username_0 on 2019-05-31)

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](https://iuuk.mff.cuni.cz/~koucky/papers/acc.pdf) 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?

**Tags:** cc.complexity-theory, circuit-complexity, polynomials

> **Comments:**
> **username_0**: @EmilJeřábek Would you be so kind to give some references, such as the title of a relevant paper?  
> **username_1**: See for instance Lemma 1 of [this paper](https://doi.org/10.1007/PL00001597) by Tardos and Barrington.  
> **username_1**: The original source is probably [this paper](https://doi.org/10.1137/0213028) by Chandra, Stockmeyer and Vishin, - although just for the special case of $p=2$.  

---

## 2 answers

### Answer by username_2 on 2019-06-24. Score: 4 | Accepted answer

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 by username_3 on 2019-06-21. Score: 4

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](https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-spring-2016/lecture-notes/MIT18_405JS16_Razborov.pdf).

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.

> **Comments:**
> **username_1**: But unfortunately without proof.  
> **username_1**: I believe you are missing the point that from a circuit with $\textrm{MOD}_{q}$ gates where $q=p^k$ one constructs a polynomial in $\mathbf{Z}_p$ and not $\mathbf{Z}_q$. In Smolensky's original paper this conversion is left to the reader, and was at that point already a folklore construction. The OP asked for a proof of this.  

---

