Grahamovo číslo

Číslo Graham , pojmenované po matematik Ronald Graham , je přirozené číslo známo, že již dlouhou dobu největší integer objevit v matematickém důkazu. Je příliš velká na to, aby se dala psát pomocí vědecké notace, a vyžaduje notaci, kterou lze použít k zápisu velmi velkých čísel. Je však možné získat jeho nejnovější údaje bez větších obtíží. Takže jeho posledních deset číslic je 2464195387.

Grahamův problém

Grahamovo číslo souvisí s oborem matematiky známým jako Ramseyova teorie :

Dovolit být hyperkrychle dimenze n, z nichž spojíme všechny dvojice vrcholů, abychom získali úplný graf s 2 n vrcholy. Pokud zbarvíme každý ze 2 n –1 (2 n - 1) okrajů grafu modře nebo červeně, jaká je nejmenší hodnota n taková, že pro každý způsob vybarvení grafu existuje částečný monochromatický graf na čtyřech koplanárních vrcholech ?

Zatím neznáme odpověď na tuto otázku, ale od roku 2003 víme, že toto nejmenší n musí být větší nebo rovné 11 a od roku 2008 má dokonce hodnotu nejméně 13.

Pokud jde o horní hranice tohoto nejmenšího n , nejznámější v roce 1971 byl

${\ displaystyle \ left. {\ begin {matrix} \ underbrace {2 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 3} \\\ spodní výztuha {2 \ uparrow \ cdots \ cdots \ cdots \ uparrow 3} \\ {\ vdots} \\\ underbrace {\ qquad \ qquad \ qquad} \\ {2 \ uparrow \ cdots \ cdots \ uparrow 3} \ end {matrix}} \ right \} {\ text {7 úrovní}}}$

(od té doby byl vylepšen).

Toto číslo je obrovské, ale ještě menší než „Grahamovo číslo“ G níže. Číslo G vděčí za svou slávu a jméno tomu, co v roce 1977 představil Martin Gardner ve vědeckém časopise Scientific American jako horní mez kvůli Grahamovi, namísto mnohem přesnější horní meze výše, kterou našli Graham a Rothschild .

Definice

Číslo Grahamova je 64 th doba trvání pořadí:

4, \ 3 \ uparrow \ uparrow \ uparrow \ uparrow 3, \ 3 \ uparrow \ cdots \ uparrow 3, \ 3 \ uparrow \ cdots \ uparrow 3, \ \ ldots

kde každý člen je počet šípů v příštím členu pomocí Knuthovy šipkové notace .

Ekvivalentně nechť f ( n ) = hyper (3, n + 2, 3) = 3 → 3 → n ; pak počet Graham je hodnota 64 th iteraci z funkce f v bodě 4.

\ 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 \ uparrow 3 \ end {matrix}} \ right \} {\ text {64 úrovní}}

Samotné číslo Grahama G není vhodně vyjádřeno pomocí Conwayovy řetězové šipky , ale máme rámec

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

Stejně tak rychle rostoucí hierarchie umožňuje psát koučování

{\ displaystyle f _ {\ omega +1} (63) <G <f _ {\ omega +1} (64).}

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z anglického článku Wikipedie s názvem „ Grahamovo číslo “ ( viz seznam autorů ) .

Na konci 80. let se celá čísla mnohem větší než Grahamovo číslo objevila v několika vážných matematických důkazech, například ve vztahu ke konečným formám Kruskalovy věty objeveným Harveyem Friedmanem .
(in) Geoffrey Exoo , „ Euclidean Ramsey Problem “ , diskrétní výpočet. Geom. , sv. 29, n O 22003, str. 223-227 ( DOI 10.1007 / s00454-002-0780-5 ).
(in) Jerome Barkley, „ Vylepšena dolní hranice jednoho roku s problémem Euclidean Ramsey “2008( arXiv 0811.1055 ) .
(in) RL Graham a BL Rothschild, „ Ramseyova věta pro n -parametrické množiny “ , Trans. Hořký. Matematika. Soc. , sv. 159,1971, str. 257-292 ( číst online )( str. 290 ).
(in) Michail Lavrov , Mitchell Lee a John Mackey , „ Grahamovo číslo je menší než 2 ↑↑↑ 6 “2013( arXiv 1304,6910 ) . KomentářeDavida Robertsa:„ Název tohoto příspěvku je zavádějící […] je to přesné řešení tohoto problému, které nazývají„ Grahamovo číslo “[…] Ve skutečnosti je vazba uvedená v názvu, 2 ↑↑↑ 6, je zjednodušení a v článku není dosažena nejmenší hranice, která je 2 ↑↑ 2 ↑↑ 2 ↑↑ 9 […] Pokud jde o funkci F Grahama a Rothschilda, vazba LLM je mezi F (4) a F (5) “.
(in) Mr. Gardner, „ Mathematical Games “ , Scientific American , sv. 237,1977, str. 18-28 ( DOI 10.1038 / scientificamerican1177-18 ). Tuto nepřesnost přijímá (ne) Eric W. Weisstein , „ Grahamovo číslo “ na MathWorld .
Podrobnosti viz (v) John Baez , „ Před nějakou dobou jsem ti řekl o Grahamově čísle ... “ ,Leden 2013.

Podívejte se také

Bibliografie

(en) John H. Conway a Richard Guy , Kniha čísel , Springer-Verlag, 1996, str. 61-62 [ číst online ]

Externí odkaz

(en) Geoffrey Exoo, „ Ramseyův problém na Hypercubes “