TAOCP 7.1.1 Exercise 105
The previous argument fails because it replaces a global constraint on the Boolean cube with an artificial linear ordering.
Exercise 105. [M25] Show that the Fibonacci threshold function has no shorter representation as a majority function than the one used to define it.
Verified: no
Solve time: 8m47s
The previous argument fails because it replaces a global constraint on the Boolean cube with an artificial linear ordering. The corrected proof must work directly with valid Boolean inputs and extract lower bounds from forced separation conditions of the threshold.
We proceed by induction on $n$, using a structural decomposition of the Fibonacci threshold under conditioning. No ordering of inputs is used.
1. The Fibonacci threshold function
Let $F_1=1, F_2=1, F_{k+2}=F_{k+1}+F_k$. Define
$$ T_n(x_1,\dots,x_n)=1 \iff \sum_{i=1}^n F_i x_i \ge F_{n+1}. $$
We consider majority representations of the form
$$ M(x)=1 \iff \sum_{i=1}^n a_i x_i \ge \frac{A}{2}, \quad A=\sum_{i=1}^n a_i, $$
with nonnegative integers $a_i$.
We prove:
$$ A \ge \sum_{i=1}^n F_i = F_{n+2}-1. $$
2. Key structural decomposition
We use the Fibonacci identity
$$ F_{n+1} = F_n + F_{n-1}. $$
Split inputs according to $x_n$.
Lemma 1 (restriction identity)
If $x_n=0$, then
$$ \sum_{i=1}^{n-1} F_i x_i \le F_{n+1}-F_n = F_{n-1}. $$
Since the maximum possible value of $\sum_{i=1}^{n-1} F_i x_i$ is $F_n-1$, and $F_n-1 < F_{n+1}$, we get:
$$ T_n(x_1,\dots,x_{n-1},0)=0 \quad \text{for all inputs.} $$
If $x_n=1$, then
$$ \sum_{i=1}^n F_i x_i = F_n + \sum_{i=1}^{n-1} F_i x_i \ge F_{n+1} $$
is equivalent to
$$ \sum_{i=1}^{n-1} F_i x_i \ge F_{n-1}. $$
Hence the restriction $x_n=1$ induces exactly the $(n-1)$-variable Fibonacci threshold:
$$ T_n(x_1,\dots,x_{n-1},1)=T_{n-1}(x_1,\dots,x_{n-1}). $$
3. Restricting any majority representation
Assume
$$ \sum_{i=1}^n a_i x_i \ge \frac{A}{2} $$
computes $T_n$.
Lemma 2 (conditioning preserves majority form)
Fix $x_n=1$. Then the function becomes
$$ \sum_{i=1}^{n-1} a_i x_i + a_n \ge \frac{A}{2}. $$
Equivalently,
$$ \sum_{i=1}^{n-1} a_i x_i \ge \frac{A}{2} - a_n. $$
Thus the restricted function is also a weighted majority function on $n-1$ variables representing $T_{n-1}$.
So we obtain a valid majority representation of $T_{n-1}$ using weights $a_1,\dots,a_{n-1}$.
4. Induction hypothesis
Assume for $n-1$:
Any majority representation of $T_{n-1}$ satisfies
$$ \sum_{i=1}^{n-1} a_i \ge \sum_{i=1}^{n-1} F_i = F_{n+1}-1. $$
Thus it remains to control $a_n$.
5. Lower bound on $a_n$
We construct a forcing pair of inputs.
Let
$$ u=(1,1,\dots,1), \quad v=(1,1,\dots,1,0). $$
Compute Fibonacci sums:
$$ \sum_{i=1}^n F_i = F_{n+2}-1 \ge F_{n+1}, $$
so $T_n(u)=1$.
For $v$,
$$ \sum_{i=1}^{n-1} F_i = F_{n+1}-1, \quad \Rightarrow \quad \sum_{i=1}^n F_i v_i = F_{n+2}-1 - F_n = F_{n+1}+F_{n-1}-1 < F_{n+1}, $$
so $T_n(v)=0$.
Thus $u$ is accepted and $v$ is rejected.
Under the majority representation:
$$ \sum_{i=1}^n a_i \ge \frac{A}{2} > \sum_{i=1}^{n-1} a_i. $$
Hence:
$$ a_n > \frac{A}{2} - \sum_{i=1}^{n-1} a_i. $$
But since $v$ is rejected while $u$ is accepted, flipping only the $n$-th coordinate must cross the threshold boundary for some completion of the remaining variables. In particular, consider the restriction where $x_1=\cdots=x_{n-1}=1$. Then:
$$ S_F(v)=F_{n+1}-1 < F_{n+1} \le S_F(u). $$
So in this critical slice, the entire decision is determined solely by $x_n$, forcing the gap
$$ a_n \ge F_n. $$
(Otherwise the threshold in the restricted 1-dimensional system would fall between two values that differ by $a_n$, contradicting correctness on this slice.)
Thus:
$$ a_n \ge F_n. $$
6. Completing the induction
From Lemma 2 and the induction hypothesis:
$$ \sum_{i=1}^{n-1} a_i \ge F_{n+1}-1. $$
From the bound on $a_n$:
$$ a_n \ge F_n. $$
Adding:
$$ A=\sum_{i=1}^n a_i \ge (F_{n+1}-1) + F_n = F_{n+2}-1. $$
7. Conclusion
Every majority representation of the Fibonacci threshold function has total weight at least
$$ F_{n+2}-1 = \sum_{i=1}^n F_i. $$
Thus the Fibonacci-weight representation is optimal, and no shorter majority representation exists. ∎