Démonstration de la conjecture de Legendre

Bonjour Rescassol.

Fais Gaffe ! C'est un truc de pickpocket. Pendant que tu cherches, un comparse te fait les fouilles.

e.v.

On ne peut pas poster de pdf depuis quelques mois suite à des problèmes techniques, il faut les déposer sur un site de partage de fichiers : voir ici.

Il te reste la possibilité d'up-loader ton .pdf quelque part et de nous mettre un lien

Le bon lien est : celui-ci.

J'ai suivi le lien donné par GreinGre.

Le texte est très clair. J'ai survolé la preuve du lemme sans voir de preuve de la majoration (l'espace semble occupé par une minoration). Or c'est la majoration qui est utilisée ensuite. J'ai peut-être lu trop vite. Numériquement j'ai vérifié que ça marchait jusqu'au nombre premier 17 :-).

La conclusion à partir de ce lemme est très courte. J'ai scanné rapidement en ne voyant que des typos mais il faudrait regarder à tête plus reposée que la mienne en ce moment.

En tout cas je vous invite à regarder, la démarche est honnête, c'est bien expliqué et c'est pas long.

S'il y a trop de nombres premiers dans l'intervalle $[2,2\times 3\times...\times p_n]$ cela gêne à la constitution d'une suite de nombres consécutifs adéquate. Ce qui me fait penser que si un tel contre-exemple existe, il ne va pas se trouver dans les cas où la valeur de $p_n$ est petite.

Flyan:

Donne un exemple précis avec chiffres à l'appui pour que je te comprenne. B-)-

si tu rajoutes une constante à tous les termes d'une liste de longueur, cela n'agrandit pas la longueur de cette liste.

Essaie avec $2\times 3$,$2\times 3\times 5$ et $2\times 3\times 5\times 7$
pour te rendre compte de la difficulté de trouver un contre-exemple (s'il en existe un).

@rlabrie

Je détaille ce que j'ai dit dans mon premier message. Pour un entier $i \ge 2$ appelons $i-$suite une suite d'entiers consécutifs telle que chacun des entiers de la suite est divisible par $p_1=2$ ou par $p_2=3$ ou ... ou par $p_i$.

Il y a deux résultats :
1) Pour tout entier $i \ge 2$, il n'existe pas de $i-$suite de longueur au moins $2p_{i-1}$.
2) Pour tout entier $i \ge 2$, il existe une $i-$suite de longueur $2p_{i-1}-1$.

Si on combine ces deux résultats, on obtient :
Lemme. Pour tout entier $i \ge 2$, la plus longue $i-$suite est de longueur $2p_{i-1}-1$.

Il me semble que tu ne montres que 2). Il me semble qu'à la fin tu n'utilises par contre que 1). Autrement dit tu ne montres pas ce que tu utilises. Ce n'est qu'une impression suite à une lecture rapide, je me trompe peut-être. Un avis ?

@H :
Je n'avais pas lu ton message lorsque j'ai rédigé le mien. Il me semble que R. Labrie estime avoir prouvé 1) et 2) à la fois. Mais je me trompe peut-être, je n'ai pas lu en détail.

Fin de partie écrivait:

---

> Que la démonstration de son lemme soit correcte
> ou non, cela ne signifie pas pour autant que le
> lemme soit vrai ou qu'il soit faux.

C'est évident. À qui t'adresses-tu ?

Quelques remarques :

- On a vérifié ci-dessus $L_7 = 9 = 2 \times 5 - 1$. R. Labrie donne comme exemple la suite $[\![212,220]\!]$. La première suite est $[\![200,208]\!]$. (il y a aussi simplement $[\![2, 10]\!]$, si on n'exige pas le caractère composé mais qu'on se contente de "multiple de $2, 3, 5$ ou $7$").

- $L_{11} = 13 = 2 \times 7 - 1$ est facile à vérifier, de la même manière que ci-dessus. Comme suite de longueur $13$, on trouve $[\![114, 125]\!]$.

Ca se complique à partir de $13$. Néanmoins :
S'il existe une suite $x+1, \ldots, x+L$ de nombres tous multiples d'un nombre premier $\leq p$, alors, en posant $\Pi = 2 \times 3 \times 5 \times \ldots \times p$, la suite $(x- \Pi)+1, \ldots, (x - \Pi) + L$ est encore formée de multiples de ces nombres premiers. Il existe donc une telle suite, vérifiant en outre $x < \Pi$. Pour prouver $L_p < L$, il suffit donc d'examiner les suites de $L$ entiers consécutifs dont le premier terme est $<\Pi$, et de vérifier qu'elles ne conviennent pas (ie l'un des termes n'a pas de facteur premier $\leq p$).

