# Ramsey Theory: Showing the existence of a special set of natural numbers.

Show that there is an infinite set of natural numbers such that the sum of any two elements has an even number of prime factors.

My attempt:

Define a coloring on the doubletons of $\mathbb{N}$, that is a coloring $f:\mathbb{N}^{(2)}\to \{0,1\}$ by: $$f(\{x,y\}) = \left\{ \begin{array}{ll} 0 & \quad \text{if x+y is has an even number of prime factors} \\ 1 & \quad \text{otherwise} \end{array} \right.$$ By the Infinite Ramsey Theorem, there exists an infinite subset $N\subseteq \mathbb{N}$ such that all of the doubletons of $N$ are colored $0$ or all of the doubletons of $N$ are colored $1$. If $N$ is monochromatic in $0$, then we are done, as $N$ witnesses the desired property. Otherwise, assume, $N$ is monochromatic in $1$. Then for every doubleton of $\{x,y\}\subseteq N$, $x+y$ has an odd number of prime factors. If there exists a prime $p$ such that for all $x\in N$, $p\nmid x$. Then define: $$pN=\{px \mid x\in N\}$$ We have that for arbitrary $\{x,y\} \subseteq N$, $x+y$ has an odd number of prime factors. Therefore, we have that $px + py = p(x+y)$ will have an even number of prime factors and we are done as $pN$ witnesses the desired property. Otherwise, we have that $N$ satisfies: $$\forall p \exists x (p\mid x)$$ If there is a $p$ such that $p$ only divides finitely many $\{x_1,x_2,\ldots, x_n\} \subseteq N$
then $N\setminus \{x_1,x_2,\ldots, x_n\}$ is still an infinite set and we do the same trick as before: $$p(N\setminus \{x_1,x_2\ldots,x_n\})=\{px: x\in N\setminus \{x_1,x_2\ldots,x_n\}\}$$ witnesses the desired property. If not then for all $p$, $p$ divides infinitely many of the elements of $N$. In fact, for every prime $p$, $p$ divides all but finitely many elements of $N$. Because if there is an infinite subset $A\subseteq N$ and a prime $p$ such that $p$ divides each element of $A$ but $N\setminus A$ is infinite, then we can appeal to the same argument as above to obtain a set that has the desired properties. Now enumerate $N$ as $N=\{n_1,n_2,n_3,\ldots\}$, we know that for each prime $p$, there is an index $i$, such that $p\mid n_j$ for all $j\ge i$. We can deduce that there is a finite index $k$, such that every prime $p$ divides $n_i$ for $i\ge k$. If not, then there is a prime $p$, such that for all $k\in \mathbb{N}$, $p\nmid n_i$ for $i\ge k$ which is not the case. So every prime number divides $\{n_k,n_{k+1},n_{k+2},\ldots \}$ a wild contradiction to the fact that $N$ is a subset of natural numbers.

My Question:

Am I coming to a false conclusion in the last paragraph? I feels ridiculous that I should end up deducing that the set: N has numbers that infinitely many primes divide.

Wrong conclusion. $$We can deduce that there is a finite index $k$, such that every prime $p$ divides $n_i$ for $i\ge k$." is not true, we cannot deduce that...

• Everything goes well, until the last paragraph. You have that for each $p$ there is an $i$ such that $p\mid n_j$ for all $j\ge i$. This does not imply that there is a fixed $k$ such that $p\mid n_i$ for all $i\ge k$. For instance, let $n_i$ be the product of the first $i$ primes, for all $i$. – Andrés E. Caicedo May 7 '14 at 3:11
• @AndresCaicedo I just realized I could have used the set: $\{pn+1: n \in \omega\}$ for fixed prime $p$, which makes the problem a triviality.... Also, I realized, the false logic there too – Rustyn May 7 '14 at 3:12
• Yes. The problem was asked here a few years ago (of course), and that was the approach, but I like the additional analysis that you provided. – Andrés E. Caicedo May 7 '14 at 3:14
• I guess what I've proved is sort of interesting. Under this coloring, either there is a monochromatic set such that the sum of every two numbers of that set has an even number of prime factors or there is a monochromatic set such that each prime $p$ divides all but finitely many of its elements. – Rustyn May 7 '14 at 3:34

Ah we just use the set: $\{7n+1: n \in \omega\}$ to begin with.