Nombre de Graham : Mathématique

D	L	M	M	J	V	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

« Ronald Graham | Page d'accueil | Parcours de Graham »

21/11/2015

Nombre de Graham

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¹. 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).

Sommaire

[masquer]

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 à 2ⁿ sommets. Si l'on colore chacune des 2^n–1(2ⁿ– 1) arêtes du graphe en bleu ou en rouge, quelle est la plus petite valeur de n telle que pour chaque façon de colorer le graphe, il existe un sous-graphe complet monochrome sur quatre sommets coplanaires ?

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⁴

$left . begin{matrix} underbrace{2 uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow uparrow 3} \ underbrace{2 uparrow dots dots dots uparrow 3} \ {vdots } \ underbrace{qquad qquad qquad } \ {2 uparrow dots dots uparrow 3} end{matrix} right } text{7 niveaux}$

(il a été 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 (en).

Définition[modifier | modifier le code]

Le nombre de Graham est le 64^e terme de la suite :

4, 3uparrowuparrowuparrowuparrow3, 3uparrowcdotsuparrow3, 3uparrowcdotsuparrow3, 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 64^e itérée de la fonction f au point 4.

left. begin{matrix} G &=&3underbrace{uparrow uparrow cdotscdotscdotscdotscdots uparrow}3 \ & &3underbrace{uparrow uparrow cdotscdotscdotscdots uparrow}3 \ & &underbrace{qquad;; vdots qquad;;} \ & &3underbrace{uparrow uparrow cdotscdotcdot uparrow}3 \ & &3uparrow 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

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

Notes et références[modifier | modifier le code]

(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).

↑ 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) Geoffrey Exoo, « A Euclidean Ramsey Problem », Discrete Comput. Geom., vol. 29, n^o 2,‎ 2003, p. 223-227 (DOI 10.1007/s00454-002-0780-5).
↑ (en) Jerome Barkley, « Improved lower bound on an Euclidean Ramsey problem »,‎ 2008 (arXiv 0811.1055).
↑ (en) R. L. Graham et B. L. Rothschild, « Ramsey's theorem for n-parameter sets », Trans. Amer. Math. Soc., vol. 159,‎ 1971, p. 257-292 (lire en ligne [archive]) (p. 290).
↑ (en) Mikhail Lavrov, Mitchell Lee et John Mackey, « Graham's number is less than 2 ↑↑↑ 6 »,‎ 2013 (arXiv 1304.6910). Commentaires [archive] de David Roberts : « The title of this paper is misleading […] it is the exact solution to this problem that they are calling 'Graham's number' […] In fact the bound given in the title, 2↑↑↑6, is a simplification, and not the smallest bound arrived at in the paper, which is 2↑↑2↑↑2↑↑9 […] In terms of the function F of Graham and Rothschild, the LLM bound is between F(4) and F(5) ».
↑ (en) M. Gardner, « Mathematical Games », Scientific American, vol. 237,‎ 1977, p. 18-28 (DOI 10.1038/scientificamerican1177-18). Cette inexactitude est reprise dans (en) Eric W. Weisstein, « Graham's Number [archive] », MathWorld.
↑ Pour plus de détails, voir (en) John Baez, « A while back I told you about Graham's number... » [archive],‎ janvier 2013.