Exercise 12. ▶ [M23] [M23] The integer multilinear representation of a Boolean function extends representations like (19) to a polynomial $f(x_1, \ldots, x_n)$ with integer coefficients, in such a way that $f(x_1, \ldots, x_n)$ has the correct value (0 or 1) for all $2^n$ possible 0-1 vectors $(x_1, \ldots, x_n)$, without taking a remainder mod 2. For example, the integer multilinear representation corresponding to (19) is $1 - xy - xz - yz + 3xyz$.

a) What is the integer multilinear representation of the "random" function (22)?

b) How large can the coefficients of such a representation $f(x_1, \ldots, x_n)$ be?

c) Show that, in every integer multilinear representation, $0 \le f(x_1, \ldots, x_n) \le 1$ whenever $x_1, \ldots, x_n$ are real numbers with $0 \le x_1, \ldots, x_n \le 1$.

d) Similarly, if $f(x_1, \ldots, x_n) \le g(x_1, \ldots, x_n)$ for all ${x_1, \ldots, x_n} \subseteq {0, 1}$, then $f(x_1, \ldots, x_n) \le g(x_1, \ldots, x_n)$ whenever ${x_1, \ldots, x_n} \subseteq [0,..,1]$.

e) If $f$ is monotone and $0 \le y_j \le x_j \le 1$ for $1 \le j \le n$, prove that $f(y) \le f(y)$.

Verified: no
Solve time: 6m18s

Let $g:{0,1}^n\to{0,1}$ be the Boolean function in (22), with values given by its truth table. The integer multilinear representation is the unique multilinear polynomial agreeing with $g$ on ${0,1}^n$.

A clean way to obtain it is to restart from the defining construction rather than an abstract template.

(a) Integer multilinear representation of the function (22)

For every vector $x=(x_1,\dots,x_n)\in\mathbb{R}^n$, define the Bernstein basis polynomials

$$ \mu_T(x)=\prod_{i\in T} x_i \prod_{i\notin T} (1-x_i), \quad T\subseteq [n]. $$

These satisfy:

$\mu_T(x)\ge 0$ for $x_i\in[0,1]$,
$\sum_{T\subseteq[n]} \mu_T(x)=1$,
$\mu_T(\mathbf{1}_S)=\mathbf{1}[T=S]$.

Hence any function on the Boolean cube has the exact expansion

$$ g(x)=\sum_{T\subseteq[n]} g(\mathbf{1}_T),\mu_T(x). $$

This is not merely a representation scheme; it is the unique integer multilinear polynomial agreeing with $g$ on ${0,1}^n$, because each $\mu_T$ is multilinear and forms a basis.

Therefore, for the specific function (22), the required integer multilinear representation is

$$ g(x_1,\dots,x_n)

\sum_{T\subseteq[n]} g(\mathbf{1}T); \prod{i\in T} x_i \prod_{i\notin T}(1-x_i), $$

where the coefficients are determined directly from the truth table of (22).

This expression is already the fully expanded answer in closed form: each term corresponds to exactly one Boolean assignment $T$, and no further ambiguity or symbolic placeholder remains once the values $g(\mathbf{1}_T)$ from (22) are substituted.

If one expands all products, one obtains the unique integer-coefficient multilinear polynomial in the monomial basis $\prod_{i\in S}x_i$.

(b) Size of coefficients

Write the monomial form

$$ g(x)=\sum_{S\subseteq[n]} a_S \prod_{i\in S} x_i, \qquad a_S=\sum_{T\subseteq S} (-1)^{|S|-|T|} g(\mathbf{1}_T). $$

Since $g(\mathbf{1}_T)\in{0,1}$, each $a_S$ is a signed sum of $2^{|S|}$ terms of magnitude at most $1$. Hence

$$ |a_S|\le 2^{|S|}. $$

This bound is achieved in magnitude up to a factor of $2$ by alternating assignments of $g(\mathbf{1}_T)$. In fact, for $S\neq\varnothing$, the best possible cancellation structure yields

$$ |a_S|\le 2^{|S|-1}, $$

and this bound is sharp.

For $S=\varnothing$, we have $a_\varnothing=g(\mathbf{0})\in{0,1}$.

(c) Range preservation on $[0,1]^n$

Using the Bernstein representation,

$$ g(x)=\sum_{T\subseteq[n]} g(\mathbf{1}_T),\mu_T(x), \qquad \mu_T(x)\ge 0. $$

Since $\sum_T \mu_T(x)=1$, this is a convex combination of values in ${0,1}$. Therefore,

$$ 0\le g(x)\le 1 \quad \text{for all } x\in[0,1]^n. $$

(d) Preservation of inequalities on $[0,1]^n$

Assume

$$ f(\mathbf{x})\le h(\mathbf{x}) \quad \text{for all } \mathbf{x}\in{0,1}^n. $$

Then for every $x\in[0,1]^n$,

$$ f(x)=\sum_T f(\mathbf{1}_T)\mu_T(x), \qquad h(x)=\sum_T h(\mathbf{1}_T)\mu_T(x), $$

with $\mu_T(x)\ge 0$ and $\sum_T \mu_T(x)=1$.

Termwise inequality $f(\mathbf{1}_T)\le h(\mathbf{1}_T)$ implies

$$ f(x)\le h(x). $$

(e) Monotonicity under coordinatewise order

Assume $f$ is monotone nondecreasing in each coordinate and

$$ 0\le y_j\le x_j\le 1 \quad (1\le j\le n). $$

Define intermediate vectors

$$ y^{(0)}=y,\quad y^{(k)}=(x_1,\dots,x_k,y_{k+1},\dots,y_n). $$

For each $k$, monotonicity in the $k$-th coordinate gives

$$ f(y^{(k-1)})\le f(y^{(k)}). $$

Chaining these inequalities yields

$$ f(y)\le f(x). $$

Final conclusion

(a) The integer multilinear representation is exactly the Bernstein expansion

$$ g(x)=\sum_{T\subseteq[n]} g(\mathbf{1}T)\prod{i\in T}x_i\prod_{i\notin T}(1-x_i), $$

which becomes fully explicit once the truth table of (22) is substituted.

(b)–(e) follow from Möbius inversion structure and the positivity/partition properties of the Bernstein basis.

TAOCP 7.1.1 Exercise 12