Nombres Univers 8


Pi est un nombre irrationel (il est même « transcendant« ) : comme il ne peut pas s’écrire sous forme d’une fraction, ses décimales ne « cyclent » jamais commes celles de 22/7 = 3.142857 142857 142857 … par exemple, et il y en a une infinité, donc a priori une infinité de séquences de décimales toutes différentes.

Pas étonnant donc qu’on puisse facilement trouver sa date de naissance dans les décimales de Pi, mais est-on sur de trouver n’importe quelle séquence (finie) de chiffres dans les décimales de Pi, par exemple un million de chiffres 5 consécutifs, ou l’oeuvre complète de Shakespeare traduite en chiffres ? Pour ça, il faudrait que pi soit un « nombre univers« . Et n’en déplaise à certains, on n’en sait rien pour l’instant*, et il en va de même pour e, sqrt{2}, ln(2) et tous les nombres irrationnels usuels, et ce non seulement en base 10 mais dans n’importe quelle base [1].

Par contre il existe une infinité de nombres univers, on sait les fabriquer, et c’est même très facile. Exemple: la constante de Champernowne. On la forme en concaténant simplement les entiers croissants dans les décimales :

C10=0,123456789101112131415161718192021…

Les nombres ainsi construits sont même plus qu’univers, ce sont des nombres « normaux » parce que toute séquence de décimales finie se répète indéfiniment avec une probabilité uniforme. Dans C10, la séquence 1234 du début va se trouver plus loin …1233 1234 1235… et encore plus loin  …11233 11234 11235… et ainsi de suite jusqu’à l’infini. La séquence 1234 se retrouve statistiquement dans 1/10000 ème des groupes de 4 décimales.

Un nombre univers compact ?

Les nombres normaux font un beau gâchis de décimales, car ils contiennent l’oeuvre complète de Shakespeare une infinité de fois. Peut-on imaginer un nombre univers plus économique ?

Essayons de compacter la constante_de_Champernowne en:

  1. ne répétant pas les décimales déjà présentes. Par exemple après 0,1234567891011 , on ne va pas écrire 12 parce que le 1 est déjà présent, mais seulement 2 : 0,12345678910112 …
  2. ne répétant pas les nombres déjà présents dans les décimales précédentes : dans l’exemple ci-dessus, le 12 est déjà présent dans les toutes premières décimales, donc on peut passer directement au 13 :

on obtient ainsi 0,123456789 10113141516171819 20212242526272829 3032335 …

On voit qu’on ne gagne que quelques pourcents de décimales. Mais on peut aller plus loin : les 9 premières décimales de C10 ne servent à rien puisqu’elles sont forcément présentes dans les décimales de 10..à..99, lesquelles ne servent à rien puisqu’elles figurent 10x dans les décimales de 100..à..999 et ainsi de suite.

Ses séquences de De Bruijn

Une tresse de De Bruijn

Mais d’abord, est-ce bien malin de fabriquer un nombre univers compact en concaténant des entiers consécutifs ? Peut-on fabriquer une séquence contenant chaque nombre de n décimales et qui soit nettement plus compacte que l’énumération ? Jean-Paul Alllouche m’a gentiment indiqué que les séquences De Brujin (SDB) font exactement ça, et même très bien puisque chaque nombre de n chiffres en base b n’est présent qu’une seule fois dans la séquence B(b,n). La page Wikipédia sur les SDB (en anglais) pointe sur un site étonnant : le « Combinatorial Object Server » qui comporte entre autres outils un générateur de SDB permettant de générer très rapidement par exemple :

