Nombre de Graham

La théorie de Ramsey est un domaine des mathématiques qui pose des questions comme les suivantes :

Supposons que nous dessinions un certain nombre de points, et que nous relions chaque paire de points par une ligne. Certaines lignes sont bleues et d'autres sont rouges. Pouvons-nous toujours trouver 3 points pour lesquels les 3 lignes qui les relient sont toutes de la même couleur ?

Il s'avère que pour ce simple problème, la réponse est "oui" lorsque nous avons 6 points ou plus, quelle que soit la couleur des lignes. Mais lorsque nous avons 5 points ou moins, nous pouvons colorer les lignes de manière à ce que la réponse soit "non".

Le numéro de Graham provient d'une variation sur cette question.

Encore une fois, disons que nous avons quelques points, mais qu'ils sont maintenant les coins d'un hypercube à n dimensions. Ils sont encore tous reliés par des lignes bleues et rouges. Pour 4 points, il y a 6 lignes qui les relient. Pouvons-nous trouver 4 points qui se trouvent tous sur un plan, et les 6 lignes qui les relient sont toutes de la même couleur ?

En demandant que les 4 points se trouvent dans un avion, nous avons rendu le problème beaucoup plus difficile. Nous aimerions savoir : pour quelles valeurs de n la réponse est "non" (pour une certaine façon de colorer les lignes), et pour quelles valeurs de n la réponse est "oui" (pour toutes les façons de colorer les lignes) ? Mais ce problème n'a pas encore été complètement résolu.

En 1971, Ronald Graham et B. L. Rothschild ont trouvé une réponse partielle à ce problème. Ils ont montré que pour n=6, la réponse est "non". Mais lorsque n est très grand, aussi grand que le nombre de Graham ou plus grand, la réponse est "oui".

L'une des raisons pour lesquelles cette réponse partielle est importante est qu'elle signifie que la réponse est finalement "oui" pour au moins un grand n. Avant 1971, nous n'en savions même pas beaucoup.

Le numéro de Graham est non seulement trop grand pour écrire tous ses chiffres, il est même trop grand pour être écrit en notation scientifique. Pour pouvoir l'écrire, nous devons utiliser la notation ascendante de Knuth.

Nous allons écrire une séquence de chiffres que nous appellerons g1, g2, g3, etc. Chacun sera utilisé dans une équation pour trouver le suivant. g64 est le numéro de Graham.

Tout d'abord, voici quelques exemples de flèches montantes :

• 3 ↑ 3 {\displaystyle 3\uparrow 3} est 3x3x3 ce qui équivaut à 27. Une flèche entre deux nombres signifie simplement le premier nombre multiplié par lui-même le deuxième nombre de fois.
• On peut penser que 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} est 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)} parce que deux flèches entre les nombres A et B signifient simplement que A a écrit un B plusieurs fois avec une flèche entre chaque A. Parce que nous savons ce que sont les flèches simples, 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)} est égal à 3 multiplié par lui-même 3 ↑ 3 {\displaystyle 3\uparrow 3} fois et nous savons que 3 ↑ 3 {\displaystyle 3\uparrow 3} est égal à vingt-sept. Donc 3 ↑↑ 3 {\displaystyle 3\uparrow 3} est 3x3x3x3x.... x3x3, au total 27 fois. Cela équivaut à 7 625 597 484 987.
• 3 ↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow 3} est 3 ↑↑ ( 3 ↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)} et nous savons que 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} est 7 625 597 484 987. Donc, 3 ↑↑ ( 3 ↑↑ 3 )* est de 3 ↑↑ 7 , 625 , 597 , 484 , 987 . Cela peut aussi s'écrire 3 ↑ ( 3 ↑ ( 3 ↑ ( 3 ↑ . . . ( 3 ↑ ( 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow (3\uparrow (3\uparrow ...(3\uparrow (3\uparrow (3\uparrow 3)} avec un total de 7.625.597.484.987 3s. Ce nombre est si énorme que ses chiffres, même écrits en toutes petites lettres, pourraient remplir l'univers observable et au-delà.
• Bien que ce nombre soit déjà incompréhensible, ce n'est qu'un début pour ce nombre géant.
• La prochaine étape comme celle-ci est 3 ↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3} ou 3 ↑↑↑ ( 3 ↑↑↑ 3 ) {\displaystyle 3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)} . C'est le numéro que nous appellerons g1.

Après cela, g2 est égal à 3 ↑↑↑ ... ↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3} ; le nombre de flèches dans ce nombre est g1.

g3 est égal à 3 ↑↑↑↑ ... ↑↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3} , où le nombre de flèches est g2.

Nous continuons dans cette voie. Nous nous arrêtons lorsque nous définissons g64 comme étant 3 ↑↑↑↑ ... ↑↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3} , où le nombre de flèches est g63.

C'est le numéro de Graham.

• La notation ascendante de Knuth