1
$\begingroup$

I have question about Computational Comlexity, the following statement can be found in $AC^0$ Circuits Cannot Compute PARITY.

Each $n$-varibale polynomial over $\mathbb{Z}_3$ defines a function from $\left \{0,1\right \}^n$ to $\mathbb{Z}_3$.

  • $1-x_1$, defines $NOT(x_1)$, which is very convincing and very easy to check,

when $x_1=1, 1-x_1=1-1=0=NOT(1)$, very easy and pretty straightforward

  • $x_1…x_n$ defines $AND(x_1,..x_n)$, which is also easy to check.
  • $1-1((1-x_1)…(1-x_n))$ defines $OR(x_1,…,x_n)$, less straightforward, but still very easy to check.

when it comes to $MOD_3$ function the polynomial became more complicated $(x_1 + … + x_n)^2$ over $\mathbb{Z}_3$ represents $MOD_3$ function.I have no idea how to check this relationship, maybe $\mathbb{Z}_3$ should somehow help me to check it, because in three previous examples I didn't know how to use the fact that the representation is correct on $\mathbb{Z}_3$. $MOD_3$ is 1 if and only if the sum of its input is non-zero modulo 3.

The questions are:

  1. how to verify the relationship between $(x_1 + … + x_n)^2$ over $\mathbb{Z}_3$ and $MOD_3$.
  2. What is so special in $\mathbb{Z}_3$, why we cannot use any other field.

1 Answers 1

3

$\begin{eqnarray}{\bf Hint} &&\rm\ MOD_3(x_1,\ldots,x_n) \equiv 1\\ \iff &&\rm \ \,x_1+\,\cdots +x_n\ \not\equiv\ 0 \pmod 3\ \ \ by\ \ definition \\ \iff &&\rm\ \, x_1+\,\cdots + x_n\ \equiv \pm 1\!\!\!\!\pmod 3\\ \iff &&\rm (x_1+\,\cdots + x_n)^2\! \equiv 1\! \pmod 3 \end{eqnarray}$

So, as you see, what's special about $\,\Bbb Z_3\,$ above, is $\rm\:x\not\equiv 0\iff x^2\equiv 1$