David Madore's WebLog: Pourquoi e et π paraissent-ils plus aléatoires que génériques ?

Je veux discuter ici non d'une question de maths mais d'une question de philosophie des maths (et qui, pour une fois, n'est pas de la logique mais plutôt la théorie des nombres !). Néanmoins, pour l'expliquer, il faut bien que je parle de maths.

Un fait empirique est le suivant : quand on fait des études statistiques sur les décimales, disons, du nombre e ou du nombre π, celles-ci se comportent empiriquement comme une suite aléatoire (comme si elles avaient été tirées au hasard par un grand dé cosmique). Par exemple, les décimales en base 10 semblent équidistribuées (il y a autant de 0 que de 1 que de 2… que de 9) ; mieux, les suites de 2 chiffres semblent équidistribuées (il y a autant de 00 que de 01… que de 99), et pareil pour les suites de 3 chiffres et plus, tant qu'on a assez de données pour faire des statistiques significatives (or, s'agissant des décimales de π, on en a beaucoup). Autrement dit, on conjecture que π est un nombre « normal », ce qui regroupe ces différentes affirmations sur la fréquence des décimales. Et ce n'est pas vrai qu'en base 10, qui n'a aucune raison d'être spéciale : on conjecture que π est normal en toute base (entre autres, écrit en base 2, on conjecture qu'il devrait contenir quelque part le contenu de ce blog jusqu'à sa fin, codé en binaire ; ceci n'a, évidemment, rien de remarquable : il faudrait aller si loin dans les décimales pour le trouver qu'indiquer l'endroit où on le trouve est essentiellement aussi long que donner le contenu lui-même).

Pour motiver cette conjecture on donne typiquement l'explication suivante : « presque tous » les nombres réels sont normaux en toute base. C'est-à-dire que si on tire un nombre réel aléatoirement (uniformément entre 0 et 1), la probabilité qu'il ait les propriétés que j'esquisse ci-dessus vaut exactement 1. Ceci est un énoncé mathématique clair et pas très difficile (pas du tout conjectural) : l'ensemble des nombres réels qui n'ont pas la propriété d'être normaux en toute base est un ensemble dit négligeable (=de mesure de Lebesgue nulle, ce qui signifie techniquement qu'on peut le recouvrir par une suite d'intervalles dont la somme des longueurs converge et a une somme arbitrairement petite, cf. ci-dessous), correspondant à un événement de probabilité 0. On reformule aussi ce fait en disant que presque tous les nombres réels sont normaux en toute base (presque tous veut dire précisément que l'ensemble de ceux qui ne le sont pas est négligeable). Dès lors (dit-on), il n'est pas surprenant, si presque tous les nombres réels ont la propriété d'être normaux en toute base, de conjecturer que π en particulier l'est. Je ne prétends pas que cette justification soit insensée, mais elle glisse de la poussière sous le tapis, à savoir la raison pour laquelle presque tous est une bonne notion.

Pour expliquer la poussière dont je me plains, il faut que je signale un autre fait mathématique : la dualité entre mesure [de Lebesgue] et catégorie [topologique]. (Je suis obligé ici de donner quelques précisions techniques, mais les détails ne sont pas extrêmement importants et peuvent être survolés.) En effet si la définition que j'ai donnée ci-dessus,

