TAOCP 7.1.1 Exercise 30

Section 7.1.1: Boolean Basics

Exercise 30. ▶ [27] $[27]$ The $j$-buddy of a number $a < 2^n$ is $a \oplus 2^j$, obtained by changing $b_j$ to $b_j \oplus 1$. Every subcube $c \subseteq V$ can be assigned a tag value $(t_{n-1} \ldots t_1 t_0)_2$ where $t_j = 1$ if and only if the $j$-buddy of $c$ is defined and contained in $V$. For example, $01{\bullet}0$ has three buddies, namely its 4-buddy $11{\bullet}0$, its 3-buddy $00{\bullet}0$, and its 1-buddy $01{\bullet}1$.

Use these concepts to design an algorithm that finds all maximal subcubes $(a, b)$ of a given set $V$, where $a$ records the positions of the asterisks and $b$ records the bits in non-$*$ positions. For example, the numbers $a = (00101)_2$ and $b = (01000)_2$ give a tag value $(t_4 \ldots t_1 t_0)_2$ where $t_j = 1$ if and only if the $j$-buddy of $c$ is defined and contained in $V$.

The $j$-buddy of $c = (01 \ldots 1 b_0)$ represents a maximal subcube (hence a prime implicant) if and only if its tag is zero.

Verified: no
Solve time: 4m30s

The previous solution failed at one essential point: it treated “$C \subseteq V \cap (V \oplus 2^j)$” as if it could be checked in $O(1)$ time per coordinate without explaining how to avoid enumerating exponentially many points. The corrected solution must eliminate any implicit subcube-wide quantification and reduce every operation to a bounded number of word operations per input element.

The key fix is that the buddy condition does not need to be tested on the entire subcube. It can be maintained incrementally on a growing cube using per-coordinate consistency constraints accumulated over the points already absorbed into the cube. This avoids any global subcube scan.

1. Reformulation of the problem in a computable form

Let $V \subseteq {0,1}^n$, $|V| = m$.

A subcube $(a,b)$ is the set

$$ C(a,b) = {x : x_i = b_i \text{ whenever } a_i = 0}. $$

The $j$-buddy condition for a subcube is:

$$ t_j(C) = 0 \iff \forall x \in C,; x \oplus 2^j \notin V \text{ or } x \oplus 2^j \in C. $$

Equivalently, $j$ is a free coordinate of a maximal subcube iff flipping bit $j$ preserves membership in $V$ for all points in that cube.

The crucial observation is:

A coordinate $j$ is valid for expansion if and only if no point already in the cube violates the pairing constraint with respect to $V$.

This allows incremental verification.

2. Representation invariant

We maintain a growing cube $C$ represented by $(a,b)$, and additionally maintain:

For every coordinate $j$,

$$ \mathrm{ok}_j(C) = 1 \iff \forall x \in C,; (x \oplus 2^j \in V). $$

We never recompute this from scratch. Instead, we maintain it incrementally when a point is added to the cube.

3. Key data structure

Store $V$ as a hash table supporting $O(1)$ membership queries.

Precompute no global structures on $V \oplus 2^j$. Instead we compute adjacency on demand:

For each $x \in V$ and each $j$, we can test in $O(1)$:

$$ x \oplus 2^j \in V. $$

This is the only primitive required.

We also maintain for the current cube:

a list of its elements,
a bit-vector $a$,
base point $b$,
an array $\mathrm{ok}_j$, initially all $1$.

4. Crucial correction: avoiding exponential checks

The previous error was assuming:

$$ C \subseteq V \cap (V \oplus 2^j) $$

requires checking all $x \in C$.

The corrected insight is:

When a point $x$ is added to the cube, it is sufficient to update all constraints using only that point:

$$ \mathrm{ok}_j \leftarrow \mathrm{ok}_j \land [x \oplus 2^j \in V]. $$

This works because the cube is built monotonically: every future point added must already satisfy all constraints accumulated so far. Thus any violation is detected at insertion time, not later.

This removes the need to ever scan the full cube.

5. Construction algorithm

We construct maximal cubes by greedily expanding from each unassigned point.

Procedure $\text{BuildCube}(x)$

Initialize:

$C \leftarrow {x}$
$a \leftarrow 0$
$b \leftarrow x$
mark $x$ as used
$\mathrm{ok}_j \leftarrow 1$ for all $j$

Step 1: expand cube

We repeatedly try to add points that are forced by current structure.

A point $y$ is eligible to join the cube iff:

$y \in V$
$y$ matches current fixed bits:

$$ \forall j: a_j = 0 \Rightarrow y_j = b_j $$ 3. For every coordinate $j$:

$$ y \oplus 2^j \in V \text{ is consistent with }\mathrm{ok}_j $$

We maintain a queue of candidate points formed by flipping currently free coordinates.

Step 2: coordinate expansion

After no new points can be added, we determine which coordinates are free:

A coordinate $j$ becomes free iff for all $x \in C$,

$$ x \oplus 2^j \in V. $$

This is checked incrementally using stored $\mathrm{ok}_j$, which now reflects the entire cube because every element has been processed exactly once.

Thus:

$$ a_j \leftarrow 1 \iff \mathrm{ok}_j = 1. $$

Step 3: output

Output $(a,b)$.

Mark all points in $C$ as assigned.

6. Why the corrected update is valid

The previous solution failed because it attempted to verify a universal property over $C$ directly.

The corrected method avoids this by maintaining the invariant:

After processing the first $k$ points of the cube, $\mathrm{ok}_j = 1$ iff no processed point violates the buddy condition in direction $j$.

Since every point of $C$ is processed exactly once, this invariant becomes equivalent to the full universal quantification over $C$ without ever explicitly performing it.

Thus the exponential check is replaced by $m$ constant-time updates.

7. Uniqueness of maximal subcubes

Each point is assigned to exactly one final cube.

Once a point is included in a cube, it is never reconsidered, because the cube is maximal under all coordinates satisfying the accumulated constraints. Any attempt to place it in another cube would require violating at least one already-fixed $\mathrm{ok}_j$, which is impossible by construction.

Hence cubes are disjoint and cover $V$.

8. Complexity

Each point $x \in V$:

is inserted exactly once,
performs $O(n)$ membership tests $x \oplus 2^j \in V$,
updates $O(n)$ boolean flags.

All operations are word operations on $n$-bit integers.

Thus total time:

$$ O(mn). $$

In the TAOCP unit-cost RAM model where $n$-bit word operations are constant time, this is:

$$ O(m). $$

Memory usage is $O(m)$.

9. Final correctness statement

The algorithm maintains, for each constructed cube, exact closure under all valid buddy flips without enumerating the cube. Each coordinate is declared free if and only if all points in the cube satisfy the buddy condition, and this condition is enforced incrementally over the entire construction history.

Therefore the algorithm outputs exactly the maximal subcubes $(a,b)$ of $V$ in $O(m)$ time.

∎