# Computing MOD_4 function using MOD_2, OR, AND, NOT gates

Define the $\newcommand{\MOD}{\text{MOD}}\MOD_q$ function from $\{0,1\}^n \rightarrow \{0,1\}$ as follows:

Let $x_1,\cdots,x_n$ be the input. Then $\MOD_q(x_1,\cdots,x_n)=0$ if the number of 1's in $x_1,\dots,x_n$ is divisible by $q$; $\MOD_q(x_1,\cdots,x_n)=1$ otherwise.

I want to compute $\MOD_4$ using a constant depth circuit using only the following gates: $\MOD_2$ gates and the usual AND, OR, NOT gates. Gate fan-in is unbounded. Technically I want to show that $\MOD_4 \in \text{ACC}_0[2]$, where $\text{ACC}_0[2]$ means alternating circuit of constant depth with parity gates ($\MOD_2$ counters). Or more generally, I want to show that $\MOD_{p^k} \in \text{ACC}_0[p]$.

Can this be done? Is there a way to compute $\MOD_4$ using $\MOD_2$, AND, OR, and NOT gates?

My attempt: If I pass the input through a $\MOD_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD_4$ is also $= 1$. But $\MOD_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.

• Hint: Compute running sums $y_i = x_1 \oplus \cdots \oplus x_i$; you want to know whether $y_n = 0$ and the number of times that the sequence $y_1,\ldots,y_n$ changed from 1 to 0 is even. – Yuval Filmus Apr 22 '16 at 11:22
• @Raphael The question here is to show that MOD4 is in AC0[2], the class of uniform constant-depth circuits with parity gates ("I want to compute MOD4..."). It's a standard question in circuit complexity. You might be surprised that MOD3 is not in AC0[2]. So something is going on here. – Yuval Filmus Apr 22 '16 at 12:30
• @Raphael, it's a standard question in Boolean circuit complexity. Explaining background will take a lot of time. I have read in Sanjeev Arora, Boaz Barak textbook that $MOD_p$ function cannot be computed using $MOD_q$ gates (besides AND, OR, NOT) , where $p, q$ are distinct primes. – Pranav Bisht Apr 22 '16 at 17:06
• @YuvalFilmus Thanks for the nice hint! But how will I capture the flips in parity using a constant depth circuit. – Pranav Bisht Apr 22 '16 at 17:21
• @PranavBisht Be resourceful. – Yuval Filmus Apr 22 '16 at 20:10

How do we "halve" the number of ones? The idea is to consider the running sums $$y_i = x_1 \oplus \cdots \oplus x_i.$$ Each time $x_i = 1$, we have $y_{i+1} \neq y_i$. Half the time, $y_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.
• I thought of following solution as per your construction: First at level 1, I will have $n$ parity gates each computing $y_i$. Then at level 2, for each pair $(y_i,y_{i+1})$ I will compute $y_i \wedge \overline{y_{i+1}}$ so as to compute number of transitions from 1 to 0. Then at third level, I will have a single parity taking as input, the output of ANDs of 2nd level. Finally at level 4, I will compute AND between $y_n$ and the output of parity gate at third level. (to check whether no of inputs were even at first place) – Pranav Bisht Apr 24 '16 at 5:39