La carte d’identité d’un nombre

Les nombres premiers sont les nombres plus grands que $2$ qui ne sont divisibles que par eux-mêmes et par $1$ : \[2,3,5,7,11,13,17,19,23, 29, 31,...\] et la liste se poursuit sans jamais s’arrêter.

Un résultat mathématique très important nous apprend que chaque nombre plus grand que $2$ est soit premier, soit peut s’obtenir en multipliant certains nombres premiers entre eux. Dans ce cadre, les mathématiciens préfèrent parler de produit plutôt que de multiplication. De plus, dans le cas où le nombre en question est premier, ils considèrent qu’il est produit de lui-même avec... rien ! En définitive, ils énoncent plus succinctement : tout nombre plus grand que $2$ est produit de nombres premiers. Par exemple,
\[\begin{aligned} {15 = 5 \times 3\\ 41 = 41 \, \text{(il est premier)} \\ 24 = 2\times 2 \times 2 \times 3\\ 57 = 3 \times 19\\ 45= 3 \times 3 \times 5 \\ 82= 2 \times 41} \end{aligned} \]
Si un nombre est grand, trouver comment l’obtenir comme produit de nombres premiers peut être long, mais c’est toujours possible : on sait le démontrer.

Il y a mieux. Prenons \[186 = 2 \times 3 \times 31.\] Y avait-il une autre manière de l’obtenir comme un produit de nombres premiers ? La réponse est non ! Certes, on peut aussi écrire
\[186 = 31 \times 2 \times 3\]
ou encore
\[ 186 = 3 \times 31 \times 2,\]
etc., mais nous conviendrons que c’est la même chose.

Plus généralement tout nombre s’obtient d’une manière et d’une seule comme produit de nombres premiers, pourvu que l’on convienne qu’on ne tient pas compte de l’ordre dans lequel on fait les multiplications. Là encore c’est quelque chose que l’on sait prouver (et ce n’est pas si évident !). Encore un point de vocabulaire, les nombres premiers qui permettent d’obtenir un nombre en effectuant des multiplications sont appelés les diviseurs premiers de ce nombre. Ainsi les diviseurs premiers de $186$ sont $2$, $3$ et $31$.

Chaque nombre possède donc une sorte de carte d’identité, la liste de ses diviseurs premiers que je noterai dans l’ordre croissant entourés de parenthèses. La carte d’identité de $186$ est donc $(2,3,31)$. Celle de $13$ est $(13)$ puisque $13$ est un nombre premier. Il est important d’insister sur le fait que dans la carte d’identité d’un nombre, chaque diviseur premier est répété autant de fois que nécessaire. Par exemple, la carte d’identité de $24$ n’est pas
\[ (2,3)\]
mais
\[(2,2,2,3).\]
Résumons : tout nombre a une seule carte d’identité (difficile de frauder dans l’univers impitoyable des nombres), aucun nombre n’a la même (sinon ce ne serait plus une carte d’identité !).

On peut se poser plein de questions sur la carte d’identité d’un nombre. Comme mentionné plus haut, si on prend un nombre très grand (disons plusieurs centaines de chiffres), un ordinateur même très puissant ne sera pas toujours en mesure de vous donner rapidement sa carte d’identité. Cependant, les mathématiciens peuvent conjecturer et parfois démontrer des phénomènes statistiques portant sur une grande collection de nombres. L’objet de cet article est précisément de décrire l’un de ces phénomènes.

Carte d’identité et parité

Nous allons nous intéresser à un phénomène de parité. Ici parité désigne tout simplement pour un nombre le fait d’être pair ou impair.
Précisément, nous allons observer la parité du nombre de diviseurs premiers apparaissant dans la carte d’identité d’un nombre. Par exemple, la carte d’identité de $36$ est $(2,2,3,3)$, elle comporte $4$ diviseurs premiers, un nombre pair donc. En revanche, la carte d’identité de $42$ est $(2,3,7)$, il y a $3$ diviseurs premiers, donc un nombre impair.

Regardons ce qu’il se passe pour les nombres pris dans l’ordre jusque $15$. Dans la première ligne, je mets le nombre, dans la deuxième sa carte d’identité. Et enfin dans la dernière ligne, j’indique si le nombre de diviseurs premiers du nombre est pair ou impair. Mais plutôt que de noter P ou I pour pair ou impair, je vais noter 0 pour pair, 1 pour impair. C’est visuellement plus agréable et cela garde une cohérence mathématique car les nombres pairs (resp. impairs) sont exactement les nombres dont le reste dans la division par $2$ vaut $0$ (resp. $1$).

Nous effectuons à présent une petite manœuvre cosmétique en oubliant la première et la deuxième ligne du tableau pour n’en conserver que la troisième.

Nous allons ensuite poursuivre cette liste en programmant un ordinateur. Nous lui demandons donc de prendre les nombres les uns après les autres jusque 1000, de déterminer leur carte d’identité et de déterminer si la parité associée correspond à 0 ou 1. Voici ce que l’on obtient.

1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1

Et la liste se poursuit indéfiniment à mesure que l’on prend plus de nombres en compte.

Question : sommes-nous sûrs de toujours rencontrer des $0$ dans cette liste infinie ? de toujours rencontrer des $1$ ?

Dans les deux cas, la réponse est oui. Pouvez-vous trouver pourquoi ?

Voici une question naturelle mais beaucoup moins simple.

Y a-t-il plus de $0$ ou plus de $1$ dans cette liste infinie de $0$ et de $1$ ?

