pi(n)

borde

Bonsoir,

Afin de mesurer la difficulté de cet exercice, je propose (une fois n'est pas coutume...) de démontrer (ou d'infirmer) l'inégalité suivante, valable pour tout entier $n \geqslant 25$ : $$\pi(n) \leqslant \frac {n}{3} + \frac {5}{6}$$ où, comme d'habitude, $\pi(n)$ désigne le nombre de nombres premiers $p \leqslant n$ (sans artifice technique du genre {\it inégalités de Tchébytchev} ou {\it th. des nombres premiers}). On peut, par exemple, s'inspirer de la preuve figurant dans le Sierpinski ({\it 250 problèmes de théorie élémentaire des nombres}) page 165, lemme 7.

Merci et bon courage,

Borde.

borde

...la constante $\displaystyle {\frac {5}{6}}$ importe peu (on peut la remplacer par $2$ ou $3$, par exemple). C'est surtout le $\displaystyle {\frac {n}{3}}$ qui m'intéresse.

Borde.

lolo1

Bon , j'essaie (sans Sierpinski):
les multiples de 2 inférieur à n ne sont pas premiers et il y en a au moins
n/2 - 2 , les multiples de 3 au moins n/3 - 3 MAIS pour ne pas compter deux fois les multiples de 6 :
on a au maximum n - n/2 - n/3 + n/6 +C nombres premiers d'où la majoration par n/3 + C.

j'espère ne pas m'être fourvoyé en cette heure tardive ?

lolo

borde

Excellent, Lolo, je suis entièrement d'accord avec cette idée.

Merci d'avoir pris ton temps pour réfléchir à ce problème, et d'avoir répondu si vite.


Borde.

bob26

Bonjour à tous,

Bravo lolo! Comme j'ai étudié de prêt cette question, je me permets de donner un complément de réponse.

Plus généralement, on a

(*) pi(x) <= pi(y) + phi(x,y)

où phi(x,y) est le cardinal de l'ensemble des nombres <= x, dont tous les facteurs premiers sont > y. On est ramené à majorer phi(x,y) = cardinal de l'ensemble des entiers <= x et premiers au produit des nombres premiers <= y. On a alors le petit lemme qui se démontre facilement (uniformément en a)

lemme. /{n<=x, (n,a) = 1}/ = xphi(a)/a + 0(a)

où phi est la fonction d'Euler.

On obtient donc uniformément en x et y

phi(x,y) = x.produit sur p<=y de (1-1/p) + 0(y^y)

En réinjectant dans (*), on obtient

Proposition. pi(x) <= x.produit sur p<=y de (1-1/p) + 0(y^y).

En particularisant en y=3, on retrouve l'argumentation de lolo.
On peut aussi chercher à optimiser en y; par produit Eulérien et comparaison de somme 1/n avec l'intégrale, on montre que

produit sur p<=y de (1-1/p) < 1/log y, d'où finalement par un petit calcul d'optimisation

pi(x) <= (1+o(1))x/loglog x.


Tout cela est en fait extrait du premier chapitre d'INGHAM, The distribution of prime numbers.

Bien amicalement,

Bob

borde

Je suis d'accord, Bob, tu as utilisé ce que l'on appelle maintenant les {\it méthodes de cribles} (en l'occurrence, ici, une version améliorée par Legendre du célèbre crible d'Erathostène).

Tu peux améliorer ton résultat, et aller vers les {\it inégalités de Tchebytchev} par la méthode suivante :

