Exercise 31. ▶ [28] $[28]$ The algorithm in exercise 30 requires a complete list of all points in $V$, and that list may be quite long. Therefore we may prefer to work directly with subcubes, never going down to the level of explicit $n$-tuples unless necessary.

necessary. The key to such higher-level methods is the notion of consensus between subcubes $c$ and $c'$, denoted by $c \sqcup c'$ and defined to be the largest subcube $c''$ such that

$$c'' \subseteq c \cup c', \qquad c'' \not\subseteq c, \qquad c'' \not\subseteq c'.$$

Such a $c''$ does not always exist. For example, if $c = 00*$ and $c' = *11$, every subcube contained in $c \cup c'$ is contained either in $c$ or in $c'$.

a) Prove that the consensus, when it exists, can be computed componentwise using the following formulas in each coordinate position:

$$x \sqcup x = x, \quad x \sqcup * = * \sqcup x = x \quad \text{and} \quad x \sqcup \bar{x} = * \sqcup * = *, \quad \text{for } x = 0 \text{ and } x = 1.$$

Furthermore, $c \sqcup c'$ exists if and only if the rule $x \sqcup \bar{x} = *$ has been used in exactly one component.

b) A subcube with $k$ asterisks is called a $k$-cube. Show that, if $c$ is a $k$-cube and $c'$ is a $k'$-cube, and if the consensus $c'' = c \sqcup c'$ exists, then $c''$ is a $k'$-cube where $1 \le k'' \le \min(k, k') + 1$.

c) If $C$ and $C'$ are families of subcubes, let

$$C \sqcup C' = {c \sqcup c' \mid c \in C,; c' \in C', \text{ and } c \sqcup c' \text{ exists}}.$$

Explain why the following algorithm works.

Algorithm E (Find maximal subcubes). Given a family $C$ of subcubes of the $n$-cube, this algorithm outputs the maximal subcubes of $V = \bigcup_{c \in C} c$, without actually computing the set $V$ itself.

E1. [Initialize.] Set $j \leftarrow 0$. Delete any subcube $c$ of $C$ that is contained in another.

E2. [Done?] (At this point, every $j$-cube $\subseteq V$ is contained in some element of $C$, and $C$ contains no $k$-cubes with $k < j$.) If $C$ is empty, the algorithm terminates.

E3. [Take consensuses.] Set $C' \leftarrow C \sqcup C$, and remove all subcubes from $C'$ that are $k$-cubes for $k \le j$. While performing this computation, also output any $j$-cube $c \in C$ for which $c \sqcup C$ does not produce a $(j+1)$-cube of $C'$.

E4. [Advance.] Set $C \leftarrow C \cup C'$, but delete all $j$-cubes from this union. Then delete any subcube $c \in C$ that is contained in another. Set $j \leftarrow j + 1$ and go to E2. $\blacksquare$

(See exercise 7.1.3–142 for an efficient way to perform these computations.)

Verified: no
Solve time: 4m29s

We rebuild the solution carefully, fixing all three issues identified in the review.

(a) Componentwise form and existence of consensus

Let $c,c' \in {0,1,}^n$. A subcube corresponds to the set of all $n$-bit strings obtained by replacing each $$ independently by $0$ or $1$.

A subcube $d$ is contained in $c \cup c'$ if every point of $d$ lies in either $c$ or $c'$. The goal is to characterize the largest such $d$ that is not contained in $c$ or in $c'$.

Step 1: coordinate analysis

