A proof of Deuber’s theorem using Hales-Jewett’s theorem

In my previous post I explained how Rado’s theorem follows from Deuber’s theorem (which in turn gives a little more than Rado’s theorem, in one direction). The main purpose of this post is to give a full proof of Deuber’s theorem, which will then complete the proof of Rado’s theorem.

I will follow the proof presented in this survey by Gunderson (available here). According to the survey, this proof was first suggested by Leeb and later worked out by Prömel. The main tool for the proof is the Hales-Jewett theorem. I wrote about this theorem twice before in this blog, including a complete proof. In particular I showed how van der Waerden’s theorem on arithmetic progressions, which is an important corollary of Deuber’s theorem, follows from Hales-Jewett’s theorem.

However, Deuber’s theorem (which I will formulate precisely below) implies also Schur’s theorem, and it is not at all clear how to derive Schur’s theorem from Hales-Jewett theorem directly. Thus it is somewhat surprising that one can leverage the Hales-Jewett theorem to deduce Deuber’s theorem.

— 1. Precise definitions and statements —

For completeness I will give, in this section, the precise statements of Deuber’s theorem and Hales-Jewett theorem, starting with the former.

Definition 1 Let {m,p,c\in{\mathbb N}} and let {F_p=\{-p,-p+1,\dots,p-1,p\}}. For each {\vec s=(s_0,s_1,\dots,s_m)\in{\mathbb N}^{m+1}}, the {(m,p,c)}-set generated by {\vec s} is the set

\displaystyle D(m,p,c;\vec s):=\left\{\begin{array}{lr}cs_0&\\is_0+cs_1,& i\in F_p\\i_0s_0+i_1s_1+cs_2,& i_0,i_1\in F_p\\ \vdots&\vdots\\i_0s_0+\cdots+i_{m-1}s_{m-1}+cs_m,&\qquad i_0,\dots,i_{m-1}\in F_p \end{array}\right\}

Thus an {(1,2,1)}-set is a set of the form {\{x,y-2x,y-x,y,x+x,y+2x\}} and a {(2,1,1)}-set is a set of the form {\{x,y,z,y-x,y+x,z-x,z+x,z-y-x,z-y+x,z+y-x,z+y+x\}}. Deuber’s theorem says, roughly speaking, that in a partition of a large {(M,P,C)}-set there exists a smaller {(m,p,c)}-set contained in a single cell of the partition:

Theorem 2 Let {m,p,c,r\in{\mathbb N}}. Then there exist {M,P,C\in{\mathbb N}} such that for any coloring of a {(M,P,C)}-set into {r} colors, there exists a monochromatic subset which is an {(m,p,c)}-set.

For the proof of this theorem it will be convenient to deal with each line of an {(m,p,c)}-set at a time. For clarity we need another definition:

Definition 3 Let {k,m,p,c\in{\mathbb N}} with {k\leq m} and let {\vec s=(s_0,\dots,s_m)\in{\mathbb N}^{m+1}}. We define the set

\displaystyle L(k,p,c;\vec s)=\left\{\sum_{j=0}^{k-1}i_js_j+cs_k:i_0,\dots,i_{k-1}\in F_p\right\}

Also define {L(0,p,c;\vec s):=\{cs_0\}}.

Observe that, whenever {0\leq k\leq m}, the line {L(k,p,c;\vec s)} is a subset of the {(m,p,c)}-set {D(m,p,c;\vec s)}. In fact, an {(m,p,c)}-set is the union of {m+1} lines of the form {L(k,p,c;\vec s)} with {k=0,1,\dots,m}.

Now we give the definitions needed to formulate the Hales-Jewett theorem.

Definition 4 Let {n\in{\mathbb N}}, let {F} be a finite set and let {*} be an element not in {F}.

  • A variable word in {F^n} is an element {w\in(F\cup\{*\})^n} which is not in {F^n} (so the {*} must appear somewhere in {w}).
  • Given a variable word {w} and a letter {a\in F} we denote by {w(a)} the element of {F^n} obtained from {w} by replacing each instance of {*} with {a}.
  • Given a variable word {w}, the combinatorial line induced by {w} is the set {\{w(a):a\in F\}\subset F^n}.

