Il existe des nombres si grands que leur simple évocation provoque un vertige mental. Le nombre de Graham, du nom du mathématicien américain Ronald Graham, est l’un d’eux. Pendant près de trois décennies, il a détenu le record officiel du plus grand entier jamais utilisé dans une démonstration mathématique sérieuse. Sa taille dépasse si radicalement tout ce que l’univers physique peut contenir que même tenter de l’écrire dans son intégralité remplirait un volume plusieurs fois supérieur à celui de l’univers observable. Pourtant, ce nombre n’est pas une abstraction vide de sens : il répond à un problème précis de combinatoire, et ses derniers chiffres sont bel et bien connus. Plongeons dans l’histoire de ce géant mathématique, entre théorie de Ramsey, notation des flèches de Knuth et la fascinante personnalité de son inventeur.

Le problème à l’origine du nombre

Le nombre de Graham trouve son origine dans un problème relevant de la théorie de Ramsey, une branche des mathématiques discrètes qui étudie l’apparition inévitable de structures organisées au sein de systèmes désordonnés. Le principe fondamental de cette théorie peut se résumer ainsi : un désordre complet est impossible dès lors que la structure considérée devient suffisamment grande. Frank Ramsey, mathématicien et philosophe britannique, posa les bases de cette théorie en 1930, peu avant sa mort prématurée à l’âge de vingt-six ans.

Le problème spécifique que Graham attaqua dans les années 1970 était le suivant. Considérons un hypercube de dimension n, c’est-à-dire l’équivalent multidimensionnel d’un cube classique. Relions tous les couples de sommets de cet hypercube par des arêtes, de manière à obtenir un graphe complet. Imaginons maintenant que nous colorions chaque arête soit en rouge, soit en bleu. Existe-t-il une dimension n à partir de laquelle, quelle que soit la manière de colorier les arêtes, on trouvera forcément quatre sommets coplanaires dont les six arêtes sont toutes de la même couleur ? En d’autres termes, peut-on garantir l’apparition inévitable d’une structure monochrome dans un espace de dimensions suffisamment élevé, quels que soient les choix de coloration ?

Graham et son collègue Bruce Rothschild démontrèrent en 1971 qu’une telle configuration existe nécessairement au-delà d’une certaine dimension. Mais la borne supérieure qu’ils établirent pour garantir cette propriété était vertigineuse. Le nombre de Graham, noté G, est cette borne supérieure. Il répond à la question de la façon suivante : si la dimension n est supérieure ou égale à G, alors la condition de l’existence d’un sous-graphe complet monochrome à quatre sommets coplanaires est automatiquement satisfaite, quels que soient les choix de coloration.

Ce qui rend ce résultat à la fois brillant et déroutant, c’est que la véritable solution du problème, c’est-à-dire la plus petite dimension à partir de laquelle la propriété s’applique, est probablement un nombre très modeste. On sait aujourd’hui que cette dimension minimale est au moins égale à 13 (grâce aux travaux de Geoffrey Exoo en 2003 et à une amélioration en 2008). Certains chercheurs estiment qu’elle pourrait se situer aux alentours de quelques centaines ou de quelques milliers. L’écart abyssal entre cette valeur probablement petite et le nombre de Graham illustre de manière spectaculaire la différence entre une borne supérieure et une solution exacte en mathématiques. Nous savons que la réponse existe et qu’elle est inférieure à G, mais la déterminer précisément demeure hors de portée, même avec les ordinateurs les plus puissants.

La notation des flèches de Knuth

Pour comprendre la taille du nombre de Graham, il faut d’abord abandonner l’idée de l’écrire en notation scientifique classique. Cette notation, qui exprime les nombres sous la forme a multiplié par dix puissance b, atteint rapidement ses limites. Le nombre d’atomes dans l’univers observable est d’environ 10 puissance 80, un nombre que l’on peut encore écrire sur une ligne. Mais dès que l’on cherche à exprimer des valeurs bien plus grandes, la notation scientifique devient elle-même insuffisante.

