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,
Un ensemble N⊆ℝ est dit négligeable (ou de mesure nulle) lorsque, donné ε>0 arbitrairement petit, on peut trouver une suite (Ii) (indicée par les entiers naturels) d'intervalles tels que (1) N⊆⋃iIi (c'est-à-dire, ces intervalles recouvrent N), et (2) ∑iℓ(Ii)<ε (c'est-à-dire, la somme des longueurs ℓ(Ii) des intervalles est inférieure au ε qu'on s'était donné).
Le complémentaire d'un ensemble négligeable est dit (conégligeable ou) de mesure pleine. On dit aussi que
presque tous [au sens de la mesure]les nombres réels vérifient une propriété P lorsque l'ensemble de ceux qui la vérifient est de mesure pleine (i.e., l'ensemble de ceux qui ne la vérifient pas est négligeable).
— est une définition raisonnable d'un ensemble de réels « très petit », il y en a une autre, concurrente :
Un ensemble M⊆ℝ est dit maigre (ou parfois
de première catégorie, mais c'est une terminologie épouvantable) lorsqu'il existe une suite (Fi) (indicée par les entiers naturels) de parties de ℝ tels que (1) M⊆⋃iFi (c'est-à-dire, ces parties recouvrent M) et (2) chaque Fi est fermé d'intérieur vide, ce qui signifie (2a) « fermé » : que si x n'appartient pas à Fi, alors il existe un ε>0 tel qu'aucun des nombres entre x−ε et x+ε n'appartienne à Fi et (2b) « d'intérieur vide » : que Fi ne contient aucun intervalle de longueur non-nulle.Le complémentaire d'un ensemble maigre est dit comaigre (ou résiduel ; ceci signifie exactement que l'ensemble contient une intersection dénombrable d'ouverts denses). On pourrait dire que
quasiment tous au sens de la catégorieles nombres réels vérifient une propriété P lorsque l'ensemble de ceux qui la vérifient est comaigre (i.e., l'ensemble de ceux qui ne la vérifient pas est maigre).
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/br
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 bn désigne le n-ième
bit (valant 0 ou 1) d'un nombre réel x, considérons la
suite
(si le MathML est cassé dans votre navigateur, il s'agit
de la moyenne des n
premiers bk, i.e.,
(1/n)·somme(bk, 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 bn
à bn² 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 2n 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² 2n²
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 bn et bn², 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 bn à bn² 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/qd : 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 () : 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).