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?

$\endgroup$
10
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented Feb 25, 2012 at 3:20
  • 5
    $\begingroup$ I think the question is supposed to be about $\sum_{i=1}^n\phi(i)$. $\endgroup$ Commented Feb 25, 2012 at 3:22
  • 1
    $\begingroup$ 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? $\endgroup$
    – wjmolina
    Commented Feb 25, 2012 at 3:27
  • 1
    $\begingroup$ 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)$). $\endgroup$
    – Joel Cohen
    Commented Feb 25, 2012 at 3:36
  • 1
    $\begingroup$ 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. :/ $\endgroup$
    – wjmolina
    Commented Feb 25, 2012 at 3:46

3 Answers 3

9
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Is that considering $\Phi(n)=\sum_{i=1}^{n}\phi(n)$ or $\Phi(n)=\sum_{i=1}^{n}\phi(i)$? $\endgroup$
    – wjmolina
    Commented Feb 25, 2012 at 4:50
  • $\begingroup$ 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. $\endgroup$ Commented Feb 25, 2012 at 4:58
  • 1
    $\begingroup$ The typo is fixed in the sixth edition, which defines $\Phi(n)$ to be $\sum_{i=1}^n \phi(i)$. $\endgroup$ Commented Feb 25, 2012 at 5:51
  • $\begingroup$ @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/… $\endgroup$ Commented Feb 25, 2012 at 13:44
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

So, required answer is just:

$$ \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 the twice the limit in your question is the probability that 2 chosen numbers in 1 to n is 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}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .