ArithmétiqueNotion · Glossaire
nombre de Graham
Le nombre de Graham est un entier naturel fini, défini comme le 64e terme d'une récurrence fondée sur la notation à flèches de Knuth et utilisé comme borne supérieure dans un problème de théorie de Ramsey. Sa croissance itérée le rend immensément plus grand que ce qu'une écriture décimale ou la notation scientifique permettent de représenter en pratique : sa définition compacte permet de le désigner et d'en étudier certaines informations sans en écrire tous les chiffres.
Sommaire
Ce que vous allez apprendre
- Lire la notation à une et deux flèches sur un exemple entièrement calculé.
- Identifier la suite de 64 termes qui définit le nombre de Graham.
- Distinguer cet entier fini de l'infini et d'un prétendu plus grand nombre.
- Relier les dix derniers chiffres aux calculs de congruences sans développer l'entier.
En clair
Écrire 3 × 3 demande une multiplication. Écrire 33 remplace cette opération par trois facteurs égaux à 3. Les flèches de Knuth poursuivent cette escalade : une flèche code une puissance, deux flèches une tour de puissances, puis chaque flèche supplémentaire répète l'opération précédente.
Le nombre de Graham naît en répétant ce mécanisme avec un nombre de flèches qui devient lui-même gigantesque. Il reste pourtant un entier fini, avec une écriture décimale déterminée, même si celle-ci ne peut pas être déployée matériellement.
Définition
Le nombre de Graham, noté ici G, est un entier naturel fini défini par une suite de 64 termes. La notation à flèches de Knuth compacte des itérations d'opérations : pour deux entiers positifs a et b, une flèche donne la puissance . Deux flèches répètent les puissances ; trois flèches répètent l'opération à deux flèches, et ainsi de suite.
Le premier terme, nommé g1, place quatre flèches entre deux 3. Pour chaque rang suivant n, le nombre de flèches entre les deux 3 est le terme précédent. La construction complète est :
L'exposant au-dessus de la flèche indique ici le nombre de flèches, et non une puissance de la flèche.
Cet entier est apparu dans une démonstration liée à la théorie de Ramsey. Il fut un temps le plus grand entier connu employé dans une preuve rigoureuse. Sa définition n'exige pas d'écrire tous ses chiffres : des calculs modulaires permettent néanmoins d'en déterminer des chiffres terminaux, dont les dix derniers en base dix.
Un exemple, pas à pas
Prenons comme données la base 3, une puis deux flèches, et le fait que les chiffres des unités des puissances de 3 suivent un cycle de longueur 4. L'objectif est de calculer les deux premières marches visibles de l'itération.
1. Une flèche signifie une puissance : .
2. Deux flèches et un second argument égal à 2 donnent .
3. Avec un second argument égal à 3, la tour gagne un étage : . La figure matérialise cette augmentation sans prétendre dessiner le nombre de Graham lui-même.
4. Pour contrôler le chiffre des unités, 27 laisse le reste 3 dans la division par 4. Le résultat doit donc finir comme 33, par 7 ; c'est bien le cas. Dès quatre flèches, le même principe est itéré à un niveau où l'écriture décimale n'est plus une méthode praticable.
En pratique
Dans la démonstration issue de la théorie de Ramsey, le nombre de Graham sert à formuler une borne finie. Lorsque seule l'existence d'une borne rigoureuse compte, sa définition récursive est préférable à une impossible expansion décimale.
Pour comparer des vitesses de croissance, on part de petits arguments calculables, comme 3 ↑ 3 et 3 ↑↑ 3. La notation scientifique convient aux puissances ordinaires ; les flèches deviennent utiles lorsque l'opération elle-même est répétée.
Pour étudier les derniers chiffres, on ne développe pas l'entier. On travaille avec les restes modulo 10, 100 ou une puissance de 10 adaptée au nombre de chiffres cherchés. Ce choix conserve l'information terminale et écarte l'essentiel de la taille.
À ne pas confondre
Avec l'infini. Le nombre de Graham est un entier naturel déterminé : on peut lui ajouter 1 et obtenir un entier plus grand. L'infini n'est pas un entier terminal de cette suite d'opérations.
Avec « le plus grand nombre ». Aucun entier naturel n'est le plus grand, puisque son successeur le dépasse. L'affirmation historique porte seulement sur le plus grand entier alors connu dans une démonstration rigoureuse, pas sur un maximum absolu.
Avec une grande puissance de 10. Une écriture comme 10100 fixe une seule exponentiation. Le nombre de Graham repose sur plusieurs niveaux d'itération, puis sur 64 étapes où le terme précédent fixe le nombre de flèches.
Limites et pièges
Une borne n'est pas nécessairement la valeur exacte cherchée. L'apparition du nombre de Graham dans une preuve établit qu'un entier fini suffit dans le problème concerné. Elle ne signifie pas que cette valeur est le seuil minimal du problème de Ramsey.
Le record est historique. La formule « plus grand entier connu » doit conserver la précision « pendant un temps » et le contexte d'une démonstration mathématique. Sans ces deux restrictions, l'énoncé devient faux.
Connaître dix chiffres ne revient pas à écrire le nombre. Les dix derniers chiffres en base dix peuvent être calculés par congruences sans connaître toute l'expansion décimale. Il faut donc préciser la base et le côté observé.
Le nombre de flèches change à chaque rang. À partir de g2, ce nombre est égal au terme précédent ; il ne reste ni fixé à quatre ni égal au rang. Pour éviter l'erreur, il faut relire la récurrence avant toute comparaison.
Pour aller plus loin
La fiche puissances itérées de Knuth développe le langage compact qui transforme les répétitions de puissances en suites de flèches.
La fiche théorie de Ramsey replace cette borne immense dans la recherche d'ordre inévitable au sein de configurations combinatoires.
La fiche grand nombre compare les façons usuelles de nommer et d'écrire des nombres bien plus modestes.
L'article L’ordre selon Ramsey prolonge le contexte combinatoire dans lequel une structure finit par apparaître malgré le désordre initial.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres