2
$\begingroup$

For all $k>0$, we are to show that
there exists an even number $2n > 0$ that can be written as sum of two primes in at least $k$ ways.
($8=3+5=5+3$ counts as one way)

I tried to use pigeonhole principle to "fill" odd numbers in the lower half of $2n$ with primes, i.e. to show $\pi(2n)-[\frac{n}{2}]$ can be arbitrarily large, but it turns out to diverge to negative infinity instead.
Of course, requiring the entire half to be primes is an overkill, but I don't know how to rephrase the problem into a manageable form.
It probably has something to do with Prime Number Theorem, but I am not sure.

Thank you for any help.

$\endgroup$
  • $\begingroup$ The Green-Tao theorem states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. Consequently, for any integer $k>0$ there is an arithmetic sequence of odd prime numbers at least $2k$ in length. The sums of the first and last, the second and next to last, etc., will all be the same, and will be an even number. Thus there will be $k$ ways to express that sum. $\endgroup$ – Keith Backman Nov 25 '20 at 16:16
  • $\begingroup$ @KeithBackman While that’s true and correct, it is a bit like swatting a fly with a high-powered laser. The pigeonhole argument goes through with substantially less input than Green-Tao, and in fact doesn’t even require PNT. It should be enough to use the divergence of the series of prime reciprocals, which dates back to Euler. $\endgroup$ – Erick Wong Nov 26 '20 at 5:04
5
$\begingroup$

You're on the right track with the pigeonhole principle, but your counting is wrong; you want to get a 'quadratic-like' term to show unboundedness. Try this approach instead: consider how many unordered pairs of primes $\leq n$ there are; call this $f(n)$. Now, note that there are only $n$ even numbers less than $2n$. If each of these could be written as the sum of primes in $\leq C$ different ways for some constant $C$, what would that say about $f(n)$? Can you find a contradiction from here?

$\endgroup$
0
$\begingroup$

There are $\pi(n)-1 \approx \pi(n)$ odd primes less than $n$. Summing them two at a time, we obtain $\frac{(\pi(n))!}{(\pi(n)-2)!2!}=\frac{(\pi(n))\cdot (\pi(n)-1)}{2}$ even sums, all of which are smaller than $2n$. In addition, there are $\pi(n)$ occurrences of sums of the form $p_i+p_i$ not generated by the pairwise summing, and including those with the previous result, we obtain $\frac{(\pi(n))(\pi(n)+1)}{2}\approx \frac{(\pi(n))^2}{2}$ even sums to consider. There are $n$ even numbers smaller than $2n$

If for a chosen $n$ and any $k$, the number of sums exceeds $kn$, then by the pigeon hole principle, at least one even number $\le 2n$ is expressible as a sum of two odd prime numbers in at least $k$ different ways. This occurs with certainty when $\frac{(\pi(n))^2}{2}>kn$ or $(\pi(n))^2>2kn$

According to PNT, $\pi(n) \approx \frac{n}{\ln(n)}$. Substituting, the necessary condition becomes $\frac{n}{\ln^2(n)}>2k$

Since $\frac{n}{\ln^2(n)}$ grows without bound, it is always possible to choose an $n$ large enough to ensure that some even number smaller than $2n$ can be expressed as the sum of two odd primes in at least $k$ different ways.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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