5
$\begingroup$

Here are the statements. I have several ideas on how to go about proving them, but I couldn't develop those ideas fully. I'd like to ask for some comments/hints.

(i) Show that whenever the natural numbers $\Bbb N$ are finitely coloured, one can find monochromatic $x,y,z \in \Bbb N$ such that $x+y=z$.

(ii) Show that whenever the natural numbers $\Bbb N$ are finitely coloured, one can find distinct monochromatic $x,y,z \in \Bbb N$ such that $x+y=z$.

In my proof attempts I use the infinite Ramsey theorem, which is as follows:

Theorem 1.1. For any positive integer $k$ and and $r$-colouring of $\binom{\Bbb{N}}{k}$, there exists an infinite set $S \subseteq \Bbb N$ for which $\binom{S}{k}$ is monochomatic.

Here of course $k =1$.

My first idea is to use induction on the number of infinite monochromatic sequences, which is at least 1 by the infinite Ramsey theorem. If there's only one such sequence, then it contains a number $u$ that is greater than any number in any other sequences. Then we can have $x = u, y = u, z = 2u$ (or $x = u, y = 2u, z = 3u$ for part (ii)). .

If, otherwise, there are $k$ infinite monochromatic sequences, we can go "color-blind", considering the colors $k-1$ and $k$ to be the same, thus reducing the number of infinite monochromatic sequences by 1. By the induction hypothesis, a monochromatic triple $\{x,y,z\}$ exists, and in particular it must belong to the sequence $S_{k-1} \cup S_k$ (as otherwise the merging or splitting of the two sequences $S_{k-1} \text{ and } S_k$ doesn't affect the membership status of $x,y,z$ and we would be done). But here I can't go further to show that $\{x,y,z\}$ must be either in $S_{k-1} \text{ or } S_k$.

The second idea comes from the observation that, assuming the contradiction, if a sequence contains some members $x \text{ and } y$, then it cannot contains $2x, 2y \text{ and } x+y$. The monochromatic sequences are infinite, the number of colors is finite, and so I think the pigeonhole principle can somehow be used to show that some appropriate multiples of numbers or sums of them would end up in one of the sequences.


Edit: it has been pointed out to me that the triples I seek are called Schur's triples. The proof presented uses a different version of Ramsey's theorem, but I'm still interested in whether it's possible to prove this using my first idea above. I feel like it's come quite close.

$\endgroup$
1
  • 1
    $\begingroup$ Please do not use pictures for critical portions of your post. Pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. I have edited your question to reflect this principle. $\endgroup$ Jan 25, 2020 at 18:27

1 Answer 1

4
$\begingroup$

Referring to i) only, what you are after are monochromatic Schur triples. (A Schur triple is a triple $(a,b,c)$ with $c=b+a$.) It was shown by Schur that for any fixed $r$ there exists some $s(r)$ such that if the integers $1,2,...,s(r)$ are colored in $r$ colors, then one of the color classes contains a monochromatic triple. This is, in fact, an easy consequence of the Ramsey theorem: assuming that every positive integer $z$ is assigned the color $c(z)\in\{1,\dotsc,r\}$, consider the complete graph on $n$ vertices with the edge joining vertices $i$ and $j$ assigned the color $c(|i-j|)$. If $n$ is large enough, then (by the Ramsey theorem) this graph contains a monochromatic triangle, and it is very easy to see that the vertices of this triangle correspond to a Schur triple.

$\endgroup$
6
  • $\begingroup$ Thanks. I believe there's a small typo in the proof? Shouldn't the edge $(i,j)$ be assigned color $c(|i-j|)$, but not color $|i-j|$? $\endgroup$
    – ensbana
    Jan 26, 2020 at 13:51
  • $\begingroup$ Would it be possible to arrive at another proof from my first idea? I feel like it's come very close. $\endgroup$
    – ensbana
    Jan 26, 2020 at 13:52
  • $\begingroup$ Well, no typo in fact: it is very common practice to identify colors with integers. I do not really understand your idea. "For any $r$-coloring of the integers there is an infinite monochromatic sequence"? This is just trivial, and by no means equivalent to the Ramsey theorem. My last remark is that, looking at my solution again, it works perfectly for your question ii), too. $\endgroup$
    – W-t-P
    Jan 26, 2020 at 14:37
  • $\begingroup$ Nice answer! I think it was a typo - the edge between $i, j$ should be the same colour as $|i - j|$, not the colour $|i - j|$ (else it's not a finite colouring). Then in a monochromatic triangle $ijk$, the vertices don't form a Schur triple. Rather, if $i < j < k$, then $j - i$, $k - j$ and $k - i$ is a Schur triple. And indeed these may well not all be distinct even though $i, j, k$ are. The answer to (ii) lies in the fact that "$x = 2y$" is not a partition regular system - we can "wreck" this possibility by refining the given colouring so $x$ and $2y$ are always coloured differently. $\endgroup$ Mar 16, 2023 at 13:17
  • 1
    $\begingroup$ @IzaakvanDongen: Corrected, thanks! $\endgroup$
    – W-t-P
    Mar 20, 2023 at 19:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .