Wiki Googologie
Advertisement
Wiki Googologie

Expression visuelle du nombre de Graham

Le nombre de Graham G est un grand nombre célèbre, défini par Ronald Graham.[1]

En utilisant la notation des puissances itérées, le nombre de Graham, G, est défini comme G = g64(4) lorsque g(n) = 3↑n3. C'est équivalent à,

La définition peut également être exprimée par la figure.

Le nombre de Graham est généralement célébré comme le plus grand nombre jamais utilisé dans une preuve mathématique sérieuse, bien que des nombres beaucoup plus grands aient depuis revendiqué ce titre (comme TREE(3) et SCG(13)).

Historique

Le nombre de Graham est né du problème non résolu suivant dans la théorie de Ramsey :

Soit N* la plus petite dimension n d'un hypercube telle que si les lignes joignant toutes les paires de coins sont bicolores pour tout nN*, un graphe complet K4 d'une couleur avec des sommets coplanaires sera forcé. Trouvez N*.

Pour comprendre ce que demande ce problème, considérez d'abord un hypercube de n'importe quel nombre de dimensions (1 dimension serait une ligne, 2 serait un carré, 3 serait un cube, 4 serait un tesseract (cube à 4 dimensions), etc.), et appelez ce nombre de dimensions N. Ensuite, imaginez que vous connectez toutes les paires de sommets possibles avec des lignes, et que vous coloriez chacune d'entre elles en rouge ou en bleu - une telle façon de colorer toutes les paires de sommets du cube à 3 dimensions est illustrée à droite. Quel est le plus petit nombre de dimensions N pour que toutes les colorations possibles donnent un graphe complet monochromatique de quatre sommets coplanaires (c'est-à-dire un ensemble de quatre points reliés de toutes les manières possibles, toutes les lignes étant de la même couleur) ?

Graham a publié un article en 1971 prouvant que la réponse existe, fournissant la borne supérieure F7(12), où F(n) = 2 ↑n 3 en notation des puissances itérées.[2] Sbiis Saibian appelle ce nombre "Little Graham". Martin Gardner, lorsqu'il a découvert la taille du nombre, l'a trouvé difficile à expliquer, et il a conçu un nombre plus grand et plus facile à expliquer que Graham a prouvé dans un article non publié de 1977. Martin Gardner a écrit sur ce nombre dans Scientific American[3] et il est même entré dans le Guiness World Records en 1980 comme[4]

The highest number ever used in mathematical proof is a bounding value published in 1977 and known as Graham's number. It concerns bichromatic hypercubes and is inexpressible without the special "arrow" notation, devised by Knuth in 1976, extended to 64 layers.

bien que quelques années plus tard, le titre ait été retiré du Guinness World Records.

En 2013, la borne supérieure a encore été réduite à N' = 2↑↑2↑↑(3+2{tet}}8) en utilisant le théorème de Hales-Jewett,[5] et à N" = (2↑↑5138) x ((2↑↑5140)↑↑(2 x (2↑↑5137))) << 2↑↑↑5 en 2019.[6] En 2014, la borne inférieure la plus connue pour N* est 13, montrée par Jerome Barkley en 2008.[7]

Dans la bande dessinée japonaise des grands nombres Sushi Kokuu Hen[8], le premier épisode commence soudainement par une discussion sur le nombre de Graham, et les lecteurs sont attirés par le monde de la googologie.

Comparaison

Conway a écrit que le nombre de Graham, G, est compris entre 3→3→64→2 et 3→3→65→2 avec la notation des flèches chaînées, et donc inférieur à 3→3→3→3.[9]

Dans la fonction d'Ackermann multivariable, A(1,1,64) < G < A(1,1,65).

Tim Chow a prouvé que le nombre de Graham est beaucoup plus grand que celui de Moser.[10] La preuve repose sur le fait que, en utilisant la notation de Steinhaus-Moser, n dans un (k + 2)-gone est inférieur à . Il a envoyé la preuve à Susan Stepney le 7 juillet 1998[11]. Par coïncidence, Stepney a reçu une preuve similaire de Todd Cesere quelques jours plus tard.

Il a été prouvé que le nombre de Graham est bien inférieur à Σ(64) dans la fonction du castor affairé.[12] Selon Wythagoras, il a trouvé une machine de Turing qui prouve Σ(18) > G en améliorant la machine de Deedlit11,[13] et a écrit une brève esquisse de la preuve au lieu d'une preuve rigoureuse.

Dans la hiérarchie de croissance rapide, le nombre de Graham est inférieur à .[14]

Vidéos

1. Les nombres archi-méga-super géants | Infini 1

2. Des nombres grands, TRÈS grands - Micmaths

Références

  1. Graham's Number, Wolfram MathWorld
  2. Graham, R. L. et Rothschild, B. L. "Ramsey's Theorem for n-Parameter Sets.". Trans. Amer. Math. Soc. 159, 257-292, 1971.
  3. Gardner, M. (1977) "Mathematical games : Dans lesquels joindre des ensembles de points conduit à des chemins divers (et détournés)". Scientific American 237(5), 18-28. doi:10.1038/scientificamerican1177-18.
  4. Guiness Book of World Record, 1980. Stamford, CT : Guinness Media. p. 193, l. 27-31
  5. http://arxiv.org/abs/1304.6910
  6. http://arxiv.org/abs/1905.05617
  7. http://arxiv.org/abs/0811.1055
  8. Doom Kobayashi, "Sushi Kokuu hen", en japonais, anglais et chinois, pixiv comic (2015) et SansaiBooks (2017)
  9. Conway, J. H. and R. Guy (1995) Book of Numbers, Copernicus.
  10. Proof that G >> M. (This website uses n[m] = n inside an m-gon for Steinhaus-Moser Notation.)
  11. Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
  12. Proof that BB(64) >> G
  13. en:User blog:Wythagoras/The nineteenth Busy Beaver number is greater than Graham's Number!
  14. Fish. Upper bound of Graham's number in fast-growing hierarchy, July 11, 2021.
Advertisement