Numer Grahama

Liczba Grahama , nazwana na cześć matematyka Ronalda Grahama , jest liczbą naturalną, o której wiadomo, że od dawna jest największą liczbą całkowitą występującą w dowodzie matematycznym. Jest o wiele za duży, aby można go było zapisać za pomocą notacji naukowej, i wymaga notacji do pisania bardzo dużych liczb. Jednak bez większych trudności można uzyskać jego najnowsze dane. Zatem ostatnie dziesięć cyfr to 2464195387.

Problem Grahama

Liczba Grahama jest powiązana z gałęzią matematyki znaną jako teoria Ramseya :

Niech będzie hipersześcianem o wymiarze n, którego połączymy wszystkie pary wierzchołków, aby otrzymać pełny wykres z 2 n wierzchołkami. Jeśli pokolorujemy każdą z 2 n –1 (2 n - 1) krawędzi wykresu na niebiesko lub czerwono, jaka jest najmniejsza wartość n, tak aby dla każdego sposobu kolorowania wykresu powstał sub-pełny monochromatyczny wykres na czterech współpłaszczyznowych wierzchołkach ?

Nie znamy jeszcze odpowiedzi na to pytanie, ale od 2003 roku wiemy, że to najmniejsze n musi być większe lub równe 11, a od 2008 roku jest nawet warte co najmniej 13.

Jeśli chodzi o górne granice tego najmniejszego n , to najbardziej znany był w 1971 roku

${\ displaystyle \ left. {\ rozpocząć {matrix} \ underbrace {2 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 3} \\\ underbrace {2 \ uparrow \ cdots \ cdots \ cdots \ uparrow 3} \\ {\ vdots} \\\ underbrace {\ qquad \ qquad \ qquad} \\ {2 \ uparrow \ cdots \ cdots \ uparrow 3} \ end {matrix}} \ right \} {\ text {7 poziomów}}}$

(od tego czasu został udoskonalony).

Ta liczba jest ogromna, ale nawet mniejsza niż „liczba Grahama” G poniżej. Liczba G zawdzięcza swoją sławę i nazwę temu, co zostało przedstawione w 1977 roku przez Martina Gardnera w Scientific American , jako górna granica należna Grahamowi, zamiast znacznie dokładniejszej górnej granicy powyżej, znalezionej przez Grahama i Rothschilda .

Definicja

Liczba Grahama to 64- ty człon ciągu:

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

gdzie każdy wyraz to liczba strzałek w następnym członie, używając notacji strzałek Knutha .

Równoważnie niech f ( n ) = hyper (3, n + 2, 3) = 3 → 3 → n ; Następnie ilość Graham wartość 64 th iteracyjne funkcji F w punkcie 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 level}}

Sama liczba Grahama G nie jest dogodnie wyrażona za pomocą notacji łańcuchowej strzałki Conwaya , ale mamy obramowanie

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

Podobnie szybko rosnąca hierarchia umożliwia pisanie coachingu

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

Uwagi i odniesienia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu Wikipedii w języku angielskim zatytułowanego „ Numer Grahama ” ( zobacz listę autorów ) .

Pod koniec lat osiemdziesiątych XX wieku liczby całkowite znacznie większe niż liczba Grahama pojawiły się w kilku poważnych dowodach matematycznych, na przykład w odniesieniu do skończonych form twierdzenia Kruskala odkrytych przez Harveya Friedmana .
(w) Geoffrey Exoo , " Problem Euklidesa Ramseya " , Discrete Comput. Geom. , vol. 29 N O 22003, s. 223-227 ( DOI 10.1007 / s00454-002-0780-5 ).
(w) Jerome Barkley, „ Ulepszony roczny problem z dolną granicą Euklidesa Ramseya ”2008( arXiv 0811.1055 ) .
(w) RL Graham i BL Rothschild, " Twierdzenie Ramseya dla zbiorów n -parametrów " , przeł. Gorzki. Matematyka. Soc. , vol. 159,1971, s. 257-292 ( czytaj online )( str. 290 ).
(w) Michaił Ławrow , Mitchell Lee i John Mackey , „Liczba Grahama jest mniejsza niż 2 ”Diplotop 6 ”2013( arXiv 1304.6910 ) . KomentarzDavida Robertsa:„ Tytuł artykułu jest mylący […] to dokładne rozwiązanie tego problemu nazywają„ numerem Grahama ”[…] W istocie ograniczenie podane w tytule, 2 ↑ & uarr; to uproszczenie, a nie najmniejsza granica, do której doszło w artykule, czyli 2 ↑ ↑ 2 ↑ ↑ 2 ↑GRAM 9 […] Jeśli chodzi o funkcję F Grahama i Rothschilda, granica LLM znajduje się między F (4) i F (5) ”.
(w) Pan Gardner, „ Mathematical Games ” , Scientific American , tom. 237,1977, s. 18-28 ( DOI 10.1038 / Scientificamerican1177-18 ). Ta nieścisłość została uwzględniona w (nie) Eric W. Weisstein , „ Graham's Number ” na MathWorld .
Aby uzyskać szczegółowe informacje, patrz (w) John Baez , „ Jakiś czas temu mówiłem ci o numerze Grahama ... ” ,Styczeń 2013.

Zobacz też

Bibliografia

(en) John H. Conway and Richard Guy , The Book of Numbers , Springer-Verlag, 1996, str. 61-62 [ czytaj online ]

Link zewnętrzny

(en) Geoffrey Exoo, „ A Ramsey Problem on Hypercubes ”