Pi dans la théorie de l'aléatoire

Cette page est consacrée à la place de notre constante Pi dans le domaine théorique de l'aléatoire. Dans son plan, elle est largement inspirée jusqu'à la section D de la remarquable section 10 du "Fascinant nombre Pi" de J.P. Delahaye, mais comment présenter autrement ce qui est si bien expliqué !
Cette page s'enrichira également au fil de ma collecte, l'état des lieux dans cette discipline n'est pas si simple à réaliser. Pour ma part je n'ai encore qu'une vision imparfaite et en tous les cas très incomplète de tout cela, donc n'hésitez-pas à me parler de théorèmes, exemples et définitions complémentaires que vous connaissez !
Voici les paragraphes abordés successivement, vous avez de la lecture !

A - Nombres de Liouville
B - Définir l'aléatoire

1 - Définition de "aléatoire" grâce à l'aléatoire au sens de Martin-Löf
2 - Propriétés "exceptionnelles et effectivement vérifiables"
3 - Théorie de la complexité de Kolmogorov

C - Les principales familles de l'aléatoire

1 - Nombres univers
2 - Nombres équirépartis
3 - Nombres normaux

D - Des théorèmes sur la complexité

1 - Et Pi dans tout cela ??
2 - Conjecture de Hartmanis et Stearns...
3 - Générateurs aléatoires

E - Formules BBP

1 - Hypothèse de Bailey et Crendall
2 - Notion d'attracteur fini
3 - Nombres équidistribués

Biblio

---

Pi est-il un nombre aléatoire ?

Le débat sur la caractère aléatoire du nombre Pi est plus important qu'il n'y parait. D'une part, une réponse pour ce nombre impliquerait sans doute l'apport d'une réponse pour bien d'autres constantes par les mêmes techniques. En outre, la compréhension des propriétés des nombres s'en trouverait grandement avancée.

Historiquement, les résultats d'irrationnalité et de transcendance de Pi tout d'abord découverts n'ont pas apporté de grandes révélations sur la répartition de ses décimales hormis le fait qu'elles n'étaient pas périodiques. On peut aller un tout petit peu plus loin en introduisant la notion de nombre de Liouville.

A - Nombres de Liouville

En 1851, Joseph Liouville montre que tous les nombres ne sont pas algébriques, et plus précisément que si x est irrationnel et racine d'une équation algébrique de degré n, alors il existe C>0 tel que tout rationnel p/q vérifie :

Intuitivement, cela signifie qu'un nombre irrationnel algébrique ne peut être approché de trop près par un rationnel. Un nombre irrationnel qui se laisserait approcher par des rationnels est alors transcendant.

On définit ainsi les nombres de Liouville par cette dernière propriété, c'est à dire que x est un nombre de Liouville (et donc transcendant) si pour tout n entier et C>0, il existe p, q tel que

Une propriété assez amusante est que ce résultat décide de la transcendance de certains nombres contenant beaucoup de 0. Par exemple est transcendant car grâce aux longues séquences de 0, on peut l'approcher de plus en plus finement par des rationnels. On connait aussi le nombre de Liouville défini par des 0, avec des 1 placés aux n! places.

La réciproque n'est pas vraie, c'est à dire que tous les transcendants ne sont pas des nombres de Liouville. Par exemple, les frêres Chudnovsky ont montré pour Pi que

pour q assez grand.

Ce qui implique notamment que l'on ne puisse pas trouver une infinité de fois "15n" zéros à partir du rang n, c'est à dire par exemple 15000 zéros à partir du rang 1000. C'est tout de même une contrainte très très faible ! Imaginez...
Cependant, cela montre tout de même que Pi n'est pas un nombre de Liouville et donc pas approchable de trop près par des rationnels.

A force de ne pouvoir éclaircir la nature de la répartition des décimales de Pi, l'idée qu'elles pouvaient être réparties de façon "aléatoire" a germé.

Pi n'a pourtant aucune raison d'être aléatoire puisque dans certaines représentations, Pi a une expression parfaitement déterminée. Par exemple la série d'Euler montre que dans la base mobile à pas variable , Pi a une expression très simple 2,22222... Cette propriété avait justement donné naissance à l'algorithme compte-goutte !