Theorem 5 (Hales-Jewett) For any finite set {F} and any {r\in{\mathbb N}} there exists some {n\in{\mathbb N}} such that for any finite partition of { F^n} into {r} pieces, one of the pieces contains a combinatorial line.

— 2. Proof of Deuber’s theorem —

The first observation towards the proof of Deuber’s theorem is that for any {m,p,c\in{\mathbb N}}, if {0\leq k_0<k_1<\cdots<k_m\leq M} are integers and {\vec S\in{\mathbb N}^{M+1}}, then the union

\displaystyle \bigcup_{i=0}^m L(k_i,p,c;\vec S)

contains an {(m,p,c)}-set, namely {D(m,p,c,\vec s)} where {s=(S_{k_0},S_{k_1},\dots,S_{k_m})\in{\mathbb N}^{m+1}}.

Next observe that if {M>r(m+1)} and an {(M,p,c)}-set is colored into {r} colors in such a way that each line {L(k,p,c;\vec S)} is monochromatic, then, by the pigeonhole principle there are {m+1} lines all of the same color, and by the observation in the previous paragraph we deduce that there exists a monochromatic {(m,p,c)}-set.

The strategy we will use is to start with a {r}-coloring of a huge {(M,P,C)}-set and find (using the Hales-Jewett theorem) a smaller {(M',P',C')}-set with the last line monochromatic. Then (using again the Hales-Jewett theorem) we find a smaller {(M'',P'',C'')}-set whose last line is contained in the last line of the {(M',P',C')}-set (and hence is monochromatic) and such that the second to last line is also monochromatic, and we iterate this process until we have a not so huge (but still pretty large) {(M_0,P_0,C_0)}-set with each line monochromatic, at which point we can finish the proof as outlined above.

To isolate the important steps it is convenient to give a name to colorings of {(m,p,c)}-sets that have certain lines monochromatic:

Definition 6 Let {m,p,c,k\in{\mathbb N}} with {k\leq m}. A coloring of an {(m,p,c)}-set is called {k}-regular if each of the last {k} lines are monochromatic. More precisely, if for each {j>m-k} the {j}-th line {L(j,p,c;\vec s)} is monochromatic.

The main step in the proof is the following lemma, which will later be iterated:

Lemma 7 Let {m,p,c,r\in{\mathbb N}} and let {0\leq k<m}. Then there exist {M,P,C\in{\mathbb N}} such that whenever a {(M,P,C)}-set is given a {k}-regular {r}-coloring, there exists a subset which is a {(m,p,c)}-set with a {(k+1)}-regular {r}-coloring.

Proof: We will apply the Hales-Jewett with {F:=F_p^{m-k}} and the same {r} from this lemma. Let {n} be given by Theorem 5. It will be convenient to denote by {N:=n(m-k)}, and let {M=N+k}, {P=\max\{p^2,pc,c^2\}} and {C=c^2}.

We will show that given any {(M,P,C)}-set one can extract a subset which is a {(m,p,c)}-set whose line {L(m-j,p,c;\vec s)} is contained in {L(M-j,P,C;\vec S)} for each {j=0,\dots,k}, and such that the line {L(m-k,p,c;\vec s)} is a monochromatic subset of the line {L(N,P,C,\vec S)} (note that {|L(m-k,p,c;\vec s)|=|F|}, and hence the {(m-k)}-th line of a {(m,p,c)}-set has the same cardinality as any combinatorial line in {F^n}. This hints at how the Hales-Jewett theorem will be used).

Given {\vec S\in{\mathbb N}^{M+1}} and a {k}-regular {r}-coloring {\chi:D(M,P,C;\vec S)\rightarrow[r]} (where, as usual, we denote by {[r]} the set {\{0,\dots,r-1\}}) of the {(M,P,C)}-set {D(M,P,C;\vec S)} we can induce a coloring of {F^n} as follows: let {I=(I_0,\dots,I_{n-1})\in F^n=(F_p^{m-k})^n=F_p^N} with each

\displaystyle I_j=(i_{j,0},i_{j,2},\dots,i_{j,m-k-1})\in F=F_p^{m-k}

and then define

\displaystyle \tilde\chi(I):=\chi\left(c\sum_{j=0}^{n-1}\sum_{t=0}^{m-k-1}i_{j,t}S_{j(m-k)+t}+CS_N\right)