Il existe bien sûr des ensembles qui sont « très petits » dans les deux sens (à la fois négligeables et maigres) : l'ensemble ℚ des rationnels, ou plus généralement, tout ensemble dénombrable ou à plus forte raison fini, est négligeable et maigre ; l'ensemble de Cantor standard (obtenu en partant de [0;1] et en retirant de façon répétée le tiers du milieu de chaque intervalle restant), bien qu'indénombrable, est à la fois négligeable et maigre (en fait, c'est déjà un fermé d'intérieur vide, donc la maigreur est plus évidente que la négligeabilité). Les deux notions ont des propriétés communes, comme le fait que la réunion d'une suite (i.e., d'une famille dénombrable) d'ensembles négligeables, resp. maigres, et encore négligeable, resp. maigre. Ou encore, le fait que ni un ensemble négligeable ni un ensemble maigre ne peuvent contenir un intervalle de longueur non nulle (aussi petite soit-elle) : ceci est généralement reformulé en disant qu'un ensemble de mesure pleine ou un ensemble comaigre sont denses (i.e., rencontrent tout intervalle de longueur non nulle ; un cas résulte de l'additivité de la mesure de Lebesgue, l'autre du théorème de Baire).

Les parallèles entre ces deux notions classiques de « petitesse » sont assez nombreux et importants pour que quelqu'un ait consacré un livre essentiellement à cette question (il s'agit de Measure and Category de John Oxtoby, le numéro 2 dans la série des Graduate Texts in Mathematics de Springer). Je donne d'autres exemples de parallèle en petits caractères ci-dessous (le lecteur non intéressé par les détails mathématiques peut les sauter).

