For each positive integer $k$, let $P_k$ denote the product of the first k primes. Show that $\varphi(P_k) = \theta(P_k / \log \log P_k)$ is the worst case, in the sense that $\varphi(n) = \Omega(n / \log \log n)$.

Any help would be appreciated. Thanks

  • $\begingroup$ I think you mean $\phi(n) \gg n/\log\log n$, not $\phi(n) = \Omega(n/\log\log n)$. The first statement says that $\phi(n)$ is always at least that large; the second statement says only that $\phi(n)$ is infinitely often that large. $\endgroup$ – Greg Martin Mar 7 '13 at 1:55
  • $\begingroup$ What does the phrase "is the worst case, in the sense" mean here? The symbols $\theta$ and $\Omega$ are well-defined; neither does "being the worst case" make any sense applied to $\theta$, nor is it clear (to me) how it could be imbued with any sense by the $\Omega$ statement. Please explain. $\endgroup$ – joriki Mar 7 '13 at 1:56
  • $\begingroup$ It's a little hard to decide what your question is. Are you saying that you already know that $\phi(P_k) = O(P_k/\log\log P_k)$, and you're looking for a proof that $\phi(n) \gg n/\log\log n$ for any $n$? $\endgroup$ – Greg Martin Mar 7 '13 at 1:56
  • $\begingroup$ What you stated is correct Greg $\endgroup$ – Matt Mar 7 '13 at 2:03
  • $\begingroup$ Any ideas? I am still struggling on this one. Thanks $\endgroup$ – Matt Mar 7 '13 at 2:50

The overall result is due to Landau, 1903, Theorem 328 in Hardy and Wright, that $$ \liminf \; \frac{e^\gamma \phi(n) \log \log n}{n} = 1, $$ proof in section 22.9.

Oh, well. Note that the statement you think you are trying to prove is incorrect. Nicolas showed that if the Riemann Hypothesis is true, then whenever $n = 2 \cdot 3 \cdot 5 \cdots p_k$ is a primorial, then $\frac{e^\gamma \phi(n) \log \log n}{n} < 1.$ If the Riemann Hypothesis is false, then $\frac{e^\gamma \phi(n) \log \log n}{n} < 1$ for infinitely many primorials $n$ and $\frac{e^\gamma \phi(n) \log \log n}{n} > 1$ for infinitely many primorials $n.$ As the Rosser and Schoenfeld lower bound from my earlier post and Wikipedia holds for all numbers greater than 2, this says that the ratios depicted that are below 1 are awfully close to it.

For more precise information, see both my answers at Is the Euler phi function bounded below?

sources: NICOLAS and a comment at PLANAT


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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