Proving $\phi (n_k) \ll \frac{n_k}{\log \log n_k}.$

136 Views Asked by At

Show that there is an increasing sequence of positive integers $n_1, n_2, \cdots$ such that $$\phi (n_k) \ll \frac{n_k}{\log \log n_k}.$$

I was able to prove that $\phi (n) \gg \frac{n}{\log \log n}$ (the proof is a bit lengthy, so I will not post it unless requested), but I am unsure how to show this result for an increasing sequence of positive integers.

Notation:

$f(x) \ll g(x)$ if $|f(x)|\leq Mg(x)$.

2

There are 2 best solutions below

0
On BEST ANSWER

Consider numbers of the form $L_N = \prod_{p \le N} p$. Note $\log L_N = \psi(N) \sim N$, so $\log \log L_N \sim \log N$. And, $\phi(L_N) = \prod_{p \le N} (p-1)$, so you just need to show $\prod_{p \le N} (1-\frac{1}{p}) \ll \frac{1}{\log N}$. This is true.

0
On

If $n_k=\prod\limits_{p\leq p_k}p$ (aka primorial) then (also considering Mertens' third theorem) $$\frac{\phi(n_k)}{n_k}= \prod\limits_{p\leq p_k}\left(1-\frac{1}{p_i}\right)\sim \frac{e^{-\gamma}}{\ln{p_k}}$$ This means that from some $k_0$ onwards $$\frac{\phi(n_k)}{n_k}< (1+\varepsilon) \frac{e^{-\gamma}}{\ln{p_k}} \tag{1}$$ But $$\ln{n_k}=\sum\limits_{p\leq p_k}\ln{p}=\vartheta(p_k) < 1.000028\cdot p_k$$ or $$\ln{\ln(n_k)}-\ln{1.000028}<\ln{p_k}$$ and $(1)$ becomes $$\frac{\phi(n_k)}{n_k}< (1+\varepsilon) \frac{e^{-\gamma}}{\ln{\ln(n_k)}-\ln{1.000028}}< (1+\varepsilon)^2 \frac{e^{-\gamma}}{\ln{\ln(n_k)}} \tag{2}$$ simply because $\lim\limits_{k\rightarrow\infty} \frac{1}{1-\frac{\ln{1.000028}}{\ln{\ln(n_k)}}}=1$.

As a result for $(1+\varepsilon)^2 < e^{\gamma} \Rightarrow \forall \varepsilon: 0<\varepsilon <\sqrt{e^{\gamma}}-1 \approx 0.335, \exists k(\varepsilon)$ s.t. $$\frac{\phi(n_k)}{n_k}< \frac{1}{\ln{\ln(n_k)}} \tag{3}$$ for $\forall k>k(\varepsilon)$.