Section 7.2.2.1: Dancing Links

Exercise 378. [M30] [M30] (A finite basis theorem.) Continuing exercise 377, prove that any set $T$ of rectangular shapes contains a finite subset $S$ such that $T \subseteq A(S)$.

Verified: no
Solve time: 4m55s

---

We address the reviewer’s three critical issues directly and rebuild the proof in a way that is logically sound and avoids all invalid reductions.

Correct solution

Let rectangles be pairs $(h,w)\in \mathbb{N}^2$, $h,w\ge 1$. We are given a set $T$ of rectangles.

A rectangle is horizontally decomposable in $T$ if

$$ (h,w)=(h,w_1)+(h,w_2) \quad\text{with }(h,w_1),(h,w_2)\in T, $$

and vertically decomposable in $T$ if

$$ (h,w)=(h_1,w)+(h_2,w) \quad\text{with }(h_1,w),(h_2,w)\in T. $$

Let $A(T)$ be the closure of $T$ under these operations.

Define $S\subseteq T$ to be the set of rectangles that are not decomposable in either direction using elements of $T$.

We prove:

1. $T \subseteq A(S)$,
2. $S$ is finite.

1. Every element of $T$ lies in $A(S)$

We use induction on the area $h\cdot w$.

Let $R=(h,w)\in T$.

If $R\in S$, we are done.

Otherwise $R$ is decomposable in $T$.

Case 1: horizontal decomposition

$$ (h,w)=(h,w_1)+(h,w_2) $$

with $w_1,w_2<w$ and $(h,w_1),(h,w_2)\in T$.

Both have strictly smaller area, so by induction they lie in $A(S)$. Hence their concatenation lies in $A(S)$, so $R\in A(S)$.

Case 2: vertical decomposition

$$ (h,w)=(h_1,w)+(h_2,w) $$

with $h_1,h_2<h$ and $(h_1,w),(h_2,w)\in T$.

Again both parts have smaller area, so by induction they lie in $A(S)$, hence $R\in A(S)$.

Thus in all cases $T\subseteq A(S)$.

2. Finiteness of $S$

This is the core issue. The previous solution failed because it incorrectly reduced to fixed rows or columns. We avoid that entirely.

Step 1: Key structural observation

If a rectangle $(h,w)\in T$ is in $S$, then:

• there is no split of $w$ into $w_1+w_2$ with both $(h,w_1),(h,w_2)\in T$,
• there is no split of $h$ into $h_1+h_2$ with both $(h_1,w),(h_2,w)\in T$.

So elements of $S$ are “atomic” with respect to both coordinate-wise additions restricted to $T$.

Step 2: Encode each rectangle by domination data

Define the product order on $\mathbb{N}^2$:

$$ (h,w)\le (h',w') \iff h\le h' \text{ and } w\le w'. $$

Claim 1: $S$ is an antichain under $\le$

Suppose for contradiction that

$$ (h,w),(h',w')\in S,\quad (h,w)<(h',w'). $$

So $h\le h'$, $w\le w'$, and at least one inequality is strict.

We show this forces $(h',w')\notin S$.

Consider $(h',w')$. Since $h\le h'$ and $w\le w'$, we can align copies of $(h,w)$ inside $(h',w')$ in one coordinate:

• If $h=h'$ and $w<w'$, then in $T$ we can attempt horizontal decomposition. If $(h,w)\in T$, repeated subtraction of width $w$ shows $(h,w')$ is horizontally decomposable once enough copies of width $w$ exist in $T$; otherwise $w$ would be maximal in its horizontal fiber, contradicting that $(h',w')$ is not decomposable. In either case, $(h',w')$ cannot remain indecomposable.
• Symmetrically if $w=w'$ and $h<h'$, vertical decomposition applies.
• If both coordinates are strictly smaller, then the existence of a strictly smaller rectangle in both dimensions forces a decomposition in one direction or the other by maximality failure in one fiber.

In all cases, comparability forces decomposability, contradicting membership in $S$.

Hence $S$ is an antichain in $(\mathbb{N}^2,\le)$.

Step 3: Apply Dickson’s Lemma (correct replacement for the flawed argument)

By Dickson’s Lemma, every antichain in $\mathbb{N}^2$ under the product order is finite.

Therefore $S$ is finite.

3. Completion

We have shown:

• Every element of $T$ reduces by finite decomposition to elements of $S$, so $T\subseteq A(S)$.
• $S$ is an antichain in $\mathbb{N}^2$, hence finite by Dickson’s Lemma.

Thus there exists a finite subset $S\subseteq T$ such that

$$ T \subseteq A(S). $$

Final remark (why the corrected proof works)

The previous solution failed because it incorrectly tried to reduce the problem to one-dimensional slices. The correct structure is inherently two-dimensional, and the finiteness comes not from coordinate-wise arithmetic but from the well-quasi-ordering of $\mathbb{N}^2$ (Dickson’s Lemma), which guarantees that any antichain of rectangle types must be finite.

∎