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]$?



What is a multivariable Boolean polynomial?
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.