Dans le début de la liste affichée ci-dessus, $1$ apparaît 508 fois, $0$ apparaît 492 fois, soit une proportion de 50,8 % contre 49,2 %. C’est serré. Ne nous arrêtons pas là, voyons grand, et étendons la liste en programmant l’ordinateur pour aller jusque un million ! Je n’affiche pas la liste, bien sûr, mais je vous livre le résultat : les proportions respectives de $1$ et $0$ sont maintenant de 50,0265 % et 49,9735 %. On s’est rapproché d’une parité parfaite.

Et c’est précisément ce phénomène que sont capables de prouver les mathématiciens : à mesure que l’on élargit la liste, la proportion de $0$ et $1$ converge vers une parité parfaite. [1]

Pair-Impair ou Pile-Face ?

Quittons un bref instant l’univers des nombres et de leur carte d’identité pour jouer... au jeu de Pile ou Face ! Imaginons que nous disposions d’une pièce bien équilibrée, c’est-à-dire telle que vous avez tout autant de chances pour un lancer de tomber sur pile ou sur face. On répète plusieurs fois l’opération et à chaque fois on note $1$ pour un Pile obtenu, $0$ pour un Face. Allez, je m’y colle, je lance ma pièce mille fois et j’obtiens la suite suivante.

0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0

Nous sommes d’accord, si je relance ma pièce mille fois, je vais obtenir une liste différente.
Imaginons à présent que je donne à quelqu’un dix listes obtenues en jouant à Pile ou Face, et que j’y glisse le début de la liste obtenue à partir des cartes d’identité des nombres (appelons-là liste n° 1), qui elle, ne doit rien au hasard. Va-t-il observer les onze listes et soudainement m’objecter qu’une d’entre elles ne résulte pas de lancers à Pile ou Face parce qu’il lui semble que les $0$ et les $1$ semblent suivre un motif non aléatoire ? Probablement pas.

Voici la conclusion à laquelle les mathématiciens aimeraient aboutir : établir que si la liste n° 1 ne doit rien au hasard (on dit qu’elle est déterministe) elle en a toutes les caractéristiques ! À ce stade, il faut nous demander comment évaluer si une liste infinie de $0$ et de $1$ présente ou non les attributs de l’aléatoire. Le premier test, qui paraît logique, consiste à établir que lorsqu’on agrandit la liste, les proportions respectives de $0$ et $1$ convergent vers 50 %. Cela tombe bien, nous avons vu que c’est le le cas de notre liste n° 1.

Mais ce n’est pas suffisant. Devinez-vous ce que pourrait être un deuxième critère ? Eh bien de jeter un œil aux motifs $00$, $10$, $01$, $11$. Reprenons le tout début de la liste n° 1 :

Par exemple, combien de fois y observe-ton le motif $01$ ?

Nous sommes d’accord, $3$ fois. Et les motifs $00$, $10$, $11$ apparaissent respectivement $2$, $4$ et $4$ fois. Si on élargit la liste jusqu’à obtenir mille $0$ et $1$ comme toute à l’heure, on peut faire le même décompte et je vous donne directement les arrondis des pourcentages d’apparitions :

Et voilà ce que l’on obtient si on élargit encore la liste jusque un million :

Les proportions d’apparitions de ces quatre motifs semblent converger vers 25 %. Cela semble valider notre intuition du hasard, aucun motif ne prédomine.
Seulement voilà, il ne s’agit là que d’une observation expérimentale, on ne sait pas démontrer ce phénomène de convergence. Et plus généralement on souhaiterait montrer que n’importe quel motif de $0$ et $1$, aussi long soit-il, apparaît avec la proportion attendue [2]. On aurait alors affaire à une liste qui imite (les mathématiciens disent plutôt « qui simule ») le hasard.

D’un point de vue pratique, cela n’aurait guère d’utilité car nous n’aurions ainsi produit qu’une seule liste de ce type. Or on a justement besoin d’être en mesure de créer de nombreuses suites de chiffres confidentielles les plus aléatoires possible : pensez par exemple aux clés des box internet. Pour générer ces dernières, on se tourne vers d’autres techniques mathématiques dont le but est de mettre au point ce qu’on appelle des générateurs de nombres pseudo-aléatoires.

Pour aller plus loin

Ce serait néanmoins un splendide résultat théorique d’établir qu’effectivement la liste de $0$ et $1$ obtenue à partir des diviseurs premiers des nombres simule le hasard. Disons succinctement où en est la recherche sur ce sujet. D’abord, signalons qu’il est assez simple de montrer que les motifs $01$, $00$, $10$, $11$ apparaissent tous une infinité de fois dans la liste. Mais il se pourrait très bien que l’un d’entre eux apparaisse de moins en moins souvent de sorte que sa proportion d’apparition convergerait vers 0 % à mesure que l’on étendrait la liste. Eh bien grâce à des travaux récents de Kaisa Matomaki et Maksym Radziwill, on sait que cette situation ne se produit pas. En collaboration avec Terence Tao, ils obtiennent un résultat identique pour les motifs de longueur $3$, soit $000$, $001$, $010$, $011$, $100$, $111$, $101$ et $110$. Cela peut vous paraître modeste comme avancée, mais tous les spécialiste du domaine considèrent ces résultats comme spectaculaires car le problème est jugé terriblement difficile.

Pour les motifs de longueur supérieure à $4$, on se sait rien démontrer à ma connaissance. Pas même montrer par exemple que l’on va retrouver le motif $1001$ une infinité de fois dans la liste. C’est dire le chemin qui reste à parcourir !