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:
- how to verify the relationship between $(x_1 + … + x_n)^2$ over $\mathbb{Z}_3$ and $MOD_3$.
- What is so special in $\mathbb{Z}_3$, why we cannot use any other field.