Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
168 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Indicatrice d'Euler

Envoyé par Madvin 
Indicatrice d'Euler
il y a treize années
Bonjour à tous,

Je viens juste de m'inscrire sur le forum, et vu la quantité de passionnés qui s'y trouve régulièrement, j'espère pouvoir trouver des réponses à mes questions et avoir des discussions intéressantes.

Alors voilà, je suis qu'un amateur en mathématiques, de niveau BAC+2 (j'ai eu mon DEUG MIAS), mais j'ai continué après dans une filière informatique (et oui, j'adore ça aussi). Je suis passionné par la théorie des nombres et j'ai toujours voulu écrire un papier assez complet sur la fonction indicatrice d'Euler que je trouve particulièrement intéressante.

D'où ma première question : J'avais trouvé un jour dans un livre (qui faisait partie d'une série de 6 ou 7 volumes), une démonstration de la propriété suivante :

$\forall n \ge 3$, $\varphi(n) \ge \frac{n\ln 2}{\ln n + \ln 2}$

1. Je n'arrive plus à retrouver la démonstration par moi-même... Est-ce que quelqu'un aurait une idée ?

2. Je ne me souviens plus des références (auteur, titre, éditeur,...) de cette série de livres. Si je me souviens bien, les couvertures étaient simples : écriture noire sur fond blanc. Est-ce que cela dit quelque chose à quelqu'un ?

3. Latex n'affiche pas la lettre phi minuscule comme je l'attendais : à savoir le symbole avec une seule boucle. Est-il possible d'afficher ce phi qui possède qu'une seule boucle ?

Merci beaucoup.

[Pour le 3) : $\varphi$ s'écrit \verb=\varphi=. :) AD]
Re: Indicatrice d'Euler
il y a treize années
{\bf Premier point}.

On trouve une preuve de l'inégalité $$\varphi(n) > \frac {\ln 2}{2} \frac {n}{\ln n}$$ valide pour $n \geqslant 3$ (donc du même ordre de grandeur que la tienne) dans le papier : {\bf H. Hatalova et T. Salat}, {\it Remarks and results in the elementary theory of numbers}, Acta Fac. Rer. Natur Univ. Comenian Math. {\bf 20} (1969), 113--117.


{\bf Second point}.

On va faire mieux et montrer que l'inégalité $$\frac {n}{\varphi(n)} < \left ( e^{\gamma + 7/\ln\ln n} \right ) \ln \ln n$$ est valide pour tout entier $n \geqslant 3$. Cette inégalité est du {\it bon ordre de grandeur}, puisque l'on sait que, pour une infinité de valeurs de $n$, on a : $$\frac {n}{\varphi(n)} > e^{\gamma}\ln \ln n$$ (Voir {\bf J-L. Nicolas}, {\it Petites valeurs de la fonction d'Euler}, J Number Theory {\bf 17} (1983), 375--388).


{\bf Notations} $\gamma \approx 0,577 \, 215 \, 664 \dotsc$ est la constante d'Euler et $B \approx 0,26 \, 149 \, 721\dotsc$ est la constante de Mertens. $\omega(n):=\sum_{p \mid n} 1$ est le nombre de facteurs premiers distincts de $n$.


{\bf Lemme 1}. Pour tout $n \geqslant 3$ entier, on a : $$\omega(n) < 1,4 \frac {\ln n}{\ln \ln n}$$ (voir {\bf G. Robin}, {\it Estimations de la fonction $\theta$ sur le k-ème nombre premier et grandes valeurs de la fonction $\omega(n)$ nombre de diviseurs premiers de $n$}, Acta Arith. {\bf 42} (1983), 367--389).


{\bf Lemme 2}. Pour tout réel $x \geqslant 2$, on a : $$\left | \sum_{p \leqslant x} \frac {1}{p} - \ln \ln x - B \right | \leqslant \frac {2+\ln 16}{\ln x}.$$

Preuve bien connue, que l'on trouve dans n'importe quel livre de théorie analytique des nombres.


{\bf Lemme 3}. Pour tout entier $n \geqslant 2$, on a : $$\frac {n}{\varphi(n)} < e^{\gamma - B} \exp \left ( \sum_{p \mid n} \frac {1}{p} \right ).$$

{\it Preuve}. On a : $$\frac {n}{\varphi(n)} = \prod_{p \mid n} \left ( 1 - \frac {1}{p} \right )^{-1} = \exp \left ( \sum_{p \mid n} \frac {1}{p} + \sum_{k=2}^{\infty} \sum_{p \mid n} \frac {1}{k p ^k} \right ),$$ et on conclut avec $$\sum_{p} \sum_{k=2}^{\infty} \frac {1}{k p ^k} = \gamma - B.$$


{\bf Lemme 4}. Pour tout entier $n \geqslant 3$, on a : $$\sum_{p \mid n} \frac {1}{p} < \ln \ln \ln n + B + \frac {7}{\ln \ln n}.$$

{\it Preuve}. Soit $t > 1$ un paramètre à notre disposition. On a : $$\sum_{p \mid n} \frac {1}{p} = \sum_{\substack{p \mid n \\ p \leqslant t}} \frac {1}{p} + \sum_{\substack{p \mid n \\ p > t}} \frac {1}{p} < \sum_{p \leqslant t} \frac {1}{p} + \frac {\omega(n)}{t},$$ et les lemmes 1 et 2 fournissent : $$\sum_{p \mid n} \frac {1}{p} < \ln \ln t + B + R(t) + \frac {1,4 \, \ln n}{\ln \ln n},$$ avec $0 \leqslant R(t) \leqslant \frac {2 + \ln 16}{\ln t}$. Le résultat s'ensuit en prenant $t = \ln n$.

Le théorème découle alors directement des lemmes 3 et 4.


Borde.
Re: Indicatrice d'Euler;)
il y a treize années
Salut, c'est re-moi ! :D

Désolé d'avoir mis autant de temps pour reprendre le fil de la discussion mais j'avais pas mal de choses à faire ces derniers jours...

Merci [borde] pour toutes ces infos : ta démo est beaucoup plus compliquée que celle que je cherche, mais c'est toujours intéressant de connaître ce genre de résultats.
Surtout que le cheminement d'une démonstration est généralement toujours plus intéressant que la description de la proposition qu'elle prouve.

Pour revenir à mes questions :

{\bf Q3.} Merci à l'administrateur pour l'info. Donc apparemment c'est \verb=\varphi= qu'il faut utiliser... (ça marche bien \verb=\varphi= ? Voyons... : $\varphi$ !! Ca a marché \verb=\varphi= ? A ben apparemment oui ! Merci !! :)-D)
{\bf CLOS}


{\bf Q2.} J'ai retrouvé les références de ces fameux bouquins d'arithmétique pour amateur. C'est de Marc Guinot / Edition ALEAS. La démonstration que je cherche (voir question 1) doit très certainement se trouver dans le tome : Ce Diable d'homme d'Euler.
{\bf CLOS}


{\bf Q1.} Je me souviens que la démonstration était très simple et tenait sur quelques lignes seulement.
Mais j'arrive pas à la retrouver par moi-même, j'oublie certainement quelque chose quelque part... Personne n'a d'idée ?


Questions supplémentaires :

{\bf Q4.} La grande majorité des résultats mathématiques intéressants (les plus compliqués ou/et longs à démontrer) ainsi que leur démo ne se trouvent que dans des revues spécialisées ou des bouquins rares (voir par exemple le message de [borde] ci-dessus dans lequel il donne des références bibliographiques). Question que je me pose : A quoi sert donc internet ? Que je sache les démonstrations mathématiques n'appartiennent à personne : les publications oui, mais les démonstrations en elles-même ? N'y a t-il pas des sites ou autres permettant à quiconque d'accéder à ces démonstrations ?


{\bf Q5.} Revenons-en à cette indicatrice d'Euler : comme on l'a vu plus haut notamment, il a été démontré bon nombre d'inégalités permettant de minorer $\varphi(n)$ pour tout $n$ supérieur à un certain nombre.
C'est-à-dire : Pour tout entier $n \ge C$ avec $C$ un réél, $f(n) \le \varphi(n)$ avec $f$ une fonction.
Mais peut-on trouver des fonctions permettant, de la même sorte, de majorer $\varphi(n)$ ?
Alors bien sûr vous allez bien évidemment tout de suite me dire que $f(n) = n$ ou encore plus précis $f(n) = n - 1$ conviennent pout tout $n \ge 2$ (cela se déduit aisément de la définition de la fonction $\varphi$, avec notamment les cas où $n$ est premier et pour lesquels $\varphi(n) = n - 1$).
Mais ma question sera celle-ci :
{\bf Peut-on trouver une fonction $f$ non affine et un réél $C$ tels que $\forall n \in \mathbb{N}$, avec $n \ge C$ et $n$ non premier, $\varphi(n) \le f(n) < n - 1$ ?}
Et j'ai bien précisé 'non affine' !!! Car sinon des petits malins auraient donné des solutions du genre $f(n) = n - 1,1$ !!! spinning smiley sticking its tongue out
Et ne m'obligez pas à rajouter continue et dérivable $\forall x \in \mathbb{R}$, $x \ge C$. spinning smiley sticking its tongue outspinning smiley sticking its tongue out
Vous avez très bien compris quelle sorte de fonction j'attends comme solution... Pas de bidouillage je vous prie... ;)

Q5.1 - D'après Wikipédia, $f(n) = n - \sqrt{n}$ convient $\forall n \in \mathbb{N}$, $n \ge 4$ ($n$ composé je le rappelle). Avez-vous une démo ?
Q5.2 - Peut-on trouver une fonction $f$ solution de l'ordre de $\frac {n}{\ln n}$ ?

Bilan des questions :

Q1. En cours...
Q2. CLOS
Q3. CLOS
Q4. Nouvelle
Q5. Nouvelle
Q5.1 Nouvelle
Q5.2 Nouvelle
Re: Indicatrice d'Euler
il y a treize années
Pour la question Q4, reproduire en accès public une preuve appartenant à un auteur pose sans doute un problème de copyright. Ceci étant, on trouve parfois des sites qui proposent quelques résultats. Cependant, il subsiste sur ces sites une probabilité que le texte soit erroné.

Ainsi vaut-il mieux, selon moi, consulter les articles, accessibles librement dans une BU.


Pour la question Q5.1, voir mon livre exercice 4.3 page 125.


Quant à la question Q5.2, elle ne présente plus d'intérêt puisque l'on a montré ci-dessus une majoration nettement meilleure.

Maintenant, si tu la trouves trop longue, tu peux la raccourcir en étant moins exigeant dans le résultat. Par exemple, on peut repartir du lemme 3 simplifié en remarquant que $\displaystyle {\sum_{p} \sum_{k=2}^{\infty} \frac {1}{k p^k} < 2}$ de sorte que $$\frac {n}{\varphi(n)} < 2 \exp \left ( \sum_{p \mid n} \frac {1}{p} \right ) \leqslant 2 \exp \left ( \sum_{p \leqslant n} \frac {1}{p} \right ) \ll \exp (\ln \ln n ) \ll \ln n,$$ mais l'amélioration obtenue plus haut, à peine plus difficile que ce résultat, ne mérite pas que l'on ne la fasse pas...d'autant plus que l'on a atteint, comme je l'ai dit plus haut, le {\it bon ordre de grandeur}.

Borde.
Re: Indicatrice d'Euler
il y a treize années
{\bf Q1.} Ca y est, j'ai réussi. Je mettrai la démo complète un peu plus tard dans la journée.
Voici juste les étapes importantes, pour ceux qui auraient envie de trouver la démo par eux-même ;) :

Soit $m$, le nombre de facteurs premiers d'un entier naturel $n \ge 3$.
a) Montrer que $m \le \frac {\ln n} {\ln 2}$
b) Montrer que $\varphi(n) \ge \frac {n} {m+1}$
c) Conclure à partir de a) et b)