Si l'on regarde les fractions continues régulières, on sait aussi que celle de e est parfaitement prévisible tandis que ce n'est pas le cas pour celle de Pi. Que doit-on en conclure ?

Et en premier lieu, qu'est-ce que veut dire être aléatoire pour un nombre ?

B - Définir l'aléatoire

Pour bien comprendre l'état actuel des conjectures sur ces problèmes, il convient d'introduire quelques définitions :

B.1 - Définition de "Aléatoire"

Un nombre sera dit aléatoire si la taille du programme minimal générant n décimales du nombre est au moins de taille n. Intuitivement, cela signifie que l'on ne peut compresser l'information contenue dans ce nombre.

Plus précisément, cette approche est liée au fait que puisque la probabilité de tirer une suite précise de décimales est nulle, on ne peut facilement utiliser la théorie de la mesure. On peut par contre passer par la théorie de la calculabilité mise au point dans les années 40 par Gödel, Turing, Church et Kleene. Celle-ci indique que toutes les suites de nombres ne sont pas programmables, donc calculables par machine. A l'issue de ces travaux, d'autres menés par Kolmogorov, Solomonoff, Chaitin et Martin-Löf dans les années 60 ont précisé la définition d'un nombre aléatoire au sens de Martin-Löf comme un nombre ne possédant pas de propriété exceptionnelle que l'on puisse effectivement vérifier.

On retombe sur la théorie de la mesure en définissant une propriété exceptionnelle comme une propriété qui n'est presque sûrement pas vérifiée. Pour ne pas se faire piéger par des cas un peu spéciaux mais que l'on ne pourrait pas déceler, on rajoute la condition de vérification effective. Elle signifie que l'on peut vérifier la propriété par programme avec un risque de se tromper s'amenuisant avec le degré de vérification.

B.2 - Définition précise (et pénible !) de exceptionnelle et effectivement vérifiable

Une propriété P est exceptionnelle et effectivement vérifiable s'il existe un programme de test qui, pour tout entier n (correspondant au degré du test, en pratique un nombre f(n) de décimales), élimine certaines suites qui apparaissent satisfaire la propriété P. Le test, au niveau n, s'effectue en utilisant un nombre fini de chiffres de la suite, et est tel que les suites éliminées soient dans une proportion d'au plus 2^-n. Les suites qui sont toujours éliminées à partir d'un certain rang n doivent être exactement celles qui satisfont la propriété P.

Intuitivement, plusieurs remarques s'imposent :

• Le 2^-n assure que l'ensemble restant soit de mesure nulle

• La définition est très générale pour une propriété exceptionnelle. Car on pourrait par exemple définir la propriété exceptionnelle "être égal à Pi". Dans ce cas, Pi aurait une propriété exceptionnelle et ne serait donc pas aléatoire ! C'est dans ce cas la condition de vérification possible par programme qui sauve le tout. Cette condition va tout naturellement imposer de pouvoir vérifier en temps fini ou de lancer une boucle, bref de compresser la vérification, et c'est la base de la théorie de la complexité de Kolmogorov.

• La condition de vérification tempère donc la condition probabiliste qui se serait révélée inefficace car aboutirait à une définition vide.

Pour faire le lien avec la définition donnée au départ, on passe par la théorie de la complexité de Kolmogorov :

B.3 - Théorie de la complexité de Kolmogorov

La complexité définie au sens de Kolmogorov pour un nombre mesure la taille du programme minimal permettant d'imprimer ce nombre. Une suite de 1 a une complexité bien sûr faible tandis qu'une suite de longueur 10¹³ dont le programme servant à l'imprimer a une taille supérieure ou égale à 10¹³ a une forte complexité et est totalement incompressible...

Le théorème remarquable démontré dans les années 70 indépendamment par Schnorr, Levin et le grand Chaitin est le suivant :

Une suite infinie de "0" et de "1" est aléatoire au sens de Martin-Löf si et seulement si elle est incompressible, c'est à dire si et seulement si il existe une constante c telle que la comprexité de Kolmogorov des n premiers chiffres de la suite est toujours plus grande que n-c.

La constante c sert à éviter les problèmes avec les débuts des séquences (par exemple commençant par une centaine de 1).

