6
$\begingroup$

This is more a casual/recreational question...

It seems to me, that the limit as given in the subject line $$\lim_{n \to \infty} {\log \left( \sum_{k=2}^n \varphi(k) \right) \over \log(n)} = \log_n \left( \sum_{k=2}^n \varphi(k) \right) \le 2 $$

Possibly this is somehow trivial. And does it approach 2 in the limit?

$\endgroup$
5
  • 1
    $\begingroup$ Hint: $\sum_{k=1}^n \varphi(k) \leq \sum_{k=1}^n k \leq \sum_{k=1}^n n = n^2$ $\endgroup$ Jul 18, 2013 at 18:36
  • $\begingroup$ @Peter: ...arrrggh...I'm stupid! True; that's correct. I'd thought already myself about your left inequality, but didn't arrive at the second. But is there a certain limit for that formula? Or a better expression? $\endgroup$ Jul 18, 2013 at 18:39
  • $\begingroup$ Strictly speaking, the second inequality is unnecessary; the sum can be evaluated explicitly as $n(n+1)/2$; which behaves just like $n^2$ when taking logarithms. $\endgroup$ Jul 18, 2013 at 18:44
  • $\begingroup$ @Peter: well, what I'm just thinking about was whether there is some modification of the Euler-product to arrive at the limit as n goes to infinity. But I'm not sure about this... $\endgroup$ Jul 18, 2013 at 18:50
  • 1
    $\begingroup$ possible duplicate of Asymptotic formula for $\mu(n)[x/n]^2$ summation $\endgroup$ Jul 18, 2013 at 19:09

2 Answers 2

7
$\begingroup$

Thm: We have $$ \sum_{n < x} \varphi(n) \sim \frac{3}{\pi^2} x^2 $$ Proof: Since $$ n = \sum_{d | n} \varphi(d) $$ by Moebius inversion we get $$ \varphi(n) = n \sum_{d | n} \frac{\mu(d)}{d} $$ Therefore $$ \sum_{n < x} \varphi(n) = \sum_{n < x} n \sum_{d | n} \frac{\mu(d)}{d} $$ Interchanging summation we get $$ \sum_{d < x} \frac{\mu(d)}{d} \sum_{d | n, n < x} n $$ The inner sum equals $$ d \cdot \frac{x^2}{2 d^2} + O(x) = \frac{x^2}{2d} + O(x) $$ Therefore the final answer is $$ \sum_{d < x} \frac{\mu(d)}{2 d^2} \cdot x^2 + O(x\log x) = \frac{1}{2\zeta(2)} x^2 + O(x\log x) $$ because the later sum converges to $1 / \zeta(2) = 6/\pi^2$. $\square$

EDIT: In particular your limit is indeed equal to $2$!

EDIT 2: Actually for most integers $\varphi(n) \asymp n$.

In fact the proportion of integers $n < x$ such that $\alpha n < \varphi(n) < \beta n$, with $\alpha < 1$ converges to a continuous distribution function $$\mathbb{P}(\alpha < X < \beta) > 0$$ where explicitely $$ X := \prod_{p} \bigg ( 1 - \frac{X(p)}{p} \bigg )$$ and the $X(p)$ are independent random variables with $$\mathbb{P}(X(p) = 1) = \frac{1}{p} \text{ and } \mathbb{P}(X(p) = 0) = 1 - \frac{1}{p}.$$ This is Schoenberg's theorem.

$\endgroup$
3
  • $\begingroup$ Very nice! Numerically it comes out very near for x up to $2^{19}$ . I'll have to chew on this a bit more, thanks for the hint to the Moebius-inversion! $\endgroup$ Jul 18, 2013 at 19:03
  • 1
    $\begingroup$ Hi! I've added an edit on Schoenberg's theorem which might interest you. If you have any questions about the proof of either let me know! $\endgroup$
    – blabler
    Jul 18, 2013 at 19:08
  • $\begingroup$ Thanks again. I accepted it also now, because it was initially most hepful and also because the question seems to get closed soon. $\endgroup$ Jul 18, 2013 at 20:18
4
$\begingroup$

We have the asymptotic result $$\sum_{n\leq x}\phi(n)=\frac{3}{\pi^{2}}x^{2}+O\left(x\log x\right),$$ so your limit is $2$.

For a complete overview with proof of the above as well as proofs of the $\Omega$ type results for the error term, take a look at this Blog Post.

A solution to this question can also be found in two other answers of mine on Math Stack Exchange: Probability that two random numbers are coprime and Asymptotic formula for $\sum_{n\leq x}\mu(n)[x/n]^2$ and the Totient summatory function $\sum_{n\leq x} \phi(n)$

$\endgroup$
1
  • $\begingroup$ Thanks for the link. Your answer there is much interesting! $\endgroup$ Jul 18, 2013 at 19:36

You must log in to answer this question.

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