# For what c is division by c in AC0?

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can we do it with a constant depth circuit for every $c$? What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.

## 1 Answer

For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}})$$

It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$. Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$.

As noted by Emil in the comments there is an easy reduction for odd prime $c$ from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to $x\bmod c$ with binary input: we use only input bits which are multiples of $p-1$ and use FLT ($2^{(p-1)i} \bmod p = 1$).

• The same argument applies to any $c$ which is not a power of 2. – Emil Jeřábek Dec 2 '14 at 23:33
• That $x\bmod c$ is not AC^0 for other $c$ is easy to show: for instance, we can assume $c=p$ is an odd prime, and then you can reduce MOD_p to it by using every $(p-1)$th bit. Or you can apply the Barrington-Thérien classification: it's a regular language, and its syntactic monoid is a nontrivial group. – Emil Jeřábek Dec 2 '14 at 23:42
• @Emil Jerabek: Thanks, this was exactly the help i needed :) – daniello Dec 2 '14 at 23:52