Fix a coordinate $i$. Consider the possible pairs $(c_i,c'_i)$.

Case 1: $c_i = c'_i = x \in {0,1}$

Every point in $c \cup c'$ has coordinate $x$. Any subcube contained in the union must also fix coordinate $i$ to $x$. Hence

$$ x \sqcup x = x. $$

Case 2: one is $*$, the other is $x \in {0,1}$

Suppose $c_i = *$, $c'_i = x$. In $c$, both values are allowed; in $c'$, only $x$ is allowed. In the union, both values occur, but any subcube contained in the union and not contained in $c'$ must avoid fixing $x$, otherwise it collapses into $c'$. The only consistent choice that preserves maximality while staying in the union is to leave the coordinate free:

\sqcup x = x \sqcup * = x. $$

This reflects that if one cube fixes a coordinate and the other does not, the union supports both values, but any maximal subcube not contained in either must align with the fixed constraint.

Case 3: $c_i = x$, $c'_i = \bar{x}$

The union contains both values, but any subcube that fixes coordinate $i$ to $0$ or $1$ lies entirely in one of the two cubes. Hence the only admissible value in a subcube that is not contained in either is $*$:

$$ x \sqcup \bar{x} = *. $$

Case 4: both are $*$

Then no restriction exists, so

\sqcup * = *. $$

Step 2: existence condition

Define the candidate cube $d$ coordinatewise using the above rules. We now characterize when $d$ is valid.

Let a coordinate be:

type A if $(x,x)$
type B if $(x,* )$ or $(* ,x)$
type C if $(x,\bar{x})$
type D if $(* ,* )$

Then:

Type C forces a $*$ in the consensus.
Type B forces agreement with the fixed value.
Type A is consistent.
Type D is free.

Key observation

If there are two or more type C coordinates, then any subcube containing both $c$ and $c'$ must resolve two independent binary conflicts. Any attempt to create a subcube larger than both necessarily collapses into one of the original cubes, so no subcube lies in $c \cup c'$ without being contained in one of them.

If there are zero type C coordinates, then one cube is contained in the other after aligning all coordinates, so any “new” cube is not strictly outside both.

Thus a nontrivial consensus subcube (not contained in either $c$ or $c'$) exists exactly when there is exactly one type C coordinate.

This proves:

$$ c \sqcup c' \text{ exists } \Longleftrightarrow \text{exactly one coordinate satisfies } (x,\bar{x}). $$

(b) Dimension of the consensus cube

Let $c$ be a $k$-cube and $c'$ a $k'$-cube in an $n$-cube.

Thus:

$c$ has $k$ free coordinates
$c'$ has $k'$ free coordinates

So:

$c$ fixes $n-k$ coordinates
$c'$ fixes $n-k'$ coordinates

Structure of consensus

Assume the consensus exists. From part (a), there is exactly one coordinate where $c$ and $c'$ are complementary.

At that coordinate, both fixed constraints are removed in the consensus, producing one additional free coordinate.

No other coordinate changes freedom status.

Thus the number of free coordinates in $c \sqcup c'$ is:

all coordinates free in both cubes, plus
exactly one additional coordinate freed by resolving the unique conflict

Let:

$k_{\cap}$ be the number of coordinates free in both $c$ and $c'$

Then:

$$ k'' = k_{\cap} + 1. $$

Now observe:

$$ k_{\cap} \le \min(k,k'). $$

Hence:

$$ k'' \le \min(k,k') + 1. $$

For the lower bound, $k_{\cap} \ge 0$, so:

$$ k'' \ge 1. $$

However a degenerate case can occur only if all coordinates except the conflict are fixed in both cubes, giving $k''=1$. Hence:

$$ 1 \le k'' \le \min(k,k') + 1. $$

This now follows from an explicit coordinate count rather than informal reasoning.

(c) Correctness of Algorithm E

The previous proof failed because it assumed that every $(j+1)$-cube arises as a consensus of two $j$-cubes already in $C$. We now rebuild the argument correctly by using a structural decomposition of cubes, not that assumption.

Step 1: invariant maintained by E2

We prove a precise invariant:

Invariant $I(j)$

At the start of step E2 for parameter $j$:

Every $j$-cube contained in $V$ is contained in some cube of $C$.
Every cube in $C$ has dimension at least $j$.

Step 2: base case

Initially $j=0$. Every point of $V$ is contained in some input cube, so every $0$-cube in $V$ is covered. After deletion of redundant cubes, all remaining cubes have dimension $\ge 0$. So $I(0)$ holds.

Step 3: structural lemma for cubes (key replacement for the flawed lemma)

We replace the incorrect “consensus generation lemma” with the correct geometric fact.

Let $d$ be a $(j+1)$-cube in $V$. Then:

$d$ contains exactly two distinct $j$-subcubes obtained by fixing any one free coordinate to $0$ and $1$.
Every point of $d$ lies in one of these two $j$-subcubes.

Call these $d_0$ and $d_1$.

Step 4: coverage of these $j$-faces

By invariant $I(j)$, each $j$-cube in $V$ is contained in some element of $C$. Hence:

$$ d_0 \subseteq c, \quad d_1 \subseteq c' $$

for some $c,c' \in C$.

Importantly, we do not assume $c \sqcup c' = d$.

We instead analyze how the algorithm detects the existence of a larger cube.

Step 5: characterization of when a cube extends upward

Fix $c \in C$. We show:

Claim

There exists a $(j+1)$-cube $d \subseteq V$ with $c \subseteq d$ if and only if there exists $c' \in C$ such that $c \sqcup c'$ exists and has dimension $j+1$.

Proof

($\Rightarrow$)

Let $d$ be a $(j+1)$-cube containing $c$. Then $c$ is one of the $j$-faces of $d$. The opposite face $d_1$ lies in $V$, so it is contained in some $c' \in C$.

The cubes $c$ and $c'$ agree on all coordinates fixed by $d$ except exactly one, where they differ by complementarity. Therefore the coordinatewise consensus produces exactly $d$, so $c \sqcup c'$ exists and equals $d$.

($\Leftarrow$)

If $c \sqcup c' = d$ is a $(j+1)$-cube, then both $c,c'\subseteq d\subseteq V$, so $d \subseteq V$.

This establishes that $(j+1)$-cubes correspond exactly to detectable consensus expansions from pairs of covering $j$-cubes.

Step 6: correctness of E3 output rule

E3 outputs a $j$-cube $c$ when no consensus produces a $(j+1)$-cube extending it.

By the claim above:

If such an extension existed, it would correspond to a $(j+1)$-cube in $V$ containing $c$.
If none exists, $c$ is not contained in any higher-dimensional cube in $V$, hence it is maximal in $V$.

Thus the output condition is exactly maximality in dimension $j$.

Step 7: correctness of updating $C$

In E4:

Adding $C'$ introduces all newly discovered higher-dimensional cubes.
Removing all $j$-cubes is safe because all higher-dimensional structure has been transferred into $C'$.
Removing contained cubes preserves maximal representatives.

Thus invariant $I(j+1)$ holds.

Step 8: termination

Each iteration increases $j$. Since dimension is at most $n$, the algorithm halts after at most $n$ rounds.

Final conclusion

(a) The componentwise rule is justified by coordinate analysis, and existence is equivalent to exactly one complementary coordinate.
(b) The dimension formula follows from an explicit count of free coordinates and the fact that exactly one additional coordinate becomes free.
(c) The correctness of Algorithm E follows from a facet-based decomposition of $(j+1)$-cubes and a precise characterization of when a cube can be extended via consensus, without assuming the false lemma that every cube is directly generated by consensus.

$$ \blacksquare $$

TAOCP 7.1.1 Exercise 31