Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $s(n)$ denote the sum of primes less than or equal to n. Clearly, $s(n)$ is bounded from above by the sum of the first $n/2$ odd integers $+1$. $s(n)$ is also bounded by the sum of the first $n$ primes, which is asymptotically equivalent to $\frac{n^2}{2\log{n}}$. It should thus be possible to find estimates for $s(n)$ using the fact that for an $\epsilon > 0$ and $n$ large enough $s(n) < (1+\epsilon)\frac{n^2}{\log{n}}.$

I would like to know if there are any known sharp upper bounds for $s(n)$. That is, I am looking for a function $f(n)$ such that for every $n > N_0$ $$ s(n) \leq f(n)$$

As a way of relaxing the question, $s(n)$ could be regarded as the sum of the primes in the interval $[c,n]$ given a constant $c$.

share|improve this question
2  
I would have thought the sum of the first $n$ primes was asymptotically equivalent to $(n^2 \log n)/2$. (The $n$th prime is near $n \log n$, so the sum of the integers up to the $n$th prime is near $(n \log n)^2/2$, but only a proportion $1/\log n$ of the summands are prime. –  Michael Lugo Apr 29 '11 at 14:28
    
Did you try already to use Weil's explicit formula. Appropiated choosen tex functions, e.g. $e^{x tanh(x)} e^{-x^2 \delta}$ should give you an upper bound. –  plusepsilon.de Apr 29 '11 at 14:33
add comment

5 Answers

up vote 16 down vote accepted

By partial summation $$ s(n) = n\pi(n)-\sum_{m=2}^{n-1}\pi(m) $$ so by the Prime Number Theorem $$ s(n) = \frac{n^2}{\log n}-\sum_{m=2}^{n-1}\frac{m}{\log m}+O\left(\frac{n^2}{\log^2 n}\right). $$ The sum on the right is $$ \sum_{m=2}^{n-1}\frac{m}{\log m} = \int_2^n \frac{x}{\log x}dx + O\left(\frac{n}{\log n}\right) $$ using the monotonicity properties of the integrand. Now the integral equals, by partial integration, $$ \int_2^n \frac{x}{\log x}dx = \left[\frac{x^2}{2\log x}\right]_2^n + \int_2^n \frac{x}{2\log^2 x}dx = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$ Altogether we have $$ s(n) = \frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$ This can be made more precise both numerically and theoretically.

share|improve this answer
add comment

It is not difficult to calculate upper bounds on $s(n)$ from bounds on the prime counting function $\pi(n)$. Just use integration by parts, $$ s(n) = \int\_0^n x\\,d\pi(x) = n\pi(n) - \int\_0^n\pi(x)\\,dx. $$ I'm not sure what the currently best known bounds for $\pi(x)$ are but, checking Wikipedia, gives $$ \frac{x}{\log x}\left(1+\frac{1}{\log x}\right) < \pi(x) < \frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.51}{(\log x)^2}\right) $$ with the left hand inequality holding for $x\ge599$ and the right hand holding for $x\ge355991$. So,

$$ s(n)\le \frac{n^2}{\log n}\left(1+\frac{1}{\log n}+\frac{2.51}{(\log n)^2}\right)-\int^n\left(1+\frac{1}{\log x}\right)\frac{x\\,dx}{\log x}+c $$ (where $c$ is a constant which you can compute if you feel so inclined). Applying integration by parts,

$$ s(n)\le\frac{n^2}{2\log n}\left(1+\frac{1}{\log n}+\frac{5.02}{(\log n)^2}\right)-\frac12\int^n\left(1+\frac{2}{\log x}\right)\frac{x\\,dx}{(\log x)^2}+c $$

Bounding $\log x\le\log n$ in the integral gives a bound

$$ s(n)\le\frac{n^2}{2\log n}\left(1+\frac{1}{2\log n}+\frac{4.02}{(\log n)^2}\right)+c $$

You can also take $c=0$ if you only require the bound to hold for $n\ge N$ (some $N$), since the term I neglected in the integral by applying $\log x\le \log n$ grows withuot bound, and will eventually dominate any constant term. Obviously, if you know any better bounds for $\pi(n)$ then you will get improved bounds for $s(n)$. For example, the same Wikipedia article linked to above states that $\left\vert\pi(x)-{\rm Li}(x)\right\vert\le\frac{\sqrt{x}\log x}{8\pi}$ for $x\ge2657$ under the assumption that the Riemann hypothesis holds.

share|improve this answer
    
+1 nice answer! –  plusepsilon.de Apr 29 '11 at 15:22
add comment

There definitely are earlier references than our book. An asymptotic formula for

$\sum_{p \leq x} p^a$

is in T. Salát and S. Znám, On the sums of the prime powers, Acta Fac. Rer. Nat. Univ. Com. Math. 21 (1968), pp. 21-24. (Cited by Spearman & Williams--I actually have not seen this paper.) It probably goes back further than that. The natural place to look would be Landau's "Primzahlen"--I forget the exact title--but I was unable to find that sum in there.

Eric.

share|improve this answer
    
Welcome to MathOVerflow, Eric! –  Charles May 20 '11 at 4:04
add comment

The following paper gives the asymptotic expansion of the sum of the first $n$ prime numbers. Hence for sufficiently large $n$, the first few positive and negative terms of the asymptotic expansion will give best upper and lower bound on the sum of primes.

http://arxiv.org/pdf/1011.1667.pdf

$$ \sum_{r \le n}p_r = \frac{n^2}{2}\Bigg[\ln n + \ln\ln n - \frac{3}{2} + \frac{\ln\ln n}{\ln n} - \frac{3}{\ln n}- \frac{\ln^2 \ln n}{2\ln^2 n} $$

$$ + \frac{7 \ln \ln n}{2\ln^2 n} - \frac{27}{4\ln^2 n} + o\Bigg(\frac{1}{\ln^2 n}\Bigg) \Bigg]. $$

share|improve this answer
add comment

Until a better answer appears. Here is a link:

http://mathworld.wolfram.com/PrimeSums.html

It says that

$$s(p_n) \tilde \quad n^2 \log n /2.$$

where $p_n$ is the $n$-th prime.

Perhaps you want to look at the reference, and figure out if you can make the bound effective.

share|improve this answer
    
So Michael Lugo's heuristic actually can be made effective... –  plusepsilon.de Apr 29 '11 at 15:08
1  
Not exactly: there is a difference between the sum of primes less than or equal to $n$, and the sum of the $n$ first primes. I must have missed something: how could $s(n) \sim n^2 \ln(n)/2$ have not be proven before 1996 by Bach and Shallit? I do not see what is wrong with the fact that, since, $p_n \sim n \ln(n)$ (prime number theorem), one has: $\sum_{k=1}^n p_k \sim \sum_{k=1}^n k \ln(k) \sim \int_1^n t\ln(t) \mathrm{d}t \sim n^2\ln(n)/2$ –  Bernikov Apr 29 '11 at 15:11
    
Sorry, I have missed that difference. I did not read carefully. –  plusepsilon.de Apr 29 '11 at 15:18
    
Fixed the mistake... –  plusepsilon.de Apr 29 '11 at 15:25
add comment

Your Answer

 
discard

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.