# Parity function

How is the parity function defined in standard way if inputs are in $\{-1,+1\}$ instead of $\{0,1\}$. For $\{0,1\}$, parity is $x_1\oplus x_2\oplus\cdots\oplus x_{n-1}\oplus x_n$. I am looking for how is inner product mod $2$ defined if inputs are in $\{-1,+1\}$. Is it $\frac{1}{4}\sum_i(x_i+1)(y_i+1)\mod 2$ or just $\sum_i x_iy_i \mod 2$?

What if one replaces $2$ by $p$ a prime or $N$ a composite?

In the representation of bits by $\pm 1$, the most important aspect is in fact the sign. In fact the best way to describe the mapping from $\{0,1\}$ to $\{-1,+1\}$ is the function $f(x) = (-1)^x$. This is a representation in which logical AND and OR are awkward at best, but PARITY is dead easy. Let $a = f(x)$, $b = f(y)$, and $c = f(x \oplus y)$: $$c := f(x\oplus y) = f(x + y - 2xy) = (-1)^{x + y - 2xy} = (-1)^{x + y} = f(x) f(y) = ab.$$ Thus, in the sign representation, parities are computed by multiplication.
• $0->1$ and $1->-1$. How about for inner product? – Turbo Dec 9 '14 at 18:39
• @Turbo: I am not sure what you mean either by your remark, or your question, in your comment above. Do you mean to ask how to represent $(x_1 \wedge y_1) \oplus (x_2 \wedge y_2) \oplus \cdots \oplus (x_n \wedge y_n)$? – Niel de Beaudrap Dec 9 '14 at 18:40
• Yes. when inputs are in $\{-1,+1\}$. For $\{0,1\}$ it is just $\sum_ix_iy_j\mod P$. The parity has to agree when using either formulation of inputs. – Turbo Dec 9 '14 at 18:57
• I mean $0\rightarrow 1$ and $1\rightarrow -1$. – Turbo Dec 9 '14 at 18:58
• As I noted in my answer, logical AND is awkward in the sign representation. For $a = (-1)^x$ and $b = (-1)^y$ we can define $\mathrm{AND}(a,b) = 1 + (\tfrac{a+b}{2}) - (\frac{a+b}{2})^2$, and simply express the dot-product as the product of $\mathrm{AND}(a_1,b_2), \mathrm{AND}(a_2,b_2), \ldots, \mathrm{AND}(a_n,b_n)$ as with the boolean representation; but that seems terribly awkward, and I'm not sure when one would want to. – Niel de Beaudrap Dec 9 '14 at 19:44