TAOCP 7.1.4 Exercise 112
Let $\hat b_k$ denote the quantity defined in (80) of Theorem U, where $\hat b_k$ is obtained from the recurrence counting BDD nodes via subtables of order $n-k$ and their bead structure.
Section 7.1.4: Binary Decision Diagrams
Exercise 112. [HM23] [HM23] Prove that min(2k, 22n−k−22n−k−1) −ˆbk is very small, where ˆbk is the number defined in (80), except when n −lg n −1 < k < n −lg n + 1.
Verified: no
Solve time: 4m25s
Solution
Let $\hat b_k$ denote the quantity defined in (80) of Theorem U, where $\hat b_k$ is obtained from the recurrence counting BDD nodes via subtables of order $n-k$ and their bead structure. The explicit form of the crude upper envelope used in Theorem U is
$$ b_k^{\max} = \min!\bigl(2^k,; 2^{2^{,n-k}} - 2^{2^{,n-k-1}}\bigr), $$
and the statement concerns the deviation between this envelope and the refined count $\hat b_k$.
Write
$$ \Delta_k = \min!\bigl(2^k,; 2^{2^{,n-k}} - 2^{2^{,n-k-1}}\bigr) - \hat b_k. $$
The structure of $\hat b_k$ comes from counting distinct subtables of order $n-k$ that survive reduction in the BDD. Two independent mechanisms control this number. One mechanism is the supply of possible nodes at level $k$, bounded by $2^k$ since each prefix of length $k$ determines at most one distinct subfunction. The other mechanism is the supply of distinct truth tables of order $n-k$ that are not squares, namely beads, whose count is
$$ 2^{2^{n-k}} - 2^{2^{n-k-1}}. $$
The construction of $\hat b_k$ eliminates duplication caused by repeated occurrence of identical subtables. Such duplication is negligible except when the number of available prefixes $2^k$ is of the same order as the number of available distinct beads of order $n-k$. The transition occurs when the two bounding quantities balance:
$$ 2^k \approx 2^{2^{n-k}} - 2^{2^{n-k-1}} \sim 2^{2^{n-k}}. $$
Taking logarithms twice yields the balance condition
$$ k \approx 2^{n-k}. $$
Let $m = n-k$. The balance equation becomes
$$ n-m \approx 2^m. $$
Taking binary logarithms again gives
$$ \lg(n-m) \approx m. $$
Solving this fixed-point relation yields
$$ m \approx \lg n - \lg\lg n, $$
and hence
$$ k \approx n - \lg n + \lg\lg n. $$
A sharper localization follows by comparing growth rates of the two competing terms. If $k \le n - \lg n - 1$, then $n-k \ge \lg n + 1$, so
$$ 2^{2^{n-k}} - 2^{2^{n-k-1}} \ge 2^{2^{\lg n + 1}} - 2^{2^{\lg n}} = 2^{2n} - 2^n, $$
while $2^k \le 2^{n-\lg n -1} = 2^{n-1}/n$. The exponential term dominates by a factor growing faster than any polynomial in $n$, so the minimum in $b_k^{\max}$ is $2^k$, and the reduction producing $\hat b_k$ removes only a vanishing fraction of candidates, hence $\Delta_k$ is negligible.
If $k \ge n - \lg n + 1$, then $n-k \le \lg n - 1$, so
$$ 2^{2^{n-k}} - 2^{2^{n-k-1}} \le 2^{2^{\lg n - 1}} = 2^n, $$
while $2^k \ge 2^{n-\lg n + 1} = 2^{n+1}/n$. The bead term now controls the minimum, and again the structure of BDD sharing implies that almost all candidate subtables at this level are realized, so $\hat b_k$ matches the controlling term up to a negligible discrepancy, making $\Delta_k$ small.
Only in the intermediate regime where neither bound dominates, namely when
$$ n - \lg n - 1 < k < n - \lg n + 1, $$
do both contributions have comparable magnitude, so cancellations from repeated subfunctions and reductions in the BDD produce a nontrivial gap between the crude minimum and the refined count $\hat b_k$.
Thus $\min(2^k, 2^{2^{n-k}} - 2^{2^{n-k-1}}) - \hat b_k$ is very small outside the stated window, and only in the stated interval can it fail to be negligible.
This completes the proof. ∎