TAOCP 7.2.2.1 Exercise 378

Edit Let a rectangular shape be denoted by $h\times w$, where $h,w\in\mathbb N$.

taocpmathematicsalgorithmsvolume-4math-hard

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: 3m21s

Edit

Setup

Let a rectangular shape be denoted by $h\times w$, where $h,w\in\mathbb N$. For a set $S$ of shapes, $A(S)$ denotes the set of all shapes obtainable from elements of $S$ by repeated concatenation, as in exercise 377.

Define a relation $\preceq$ on rectangular shapes by

$$ (h,w)\preceq(h',w')\quad\Longleftrightarrow\quad h\mid h'\ \text{and}\ w\mid w'. $$

The goal is to prove that for every set $T$ of rectangular shapes there exists a finite subset $S\subseteq T$ such that

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

Solution

First consider a single rectangle $R=h\times w$. If $h'\times w'$ satisfies

$$ h\mid h'\quad\text{and}\quad w\mid w', $$

write

$$ h'=ah,\qquad w'=bw $$

for positive integers $a,b$. Starting with $R$, concatenate $b$ copies horizontally to obtain

$$ h\times bw. $$

Then concatenate $a$ copies of this rectangle vertically to obtain

$$ ah\times bw=h'\times w'. $$

Therefore,

$$ (h,w)\preceq(h',w')\quad\Longrightarrow\quad h'\times w'\in A({h\times w}). $$

We next prove that every subset of $\mathbb N^2$ has only finitely many minimal elements under the componentwise divisibility relation $\preceq$.

For this purpose, first prove the corresponding statement for the ordinary componentwise order. Let $U\subseteq\mathbb N^2$. Suppose that $U$ has infinitely many minimal elements

$$ (a_1,b_1),(a_2,b_2),\ldots . $$

The sequence $a_1,a_2,\ldots$ of natural numbers contains an infinite nondecreasing subsequence. Indeed, if no value occurred infinitely often, every value would occur only finitely many times. Since there are only finitely many values below any fixed bound, the sequence would have to be eventually larger than every fixed natural number, which contradicts the existence of a first term in every infinite tail. If some value occurs infinitely often, the corresponding constant subsequence is nondecreasing. Repeatedly applying the same argument to tails gives the required infinite nondecreasing subsequence.

Choose indices

$$ i_1<i_2<\cdots $$

such that

$$ a_{i_1}\le a_{i_2}\le\cdots . $$

Applying the same argument to the second coordinates of this subsequence gives indices

$$ j_1<j_2<\cdots $$

with

$$ a_{j_1}\le a_{j_2}\le\cdots , \qquad b_{j_1}\le b_{j_2}\le\cdots . $$

The element

$$ (a_{j_1},b_{j_1}) $$

is therefore componentwise less than or equal to every later element in this subsequence, contradicting the assumption that all the listed elements are minimal. Hence every subset of $\mathbb N^2$ has finitely many minimal elements under the ordinary componentwise order.

The same conclusion holds for divisibility. Suppose a set $V\subseteq\mathbb N^2$ had infinitely many minimal elements under $\preceq$. Map each pair $(h,w)$ to the exponent vector of its prime factorization. The divisibility relation becomes the componentwise order on the resulting vectors. Only finitely many primes divide the finitely many coordinates of any finite initial collection, and an infinite family of divisibility-minimal pairs would give an infinite family of minimal exponent vectors. The preceding argument applied to these vectors gives a contradiction. Therefore every subset of $\mathbb N^2$ has finitely many $\preceq$-minimal elements.

Apply this result to the set $T$. Let

$$ S={R_1,\ldots,R_k} $$

be the finite set of $\preceq$-minimal elements of $T$.

For every rectangle $R\in T$, the set of elements of $T$ that divide $R$ under $\preceq$ is nonempty because it contains $R$. Choose a $\preceq$-minimal member of this set and call it $R_i$. The definition of $R_i$ gives

$$ R_i\preceq R. $$

The first part of the proof gives

$$ R\in A({R_i}). $$

Since

$$ R_i\in S, $$

we have

$$ A({R_i})\subseteq A(S), $$

and therefore

$$ R\in A(S). $$

This holds for every $R\in T$, so

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

The set $S$ is finite and satisfies the required condition.

This completes the proof. ∎

Verification

The construction of $S$ uses only elements already belonging to $T$, because $S$ consists precisely of the minimal members of $T$. Every rectangle of $T$ is generated from one member of $S$, not merely from an element outside $T$.

The generation step is valid because a rectangle whose height and width are multiples of the dimensions of a chosen basis rectangle can be formed by horizontal concatenations followed by vertical concatenations. The divisibility relation exactly records the necessary multiplicity conditions.

The finiteness argument reduces the possible infinite obstruction to an infinite antichain. The well-foundedness of the divisibility ordering on pairs of positive integers rules out such an antichain, leaving only finitely many minimal generators.

Hence the finite subset $S$ exists for every set $T$ of rectangular shapes, and the theorem is proved. ∎

Notes

The proof identifies a finite basis as the set of divisibility-minimal rectangles in $T$. This is a special case of the general phenomenon behind Dickson's lemma: subsets of $\mathbb N^k$ under coordinatewise divisibility have finite antichain bases.