Le Nombre de Graham

La mathématique c’est l’art de rendre compliquées des choses simples

Cette citation prendra ici tout son sens, nous verrons ainsi qu’un problème portant sur le coloriage de carrés amènera à la création du plus grand entier jamais utilisé – jusqu’à peu – dans une démonstration sérieuse. Nous nous intéresserons également à l’homme qui l’imagina: Ron Graham.

Beaucoup de mathématiciens sont fascinés par le Nombre de Graham qui est d’une incroyablement vertigineuse grandeur. Mais qu’est-ce ce nombre ?

Graham carréPrenons un carré, comme il s’agit d’une figure bidimensionnelle le nombre de sommets est 2^2 = 4. En connectant toutes les paires possible de sommets nous créons deux nouveaux segments. Le nombre total de segments correspond alors au coefficient binomial \binom{4}{2}=6. On peut alors colorier ces arrêtes en bleu et en rouge de la façon ci-contre, il s’agit d’une possibilité parmi tant d’autres. On peut rechercher des configurations particulières mais le carré est cependant trop « petit », nous avons besoin d’une dimension supplémentaire.
Graham cubeEn dimension trois, nous considérons un cube à 8 sommets et à 28 segments reliant toutes les paires de sommets possibles. Nous pouvons à nouveau procéder à un coloriage mais cette fois nous allons éviter une configuration, quatre points sur le même plan ne peuvent être reliés par 6 arrêtes de même couleur.
Le défi est de réussir un tel coloriage dans le dimension la plus grande possible. En dimension quatre cela correspond à un hypercube qu’on peu représenter en perspective cavalière en réalisant une translation du dessin précédent.

ezgif.com-video-to-gif.gif

Construction d’un hypercube en perspective

Il suffit ensuite de rejoindre les sommets. La figure comporte alors 16 sommets et 120 segments.
Combien y a-t-il de coloriages possibles, il y a deux possibilités pour chacune des arêtes soit 2*2*2*2*2*2*2... ou 2^{120}. Des ordinateurs ont conclu qu’on pouvait en effet colorier un hypercube en évitant la configuration décrite précédemment.
Elle peut en fait être évitée pour des « cubes » de dimension 2, 3, 4, 5, 6, 7… mais peut-on trouver un coloriage respectant cette contrainte dans toutes les dimensions ? La réponse est non, si la dimension est assez grande, cela est mathématiquement impossible.
La dimension à partir de laquelle il a été démontré que cela se passe effectivement est la « Nombre de Graham-ème dimension ». Mais peut-être qu’il est impossible d’éviter cette contrainte dans des dimensions inférieures. Une solution a été calculée jusqu’à la douzième dimension, après celle-ci nous ne savons pas. Un cube de dimension treize présente 8192 sommets et 33 550 336 segments soit 2^{33550336} coloriages possibles.

Ces nombres sont totalement inimaginables mais minuscules comparés au Nombre de Graham. Jusqu’à très récemment, ce-dernier détint le titre de plus grand nombre utilisé dans une démonstration mathématique. A quel point est-il grand ?
Il est évident qu’il ne peut être écrit ici et aucune notation « classique » tel que la puissance ou l’empilement de puissances ne peut le faire. Il convient alors d’introduire une nouvelle notation: les puissances itérées de Knuth. Pour exprimer des nombres de plus en plus grand il est commun d’avoir recours à une opération qui constitue une répétition d’une autre opération. La puissance répète la multiplication qui répète l’addition. Pour répéter la puissance, Knuth décida d’introduire une notation plus pratique à utiliser, 3devient 3↑n.
3↑↑n signifie alors 3↑(3↑(3↑(…))) où le chiffre 3 apparaît n fois, cela est équivalent à 3333333333333333où la encore le chiffre 3 apparaît n fois. Ainsi 3↑↑3 = 3↑(3↑3) = 3↑(33) = 33= 7 625 597 484 987.
La rapidité de croissance de ces nombres est assez inimaginable, 3↑3 vaut 27 alors que 3↑↑3 vaut plus de 7 billions. Que se passe t-il avec trois flèches ? 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑(333) = 3↑↑(7 625 597 484 987) = 3333333333333333avec 7 billions de 3… Le résultat est constitué de plus de 3,6 billions de chiffres, 3↑↑↑3 nous donne un chiffre si grand qu’il devient impossible à écrire, sauf peut-être comme ça: 1,258014298121*10^{3638334640024}.
Ajoutons une flèche,

ezgif.com-video-to-gif.gif

Representation de 3↑↑↑↑3 par Numberphile

