Grahams tal er et ekstremt stort naturligt tal, som blev indført af matematikeren Ronald Graham i forbindelse med et problem i Ramsey-teori. Graham viste, at svaret på hans oprindelige Ramsey-type-problem er mindre end Grahams tal, og tallet fungerer derfor som et (meget groft) øvre skøn i et teoretisk bevis.

Hvordan defineres Grahams tal?

Grahams tal er defineret ved en meget hurtig voksende, iterativ proces, der bruger Knuths up-arrow-notation (en måde at beskrive gentagne potenser og hyperoperationer på). En kort og standard måde at beskrive konstruktionen på er:

g1 = 3 ↑↑↑↑ 3, og for hvert n ≥ 1 defineres g(n+1) = 3 ↑^{g(n)} 3, altså hvor antallet af up-pile (↑) i udtrykket er lig med g(n). Grahams tal G sættes så til g64 (dvs. det 64. led i denne række).

Det betyder, at allerede g1 er astronomisk stort (tårne af potenser med højde og kompleksitet, der overskrider almindelig forestilling), og hvert trin i rækken fører til et tal med vækst langt ud over almindelige eksponentielle eller selv dobbelttetrationelle størrelser. Derfor bliver G ubegribeligt stort.

Betydning i Ramsey-teori

Den oprindelige motivation for Grahams tal var et spørgsmål i Ramsey-teori om farvninger af kanter i højdimensionelle hyperkuber og forekomsten af bestemte monochromatiske delstrukturer. Ronald Graham brugte sin konstruktion til at give et konkret, omend ekstremt stort, øvre skøn for det dimensionstal, hvor en vis ønsketegenskab nødvendigvis optræder ved enhver to-farvning. Så Grahams tal er ikke et «naturligt» antal, man regner med at møde i praktiske beregninger, men et bevisligt øvre skøn i teoretisk kombinatorik.

Hvorfor er tallet så enormt?

  • Itererede hyperoperationer: Hver gang man anvender reglen g(n+1) = 3 ↑^{g(n)} 3, øges antallet af pile (↑) dramatisk, og det fører til vækstformer langt voldsommere end almindelig eksponentiering eller tetration.
  • Umålelig størrelse i fysisk forstand: Grahams tal er så stort, at selv hvis hvert enkelt ciffer i Grahams tal blev skrevet med den mindste tænkelige skrifttype, ville det stadig være for stort til at passe ind i det observerbare univers.
  • Alligevel veldefineret og endelig: På trods af størrelsen er Grahams tal et helt endeligt, veldefineret naturligt tal — ikke et symbol for uendelighed.

Senere arbejde og nutidig opfattelse

Efter Grahams oprindelige arbejde har andre forskere finpudset og skærpet de teknikker, der bruges i denne type Ramsey-problemer. Det betyder, at man i mange tilfælde i dag kan give meget mindre (og mere relevante) øvre skøn for de samme eller beslægtede problemer. Det ændrer dog ikke, at Grahams tal historisk er blevet et kendt eksempel på, hvor store tal der kan dukke op i teoretiske beviser.

Grahams tal har desuden været populært omtalt i populærvidenskabelige bøger og artikler som et illustrativt eksempel på ekstrem vækst i matematikken. Det fungerer som en måde at vise forskellen mellem «teoretisk» størrelsesorden (hvor et tal blot skal være endeligt og kunne indgå i et bevis) og «praktisk» størrelsesorden (hvor størrelsen skal kunne håndteres eller fortolkes i fysiske termer).

Ekstra bemærkninger

Selvom Grahams tal er ubegribeligt stort, kan visse aritmetiske egenskaber (fx nogle af de sidste decimaler) udledes ved hjælp af modulær aritmetik og strukturen i definitionen. Men det ændrer ikke ved, at størrelsesordenen for tallet som helhed ligger langt uden for enhver fysisk eller praktisk anvendelse.

Grahams tal er derfor først og fremmest en matematisk kuriositet og et historisk vigtigt eksempel på, hvordan Ramsey-type-argumenter kan føre til enorme, men endelige, øvre grænser i kombinatorik og diskret matematik.