Si l'on doit retenir l'idée du paragraphe précédent c'est qu'aléatoire au sens mathématique signifie incompressible, ce qui intuitivement n'est pas absurde.
Avec cette définition, Pi n'est absolument pas aléatoire, puisque le simple fait que l'on puisse l'écrire sous formes de séries permet d'écrire un programme de taille inférieure à n pour calculer n décimales (il existe notamment un programme en c comportant 158 caractères et fournissant 2400 décimales de Pi, on appelle ce genre de code des tiny-programs).
Une petite remarque complémentaire, cette définition montre aussi que les fonction random des calculateurs ne sont pas "aléatoires" au sens absolu.
De plus, les nombres aléatoires au sens de Martin-Löf sont forcément transcendants et normaux, terme que l'on va définir par la suite.
Enfin, de par sa définition avec les propriétés exceptionnelles, presque tous les nombres sont aléatoires au sens de Martin-Löf, même si ni les algébriques (d'ailleurs en nombre dénombrable) ni les nombres calculables (également en nombre dénombrables comme le nombre de programmes à cause des instructions) ne sont aléatoires !
On ne connait d'ailleurs que le seul nombre de Chaitin comme véritablement aléatoire (la probabilité qu'un ordinateur universel à programmes autodélimités s'arrête).

Si Pi n'est pas aléatoire au sens de Martin-Löf, il faut alors passer par d'autres propriétés un peu moins "aléatoires" sous peine de ne toujours rien savoir de Pi !

C - Les principales familles de nombres de l'aléatoire

C.1 - Nombre-univers

Les nombres univers sont les nombres où chaque séquence de chiffres est présente. C'est le cas si chaque chiffre a une probabilité non nulle d'être tirée dans un suite infinie de chiffres tirés au hasard.

On ne sait pas démontrer si Pi est un nombre univers. On sait en revanche que presque tous les nombres sont des nombres univers, même si il en existe une infinité non dénombrable qui ne sont pas des nombres univers.

Un exemple trivial de nombre univers est le nombre de Champernowne qui vaut 0,123456789101112131415... qui est la suite de tous les nombres entiers.

Sa propriété fascinante implique notamment que si Pi est un nombre univers, il contient en autres la version convertie en chiffres de la Bible, de sa propre biographie complète, sans compter les innombrables contenant des erreurs. On peut déjà trouver sur Internet des sites proposant de chercher sa date de naissance dans les décimales connues.

Certains nombres transcendants sont des nombres univers (nombre de Champernowne) d'autres non, par contre, on ne sait rien pour les nombres algébriques (irrationnels).

C.2 - Equirépartition

D'après la loi des grands nombres, pour une base b donnée, la fréquence des 0 dans une séquence de n chiffres tirés au hasard tend vers 1/b lorsque n tend vers l'infini.

Réciproquement, si la fréquence de chacun des b chiffres d'un nombre est 1/b alors on dit que le nombre est équiréparti (ceci pour une base b, ou bien pour toutes les bases b, la notation suivant).

C.3 - Nombre Normal

La normalité est une généralisation de l'équirépartition.

Un nombre est dit normal en base b si il est équiréparti en base b bien sûr, mais si en plus la fréquence des couples de chiffres est équirépartie, la fréquence des triplets également, etc...

Ainsi, en base 10 la fréquence du chiffre 2 doit être 1/10, celle du couple 29 doit être 1/100, celle de 356 doit être 1/1000, etc...

Un nombre normal en base b est a fortiori équiréparti en base b tandis que l'exemple 1/3=0.010101010101... en base 2 fournit un rationnel équiréparti en base 2, mais absolument pas normal en base 2. Un nombre normal en toute base est dit absolument normal.

La notion de normalité est la plus courante, c'est à dire que c'est souvent la propriété ultime que l'on cherche à démontrer pour un nombre. On suppose en effet en général pour les constantes les plus courantes (mais pas les plus triviales comme l'exemple précédent) qu'elles vérifient cette propriété. Emile Borel a d'ailleurs montré que presque tous les nombres sont absolument normaux.

