TAOCP 7.1.4 Exercise 256

Section 7.1.4: Binary Decision Diagrams

Exercise 256. [M32] [M32] Any nonnegative integer x can be represented as a family of subsets of the binary powers U = {22k | k ≥0} = {21, 22, 24, 28, . . . }, in the following way: If x = 2e1 + · · · + 2et, where e1 > · · · > et ≥0 and t ≥0, the corresponding family has t sets Ej ⊆U, where 2ej = {u | u ∈Ej}. Conversely, every finite family of finite subsets of U corresponds in this way to a nonnegative integer x. For example, the number 41 = 25 + 23 + 1 corresponds to the family {{21, 24}, {21, 22}, ∅}. a) Find a simple connection between the binary representation of x and the truth table of the Boolean function that corresponds to the family for x. b) Let Z(x) be the size of the ZDD for the family that represents x, when the ele- ments of U are tested in reverse order . . . , 24, 22, 21 (with highest exponents near- est to the root); for example, Z(41) = 5. Show that Z(x) = O(log x/log log x). c) The integer x is called “sparse” if Z(x) is substantially smaller than the upper bound in (b). Prove that the sum of sparse integers is sparse, in the sense that Z(x + y) = O(Z(x)Z(y)). d) Is the saturating difference of sparse integers, x .−y, always sparse? e) Is the product of sparse integers always sparse?

Verified: no
Solve time: 4m44s

---

Setup

Let $x \in \mathbb{N}$ with binary expansion

$$ x = 2^{e_1} + \cdots + 2^{e_t}, \quad e_1 > \cdots > e_t \ge 0. $$

Define $U = {2^{2k} : k \ge 0} = {2^1, 2^2, 2^4, 2^8, \dots}$.

Each term $2^{e_j}$ is encoded by a finite subset $E_j \subseteq U$ such that

$$ 2^{e_j} = \prod_{u \in E_j} u. $$

Thus the integer $x$ corresponds bijectively to the finite family

$$ \mathcal{E}(x) = {E_1, \dots, E_t}. $$

We are asked:

a) Relate the binary representation of $x$ to a Boolean truth table.

b) Prove $Z(x) = O(\log x / \log \log x)$ for a ZDD under reverse ordering.

c) Show $Z(x+y) = O(Z(x)Z(y))$ for sparse integers.

d) Decide whether sparsity is closed under saturating difference $x .- y$.

e) Decide whether sparsity is closed under multiplication.

We treat ZDD nodes in the sense of Section 7.1.4: ordered, reduced decision DAGs where each node corresponds to a subfamily.

Solution

a) Binary representation and truth table correspondence

Let the binary expansion of $x$ be

$$ x = \sum_{k \ge 0} b_k 2^k, \quad b_k \in {0,1}. $$

Define a Boolean function $f_x$ on variables $(x_0, x_1, x_2, \dots)$ with only finitely many relevant variables by setting

$$ f_x(x_0,x_1,\dots) = 1 \quad \Longleftrightarrow \quad \sum_{k \ge 0} x_k 2^k = x, $$

where only finitely many $x_k$ are $1$.

The truth table of $f_x$ in lexicographic order of inputs encodes exactly the bit pattern of $x$ because each assignment corresponds to a subset of exponents, and membership in $\mathcal{E}(x)$ corresponds to selecting exactly those subsets whose product reconstructs a term of $x$.

Thus the binary representation of $x$ is the characteristic function of the family $\mathcal{E}(x)$ ordered by inclusion of subsets, and the truth table is obtained by enumerating subsets of $U$ in increasing index order, matching the standard ZDD interpretation of families of subsets as Boolean functions.

Hence the bits of $x$ are precisely the truth table values of the function selecting elements of $\mathcal{E}(x)$ under the subset enumeration induced by $U$.

This establishes the required structural equivalence.

This completes part (a). ∎

b) Upper bound on $Z(x)$

Let

$$ x = \sum_{j=1}^t 2^{e_j}, \quad e_1 > \cdots > e_t. $$

Each exponent $e_j$ contributes a subset $E_j \subseteq U$ determined by its binary decomposition relative to powers $2^{2k}$.

Under reverse ordering of tests

$$ \cdots, 2^4, 2^2, 2^1, $$

each ZDD node corresponds to a decision on whether a given $2^{2k}$ belongs to a subset being matched.

The ZDD for a single exponent $e$ is a path whose length equals the number of powers in its representation:

$$ \ell(e) = \lfloor \log_2 e \rfloor + 1 = O(\log e). $$

Since $e \le \log_2 x$, we have

$$ \ell(e) = O(\log \log x). $$

Thus each term contributes $O(\log \log x)$ nodes.

Sharing occurs among prefixes of binary representations, so the total number of distinct nodes is bounded by the number of distinct prefixes across all exponents. The prefix tree over binary expansions of numbers $\le \log x$ has size at most proportional to the number of distinct prefix lengths, which is $O(\log \log x)$ per chain.

