David Madore's WebLog: Une conjecture « du dimanche » sur les nombres premiers

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2527 [older|newer] / Entrée #2527 [précédente|suivante]:

(jeudi)

Une conjecture « du dimanche » sur les nombres premiers

Je racontais ici que les « mathématiciens du dimanche » étaient souvent fascinés par les nombres premiers et capables de produire toutes sortes de conjectures fantaisistes à leur sujet ; et aussi, ils sont fascinés par l'écriture en base 10. Voici que je vois passer sur MathOverflow (et précédemment sur Math.StackExchange) la conjecture suivante, qui ressemble beaucoup à la caricature de la « conjecture du mathématicien du dimanche », à ceci près qu'elle conjecture que des nombres ne sont pas premiers :

Soit j≥1 un entier naturel, et Nj le nombre formé de la concaténation des écritures en base 10 des nombres (« de Mersenne » consécutifs) 2j+1−1 et 2j−1 ; c'est-à-dire : Nj = 10m·(2j+1−1) + (2j−1) où m := ⌊log(2j−1)/log(10)⌋+1 est le nombre de chiffres de l'écriture décimale de 2j−1.

(Par exemple, N₁=31 (concaténation de 3 et 1), N₂=73 (concaténation de 7 et 3), N₃=157 (concaténation de 15 et 7), N₄=3115 (concaténation de 31 et 15), etc.)

Conjecture d'Enzo Creti : si Nj≡6 (mod 7), alors Nj n'est pas premier.

(Par exemple : pour j=9, on a N9=1023512, qui est congru à 6 modulo 7, et il n'est pas premier : il vaut 19×103×523 ; pour j=10, on a N10=20471023, qui est congru à 6 modulo 7, et il n'est pas premier : il vaut 479×42737.)

(Je ne sais pas si l'auteur de cette conjecture est un mathématicien « du dimanche », je ne sais rien sur lui, mais l'énoncé, en tout cas, ressemble exactement au type de spéculations sur les nombres premiers et les écritures en base 10 dont je voulais parler.)

Ce genre de problèmes est à la fois agaçant et passablement intéressant au niveau méta.

Expérimentalement, la conjecture est vérifiée jusqu'à des valeurs passablement grandes de j (l'auteur prétend être allé jusqu'à 4×10⁵ ; moi je me suis arrêté à 10⁴) ; et de plus, elle n'est pas vide, c'est-à-dire qu'il y a effectivement une densité significative (en fait, 1 sur 9) de j pour lesquels la prémisse Nj≡6 (mod 7) est vérifiée.

