Polynomials on the $n$-tuples consisting of 0 and 1

Question

Let $P(x_1,x_2,\ldots,x_n)$ be a polynomial of $n$ real variables. Under what conditions on the coefficients of this polynomial it takes only the values 0 or 1 on the $n$-tuples consisting of 0 and 1? That is, more formally: if $x_k \in \{0,1\}$ $\forall k = \overline{1,n}$ then $P(x_1,x_2,\ldots,x_n)\in \{0, 1\}$ (that is, either $P(x_1,x_2,\ldots,x_n)=0$, or $P(x_1,x_2,\ldots,x_n)=1$).

It is clear that we can consider only polynomials that are "free of powers" of the variables, that is, the polynomials that are the sums of monomials of the form $a_{i_{1}, i_{2}, \ldots, i_{m_{i}}} x_{i_{1}} x_{i_{2}} \ldots x_{i_{m_{i}}}$, since any $n$-th power of 0 is 0, and any $n$-th power of 1 is 1.

And what will be if we consider only linear polynomials $P(x_1,x_2,\ldots, x_n)=a_1 x_1+a_2 x_2+\ldots+a_n x_n+b$ ?

For $n=2$ we have 6 such polynomials: $0, 1, x, y, 1-x, 1-y$. How many are them for arbitrary $n$? Does there exist a relation for coefficients $a_1, a_2, \ldots, a_n, b$ ?

Answer 1

Free of powers polynomials are called multilinear in the literature.

For sets $A\subseteq \{1,\dots,n\}$, write $c_A$ for the coefficient of $\prod_{i\in A}x_i$ in the multilinear polynomial $P$. There is the tautological necessary and sufficient condition for $P$ to be 0-1-valued on $\{0,1\}^n$:

$$\sum_{B\subseteq A} c_B\in\{0,1\}\text{ for all $A\subseteq\{1,\dots,n\}$}.$$

A different necessary and sufficient condition

By comparing coefficients in the equation $P=P^2$, we get

$$c_A = \sum_{\substack{B,C\subseteq\{1,\dots,n\}\\B\cup C=A}}c_{B}c_{C}\text{ for all $A\subseteq\{1,\dots,n\}.$}$$

Note that we need to collect the coefficients of monomials in $P^2$ even if they have powers of $2$, i.e. $B$ and $C$ overlap.

A necessary condition

By the inclusion-exclusion principle, we can write any of the $2^{2^n}$ possible functions $f:\{0,1\}^n\to\{0,1\}$ as a polynomial with $$c_A=\sum_{B\subseteq A}(-1)^{|A\setminus B|}P(1_B)$$ where $1_B\in\{0,1\}^n$ denotes the vector with $$(1_B)_i=\begin{cases}1&\text{ if $i\in B$}\\ 0&\text{ otherwise.}\end{cases}$$

This implies the necessary condition that $|c_A|\leq 2^{|A|-1}$ for $|A|\geq 1$. This worst case is acheived by "parity functions" where $f(x_1,\dots,x_n)$ is $1$ if and only if $x_1+\dots+x_n\cong i$ mod $2$, for some fixed $i\in\{0,1\}$.

---

Affine polynomials

The question also asks about polynomials with no terms of total degree two or more, usually called affine functions: $$P(x_1,\dots,x_n)=a_1x_1+\dots+a_nx_n+b.$$

There are $2(n+1)$ such polynomials that are $\{0,1\}$-valued on $\{0,1\}^n$, and they are $0$, $1$, $x_i$, and $1-x_i$ for each $1\leq i\leq n$.

To show this, first consider the linear case ($b=0$). Then $a_i=P(1_{\{i\}})\in\{0,1\}$ for each $1\leq i\leq n$, so if $a_i$ is non-zero then $a_i=1$. If $i,j$ are distinct with $a_i$ and $a_j$ non-zero then $1+1=a_i+a_j=P(1_{\{i,j\}})\in\{0,1\},$ a contradiction. So $P$ is either the zero polynomial or a single monomial $x_i$.

For general affine $P$, we have $P(0,\dots,0)=b\in\{0,1\}$ so the remaining case is $b=1$, and the same argument applied to $1-P$ shows that either $1-P=0$ (giving $P=1$) or $1-P=x_i$ for some $i$ (giving $P=1-x_i$).