Voir la source de 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<ref>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]].</ref>. 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 387{{Refnec|date=21 mai 2024}}.

== Le problème de Graham ==
[[Image:GrahamCube.svg|right|thumb|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]] :

{{Énoncé|Soit un [[hypercube]] de dimension ''n'' dont on relie tous les couples de sommets pour obtenir un [[graphe complet]] à 2{{exp|''n''}} sommets. Si l'on colorie chacune des 2{{exp|''n''–1}}(2{{exp|''n''}} – 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 colorier le graphe, il existe un sous-graphe complet [[monochrome]] sur quatre sommets [[coplanaire]]s ?}}

On ne connait pas encore la réponse à cette question, mais on sait depuis 2003<ref>{{Article|lang=en|nom=Exoo|prénom=Geoffrey|année=2003|titre=A Euclidean Ramsey Problem|revue=[[Liste des journaux scientifiques en mathématiques#D|Discrete Comput. Geom.]]|vol=29|numéro=2|p.=223-227|doi=10.1007/s00454-002-0780-5}}.</ref> que ce plus petit ''n'' doit être supérieur ou égal à 11 et depuis 2008<ref>{{Lien web|lang=en|arxiv=0811.1055|auteur=Jerome Barkley|titre=Improved lower bound on an Euclidean Ramsey problem|année=2008}}.</ref> qu'il vaut même au moins 13.

Quant aux [[Majorant ou minorant|majorants]] de ce plus petit ''n'', le meilleur connu en 1971 était<ref>{{Article|lang=en|auteur=R. L. Graham|auteur2=B. L. Rothschild|titre=Ramsey's theorem for ''n''-parameter sets|revue=[[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]]|vol=159|p.=257-292|année=1971|url=http://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/}} ({{p.|290}}).</ref>
:<math>
\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 \\
    & &12
 \end{matrix} 
\right \} \text{7 niveaux}
</math>
(il a été (énormément) affiné depuis<ref>{{Lien web|lang=en|nom1=Lavrov|prénom1=Mikhail|nom2=Lee|prénom2=Mitchell|nom3=Mackey|prénom3=John|titre=Graham's number is less than 2 ↑↑↑ 6|année=2013|arxiv=1304.6910}}. [https://selectedpapers.net/topics/RamseyTheory Commentaires] de David Roberts : {{Citation étrangère|lang=en|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)}}.</ref>).

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<ref>{{Article|lang=en|auteur=M. Gardner|titre=Mathematical Games|revue=Scientific American|vol=237|p.=18-28|année=1977|doi=10.1038/scientificamerican1177-18}}. Cette inexactitude est reprise dans {{MathWorld|nom_url=GrahamsNumber|titre=Graham's Number}}.</ref>, au lieu<ref>Pour plus de détails, voir {{Lien web|lang=en|url=https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ|auteur=[[John Baez]]|mois=1|année=2013|titre=A while back I told you about Graham's number...}}.</ref> du majorant bien plus précis ci-dessus, trouvé par Graham et [[Bruce Lee Rothschild|Rothschild]].

== Définition ==

Le nombre de Graham est le {{64e|terme}} de la suite :

<center> <math>4,\ 3\uparrow\uparrow\uparrow\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \ldots</math> </center>

où chaque terme est le nombre de flèches du terme suivant, en utilisant la [[Notation des puissances itérées de Knuth|notation des flèches de Knuth]].

De façon équivalente, soit ''f''(''n'') = [[Hyperopération|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.

:<math> 
\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}
</math>

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
<center> <math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.</math> </center>
De même, la [[hiérarchie de croissance rapide]] permet d'écrire l'encadrement
<center><math>f_{\omega+1}(63)<G<f_{\omega+1}(64).</math></center>

== Notes et références ==
{{Traduction/Référence|en|Graham's number|13345495|type=note}}
{{Références}}

== Voir aussi ==
=== Bibliographie ===
{{en}} [[John Horton Conway|John H. Conway]] et [[Richard Guy]], ''{{Langue|en|The Book of Numbers}}'', [[Springer Science+Business Media|Springer-Verlag]], 1996, {{p.|61-62}} {{lire en ligne|lien=https://books.google.fr/books?id=0--3rcO7dMYC&pg=PA61}}

=== Liens externes ===
* {{Lien vidéo |people=Mickaël Launay|année=2014|titre=Des nombres grands, TRÈS grands|émission=|chaine=MicMaths|durée=16|url=https://www.youtube.com/watch?v=oqMYAVV-hsA|medium=you tube|éditeur=|lieu=|consulté le=31 janvier 2025}}
* {{Lien web|langue=en|url=http://isu.indstate.edu/ge/GEOMETRY/cubes.html|titre=A Ramsey Problem on Hypercubes|auteur=Geoffrey Exoo}}

{{portail|mathématiques}}

[[Catégorie:Grand nombre]]
[[Catégorie:Nombre remarquable|Graham]]

[[pl:Notacja strzałkowa#Liczba Grahama]]