Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '11 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 '11 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 '11 at 19:53
add comment

3 Answers 3

up vote 12 down vote accepted

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

share|improve this answer
    
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 '11 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 '11 at 21:07
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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