Nous allons voir qu'il est parfois utile d'utiliser les probabilités pour répondre à certaines questions difficiles, même quand celles-ci portent sur les entiers naturels.
Nous allons nous intéresser à deux théorèmes principaux de cette théorie, dont les fondateurs sont Paul Erdös et Mark Kac :
le théorème de Hardy-Ramanujan de 1917
et
le théorème de Erdös-Kac de 1939.
EN MOYENNE, COMBIEN DE DIVISEURS ADMET UN ENTIER ?
D'après le théorème fondamental de l'arithmétique, tout entier strictement positif peut être écrit comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs.
Par exemple : \(6 936 = 2^3 × 3 × 17^2\) et il n'existe aucune autre factorisation sous forme de produits de nombres premiers, excepté par réarrangement des facteurs ci-dessus.
Notons \(d(n)\) le nombre de diviseurs d'un entier naturel non nul \(n\).
Si \(n=7 875\) : \(n=3^{\color{red}{2}} \times 5^{\color{red}{3}} \times 7^{\color{red}{1}}\) donc \(d(n)=( {\color{red}{2}} +1)( {\color{red}{3}} +1)( {\color{red}{1}} +1)=24\).
Les 24 diviseurs de \(7 875\) sont en effet les suivants :
\[\begin{array}{cc}
1 & 7 875 \\
3 & 2 625 \\
5 & 1 575 \\
7 & 1 125 \\
9 & 875 \\
15 & 525 \\
21 & 375 \\
25 & 315 \\
35 & 225 \\
45 & 175 \\
63 & 125 \\
75 & 105 \\
\end{array}\]
Plus généralement, si la décomposition de \(n\) est \(\displaystyle \prod_{i=1}^r p_i^{k_i}\) alors \(\displaystyle d(n)=\prod_{i=1}^r (k_i+1)\).
On sait donc, si l'on sait décomposer un entier, calculer le nombre de ses diviseurs.
Voici des représentations graphiques de d(n) :
Signalons quelques records visibles sur ces graphiques :
- les nombres \(83 160\) et \(98 280\), qui ont 128 diviseurs !
Leurs décompostions sont : \(83 160 = 2^3 \times 3^3 \times 5 \times 7 \times 11\) et \(98 280 = 2^3 \times 3^3 \times 5 \times 7 \times 13\) ;
- les nombres \(55 440\), \(65 520\), \(75 600\), \(85 680\), \(90 720\), \(92 400\) et \(95 760\) ont 120 diviseurs.
Il est également remarquable de constater que près de 46% des entiers inférieurs à 100 000 ont 4 ou 8 diviseurs (voir graphique ci-dessous).
Nous savons donc, si l'on sait décomposer un entier, calculer le nombre de ses diviseurs...
MAIS... Il est extrêment difficile, même aujourd'hui avec les moyens informatiques dont on dispose, de décomposer un grand entier (au moins de l'ordre de 100 chiffres) en facteurs premiers (c'est d'ailleurs grâce à cela que le système RSA, qui permet entre autres de crypter les transactions bancaires, est jugé sûr) ! Par conséquent, plutôt que de vouloir à tout prix une valeur exacte, les mathématiciens essaient d'obtenir une valeur approchée de ce nombre ou d'une valeur moyenne... C'est mieux que rien.
Plus précisément, on peut montrer que : \(\dfrac{d(1)+d(2)+d(3)+...+d(n)}{n} \sim \ln n\).
Autrement dit :
les entiers naturels non nuls inférieurs à \(n\) ont, en moyenne, environ \(\ln n\) diviseurs
(cette approximation étant d'autant plus précise que \(n\) est grand).
| On dit qu'en ordre moyen, le nombre de diviseurs d'un entier compris entre 1 et \(n\) est \(\ln n\). |
Remarque : \(\dfrac{d(1)+d(2)+d(3)+...+d(100 000)}{100 000} = \dfrac{1 166 750}{100 000} = 11,6675\)
donc en moyenne ("la vraie"), le nombre de diviseurs d'un entier compris entre 1 et \(100 000\) est environ \(\textbf{11,7}\)
alors que l'ordre moyen est \(\bf \ln(100 000) \approx 11,51\). Approximation remarquable !
EN MOYENNE, COMBIEN DE FACTEURS PREMIERS ADMET UN ENTIER ?
On note \(\omega(n)\) le nombre de facteurs premiers distincts d'un entier naturel non nul \(n\).
Par exemple, \(\omega(7 875) = 3\), puisque \(7 875=3^{2} \times 5^{3} \times 7\).
Godfrey Harold Hardy (1877-1947) et Srinivâsa Aiyangâr Râmânujan (1887-1920)
mathématiciens britannique (Hardy) et indien (Ramanujan)
Hardy et Ramanujan ont montré en 1917 que :
\(\dfrac{\omega(1)+\omega(2)+\omega(3)+...+\omega(n)}{n} \sim \ln \ln n\).
| On dit qu'en ordre moyen, le nombre de facteur premiers distincts d'un entier compris entre 1 et \(n\) est \(\ln \ln n\). |
Quelques exemples :
- en ordre moyen, le nombre de facteurs premiers d'un entier inférieur à un million (\(10^6\)) est \(\ln \ln 10^6 \approx 2,63\).
- en ordre moyen, le nombre de facteurs premiers d'un entier inférieur à un milliard (\(10^9\)) est \(\ln \ln 10^9 \approx 3,03\).
- en ordre moyen, le nombre de facteurs premiers d'un entier inférieur à un milliard de milliard (\(10^{18}\)) est \(\ln \ln 10^{18} \approx 3,72\).
- en ordre moyen, le nombre de facteurs premiers d'un entier s'écrivant avec moins de 100 chiffres (inférieur à \(10^{100} -1\)) est \(\ln \ln (10^{100}-1) \approx 5,44\).
Tentons de vérifier la qualité de ces approximations avec des valeurs "accessibles" de \(n\).
Voici la répartition de \(\omega(n)\) pour quelques valeurs de \(n\), autrement dit le nombre d'entiers inférieurs à \(n\) ayant 1, 2, ..., 9 facteurs premiers distincts :
Remarque : j'ai calculé les valeurs pour \(n=2^{31}\) avec Maple, cela lui a pris 46 heures et 20 minutes !
\[\begin{array}{|c|r|r|r|r|r|}
\hline
n \rightarrow & 100 \ 000 & 1 \text{ million} & 10 \text{ millions} & 20 \text{ millions} & 50 \text{ millions} & 2^{31} \\
\hline
1 & 9\ 700 & 78\ 734 & 665\ 134 & 1\ 271\ 339 & 3\ 002\ 195 & 105\ 102\ 701 \\
2 & 33\ 759 & 288\ 726 & 2\ 536\ 838 & 4\ 899\ 326 & 11\ 724\ 908 & 430\ 406\ 227\\
3 & 38\ 844 & 379\ 720 & 3\ 642\ 766 & 7\ 187\ 515 & 17\ 643\ 224 &703\ 812\ 972\\
4 & 15\ 855 & 208\ 034 & 2\ 389\ 433 & 4\ 912\ 636 & 12\ 655\ 989 & 584\ 765\ 981\\
5 & 1\ 816 & 42\ 492 & 691\ 209 & 1\ 536\ 136 & 4\ 326\ 176 & 258\ 930\ 865\\
6 & 25 & 2\ 285 & 72\ 902 & 187\ 066 & 620\ 108 & 58\ 419\ 244\\
7 & 0 & 8 & 1\ 716 & 5\ 971 & 27\ 253 & 5\ 851\ 823\\
8 & 0 & 0 & 1 & 10 & 146 & 192\ 915\\
9 & 0 & 0 & 0 & 0 & 0 & 919\\
\hline
\end{array}\]
On trouve alors :
\[\begin{array}{|c|r|r|r|r|r|}
\hline
n \rightarrow & 100 \ 000 & 1 \text{ million} & 10 \text{ millions} & 20 \text{ millions} & 50 \text{ millions} & 2^{31} \\
\hline
\text{moyenne} & 2,6640 & 2,8537 & 3,0130 & 3,0564 & 3,1110 & 3,3081\\
\ln \ln n & 2,4435 & 2,6258 & 2,7799 & 2,8220 & 2,8751 & 3,0675\\
\text{écart} & 0,2205 & 0,2279 & 0,2331 & 0,2344 & 0,2359 & 0,2406\\
\hline
\end{array}\]
On constate que l'écart (absolu) entre la moyenne réelle et l'ordre moyen \(\ln \ln n\) augmente...
Pour remédier à ce "problème", on peut utiliser un résultat un peu plus précis qui dit que l'ordre moyen est \(\ln \ln n + M\) où \(M \approx 0,261497213\) est la constante de Meissel-Mertens (lien).
On obtient alors les approximations suivantes qui semblent meilleures (l'écart diminue) :
\[\begin{array}{|c|r|r|r|r|r|}
\hline
n \rightarrow & 100 \ 000 & 1 \text{ million} & 10 \text{ millions} & 20 \text{ millions} & 50 \text{ millions} & 2^{31} \\
\hline
\text{moyenne} & 2,6640 & 2,8537 & 3,0130 & 3,0564 & 3,1110 & 3,3081\\
\ln \ln n + M & 2,7050 & 2,8873 & 3,0414 & 3,0835 & 3,1366 & 3,3290\\
\text{écart} & 0,0410 & 0,0336 & 0,0284 & 0,0271 & 0,0256 & 0,0209\\
\hline
\end{array}\]
Nous avons donc vu qu'il est possible d'avoir une information sur la moyenne de facteurs premiers distincts d'un entier... mais cela ne nous dit rien sur la plupart des entiers !
En effet, dire qu'une classe a obtenu 12,3 de moyenne à un devoir surveillé ne donne aucune indication sur la répartition des notes : il se peut que la plupart des élèves ait eu entre 11 et 13, comme il se peut que les notes soient très dispersées entre 1 et 20.
Voilà pourquoi nous allons avoir besoin de la notion d'ordre normal.
ORDRE NORMAL
Dans la théorie des nombres, un ordre normal d'une fonction arithmétique est une fonction plus simple ou mieux comprise qui "habituellement" prend les mêmes valeurs ou approximativement proches.
En 1917, Hardy et Ramanujan publient le théorème suivant, considéré comme fondateur de la théorie probabiliste des nombres :
Théorème de Hardy-Ramanujan (1917)
On note \(\omega(n)\) le nombre de facteurs premiers distincts d'un entier naturel non nul \(n\).
Un ordre normal de \(\omega(n)\) est \(\ln \ln n\).
Autrement dit, "la plupart des entiers" \(n\) ont \(\ln \ln n\) facteurs premiers distincts.
Précisons ce que signifie "la plupart des entiers" et ce qu'est un ordre normal.
Soit \(f\) une fonction définie sur les entiers naturels.
On dit que \(g\) est un ordre normal de \(f\) si pour tout réel \(\epsilon > 0\) on a "presque partout" \[(1-\epsilon)g(n) \leqslant f(n) \leqslant (1+\epsilon)g(n)\]
Cela revient à dire que \(1-\epsilon \leqslant \dfrac{f(n)}{g(n)} \leqslant 1+\epsilon\), c'est-à-dire que \(\dfrac{f}{g}\) est, la plupart du temps, très proche de 1,
ou encore que \(f\) est souvent très proche de \(g\).
|
Une propriété vraie "presque partout" ? Soit \(P(n)\) une propriété qui dépend d'un entier naturel \(n\). c'est-à-dire si \(\displaystyle{\lim_{x \to + \infty} \frac{N(x)}{x}=1}\). Par exemple, la propriété "tous les entiers sont composés" est vraie "presque partout". Une autre définition est : \(P(n)\) est vraie presque partout si la proportion des entiers \(k\) tels que \(k \leqslant x\) |
Plus précisément, Hardy et Ramanujan ont montré que :
Théorème de Hardy-Ramanujan (1917)
Si \(\phi\) est une fonction qui tend vers \(+\infty\) lorsque \(n\) tend vers \(+\infty\),
alors \(\ln \ln n - \phi (n) \sqrt{\ln \ln n} < \omega (n) < \ln \ln n + \phi (n) \sqrt{\ln \ln n}\) presque partout.
Source : page 336 de ce document
Nous avons donc vu qu'en "moyenne" (ordre moyen), un entier \(n\) possède \(\ln \ln n\) facteurs premiers distincts, mais qu'en plus "la plupart" des entiers \(n\) possèdent ce nombre de facteurs premiers disctincts : on dit souvent que la valeur moyenne est aussi la valeur normale.
C'est tout à fait spectaculaire ! Cela signifie que, statistiquement, le nombre de facteurs premiers d'un entier \(n\) dépend uniquement de sa taille (son ordre de grandeur).
UNE EXTENSION INCROYABLE DU THÉORÈME DE HARDY-RAMANUJAN, SIGNÉE ERDÖS
Paul Erdös (1913-1996) en 1992 et Mark Kac* (1914-1984)
mathématiciens hongrois (Erdös) et américain d'origine polonaise (Kac)
* prononcer katz
Qu’y a-t-il de moins aléatoire que les nombres entiers 1,2,3,4,... ? Et pourtant, les "briques" de ses nombres que sont les nombres premiers semblent bien avoir un comportement aléatoire, comme vous allez le voir.
En 1939, Erdös rencontre Marc Kac, un mathématicien d'origine polonaise persuadé que le résultat de Hardy et Ramanujan cache en fait une loi gaussienne.
Reprenons les données de répartition de \(\omega(n)\) :
\[\begin{array}{|c|r|r|r|r|r|}
\hline
n \rightarrow & 100 \ 000 & 1 \text{ million} & 10 \text{ millions} & 20 \text{ millions} & 50 \text{ millions} & 2^{31} \\
\hline
1 & 9\ 700 & 78\ 734 & 665\ 134 & 1\ 271\ 339 & 3\ 002\ 195 & 105\ 102\ 701 \\
2 & 33\ 759 & 288\ 726 & 2\ 536\ 838 & 4\ 899\ 326 & 11\ 724\ 908 & 430\ 406\ 227\\
3 & 38\ 844 & 379\ 720 & 3\ 642\ 766 & 7\ 187\ 515 & 17\ 643\ 224 &703\ 812\ 972\\
4 & 15\ 855 & 208\ 034 & 2\ 389\ 433 & 4\ 912\ 636 & 12\ 655\ 989 & 584\ 765\ 981\\
5 & 1\ 816 & 42\ 492 & 691\ 209 & 1\ 536\ 136 & 4\ 326\ 176 & 258\ 930\ 865\\
6 & 25 & 2\ 285 & 72\ 902 & 187\ 066 & 620\ 108 & 58\ 419\ 244\\
7 & 0 & 8 & 1\ 716 & 5\ 971 & 27\ 253 & 5\ 851\ 823\\
8 & 0 & 0 & 1 & 10 & 146 & 192\ 915\\
9 & 0 & 0 & 0 & 0 & 0 & 919\\
\hline
\end{array}\]
En représentant graphiquement ces données, il est clair que la distribution de \(\omega\) prend l'allure de la fameuse courbe en cloche (voir plus bas) :
En proportion, cela devient encore plus flagrant :
En isolant la représentation pour \(n\) = 50 millions, une "courbe en cloche" apparaît clairement :
Lors d'une conférence à laquelle Erdös assiste, Kac expose les difficultés qu'il rencontre dans ses recherches (il n'était pas un spécialiste en théorie probabiliste des nombres). Au milieu de l'exposé, Erdös lève la main et indique savoir comment faire pour terminer le raisonnement.
Quelques mois plus tard, Erdös et Kac démontrent le résultat que voici :
Théorème de Erdös-Kac (1939)
La distribution des valeurs de \(\omega (x)\) pour \(1 \leqslant x \leqslant n\) tend vers une loi normale de moyenne \(\ln \ln n\) et d'écart-type \(\sqrt{\ln \ln n}\) lorsque \(n\) tend vers \(+\infty\).
Plus précisément :
Théorème de Erdös-Kac (1939)
Soit \(K_{n,t}\) le nombre d'entiers \(x\) entre 1 et \(n\) tels que \(\omega (x) \leqslant \ln \ln n+t \sqrt{\ln \ln n}\) où \(t \in \mathbb{R}\).
\[\displaystyle{\lim_{n \to +\infty} \frac{K_{n,t}}{n} = \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{t} e^{-\frac{u^2}{2}} \mathrm{d}u}\]
... on reconnaît bien la densité d'une loi normale*. Incroyable !
Sur les données associées à \(n\) = 50 millions, on peut donc tracer la courbe de la loi normale de moyenne \(ln(ln(5 \times 10^7)) \approx 2.8751\) et d'écart-type \(\sqrt{\ln \ln (5 \times 10^7)} \approx 1.6956\) :
De même avec \(n=2^{31}=2\ 147\ 483\ 648\) :
Il est alors intéressant (puisque le résultat est un résultat asymptotique : limite lorsque \(n\) tend vers \(+\infty\)) de faire de même pour chacun des histogrammes associés à \(n=100\ 000\) ; 1 million ; 10 millions ; 20 millions ; 50 millions ; \(2^{31}=2\ 147\ 483\ 648\) (histogramme vert) :
En "centrant" et en "réduisant" les données, on peut tracer la courbe de la loi normale centrée réduite :
De même pour chacun des histogrammes associés à \(n=100\ 000\) ; 1 million ; 10 millions ; 20 millions ; 50 millions ; \(2^{31}=2\ 147\ 483\ 648\) (histogramme vert) :
* Sur la loi normale : un théorème mathématique, appelé « théorème central limite » (démontré en 1809 par Pierre-Simon de Laplace) affirme que toute somme de variables aléatoires indépendantes et identiquement distribuées tend vers une variable aléatoire qui suit une loi normale (courbe de Gauss ou courbe en cloche).
Autrement dit, peu importe l'expérience, si on la répète un grand nombre de fois de manière indépendante et identique, on verra apparaître une loi normale !
Ce théorème et ses généralisations offrent une explication à l'omniprésence de la loi normale dans la nature : de nombreux phénomènes sont dus à l'addition d'un grand nombre de petites perturbations aléatoires, à la superposition de causes nombreuses, plus ou moins indépendantes, il en résulte que la loi normale les représente de manière raisonnablement efficace.
On dit qu'une loi normale intervient dans « la modélisation de nombreux phénomènes aléatoires possédant de nombreuses causes indépendantes dont les effets s'ajoutent, sans que l'une d'elles soit dominante ».
Appliquées au théorème de Erdös-Kac avec une valeur de \(n\) "assez grande", nos connaissances sur les lois normales nous permettent de dire, par exemple, qu'en choisissant au hasard un nombre s'écrivant avec moins de 100 chiffres (donc inférieur à \(10^{100}\)) :
- la probabilité qu'il admette entre 1 et 10 facteurs premiers distincts est d'environ 94,6 %
- la probabilité qu'il admette entre 1 et 3 facteurs premiers distincts est d'environ 12 %
- la probabilité qu'il admette entre 1 et 2 facteurs premiers distincts est d'environ 4,2 %
- la probabilité qu'il admette 1 facteur premier (donc qu'il soit premier) est d'environ 2,9 %
(en calculant \(p(0,5 \leqslant X \leqslant 1.5)\) où \(X\) suit une loi normale de paramètres \(\ln \ln 10^{100} \approx 5,4392\) et \(\sqrt{\ln \ln 10^{100}} \approx 1,6956\), c'est ce qu'on appelle "la correction de continuité", voir ici).
Ceci est intéressant car, contrairement à \(n=50\) millions, on ne sait pas calculer \(\omega(n)\) avec de grandes valeurs de \(n\) comme \(10^{100}\).
Le dernier résultat semble un peu surprenant, car on sait - c'est le théorème de raréfaction de Hadamard-De La Vallée Poussin, conjecturé par Gauss lorsqu'il avait 15 ans - que la quantité de nombres premiers inférieurs à \(10^{100}\) est environ égale à \(\dfrac{10^{100}}{ln 10^{100}} \approx 4,33 \times 10^{97}\), ce qui représente environ 0,43 % des entiers...
En réalité, "l'erreur" vient sans doute du fait que \(n\) n'est pas encore assez grand (bien que \(10^{100}\) soit un très très grand nombre).
En effet, A. Rényi et P. Turán (mathématiciens hongrois comme Erdös) ont montré en 1958 que :
Théorème de Rényi-Turán (1958)
L'erreur commise en approchant \(\dfrac{K_{n,t}}{n}\) par \(\dfrac{1}{\sqrt{2 \pi}} \int_{-\infty}^{t} e^{-\frac{u^2}{2}} \mathrm{d}u\) (loi normale centrée réduite) est de l'ordre de \(\dfrac{1}{\sqrt{\ln \ln n}}\).
Or, ce terme décroît extrêment lentement !
Exemples : \(\dfrac{1}{\sqrt{\ln \ln (10^{20})}} \approx 0,51\) ; \(\dfrac{1}{\sqrt{\ln \ln (10^{30})}} \approx 0,49\) ; \(\dfrac{1}{\sqrt{\ln \ln (10^{50})}} \approx 0,46\) ; \(\dfrac{1}{\sqrt{\ln \ln (10^{80})}} \approx 0,44\) ; ...
Remarque : \(10^{30}=10^{20} \times 10^{10}\) donc \(10^{30}\) est 10 milliards de fois plus grand que \(10^{20}\) !
Même si l'erreur commise sera sans doute énorme, tentons d'utiliser le théorème d'Erdös-Kac avec \(n=50\) millions : on pourra calculer les erreurs commises puisque nous disposons des valeurs réelles pour cet exemple.
En utilisant l'approximation du théorème d'Erdös-Kac, en choisissant au hasard un nombre inférieur à \(50\) millions :
- la probabilité qu'il admette entre 2 et 4 facteurs premiers distincts est d'environ 62 % avec la correction de continuité...
- la probabilité qu'il admette entre 1 et 6 facteurs premiers distincts est d'environ 90 % avec la correction de continuité...
... alors que les valeurs réelles respectives sont d'environ 84 % et 99,95 % !
Là encore, il faut être prudent : utiliser une loi continue pour approcher une loi discrète n'est pas toujours un bon choix, surtout quand le théorème utilisé est un résultat asymptotique (plus \(n\) est grand, plus la valeur approchée est "bonne").
Références :
- Paul Erdös et la vision probabiliste de l'arithmétique, article de la revue Tangente n°177 (lire en ligne)
Attention, cet article contient des erreurs et approximations, je les ai signalées. - Gérald Tenenbaum, « Paul Erdös et l’anatomie des nombres entiers », conférence du 22 février 2017
- Sur le théorème de Hardy-Ramanujan :
G. Hardy et S. Ramanujan, « The normal number of prime factors of a number n », Quarterly Journal of Mathematics, 48: 76–92 (lire en ligne) - Sur le théorème de Erdös-Kac :
- Paul Erdös et Mark Kac, « The Gaussian law of errors in the theory of additive functions », Proc. N. A. S., vol. 25,? , p. 206-207 (lire en ligne)
- Paul Erdös et Mark Kac, « On the Gaussian law of errors in the theory of additive number theoretic functions », Amer. J. Math., vol. 62,? , p. 738–742 (lire en ligne) - Gérald Tenenbaum, « Qu'est-ce qu'un entier normal ? », version du 5/11/2009 (lire en ligne)