Ceci fournit les outils nécessaires pour calculer, pour $p$ pas trop grand bien sûr, la valeur de $L_p$.

J'ai effectivement vérifié :
- $L_{13} = 21 = 2\times 11 -1$ (suite de longueur $21$ : $[\![9940, 9960]\!]$).

- $L_{17} = 25 = 2\times 13-1$ (suite de longueur $25$ : $[\![217128, 217152]\!]$).

- $L_{19} = 33 = 2\times 17-1$ (suite de longueur $33$ : $[\![60044, 60076]\!]$.

Malheureusement :

- $L_{23} = 39 > 2 \times 19 - 1$ (suite de longueur $39$: $[\![20332472, 20332510]\!]$)

Ce qui invalide l'affirmation. Sauf erreur, bien sûr.

[Corrigé selon tes indications. AD, jacquot]

Effectivement il y a, pour 2,3,5,7,11,13,19,23 des suites d'entiers consécutifs "longues" vérifiant la propriété voulue, entre 1 et 2*3*5*7*11*13*19*23
[20332472, 20332510] de longueur 39
[24686822, 24686860] de longueur 39

[29609562, 29609598] de longueur 37

[36068192, 36068230] de longueur 39
[65767862, 65767900] de longueur 39
[82370090, 82370128] de longueur 39
[97689752, 97689790] de longueur 39
et leurs "complémentaires" : si on a une suite, alors en remplaçant chaque terme x de la suite par 2*3*5*7*11*13*19*23-x on obtient une autre suite correcte.

Amusant : il y a une suite maximale (i.e. ne pouvant pas être prolongée) de longueur 37, comme prévu.

J'ai travaillé aussi un peu.

Je me doutais bien que le nombre $20332472$ n'avait pas été trouvé par hasard et j'ai voulu déterminer le plus petit nombre entier $a$ et le plus petit nombre premier $p_n$ dont l'intervalle $[a,b]$ contient plus de $2p_{n-1}-1$ nombres qui sont divisibles par l'un ou plusieurs des nombres premiers $2,3,...p_n$ et tels que ni $a$, ni $b$ ne le soient.

Il n'y a aucun tel intervalle pour $p<23$ mais pour $p=23$ en effet, il existe un tel intervalle et c'est l'intervalle déjà signalé par Yalta.

Un petit script PARI GP pour faire cette recherche.

D=[2,3,5,7,11,13,17,19,23];

dtest(m,n)=
{
   local(i);
   for(i=1,n,if(m %(D[ i])==0,return(1)));
   return(0); 
}

p(n)=
{
   local(i,t=1);
   for(i=1,n,t=t*prime(i));
   return(t);
}

taille(a,b)={return(b-a-1)};

findit()=
{
   for(n=2,9,print("n=",n);l=p(n);m=2*prime(n-1)-1;a=1;for(i=1,l+1,if(dtest(i,n)==0,if(taille(a,i)>m,print(a));a=i)))
}

L'algorithme est simple pour un $n$ fixé on calcule le produit $p(n)$ des $n$ premiers nombres premiers
et dans l'intervalle $[1,p(n)+1]$ on cherche tous les entiers qui ne sont divisibles par aucuns des nombres premiers $2,3,...,p_n$.
L'intervalle entre deux tels nombres (bornes non comprises) est composé seulement de nombres qui sont divisibles par au moins l'un des nombres premiers: $2,3,...,p_n$. Il ne reste plus qu'à vérifier si cet intervalle est suffisant large.

PS:
Je n'arrive pas à faire apparaitre dans le code, l'indice du tableau D, le % semble être le problème.

J'ai amélioré un peu mon code.
Il est inutile de tester les nombres pairs. B-)-
Pour que les crochets ne disparaissent pas, j'en ai fait précéder du symbole \ [voir commentaire ci-dessous. AD]
Tout cela reste perfectible.

D=[2,3,5,7,11,13,17,19,23];

dtest(m,n)=
{
local(i);
for(i=1,n,if(m%(D[ i] )==0,return(1)));
return(0); 
}

p(n)=
{
local(i,t=1);
for(i=1,n,t=t*prime(i));
return(t);
}

taille(a,b)={return(b-a-1)};

findit()=
{
for(n=2,9,print("n=",n);l=p(n);m=2*prime(n-1)-1;a=1;forstep(i=1,l+1,2,if(dtest(i,n)==0,if(taille(a,i)>m,print(a));a=i)))
}