Voici un exemple : une partie de ℝ² est négligeable, resp. maigre (la notion de partie négligeable ou maigre de ℝ² se définit de façon essentiellement identique au cas de ℝ — il suffit en gros de remplacer les intervalles par des rectangles, et, pour la mesure, de prendre le produit de leurs côtés) si et seulement si son intersection avec les droites horizontales y=c est négligeable, resp. maigre, vue comme partie de ℝ, pour « presque toutes au sens de la mesure » (resp. « quasiment toutes au sens de la catégorie ») les valeurs de c, autrement dit, l'ensemble des c telle que l'intersection ne soit pas négligeable, resp. maigre, est un ensemble négligeable, resp. maigre. (Dans le cas de la mesure, ceci est une incarnation du théorème de Fubini.) ❦ Voici un autre exemple : supposons que A est une partie borélienne de ℝ (c'est-à-dire, qui peut s'obtenir à partir des intervalles en répétant de façon arbitraire des opérations de complémentaire, de réunion dénombrable et d'intersection dénombrable), et supposons que A est invariant par changement des premières décimales d'un nombre (en une base b fixée quelconque), c'est-à-dire que si x∈A et si x′ diffère de x par un rationnel de la forme N/b^r où N, r sont entiers (i.e., les décimales de x′ coïncident avec celles de x à partir d'un certain rang r) alors x′∈A ; alors : A est soit de mesure nulle (=négligeable) soit de mesure pleine, et A est soit maigre soit comaigre (le cas de la mesure s'appelle loi du 0–1 de Kolmogorov). ❦ Un résultat de théorie descriptive des ensembles : la projection sur la première coordonnée d'un ensemble borélien de ℝ² n'est pas nécessairement borélienne, en revanche elle diffère d'un borélien (au sens de la différence symétrique) par un ensemble simultanément[#] négligeable et maigre. ❦ Je pourrais enfin citer un théorème classique d'Erdős, généralisant un résultat antérieur de Sierpiński, selon lequel, sous l'hypothèse du continu, il existe une involution ℝ→ℝ qui envoie ensembles négligeables sur ensembles maigres et vice versa.

[#] Note technique : on donne la définition suivante : un ensemble Lebesgue-mesurable est la différence symétrique d'un borélien et d'un négligeable, et un ensemble ayant la propriété de Baire est la différence symétrique d'un borélien et d'un maigre. Il est alors vrai qu'un ensemble à la fois Lebesgue-mesurable et ayant la propriété de Baire, est la différence symétrique d'un borélien et d'un ensemble à la fois négligeable et maigre. Comme je ne trouve de preuve nulle part, en voici une : on peut écrire (cf. ci-dessous) ℝ=M∪N où M est maigre et N est négligeable, M et N sont disjoints (i.e., complémentaires l'un de l'autre), et tous les deux sont boréliens. Si X est mesurable et a la propriété de Baire, alors : X∩M est mesurable (puisque M est borélien), donc on peut écrire X∩M = A∆N′ où A est borélien et N′ négligeable ; et quitte à intersecter A et N′ avec M, on peut supposer qu'ils sont inclus dedans : du coup, N′ est simultanément maigre et négligeable ; or de même, X∩N peut s'écrire B∆M′ avec B borélien inclus dans N et M′ simultanément négligeable et maigre inclus dans N ; on a alors X = (A∪B)∆(M′∪N′) différence symétrique d'un borélien et d'un ensemble simultanément négligeable et maigre.

Néanmoins, pour parallèles qu'elles soient, ces deux notions de petitesse, être négligeable et être maigre, sont aussi souvent en opposition. En effet, l'ensemble ℝ de tous les réels est réunion d'un ensemble négligeable et d'un ensemble maigre. Comme ℝ n'est certainement pas un ensemble « très petit » de réels, s'il est réunion de deux ensembles, il faut croire que l'un de ces ensembles n'est pas si petit que ça. Ssi on préfère, il y a des ensembles négligeables qui sont comaigres, ou de façon encore équivalente, des ensembles de mesure pleine qui sont maigres. Et en fait, si on prend l'ensemble des nombres normaux en base b, ou bien normaux en toute base, c'est un exemple tout à fait explicite d'un ensemble de mesure pleine qui est maigre : c'est-à-dire : au sens de la mesure, presque tous les nombres réels sont normaux, mais au sens de la catégorie, quasiment aucun ne l'est !

L'argument heuristique présenté ci-dessus pour expliquer pourquoi il est raisonnable de conjecturer que e et π sont normaux, c'est que presque tous les nombres le sont (la probabilité qu'un nombre tiré au hasard ne soit pas normal vaut 0) ; mais c'est presque tout au sens de la mesure : or à l'inverse, comme je viens de le dire, au sens de la catégorie, quasiment aucun nombre n'est normal, donc on pourrait tout aussi bien conjecturer que e et π ne sont pas normaux.

Ainsi, si on doit faire une conjecture sur le comportement des décimales de π, Monsieur Eugsebel (avocat de la théorie de la mesure) va nous dire je conjecture que π est normal en toute base, parce que l'ensemble des nombres qui le sont est de mesure pleine, et on trouve ça raisonnable. Mais Monsieur Eriab (avocat de la catégorie topologique), au contraire, va dire et moi je conjecture que π n'est normal en aucune base, parce que l'ensemble des nombres normaux est maigre (en fait, Monsieur Eriab va faire des prévisions beaucoup plus précises que « ne pas être normal », j'en donnerai des exemples plus loin) ; et expérimentalement il semble que Monsieur Eugsebel ait raison dans sa conjecture alors que Monsieur Eriab aurait tort. Comment cela se fait-il ?

La question philosophique, c'est donc : étant donné que ces notions classiques et naturelles sont « duales », présentant un grand parallèle, comment se fait-il que la théorie de la mesure prédise apparemment mieux que la catégorie topologique le comportement d'un nombre « naturel » comme e ou π ?

Pour essayer d'éclaircir un peu pourquoi c'est une question naturelle à se poser, il faut que je mentionne encore les deux notions de nombre aléatoire et de nombre générique, qui correspondent respectivement aux prédictions faites par la mesure et par la catégorie. La question deviendra alors : comment se fait-il que des nombres naturels comme e et π ressemblent plus fortement à des nombres aléatoires qu'à des nombres génériques ? (alors qu'ils ne sont ni l'un ni l'autre).

⚠La notion de nombre aléatoire peut être source de beaucoup de confusion. D'abord, il y a ce que les probabilistes appellent une variable aléatoire : un nombre réel aléatoire, dans ce sens, ce n'est pas un nombre réel, c'est techniquement une fonction à valeurs réelles sur un espace de possibles (espace probabilisé) ; on peut alors parler de toutes sortes de choses sur des nombres tirés aléatoirement selon telle ou telle distribution de probabilités : c'est là le sens usuel du mot aléatoire et ce n'est pas celui dont je veux parler, même si celui dont je veux parler (dû à Martin-Löf) est évidemment apparenté. Il s'agit ici d'un concept d'« aléatoire » absolu : en ce sens, un réel (qui peut sans problème être identifié à la suite de ses décimales) est ou n'est pas aléatoire, ce qui est différent de la notion d'aléatoire des probabilistes où il n'y a pas de sens à dire qu'un nombre dans l'absolu ait été tiré aléatoirement.

En fait, je n'ai pas l'intention de donner la définition formelle de nombre aléatoire : mais essentiellement, un nombre est aléatoire lorsqu'il n'appartient à aucun ensemble négligeable qui puisse être décrit de façon explicite ou calculable. Naïvement, on aimerait dire qu'un nombre aléatoire est un nombre qui n'appartient à aucun ensemble négligeable — cela, bien sûr, n'a pas de sens car x appartient toujours à {x}, et {x} est négligeable (puisque fini). Alors on fait le mieux qu'on puisse faire : on suppose donnée une notion de calculabilité (relativement à quoi la définition sera faite), et on appelle « aléatoire » un nombre qu'on n'arrive pas à mettre dans un ensemble négligeable qui puisse être décrit par une suite calculable (par exemple à partir des intervalles à extrémités rationnelles et au moyen des opérations de complémentaire, de réunion dénombrable et d'intersection dénombrable). Ceux qui veulent voir une définition précise peuvent se rapporter à cette vieille entrée où je traite essentiellement de la même question qu'ici mais sous un angle différent ; ou bien à l'article Wikipédia sur la question ; ou encore, par exemple au livre Computability de S. Barry Cooper (§15.7) ; voir aussi Jech, Set Theory, lemme 26.4 dans la Third Millennium Edition (ou 42.6 dans l'ancienne), même s'il s'agit là d'une définition beaucoup plus forte (car relativement à une notion de calculabilité elle-même beaucoup plus forte).

La notion de nombre générique est duale : un nombre est générique lorsqu'il n'appartient à aucun ensemble maigre qui puisse être décrit de façon explicite ou calculable (de nouveau, voir cette vieille entrée pour une définition précise, ou §13.3 dans le livre de Cooper, ou encore chapitre IV, §2, dans le livre Degrees of Unsolvability de Lerman).

Mesure (de Lebesgue)	Catégorie (topologique)
négligeable =de mesure nulle	maigre =de première catégorie
conégligeable =de mesure pleine =de complémentaire négligeable	comaigre =résiduel =de complémentaire maigre
presque tous (pour la mesure) =tous dans un ensemble de mesure pleine	quasiment tous pour la catégorie [terme non standard] =tous dans un ensemble comaigre
réel aléatoire =dans aucun ensemble négligeable calculable	réel générique =dans aucun ensemble maigre calculable

Autrement dit, un nombre aléatoire est un nombre sur lequel Monsieur Eugsebel fait des prévisions correctes, tandis qu'un nombre générique en est un sur lequel c'est Monsieur Eriab qui a raison. Cette dernière notion n'est pas évidente à visualiser intuitivement. La notion de nombre aléatoire se comprend assez bien, et correspond effectivement à l'image qu'on peut se faire d'un nombre obtenu par tirage aléatoire de la suite de ses décimales. En particulier, un nombre aléatoire est normal en toute base — justement puisque l'ensemble des nombres qui ne le sont pas est négligeable et que cet ensemble se décrit de façon calculable (je ne rentre pas dans les détails). Un nombre générique, en revanche, n'est pas normal, puisque l'ensemble des nombres normaux est maigre ; mais il est intéressant d'essayer de décrire de façon plus positive comment ses décimales se comportent.

Prenons la base 2 pour simplifier : si b_n désigne le n-ième bit (valant 0 ou 1) d'un nombre réel x, considérons la suite $\frac{1}{n}\sum _{k=0}^{n-1}{b}_k$ (si le MathML est cassé dans votre navigateur, il s'agit de la moyenne des n premiers b_k, i.e., (1/n)·somme(b_k, k=0…n−1)) : autrement dit, il s'agit de la proportion de 1 parmi les n premiers bits du nombre considéré. Comment se comporte cette suite ? Si on suppose que x est aléatoire, alors elle tend vers ½ : en effet, l'ensemble des nombres x pour lesquels la suite ne tend pas vers ½ est un ensemble négligeable, ceci est une conséquence de la loi des grands nombres, et la normalité d'un nombre est un renforcement de cette affirmation. Et comme je l'ai souligné, c'est le cas, expérimentalement, pour des nombres comme e ou π. En revanche, si x est générique, il en va tout autrement : la suite n'a pas de limite, et en fait elle s'approche arbitrairement, et infiniment souvent, de toute valeur de l'intervalle [0;1] (notamment, sa limite inf. vaut 0 et sa limite sup. vaut 1). C'est-à-dire qu'alors que les bits d'un nombre aléatoire se répartissent bien en proportion, tendant vers moitié de 0 et moitié de 1, pour un nombre générique, la proportion de 1 ne converge jamais, elle ne cesse de changer. Donc, s'il est vrai pour un nombre générique aussi bien que pour un nombre aléatoire que toutes les suites de chiffres apparaissent dans les décimales du nombre, en revanche, s'agissant d'un nombre générique, elles ne le font pas avec une fréquence bien définie. Un autre phénomène du même genre (et qui implique le précédent) est que si x est générique, il existe des n arbitrairement grands tels que toutes les décimales b_n à b_n² soient des 0 (et de même avec des 1, ou une alternance de 0 et de 1, ou ce genre de motifs ; et de même en remplaçant n² par 2ⁿ ou, en fait, n'importe quelle fonction calculable de n) : ceci n'est pas le cas avec les nombres aléatoires (pour trouver n² bits 0 consécutifs dans une suite aléatoire, il faudra aller jusqu'au bit n² 2^n² environ).

Pour montrer ce résultat, il s'agit simplement de remarquer que, lorsque m est fixé, l'ensemble des suites binaires qui, pour un certain n≥m, n'ont que des zéros entre les termes b_n et b_n², est un ouvert dense, ce qu'il est facile de vérifier. En prenant l'intersection de ces ensembles pour tous les m entiers naturels, on voit que l'ensemble des réels pour lesquels il existe des n arbitrairement grands tels que toutes les décimales b_n à b_n² soient des 0 est comaigre. On peut évidemment faire pareil pour des 1 ou des alternances de 0 et de 1 avec n'importe quelle période rationnelle fixée : ceci montre que la densité de 1 va s'approcher asymptotiquement de n'importe quel rationnel fixé.

Si j'essaie de donner une image intuitive des réels aléatoires et génériques, je dirai que les deux font « n'importe quoi » mais différemment : les aléatoires obéissent à des lois statistiques, donc leurs décimales se répartissent bien en proportion ; à l'inverse, les génériques font n'importe quoi en ce sens qu'ils s'amusent à obéir à tous les motifs réguliers qu'on peut imaginer, y compris pour très longtemps.

Une autre différence intéressante concerne l'approximation diophantienne : on dit qu'un réel ξ est approchable à l'ordre d par les rationnels lorsqu'il existe une infinité de rationnels p/q et une constante C>0 tels que |ξ−(p/q)| < C/q^d : cette condition est d'autant plus forte que d est grand. L'algorithme d'Euclide montre que tout nombre irrationnel est approchable à l'ordre 2 par les rationnels (les rationnels eux-mêmes ne sont approchables qu'à l'ordre 1). Un nombre approchable à tous les ordres est appelé nombre de Liouville (ces nombres sont tous transcendants — et c'est d'ailleurs la raison pour laquelle Liouville les a introduits — car il est facile de montrer qu'un nombre algébrique de degré d ne peut pas être approchable à un ordre >d ; en fait, un théorème difficile montre qu'il ne l'est même pas à un ordre >2). Là aussi, la mesure et la catégorie diffèrent complètement dans leur jugement : l'ensemble des nombres de Liouville est comaigre alors que l'ensemble des nombres approchables à un ordre >2 quelconque est négligeable. Autrement dit, un nombre aléatoire est approchable par les rationnels à l'ordre 2 et pas mieux, alors qu'un nombre générique est approchable à tous les ordres. De nouveau, Monsieur Eugsebel prédira que e et π ne sont pas approchables par les rationnels à mieux que l'ordre 2 alors que Monsieur Eriab prédira qu'ils le sont à tous les ordres — et pour le coup, on sait que Monsieur Eriab a tort (s'agissant de e, on sait que Monsieur Eugsebel a raison : le meilleur ordre d'appproximation est 2, cela peut se montrer à partir de la fraction continuée habituelle pour ce nombre ; s'agissant de π, d'après ce papier, on sait qu'il n'est pas approchable à un ordre mieux que 8.02, et il me semble qu'on conjecture aussi que le meilleur ordre est 2). ❦ Voir aussi la discussion autour de la constante de Hinčin (Khintchine) pour une propriété amusante des nombres aléatoires que n'ont pas les nombres génériques : cette fois-ci, s'agissant de e, ni Monsieur Eugsebel ni Monsieur Eriab n'ont raison, la moyenne géométrique des coefficients de son écriture en fraction continuée tend vers +∞, donc ni la constante de Hinčin qu'avait prédite Monsieur Eugsebel ni l'absence de limite qu'avait prédite Monsieur Eriab (s'agissant de π, expérimentalement, Monsieur Eugsebel a raison).

Il faut que je souligne clairement ceci : ni e ni π ne sont ni aléatoire ni générique (en effet, un nombre aléatoire ou générique ne peut pas être calculable, et e et π sont de toute évidence calculables), ils font seulement semblant de l'être : j'ai envie de les appeler empiriquement aléatoires ou pseudoaléatoires. Et à la limite, la question n'est pas tant pourquoi ils sont pseudoaléatoires que pourquoi ils ne sont pas « empiriquement génériques » ou « pseudogénériques ».

En fait, je ne sais même pas si on pourrait construire un « générateur pseudogénérique » simple comme on peut construire un générateur pseudoaléatoire, ou à quoi ça ressemblerait. À plus forte raison, je ne connais aucun nombre « naturel » (i.e., apparu en mathématiques pour d'autres raisons) qui aurait ne serait-ce qu'expérimentalement l'air d'être pseudogénérique, alors que les nombres expérimentalement pseudoaléatoires abondent. (Et comme je l'avais déjà signalé dans une autre entrée, je me demande bien si on pourrait dire des choses en crypto relativement à un oracle générique alors que la crypto fait beaucoup de choses relativement à un oracle aléatoire.)

Je pense que c'est là une question philosophique subtile et profonde, et sur laquelle je suis surpris de trouver que personne ne semble avoir ne serait-ce que tenté de dire quoi que ce soit.

Ajout : j'avais oublié de mettre un lien vers la question MathOverflow où je demande essentiellement la même chose.

Ajout (2023-11-27) : nouvelle question sur le StackExchange d'informatique théorique où je demande en substance ce qu'on sait dire sur les oracles génériques en théorie de la complexité (sachant que les oracles aléatoires ont été étudiés), et je rappelle au passage avec des références que du point de vue de la calculabilité ils n'apportent rien d'utile pour calculer une fonction déterministe (voir aussi par ici sur Twitter).