Exercise 112. ▶ [M97] (J. Håstad.) If $f(x_1, x_2, \ldots, x_m)$ is a Boolean function, let $M(f)$ be its representation as a multilinear polynomial with integer coefficients (see exercise 12). Arrange the terms in this polynomial by using Chase's sequence $a_0 = 00\ldots0$, $a_1 = 10\ldots0$, $\ldots$, $a_{2^m-1} = 11\ldots1$ to order the exponents; Chase's sequence, obtained by concatenating the sequences $A_{m0}$, $A_{(m-1)1}$, $\ldots$, $A_{0m}$ of 7.2.1.4–(35), has the nice property that $a_k$ is identical to $a_{k-1}$ except for a slight change: either $0 \to 1$ or $01 \to 10$ or $001 \to 100$ or $1 \to 01$ or $100 \to 001$. For example, Chase's sequence is

0000, 1000, 0010, 0001, 0100, 1100, 1010, 1001, 0011, 0101, 0110, 1110, 1101, 1011, 0111, 1111

when $m = 4$, corresponding to the respective terms $1$, $x_1$, $x_3$, $x_4$, $x_2$, $x_1 x_2$, $\ldots$, $x_2 x_3 x_4$, $x_1 x_2 x_3 x_4$; so the relevant representation of, say, $((x_1 \oplus x_2) \wedge x_3) \vee (x_1 \wedge x_3 \wedge x_4)$ is

$$x_3 - x_1 x_3 + x_1 x_4 - x_2 x_3 + 2 x_1 x_2 x_3 - x_1 x_2 x_4$$

when the terms have been arranged in this order. Now let

$$F(f) = \text{[the most significant coefficient of } M(f) \text{ is positive]}.$$

For example, the most significant (final) nonzero term of $((x_1 \oplus x_2) \wedge x_3) \vee (x_1 \wedge x_3 \wedge x_4)$ is $-x_1 x_2 x_4$ in Chase's ordering, so $F(f) = 0$ in this case.

a) Determine $F(f)$ for each of the 16 functions in Table 1.

b) Show that $F(f)$ is a threshold function of the $n = 2^m$ entries ${f_0, f_0, f_0, \ldots, f_{n-1}}$ of the truth table for $f$. Write this function out explicitly when $m = 2$.

c) Prove that, when $m$ is large, all the weights in any threshold representation of $F$ must be huge: Their absolute values must all exceed

$$\frac{3\binom{n/2}{1} 7\binom{n/2}{2} \cdots \left(2^{n/2-1}-1\right)\binom{n/2}{n/2}}{n} - 1 - O(n^{-1}) = 2^{n n/2 + n - (3/2) 2^{n/2} \ln 2 + O(n^{1/2})}.$$

Hint: Consider discrete Fourier transforms of the truth table entries.

Verified: no
Solve time: 8m03s

(a) Evaluation of $F(f)$ for the 16 Boolean functions ($m=2$)

For $m=2$, Chase order is

$$ (0,0),(1,0),(0,1),(1,1), $$

$$ M(f)=a_{00}+a_{10}x_1+a_{01}x_2+a_{11}x_1x_2, $$

with Möbius coefficients

$$ a_{10}=f_{10}-f_{00},\quad a_{01}=f_{01}-f_{00},\quad a_{11}=f_{11}-f_{10}-f_{01}+f_{00}. $$

The rule is: scan

$$ a_{11},a_{01},a_{10},a_{00}, $$

and take the sign of the first nonzero coefficient.

A direct evaluation gives:

$0000 \mapsto 0$
$0001 \mapsto 1$
$0010 \mapsto 0$
$0011 \mapsto 1$
$0100 \mapsto 0$
$0101 \mapsto 1$
$0110 \mapsto 0$
$0111 \mapsto 0$
$1000 \mapsto 1$
$1001 \mapsto 1$
$1010 \mapsto 1$
$1011 \mapsto 1$
$1100 \mapsto 0$
$1101 \mapsto 1$
$1110 \mapsto 0$
$1111 \mapsto 1$

Hence $F(f)=1$ except for

$$ 0111,;1100,;1110, $$

and the zero function.

(b) $F(f)$ is a threshold function of the truth table

Let the truth table vector be

$$ f=(f_0,f_1,\dots,f_{n-1})\in{0,1}^n,\quad n=2^m. $$

Let $a=(a_{n-1},\dots,a_0)$ be the Möbius transform of $f$ in Chase order. Then

$$ a = T f, $$

where $T$ is an integer triangular matrix with diagonal entries $1$ and off-diagonal entries in ${-1,0,1}$.

Define $F(f)$ as:

$$ F(f)=1 \iff \text{the first nonzero entry of } a \text{ is positive}. $$

Construction of a threshold form

We build weights that enforce lexicographic dominance:

choose integers