On pourrait encore aborder le problème des nombres finiment définissables au moyen d'un système formel de notations et dans les axiomes ZF classiques. La défintion intuitive est assez claire et on se rend compte évidemment que Pi est finiment définissable, notamment grâce à ses développements en série infinie.

Quelques exemples

C'est bien joli tout cela, mais revenons sur terre avec quelques exemples...
Le nombre de Champernowne est normal en base 10, donc équiréparti, et c'est par définition un nombre univers comme nous l'avons vu. Il est un démenti formel aux assertions impliquant l'aléatoire à partir de la normalité, puisque ce nombre possède clairement une structure identifiable ! On ne sait pas par contre s'il est normal dans les autres bases, ce qui est assez logique vu sa construction.

Copeland et Erdös ont montré que dans une certaine base b, les nombres s'écrivant 0,u₁u₂u₃u₄... où u_n est une suite croissante d'entiers telle que à partir d'un certain rang sont normaux. Ainsi, 0.246810..., 0.510152025 (multiples de 5), 0.23571113 (suite des premiers) sont normaux.

On ne sait pas construire explicitement un nombre normal en toute base, même si le nombre de Chaitin est encore une fois normal en toute base.

D - Des théorèmes sur la complexité

D.1 - Et Pi dans tout cela ?

Eh bien le résultat très décevant et en même temps prometteur est que l'on ne sait rien... Le problème principal est que les mathématiciens ne savent pas bien comment aborder le problème car Pi se dérobe à chaque fois qu'ils pensent avoir trouvé la solution !

Comme nous l'avons dit, les résultats d'irrationnalité et de transcendance n'indiquent pas grand chose sur la répartition des décimales de Pi.

Nous avons vu que les algorithmes des Borwein alliés aux techniques modernes de programmation (FFT) permettaient de calculer Pi en temps n.log(n) linéaire ce qui est un énorme progrès par rapport à précédemment. On peut imaginer aller plus loin et l'on se trouve alors devant la ...

D.2 - Conjecture de Hartmanis et Stearns !

Tout nombre irrationnel calculable en temps linéaire (un temps n donne n décimales) est transcendant.

Il existe des résultats moins forts, par exemple celui de Loxton et Van der Poorten publié en 1988 qui indique qu'un nombre irrationnel dont les décimales sont définissables par un automate à nombre fini d'état (mémoire finie) est transcendant.

Ce n'est bien sûr pas le cas pour Pi.

Une autre approche passe par les formules BBP que l'on verra dans le paragraphe suivant.

D.3 - Générateurs aléatoires

Un résultat néanmoins tout à fait intéressant de Kannan, Lenstra et Lovasz (1986) concerne l'utilisation d'un nombre comme Pi à des fins de codage ou de générateur aléatoire.
Nous savons que 1 peut s'écrire comme la composition d'un algébrique par certaines fonctions, par exemple : Pi=2*Arcsin(1)=Arccos(-1)=-2i*Ln(i). Plus généralement, pour les fonction Arccos, Arcsin, Ln et un algébrique a, on a le résultat suivant :

Si l'on connait un nombre n assez grand de décimales de a, le degré de l'équation minimale dont il est racine, ainsi que la taille maximale de ses coefficients, on peut reconstituer en temps polynômial l'équation, et ainsi reconnaitre le nombre en question (et donc continuer à calculer ses décimales). Une conséquence importante de ce résultat est que l'on ne doit pas utiliser les décimales de ces fonctions prises en a (et donc Pi) comme générateurs aléatoires, puisque l'on pourrait assez rapidement violer le code.

E - Formules BBP

En septembre 95, Bailey, Borwein et Plouffe trouvent la formule suivante :

Elle est extrêmement simple, la démonstration est évidente en passant par les intégrales et les séries, bref elle aurait pu être découverte bien avant. De plus, sa convergence est linéaire, le tout était donc de voir à quoi elle pouvait être utile.
En fait, on remarque que l'on a "presque" le développement d'un nombre (Pi ici) en base 16. Et ce presque va permettre d'évaluer le n-ième digit de Pi en base 16 sans connaitre les précédents, le tout en complexité n*ln(n) !
Ceci est maintenant bien connu, mais en poussant la réflexion un peu plus loin, on peut imaginer qu'en atteignant n'importe quelle décimale sans besoin des précédentes, on arrive - avec les mains - à commencer à prédire une à une les décimales, à connaître la loi de la formation. En fait, la question cruciale, c'est comment se dire que Pi est "aléatoire" en base 16 alors que l'on a ci-dessus un quasi-développement de Pi en base 16... Il faut enlever le quasi et la question est terminée pour peu que l'on choisisse notre définition du terme aléatoire, mais après tout le baratin ci-dessus, j'espère que c'est un peu plus clair !

