Question

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$?

---

Answer 1

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$

$=\sum_{d<X}\mu(d)(\frac{1}{2}X^2/d^2+O(X/d))=\frac{1}{2}X^2\sum_{d<X}d^{-2}\mu(d)+O(X\log{X})$

$=\frac{1}{2\zeta(2)}X^2+O(X\log{X})$.

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?)

Answer 2

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,

Answer 3

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).

Answer 4

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"