# Why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, $p$ and $q$ prime

I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $$p$$ gates cannot be computed by $$ACC^0[q]$$ circuits, where $$p$$ and $$q$$ are distinct primes. The book proves it for $$p=2$$ and $$q=3$$, and I am facing difficulties generalizing this result for arbitrary $$p$$ and $$q$$.

The proof uses two lemmas. The first one states that any $$ACC^0[3]$$ circuit can be approximated via a low degree polynomial $$\in F_3[x]$$. The change in the first lemma to generalize it to arbitrary primes, $$p$$ and $$q$$, is straightforward.

But in the second lemma, where they changed $$f\colon\{0,1\}^n\to\{0,1\}$$ to $$f\colon\{-1,1\}^n\to\{-1,1\}$$ and defined a function $$\prod_{i=1}^n y_i$$ which represents parity, I do not quite get how to generalize to arbitrary $$p$$ and $$q$$.

• Try replacing $\{-1,1\}$ with the set of $p$th roots of unity. Oct 3 '20 at 10:45
• How to change $\{0,1\}$ to $\{1,\zeta_p\}$ without changing the criteria $deg(f)<n^{1/2}$ ? Oct 3 '20 at 14:17
• I don't understand your question. The polynomial $\prod_{i=1}^n y_i$ has degree $n$. Oct 3 '20 at 14:17
• I mean what transformation should I use? Oct 3 '20 at 14:21
• How about $x \mapsto 1 + (\zeta_p-1)x$? It has degree 1, just like the special case $x \mapsto 1-2x$. Oct 3 '20 at 14:22