Je repasserai plus tard... (Non ! Pas le linge ! :o)
Re: Indicatrice d'Euler
il y a treize années
[borde] La majoration de $\varphi(n)$ que tu as donnée dans ton premier message est :

Citation
borde
Pour une infinité de valeurs de $n$, on a : $$\frac {n}{\varphi(n)} > e^{\gamma}\ln \ln n$$

Or d'après ce que tu indiques, celle-ci fonctionne pour 'une infinité de valeur', et non pas pour 'tous les entiers composés supérieurs à un certain réél'.

Me trompe-je ?

De plus le Lemme 3 concerne une minoration, et non une majoration... ;)
Re: Indicatrice d'Euler
il y a treize années
Mon premier message donne une minoration de $\varphi(n)$, aussi précise que possible, puisque la meilleure minoration explicite connue, donnée par Rosser et Schoenfeld, est : $$\frac {n}{\varphi(n)} < e^{\gamma} \ln \ln n + \frac {2,50 \, 637}{\ln \ln n}$$ (voir Rosser et Schoenfeld, {\it Approximate formulas for some functions of prime numbers}, Ill. J. Math (1962), 64--94).

Quant à la majoration indiquée, je l'avais mise ici pour montrer que la minoration est du bon ordre de grandeur. D'ailleurs, on sait depuis Landau (1903) que : $$\liminf_{n \rightarrow \infty} \frac {\varphi(n) \ln \ln n}{n} = e^{-\gamma}.$$

