MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathcal{P}$ denote the set of primes. Define the function $r_2(N)$ to be the number of ways to write $N$ as a sum of two not necessarily distinct primes (where order matters). Then the famous Goldbach Conjecture can be phrased as following:

$r_2(2N) > 0$ for all $N \geq 1$.

A related function, $r_3(N)$ which is the number of ways $N$ can be written as the sum of three not necessarily distinct primes (order matters), is used in the following classic result by I.M. Vinogradov:

Vinogradov's Theorem: Define $\mathfrak{S}(N) = \displaystyle \sum_{q=1}^\infty \frac{\mu(q)c_q(N)}{\varphi(q)^3}$ where $\mu$ is the Mobius function, $c_q$ is the Ramanujun sum, and $\varphi$ the Euler totient function. Then for odd $N$, we have:

$r_3(N) = \displaystyle \mathfrak{S}(N) \frac{N^2}{2(\log(N))^3}\left(1 + O\left(\frac{\log \log(N)}{\log(N)}\right)\right)$.

This clearly shows that $r_3(N) > 0$ for all sufficiently large odd $N$, which is to say that all sufficiently large positive odd integers $N$ can be written as the sum of three primes. Goldbach's Conjecture would be proved if we can find some arithmetic function $f(N)$ which tends to infinity such that $r_2(N) >> f(N)$.

It has been confirmed that the Goldbach Conjecture holds for the first $10^{18}$ even integers (according to Wikipedia) by exhaustive computer search. But my question is, is there anything known about $r_2(N)$ for these cases? In particular I am asking whether or not there are any examples where $r_2(N)$ is unexpectedly small. If this happens infinitely often, for instance, then attempting to prove Goldbach's Conjecture by finding a lower bound that tends to infinity would be infeasible.

Another formulation would be, is there any heuristic evidence to suggest that there exist a positive integer $M$ such that for infinitely positive integers $N$ we have $r_2(N) \leq M$?

share|cite|improve this question
up vote 5 down vote accepted

I think the heuristic evidence suggests quite the opposite, that $r_2(N)$ increases without bound. See for both theoretical background and computational results.

share|cite|improve this answer
That's what I suspect as well, but was wondering if there were some 'small number singularities' where $r_2(N)$ is unexpectedly small. – Stanley Yao Xiao Jan 19 '11 at 6:48

You should look at Andrew Granville's survey . Among other things he talks about the behavior of $r_2(N)$ (or a suitably weighted version of it -- giving the representation $p+q=N$ the weight $\log p \log q$) on the average: if one looks at the average error between that and the conjectured Hardy-Littlewood "main term" one can show that this is small on the RH. This would indicate that finding large deviations from the main term would be quite hard.

share|cite|improve this answer

Considering the density of primes in combination with Brunn's sieve (which shows that the number of weighted solutions to $p+q=n$ can't be more than a constant times the expected value) should show that $r_{2}(n) \leq M$ can't hold for all (or even almost most) primes. In fact more is known, Montgomery and Vaughan (The exceptional set in Goldbach's problem. Collection of articles in memory of Juriĭ Vladimirovič Linnik. Acta Arith. 27 (1975), 353–370.) have shown that the number of exceptional values in $[0,N]$ where $r_{2}(n)=0$ is much smaller, at most $N^{1-\delta}$ for $\delta >0$. This probably can be modified to give a similar bound on the frequency of $r_{2}(n) \ll M$ holding. Of course, it is strongly believed that this can't happen.

share|cite|improve this answer

For an idea of the growth of the function in the worst case, see Sloane's A135733.

share|cite|improve this answer

Your Answer


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.