16/03/2016

A-t-on découvert une loi ordonnant les nombres premiers?

premiers.jpgDepuis quelques jours, la communauté mathématique est en ébullition. Deux chercheurs de l’université de Stanford, en Californie – Kannan Soundararajan et Robert Lemke Oliver –, aidés d’énormes processeurs, ont découvert une propriété inédite concernant les nombres premiers (représentés ci-dessus dans un graphique circulaire), qui pour rappel, ne sont divisibles que par eux-mêmes et par 1. Le pire, c’est que cette découverte est d’une simplicité affolante, au point de se demander pourquoi personne n’y a songé avant. Elle consiste à observer les chiffres terminant les nombres premiers. Ceux-ci ne peuvent en effet se terminer que par 1, 3, 7 ou 9. Pour des raisons qu’il n’est nul besoin de démontrer, une terminaison par 2, 4, 6 ou 8 est exclue – tous les nombres de cette forme étant des multiples de 2. Raisonnement identique pour 5 ou 0 et les multiples de 5. Restent donc ces quatre chiffres, seule possibilité de terminaison pour un candidat à la primalité : 1, 3, 7 et 9. Nos deux chercheurs ont donc observé tous les nombres premiers jusqu’à un milliard et ont remarqué que la fréquence d’apparition de certaines terminaisons après d’autres n’était pas équiprobable. Prenons l’exemple d’un nombre premier se terminant par 1. En toute logique, la probabilité que le premier suivant, son successeur, se termine par 1, 3, 7 ou 9 devrait être la même. Or non, justement. Il n’en est rien. Ainsi, un premier se finissant par 1 n’a que 18% de chances d’être suivi par un premier de même forme. En revanche, il y a 30% de chances qu’il soit suivi par un premier se terminant par 3 ou 7. Et 22% par un premier se terminant par le chiffre 9. Et ainsi de suite.

Le problème, c’est que ces écarts probabilistes ne sont pas minimes. Ils sont importants, conséquents. Suffisamment en tout cas pour poser question et surtout remettre en cause l’ordre a priori aléatoire de l’apparition des premiers dans la suite des entiers. D’autant plus que l’écart se creuse encore plus lorsqu’on débute la chaîne par un premier se terminant par 9. Il a alors 65% de chances supplémentaires d’être suivi par un premier se terminant par 1 que par un autre se terminant par 9. La logique voudrait que toutes ces probabilités s’équilibrent, comme je l’ai dit avant. C’est loin d’être le cas, ce qui laisse supposer l’existence d’une loi cachée ordonnant la succession des nombres premiers et leur apparition selon un critère moins aléatoire qu’on le pensait. A moins de redéfinir la notion d’aléatoire, autrement dit de l’élargir. Nous en sommes loin.

Enfin, pour réfuter cette découverte, on pourrait affirmer que ces fréquences d’apparitions ne sont pas si illogiques lorsqu’on observe tous les nombres, premiers ou pas, se terminant par 1, 3, 7 ou 9. Prenons l’exemple de la chaîne 41, 43, 47 et 49. 41 est premier. Il est suivi par 43 (ce sont en l’occurrence des jumeaux), puis par 47. La probabilité qu’il soit suivi par un premier se terminant à son tour par 1 est donc plus faible que les autres. C’est empirique et imparable, et valable pour n’importe quelle chaîne analogue. Sauf que les deux chercheurs de Stanford (photo ci-dessous) ont envisagé ce cas de figure (raisonnement) et constaté qu’il ne tenait pas la route par rapport à la magnitude des biais découlant de leur observation des nombres dans d’autres bases (exemple en base 3, où tous les nombres se terminent par 1 ou 2). En d’autres termes, les mathématiciens ont du pain sur la planche pour plusieurs décennies.

stanford.jpg

18:32 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (4) | |  Facebook | | | |

21/01/2016

Découverte d'un nouveau nombre premier de Mersenne: qui dit mieux?

mersenne.jpgEn 1949, ce tank préhistorique traquait déjà les nombres premiers de Mersenne. En a–t-il trouvé ? Pas vraiment, et vu leur rareté, ce n’est guère étonnant. Mais l’algorithme nécessaire pour cette recherche fonctionnait parfaitement. On va un peu plus vite aujourd’hui, mais il a quand même fallu 31 jours à différents ordinateurs pour valider la découverte, ce 7 janvier, d’un nouveau nombre de Mersenne, qui est aussi désormais le plus grand nombre premier connu. Il s’agit de 274207281 – 1. Il est composé de 22 millions 338 618 chiffres. Il s’agit du 49e premier de Mersenne trouvé à ce jour (un classement provisoire, rien n’indique en effet qu’il n’en existe pas de plus petits qui n’aient pas encore été découverts). Et même si les grands premiers s’avèrent utiles en cryptographie, celui-ci est trop énorme pour avoir une quelconque utilité. Jusqu’alors, le plus grand premier de Mersenne, découvert en janvier 2013, totalisait 17 millions de chiffres et des poussières.

