4

1

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?

flag
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 – Gerhard Paseman Oct 17 2011 at 23:42
2 
 @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. – gowers Oct 18 2011 at 16:06
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 – Gerhard Paseman Oct 18 2011 at 19:53

3 Answers

10

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

link|flag
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). – idmercer Oct 18 2011 at 19:16
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. – idmercer Oct 18 2011 at 21:07
6

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.

link|flag
6

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

link|flag

Your Answer

Get an OpenID
or

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