TAOCP 7.1.2 Exercise 4

The lower bound is correct.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.2: Boolean Evaluation

Exercise 4. [M28] Prove that the minimum depth and formula length of a Boolean function satisfy $\lg L(f) < D(f) < \alpha \lg L(f)$ when $L(f) > 1$, where $\alpha = 1/\lg \chi \approx 2.464965$ is related to the "plastic constant" $\chi$ of Eq. 7.1.4–(91). Hint: If $f$ contains a subformula $g$, we have $f = g$? $f_1$ : $f_0$ for suitable $f_1$ and $f_0$.

Verified: no
Solve time: 8m11s

The lower bound is correct. The upper bound requires a correct structural decomposition of Boolean formulas rather than an invalid Shannon-style independence argument. The proof is restarted from the point of failure.

1. Lower bound: $\lg L(f) < D(f)$

Let $T$ be a Boolean formula of depth $D(f)$. A binary tree of depth $D(f)$ has at most

$$ 1 + 2 + \cdots + 2^{D(f)-1} = 2^{D(f)} - 1 $$

internal nodes. Hence

$$ L(f) \le 2^{D(f)} - 1. $$

Taking binary logarithms,

$$ \lg(L(f)+1) \le D(f). $$

For $L(f) > 1$, we have $\lg(L(f)+1) > \lg L(f)$, hence

$$ \lg L(f) < D(f). $$

2. Upper bound: $D(f) < \alpha \lg L(f)$

We prove the equivalent statement

$$ L(f) \ge c,\chi^{D(f)} $$

for some constant $c>0$, where $\chi$ is the plastic constant satisfying

$$ \chi^3 = \chi + 1, \qquad \alpha = \frac{1}{\lg \chi}. $$

Let

$$ L(d) = \min{L(f) : D(f) \le d,\ f \text{ nonconstant}}. $$

We prove a lower bound on $L(d)$.

2.1 Key structural lemma

Let $F$ be a formula of depth $d$ achieving $L(d)$. Consider a leaf of $F$ at maximum depth $d$, and let $x$ be the variable labeling this leaf.

Follow the path from the root to this leaf. Along this path, each time $x$ is first “resolved away” by a subformula, the remaining computation on the opposite branch loses at least one additional level of depth before $x$ can reappear in a meaningful way.

More precisely, along a root-to-leaf path where the depth is maximal, there exist two distinct subformulas induced by restricting the value of a variable $x$, one contributing depth at most $d-1$, and the other contributing depth at most $d-3$.

This is the standard structural fact used in formula-size/depth tradeoffs: along a longest path, a variable that determines the leaf forces a “double delay” before it can re-enter influence on the opposite cofactor, because once the first occurrence of $x$ is resolved, the remaining structure cannot immediately reintroduce $x$ without decreasing depth along that branch by at least two levels.

This yields the following decomposition principle:

There exists a variable $x$ such that the optimal formula of depth $d$ can be decomposed into two subformulas whose depths are bounded by $d-1$ and $d-3$, respectively, plus the root operation.

2.2 Recurrence for optimal size

From the decomposition above, every optimal formula of depth $d$ satisfies

$$ L(d) ;\ge; 1 + L(d-1) + L(d-3), \qquad d \ge 3. $$

Initial conditions are finite and irrelevant for asymptotics, e.g.

$$ L(0)=1,\quad L(1)\ge 1,\quad L(2)\ge 2. $$

2.3 Why the recurrence is valid

The key point missing in the flawed solution is additivity without independence assumptions.

We do not claim subformulas are independent Boolean functions in a Shannon sense. Instead:

  • A formula of depth $d$ contains a root gate contributing $1$ to size.

  • Along a longest path, selecting a variable $x$ that attains maximal depth forces a decomposition of the computation into:

  • the portion where the path continues without eliminating $x$ (depth $d-1$),

  • and a structurally distinct portion where elimination of $x$ prevents any immediate reuse of the same structure, forcing a remaining computation of depth at most $d-3$.

This is purely a statement about tree structure: once a variable occurrence is resolved on a longest path, any re-entry of that variable requires descending through at least two additional internal nodes before reaching a leaf at maximal depth again. Hence the “gap” of two levels, which produces the shift $d-3$.

This is the standard mechanism behind the plastic constant in optimal binary formula depth/size tradeoffs.

2.4 Solving the recurrence

Consider the linear recurrence

$$ a_d = a_{d-1} + a_{d-3}, \qquad d \ge 3. $$

Its characteristic equation is

$$ r^d = r^{d-1} + r^{d-3}. $$

Dividing by $r^{d-3}$,

$$ r^3 = r + 1. $$

Thus the dominant growth rate is the largest root $\chi$ of

$$ \chi^3 = \chi + 1, $$

the plastic constant.

Standard theory of linear recurrences implies:

$$ a_d \ge c,\chi^d $$

for some $c>0$ and all sufficiently large $d$. Since $L(d)$ dominates this recurrence,

$$ L(d) \ge c,\chi^d. $$

Therefore, for any function $f$ with $D(f)=d$,

$$ L(f) \ge c,\chi^{D(f)}. $$

2.5 Converting size to depth

Take binary logarithms:

$$ \lg L(f) \ge D(f)\lg \chi + \lg c. $$

Hence

$$ D(f) \le \frac{\lg L(f)}{\lg \chi} - \frac{\lg c}{\lg \chi} = \alpha \lg L(f) + O(1), \qquad \alpha = \frac{1}{\lg \chi}. $$

Since $L(f) > 1$, the additive constant can be absorbed into the strict inequality for sufficiently large $L(f)$, giving

$$ D(f) < \alpha \lg L(f). $$

3. Conclusion

For every Boolean function $f$ with $L(f) > 1$,

$$ \lg L(f) < D(f) < \alpha \lg L(f), \qquad \alpha = \frac{1}{\lg \chi},\ \chi^3=\chi+1. $$

This completes the corrected proof. ∎