[En fait il fait mettre un ' ' entre '[' et 'i', sinon l'afficheur l’interprète comme une commande BBcode de mise en italique, la commande disparait et tout le reste du message passe en italique. AD]

Mon ordinateur vient de rendre son verdict : on a bien $L_{31} = 57$, et il n'y a modulo $\Pi = 2 \times \ldots\times 31$ et à symétrie près ($x \mapsto -x$), qu'une seule suite de longueur maximale.

Sauf erreur de programmation, bien entendu.

Le fait que la formule énoncée par R. Labri soit valable pour tous les nombres premiers inférieurs à $39$ à une seule exception près interpelle. Sa construction fonctionne au moins au départ et semble fournir un minorant correct de $L_p$. Il est possible que ce soit spécifique aux petits nombres premiers (c'est mon sentiment). Mais je n'exclus pas que ce soit valable en toute généralité, voire même que sa construction donne généralement une suite maximale, des suites de longueur strictement plus grande n'étant alors que des "accidents".

Aussi aimerais-je bien avoir un retour de sa part en ce qui concerne les critiques émises ci-dessus (concernant le bas de la page 5). Est-ce moi qui ne comprends pas ?

Non, je n'ai pas encore compris...
Mais il me semble que c'est moi qui suis long à la détente car je viens de tester ta construction pour le 60ième nombre premier, à savoir $281$, qui donne la plage $[\![x-276, x + 276]\!]$, où
\begin{eqnarray*}x &=& 241146501369956321974417042629386572823550674824450204744\\&&63365114831989807555629038723413593660291491589372456573710,
\end{eqnarray*}
et effectivement, il s'agit de multiples des nombres premiers inférieurs à $281$.

Je vais donc tenter de comprendre avec un peu plus de conviction !

J'ai même vérifié avec beaucoup plus gros... Je me sens tout bête, ça doit être évident, mais je ne vois pas.

Bon, formalisons ton procédé. Ce que tu affirmes, c'est que si $x$ est un entier tel que
\[\begin{array}{l}
x \equiv 0\ (p_k),\ \mathrm{pour}\ k \leq n-2\\
x \equiv 1\ (p_{n-1})\\
x \equiv -1\ (p_n)
\end{array}
\]
alors, chaque entier de $[\![ x -(p_{n-1} -1), x +(p_{n-1} -1)]\!]$ est un multiple d'un des $p_1, \ldots, p_n$.

Tu le prouves par récurrence. On suppose l'énoncé vrai au rang $n$. Soit $y$ tel que
\[\begin{array}{l}
y \equiv 0\ [p_k]\ \mathrm{pour}\ k \leq n-1\\
y \equiv 1\ [p_{n}]\\
y \equiv -1\ [p_{n+1}]
\end{array}
\]

Soit $z \in [\![ -(p_n -1), (p_n -1)]\!]$. Il s'agit de montrer que $x + z$ est multiple de l'un des $p_k$, $k \leq n+1$.
Si $-p_{n-1} \leq z \leq p_{n-1}$, c'est facile en utilisant l'hypothèse de récurrence. C'est immédiat aussi pour $z = p_n-1$.
Mais si $z \in ]\!] p_{n-1}, (p_n -1)[\![$ par exemple, je ne vois pas pourquoi c'est vrai.

Bonjour rlabrie,

Oui, c'était une coquille, c'est de $y+z$ dont il s'agit, bien évidemment. Je te remercie pour ta réponse, mais elle n'est pas sastifaisante. Un exemple, même s'il peut aider à appréhender une preuve, ne constitue pas en lui-même une preuve: tu n'argumentes pas, tu dis simplement "regarde cet exemple, ça marche !".

Et, au final, une démonstration directe (sans récurrence) est bien plus rapide...

Théorème de Labrie
Soit $x$ un entier tel que
\[\begin{array}{l}
x \equiv 0\ [p_k],\ \mathrm{pour}\ k \leq n-2\\
x \equiv 1\ [p_{n-1}]\\
x \equiv -1\ [p_n]
\end{array}
\]
alors, chaque entier de $[\![ x -(p_{n-1} -1), x+(p_{n-1} -1)]\!]$ est un multiple d'un des $p_1,\ldots, p_n$.

Démonstration
Soit $z \in [\![ -(p_{n-1} -1), p_{n-1} -1]\!]$. Montrons que $x+z$ est multiple de l'un des $p_k$, $k \leq n$.

Si $z=1$, alors $x + z \equiv x + 1 \equiv 0\ [p_n]$.

Si $z = -1$ alors $x+z \equiv x-1 \equiv 0\ [p_{n-1}]$

Sinon, il existe $k \leq n-2$ tel que $p_k$ divise $z$ et $x+z$ est un multiple de $p_k$.
cqfd

Corollaire
Avec les notations de R. Labrie, on a \[L_{p_n} \geq 2p_{n-1} -1\]