Take the 2-minute tour ×

Let $S_x$ be the set of finite sums of prime numbers $\geq x$. In other words, let $S_x$ be the submonoid of $(\mathbf{Z}_{\geq 0},+)$ generated by the set $\mathcal{P}_{\geq x}$ of prime numbers $\geq x$.

It is easy to see that $S_x$ contains every sufficiently large integer. This follows from the classical fact that given two coprime integers $a$ and $b$, every sufficiently large integer, in fact every integer $\geq (a-1)(b-1)$, is of the form $ma+nb$ for some $m, n \in \mathbf{Z}_{\geq 0}$. See for example this page.

Let $N_x$ be the largest integer which is not in $S_x$.

Examples :

If $x=2$ then $S_2 = \{0\} \cup \mathbf{N}_{\geq 2}$ so that $N_2=1$.

If $x=3$ then $S_3 = \{0,3\} \cup \mathbf{N}_{\geq 5}$ so that $N_3=4$.

By definition, we have $N_x \geq x-1$ (in fact parity considerations imply that $N_x \geq 2x-2$ for $x \geq 3$).

On the other hand, given that there are at least two primes in the interval $[x,2x]$, the above classical fact implies that $N_x \ll x^2$.

What is the asymptotic behaviour of $N_x$ as $x \to \infty$ ?

share|improve this question
Interesting question! This is essentially Sloane's A180306, but it does not contain any information on the asymptotics. –  Charles Apr 3 '12 at 15:22
@Charles : Thanks for the reference to Sloane's database. @Mark : I don't really know. I suspect that the upper bound I gave is much too high, but I don't know what to expect since I'm not a specialist in additive number theory. –  François Brunault Apr 3 '12 at 16:10
Lemma 1 of Erdos's 1974 paper with Benkoski "On weird and pseudoperfect numbers" is: There is an absolute constant $c$ such that every integer $m > c p_k$ is the distinct sum of primes not less than $p_k$. (Here $p_k$ is the $k$th prime, in the usual order.) No proof is given. "The lemma is probably well known and, in any case, easily follows by Brun's method." –  Anonymous Apr 4 '12 at 2:08
@Anonymous : Thanks for the reference! It would be interesting to make $c$ explicit. –  François Brunault Apr 4 '12 at 8:53
In view of the answers below indicating the link with Goldbach's conjecture, which is out of reach, I would accept any answer showing that $N_x \ll x$. –  François Brunault Apr 4 '12 at 9:21

3 Answers 3

up vote 4 down vote accepted

According to "The three primes theorem with almost equal summands" by Baker and Harman, every large odd $N$ is a sum of three primes each of size $\sim N/3$. (In fact, within $N^{4/7}$ of $N/3$-- this is much closer than we need, so we could use weaker results of earlier authors, if preferred.)

For odd $N$, this gives $N$ as a sum of three primes, each at least $\sim N/3$. If $N$ is even, take a prime $p$ of size $\sim N/4$ (which exists by the prime number theorem), and write $N-p$ as a sum of three primes of size about $N/4$. So we get $N$ as a sum of four primes at least $\sim N/4$.

share|improve this answer
Thanks! This result indeed shows that $N_x/x$ is bounded (and in fact $\operatorname{limsup} N_x/x \leq 4$). –  François Brunault Apr 6 '12 at 9:17

(Edited according to the comments below)

In his article titled 'Sums of Distinct Primes', Kløve conjectured, on the basis of computational evidence, that $\displaystyle \lim_{x \rightarrow \infty} \dfrac{N_x}{x} = 3$. This would imply the binary Goldbach conjecture (for large enough $x$) in the following way: if every integer larger than $(3 + \epsilon)x$ can be written as sum of primes, where those primes are all larger than $x$, then, in particular, every even number between $(3 + \epsilon)x$ and $4x$ can be written as a sum of two primes.