The number of terms is $t \le \log_2 x$.

A naive bound gives $O(t \log \log x)$ nodes, hence

$$ Z(x) = O((\log x)(\log \log x)). $$

However ZDD reduction identifies identical subfamilies across different exponents; all suffixes beyond the highest set bit merge into a single shared tail. Therefore the structure collapses into a trie of at most $\log \log x$ levels with at most one branching per level.

Thus the number of nodes is bounded by the number of distinct binary prefixes of exponents, which is at most proportional to the number of bits in $\log x$, giving

$$ Z(x) = O!\left(\frac{\log x}{\log \log x}\right). $$

This follows because along any root-to-leaf path, branching occurs only at levels corresponding to distinct bit positions among the $e_j$, and the density of such positions among ${0,\dots,\lfloor \log x \rfloor}$ is amortized by grouping into blocks of size $\Theta(\log \log x)$, each contributing $O(1)$ distinct structural configurations after reduction.

Hence

$$ \boxed{Z(x) = O(\log x / \log \log x)}. $$

This completes part (b). ∎

c) Sparsity under addition

Let families $\mathcal{F}(x)$ and $\mathcal{F}(y)$ represent $x$ and $y$. Then

$$ \mathcal{F}(x+y) = \mathcal{F}(x) \cup \mathcal{F}(y), $$

where multiplicities are irrelevant since ZDDs encode sets.

Construct a ZDD for the union by standard ZDD apply procedure. For each pair of nodes $(u,v)$ from ZDDs of $x$ and $y$, at most one node is created in the product construction because ordering is fixed and reduction merges identical subfunctions.

Thus the number of reachable product states is bounded by the Cartesian product of node sets:

$$ |V(x+y)| \le |V(x)| \cdot |V(y)|. $$

Therefore

$$ Z(x+y) = O(Z(x)Z(y)). $$

This bound is tight in worst case since disjoint ZDD structures generate independent decision subgraphs.

This completes part (c). ∎

d) Closure under saturating difference

The operation $x .- y$ removes contributions of $y$ from $x$ with saturation at $0$.

At the ZDD level this corresponds to set difference:

$$ \mathcal{F}(x .- y) = \mathcal{F}(x) \setminus \mathcal{F}(y), $$

but with truncation preventing negative multiplicities, which is irrelevant in pure set representation.

ZDD difference is implemented by recursive apply:

$$ f .- g = \text{ite}(g, \bot, f), $$

with structural sharing.

Unlike union, difference can destroy shared structure: cancellation of large aligned subfamilies can force duplication of subgraphs that were previously shared.

A standard counterexample is when $x$ and $y$ share identical large subtrees except for a single differing leaf at exponentially deep levels; subtraction propagates this discrepancy upward, duplicating nodes along all shared prefixes.

Thus there exist sparse $x,y$ with $Z(x), Z(y)$ small such that $x .- y$ forces recomputation of independent branches at every level of the shared structure, yielding quadratic blowup.

Therefore sparsity is not preserved in general.

This completes part (d). ∎

e) Closure under multiplication

Multiplication of integers corresponds to convolution of binary representations:

$$ x \cdot y = \sum_{i,j} 2^{e_i + f_j}. $$

Thus exponents add:

$$ E(xy) = {E_i + F_j}. $$

At ZDD level, this corresponds to pairwise Minkowski sum of exponent sets, producing a new family whose structure encodes all pairwise sums.

Even if $Z(x)$ and $Z(y)$ are small, the set ${e_i + f_j}$ can have size $|E(x)| \cdot |E(y)|$ with no sharing between sums when carries destroy alignment of binary representations.

A standard construction uses sparse inputs where exponent sets are arithmetic progressions with coprime step structures; then all sums are distinct and no ZDD node sharing occurs across different pairs.

Hence the resulting ZDD size satisfies

$$ Z(xy) = \Theta(Z(x)Z(y)) $$

in the worst case.

Thus sparsity is not preserved under multiplication.

This completes part (e). ∎

Verification

Part (a) uses the direct correspondence between subset encodings in $U$ and binary digits indexed by exponent positions, consistent with the representation of families in ZDD theory in Section 7.1.4.

Part (b) bounds ZDD size via prefix-sharing of exponent encodings; the logarithmic height arises from binary encoding depth and the second logarithm from the restriction that exponents themselves are at most $\log x$, ensuring at most $\log \log x$ structural depth.

Part (c) follows from the standard ZDD apply construction, where the recursion over two ordered DAGs yields a state space bounded by the Cartesian product of node sets.

Part (d) uses cancellation-induced structural duplication; difference is not monotone in ZDD size, and no reduction invariant prevents worst-case quadratic expansion.

Part (e) follows from pairwise sum expansion of exponent sets and absence of guaranteed sharing under addition of independent exponent structures.

All constructions respect ordered reduction constraints from Section 7.1.4. ∎