Donald Knuth, l’un des géants de l’informatique théorique, proposa dans les années 1970 une notation par flèches vers le haut, dite notation des flèches de Knuth, spécialement conçue pour décrire des nombres gigantesques. Cette notation généralise l’idée des opérations arithmétiques élémentaires selon une séquence logique. L’addition répétée donne la multiplication. La multiplication répétée donne l’exponentiation. L’exponentiation répétée, ou itération de l’exponentiation, s’appelle la tétration et se note avec deux flèches. La tétration répétée, ou itération de la tétration, s’appelle la pentation et se note avec trois flèches. Et ainsi de suite.

Prenons un exemple simple pour illustrer cette progression. L’expression 3 flèche 3 signifie 3 puissance 3, ce qui donne 27. L’expression 3 double flèche 3 signifie 3 puissance 3 puissance 3, c’est-à-dire 3 puissance 27, soit environ 7 600 milliards. L’expression 3 triple flèche 3 signifie 3 tétration 3, soit une tour de puissance de 3 répétée 3 fois : 3 puissance 3 puissance 3, soit 3 puissance 7 600 milliards environ. Ce nombre possède déjà plus de 3 600 milliards de chiffres dans son écriture décimale. Et nous n’en sommes qu’à 3 triple flèche 3. Le nombre de Graham commence là où ces opérations deviennent proprement hallucinantes.

Définition récursive du nombre de Graham

Le nombre de Graham est défini de manière récursive à l’aide de la notation des flèches de Knuth. La construction procède par étapes, chaque étape étant d’une complexité si supérieure à la précédente que l’esprit humain peine à suivre la progression au-delà des premiers niveaux.

Définissons d’abord une valeur g1. Celle-ci vaut 3 quadruple flèche 3, c’est-à-dire 3 suivie de quatre flèches, puis du second 3. En clair, il s’agit de trois flèches entre deux trois, mais répété un nombre de fois lui-même défini par une triple flèche. La seule manière de conceptualiser g1 est de le décomposer en étapes. Commençons par écrire 3 triple flèche 3, que nous appellerons A. Ce nombre A, rappelons-le, est déjà si grand qu’il possède des milliards de milliards de chiffres. Ensuite, g1 vaut 3 suivi de A flèches, puis du second 3. En d’autres termes, pour calculer g1, il faut appliquer l’opération de tétration non pas trois ou quatre fois, mais un nombre de fois correspondant à A, lui-même un nombre colossal.

Le résultat g1 est un nombre d’une taille déjà inimaginable. Mais la suite est plus vertigineuse encore. Posons g2 égal à 3 suivi de g1 flèches, puis du second 3. Cela signifie que le nombre de flèches entre les deux trois qui définissent g2 est g1 lui-même, c’est-à-dire le nombre colossal que nous venons à peine d’effleurer. Chaque étape de cette construction utilise le résultat de l’étape précédente comme nombre de flèches de l’opération suivante. g3 égale 3 suivi de g2 flèches, puis du second 3. Et ainsi de suite, jusqu’à g64. Le nombre de Graham G est exactement g64.

Cette progression récursive est ce qui rend le nombre de Graham si vertigineux. Dès g1, nous sommes confrontés à un nombre que l’univers observable ne peut contenir. g2 est si grand que le simple fait d’écrire g1 sur une ligne avec des chiffres décimaux remplirait tout l’univers connu. Pourtant, g2 est encore infiniment petit comparé à ce qui vient après. Chaque itération de cette fonction fait bondir la taille du nombre dans des proportions qui défient toute tentative de visualisation mentale. Au bout de soixante-quatre itérations, nous obtenons G.

Le paradoxe des derniers chiffres

L’un des aspects les plus fascinants du nombre de Graham est que, malgré son immensité, ses derniers chiffres en base dix sont connus. Ce paradoxe apparent résulte de propriétés mathématiques liées aux congruences et à l’arithmétique modulaire. Sans avoir besoin de calculer le nombre dans son intégralité, les mathématiciens peuvent déterminer ses derniers chiffres par des raisonnements sur les puissances de 3 modulo certaines puissances de 10.

