Can anyone tell me what the expected value of Euler's totient function φ$(n)$ is (roughly) if you choose a random integer $n$ in the range $[N,N+M]$, where $M$ is large and $N$ is larger than $M$? (I think of $M$ as being $cN$ for some small constant $c$, which, if one wanted an answer accurate to $1+o(1)$, would in reality be a slowly decreasing function of $N$.)
2 Answers
I've just realized I was being a little bit slow. I had already found on the internet that $n^{-2}\sum\limits_{k=1}^n\phi(k)$ is roughly $3/\pi^2$ and stupidly didn't notice that I could "differentiate" this to get exactly what I want. That is, $\sum\limits_{k=1}^N \phi(k)$ is about $3N^2/\pi^2$, so the difference between the sum to $N+M$ and the sum to $N$ is around $6NM/\pi^2$, from which it follows that the average value near $N$ is around $6N/\pi^2$, which is entirely consistent with the well-known fact that the probability that two random integers are coprime is $6/\pi^2$.
I'm adding this paragraph after Greg's comment. To argue that the probability that two random integers are coprime, you observe that the probability that they do not have $p$ as a common factor is $(1-1/p^2)$. If you take the product of that over all $p$ then you've got the reciprocal of the Euler product formula for $\zeta(2)$, or $1^{-2}+2^{-2}+\ldots= \pi^2/6$. It's not that hard to turn these formal arguments into a rigorous proof, since everything converges nicely.
-
7$\begingroup$ It isn't difficult to argue $6N/\pi^2$ directly either. You should accept your own answer! You get a badge for that. $\endgroup$ Nov 28, 2009 at 16:15
Let me also mention the following: You can adapt Schoenberg's result to prove that 1/M * {N <= n <= N + M : phi(n) / n <= t} --> F(t) uniformly in t, where F is a distribution function. The proof goes by computing the moments sum((phi(n)/n)^k , N <= n <= N + M). You can probably get a O(loglog N / log N) rate of convergence (as was done by Levin ... if I recall correctly).
-
1$\begingroup$ + If this is of interest the distribution function F(t) decays doubly exponentially at 0, that is F(1/t) << exp(-C*exp(t)) for some constant C. This was investigated by Erdos and more recently Weingartner (mrlonline.org/proc/2007-135-09/S0002-9939-07-08771-0/…). Asymptotics for 1 - F(t) when t is close to 1 where studied by Tenenbaum and Toulmonde (a reference is in the paper above). In this case the asymptotic behaviour is more tame. There should be no problem adapting all these results to the case of the interval [N; N + M] with M as you described... $\endgroup$– mrmNov 29, 2009 at 17:59