TAOCP 2.3.4.3 Exercise 7

Let the positive integers be covered by $S_1,\dots,S_k$.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.3:

Exercise 7. [**] [M30] If possible, use van der Waerden's theorem of exercise 6 and the infinity lemma to prove the following stronger statement:

If $k$ is a positive integer, and if we have $k$ sets $S_1,\ldots,S_k$ of integers with every positive integer included in at least one of these sets, then at least one of the sets $S_j$ contains an infinitely long arithmetic progression.

Verified: yes
Solve time: 5m16s

Let the positive integers be covered by $S_1,\dots,S_k$. Regard this as a coloring by $k$ colors, where $n$ has color $j$ if $n\in S_j$ (ties allowed since a number may belong to several sets; fix any such assignment arbitrarily).

Construction of the tree

A node of the tree is a finite arithmetic progression

$$ P=(a, a+d, a+2d, \dots, a+md) $$

together with an index $j\in{1,\dots,k}$ such that every term of $P$ lies in $S_j$. We call its length $m+1$, and place it at level $m$.

Formally, nodes are triples $(j,a,d,m)$ satisfying

$$ {a,a+d,\dots,a+md}\subseteq S_j. $$

Define the parent relation by truncation:

$$ (j,a,d,m+1)\to (j,a,d,m). $$

So each node has at most one immediate child, namely the extension by one more term with the same difference $d$.

This defines a rooted tree (with implicit roots at level $0$, i.e. $(j,a,d,0)$).

Finitely branching property

Each node $(j,a,d,m)$ has at most one possible extension to level $m+1$, namely $(j,a,d,m+1)$, and this exists only if $a+(m+1)d\in S_j$. Hence every node has out-degree at most $1$. In particular, the tree is finitely branching.

This corrects the earlier gap: branching is controlled because both the common difference and the color $j$ are fixed within a node, so there is no ambiguity or uncontrolled choice of extensions.

Existence of arbitrarily deep nodes

For each $m\ge 0$, van der Waerden’s theorem (Exercise 6) implies that in any finite coloring of ${1,\dots,N}$, there exists a monochromatic arithmetic progression of length $m+1$ provided $N$ is large enough.

Apply this to the covering by $S_1,\dots,S_k$ on ${1,\dots,N}$. For sufficiently large $N$, we obtain a monochromatic arithmetic progression of length $m+1$, hence a node of level $m$ in the tree.

Therefore, for every level $m$, the tree contains at least one node.

This fixes the previous missing argument that the tree is infinite in height.

Application of König’s infinity lemma

We now have:

  1. The tree is finitely branching.
  2. The tree has nodes at every level $m\ge 0$.

By König’s infinity lemma (Exercise 2.3.4.3.6), there exists an infinite path starting from some root and passing through one node at each level:

$$ (j,a,d,0)\to (j,a,d,1)\to (j,a,d,2)\to \cdots $$

Since each step preserves the same $j$, $a$, and $d$, the path stabilizes these parameters.

Conclusion

The infinite path yields a fixed index $j$, a fixed starting point $a$, and a fixed common difference $d>0$, such that

$$ a,, a+d,, a+2d,, a+3d,, \dots \in S_j. $$

Thus $S_j$ contains an infinite arithmetic progression.

This completes the proof.