(On peut accessoirement remarquer que dans chacune des autres classes de congruence de Nj modulo 7, exceptée bien sûr la classe 0, on trouve des nombres premiers. C'est la classe 6 qui semble éviter les nombres premiers. À toutes fins utiles, en distinguant les cas de congruence de m modulo 6 et de j modulo 3, on peut remarquer que 10m·(2j+1−1) + (2j−1) est congru à 6 modulo 7 lorsque soit (m≡3 (mod 6) et j≡0 (mod 3)) soit (m≡4 (mod 6) et j≡1 (mod 3)).)

Pourtant, je pense que n'importe quel théoricien des nombres sera d'accord avec moi pour dire qu'il ne croit pas une seule seconde à une telle conjecture. Pourquoi ?

D'abord, on se rappelle que le théorème des nombres premiers peut s'interpréter en disant que la « probabilité d'être premier » empirique d'un entier x tiré au hasard vaut environ 1/log(x) ; ou si le nombre est impair par construction, disons plutôt 2/log(x). En l'occurrence, on a log(Nj) = 2·log(2)·j + O(1), si bien que Nj a empiriquement une « probabilité d'être premier » qui décroît comme une fonction harmonique de j (quelque chose comme 1/(log(2)·j), en tenant compte du fait qu'il est forcément impair). Or la série harmonique diverge, donc il n'est pas vraisemblable que les Nj échouent tous à être premiers « par hasard ». En revanche, comme la série harmonique diverge très lentement (logarithmiquement), cela veut bien dire qu'il peut être nécessaire de pousser très très loin pour trouver un contre-exemple, donc avoir vérifié 10⁴ ou 10⁵ valeurs ne vaut pas grand-chose, et il n'est pas du tout invraisemblable que 10⁴ ou 10⁵ valeurs échouent toutes à être premières « par hasard » (expliquant ainsi la constatation expérimentale).

Il est donc invraisemblable que la conjecture soit vraie « par hasard », mais vraisemblable qu'elle le paraisse quand même jusqu'à 10⁴ ou 10⁵. Maintenant, se peut-il que la conjecture soit vraie autrement que « par hasard » ? Cela voudrait dire qu'il y aurait une « raison » expliquant une factorisation de 10m·(2j+1−1) + (2j−1) à tous les coups (par exemple une identité algébrique, ou une conguence à 0 qui vaut à tous les coups, enfin, une « raison » qui fait qu'il n'est jamais premier). Or, si on met de côté la donnée que m est le nombre de chiffres décimaux de 2j−1, ce n'est pas vrai que 10m·(2j+1−1) + (2j−1) n'est jamais premier. En effet, en changeant un petit peu m, j'ai le contre-exemple de 1070·(2230−1) + (2229−1) (où le nombre 2229−1 a 69 chiffres décimaux, j'ai inséré juste un 0 de plus dans la concaténation) : ce nombre est bien congru à 6 modulo 7, et il est premier (il a 140 chiffres, alors vous m'épargnerez de l'écrire complètement). Bref, si la conjecture était vraie autrement que par hasard, il faudrait avoir une factorisation de 10m·(2j+1−1) + (2j−1) qui dépende du fait que m est précisément le nombre de chiffres décimaux de 2j−1, et ça, ça semble complètement abracadabrant. (Tout ce que je raconte est complètement empirique, bien sûr, je n'ai pas de contre-exemple à la conjecture énoncée plus haut, mais j'explique pourquoi je n'y crois pas.)

Bref, je suis complètement convaincu qu'il y a un contre-exemple, et que ce contre-exemple a un j très grand (donc un Nj gigantesque), et ce n'est pas très surprenant qu'il soit difficile à trouver. Pour être un peu plus précis dans la quantification de la vraisemblance, numériquement, le produit des 1−(2/log(Nj)) (i.e., leur probabilité empirique de ne pas être premiers, le 2 étant là parce qu'ils sont impairs) parcourant ceux des Nj qui sont congrus à 6 modulo 7 vaut environ 0.25 pour j allant jusqu'à 10⁴, c'est-à-dire qu'il y avait a priori environ 25% de chances pour qu'aucun de ces nombres ne soit premier compte tenu de leurs tailles (et du fait qu'ils sont impairs) ; si on monte jusqu'à 4×10⁵, cela doit tomber à environ 18%. Bref, ce n'est pas du tout invraisemblable que la conjecture soit vraie jusqu'à ce point-là « par hasard ». Il suffit qu'il y ait une dizaine de mathématiciens du dimanche qui essaient des conjectures de ce genre, et il y en aura bien un qui tombera sur une qui marche sur toutes les valeurs que sa patience lui permettra de tester ; en fait, il suffit même qu'un seul mathématicien du dimanche ait testé la restriction des Nj à suffisamment de classes de congruence modulo des petits nombres pour tomber sur une qui semble ne contenir que des nombres composés.

Il n'est cependant pas exclu à mes yeux qu'il y ait une « raison » un peu plus précise que le hasard pour laquelle la conjecture soit vraie pour des « assez petites » valeurs de j, et c'est un problème possiblement intéressant. Il est par exemple possible que plein de cas de congruence de j et de m excluent la primalité. (Un exemple idiot est que si j est congru à 0 modulo 4, sans aucune discussion sur m, alors Nj est multiple de 5 — parce que 2j−1 l'est — et donc Nj n'est certainement pas premier ; donc déjà il n'y a plus que les quatre cinquièmes des j qui jouent vraiment, et cela contribue à rendre encore moins invraisemblable que la conjecture soit vraie « par hasard » pour des petites valeurs de j. Mais il y a peut-être des choses plus intelligentes à dire.)

Il y a notamment une chose qu'on peut voir, c'est que m := ⌊log(2j−1)/log(10)⌋+1 (le nombre de chiffres décimaux de 2j−1) vaut en fait ⌊j·ξ⌋+1 où ξ := log(2)/log(10) ≈ 0.301. Les réduites du développement en fraction continue de ξ sont 1/3, 3/10, 28/93, 59/196, etc. Si je remplace m=⌊j·ξ⌋+1 par m=⌊j·x⌋+1 où x est une de ces réduites, j'obtiens d'autres suites de nombres Nj (dépendant de x que j'omets abusivement dans la notation), à savoir Nj := 10(⌊j·x⌋+1)·(2j+1−1) + (2j−1), qui coïncident avec Nj au début (et d'autant plus loin que la réduite est bonne), et je peux poser la question de la conjecture analogue pour ces suites-là. Pour x=1/3, la conjecture sur les N′ ne vaut pas, car pour j=330, le nombre N330 = 10111·(2331−1) + (2330−1) est congru à 6 modulo 7 et est premier ; pour x=3/10, la conjecture sur les N′ ne vaut pas non plus, car pour j=849, le nombre N849 = 10255·(2850−1) + (2849−1) est congru à 6 modulo 7 et est premier. Mais pour x=28/93 (autrement dit, avec Nj := 10(⌊j·28/93⌋+1)·(2j+1−1) + (2j−1)), je n'ai pas trouvé de contre-exemple : au moins jusqu'à j=10⁴, les Nj qui sont congrus à 6 modulo 7 ne sont jamais premiers. C'est déjà moins invraisembable d'imaginer que tous ces Nj-là soient premiers que pour les Nj de la conjecture de départ : on peut tout à fait imaginer qu'il y ait une distinction de quelque chose comme 93 cas selon la valeur de j qui permette, dans chacun des cas (ou simplement dans un grand nombre de ces cas, diminuant d'autant le hasard !), de montrer que Nj serait divisible par quelque chose. Du coup, si Nj n'est jamais premier, cela expliquerait que plein de petites valeurs de Nj soient composées, et il est encore moins surprenant qu'ensuite on tombe par hasard sur des nombres composés.

Mise à jour (avant publication) : bon, en fait, pour j=14058, le nombre N14058 = 104233·(214059−1) + (214058−1) est congru à 6 modulo 7 et semble être premier (en tout cas il passe des tests de pseudo-primalité), donc mon explication n'est pas la bonne, mais je la laisse parce qu'on voit que ce genre de choses est tout à fait imaginable.

Laissant de côté la question mathématique proprement dite, il reste la question de savoir comment un mathématicien (au hasard, féru de vulgarisation) doit réagir face à ce genre de conjectures. C'est toujours un peu délicat d'expliquer je n'y crois pas du tout malgré vos constatations expérimentales, et même si on peut expliquer tout ce que je viens d'expliquer sur les probabilités, il reste quand même un certain acte de foi, quand je dis qu'il est « complètement abracadabrant » qu'il y ait un phénomène de ce genre sur les nombres premiers qui fasse intervenir de façon cruciale le nombre de chiffres décimaux du nombre 2j−1 (même si on le revoit comme ⌊j·ξ⌋+1 avec ξ = log(2)/log(10)).

↑Entry #2527 [older|newer] / ↑Entrée #2527 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées