1
$\begingroup$

I've got a homework exercise on Schur's theorem, which says that for any $r \in \mathbb N$ there is an $n \in \mathbb N$ such that for any $r$-colouring of $[n] := \{1, \dots, n\}$ there is a monochromatic triple $\{x, y, x + y\} \subset [n]$.

An "infinite" version of this theorem is that for any $r$-colouring of $\mathbb N$, there are infinitely many such monochromatic triples $\{x, y, x + y\}$. The exercise is to prove Schur's theorem implies this assertion, and conversely the assertion implies Schur's theorem.

I've proved the forward direction, but am getting stuck on the converse. I'm trying to derive a contradiction from the negation of Schur's theorem and the assertion:

Suppose there is some $r$ such that for all $n$ there is some $r$-colouring of $[n]$ with no such monochromatic triple (negation of Schur's theorem). Now I can use the assertion to know there are infinitely many monochromatic triples $\{x, y, x+y\}$ in any extension of my colouring to $\mathbb N$, but the problem is they needn't lie in $[n]$. I can also start with any $r$-colouring of $\mathbb N$ and get a smallest monochromatic triple, but since $\neg$Schur "chooses" the colouring after the triple, I cannot be sure the triple is contained in $[n]$.

Can anyone provide me with some insight or a hint on how to proceed?

$\endgroup$
3
$\begingroup$

Results like this are typical applications of compactness arguments, very common in Ramsey theory.

You have that for all $[n]$ there is an $r$-coloring of $[n]$ with no monochromatic triples $\{x,y,x+y\}$. Let $C$ be the set of all such $r$-colorings of $[n]$, where $n$ varies over the natural numbers. We can think of $C$ as a tree, each level of which is finite. (The $n$-th level of the tree consists simply of the $f\in C$ with domain $[n]$.) The order in the tree is given by: If $f,g\in C$, $[n]$ is the domain of $f$, and $[m]$ is the domain of $g$, with $n<m$, then we say that $f<g$ iff the restriction of $g$ to $[n]$ is $f$. Note that if $n<m$ and $g$ is in the $m$-the level of $C$, then the restriction of $g$ to $[n]$ is in the $n$-th level of $C$.

OK, the point is that the tree is infinite (your assumption is that there are nodes of the tree at all levels). But each level of the tree is finite (since, regardless of whether they are colorings without monochromatic triples $\{x,y,x+y\}$ or not, there are only finitely many $r$-colorings of $[n]$). This allows us to define a sequence of functions $f_1<f_2<\dots$, with each $f_i$ in level $i$. The key observation is this:

Given any level $n$, $C$ is the union of the trees $C_f$ where $f$ varies over all nodes at level $n$, and $C_f$ consists of $f$, its restrictions to shorter domains, and all functions in $C$ at larger domains that extend $f$. Since $C$ is infinite, and there are only finitely many such $f$, then $C_f$ is infinite for at least one such $f$.

We use the observation to define the sequence $f_1<f_2<\dots$ recursively: Pick $f_1$ at level $1$ with $C_{f_1}$ infinite. Given $f_k$ with $C_{f_k}$ infinite, apply the key observation to $C_{f_k}$ in place of $C$, and $n=k+1$. This gives us at least one function $f$ at level $k+1$ that extends $f_k$, and such that $C_{f}$ is infinite. Call it $f_{k+1}$ and continue.

The outcome of this is that we can define now a coloring of all of $\mathbb N$, simply by putting together the functions $f_n$. In set theoretic notation, the coloring is just $\bigcup_n f_n$. If you prefer, we define the coloring $F:\mathbb N\to[r]$ by $F(n)=f_k(n)$ for any $k\ge n$. The point is that $F$ has no monochromatic triples $\{x,y,x+y\}$, because any such triple is monochromatic for any $f_k$ with $k$ large enough. But no $f_k$ has monochromatic Schur triples.

This completes the proof, but let me add that this is called a compactness argument, because if the $n$-th level of $C$ has size $t_n$, and we let $X_n$ be the discrete topological space on $r^{t_n}$ points, then the existence of sequences $f_1<f_2<\dots$ as required is a simple consequence of the compactness of the product space $\prod_n X_n$ (There is leeway here; one can instead simply consider $[r]^{\mathbb N}$, or have each $X_n$ have as many points as the $n$-th level of $C$). In the literature, compactness arguments are sometimes obtained that way, topologically. Sometimes the topological argument is abstracted and called Rado's selection principle. Sometimes the applications of compactness are obtained precisely as we did, building an infinite branch through an infinite but finite-branching tree. In this form, the result is referred to as König's lemma. Yet other times the argument is cast as a corollary of the compactness of propositional logic.

To close, my student Summer Kisner wrote her Master's thesis on Schur's lemma and graduated this May. You may find a short summary here, together with a link to download the thesis.

$\endgroup$
  • $\begingroup$ Thanks Andres for a very complete answer! I'd seen this type of construction before in infinite versions of Ramsey's theorem (for example, constructing a monochromatic pair inducing subset of $\mathbb N$ from a 2-colouring of $[n] \choose 2$), but I didn't see how to apply it here. Seeing it as a tree is quite helpful, as well as the different compactness arguments. $\endgroup$ – Mark Nov 21 '13 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.