Числото на Греъм — огромно число в теорията на Рамзи
Числото на Греъм: запознайте се с едно от най-огромните числа в теорията на Рамзи — удивително, непостижимо за вселената и ключово в математическите доказателства.
Числото на Греъм е много голямо естествено число, което е дефинирано от математикa Роналд Греъм. То се появява като горна граница в решаването на въпрос от областта на теория на Рамзи. Греъм е доказал, че отговорът на конкретната му задача е по-малък от това число, което дава конструктивна, макар и астрономически голяма, горна граница.
Числото на Греъм е едно от най-големите числа, използвани някога в математическо доказателство. Дори ако всяка цифра от числото на Греъм бъде написана с възможно най-малките букви, то пак ще бъде твърде голямо, за да се побере в наблюдаемата вселена. Това дава добра представа за мащаба: то надминава с много класове големини числа като гугъл (googol) или дори гугълплекс.
Как се дефинира числото на Греъм?
За да се опише формално числото на Греъм, използваме твърде бързо растяща нотация — нотацията на Knuth с „стрели“ (up-arrows). Няколко основни примера:
- a ↑ b означава a на степен b (обикновена експоненциация).
- a ↑↑ b означава т.нар. тетрация: a^(a^(...^a)) с b броя a в кулата на степените.
- Повече стрелки (↑↑↑, ↑↑↑↑ и т.н.) означават още по-големи повторения на предишните операции.
Построяването на числото на Греъм започва с:
g1 = 3 ↑↑↑↑ 3,
и след това се дефинира рекурсивно за k ≥ 1:
g_{k+1} = 3 ↑^{g_k} 3,
където в десетичната нотация ↑^{g_k} означава „стрелата“ повторена g_k пъти. Накрая самото число на Греъм се дефинира като g_{64} (понякога се обозначава с G или Graham):
Греъм = g64.
Произход в теорията на Рамзи
Числото е въведено като горна граница за конкретна задача в теорията на Рамзи, свързана с оцветяването на ребрата на n-измерен хиперкуб с два цвята и появата на определена монохроматична конфигурация (т.е. подграф със специална структура). Въпреки че горната граница, дадена чрез числото на Греъм, е изключително голяма, самият въпрос за минималното необходимо n остава отворен и енергично изследван — известно е, че реалната минимална стойност е много по-малка от числото на Греъм, но точната ѝ стойност не е установена.
Колко е „голямо“ това число на практика?
Дори g1 = 3 ↑↑↑↑ 3 е вече толкова огромно, че не може да се представи в стандартна научна нотация. Следващите g_k растат толкова бързо, че силно надвишават всякакви обичайни мащаби. Затова числото на Греъм служи повече като пример за крайна, но изключително бързо нарастваща горна граница, отколкото като практически използваема стойност.
Какво още се знае за числото на Греъм?
- Въпреки че общата стойност е недостижима, някои крайни цифри могат да се определят чрез свойства на степенните кули и аритметика по модул. По-специално е известно, че последната цифра на числото на Греъм е 7.
- Числото на Греъм остава важен и известен пример в популярната и висшата математика за стойности, които показват границите на интуицията ни относно „колко голямо“ може да бъде едно естествено число.
В заключение: числото на Греъм е конкретно дефиниран, краен, но поразително огромен горен предел за задача от теорията на Рамзи. То илюстрира как в комбинаториката и теорията на Рамзи могат да възникнат количества, които са напълно извън мащаба на ежедневните числови представяния, дори когато самият проблем е чисто дискретен и „малък“ на пръв поглед.
Контекст
Теорията на Рамзи е област от математиката, в която се задават въпроси като следния:
Да предположим, че сме начертали някакъв брой точки и сме свързали всяка двойка точки с линия. Някои линии са сини, а други - червени. Можем ли винаги да намерим 3 точки, за които трите линии, които ги свързват, са с един и същи цвят?
Оказва се, че за тази проста задача отговорът е "да", когато имаме 6 или повече точки, независимо от това как са оцветени линиите. Но когато имаме 5 или по-малко точки, можем да оцветим линиите така, че отговорът да е "не".
Отново да кажем, че имаме някакви точки, но сега те са ъглите на n-измерен хиперкуб. Всички те все още са свързани със сини и червени линии. За всеки 4 точки има 6 линии, които ги свързват. Можем ли да намерим 4 точки, които лежат на една равнина, а 6-те линии, които ги свързват, са с един и същи цвят?
Като поискахме четирите точки да лежат върху равнина, усложнихме задачата много повече. Бихме искали да знаем: за кои стойности на n отговорът е "не" (за някакъв начин на оцветяване на линиите) и за кои стойности на n е "да" (за всички начини на оцветяване на линиите)? Но този проблем все още не е напълно решен.
През 1971 г. Роналд Греъм и Б. Л. Ротшилд намират частичен отговор на този проблем. Те показват, че за n=6 отговорът е "не". Но когато n е много голямо, колкото числото на Греъм или по-голямо, отговорът е "да".
Една от причините, поради които този частичен отговор е важен, е, че той означава, че отговорът в крайна сметка е "да" за поне известно голямо n. Преди 1971 г. не знаехме дори толкова много.
Съществува много по-малка граница за същата задача, наречена N. Тя е равна на 
, където 
. Тази по-слаба горна граница на задачата, приписвана на непубликувана работа на Греъм, в крайна сметка е публикувана и назована от Мартин Гарднър в Scientific American през ноември 1977 г.
Определение
Числото на Греъм е не само твърде голямо, за да се запишат всички негови цифри, но и твърде голямо, за да се запише с научна нотация. За да можем да го запишем, трябва да използваме записа на Кнут със стрелките нагоре.
Ще запишем поредица от числа, които ще наречем g1, g2, g3 и т.н. Всяко едно от тях ще бъде използвано в уравнение, за да се намери следващото. g64 е числото на Греъм.
Първо, ето няколко примера за стрелки нагоре:
е 3x3x3, което е равно на 27. Стрелката между две числа просто означава, че първото число е умножено по себе си втори път.- Можем да мислим за
като за 
, защото две стрелки между числата А и В просто означават А, записано на В няколко пъти със стрелка между всяко А. Тъй като знаем какво представляват единичните стрелки, е 3, умножено по себе си пъти, и знаем, че е двадесет и седем. Така че е 3х3х3х3х....х3х3, общо 27 пъти. Това се равнява на 7 625 597 484 987. 
е 
и знаем, че е 7,625,597,484,987. Така че е 
. Това може да се запише и като 
с общо 7 625 597 484 987 3s. Това число е толкова огромно, че цифрите му, дори написани с много малки букви, могат да запълнят наблюдаемата Вселена и отвъд нея.- Въпреки че това число вече е непостижимо, то е едва началото на този гигантски брой.
- Следващата подобна стъпка е
или 
. Това е числото, което ще наричаме g1.
След това g2 е равно на 
; броят на стрелките в това число е g1.
g3 е равно на 
, където броят на стрелките е g2.
Продължаваме по този начин. Спираме, когато определим, че g64 е , където броят на стрелките е g63.
Това е номерът на Греъм.
Свързани страници
- Запис на стрелките нагоре на Кнут
Въпроси и отговори
В: Кой определи номера на Греъм?
О: Роналд Греъм определи числото на Греъм.
В: В коя област на математиката е работил Роналд Греъм, когато е определил числото?
О: Когато определя числото, Роналд Греъм работи в област от математиката, наречена теория на Рамзи.
Въпрос: Какво доказва Роналд Греъм със своя проблем?
О: Роналд Греъм доказа, че отговорът на задачата му е по-малък от числото на Греъм.
Въпрос: Колко голямо е числото на Греъм в сравнение с други числа, използвани в математически доказателства?
О: Числото на Греъм е едно от най-големите числа, използвани някога в математическо доказателство.
Въпрос: Ако всяка цифра на числото бъде написана, ще се побере ли то в наблюдаемата вселена?
О: Дори всяка цифра от числото на Греъм да бъде изписана с най-малкия възможен шрифт, то пак ще бъде твърде голямо, за да се побере в наблюдаемата вселена.
Въпрос: Има ли начин да се изчисли или оцени колко голямо е това число?
О: Няма точен начин да се изчисли или оцени колко голямо е това конкретно естествено число, тъй като то все още не е напълно определено.
Въпрос: Защо съществува такова голямо естествено число и за какво служи то?
О: Това много голямо естествено число съществува, защото е използвано от Роналд Грам като част от математическо доказателство и служи като горна граница за неговото решение.
обискирам