TAOCP 7.1.4 Exercise 257

The key mistake in the rejected solution is the attempt to encode coefficients as additional atoms.

taocpmathematicsalgorithmsvolume-4project

Section 7.1.4: Binary Decision Diagrams

Exercise 257. [40] [40] (S. Minato.) Explore the use of ZDDs to represent polynomials with nonneg- ative integer coefficients. Hint: Any such polynomial in x, y, and z can be regarded as a family of subsets of {2, 22, 24, . . . , x, x2, x4, . . . , y, y2, y4, . . . , z, z2, z4, . . . }; for exam- ple, x3 +3xy +2z corresponds naturally to the family {{x, x2}, {x, y}, {2, x, y}, {2, z}}.

Verified: no
Solve time: 3m24s

The key mistake in the rejected solution is the attempt to encode coefficients as additional atoms. That destroys the algebra: under set union, those atoms add, while polynomial coefficients must multiply under multiplication of monomials. The correct fix is to stop encoding coefficient values inside subsets altogether and instead let coefficients be represented purely as multiplicities of identical subsets.

We restart from the hint’s intended viewpoint.

A polynomial in variables $x,y,z$ with nonnegative integer coefficients can be written as

$$ P(x,y,z)=\sum_{k} c_k, x^{a_k} y^{b_k} z^{c_k}, \quad c_k \in \mathbb{Z}_{\ge 0}. $$

We interpret this not as a function but as a multiset of monomials. Each monomial occurrence is separate.

Encoding monomials as subsets

Fix a universe of atoms that encodes exponents in binary:

$$ U = {x^{2^i} : i \ge 0} \cup {y^{2^i} : i \ge 0} \cup {z^{2^i} : i \ge 0}. $$

A finite subset $S \subseteq U$ encodes a monomial by interpreting each variable’s exponent in binary:

$$ \deg_x(S) = \sum_{x^{2^i}\in S} 2^i,\quad \deg_y(S) = \sum_{y^{2^i}\in S} 2^i,\quad \deg_z(S) = \sum_{z^{2^i}\in S} 2^i. $$

Thus $S$ corresponds uniquely to the monomial

$$ x^{\deg_x(S)} y^{\deg_y(S)} z^{\deg_z(S)}. $$

This encoding is bijective between subsets of $U$ and monomials in $x,y,z$.

Encoding coefficients

A polynomial is represented as a family of subsets of $U$:

$$ \mathcal{F} \subseteq \mathcal{P}(U), $$

but crucially we allow repetition in the algebraic sense: the coefficient of a monomial is the number of times its corresponding subset appears in the family.

Formally, we interpret the polynomial as a function

$$ P : \mathcal{P}(U) \to \mathbb{Z}_{\ge 0} $$

with finite support, where $P(S)$ is the multiplicity of subset $S$.

Thus:

  • one monomial occurrence = one subset,
  • coefficient = number of occurrences of the same subset.

No coefficient encoding inside the subset is used.

This immediately fixes the flaw in the previous solution: coefficients are not elements of sets, so they cannot interact incorrectly under union.

Addition

For polynomials $P,Q$ with multiplicity functions $P(S), Q(S)$, define

$$ (P+Q)(S) = P(S) + Q(S). $$

At the level of families, this is multiset union. ZDDs naturally support this as the sum of characteristic representations: identical subsets simply accumulate multiplicities.

Multiplication

For subsets $A,B \subseteq U$, define

$$ A \oplus B = A \cup B. $$

Because exponent encoding is binary and uses disjoint atoms per variable and bit position, we have

$$ \deg_x(A \cup B) = \deg_x(A) + \deg_x(B), $$

and similarly for $y,z$. Hence:

$$ A \cup B ;\text{represents}; (x^{\deg_x A} y^{\deg_y A} z^{\deg_z A}) \cdot (x^{\deg_x B} y^{\deg_y B} z^{\deg_z B}). $$

Now define polynomial multiplication as convolution of multiplicities:

$$ (PQ)(S) = \sum_{A \cup B = S} P(A),Q(B). $$

This is exactly the Cartesian product of families with union on representatives.

Why coefficients now behave correctly

If a monomial $A$ appears $a$ times in $P$ and $B$ appears $b$ times in $Q$, then the subset $A \cup B$ appears exactly $ab$ times in the product, because there are $a\cdot b$ ordered pairs contributing to it. This matches the required rule that coefficients multiply under monomial multiplication.

This corrects the central error in the previous solution: coefficient arithmetic is not encoded locally inside sets at all, so no incorrect “addition of coefficients under union” can occur.

ZDD interpretation

A ZDD represents exactly a family of subsets of a fixed universe. Interpreting it as a polynomial uses:

  • each root-to-1 path corresponds to a subset $S$,
  • the number of ways that subset is generated in the algebraic construction corresponds to its coefficient.

Addition corresponds to ZDD union. Multiplication corresponds to the standard ZDD product construction, which recursively distributes union over branching and naturally implements the convolution

$$ (A,B) \mapsto A \cup B. $$

Zero suppression is consistent because absence of a subset corresponds to coefficient zero.

Conclusion

Polynomials with nonnegative integer coefficients can be represented by ZDDs by encoding:

  1. Monomials as subsets of binary-weighted variable atoms.
  2. Coefficients as multiplicities of identical subsets (not encoded inside the set).
  3. Addition as multiset union.
  4. Multiplication as Cartesian product with set union on representatives.

This yields a correct semiring isomorphism between polynomial arithmetic and ZDD-based operations on families of subsets.