Polynomial representations of Boolean functions

Question

The AND boolean function $AND(x)$ can be represented using the polynomial $P(x) = x_1x_2\cdots x_n$. I have a few questions:

1. Is there a similar polynomial for the PARITY boolean function?
2. Is there a boolean function whose polynomial doesn't have a maximum possible degree?

Answer 1

Any Boolean function of $n$ variables can be realized by a polynomial of degree $n$, using multilinear interpolation.

$$f(x_1, x_2, x_3,\cdots x_n)=(1-x_1)f(0, x_2, x_3,\cdots x_n)+x_1f(1, x_2, x_3,\cdots x_n)$$

and so on inductively.

You can expand the result as a linear combination of your $AND$ polynomials. E.g., in two variables, the function with truth table $(a,b,c,d)$ is

$$a(1-x_1)(1-x_2)+b(1-x_1)x_2+cx_1(1-x_2)+dx_1x_2\\=(a-b-c+d)x_1x_2+(c-d)x_1+(b-d)x_2+d.$$

---

Another method is to implement the Boolean operators by elementary real functions, and systematically substitute in the expressions:

• $\lnot x_1\equiv 1-x_1$,
• $x_1\land x_2\equiv x_1x_2$,
• $x_1\lor x_2\equiv x_1+x_2-x_1x_2$,
• $x_1\oplus x_2\equiv x_1+x_2-2x_1x_2$.

Answer 2

Regarding $1$: $$ \text{PARITY}(x_1,x_2,\dots,x_n) = \frac{1}{2} \cdot(1-2x_1) \cdot (1-2x_2) \cdot \ldots \cdot (1-2x_n) + \frac{1}{2} $$

The idea is that the term $(1-2x_i)$ will be $1$ if $x_i=0$ and $-1$ otherwise. The product of all these terms will have absolute value $1$ and the sign will encode the parity. To map $-1$ and $1$ back to $0$ and $1$ we multiply by $\frac{1}{2}$ and add $\frac{1}{2}$.

Regarding $2$: I'm not sure if this answers the question but every function $f(x_1, x_2, \dots, x_n)$ can be expressed with a polynomial (in $x_1, \dots, x_n$) that is linear in each of the $x_i$.

Let $A = \{ (a_1, \dots, a_n) \in \{-1, 1\}^n \mid f(\frac{a_1}{2}+\frac{1}{2},\dots,\frac{a_n}{2}+\frac{1}{2}) = 1 \}$. In other words $A$ contains all vectors that encode inputs for which $f$ is $1$, with the convention that "false" is represented by $-1$ and "true" is represented by $1$. Consider: $$ \sum_{a_1, \dots, a_n \in A} \prod_{i=1}^n \left( \frac{1}{2} (2x_i-1) a_i + \frac{1}{2} \right) = \sum_{a_1, \dots, a_n \in A} \prod_{i=1}^n \left( x_i a_i -\frac{a_i}{2} + \frac{1}{2}\right) $$

The expression $x_i a_i-\frac{a_i}{2} + \frac{1}{2}$ returns $1$ if $x_i \in \{0,1\}$ and $a_i \in \{-1,1\}$ are both "true" or both "false", and $0$ otherwise. Then the product is $1$ if $x_1,\dots,x_n$ matches $a_1, \dots, x_n$ and $0$ otherwise. Finally, the whole expression is $1$ if $x_1, \dots, x_n$ matches at least one vector in $A$, and $0$ otherwise.