MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $\varphi(n)$ denote Euler's phi-function. If we let $$ \sum_{n\leq x} \varphi(n) = \frac{3}{\pi^2}x^2+R(x),$$ then it is not hard to show that $R(x)=O(x\log x)$. What is the best known bound for $R(x)$ assuming the Riemann Hypothesis?

share|cite|improve this question
Pardon me for the dumb question. I can see that bounds of this type on $\psi(n)$ may be useful for the prime number theorem. What are some uses of summing $\phi(n)$ like this? – Anweshi Jan 31 '10 at 0:12
Letting $\Phi$ denote the summatory function of $\phi$ and calculating the local average $(\Phi(x) - \Phi(x-h))/h = 6x/{\pi}^2 + O(h) + O(x\log(x)/h)$ by the asymptotic estimate, we see that $\phi$ has average order of growth $6x/{\pi}^2$. Choosing $h = \sqrt{x\log(x)}$ optimally, we obtain the estimate $6x/{\pi}^2 + O(\sqrt{x\log(x)})$ for the local average. The calculation of the average order of $\phi$ yields: (1) The chance that two large integers be coprime is $6/{\pi}^2$ and thus (2) The chance that a lattice point be visible from the origin is $6/{\pi}^2$. – engelbrekt Jan 31 '10 at 10:17
Also the asymptotic estimate for the summatory function shows that there are $3x^2/{\pi}^2 + O(x\log(x))$ distinct rational numbers in the interval $[0,1]$ having a representation as a fraction in lowest terms with denominator $\leq x$. – engelbrekt Jan 31 '10 at 10:21
up vote 8 down vote accepted

There is information on page 68 of Montgomery and Vaughan's book, and also on page 51 of "Introduction to analytic and probabilistic number theory" by Gérald Tenenbaum. Briefly, Montgomery has established that

$$ \limsup_{x \rightarrow +\infty}\frac{R(x)}{x\sqrt{\log\log(x)}} > 0 $$

and similarly with the limit inferior. So there is only modest room for improvement. Unfortunately I cannot find any reference to an upper bound conditional on RH. On page 40 Tenenbaum has a reference to page 144 of Walfisz' book on exponential sums. Walfisz uses Vinogradov's method to show that

$$ R(x) = O\left(x\log^{2/3}(x)(\log\log(x))^{4/3}\right). $$

I don't own a copy of Walfisz' book, so I have no further details.

share|cite|improve this answer
What is the constant factor? – Mayank Pandey May 12 '14 at 17:42

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.