Rappelons qu’un premier de Mersenne est un nombre de la forme 2p – 1 dans lequel p est lui aussi premier. C’est le scientifique français Marin Mersenne (1588 – 1648, photo) Marin_mersenne.jpgqui fut le premier à en fournir une liste presque exacte, à quelques omissions près. Depuis, les nombres de Mersenne font l’objet de recherches approfondies en théorie des nombres. Je leur avais déjà consacré un billet détaillé qu’on peut consulter en cliquant ici. Rappelons encore que chaque premier de Mersenne engendre à son tour un nombre parfait, c’est-à-dire un nombre égal à la somme de ses diviseurs propres. En effet, selon différents travaux entrepris notamment par le Suisse Euler (1707 – 1783), on sait que si 2p – 1 est premier, alors 2p-1 x (2p – 1) est parfait. Par conséquent, 274207280 x (274207281 – 1) est le plus grand nombre parfait connu à ce jour.

Mais peut-on encore aller plus loin ? Oui, vu l’infinitude des nombres premiers. En d’autres termes, le challenge est désormais de battre ce nouveau nombre obtenu, tout comme le précédent en 2013, par le professeur Curtis Cooper de l’Université du Missouri – il avait du reste déjà battu deux records dans ce domaine en 2005 et 2006 - via son logiciel relié à la plateforme du GIMPS (Great Internet Mersenne Prime Search), installé depuis plusieurs années et pour lequel 150 000 ordinateurs sont déjà connectés. En effet, ce logiciel créé il y a vingt ans, et grâce auquel on a pu découvrir les 15 plus grands premiers de Mersenne, est téléchargeable par n’importe quels volontaires. L’objectif consiste à présent à trouver un nombre premier de plus de cent millions de chiffres. L'Electronic Frontier Foundation promet d'ailleurs une récompense de 150 000 $ à celui ou celle qui y parviendrait. Chiche ?

21:38 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (0) | |  Facebook | | | |

26/10/2015

Que cache la conjecture de Legendre?

premiers entre 1 et 1049.gifS’agissant des nombres premiers, la méthode du crible d’Eratosthène (tableau ci-dessus), que je suppose connue du lecteur, reste encore l’une des plus efficaces pour déterminer leur apparition dans la suite des entiers. Le problème, c’est qu’elle est fastidieuse, donc sans portée lorsqu’on tend vers de très grands nombres. S’agissant des nombres premiers toujours, plusieurs conjectures demeurent aujourd’hui ouvertes. C’est le cas de la conjecture de Legendre (1752 – 1833), qui stipule qu’il existe un nombre premier, pour tout entier non nul n, entre n2 et (n+1)2. L’affaire a l’air simple comme bonjour, elle n’est toujours pas résolue à l’heure actuelle, même si quelques démonstrations non encore validées ont fleuri ici et là sur des forums. Une conjecture très proche, le postulat de Bertrand (1822 – 1900), affirme qu’entre un entier et son double existe toujours un nombre premier. Mais celle-ci fut démontrée, par Tchebychev (1821 – 1894) en 1852, puis plus simplement par Ramanujan (1887 – 1920) et par Paul Erdöss (1913 – 1996) au XXe siècle.

Revenons à la conjecture de Legendre. Supposons qu’elle soit vraie. Prenons alors un nombre premier de rang m, soit pm. En ce cas, n peut s’écrire [pm] + 1. On aurait donc (les calculs qui suivent sont aisés à effectuer et déduire) :

Capture d’écran 2015-10-26 à 19.57.37.png

Par suite, on voit que :

Capture d’écran 2015-10-26 à 19.58.22.pngEt en simplifiant :

Capture d’écran 2015-10-26 à 19.59.09.pngCe qui nous fait presque aboutir à un autre problème irrésolu, l’hypothèse de Riemann, laquelle implique, pour une constante C strictement plus grande que 0, que :

Capture d’écran 2015-10-26 à 20.00.45.pngEst-ce réellement surprenant ? Non, dans la mesure où l’hypothèse de Riemann apparaît souvent lorsqu’on étudie un peu le comportement des nombres premiers quand ceux-ci tendent vers l’infini. Et ce court billet n’est destiné qu’à rappeler les liens parfois très serrés qu’entretiennent des domaines mathématiques apparemment éloignés. Pour exemple, rêvons un instant en nous rappelant le cheminement sinueux emprunté par Andrew Wiles pour démontrer le dernier théorème de Fermat, déjà évoqué dans ce blog.

20:19 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (0) | |  Facebook | | | |