Maintenant, il existe une foultitude d'autres inégalités faisant intervenir $\varphi$, moins précises que celles données ci-dessus, mais qui relient diverses fonctions arithmétiques entre elles. En vrac, on a par exemple :

(i) $\varphi(n) \geqslant \pi(n)$ pour $n \geqslant 90$,

(ii) $\varphi(n) \geqslant \dfrac {n}{\tau(n)}$ pour $n \geqslant 1$,

(iii) $\varphi(n) \geqslant \dfrac {\sigma(n)}{\tau(n)}$ pour $n$ impair,

(iv) $\varphi(n) \leqslant \left ( \dfrac {n}{\tau(n)} \right )^2$ pour $n \not = 4$,

(v) $\dfrac {1}{\zeta(2)} < \dfrac {\sigma(n) \varphi(n)}{n^2} < 1$ pour $n \geqslant 1$.

etc.

Rappelons que : $\pi(n) = \sum_{p \leqslant n} 1$ est le nombre de nombres premiers $\leqslant n$, $\tau(n)$ est le nombre de diviseurs de $n$ et $\sigma(n)$ est la somme des diviseurs de $n$.

Borde.
Re: Indicatrice d'Euler
il y a treize années
Merci [borde] pour toutes ces formules, la plupart je ne les connaissais pas et faudra que je regarde ça d'un peu plus près. ;)


