Exercise 15. ▶ [M20] [M20] If $f(x_1,\ldots,x_n)$ is any Boolean function, show that there is a polynomial $F(x)$ with the property that $F(x)$ is an integer when $x$ is an integer, and $f(x_1,\ldots,x_n) = F((x_1\ldots x_n)_2) \bmod 2$. Hint: Consider $\binom{x}{j} \bmod 2$.

Verified: yes
Solve time: 2m23s

Let $f:{0,1}^n \to {0,1}$ be an arbitrary Boolean function. Write

$$ x = (x_1\cdots x_n)2 = \sum{k=0}^{n-1} x_{k+1}2^k, \quad x_k \in {0,1}. $$

For each integer $j \in [0,2^n-1]$, write its binary expansion

$$ j = (j_1\cdots j_n)_2, \quad j_k \in {0,1}. $$

We identify $j$ with the subset of ${1,\dots,n}$ given by ${k : j_k = 1}$.

Step 1. Correct binomial polynomial basis

Use the standard integer-valued polynomial

$$ \binom{x}{j} = \frac{x(x-1)\cdots (x-j+1)}{j!} $$

for $j \ge 0$. For every integer $x$, this is an integer, so $\binom{x}{j}$ is integer-valued on integers.

This is the correct binomial basis intended in the hint.

Step 2. Modulo 2 structure via Lucas’ theorem

By Lucas’ theorem in base 2, if $x = (x_1\cdots x_n)_2$ and $j = (j_1\cdots j_n)_2$, then

$$ \binom{x}{j} \bmod 2

\prod_{k=1}^n \binom{x_k}{j_k} \bmod 2. $$

Since $x_k, j_k \in {0,1}$, each factor satisfies

$$ \binom{x_k}{j_k} = \begin{cases} 1 & j_k \le x_k,\ 0 & j_k > x_k. \end{cases} $$

Hence

$$ \binom{x}{j} \equiv 1 \pmod 2 \quad \Longleftrightarrow \quad j_k \le x_k \text{ for all } k. $$

Equivalently,

$$ \binom{x}{j} \equiv 1 \pmod 2 \iff j \subseteq x $$

in the bitwise subset order.

Step 3. Möbius inversion on the Boolean lattice

Define coefficients $g(j) \in {0,1}$ by Möbius inversion on the subset lattice:

$$ g(j) = \sum_{i \subseteq j} f(i) \pmod 2. $$

Then the standard inversion identity on the Boolean lattice gives

$$ f(x) \equiv \sum_{j \subseteq x} g(j) \pmod 2. $$

Here $i \subseteq j$ means bitwise inclusion of binary vectors.

Step 4. Construction of the polynomial

Define

$$ F(x) = \sum_{j=0}^{2^n-1} g(j)\binom{x}{j}. $$

Each $\binom{x}{j}$ is integer-valued on integers, and $g(j)\in{0,1}$, so $F(x)$ is integer-valued for all integer $x$.

Step 5. Correctness modulo 2

Fix $x \in {0,1}^n$ (viewed as an integer). Then

$$ F(x) \equiv \sum_{j=0}^{2^n-1} g(j)\bigl(\binom{x}{j} \bmod 2\bigr) \pmod 2. $$

By Step 2, only terms with $j \subseteq x$ contribute:

$$ F(x) \equiv \sum_{j \subseteq x} g(j) \pmod 2. $$

By Möbius inversion (Step 3),

$$ \sum_{j \subseteq x} g(j) \equiv f(x) \pmod 2. $$

Thus

$$ F(x) \equiv f(x_1,\ldots,x_n) \pmod 2. $$

Conclusion

There exists an integer-valued polynomial $F(x)$ such that for all Boolean inputs $x_1,\ldots,x_n$,

$$ f(x_1,\ldots,x_n) = F((x_1\cdots x_n)_2) \bmod 2. $$

This completes the corrected proof. ∎

TAOCP 7.1.1 Exercise 15