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

What are the odds two numbers are relatively prime? This is known to be $\frac{6}{\pi^2}$. The proof involves calculating averages of the Euler phi function. \[ \phi(1) + \phi(2) + \dots + \phi(n) \approx 3 \left(\frac{n}{\pi}\right)^2 + O(n \log n) \] So even though $\phi$ is rather noisy, it's sum is relatively "quiet" behaving like a parabola. Why does all the noise disappear?

I'm wondering how it is possible to compute the exactly coefficient of $n^2$ in this expansion. It seems like a coincidence.

For good measure I have plotted the $\sum \phi$ and $\sum \phi - (\cdot)^2$ as demonstration.

Also we could consider a related function $\displaystyle \theta(n) = n^2 \prod_{p|n} \left( 1 - \frac{1}{p^2}\right)$. Here $\theta(1) + \theta(2) + \dots + \theta(n) \approx c \cdot n^3 + \dots$ what's the procedure for computing the constant $c$?
alt text

share|cite|improve this question
Regarding your last question: First, compute the mean value of $\theta(n)/n^2$. (Use the convolution method: Write $\theta(n)/n^2 = \sum_{d \mid n} g(d)$, sum both sides over $n \leq x$, interchange the order of the sums, etc.) The asymptotic for the partial sums of $theta(n)$ then follows by partial summation. – Anonymous Dec 30 '11 at 5:37
up vote 8 down vote accepted

Here is the standard, but very enlightening, elementary computation. Using $\phi(n)=n\sum_{d|n}\frac{\mu(d)}{d}=\sum_{md=n}m\mu(d)$, we manipulate finite sums:

$\sum_{n < X}\phi(n)= \sum_{dm<X}m\mu(d) =\sum_{d<X}\mu(d)\sum_{m<X/d}m$



A similar calculation gives $\sum_{n<X}\theta(n)=\frac{1}{3\zeta(3)}X^3+O(X^2)$. (Why is the error log-free?)

share|cite|improve this answer
Not an answer to your last question, but there is a considerable literature trying to remove the log from the $\phi$ asymptotics as well. – Igor Rivin Dec 30 '11 at 10:41
yes, I think the error for $\sum_{n < X} \phi(n)$ is $X$ times a noise term of order $1$. – john mangual Dec 30 '11 at 11:09
@Igor Rivin: Originally Chowla proved that one cannot altogether remove the $\log x$ term from the error term in the $\phi$ asymptotic. Perhaps replace it by $\log \log x$, but this is open. For a brief history see this answer on MSE:… To summarize, it is conjectured by Montgomery that the error term is both $O(x\log\log x)$ and $\Omega_{\pm} (x\log \log x)$. The best lower bound is $\Omega_{\pm}(x\sqrt{\log \log x})$ by Montgomery, and $O\left(x(\log x)^{2/3+\epsilon}\right)$ by Walfisz. – Eric Naslund Dec 31 '11 at 13:51

This exact question has actually been answered a few times on Math Stack Exchange.

See this for a general approach to finding the mean value of multiplicative functions which are "close" to $n$. Here is the idea:

Heuristic: Notice $f(n)\approx n$, then $\frac{f(n)}{n}\approx 1$. For functions close to one, convolution with the Möbius function will be close to zero, so we can deal with it easily. Lets define $g(n)=(\mu*\frac{f(d)}{d})(n)=\sum_{d|n}\frac{f(d)}{d}\mu\left(\frac{n}{d}\right)$ so that $(1*g)(n)=\frac{f(n)}{n}$. The idea will be to rewrite everything in terms of $g$ since $g(n)$ will be small.

The answer linked above provides the precise computation, and this will cover the Totient function, and the second example you gave above.

For the Totient function in particular, see this answer which also gives history of upper and lower bounds on the error term. In particular, the error term is surprisingly at least $\Omega (x\sqrt{\log \log x}).$

Hope that helps,