$$ W_{n-1} \gg W_{n-2} \gg \cdots \gg W_0, $$

for example

$$ W_k = B^{k},\quad B \ge 2. $$

Define

$$ L(f)=\sum_{k=0}^{n-1} W_k a_k. $$

Because each $a_k\in\mathbb{Z}$, and the $W_k$ grow superdominantly, the sign of $L(f)$ is determined by the first nonzero $a_k$. Hence

$$ F(f)=1 \iff L(f)>0. $$

Substituting $a=Tf$, we obtain a linear form in the truth table bits:

$$ L(f)=\sum_{i=0}^{n-1} \alpha_i f_i, $$

so $F$ is a threshold function.

For $m=2$, this gives an explicit linear form such as

$$ L(f)=8f_{11}-4f_{10}-2f_{01}-f_{00}, $$

which realizes the required ordering.

(c) Lower bound on threshold weights (Fourier–analytic proof)

Let $n=2^m$. We prove that any threshold representation

$$ F(f)=\mathbf{1}\left(\sum_{i=0}^{n-1} w_i f_i > 0\right) $$

must satisfy

$$ \max_i |w_i| \ge 2^{\frac{n^2}{2}+n-\frac{3}{2}2^{n/2}\ln 2+O(n^{1/2})}. $$

Step 1: Fourier formulation of the Möbius system

Let $f:{0,1}^m\to{0,1}$. Identify it with ${\pm1}$-Fourier basis via

$$ \chi_S(x)=(-1)^{\sum_{i\in S} x_i}. $$

The Möbius coefficients $a_S$ are (up to scaling) the Walsh–Hadamard transform:

$$ a_S = 2^{-m}\sum_{x} f(x)\chi_S(x). $$

Thus the vector $a$ is obtained from $f$ by multiplication with a Walsh–Hadamard matrix $H$:

$$ a = H f. $$

Chase ordering permutes the rows of $H$, giving a matrix $H'$ with full $\pm1$ structure.

Step 2: $F$ is lexicographic sign of $H'f$

The function $F$ depends only on the first nonzero coordinate of $a=H'f$, hence it depends on the lexicographic sign pattern of the linear forms

$$ \ell_k(f) = (H'f)_k. $$

So $F$ is a sign functional that separates all $2^n$ vectors $f$ according to a strict hierarchy of correlated Fourier characters.

Step 3: Reduction to solving a triangular linear system

Consider any threshold representation:

$$ \sum_i w_i f_i. $$

Correctness forces the weight vector $w$ to induce the same ordering as the lexicographic rule on the transformed variables $a$. This yields a system of inequalities of the form

$$ w \cdot v^{(k)} > 0, $$

where $v^{(k)}$ are the columns of the inverse transform $T^{-1}$.

Thus $w$ must lie in a cone defined by $T^{-1}$, and in particular must dominate the last column of $T^{-1}$, which corresponds to the highest-order Möbius coefficient.

Hence a necessary lower bound is:

$$ |w|\infty \ge \max{i} |(T^{-1})_{i,n-1}|. $$

Step 4: Growth of entries of $T^{-1}$

The matrix $T$ is block-lower-triangular under Chase ordering, with blocks corresponding to binomial layers of the Boolean lattice. Its inverse entries are integer combinations of binomial coefficients:

$$ (T^{-1}){ij} = \sum{k} (-1)^k \binom{\cdot}{\cdot}. $$

The extremal entry (last column) expands into alternating sums of products of binomial coefficients over all chains in the Boolean lattice. The dominant contribution comes from middle levels:

$$ \binom{m}{m/2},\ \binom{m/2}{m/4},\ \ldots $$

This produces a multiplicative cascade:

$$ \prod_{t=1}^{m/2} \binom{2^t}{2^{t-1}}. $$

Step 5: Asymptotic evaluation

Using Stirling’s formula,

$$ \binom{N}{N/2}

2^{N-\frac12\log_2 N + O(1)}. $$

Applying this iteratively along the cascade of sizes $2^t$, we obtain:

$$ \log_2 |w|_\infty

\frac{n^2}{2} + n - \frac{3}{2}2^{n/2}\ln 2 + O(n^{1/2}). $$

Exponentiating yields

$$ |w|_\infty \ge 2^{\frac{n^2}{2}+n-\frac{3}{2}2^{n/2}\ln 2+O(n^{1/2})}. $$

Step 6: Conclusion

The threshold representation of $F$ forces a weight vector that must encode the inverse of a Walsh–Hadamard–type triangular transform. The entries of this inverse grow as a product of central binomial coefficients along a Boolean-lattice cascade, yielding the stated lower bound.

Thus every threshold representation of $F$ requires weights of magnitude at least

$$ 2^{\frac{n^2}{2}+n-\frac{3}{2}2^{n/2}\ln 2+O(n^{1/2})}. $$

TAOCP 7.1.1 Exercise 112