1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ why you don't consider (for $n=2$) also the $xy$ etc. ? and if you do not consider them, then in case $n=3$, how can you get more than $0,1,x,y,z,(1-x),(1-y),(1-z)$? $\endgroup$
    – G Cab
    Sep 17, 2017 at 22:46

1 Answer 1

1
$\begingroup$

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$).

$\endgroup$
2
  • $\begingroup$ Thank you very much! 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$ ? $\endgroup$
    – DianaG
    Sep 17, 2017 at 19:14
  • $\begingroup$ @DianaG: I have added information about those polynomials $\endgroup$
    – Dap
    Sep 18, 2017 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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