Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to show that the following statement is false: whenever $\mathbb{N}$ is finitely coloured by $c: \mathbb{N} \to \{1,\ldots,k\}$ (in the sense of Ramsey theory), there exists an infinite set $x_1 <x_2 <x_3 \ldots$ such that the set $\{x_i+2x_j: i \neq j\}$ is monochromatic. It is easy enough to show that this statement is true for the set $\{x_i+2x_j: i < j\}$, so I get the impression that any attempt to prove that it also held for $\{x_i+2x_j: i \neq j\}$ would fail because $x_i + 2x_j$ and $x_j + 2x_i$ might have different colours, or something along those lines.

So, I tried to find a colouring $c$ for which there is clearly no such monochromatic set, but I'm not having any luck so far by attempting to pick a colouring for which $c(x_i + 2x_j) \neq c(x_j + 2x_i)$. The closest I think I've got is by choosing $c(z)$ to be the parity of the largest power of $2$ which divides $z$: for example, we colour $1$ "EVEN", 2 "ODD", 4 EVEN, 6 ODD, 17 EVEN. This does indeed give $x_i + 2x_j$ and $x_j + 2x_i$ different colours, unless the powers of 2 which divide them are at most one apart; e.g. $x_i=2^ap,\,x_j = 2^aq$ or $x_j = 2^{a \pm 1}q$ with $p,\,q$ odd. In the former case, this gives you the same colour, and in the latter case you necessarily can't say what the colour is because you end up trying to count the power of 2 dividing $2^{a+1}(p+q)$, and $p+q$ is some even number.

I'm not sure where I'm going wrong: what I'm trying to do is produce a colouring such that for any $x_i$ and $x_j$ in our set, $x_i + 2x_j$ and $x_j + 2x_i$ are differently coloured. In fact we only actually need to find 2 elements which are differently coloured, not necessarily every pair, so maybe my attempt to prove this is overkill. For example, I tried pursuing my above colouring, assuming all $x_i$ are of the form $2^a s$ or $2^{a+1}t$ for odd $s,\,t$ but was unable to derive a contradiction. I think I might be looking at the wrong colouring - could anyone please suggest how to prove that the statement is false? Many thanks for your help.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

Let $h(n)$ be the highest power of two appearing in the binary expansion of $n > 0$, and let $c(n)$ be the parity of $h(n)$.

Suppose $h(x) = n$ and $h(y) \leq n-1$. Note that $h(x+2y) \in \{n,n+1\}$ and $h(2x+y) \in \{n+1,n+2\}$. More accurately, $h(x+2y) = n$ iff $x+2y < 2^{n+1}$, and $h(2x+y) = n+1$ iff $2x+y < 2^{n+2}$. This shows that $h(x+2y) = n$ implies $h(2x+y) = n+1$, and so in this case, $c(x+2y) \neq c(2x+y)$. The only way we can have $c(x+2y) = c(2x+y)$ is when $h(x+2y) = h(2x+y) = n+1$. In this case $$ 2^{n+2}-4y \leq 2x < 2^{n+2}-y. $$ In particular, if $h(y),h(z) < h(x)$ and both $c(x+2y) = c(2x+y)$ and $c(x+2z) = c(2x+z)$, we must have $y \leq 4z$ and $z \leq 4y$. This implies $|h(y)-h(z)| \leq 2$.

Now suppose you have an infinite set $A$ such that $c(x+2y) = c(2x+y)$ for all $x,y \in A$. Pick some $y \in A$. Since $A$ is infinite, there is some $z \in A$ such that $|h(y)-h(z)| > 2$. Again since $A$ is infinite, there is some $x \in A$ such that $h(x) > \max(h(y),h(z))$. We have reached a contradiction.

share|improve this answer
    
Very nice!$\quad$ –  Brian M. Scott May 9 '12 at 3:48
    
That's perfect, thanks Yuval! I guess I wasn't too far off with my powers of 2 attempt, but the advantage of using $h(x)$ in yours is that it gives you a property which can only be the same for a finite bounded number of $x$; dividing powers of 2 can obviously be equal for any 2 integers, no matter how far apart. –  Spyam May 9 '12 at 9:17
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.