Числото на Греъм е много голямо естествено число, което е дефинирано от математик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.
  • Числото на Греъм остава важен и известен пример в популярната и висшата математика за стойности, които показват границите на интуицията ни относно „колко голямо“ може да бъде едно естествено число.

В заключение: числото на Греъм е конкретно дефиниран, краен, но поразително огромен горен предел за задача от теорията на Рамзи. То илюстрира как в комбинаториката и теорията на Рамзи могат да възникнат количества, които са напълно извън мащаба на ежедневните числови представяния, дори когато самият проблем е чисто дискретен и „малък“ на пръв поглед.