1. Montre par récurrence que, si $n \geqslant 2$ est entier, alors $$\prod_{p \leqslant n} p \sum_{x \ln x \sum_{x

brux0

Merci beaucoup à bob et à borde pour ces deux méthodes très élégantes.
Auriez-vous dans votre musette une preuve aussi lisible et claire pour une minoration de pi(n) en n/ln n. Je connais la méthode de Nair mais bien qu'élémentaire, on ne comprend pas trop ce que l'on fait....
brux

borde

Salut Brux (ça faisait longtemps...),

Voici une version allégée de la {\bf méthode de Nair} :

{\bf Lemme}. Soit $n \geqslant 2$ entier. Si d_n = ppcm(1,2,...,n)$ alors : $$d_n \geqslant 2^{n-2}$$ (tu remarqueras que Tenenbaum a mieux dans son livre, mais c'est légèrement plus compliqué).

{\it Preuve}. Considère l'intégrale $$I_n = \int_{0}^{1} x^n (1 - x)^n \, dx$$ D'abord, en encadrant la fonction, tu vérifies facilement que, pour tout $n \geqslant 1$, on a $$0 \frac {1}{2} \times \frac {n}{\ln n}.$$

{\it Preuve}. Tu sais que $d_n$ s'écrit sous la forme $\displaystyle {d_n = \prod_{p \leqslant n} p^{e_p}}$ où $e_p$ est la plus haute puissance de $p \leqslant n$, soit $\displaystyle {e_p = \left [ \frac {\ln n}{\ln p} \right ]}$. Ainsi : $$d_n \leqslant \prod_{p \leqslant n} p^{\ln n / \ln p} = \prod_{p \leqslant n} n = n^{\pi(n)}$$ et donc $$\pi(n) \geqslant \frac {\ln d_n}{\ln n}$$ et le lemme ci-dessus te donne alors $$\pi(n) \geqslant \frac {(n-2} \ln 2}{\ln n} > \frac {1}{2} \times \frac {n}{\ln n}$$ dès que $n \geqslant 8$. Vérifies alors l'inégalité pour $n \in \{ 3,...,7 \}$.

J'espère avoir été satisfaisant.

A +

Borde.

borde

Salut Brux (ça faisait longtemps...),

Voici une version allégée de la {\bf méthode de Nair} :

{\bf Lemme}. Soit $n \geqslant 2$ entier. Si $d_n = ppcm(1,2,...,n)$ alors : $$d_n \geqslant 2^{n-2}$$ (tu remarqueras que Tenenbaum a mieux dans son livre, mais c'est légèrement plus compliqué).

{\it Preuve}. Considère l'intégrale $$I_n = \int_{0}^{1} x^n (1 - x)^n \, dx$$ D'abord, en encadrant la fonction, tu vérifies facilement que, pour tout $n \geqslant 1$, on a $$0 \frac {1}{2} \times \frac {n}{\ln n}.$$


{\it Preuve}. Tu sais que $d_n$ s'écrit sous la forme $\displaystyle {d_n = \prod_{p \leqslant n} p^{e_p}}$ où $e_p$ est la plus haute puissance de $p \leqslant n$, soit $\displaystyle {e_p = \left [ \frac {\ln n}{\ln p} \right ]}$. Ainsi : $$d_n \leqslant \prod_{p \leqslant n} p^{\ln n / \ln p} = \prod_{p \leqslant n} n = n^{\pi(n)}$$ et donc $$\pi(n) \geqslant \frac {\ln d_n}{\ln n}$$ et le lemme ci-dessus te donne alors $$\pi(n) \geqslant \frac {(n-2} \ln 2}{\ln n} > \frac {1}{2} \times \frac {n}{\ln n}$$ dès que $n \geqslant 8$. Vérifies alors l'inégalité pour $n \in \{ 3,...,7 \}$.

J'espère avoir été satisfaisant.

A +

Borde.

borde

Lire à la fin : $$\pi(n) \geqslant \frac {(n-2) \ln 2}{\ln n} > \frac {1}{2} \times \frac {n}{\ln n}.$$


Borde.

brux0

Merci beaucoup Borde ! je ne sais pas si c'est ta façon d'exposer ou si je commence enfin à prendre du recul sur ce domaine (il serait temps) mais çà me paraît très clair sous cette forme, on comprend vraiment ce que l'on fait. Rusé ce Nair ! Merci pour cette petite récréation au coeur de la matière qui occupe une grosse partie de mes journées.

brux

borde

Je crois me souvenir que tu prépares (ou tu as préparé ?) une thèse à Nancy (?) en th. analytique des nombres. Je te souhaite bon courage pour cela, car il en faut (et pas qu'un peu...) !!!

Le bouquin de Tenenbaum est très bien, à ceci près qu'il saute pas mal d'étapes, souvent importantes, et ce n'est pas toujours évident de recoller les morceaux...

Je ne sais pas si tu connais ce livre, mais la méthode de Nair (élaborée) y est exposée page 91 : {\bf W. Schwarz et J. Spilker}, {\it Arithmetical functions}, London Math. Soc. Lecture Notes series 184, CUP (1994). Ils développent cette méthode pour démontrer que $$\sum_{n \leqslant x} \psi(n) \geqslant 0,47459...x^2$$ pour $x$ suffisamment grand. Tu remarqueras que l'on est pas loin du bon ordre de grandeur de la constante, en vertu du th. des nombres premiers...

Bonne continuation,

Borde.

brux0

Quelle mémoire (je ne me rappelais pas avoir dit tout çà dans ce forum)! tu as tout juste, je soutiens début juillet.
$\psi$ c'est la fonction sommatoire associée à la fonction $\Lambda$ de von mangoldt ? Ca coïnciderait puisque selon mes calculs
$\sum_{n\le x}\psi(n) \sim \frac{1}{2} x^{2} \quad(x\rightarrow\infty).$

brux

bob26

Merci Borde pour ta première réponse.

Pour brux,

1. la maniere dont je vois la minoration de pi(x) par cx/logx (comme d'ailleurs la majoration de pi(x) par c'x/log x) c'est que fondamentalement c'est l'utilisation de la factorialité de Z sous la forme de l'identité de convolution fondamentale

L = 1*Lambda (ou Lambda est la fonction de von Mangoldt)

dans cette équation L(n) = logn et 1 sont connues, et Lambda est inconnu.
Il s'agit en quelque sorte donc de résoudre de maniere approchée cette équation.



2. Pour cela Tchebychev passe aux fonctions de répartition et obtient

(2) somme pour n<=x = somme sur tous les d>=1 de Lambda(d) [x/d]

Par Stirling, on connait parfaitement la premiere somme; en particulier elle est en premiere approximation en xlogx -x.

Pour tout a entier >=1 fixé, on connait donc parfaitement la fonction
Fa(x) = somme sur tous les d>=1 de Lambda(d) [x/ad]




3. Notre probleme est d'estimer
(3) psi(x):= somme sur d de Lambda(d) Indicatrice de (1, infini)(x/d)

et on connait parfaitement toutes les fonctions
Fa(x) = somme sur d de Lambda(d) ea(x/d)
où ea(y) = [y/a]


Si tu sais écrire fonction indicatrice de(1,infini) = somme sur a de c(a)ea, tu remplaces dans (3), tu inverses les sommations et tu as gagné. Tu as meme une formule exacte pour psi(x).

En réalité on sait ce que vaut c(a) c'est Mobius(a), le probleme c'est que l'on n'a pas le droit d'inverser les sommations!


L'idée de Tchebychev ici est de remarquer qu'en approchant fonction indicatrice de (1,infini) uniquement par une combinaison linéaire de fonctions ea, là bien sur tu as le droit d'inverser les sommations et cela te donne déjà pas mal d'information sur psi(x) en l'occurrence...le théoreme de Tchebychev!



4. La réalisation la plus simple de cette idée est d'utiliser l'encadrement

f. indicatrice de (1,2) <= e1-2e2 <= f. indicatrice de (1,infini)

et tu obtiens psi(x) - psi(x/2) <= F(x) - 2F(x/2) <= psi(x)

La deuxieme inégalité te donne psi(x) >= cx, et tu en déduis pi(x) >= c'x/logx
par sommation d'Abel et en observant que les nombres de la forme p^k avec k>= 2, jouent un role négligeable.

(Remarque: on a ici approché la fonction de Mobius par la fonction de Mobius tronquée aux deux premiers termes)

5. En utilisant la série des premieres inegalités correspondant à x, x/2, x/4 et en sommant par cascade tu obtiens psi(x) <= c"x et par sommation d'Abel pi(x) <= c""x/logx.

6. Tout cela est extrait du Que sais-je Les nombres premiers TENENBAUM-MENDES-FRANCE, mais il m'a fallu un certain temps pour le "digérer"...

A+ B.

borde

Pour Brux : oui, $\displaystyle {\psi (x) = \sum_{n \leqslant x} \Lambda(n)}$ est la seconde fonction de Tchébytchev, avec, comme le dit Bob, $\Lambda(n)$ est la fo nction d Von Mangoldt (qui vaut $\ln p$ si $n = p^l$ et $0$ sinon).

Pour Bob : oui, et voici les références utilisées par Tenenbaum et Al. : {\bf H.J. Diamond}, {\it Elementary methods in the study of the distribution of prime numbers}, Bull. AMS, Vol. 7, N° 3 (1982), 553-589. C'est un remarquable survol de tout ce qui se fait de mieux en Th. analytique, méthodes élémentaires (rappelons d'ailleurs aue, dans ce domaine, "élémentaire" signifie "qui n'utilise pas la variable complexe", et non "simple"...). Brux doit connaître cet article.

Pour Brux : quel est ton sujet de thèse ?

Borde.

bob26

Merci Borde pour ces références,

A+ B.

borde

De rien, Bob...Une petite question, juste par pure curiosité (donc ne répond que si tu le souhaites...) : en mettant le curseur sur ton pseudo, j'ai vu apparaître le nom Saïas. Or, je me souviens que Tenenbaum a eu, il y a quelques années, un Eric Saïas en Thèse, thèse par ailleurs remarquable concernant les entiers friables (difficile sujet impliquant, entre autres, la fonction de Dickman !...)...Est-ce une coïncidence ?

Borde.

bob26

Aaarrrggghhhhhhh, démasqué! Oui c'est bien moi (mais il ne faut pas mettre le trema, meme si c'est naturel de le mettre)

Pour ma part depuis trois semaines que je connais ce forum, j'ai pu apprécier tes connaissances approfondies en TAN! Mais excuse-moi je ne me souviens pas de toi. Peux-tu en dire un peu plus sur toi? (Bien sur comme pour moi, ne répond que si tu le souhaites)

Bob le démasqué

borde

<!--latex-->Tu ne peux pas te souvenir de moi, on n'était pas de la même année ! C'est en suivant un cours de G. Tenenbaum, avec en particulier ce chapitre sur les entiers sans grands facteurs premiers, que j'ai pu voir ton travail !
<BR>
<BR>Ce qui me permet donc de dire que ce forum compte maintenant quelqu'un de <I>vraiment</I> compétent en th. analytique des nombres (en tout cas, plus que moi !). Avec Brux, également ! ça fait plaisir...
<BR>
<BR>A bientôt,
<BR>
<BR>Borde.
<BR>
<BR>PS Excuse-moi pour le tréma...<BR>

bob29

non je ne suis pas d'accord avec toi;
quand j'ai vu passer les sujets où tu es intervenu, j'ai vu que tu connaissais le sujet, et que tu répondais beaucoup plus vite que je ne saurais le faire. Donc je n'accepte pas que tu dises que je suis plus compétent que toi en TAN. C'est probablement faux, et puis surtout on s'en fout!
D'ailleurs je ne m'estime pas spécialiste de TAN, meme si c'est vrai j'ai fait ma thèse dans ce domaine, et que j'ai peu de culture dans les autres domaines.

J'aime bien me considérer comme quelqu'un qui aime les maths! et toutes les maths!

Déjà je ne sais pas taper en TEX, c'est pas très sérieux...

Ce qu'il y a de bien justement dans un forum où on est anonyme(relativement...:)), c'est qu'il n'y a pas de "grade".
Quelqu'un pose une question, et c'est la réponse la plus pertinente qui va convaincre la personne qui pose la question, peu importe qui a répondu.
Bien sur, à force, on se fait des images des gens. Borde connait bien la TAN, Oumpapah répond avec pertinence et doigté, muaddob en tate coté algorithmique, Vianney est gentil, etc...mais on ne connait pas forcément pour autant le CV des gens. Et meme si on est curieux de le savoir, ce n'est pas ce qui compte.

Bien sûr, tu es excusé pour le tréma.

Böb

brux0

me revoilà !

pour bob (un de mes nombreux prédecesseurs donc) : merci beaucoup pour ton exposé sur la méthode de Tchebycheff, il est très instructif !

pour Borde : tu me prêtes des qualités que je n'ai malheureusement point, je ne connais que de nom l'article de Diamond et pour ce qui est de ma compétence, elle reste modeste. Question culture dans ce domaine tu me dépasses de 10 coudées.

Sinon ma thèse se divise en deux. En restant vague cela parle
1) de l'utilisation des entiers friables pour démontrer de nouvelles identités de Davenport (qui s'obtiennent formellement en échangeant des sommations faisant intervenir la première fonction de Bernoulli, son dvpt en série de Fourier et une fonction arithmétique).
2) de l'étude de la meilleure constante dans l'inégalité de Turan-Kubilius où l'on ne retient que les entiers friables.

bref beaucoup de friabilité dans tout çà.

D'ailleurs j'y retourne !

A+,

brux

bob26

pour brux:

oui c'est rigolo je suis ton grand frère...à propos notre frère ainé (P.S.) doit trainer dans les memes couloirs que toi, à l'occasion transmets lui mes amitiés.

donc je vois que tu fais (aussi) beaucoup dans le friable; à l'occasion tu peux passer faire un tour sur le fil "chaîne d'entiers", il y a aussi là beaucoup d'entiers friables de manière sous-jacente. Mais surtout ne le dis pas, car il faut laisser la pensée de muaddob s'exprimer sans a priori! Il sera bien temps par la suite de traduire sa pensée avec des epsilons, des deltas et autres entiers friables...

bob

borde

...En tout cas, et quoiqu'on en dise, on arrive à se faire, comme le dit Bob, une idée presque correcte des intervenants de ce forum...Même si on "se fout" de telle ou telle spécialité d'untel ou untel, disons que, maintenant, je me sens plus rassuré !

Pour Brux : je n'aurais que deux mots : Bon courage !!!

Borde.

PS c'est vrai qu'il est gentil, Vianney...