Nombre de Graham

Le nombre de Graham, du nom du mathématicien américain Ronald Graham, est un entier naturel connu pour avoir été longtemps le plus grand entier apparaissant dans une démonstration mathématique. 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é. Ainsi ses dix derniers chiffres sont 2 464 195 387Modèle:Refnec.

Le problème de Graham

Exemple d'un cube (en 3 dimensions) coloré en 2 couleurs, contenant un sous-graphe complet planaire monocolore (montré sous le cube). Si l'on remplace l'arête la plus basse de ce sous-graphe par une arête bleue, il n'y a plus aucun tel sous-graphe complet ; ce contre-exemple montre que N* > 3.

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

On ne connait pas encore la réponse à cette question, mais on sait depuis 2003 que ce plus petit n doit être supérieur ou égal à 11 et depuis 2008 qu'il vaut même au moins 13.

Quant aux majorants de ce plus petit n, le meilleur connu en 1971 était

$\begin{array}{ccc}G& =& 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow }3\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow }3\\ & & \underbrace{⋮}\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdot \cdot \uparrow }3\\ & & 12\end{array}\}\text{7 niveaux}$

(il a été (énormément) affiné depuis).

Ce nombre est énorme, mais encore moins que le « nombre de Graham » G ci-dessous. Le nombre G doit sa célébrité et son nom à ce qu'il a été présenté en 1977 par Martin Gardner, dans le Scientific American, comme un majorant dû à Graham, au lieu du majorant bien plus précis ci-dessus, trouvé par Graham et Rothschild.

Définition

Le nombre de Graham est le Modèle:64e de la suite :

$4,3\uparrow \uparrow \uparrow \uparrow 3,3\uparrow \cdots \uparrow 3,3\uparrow \cdots \uparrow 3,\dots$

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 Modèle:64e itérée de la fonction f au point 4.

$\begin{array}{ccc}G& =& 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow }3\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow }3\\ & & \underbrace{⋮}\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdot \cdot \uparrow }3\\ & & 3\uparrow \uparrow \uparrow \uparrow 3\end{array}\}\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\to 3\to 64\to 2<G<3\to 3\to 65\to 2.$

De même, la hiérarchie de croissance rapide permet d'écrire l'encadrement

$f_{\omega +1}(63)<G<f_{\omega +1}(64).$

Voir aussi

Bibliographie

Modèle:En John H. Conway et Richard Guy, Modèle:Langue, Springer-Verlag, 1996, Modèle:P. Modèle:Lire en ligne

Liens externes

• Modèle:Lien vidéo
• Modèle:Lien web