Indicatrice d'Euler

nyadis

Bonjour ! Si $n$ est suffisamment grand, peut-on écrire que $$\frac{\varphi(n)}{n} \gg  1 \quad?$$
Cela me semble logique lorsque je considère la relation suivante sur Wikipédia. $$ \frac{\varphi(n)}{n} > \frac{\mathrm{e}^{-\gamma}}{\log_2n}$$
https://fr.wikipedia.org/wiki/Indicatrice_d'Euler

Renart

Quelles sont les définitions que tu utilises ? On a $\varphi(n) \leq n$ quel que soit l'entier $n\in \N^*$, donc $\varphi(n)/n \leq 1 $, l'inégalité est d'ailleurs stricte si $n > 1$. On n'a donc aucune chance d'avoir $\varphi(n)/n \gg 1 $.

Peut-être voulais-tu dire $\varphi(n) \gg 1$ ? Dans ce cas là la réponse est oui, notamment d'après l'inégalité que tu donnes. 

Bibix

Bonjour,

On a $\frac{\varphi(n)}{n} \ll 1$ mais aussi $\frac{\varphi(\#p_n)}{\#p_n} = \prod_{k = 1}^n \left(1 - \frac{1}{p_k}\right) \underset{n \to +\infty}{\to} 0$ pour $\#p_n = \prod_{k = 1}^n p_k$ avec $p_1, p_2, ..., p_n$ les $n$ premiers nombres premiers (car $\sum_{k \in \mathbb{N}^*} \frac{1}{p_k}$ diverge). Donc non, il est faux d'écrire que $\frac{\varphi(n)}{n} \gg 1$.

nyadis

Je comprends. Mais ce n'est pas une inégalité stricte lorsque j'écris $\frac{\varphi(n)}{n} \gg 1$. Ici, la notation $\gg$ fait référence à la notation grand $O$. Donc je veux dire $\frac{\varphi(n)}{n} =O(1)$ lorsque $n$ est très grand. 

noix de totos

Tu as mis tes inégalités dans le mauvais sens : $f \ll g \iff f = O(g)$ et $f \gg g \iff g = O(f)$.

Exemple. L'inégalité mise dans ton premier message s'écrit (moins précisément) sous la forme $\varphi(n) \gg \frac{n}{\log \log n}$.

nyadis

Merci

noix de totos

Un petit point de détail supplémentaire.

L'inégalité explicite fournie par Nyadis dans son premier message est fausse en général. En fait, on sait qu'il existe une infinité d'entiers $n$ tels que $\varphi(n) < \dfrac{n}{e^\gamma \log\log n}$ (Nicolas, 1983).

En revanche, en voici trois qui corrigent cette coquille : 

(i) Rosser & Schœnfeld, 1962. Pour tout entier $n \geqslant 3$,
$$\varphi(n) \geqslant \frac{n}{e^{\gamma} \log \log n + 2,50637 (\log \log n)^{-1}}.$$
(ii) Nicolas, 2008. Pour tout entier $n \geqslant 3$,
$$\varphi(n) \geqslant \frac{n}{e^{\gamma} \log \log n + 3,65278}$$
avec égalité si $n=6$. De plus, si $n \geqslant 211$, alors
$$\varphi(n) \geqslant \frac{n}{3 \log \log \varphi(n)}.$$
En particulier, l'inégalité $\varphi(n) \gg n (\log \log n)^{-1}$ est parfaitement correcte.