B(10,3) = 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 9 0 2 1 0 2 2 0 2 3 0 2 4 0 2 5 0 2 6 0 2 7 0 2 8 0 2 9 0 3 1 0 3 2 0 3 3 0 3 4 0 3 5 0 3 6 0 3 7 0 3 8 0 3 9 0 4 1 0 4 2 0 4 3 0 4 4 0 4 5 0 4 6 0 4 7 0 4 8 0 4 9 0 5 1 0 5 2 0 5 3 0 5 4 0 5 5 0 5 6 0 5 7 0 5 8 0 5 9 0 6 1 0 6 2 0 6 3 0 6 4 0 6 5 0 6 6 0 6 7 0 6 8 0 6 9 0 7 1 0 7 2 0 7 3 0 7 4 0 7 5 0 7 6 0 7 7 0 7 8 0 7 9 0 8 1 0 8 2 0 8 3 0 8 4 0 8 5 0 8 6 0 8 7 0 8 8 0 8 9 0 9 1 0 9 2 0 9 3 0 9 4 0 9 5 0 9 6 0 9 7 0 9 8 0 9 9 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 2 2 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2 8 1 2 9 1 3 2 1 3 3 1 3 4 1 3 5 1 3 6 1 3 7 1 3 8 1 3 9 1 4 2 1 4 3 1 4 4 1 4 5 1 4 6 1 4 7 1 4 8 1 4 9 1 5 2 1 5 3 1 5 4 1 5 5 1 5 6 1 5 7 1 5 8 1 5 9 1 6 2 1 6 3 1 6 4 1 6 5 1 6 6 1 6 7 1 6 8 1 6 9 1 7 2 1 7 3 1 7 4 1 7 5 1 7 6 1 7 7 1 7 8 1 7 9 1 8 2 1 8 3 1 8 4 1 8 5 1 8 6 1 8 7 1 8 8 1 8 9 1 9 2 1 9 3 1 9 4 1 9 5 1 9 6 1 9 7 1 9 8 1 9 9 2 2 2 3 2 2 4 2 2 5 2 2 6 2 2 7 2 2 8 2 2 9 2 3 3 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8 2 3 9 2 4 3 2 4 4 2 4 5 2 4 6 2 4 7 2 4 8 2 4 9 2 5 3 2 5 4 2 5 5 2 5 6 2 5 7 2 5 8 2 5 9 2 6 3 2 6 4 2 6 5 2 6 6 2 6 7 2 6 8 2 6 9 2 7 3 2 7 4 2 7 5 2 7 6 2 7 7 2 7 8 2 7 9 2 8 3 2 8 4 2 8 5 2 8 6 2 8 7 2 8 8 2 8 9 2 9 3 2 9 4 2 9 5 2 9 6 2 9 7 2 9 8 2 9 9 3 3 3 4 3 3 5 3 3 6 3 3 7 3 3 8 3 3 9 3 4 4 3 4 5 3 4 6 3 4 7 3 4 8 3 4 9 3 5 4 3 5 5 3 5 6 3 5 7 3 5 8 3 5 9 3 6 4 3 6 5 3 6 6 3 6 7 3 6 8 3 6 9 3 7 4 3 7 5 3 7 6 3 7 7 3 7 8 3 7 9 3 8 4 3 8 5 3 8 6 3 8 7 3 8 8 3 8 9 3 9 4 3 9 5 3 9 6 3 9 7 3 9 8 3 9 9 4 4 4 5 4 4 6 4 4 7 4 4 8 4 4 9 4 5 5 4 5 6 4 5 7 4 5 8 4 5 9 4 6 5 4 6 6 4 6 7 4 6 8 4 6 9 4 7 5 4 7 6 4 7 7 4 7 8 4 7 9 4 8 5 4 8 6 4 8 7 4 8 8 4 8 9 4 9 5 4 9 6 4 9 7 4 9 8 4 9 9 5 5 5 6 5 5 7 5 5 8 5 5 9 5 6 6 5 6 7 5 6 8 5 6 9 5 7 6 5 7 7 5 7 8 5 7 9 5 8 6 5 8 7 5 8 8 5 8 9 5 9 6 5 9 7 5 9 8 5 9 9 6 6 6 7 6 6 8 6 6 9 6 7 7 6 7 8 6 7 9 6 8 7 6 8 8 6 8 9 6 9 7 6 9 8 6 9 9 7 7 7 8 7 7 9 7 8 8 7 8 9 7 9 8 7 9 9 8 8 8 9 8 9 9 9