Ainsi, les dix derniers chiffres du nombre de Graham sont 2 464 195 387. Cette connaissance partielle offre une fenêtre minuscule mais réelle sur un édifice numérique par ailleurs totalement inaccessible. C’est un peu comme connaître la dernière lettre d’un livre dont on ne peut lire aucune page. On peut vérifier que ce nombre se termine effectivement par 7, qu’il est impair, et l’on peut même effectuer certaines opérations arithmétiques sur ses terminaisons, sans jamais pouvoir appréhender sa totalité.

Cette propriété a alimenté l’imagination des passionnés de mathématiques depuis la publication du nombre par Martin Gardner dans sa célèbre rubrique du magazine Scientific American en 1977. Gardner, l’un des plus grands vulgarisateurs scientifiques du vingtième siècle, présenta le nombre de Graham à un large public pour la première fois, provoquant un émoi considérable. Le nombre fut inscrit dans le Livre Guinness des records en 1980 comme le plus grand nombre utilisé dans une démonstration mathématique sérieuse.

Au-delà de Graham : TREE(3) et les nombres encore plus grands

Depuis les années 1980, d’autres nombres bien plus grands que le nombre de Graham ont fait leur apparition dans des démonstrations mathématiques. Le plus célèbre d’entre eux est TREE(3), issu d’une variante du théorème des arbres de Kruskal. La fonction TREE, définie par le mathématicien Harvey Friedman, croît à une vitesse proprement stupéfiante, bien supérieure à celle de la suite qui définit le nombre de Graham. TREE(3) est si grand que le nombre de Graham paraît, à côté de lui, aussi petit que le nombre 1 à côté du nombre de Graham lui-même. Cette comparaison est vertigineuse : si le nombre de Graham est déjà inconcevable, TREE(3) l’est infiniment plus.

D’autres nombres encore plus vastes existent, comme le nombre de Friedman, issu du théorème de Goodstein, ou SCG(13), un autre produit de la théorie des graphes. Ces nombres poussent la notion de finitude à des extrêmes qui flirtent avec les limites de l’indécidabilité. En effet, certains de ces énoncés sont si vastes qu’ils ne peuvent être prouvés dans le cadre de l’arithmétique de Peano, le système axiomatique standard des mathématiques. Le nombre de Graham, aussi colossal soit-il, reste prouvable dans ce système, ce qui le rend en un sens accessible à la raison mathématique classique.

Ronald Graham, l’homme aux multiples talents

Derrière le nombre se cache une personnalité hors du commun. Ronald Lewis Graham, né le 31 octobre 1935 à Taft en Californie, n’était pas seulement un mathématicien de génie. Il était aussi jongleur, trampoliniste, magicien et président de l’Association internationale des jongleurs. Il lui arrivait de dire que jongler était une forme physique de mathématiques. Il a d’ailleurs cosigné un livre, Magical Mathematics, avec le mathématicien et prestidigitateur Persi Diaconis, explorant les liens entre tours de cartes et structures mathématiques.

Son parcours est atypique. Il quitta le lycée sans diplôme pour intégrer l’université de Chicago à quinze ans grâce à une bourse. Après un passage dans l’armée de l’air américaine, stationné en Alaska, il obtint un doctorat en mathématiques à l’université de Californie à Berkeley en 1962 sous la direction de Derrick Lehmer. Pour financer ses études, il se produisait dans un cirque avec un numéro de trampoline. Il continua à exécuter des figures acrobatiques complexes sur trampoline bien passé ses soixante ans.