From the choice of {n} one can now find a variable word {w=(w_1,\dots,w_n)\in(F\cup\{*\})^n} which generates a {\tilde\chi}-monochromatic combinatorial line in {F^n}. Let {A=\{j\in[n]:w_j=*\}} be the (nonempty) set of positions of the wild car {*} in {w} and let {B=[n]\setminus A}. Since for each {j\in B} we have {w_j\in F=F_p^{m-k}}, we can write

\displaystyle w_j=(w_{j,0},w_{j,2},\dots,w_{j,m-k-1})

Next let {\vec s=(s_0,\dots,s_m)\in{\mathbb N}^{m+1}} be the vector defined by

\displaystyle s_j=\left\{\begin{array}{rl} \displaystyle c\sum_{i\in A}S_{i(m-k)+j}&\displaystyle \text{ if }0\leq j<m-k	\\\displaystyle\sum_{i\in B}\sum_{t=0}^{m-k-1}w_{i,t}S_{i(m-k)+t}+cS_N&\displaystyle \text{ if }j=m-k\\\displaystyle cS_{M-m+j}&\displaystyle \text{ if }m-k<j\leq m\end{array}\right.\ \ \ \ \ (1)

I claim that {D(m,p,c;\vec s)} is a {k+1}-regular subset of {D(M,P,C;\vec S)}. I will separate this into 3 claims:

Claim 1 For {0\leq j<k} we have the inclusion {L(m-j,p,c;\vec s)\subset L(M-j,P,C;\vec S)}

Proof: We have

\displaystyle  \begin{array}{rcl}  \displaystyle L(m-j,p,c;\vec s)&=&\displaystyle \left\{\sum_{\ell=0}^{m-j-1}i_\ell s_\ell+cs_{m-j}:i_0,\dots,i_{m-j-1}\in F_p\right\} \\&=&\displaystyle \left\{\sum_{\ell=0}^{m-j-1}i_\ell s_\ell+c^2S_{M-j}:i_0,\dots,i_{m-j-1}\in F_p\right\} \end{array}

From the definition of {\vec s} we see that each {s_\ell} with {\ell=0,1,\dots,m-j-1} depends on disjoint coordinates of {\vec S}. Thus for any {i_0,\dots,i_{m-j-1}\in F_p} we have

\displaystyle \sum_{\ell=0}^{m-j-1}i_\ell s_\ell=\sum_{t=0}^{M-j-1}I_tS_t

for some {I_0,\dots,I_{M-j-1}\in{\mathbb Z}} with {|I_t|\leq p\max(c,p)\leq P}, and this means that

\displaystyle  \begin{array}{rcl} \displaystyle L(m-j,p,c;\vec s)&\subset&\displaystyle \left\{\sum_{t=0}^{M-j-1}I_t S_t+CS_{M-j}:I_0,\dots,I_{M-j-1}\in F_P\right\}\\&=&\displaystyle L(M-j,P,C;\vec S)\end{array}

\Box

Claim 2 The line {L(m-k,p,c;\vec s)} is contained in {L(M-k,P,C;\vec S)} and is monochromatic.

Proof: We have

\displaystyle  \begin{array}{rcl} &&\displaystyle L(m-k,p,c;\vec s)\\&=&\displaystyle \left\{\sum_{t=0}^{m-k-1}i_ts_t+cs_{m-k}:i_0,\dots,i_{m-k-1}\in F_p\right\}\\&=&\displaystyle \left\{\sum_{t=0}^{m-k-1}\sum_{j\in A}ci_tS_{j(m-k)+t}+c\sum_{j\in B}\sum_{t=0}^{m-k-1}w_{j,t}S_{j(m-k)+t}+c^2S_N:(i_0,\dots,i_{m-k-1})\in F\right\}\\&=&\displaystyle \left\{c\sum_{t=0}^{m-k-1}\left(\sum_{j\in A}i_tS_{j(m-k)+t}+\sum_{j\in B}w_{j,t}S_{j(m-k)+t}\right)+CS_N:(i_0,\dots,i_{m-k-1})\in F\right\}\end{array}

Since both {i_t} and {w_{j,t}} are in {F_p}, it is clear that this line is contained in {L(M-k,P,C;\vec S)}. Moreover, this is the set in correspondence with the monochromatic combinatorial line generated by {w} and hence it is monochromatic itself. \Box

Claim 3 For each {j<m-k}, the line {L(j,p,c;\vec s)} is contained in {D(M,P,C;\vec S)}.

Proof:

\displaystyle  \begin{array}{rcl}  \displaystyle L(j,p,c;\vec s)&=&\displaystyle \left\{\sum_{t=0}^{j-1}i_ts_t+cs_j:i_0,\dots,i_{j-1}\in F_p\right\}\\&=&\displaystyle \left\{\sum_{t=0}^{j-1}ci_t\sum_{i\in A}S_{i(m-k)+t}+c^2\sum_{i\in A}S_{i(m-k)+j}:i_0,\dots,i_{j-1}\in F_p\right\} \end{array}

Let {a=\max A} and {i_j=c}. Observe that for any {i_0,\dots,i_{j-1}\in F_p} we have

\displaystyle  \begin{array}{rcl}  &&\displaystyle \sum_{t=0}^{j-1}ci_t\sum_{\ell\in A}S_{\ell(m-k)+t}+c^2\sum_{\ell\in A}S_{\ell(m-k)+j}\\ &=&\displaystyle \sum_{t=0}^j\sum_{\ell\in A}ci_tS_{\ell(m-k)+t}=\sum_{\ell\in A}\sum_{t=0}^jci_tS_{\ell(m-k)+t}\\&=&\displaystyle \sum_{\ell\in A\setminus\{a\}}\sum_{t=0}^jci_tS_{\ell(m-k)+t}+\sum_{t=0}^{j-1}ci_tS_{a(m-k)+t}+CS_{a(m-k)+j}\\&\in&\displaystyle L\big(a(m-k)+j,P,C;\vec S\big)\subset D(M,P,C;\vec S) \end{array}

This finishes the proof. \Box

Since we assumed that the coloring on {D(M,P,C;\vec S)} is {k}-regular, it follows that {D(m,p,c;\vec s)} is {(k+1)}-regular and this finishes the proof of the lemma. \Box

Using Lemma 7 we can now finish the proof of Theorem 2:

Let {m,p,c,r\in{\mathbb N}}. Let {N=mr+1} and let {m_0=N}, {p_0=p} and {c_0=c}. For each {k=1,\dots,N} apply Lemma 7 to find {m_k,p_k,c_k\in{\mathbb N}} such that for any {(N-k)}-regular {r}-coloring of a {(m_k,p_k,c_k)}-set there exists a subset which is a {(m_{k-1},p_{k-1},c_{k-1})}-set with a {\big(N-(k-1)\big)}-regular {r}-coloring.

Now let {M=m_N}, {P=p_N} and {C=c_N} and consider an {r}-coloring of a an arbitrary {(M,P,C)}-set. Observe that this is trivially a {0}-regular coloring. By construction there exists a subset which is a {(m_{N-1},p_{N-1},c_{N-1})}-set with a {1}-regular coloring. Iterating this reasoning one can eventually find a subset which is a {(m_0,p_0,c_0)}-set with a {N}-regular coloring. Since {m_0=N}, this means that each line of this {(N,p,c)}-set is monochromatic. Let {\vec S=(S_0,\dots,S_N)\in{\mathbb N}^{N+1}} be the generator for this {(N,p,c)}-set. By the pigeonhole principle one can find {\frac{N-1}r+1=m+1} lines which are all of the same color, say {0\leq k_0\leq\cdots\leq k_m\leq N} such that the set

\displaystyle \bigcup_{j=0}^mL(k_j,p,c;\vec S)\ \ \ \ \ (2)

is monochromatic. Finally let {\vec s\in{\mathbb N}^{m+1}} be defined by {s_j=S_{k_j}} for each {j=0,\dots,m}. Since {k_j\geq j} we deduce that {L(j,p,c;\vec s)\subset L(k_j,p,c;\vec S)}, and hence the set (2) contains the {(m,p,c)}-set {D(m,p,c;\vec s)}, which is then monochromatic as desired.

Advertisements

About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Combinatorics, Ramsey Theory and tagged , , . Bookmark the permalink.

One Response to A proof of Deuber’s theorem using Hales-Jewett’s theorem

  1. Pingback: New polynomial and multidimensional extensions of classical partition results | I Can't Believe It's Not Random!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s