1
$\begingroup$

When I was reading a paper about optimization, I encountered to multivariable Boolean polynomials which was undefined. What is the exact definition of a multivariable Boolean polynomial and can you give me an examples of non-negative multivariable Boolean polynomial and one that is not non-negative on $\mathbb R[x_1,...,x_n]$?

$\endgroup$
  • 1
    $\begingroup$ Is a Boolean polynomial perhaps a polynomial over the finite field $\mathbb F_2$? Possibly modulo $x^2 = x$ for all monomials $x$? If not, a little more context might be useful. $\endgroup$ – Ben Barber Feb 7 '17 at 17:17
  • 1
    $\begingroup$ My immediate interpretation is: a Boolean polynomial in $n$ variables is an element of the free Boolean algebra/ring on an $n$-element set (whose elements are those variables). I don't know what the last question on examples means, since Boolean rings have characteristic $2$ where $1 = -1$. $\endgroup$ – Todd Trimble Feb 7 '17 at 18:12
2
$\begingroup$

A multivariable Boolean polynomial $P$ is an element of $\mathbb{F}_2[x_1,\ldots,x_n]$ and in coding theory and cryptography usually taken to represent a map $P:\mathbb{F}_2^n\rightarrow \mathbb{F}_2.$

It can also be taken to mean an element $P$ of $\mathbb{Z}[x_1,\ldots,x_n]/(x_1^2-x_1,\ldots,x_n^2-x_n)$

In some computer science applications, it is convenient to think of $P$ as a map $P:\{-1,+1\}^n \rightarrow \{-1,+1\}$ via the correspondence $u\in \mathbb{F_2} \leftrightarrow v\in \{-1,+1\},$ given by $v=(-1)^u,$ which has some advantages in that it allows one to write the Hadamard (sometimes termed Walsh-Hadamard) transform in a way consistent with other Fourier transforms, i.e., without needing to use the function $(-1)^{P(x_1,\ldots,x_n)}$ one can use $P$ directly in the sum defining the transform.

Finally, this last formulation of $P$ can be generalized naturally to look at $P:\{-1,+1\}^n\rightarrow \mathbb{R}$ for optimization applications, voting theorems, influences etc. The book ``Analysis of Boolean Functions'' by Ryan O'Donnell, as well as many papers by Gil Kalai and others heavily use this formulation.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.