{\bf Q5.} Pour revenir concrètement à ma question, sur la MAJORATION de $\varphi(n)$ pour tout entier composé $n$ supérieur à une constante $C$ : pour l'instant nous n'avons que la formule :
$\forall n \in \mathbb{N}$, $n \ge 2$, $n$ composé, $\varphi(n) \le n - \sqrt{n}$
J'ai essayé de démontrer cette propriété et on y arrive assez facilement. Je vous mettrai la démo un peu plus tard.


Bon sinon je vous mets enfin la démo de la Q1. Je ne la retrouvais pas car j'avais oublié (encore une fois...) de majorer $\omega(n)$. (j'espère que j'ai pas fait de bourdes parce que j'ai pas trop l'habitude du latex encore.:o).


{\bf Q1.}
{\bf Proposition 1 :} {\it $\forall n \ge 2$, $\varphi(n) \ge \dfrac{n\ln 2}{\ln n + \ln 2}$}

Pour rendre la démonstration plus claire et plus propre, nous allons d'abord démontrer les 2 lemmes suivants :

{\bf Lemme 1a :} {\it Soit $\omega : \mathbb{N} \rightarrow \mathbb{N}$, la fonction qui associe à un entier naturel $n$ le nombre total de facteurs premiers distincts qui divisent $n$.
(ex. $\omega(2^{10}.5.11^{2007}) = 3 $ [2, 5 et 11])
On a $\forall n \ge 2$, $\omega(n) \le \dfrac{\ln n}{\ln 2}$}

{\it \bf Démonstration 1a :}
Soit $n \in \mathbb{N}$, $n \ge 2$ dont la décomposition en facteurs premiers est $$n = q_1^{r_1}.q_2^{r_2}...q_{\omega(n)}^{r_{\omega(n)}} = \prod_{k=1}^{\omega(n)} q_k^{r_k}$$ avec $\forall i \in \mathbb{N}$, $1 \le i \le \omega(n)$ : $q_i$ est un nombre premier, $r_i \in \mathbb{N^*}$
et avec $\forall i \in \mathbb{N}$, $\forall j \in \mathbb{N}$, $1 \le i \le \omega(n)$, $1 \le j \le \omega(n)$, $i < j$ : $q_i < q_j$
Tout nombre premier étant supérieur ou égal à 2, il est donc évident que
$\forall k \in \mathbb{N}$, $1 \le k \le \omega(n)$ : $q_k \ge 2$
Ce qui implique donc que :
$$\prod_{k=1}^{\omega(n)} q_k \ge 2^{\omega(n)}$$
Et comme : $$\prod_{k=1}^{\omega(n)} q_k^{r_k} \ge \prod_{k=1}^{\omega(n)} q_k$$
On a donc : $$n = \prod_{k=1}^{\omega(n)} q_k^{r_k} \ge \prod_{k=1}^{\omega(n)} q_k \ge 2^{\omega(n)}$$
Comme la fonction $\ln$ est croissante, on en déduit que : $$\ln n \ge \ln 2^{\omega(n)} = \omega(n).\ln 2$$
Ce qui donne donc : $$\omega(n) \le \dfrac{\ln n}{\ln 2}$$
{\it CQFD}


{\bf Lemme 1b :} {\it $\forall n \ge 2$, $\varphi(n) \ge \dfrac{n}{\omega(n)+1}$}