Il passa l’essentiel de sa carrière aux laboratoires Bell, où il dirigea le département des sciences de l’information pendant 37 ans, avant de rejoindre l’université de Californie à San Diego. Il y fut élu professeur de l’année par les étudiants en 2015, à l’âge de 79 ans. Ses travaux portèrent sur la théorie de Ramsey, la recherche opérationnelle, l’algorithmique et la géométrie computationnelle. Il fut président de l’American Mathematical Society et de la Mathematical Association of America, les deux plus grandes associations mathématiques des États-Unis. Il reçut le prix Steele pour l’ensemble de sa carrière en 2003. Il décéda le 6 juillet 2020 à son domicile de La Jolla, des suites d’une maladie pulmonaire chronique, à l’âge de 84 ans. La veille de sa mort, il contactait encore des collègues pour parler de mathématiques.

Graham est également connu pour le nombre d’Erdős, qui mesure la proximité collaborative entre mathématiciens à travers leurs publications communes avec Paul Erdős. Le nombre d’Erdős de Graham était de 1, ce qui signifie qu’il avait coécrit des articles directement avec Erdős. Ensemble, ils ont publié des dizaines de travaux, contribuant à façonner la combinatoire moderne. Cette collaboration illustre la culture de la recherche collective qui caractérise les mathématiques contemporaines.

Ce que le nombre de Graham nous apprend

Au-delà de l’exploit technique que représente sa construction, le nombre de Graham enseigne quelque chose de fondamental sur la nature des mathématiques. Il montre que le fini n’est pas nécessairement le petit. Un nombre parfaitement défini, fini, entier, peut être si grand qu’il dépasse toute capacité de représentation physique, tout en restant parfaitement accessible au raisonnement abstrait. Cette découverte résonne profondément avec la thèse du philosophe Eugène Wigner sur l’incroyable efficacité des mathématiques à décrire la réalité.

Le nombre de Graham illustre également la différence entre existence et construction. Nous savons que la solution du problème de Ramsey dont il est issu existe, et nous en connaissons une borne supérieure. Mais déterminer la solution exacte relève d’une difficulté telle qu’elle demeure hors de portée. Cette situation est fréquente en mathématiques modernes : on peut démontrer l’existence d’un objet sans être capable de l’exhiber concrètement. Le nombre de Graham porte cette tension à son paroxysme.

Enfin, il nous rappelle que l’imagination mathématique peut explorer des territoires que la physique, par essence limitée par les dimensions de l’univers observable, ne pourra jamais atteindre. Le nombre de Graham n’a pas d’existence physique. Il n’y a pas G atomes dans l’univers, pas G secondes depuis le Big Bang, pas G positions possibles pour une particule quantique. Pourtant, G existe bel et bien dans l’univers mathématique, comme un monument de la pensée pure, accessible à quiconque accepte de suivre le fil du raisonnement récursif qui le définit.

Et si l’on vous dit que quelqu’un a calculé les derniers chiffres du nombre de Graham, ne souriez pas. C’est mathématiquement vrai. Le nombre lui-même demeure insaisissable, mais ses dix derniers chiffres sont 2 464 195 387. Une petite fenêtre sur l’infini.

Sources

• Graham, R.L. et Rothschild, B.L. (1971). Ramsey’s theorem for n-parameter sets. Transactions of the American Mathematical Society, 159, 257-292.
• Gardner, M. (1977). Mathematical Games. Scientific American, 237(5), 18-28.
• Knuth, D.E. (1976). Mathematics and Computer Science: Coping with Finiteness. Science, 194(4271), 1235-1242.
• Graham, R.L., Rothschild, B.L. et Spencer, J.H. (1990). Ramsey Theory (2e éd.). Wiley-Interscience.
• Exoo, G. (2003). A Lower Bound for the Ramsey Number R(4,4;3). The Electronic Journal of Combinatorics, 10(1), N8.
• Graham, R.L. et Chung, F. (1998). Erdős on Graphs: His Legacy of Unsolved Problems. A K Peters.
• Diaconis, P. et Graham, R.L. (2011). Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks. Princeton University Press.
• Friedman, H. (2002). Enormous Integers in Real Life. Communication personnelle, Université d’État de l’Ohio.