Limit to Infinity of Summation of Euler Phi Function over Square
Theorem
- $\displaystyle \lim_{n \mathop \to \infty} \dfrac {\map \Phi n} {n^2} = \dfrac 3 {\pi^2}$
where:
- $\map \Phi n = \displaystyle \sum_{k \mathop = 1}^n \map \phi k$
- $\map \phi k$ is the Euler $\phi$ function of $k$.
Numerically, this evaluates to:
- $\dfrac 3 {\pi^2} \approx 0 \cdotp 30396 35509 \ldots$
This sequence is A104141 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).
Proof
We find the probability that the two random numbers not less than $n$ is coprime.
We pick randomly $x, y \in \set {1, \dots, n}$.
There are $n^2$ ways to do this.
There are three cases:
If $x > y$, for each $x$, there are $\map \phi x$ values of $y$ so that $x \perp y$.
Since $1 \le x \le n$, there are a total of $\map \phi 1 + \dots + \map \phi n = \map \Phi n$ valid values of $y$.
If $x < y$, the result is similar: there are $\map \Phi n$ valid values of $x$.
If $x = y$, $x \perp y$ only if $x = y = 1$.
Therefore the probability that the two random numbers not less than $n$ is coprime is:
- $\dfrac {\map \Phi n + \map \Phi n + 1} {n^2}$
Taking limit to infinity and using Probability of Two Random Integers having no Common Divisor:
| \(\ds \frac 6 {\pi^2}\) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \frac {\map \Phi n + \map \Phi n + 1} {n^2}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \frac {2 \map \Phi n} {n^2} + \lim_{n \mathop \to \infty} \frac 1 {n^2}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \frac {2 \map \Phi n} {n^2}\) | Basic Null Sequences | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \lim_{n \mathop \to \infty} \frac {\map \Phi n} {n^2}\) | \(=\) | \(\ds \frac 3 {\pi^2}\) |
$\blacksquare$
Add an analytic number theoretic proof using Möbius Inversion Formula, or otherwise
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
To discuss it in more detail, feel free to use the talk page.
If you are able to do this, then when you have done so you can remove this instance of {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Historical Note
This result was cited by Leonard Eugene Dickson in his History of the Theory of Numbers, Volume I of $1919$.
He attributed it to J. Perrot about whom nothing can be found.
Sources
- 1881: J. Perrot: Sur la sommation des nombres $\phi$ (Bull. des Sc. Math. et Astr. Ser. I Vol. 5, no. 2: pp. 37 – 40)
- 1919: Leonard Eugene Dickson: History of the Theory of Numbers: Volume $\text { I }$: Chapter $\text V$. Euler's $\phi$-Function, Generalizations, Farey Series
- 1983: François Le Lionnais and Jean Brette: Les Nombres Remarquables ... (previous) ... (next): $0,30396 35509 \ldots$