# Finding $\lim_{n\to\infty}\Phi(n)/n^2$, When $\Phi(n)=\sum_{i=1}^{n}\phi(n)$

This exercise is meant to be 'explored' computationally. However, I implemented it in C++ and did not get anything better than a sequence of pseudo-random numbers.

Let $\Phi(n)=\sum_{i=1}^{n}\phi(n)$. Investigate the value of $\Phi(n)/n^2$ for increasingly large values of $n$, such as $n=100$, $n=1000$, and $n=10000$. Can you make a conjecture about the limit of this ratio as $n$ grows large without bound?

Notice that $\Phi(n)=n\phi(n)$. Hence, $\Phi(n)/n^2=\phi(n)/n$. Moreover, the largest value $\phi(n)/n$ ever attains is $1$ at $n=1$; everything else falls within the interval $(0,1)$, and the closest it gets to $1$ again is when $n$ is prime (since $\phi(p)=p-1$, and $(p-1)/p\approx1$ for very large primes $p$).

However, I am tempted to say that this function diverges, and that no conjecture about its limit can be concluded as a result.

What do you guys think?

-
Since $\phi(n)$ is asymptotically $n$, I'm tempted to say $\Phi(n)/n^2$ approaches $1/2$, as $\sum\limits_{i=1}^ni=\frac{i^2+i}{2}$. – Alex Becker Feb 25 '12 at 3:20
I think the question is supposed to be about $\sum_{i=1}^n\phi(i)$. – Gerry Myerson Feb 25 '12 at 3:22
Gerry, I thought the same. However, I copied the book's question character by character (Elementary Number Theory and Its Applications 5E. by Kenneth H. Rosen, page 237). Could he have made a typo? – EsX_Raptor Feb 25 '12 at 3:27
I think the function $f(n) = \phi(n)/n$ has no limit, because for any value taken by $f$, say $f(n_0)$, then $(n_0^k)_{k>0}$ defines a subsequence that converges to this value (using the fact that $f(n_0^k) = f(n_0)$). – Joel Cohen Feb 25 '12 at 3:36
Hey guys, look at what I found. en.wikipedia.org/wiki/… Is that corroborating that the limit indeed does not exist? The mathematics are too convoluted for me to understand at this point. :/ – EsX_Raptor Feb 25 '12 at 3:46

There is a very old result that says $$\lim_{n\to\infty}\frac{\sum_{k=1}^n \varphi(k)}{n^2}=\frac{3}{\pi^2}.$$

The error term I have in notes is $O(x(\log x)^{2/3}(\log\log x)^{4/3})$, but undoubtedly there have been improvements on that. There is a large literature.

Added: The OP quoted correctly the textbook source of the problem, which asks about the behaviour of $(\sum_{i=1}^n\varphi(n))/n^2$. This is undoubtedly a typo, since $\sum_{i=1}^n\varphi(n)=n\varphi(n)$.

The ratio $\dfrac{\varphi(n)}{n}$ certainly bounces around a lot, and can be made arbitrarily close to $0$, and, much more easily, arbitrarily close to $1$.

-
Is that considering $\Phi(n)=\sum_{i=1}^{n}\phi(n)$ or $\Phi(n)=\sum_{i=1}^{n}\phi(i)$? – EsX_Raptor Feb 25 '12 at 4:50
What you wrote, both in the post and in the comment, cannot be right, since you are writing $\sum_{i=1}^n \varphi(n)$. I assumed that you mean $\sum_{i=1}^n\varphi(i)$. If we are summing over the divisors of $n$, that is an entirely different function, easy to get explicit formulas for, but somewhat chaotic. – André Nicolas Feb 25 '12 at 4:58
The typo is fixed in the sixth edition, which defines $\Phi(n)$ to be $\sum_{i=1}^n \phi(i)$. – David Moews Feb 25 '12 at 5:51
@AndréNicolas: "Undoubtedly there have been improvements on that." Surprisingly, there haven't been any. That result is due to Walfisz, and it remains the best. See this blog post for details: enaslund.wordpress.com/2012/01/15/… – Eric Naslund Feb 25 '12 at 13:44

Here is a detailed note regarding the Totient Summatory function. Part 1 and 2 should be of interest, and in part 2 there is a short proof.

Also see this Math Stack Exchange question and answer.

-