3↑↑↑↑3 = 3↑↑↑(3↑↑↑3) $\simeq$ 3↑↑↑(103 638 334 640 024$\simeq$ 3↑↑(3↑↑(3↑↑(…(3↑↑3)) avec 103 638 334 640 024 fois le chiffre 3. Il en résulte une opération qu’il vaut mieux ne pas essayer d’appréhender, son gigantisme dépasse la raison. Chacun des nombres inimaginables que nous avons vu constitue – et cela un nombre 3↑↑↑3 fois – la hauteur d’une tour de puissances. Appelons ce monstre G1, est-ce le Nombre de Graham ? Non, il est bien trop petit pour l’être.

Imaginons désormais qu’il y ait 3↑↑↑↑3 flèches, – pas décimales ni puissances mais flèches ! – entre deux trois; 3↑↑…↑↑3. Nous avons vu que 3↑↑↑3 était incommensurable et pouvait tout juste s’écrire, que 3↑↑↑↑3 défiait la raison humaine alors imaginez que ce dernier nombre constitue le nombre de flèches entre deux 3: c’est G2. Imaginez ce nombre dont même le nombre de flèches nécessaire pour écrire son calcul est inqualifiable…

Imaginez que ce nombre (G2) soit le nombre de flèches entre deux trois et que le résultat (G3) de ce calcul soit le nombre de flèches entre deux trois et que le résultat (G4) de ce calcul soit le nombre de flèches entre deux trois … 3cug2fvRépétez ce processus 64 fois, là où une itération défiait les limites du langage, le nombre de flèches croit d’une façon indicible et ajouter ne serait-ce qu’une flèche fait exploser le nombre alors imaginez… Le résultat de ces 64 étapes (G64) est ce qu’on appelle en hommage à Ronald Graham: le Nombre de Graham. Il est inutile de dire que nous ne pouvons et pourrons jamais calculer ce nombre mais il termine par un 7, et plus précisément des centaines des chiffres le terminant ont été calculés car sa fin est totalement pédictible. Cette-dernière peut être calculée à l’aide de ce qu’on appelle: l’arithmétique modulaire et plus particulièrement le théorème d’Euler.

– … but the first digits I don’t know
– It’s your number, what do you want to the first digit to be ?
– Eh… Well, in binary it’s 1!

Interview de Ronald Graham par Numberphile

1
C’est ce nombre de dimensions qui est nécessaire pour forcer l’apparition dune simple configuration colorée entre points et segments. Ou plus exactement ce nombre est compris entre 13 et le Nombre de Graham révélant un fossé dans notre connaissance du problème.

Comme il est impossible d’appréhender le nombre, essayons d’appréhender l’homme.

Ronald Lewis Graham est né le 31 octobre 1935 à Taft en Californie. Il obtint en 1962 et sous la direction de Derrick Lehmer son doctorat en mathématiques à l’université de Californie à Berkeley.
En 1972  il a inventé le parcours de Graham pour résoudre le problème du calcul de l’enveloppe convexe d’un ensemble de points dans le cadre de la géométrie algorithmique .
C’est en 1977, dans un article traitant d’un problème de la théorie de Ramsey qu’il introduit pour la première fois le nombre qui porte aujourd’hui son nom, il s’agissait – comme nous l’avons vu – de la borne supérieure de la solution.
Six ans plus tard, il épousa la mathématicienne américaine spécialiste de la théorie des graphes Fan Chung. Cette-dernière est professeur titulaire de la chaire Akamai de « mathématiques de l’Internet » à l’université de Californie à San Diego.

chung_3

Ronald Graham et Fan Chung

Entre 1993 et 1994, Graham fut président de l’American Mathematical Society (AMS).
Cinq années plus tard, il est devenu membre émérite de l’Association for Comptine Machinery et reçu en 2003 le prix Leroy P. Steele pour l’ensemble de sa carrière. il fut également lauréat du prix Pólya, l’année même où le prix était décerné pour la première fois. La médaille Euler, le prix Lester R. Ford et le prix Carl Allendoerfer s’ajoutant à la liste.
Il fut présenté dans Ripley’s Believe It or Not non seulement comme « l’un des plus célèbres mathématiciens du monde », mais aussi comme « un trampoliniste et un jongleur très doué ». Il fut également président de l’International Jugglers’ Association (Association Internationale de Jongleurs).

En 2003, Ronald Graham avait publié environ 300 articles et cinq livres, dont Concrete Mathematica coécrit par Donald Knuth.

Pour conclure, il semble intéressant de comprendre pourquoi cette vertigineuse borne supérieure est digne d’intérêt. En mathématique, le voyage est souvent plus important que la destination. La méthode utilisée pour démontrer que le Nombre de Graham constitue un limite permettra sûrement de revoir cette-dernière à la baisse afin de trouver la solution exacte. De plus le Nombre de Graham constitue un défi à la comprenions humaine et nous met face aux limites – parfois reniées – de notre nature humaine.

Sources

Pour aller plus loin…


  1. – … mais les premiers chiffres je ne sais pas
    – C’est votre nombre, que voulez-vous que le premier chiffre soit ?
    – Eh… Bien, en binaire c’est 1! 

 

Publicités

Une réflexion sur “Le Nombre de Graham

  1. Pingback: Le fascinant nombre π | Abstraction mathématique

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s