5
$\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
    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}$.2012-02-25
  • 4
    I think the question is supposed to be about $\sum_{i=1}^n\phi(i)$.2012-02-25
  • 0
    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?2012-02-25
  • 0
    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)$).2012-02-25
  • 0
    Hey guys, look at what I found. http://en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_of_the_function Is that corroborating that the limit indeed does not exist? The mathematics are too convoluted for me to understand at this point. :/2012-02-25
  • 0
    Where do you get $\Phi(n) = n \phi(n)$ from ?2012-02-25
  • 0
    $\Phi(n)=\sum_{i=1}^{n}\phi(n)=\phi(n)+\phi(n)+\cdots+\phi(n)=n\phi(n)$.2012-02-25
  • 0
    From the fact that $\phi(1)+\cdots+\phi(n)=3n^2/\pi^2+O(n\log n)$, assuming the author meant $\phi(i)$ we have that the limits is $3/\pi^2$. Note: this is near the bottom of the wikipedia page.2012-02-25
  • 0
    @Josue Molina: I checked my copy of the Rosen book, fifth edition. Undoubtedly there is a typo in the book.2012-02-25
  • 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

7

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
    Is that considering $\Phi(n)=\sum_{i=1}^{n}\phi(n)$ or $\Phi(n)=\sum_{i=1}^{n}\phi(i)$?2012-02-25
  • 0
    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.2012-02-25
  • 1
    The typo is fixed in the sixth edition, which defines $\Phi(n)$ to be $\sum_{i=1}^n \phi(i)$.2012-02-25
  • 0
    @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: http://enaslund.wordpress.com/2012/01/15/the-sum-of-the-totient-function-and-montgomerys-lower-bound/2012-02-25
3

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.