9
$\begingroup$

A blog claims that the following Ramsey-type (or van der Waerden type) problem is open:

If the natural numbers are colored with finitely many colors, must there exist x and y (not both 2) such that x+y and xy are the same color?

Is it correct that this is an open problem, and can anybody help me track down a reference?

Improve this question
$\endgroup$
3
  • $\begingroup$ It is most like a chromatic number problem for a certain kind of graph on the integers greater than 4. Gerhard "Ask Me About System Design" Paseman, 2011.10.17 $\endgroup$
    – Gerhard Paseman
    Commented Oct 17, 2011 at 23:42
  • 2
    $\begingroup$ @Gerhard Paseman It's not just like an chromatic number problem -- it is asking whether the chromatic number of a certain graph is infinite. (Of course, you must be aware of this or you wouldn't have posted your comment.) Unfortunately, that reformulation doesn't seem to help much, essentially because the graph is too concrete for general facts about graph colouring to be of any use. However, I did once attend a talk that discussed the problem in those terms. $\endgroup$
    – gowers
    Commented Oct 18, 2011 at 16:06
  • $\begingroup$ Well..., umm..., yeah. I guess I should have continued with "Perhaps searching with the phrase 'chromatic number' might yield more information on this particular problem.' Not so much need for me to add that now. Gerhard "Can't You Read My Mind?" Paseman, 2011.10.18 $\endgroup$
    – Gerhard Paseman
    Commented Oct 18, 2011 at 19:53

4 Answers 4

Reset to default
15
$\begingroup$

The problem (and several extensions) was mentioned by Hindman.

The case of two colours was solved by Graham:
The interval $[1,252]$ contains $x$ and $y$ such that $x,y, x+y$ and $xy$ are all monochromatic, and 252 is minimal.

References:

1) J Fox, Yeu-Whai Kathy Lin, and M Thibaul
The Clique Number of the Graph of Pairwise Sums and Products is 3 or 4

http://math.mit.edu/classes/18.821/documents/sample.pdf

2) N Hindman, Partitions and sums and products of integers, Trans. Amer. Math. Soc. 247 (1979), 227-245.

http://www.ams.org/journals/tran/1979-247-00/S0002-9947-1979-0517693-4/home.html

(This contains for example Graham's proof and extensions)

3) R.K. Guy, Unsolved problems in number theory, section E29

Improve this answer
$\endgroup$
2
  • $\begingroup$ Note that the claim in my question appears weaker than the claim that Graham proved a particular instance of. The claim in my question makes no requirement about the colors of x and y. Note the following: If the integers from 1 to 8 are colored with two colors, then there must exist x and y such that x+y and xy are the same color. To see this, note that two of the numbers 6,7,8 must be the same color. If 6 and 7 are the same color, take (x,y) = (1,6). If 6 and 8 are the same color, take (x,y) = (2,4). If 7 and 8 are the same color, take (x,y) = (1,7). $\endgroup$
    – idmercer
    Commented Oct 18, 2011 at 19:16
  • $\begingroup$ But in any case, after reading a little more of your references, I see statements of the exact problem I mention, as well as closely related problems. Thank you. $\endgroup$
    – idmercer
    Commented Oct 18, 2011 at 21:07
17
$\begingroup$

Joel Moreira has now proved that we always get monochromatic sets of the shape $\{x, xy, x+y\}$. The main result is much more general and uses a connection with topological dynamics, but he includes a beautifully simple direct proof of this special case, assuming only an easy to check consequence of van der Waerden's theorem.

Improve this answer
$\endgroup$
10
$\begingroup$

The question you pose is (currently) still open, but there was an interesting result by my friend Peter Blanchard which proves a "divisible" version of the problem. Namely, given a finite coloring, there are $x$, $y$ and $x+y$ all with the same color, and $x|y$.

Pseudo-arithmetic sets and Ramsey theory

Improve this answer
$\endgroup$
7
$\begingroup$

Almost this problem appears as Question 11 in Vitaly Bergelson's 1996 paper Ergodic Ramsey Theory - An Update. (In that paper he asks whether $x$, $y$, $x+y$ and $xy$ can all have the same colour.

Improve this answer
$\endgroup$

You must log in to answer this question.

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