Prove that for each positive integer $K$ there exist infinitely many even positive integers which can be written in more than $K$ ways as the sum of two odd primes.
Problem
Source:
Tags: pigeonhole principle, inequalities, Additive Number Theory
17.09.2007 20:55
We will prove the following stronger statement (implying the above with $ S=\{2\}$, and we don't even need the distinctness of the primes): Let $ \mathbb P$ be the set of primes and let $ S\subset\mathbb P$ be finite. Then for any $ K$, we find $ \infty$ integers expressible as sum of two distinct primes in $ \mathbb P\backslash S$ in more than $ K$ ways. Proof: Call $ \pi(n)$ the number of primes $ \leq n$. Lets see that we find at least one such integer $ x$ for any $ K$: Take some integer $ n$. There are $ m: =\binom{\pi(n)-|S|}2$ different pairs $ (a,b)$ of primes $ a < b\leq n$ not in $ S$, their sum $ a+b$ trivially being $ <2n$. If $ m > (K-1)\cdot 2n$, $ K$ of these sums are the same by Pidgeonhole-Principle, thus such $ x$ exists. Thus lets prove that inequality for some large $ n$: By Chebyshev, there is a $ c>0$ such that $ \pi(n) > c\cdot\frac {n}{\log(n)}$. As we also have $ m=\binom{\pi(n)-|S|}2\geq\frac{1}{2}(\pi(n)-|S|-1)^{2}\geq\frac{1}{2}\left( c\cdot\frac {n}{\log(n)}-|S|-1\right)^{2}$, we just want that $ \frac{1}{2}\left( c\cdot\frac {n}{\log(n)}-|S|-1\right)^{2}> (K-1)\cdot 2n$, clearly happening for some $ n$ (the LHS grows like $ c^{2}\cdot\frac{n^{2}}{\log(n)^{2}}$, the RHS only linear in $ n$). Now that we found one $ x_{K}$ expressible as sum of two different primes from $ T: =\mathbb{P}\backslash S$ in $ K$ different ways for any $ K$, we even get infinitely many of them: If $ x_{K}$ can be expressed in exactly $ L\geq K$ different ways as sum of two different primes in $ T$, we simply take $ K^{\prime}= L+1$, then $ x_{K^{\prime}}\neq x_{K}$ but still fulfills our requirements. Continuing this, we get infinitely many $ x$ with the desired property. Note: in the proof above, we used Chebyshevs theorem. But it's easy to see that the following suffices (being slightly easier): $ \frac{\pi(n)}{\sqrt n}$ is unbounded.