share|improve this answer
@Woett: In that paper, the word "prime" does not appear. –  Mark Sapir Apr 3 '12 at 16:24
Hmm, maybe I understand the question wrong. Please read page 56 of the article of Erdos and Graham (page 52 of this pdf: math.ucsd.edu/~ronspubs/80_11_number_theory.pdf) –  Woett Apr 3 '12 at 16:30
@Woett: Yes, Kløve, Torleiv Sums of distinct primes. Nordisk Mat. Tidskr. 21 (1973), 138–140. According to Math Reviews he conjectured there that the limit is 3. The review does not mention Goldbach. The paper is not on-line, unfortunately. –  Mark Sapir Apr 3 '12 at 17:53
Does Vinogradov result that every sufficiently large odd number is a sum of three primes imply that the limit is at most 5 (or at least $< \infty$)? Vinogradov does not claim that his primes are all of approximately the same size, but perhaps his method can be adapted to produce such a result. –  Mark Sapir Apr 3 '12 at 18:18
@François: No, since not requiring the primes to be distinct can only make the limit lower, but the limit has to be at least 3 (there is an odd composite in $[3n-5,3n)$). –  Emil Jeřábek Apr 4 '12 at 10:18

Just to spell it out, If Golbach's conjecture is false, then at least once $N(x)>4x$, but that seems extremely unlikely. It is certain that $N(x)>3x$ infinitely often, but there is every reason to believe that $N(x)<(3+\epsilon)x$ with finitely many exceptions. If so, then we could equivalently define $N_x$ as the largest odd integer which is neither prime nor a sum of $3$ primes all at least $x$.

it will frequently happen that the next prime after $p$ is at least $p+8.$ In these cases we can write $3p$ as a sum of primes at least $x=p$ however at least one of the odd numbers $3p+2,3p+4,3p+6$ is not itself prime and hence not a sum of primes all greater than $x=p.$ This establishes that $N(x)>3x$ infinitely often.

There is no proof that every even integer is a sum of two primes. Were there a counter-example, $E$, it would need to be a sum of at least 4 primes and hence furnish an example of $N(x)>4x$ where $x$ is $\frac{E}{4}.$ However there is every reason to believe the stronger statement that for every $\epsilon \gt 0$ there is an $M(\epsilon)$ such that $2m$ is a sum of two primes, both larger than $m(1-\epsilon)$ for all $m \gt M(\epsilon).$ If so, then $N(x)<(3+\epsilon)x$ provided that $x$ is reasonably larger $\frac{M(\epsilon)}{1-\epsilon}.$

share|improve this answer
Using $x = k! + 1$, we can even show that $\limsup_{x \rightarrow \infty} N(x) - 3x = \infty$. In fact, using an estimate of Rankin on large prime gaps, we should get $N(x) - 3x > c\log x \log \log x \log \log \log \log x (\log \log \log x)^{-2}$ infinitely often. –  Woett Apr 4 '12 at 4:15
However, does not rule out the possibility that for every $\epsilon \gt 0$ we have $\limsup_{x \to \infty}N(x)-(3+\epsilon)x=-\infty$ –  Aaron Meyerowitz Apr 4 '12 at 4:33
Oh, of course not! Perhaps even $N(x) < 3x + x^{\epsilon}$ for large $x$. But this should be really far from what can be proven with current methods :) –  Woett Apr 4 '12 at 4:41
True. With current methods we can not prove Golbach's conjecture so we do not know that $N(x) \lt 4x$ is true, although we believe it is. Were I foolish I would predict $(3+c_1/\ln{x})x \lt N(x) \lt (3+c_2/\ln{x})x.$ –  Aaron Meyerowitz Apr 4 '12 at 5:08
Thanks Aaron for your answer. I believe your argument shows that for any odd $x$ which is not prime, we have $N(x) \geq 3x$, since $3x$ cannot be written as a sum of primes $\geq x$. –  François Brunault Apr 4 '12 at 9:18

Your Answer


