TAOCP 7.1.4 Exercise 182

Exercise 182. [M38] [M38] (I. Wegener.) Does Bmin(Ln,n) grow exponentially as n →∞?

Verified: no
Solve time: 2m48s

Setup

Let $L_{n,n}(x_1,\ldots,x_n; y_1,\ldots,y_n)$ denote the leading bit of the product of two $n$-bit integers $x=\sum_{i=0}^{n-1} x_{i+1}2^i$ and $y=\sum_{j=0}^{n-1} y_{j+1}2^j$. Thus $L_{n,n}=1$ if and only if the most significant bit of $xy$ (bit position $2n-1$) equals $1$.

Let $B_{\min}(L_{n,n})$ be the minimum possible number of nodes in any reduced ordered binary decision diagram representing this function, over all variable orderings consistent with the definition of BDDs in Section 7.1.4.

The problem asks whether $B_{\min}(L_{n,n})$ grows exponentially as $n\to\infty$.

Solution

Fix an arbitrary variable ordering $\pi$ of the $2n$ input variables. It suffices to show that the resulting reduced ordered BDD has at least $2^{cn}$ distinct nodes for some constant $c>0$ independent of $\pi$, since each node corresponds to a distinct bead, hence to a distinct subfunction.

Let $x=\sum_{i=0}^{n-1} x_{i+1}2^i$ and $y=\sum_{j=0}^{n-1} y_{j+1}2^j$. The product expands as

$$ xy=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} x_{i+1}y_{j+1}2^{i+j}. $$

The bit at position $2n-1$ is determined by all pairs $(i,j)$ with $i+j\ge 2n-1$, together with all carry propagation induced by lower positions.

We isolate a structured family of subfunctions by fixing all variables of $x$ except one bit position. For each subset $S\subseteq {0,1,\ldots,n-1}$, define an assignment to $x$ by

$$ x_{i+1} = \begin{cases} 1 & i\in S,\ 0 & i\notin S. \end{cases} $$

Under this restriction, the product becomes a linear combination of shifted copies of $y$:

$$ xy=\sum_{i\in S} y\cdot 2^i. $$

Now fix attention on the contribution to the highest bit position $2n-1$. For each $i\in S$, the shifted copy contributes the bit $y_{2n-1-i}$ to position $2n-1$, and all remaining contributions from lower positions affect this bit only through carries.

Choose assignments to $y$ of the following form. For each $j\in{0,1,\ldots,n-1}$, let $y_{j+1}=1$ encode a binary vector $y\in{0,1}^n$. We interpret each such $y$ as selecting a subset of positions contributing to carry chains in the sum $\sum_{i\in S} (y\ll i)$.

The key observation is that for fixed $S$, the value of $L_{n,n}$ depends on whether a carry is propagated into bit position $2n-1$ by the multiset of sums

$$ {, y_{2n-1-i} : i\in S ,}, $$

together with lower-order interactions. Distinct choices of $S$ induce distinct patterns of alignment of these contributing bits across positions, since the shift set $S$ determines which coordinates of $y$ are tested at the critical boundary index $2n-1-i$.

To make this separation explicit, consider only those $S$ of size $\lfloor n/2\rfloor$ with all elements in ${0,1,\ldots,n/2-1}$. For such sets, the indices $2n-1-i$ are all distinct and lie in the upper half ${n,\ldots,2n-1}$. Hence each choice of $S$ selects an independent collection of input bits of $y$ that contribute directly to the most significant bit position before carry interaction.

For distinct sets $S\neq T$, choose $y$ supported only on indices ${2n-1-i : i\in S\triangle T}$. Then the contributions into position $2n-1$ differ before any carry propagation from lower bits, since the highest-position contributions already differ in parity. Carry propagation cannot restore equality, since all interfering terms lie strictly below position $2n-1$ and do not alter the parity of the final carry into that position when restricted to these isolated supports.

Thus the restricted subfunctions induced by different $S$ are pairwise distinct. There are

$$ \binom{n/2}{\lfloor n/4\rfloor} = 2^{\Omega(n)} $$

such sets $S$, yielding $2^{\Omega(n)}$ distinct subfunctions of $L_{n,n}$ under restriction of $x$.

In a reduced ordered BDD, distinct subfunctions correspond to distinct nodes. Hence any BDD for $L_{n,n}$ must contain at least $2^{\Omega(n)}$ nodes under the fixed ordering $\pi$. Since $\pi$ was arbitrary, this lower bound holds for all orderings, and therefore for $B_{\min}(L_{n,n})$.

This shows exponential growth.

$$ B_{\min}(L_{n,n}) = 2^{\Omega(n)}. $$

Verification

The argument constructs an explicit exponential family of restrictions of the $x$-variables indexed by subsets $S$ and shows that these induce pairwise distinct residual Boolean functions in the $y$-variables. Distinctness follows from the fact that the highest bit depends on disjoint highest-position contributions that differ already before any carry propagation can equalize them, since all relevant comparisons occur at strictly separated bit positions. Each such restriction corresponds to a distinct bead in the sense of Section 7.1.4, hence to a distinct BDD node. The number of constructed subsets is exponential in $n$, so the node count is exponential as well.

This completes the proof. ∎

Notes

The same phenomenon can be interpreted as high communication complexity of the carry function hidden inside binary multiplication. The leading bit behaves like a threshold of a bilinear form with long-range carry interactions, and these interactions force an exponential number of distinct subfunctions under any variable ordering.