Nombre de Graham

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le nombre de Graham, du nom du mathématicien Ronald Graham, est un entier naturel connu pour avoir été longtemps le plus grand entier apparaissant dans une démonstration mathématique[note 1]. Il est beaucoup trop grand pour être écrit grâce à la notation scientifique et nécessite une notation permettant d'écrire de très grands nombres. Toutefois, il est possible d'obtenir ses derniers chiffres sans trop de difficulté (les dix derniers sont …2464195387).

Le problème de Graham[modifier | modifier le code]

Le nombre de Graham entretient un lien avec une branche des mathématiques connue sous le nom de théorie de Ramsey :

« Soit un hypercube de dimension n dont on relie tous les couples de sommets pour obtenir un graphe complet à 2n sommets (et donc 2n–1(2n – 1) arêtes). Si l'on colorie chacune des arêtes du graphe en bleu ou en rouge, quelle est la plus petite valeur de n pour laquelle toutes les façons de colorier le graphe permettent d'obtenir quatre sommets coplanaires tels que le sous-graphe complet qu'ils déterminent ait toutes ses arêtes de la même couleur ? »

On ne connait pas encore la réponse à cette question, mais l'on sait qu'elle ne peut pas être supérieure au nombre de Graham.

Dans son livre Penrose Tiles to Trapdoor Ciphers sorti en 1989, Martin Gardner a écrit que « les spécialistes de la théorie de Ramsey estiment que la valeur du nombre de Ramsey pour ce problème est 6, faisant peut-être du nombre de Graham la pire plus petite borne supérieure jamais découverte ». En 2003, Geoffrey Exoo, de l'université de l'Indiana, a démontré que le résultat ne peut être inférieur à 11 et pense même que la réponse est plus grande. En 2008, Jerome Barkley démontre qu'il ne peut être inférieur à 13. Les bornes connues sont donc pour l'instant pour la solution N* : 13 ≤ N* ≤ N'.

Définition[modifier | modifier le code]

Le nombre de Graham est le 65e terme de la suite :

4,\ 3\uparrow\uparrow\uparrow\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \ldots

où chaque terme est le nombre de flèches du terme suivant, en utilisant la notation des flèches de Knuth.

De façon équivalente, soit f(n) = hyper(3,n+2,3) = 3→3→n ; alors le nombre de Graham est la valeur de la 64e itérée de la fonction f au point 4.

 
\left. 
 \begin{matrix} 
  G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\ 
    & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\ 
    & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix} 
\right \} \text{64 niveaux}

Le nombre de Graham G lui-même ne s'exprime pas commodément avec la notation des flèches chaînées de Conway, mais on a l'encadrement

 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.

Note et référence[modifier | modifier le code]

  1. Vers la fin des années 1980, des entiers bien plus grands que le nombre de Graham sont apparus dans plusieurs démonstrations mathématiques sérieuses, par exemple en relation avec les formes finies du théorème de Kruskal découvertes par Harvey Friedman.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham's number » (voir la liste des auteurs).

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

(en) John H. Conway et Richard Guy, The Book of Numbers, Springer-Verlag, 1996, p. 59-62 [lire en ligne]

Liens externes[modifier | modifier le code]