{\it \bf Démonstration 1b :}
Soit $n \in \mathbb{N}$, $n \ge 2$ dont la décomposition en facteurs premiers est $$n = q_1^{r_1}.q_2^{r_2}...q_{\omega(n)}^{r_{\omega(n)}} = \prod_{k=1}^{\omega(n)} q_k^{r_k}$$ avec $\forall i \in \mathbb{N}$, $1 \le i \le \omega(n)$ : $q_i$ est un nombre premier, $r_i \in \mathbb{N^*}$
et avec $\forall i \in \mathbb{N}$, $\forall j \in \mathbb{N}$, $1 \le i \le \omega(n)$, $1 \le j \le \omega(n)$, $i < j$ : $q_i < q_j$
Il est trivial de remarquer que $\forall i \in \mathbb{N}$, $1 \le i \le \omega(n)$ : $q_i \ge p_i \ge i+1$, avec $p_i$ le i-ème nombre premier. ($q_1 \ge p_1 = 2 \ge 1+1$, $q_2 \ge p_2 = 3 \ge 2+1$, $q_3 \ge p_3 = 5 \ge 3+1$, etc...)
Donc, comme la fonction inverse est décroissante, on a $\forall i \in \mathbb{N}$, $1 \le i \le \omega(n)$ : $$\dfrac{1}{q_i} \le \dfrac{1}{i+1}$$
D'où : $$1-\dfrac{1}{q_i} \ge 1-\dfrac{1}{i+1}$$
D'où : $$\dfrac{q_i-1}{q_i} \ge \dfrac{i}{i+1}$$
Donc : $$\prod_{k=1}^{\omega(n)} \dfrac{q_k-1}{q_k} \ge \prod_{k=1}^{\omega(n)} \dfrac{k}{k+1} = \dfrac{1}{2} . \dfrac{2}{3} . ... . \dfrac{\omega(n)-1}{\omega(n)} . \dfrac{\omega(n)}{\omega(n)+1} = \dfrac{1}{\omega(n)+1}$$
Donc, en multipliant par $n$ : $$n\prod_{k=1}^{\omega(n)} \dfrac{q_k-1}{q_k} \ge \dfrac{n}{\omega(n)+1}$$
Or d'après le théorème d'Euler, on sait que : $$\varphi(n) = n\prod_{k=1}^{\omega(n)} \dfrac{q_k-1}{q_k}$$
D'où on déduit : $$\varphi(n) = n\prod_{k=1}^{\omega(n)} \dfrac{q_k-1}{q_k} \ge \dfrac{n}{\omega(n)+1}$$
{\it CQFD}

A partir de ces 2 lemmes, on peut maintenant démontrer la {\bf Proposition 1} :

{\it \bf Démonstration 1 :}

Le lemme 1a montre que $\forall n \ge 2$ : $$\omega(n) \le \dfrac{\ln n}{\ln 2}$$
Donc : $$\omega(n)+1 \le \dfrac{\ln n}{\ln 2}+1 = \dfrac{\ln n + \ln 2}{\ln 2}$$
Donc, comme la fonction inverse est décroissante : $$\dfrac{1}{\omega(n)+1} \ge \dfrac{\ln 2}{\ln n + \ln 2}$$
Puis en multipliant par $n$, on obtient : $$\dfrac{n}{\omega(n)+1} \ge \dfrac{n\ln 2}{\ln n + \ln 2}$$
Or, le lemme 1b indique que $\forall n \ge 2$ : $$\varphi(n) \ge \dfrac{n}{\omega(n)+1}$$
On en déduit donc que $\forall n \ge 2$ : $$\varphi(n) \ge \dfrac{n}{\omega(n)+1} \ge \dfrac{n\ln 2}{\ln n + \ln 2}$$
{\it CQFD}

Fiouf, enfin... Si vous trouvez des coquilles ou si vous avez des remarques, je vous en prie...
De plus c'est étrange, je suis pratiquement sûr que dans le livre la formule était démontrée pour $n \ge 3$, alors qu'elle fonctionne apparemment pour $n=2$... Non ? Y a-t il un point dans la démo qui ne fonctionne pas pour $n=2$ ? A moins que l'inégalité démontrée dans le livre était stricte...


Bilan :
Q1. Rédigée (En cours de relecture...)
Q2. CLOS
Q3. CLOS
Q4. En attente de réponse...
Q5. En attente de réponse...
Q5.1 En cours de rédaction...
Q5.2 En attente de réponse...
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 145 192, Messages: 1 445 229, Utilisateurs: 27 183.
Notre dernier utilisateur inscrit Mikahopff.


Ce forum
Discussions: 5 441, Messages: 66 224.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page