Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
IIRC Hardy and Wright says a lot about average values of arithmetic functions such as as phi. (there's a chapter or two on it). –  Kevin Buzzard Nov 28 '09 at 11:59

2 Answers 2

I've just realized I was being a little bit slow. I had already found on the internet that $n^{-2}\sum_{k=1}^nφ(k)$ is roughly $3/π^2$ and stupidly didn't notice that I could "differentiate" this to get exactly what I want. That is, $\sum_1^N φ(k)$ is about $3N^2/π^2$, so the difference between the sum to $N+M$ and the sum to $N$ is around $6NM/π^2$, from which it follows that the average value near $N$ is around $6N/π^2$, which is entirely consistent with the well-known fact that the probability that two random integers are coprime is $6/π^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 ζ(2), or 1^{-2}+2^{-2}+... = π^2/6. It's not that hard to turn these formal arguments into a rigorous proof, since everything converges nicely.

share|improve this answer
4  
It isn't difficult to argue $6N/\pi^2$ directly either. You should accept your own answer! You get a badge for that. –  Greg Kuperberg Nov 28 '09 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).

share|improve this answer
    
+ 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... –  mrm Nov 29 '09 at 17:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.