share|cite|improve this answer
Your second link is the same as the first... it meant to point to something historical? – john mangual Dec 30 '11 at 18:12
@John: Sorry about that, things got mixed up when I pasted the links. I have fixed it now. – Eric Naslund Dec 30 '11 at 19:12

A more analytic way to see this is through Dirichlet series, namely we know that (H&W as mentioned in the other answers is a good reference, but the identity can be seen by the Euler product) $$ \sum_{k=1}^\infty \phi(k) k^{-s}= \frac{\zeta(s-1)}{\zeta(s)}. $$ Perron's formula gives $$ \sum_{k=1}^n \phi(k) =\frac 1 {2 \pi i}\int_{c-\infty i}^{c+\infty i} \frac{\zeta(s-1)}{\zeta(s)} \frac{x^s} s ds, \qquad (n < x < n+1)$$ where $ c > 2$ is large enough for the Dirichlet series to be absolutely convergent. From moving $c>2$ to $ 1 < c < 2$ we pick up a residue at $s=2$ coming from the zeta-function's pole at Re$(s)=1$, from where the main term comes. This will be exactly $\frac {x^2} {2 \zeta(2)}=3 x^2/\pi^2$.

The remaining integral can be estimated as an error term (the strong form of the error term as mentioned above will be more difficult to obtain this way however).

The Dirichlet series argument why all the noise disappears (The error term is rather good) is simply that the Dirichlet series in the region $ 1 < $ Re $ (s)<2 $ does not behave too badly (i.e. has no poles, and does not grow too fast when Im$(s)\to \infty$). This method also works for other arithmetical functions (often with worse error terms), for example divisor problems. Cases more difficult to treat with the convolution method, where even more noise remains because the function has poles includes for example estimating sums of the Möbius function or the Von Mangoldt function (the RH gives much better estimates than known unconditional estimates in these cases).

share|cite|improve this answer

Let's say we want to figure out how many lattice points in a disk of radius $R$ are "visible" (have relatively prime coordinates). Call this function $f(R).$The basic point in proving the first statement is that if you look at lattice points in (say) a disk of radius $R$, that set has a stratification according to to the gcd of the coordinates, so you have a sum like $\pi R^2 = \sum_{d=1}^\infty f(R/d).$ If you assume that the probability exists, then we can write the above as: $\pi R^2 = f(R) \sum_{d=1}^\infty\frac{1}{d^2}= f(R) \zeta(2).$ While the computation is not rigorous, it gives the right constant, and the right intuition.

By the way, the fact that the limit exists is related to the fact that $SL(2, Z)$ acts ergodically on $\mathbb{R}^2.$ See

Densities in free groups and $\mathbb {Z}^ k $, Visible Points and Test Elements (I Kapovich, I Rivin, P Schupp, V. Shpilrain)

for group-theoretic applications.

I am quite sure that the $\theta$ computation can be given in the same way if you interpret the sum "geometrically"

share|cite|improve this answer
Probably "englightening" is in the eye of the beholder! I think my brain finds "algebraic" arguments much more enlightening than "geometric" ones; I was reading arguments of the sort David presented in Hardy and Wright when I was in my last year of high school [H&W was the unique undergraduate level mathematics textbook in my local library and is arguably the reason I became a number theorist] and found them very enlightening! – Kevin Buzzard Dec 30 '11 at 11:05
@Kevin: certainly, to each his own. By the way, I never thought of H&W as a textbook (more as a desk reference), but then I am not a number theorist :) – Igor Rivin Dec 30 '11 at 11:19
You call points "t-visible" if $(x,y)$ with $\mathrm{gcd}(x,y)=t$ and your Prop 1.7 and Theorem B give a dynamical systems proof, at least for these problems. The algebra is always handy to calculate with when you can't draw a picture. Somehow they give the same result. – john mangual Dec 30 '11 at 12:09
" The algebra is always handy to calculate with when you can't draw a picture." So in other words, most of the time. :) – David Hansen Dec 30 '11 at 17:25

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.