0
$\begingroup$

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?
$\endgroup$
5
  • $\begingroup$ Are the polynomials over the reals or over $\mathbb{Z}_2$? $\endgroup$
    – Steven
    Sep 17, 2023 at 20:09
  • $\begingroup$ Over the reals. In the case of $\mathbb{Z}_2$, PARITY is just $P(x) = x_1 + \ldots + x_n \mod{2}$. But I'm curious about $\mathbb{R}$ in general. $\endgroup$
    – user163048
    Sep 17, 2023 at 20:12
  • $\begingroup$ Please don't delete your question after receiving an answer. Our mission is to build up a reference library of knowledge that will be useful to others, in the form of questions and answers. So this Q&A is not just for you, but for everyone else in the future. When someone answers your question, they might be answering from the perspective not just of helping you but also helping others in the future, so it might be considered impolite to delete your question after receiving an answer. $\endgroup$
    – D.W.
    Sep 17, 2023 at 20:57
  • $\begingroup$ For the future, please ask only one question per post. If you have multiple questions, they can be posted separately. $\endgroup$
    – D.W.
    Sep 17, 2023 at 20:59
  • 2
    $\begingroup$ What do you call "maximum possible degree" ? $\endgroup$
    – user16034
    Sep 18, 2023 at 11:49

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.