Et un premier résultat d'irrationnalité par exemple peut tomber. Alors pour Pi, ça ira, on sait que c'est irrationnel depuis un bail, mais pensez aux combinaisons de Pi avec les logarithmes, aux polylogarithmes ou même (surtout) aux valeurs entières de la fonction Zêta, dont on sait depuis les derniers résultats de Broadhurst, Plouffe, Huvent, Gourévitch qu'elles peuvent être mises sous la forme d'une formule BBP !! Ce serait un sacré résultat....
Il y a besoin de s'éloigner un tout petit peu de Pi, c'est pourquoi je n'irai pas très loin (sinon, on en finit plus !).

Intuitivement, la relative facilité avec laquelle on accède à une décimale sans connaître les précédente laisse supposer que l'on puisse trouver peut-être des propriétés sur les décimales de ces constantes. Des théorèmes reliant les fonctions polylogarithmes et l'irrationnalité existent mais sont difficilement exploitables dans ce cadre.

Par contre, en octobre 2000, Bailey et Crandall ont réduit les conditions de normalité à la vérification de l'hypothèse suivante :

E.1 - Hypothèse "A" de Bailey et Crandall

Notons , n>0 une fraction rationnelle polynômiale avec deg(p)<deg(q) et r sans pôles sur N (C'est la partie entre parenthèses des formules BBP après regroupement au même dénominateur). Soit b2 et x₀=0 (b représente la puissance dans la formule BBP, c'est à dire aussi la base). Alors la suite {x₀, x₁, x₂...} définie par :

a un attracteur fini ou est équidistribuée sur [0,1].
Ces deux derniers termes réclament des précisions :

E.2 - Attracteur fini

Intuitivement, la propriété de posséder un attracteur fini représente le fait pour une séquence de s'approcher toujours des mêmes valeurs à partir d'un certain rang, ceci dans n'importe quel ordre (on peut montrer que dans le cas qui nous intéresse, c'est toujours le même ordre). C'est comme si l'on tendait vers une sorte de rationnel (dont les séquences de décimales sont périodiques) généralisé :

Précisément, une suite possède un attracteur fini si il existe et tel que pour tout k0,

On peut également montrer que dans le cas qui nous intéresse (formules BBP), cette propriété est équivalente à la rationnalité de la limite de x_n.

E.3 - Equidistribution

Cette notion est assez intuitive, elle est vérifiée si la proportion d'apparition d'une séquence à valeurs dans [0,1] dans un intervalle donné [c,d] est justement la longueur de cet intervalle, soit d-c, bref si les valeurs prises sont distribuées uniformément dans l'intervalle [0,1] :

Cette notion est plus forte que la simple densité de la séquence (à cause du caractère uniforme de la répartition) et représente l'analogue continu de la propriété d'équirépartition des décimales d'un nombre.

Conséquence

L'équirépartition pour ce genre de séquence implique leur normalité. Comme l'on sait que certaines constantes comme 1, ln(2) ou sont irrationnelles, sous l'hypothèse A, on en déduit la normalité de ces constantes. Reste à prouver l'hypothèse A...

On sait que la normalité d'un nombre entraine son irrationnalité. Cette condition est donc une sorte de conjecture menant à la réciproque dans le cas des formules BBP ou plus généralement des séquences définies plus haut. Les formules BBP n'ont en tous les cas pas encore livré tous leurs secrets...

Bibliographie

Oh, vous vous en doutez...

[1] J. P. Delahaye, Le fascinant nombre Pi

[2] D. Bailey, R. Crandall, On the Random Character of Fundamental Constant Expansions.
http://www.nersc.gov/~dhb/dhbpapers/bcrandom.pdf