6
$\begingroup$

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?

  • 0
    @JoelCohen: you are correct that $\phi(n)/n$ does not tend to a limit, but your argument is incomplete - you need to note that $f$ is not a constant sequence.2012-02-25

2 Answers 2

8

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

  • 0
    @AndréN$i$colas: "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: http://enaslund.wordpress.com/2012/01/15/the-sum-of-the-totient-function-and-montgomerys-lower-bound/2012-02-25
4

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.