# 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}$. Commented Feb 25, 2012 at 3:20
• I think the question is supposed to be about $\sum_{i=1}^n\phi(i)$. Commented Feb 25, 2012 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? Commented Feb 25, 2012 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)$). Commented Feb 25, 2012 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. :/ Commented Feb 25, 2012 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)$? Commented Feb 25, 2012 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. Commented Feb 25, 2012 at 4:58
• The typo is fixed in the sixth edition, which defines $\Phi(n)$ to be $\sum_{i=1}^n \phi(i)$. Commented Feb 25, 2012 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/… Commented Feb 25, 2012 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.

i found an interesting connection between the following probability problem and your question:

Question: If 2 integers are randomly chosen between 1 and n, then as n tends to infinity, find the probability that the chosen numbers are coprime.

Now the probability that 2 numbers are not divisible by a prime p is $$(1-1/p^2)$$. So we require the infinite product:

$$\prod_{p}{(1-\frac{1}{p^2})}$$

And this can be easily seen to be $$\frac{1}{\zeta(2)}= \frac{6}{\pi^2}$$ which is the answer, where $$\zeta(z)$$is the Reimann zeta function.

Thinking in terms of definition, probability is ratio of favourable outcomes and total outcomes. Now, number of possible pairs of numbers is $$n²$$.

What is the number of coprime pairs $$(x,y)$$,$$1≤x≤y≤n$$, x,y being integers? Setting $$y=k$$, the possible pairs is $$\phi(k)$$, because $$\phi(k)$$is the number of integers less than k and prime to k.

$$\lim_{n\to \infty} \frac{2(\phi(1)+\phi(2)+...\phi(n))}{n^2}$$
(2 introduced so that if $$(x,y)$$are coprime, then and$$(y,x)$$ is also coprime.)
So your answer must be $$\lim_{n\to \infty} \frac{(\phi(1)+\phi(2)+...\phi(n))}{n^2} =\frac{1}{2\zeta(2)}= \frac{3}{\pi^2}$$