$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?

Question

Now, I have the following conjecture.

$\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$.

However, I am at a loss at how to realize/see this. Could anybody help me out?

Answer 1

Consider what happens when you feed into a majority gate the the inputs $x_1,\ldots,x_k$ and $k-1$ zeroes. You get an $\mathsf{AND}$ gate. If you feed into it $k-3$ zeroes, you get a gate corresponding to $x_1+\cdots+x_k \geq k-1$. Using similar ideas, you can construct a constant-depth circuit over the basis $\{\lnot,\mathsf{MAJ}\}$ that computes $x_1+\cdots+x_k = \ell$ and so $\mathsf{MOD}_{2017}$.

If you're not allowed to use constants but there is a tie-breaking rule for $\mathsf{MAJ}$, then you can implement constants using $\mathsf{MAJ}(x_1,\lnot x_1)$, whose constant value will depend on the tie-breaking rule.

If you're not allowed to use constants and every majority gate needs to have an odd number of inputs, then it is generally not possible to construct such a circuit. Indeed, suppose that you plug $x_i = x_1$ for all $i>1$, and that $k$ is chosen so that the output is constant whatever the value of $x_1$ is (this depends on your definition of $\mathsf{MOD}$, which you haven't supplied). On the other hand, you can prove by induction that every gate computes either $x_1$ or $\lnot x_1$, and in particular not a constant function