qui ne comporte que 1000 chiffres au lieu des 3000 qui seraient nécessaires pour une énumération. Si vous êtes observateur, vous remarquerez que 900 n’est pas présent dans la séquence. C’est parce qu’elle est cyclique, il faut l’imaginer « bouclée » et alors les 00 du début de la séquence dont on pouvait penser qu’ils étaient inutiles se placent après le 9 final pour former le 900.

Cette nature cyclique permet donc  de commencer la séquence B(b,n) n’importe où en prenant n chiffres, puis de passer au suivant en se décalant d’un chiffre soit vers la gauche soit vers la droite et ainsi de suite. Après avoir effectué ainsi bn décalages, on se retrouve au point de départ en ayant la certitude d’être passé une et une seule fois par chaque nombre compris entre 0 et bn-1. Beau, non ?

Et utile. Par exemple pour ouvrir une porte protégée par un digicode de 3 chiffres sans touche « entrée », qui s’ouvrirait dès qu’on tape les trois chiffres secrets consécutivement. Si vous avez oublié le code, la SDB B(10,3) donne la séquence qui ouvrira la porte à coup sur en pressant le minimum de touches…

On peut aussi remarquer qu’une SDB comme

B(2,8) = 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1

, qui définit en 256 bits les 256 octets possibles en binaire (compression d’un facteur 8 par rapport à l’énumération!), se rapproche assez du code de Gray(-Gros)  connu par 1 des 10 types de mathématiciens: on passe d’un nombre à l’autre par un décalage à gauche ou à droite et l’entrée d’un seul bit d’information du côté opposé.

Retour au nombre univers compact

Dans la SDB B(10,n), tous les nombres à n chiffres ne sont représentés qu’une seule fois.

La tentation est grande de proposer comme nombre univers le plus compact qui soit un nombre dont les décimales seraient données par B(10,∞), ce qui garantirait que chaque nombre de longueur infinie n’y figure qu’une seule fois…

J’aurais même été tenté d’en écrire les premières décimales :

U=0,3 141 592 653 589 793 238 462 643 383 279 502 884 197 169 399 375 105 820 974 944 592 307 816 406 286 208 998 628 034 825 342 117 067 982 148 086 513 282 306 647 093 844 609 550 582 231 725 359 408 128 481 117 450 284 102 701 938 521 105 559 644 622 948 954 930 381 964 428 810 975 665 933 446 128 475 648 233 786 783 165 271 201 909 145 648 566 …

Ben oui, comme les SDB sont cycliques, je pourrais m’arroger le droit de commencer la séquence là où commence l’infinité de décimales de Pi, par pur esprit de provocation…

Mais on n’a pas le droit de faire tout ça; manipuler les infinis mathématiques nécessite des précautions dont je suis incapable. Je vais donc me contenter d’un nombre « presque » univers, tout comme l’Univers astronomique est peut-être infini, mais seule un volume fini nous est accessible : B(10,1’000’000). Dans ce très très grand nombre, il y a une seule fois le nombre formé d’un million de chiffres 5, et l’oeuvre complète de Shakespeare s’y trouve aussi, ainsi que tous les autres livres édités et pas encore écrits, ainsi que toutes les autres informations accumulées par l’humanité puisqu’elles sont en nombre largement inférieur quoique colossal. De plus, comme chaque bloc d’un million de décimales de pi, de e et des autres transcendants y figure aussi, j’ai cette fois rigoureusement le droit de commencer la séquence par le premier million de décimales de pi. J’y tiens ;-)

Note* : en fait c’est fortement suspecté et Bailey et Crandall ont proposé en 2001 une démonstration de la normalité en base 2 de pi, e et d’autres « constantes fondamentales » basée sur une conjecture qu’il reste à prouver. [1]

