Skip to main content

Section 5.3 Exercises

These exercises are based on the material covered in Chapter 5.

Use the Hales-Jewett theorem to prove van der Waerden's theorem.

Solution

Let \(l,k\in \mathbb{N}\) be given. Let \(c:\mathbb{N}\to \{ 1,2,\ldots,k\}\) be a \(k\)-colouring of the set of natural numbers. Let \(N=HJ(l,k)\text{.}\)

We define a \(k\)-colouring of the \(N\)-cube \([1,l]^N\) as follows

\begin{equation*} c'(x_1x_2\cdots x_N)=c(x_1+x_2+\ldots+x_N), \ x_1x_2\cdots x_N\in [1,l]^N\text{.} \end{equation*}

By the Hales-Jewett theorem there is a \(c'\)-monochromatic line rooted in the root \(\tau\in [1,l]_\ast^N\text{.}\) Let \(S\subset [1,N]\) be such that

\begin{equation*} \tau(i)\in [1,l]\mbox{ if } i\in S \mbox{ and } \tau(i)=\ast \mbox{ if } i\in [1,N]\backslash S\text{.} \end{equation*}

Let

\begin{equation*} a=\sum _{i\in S}\tau(i) \mbox{ and } d=|[1,N]\backslash S|\text{.} \end{equation*}

Note that

\begin{align*} \sum _{i=1}^N\tau_1(i)\amp = \amp \sum _{i\in S}\tau_1(i) +\sum _{i\in [1,N]\backslash S}\tau_1(i) =a+\sum _{i\in [1,N]\backslash S}1=a+d\\ \sum _{i=1}^N\tau_2(i)\amp = \amp \sum _{i\in S}\tau_2(i) +\sum _{i\in [1,N]\backslash S}\tau_2(i) =a+\sum _{i\in [1,N]\backslash S}2=a+2d\\ \amp \vdots\amp\\ \sum _{i=1}^N\tau_l(i)\amp = \amp \sum _{i\in S}\tau_l(i) +\sum _{i\in [1,N]\backslash S}\tau_l(i) =a+\sum _{i\in [1,N]\backslash S}l=a+ld\text{.} \end{align*}

On the other hand

\begin{equation*} c'(\tau_1)=c'(\tau_2)=\cdots=c'(\tau_l) \end{equation*}

which together with

\begin{equation*} c'(\tau_j)=c\left( \sum _{i=1}^N\tau_j(i)\right)=c(a+jd), \mbox{ for each } i\in [1,l]\text{,} \end{equation*}

implies that

\begin{equation*} c(a+d)=c(a+2d)=\cdots=(a+ld)\text{.} \end{equation*}

Thus, there is a \(c\)-monochromatic \(l\)-term arithmetic progression.

Let \(A=\{a,b,c,d\}\text{.}\) Find all combinatorial lines in \(A^2\text{.}\)

Solution

Since all roots in \(A^2_\ast\) are given by

\begin{equation*} \ast a, \ast b, \ast c,\ast d,a\ast, b\ast, c\ast, d\ast, \ast\ast\text{,} \end{equation*}

all combinatorial lines given by

\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline a a\amp a b\amp a c\amp ad\amp aa\amp ba\amp ca\amp da\amp aa\\ b a\amp b b\amp bc\amp b d\amp ab\amp bb\amp cb\amp db\amp bb\\ c a\amp cb\amp c c\amp cd\amp ac\amp bc \amp cc \amp dc\amp cc\\ d a\amp db\amp d c\amp dd\amp ad\amp bd\amp cd\amp dd\amp dd\\ \hline \end{array} \end{equation*}

Let \(A=\{a,b,c,d\}\text{.}\) Can you find a 2-colouring of \(A^2\) that does not contain a monochromatic combinatorial line? If yes, does this contradict the claim of Hales-Jewett theorem? Justify your answer.

Solution

A possible red/black colouring is given by:

\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline a a\amp a b\amp a c\amp ad\amp a a\amp ba\amp ca\amp da\amp a a\\ b a\amp b b\amp bc\amp b d\amp ab\amp bb\amp cb\amp db\amp bb\\ c a\amp cb\amp c c\amp cd\amp ac\amp bc \amp cc \amp dc\amp cc\\ d a\amp db\amp d c\amp dd\amp ad\amp bd\amp cd\amp dd\amp dd\\ \hline \end{array} \end{equation*}

This does not contradict the Hales-Jewett theorem. It just shows that \(HJ(4,2)>2\text{.}\)

Use the Hales-Jewett theorem to prove that any 2-colouring of positive integers contains a monochromatic 5-term arithmetic progression.

Solution

Let \(c:\mathbb{N}\to \{ 1,2\}\) be a \(2\)-colouring of the set of natural numbers. Let \(N=HJ(5,2)\text{.}\)

We define a \(2\)-colouring of the \(N\)-cube \([1,5]^N\) as follows

\begin{equation*} c'(x_1x_2\cdots x_N)=c(x_1+x_2+\ldots+x_N), \ x_1x_2\cdots x_N\in [1,5]^N\text{.} \end{equation*}

By the Hales-Jewett theorem there is a \(c'\)-monochromatic line rooted in the root \(\tau\in [1,5]_\ast^N\text{.}\) Let \(S\subset [1,N]\) be such that

\begin{equation*} \tau(i)\in [1,N]\mbox{ if } i\in S \mbox{ and } \tau(i)=\ast \mbox{ if } i\in [1,N]\backslash S\text{.} \end{equation*}

Let

\begin{equation*} a=\sum _{i\in S}\tau(i) \mbox{ and } d=|[1,N]\backslash S|\text{.} \end{equation*}

Note that

\begin{align*} \sum _{i=1}^N\tau_1(i)\amp = \amp \sum _{i\in S}\tau_1(i) +\sum _{i\in [1,N]\backslash S}\tau_1(i) =a+\sum _{i\in [1,N]\backslash S}1=a+d\\ \sum _{i=1}^N\tau_2(i)\amp = \amp \sum _{i\in S}\tau_2(i) +\sum _{i\in [1,N]\backslash S}\tau_2(i) =a+\sum _{i\in [1,N]\backslash S}2=a+2d\\ \amp \vdots\amp\\ \sum _{i=1}^N\tau_5(i)\amp = \amp \sum _{i\in S}\tau_5(i) +\sum _{i\in [1,N]\backslash S}\tau_5(i) =a+\sum _{i\in [1,N]\backslash S}5=a+5d\text{.} \end{align*}

On the other hand

\begin{equation*} c'(\tau_1)=c'(\tau_2)=\cdots=c'(\tau_5) \end{equation*}

which together with

\begin{equation*} c'(\tau_j)=c\left( \sum _{i=1}^N\tau_j(i)\right)=c(a+jd), \mbox{ for each } i\in [1,5]\text{,} \end{equation*}

implies that

\begin{equation*} c(a+d)=c(a+2d)=\cdots=(a+5d)\text{.} \end{equation*}

Thus, there is a \(c\)-monochromatic \(5\)-term arithmetic progression.