Références

  1. David H. Bailey and Richard E. Crandall « On the Random Character of Fundamental Constant Expansions », Experiment. Math. Volume 10, Issue 2 (2001), 175-190.
  2. « mots de De Brujin » sur Jeux et Mathématiques (avec un générateur en ligne acceptant les lettres)
  • http://www.hyperbate.com/dernier/ Jean-no

    Dans le film PI, de Darren Aronofsky, un petit génie des maths au cerveau en compote (il est victime de terribles migraines) croit trouver une règle à PI, enfin un rythme. Il devient alors un enjeu pour des juifs orthodoxes et des boursicoteurs, persuadés pour les uns que PI est la clef qui permet d’accéder à Dieu et pour les autres, celle de la prédiction économique. Amusant.

  • http://gloumouth1.free.fr Gloumouth1

    bonjour,
    très intéressant

    grâce à vous, je viens de me rendre compte que l’algo que je m’étais évertué à coder et placer sur mon site :
    http://gloumouth1.free.fr/test/Digicode
    est connu depuis bien longtemps
    http://en.wikipedia.org/wiki/De_Bruijn_sequence

    salutations,
    g.

    • http://drgoulu.com Dr. Goulu

      Ne soyez surtout pas déçu! Trouver soi-même un algo comme ça seulement 50 ans après un matheux, ça doit vous remplir de fierté. Bravo !

      En plus les « séquences de De Bruijn » sont peu connues : peu de pages en français leurs sont consacrées, ce qui fait qu’on ne trouve pas ça simplement en googlant. Pour ma part, j’avais contacté Jean-Paul Delahaye (voir les nombres minéralisés) à ce sujet et même LUI ne connaissait pas et m’a redirigé vers un spécialiste, Jean-Paul Allouche, qui m’a indiqué les SDB. Et là je dois dire que je suis tombé sur le Q en découvrant la puissance/simplicité de la chose.

      En passant, c’est impressionnant ce que les profs, scientifiques, même connus, sont disponibles pour répondre aux questions. Si vous ne trouvez pas en cherchant et en postant votre question sur des forums, n’hésitez pas à envoyer un e-mail à l’auteur d’un article scientifique sur un sujet connexe. Ne soyez pas timide. En science, l’étape No 1 c’est d’apprendre ce qui existe déjà. L’étape 2 aussi. Et la 3. Ce n’est qu’à l’étape N que vous tomberez sur un trou qui n’attend que d’être comblé.

  • http://blog.neamar.fr Neamar

    Tiens, des précisions (plus que) complémentaires :)
    Merci pour ces infos !

  • Sazaju HITOKAGE

    Effectivement ça semble vachement bien ces séquences de De Bruijn.

    J’ai regardé le code de Gloumouth1 et je suis étonné de voir une fonction power(x,y) pour faire x^y … pourquoi ne pas utiliser Math.pow(x,y) ?

    Cela dit j’essaye de comprendre l’algorithme mais j’avoue avoir un peu de mal {‘^_^}. Est-ce que tu as un algorithme (avec preuve si possible) ou des sources où le récupérer ?

    • http://drgoulu.com Dr. Goulu

      En cherchant du code source, je suis tombé sur cette page qui explique une utilisation intéressante des SDB dans les tables de hachage, et plus particulièrement pour la programmation du jeu d’échecs (un sujet qu’il faudrait que je creuse un peu pour bien comprendre…) Le code proprement dit est ici.

      Mais cette page révèle une autre chose intéressante : les séquences de De Brujin pour le binaire ont été découvertes par Camille Flye Sainte-Marie en 1894 déjà!

    • http://gloumouth1.free.fr Gloumouth1

      @Sazaju HITOKAGE

      1) j’avais codé cet algorithme pendant l’été 1999. Peut-être que je me trompe, mais le jdk ne proposait pas Math.pow à l’époque.

      2) pour ce qui est de l’explicitation de l’algorithme, je me souviens juste que je m’étais sévèrement sur ce « problème de digicode », et que j’avais rempli un cahier de brouillon entier avec des matrices avant de trouver le « truc ». Ce code source est malheureusement tout ce qui me reste, et je peinerais probablement autant que vous si je voulais comprendre aujourd’hui pourquoi ce code source est une solution au problème posé.

  • Sazaju HITOKAGE

    Ba, en fait je voulais l’utiliser pour la compression mais ça n’a pas l’air intéressant (compression nulle : autant de bits que le code d’origine dans le meilleur des cas).