Grahams tal (Grahams nummer)

Ramseyteori är ett område inom matematiken där man ställer frågor som följande:

Antag att vi ritar ett antal punkter och att varje par punkter förbinds med en linje. Vissa linjer är blå och andra är röda. Kan vi alltid hitta tre punkter för vilka de tre linjer som förbinder dem alla har samma färg?

Det visar sig att för detta enkla problem är svaret "ja" när vi har 6 eller fler punkter, oavsett hur linjerna är färgade. Men när vi har 5 eller färre punkter kan vi färga linjerna så att svaret blir "nej".

Återigen, låt oss säga att vi har några punkter, men nu är de hörnen av en n-dimensionell hyperkub. De är fortfarande förbundna med blå och röda linjer. För fyra punkter finns det sex linjer som förbinder dem. Kan vi hitta 4 punkter som alla ligger på ett plan och där de 6 linjerna som förbinder dem alla har samma färg?

Genom att kräva att de fyra punkterna ska ligga på ett plan har vi gjort problemet mycket svårare. Vi skulle vilja veta: för vilka värden av n är svaret "nej" (för vissa sätt att färga linjerna), och för vilka värden av n är det "ja" (för alla sätt att färga linjerna)? Men detta problem har ännu inte lösts helt och hållet.

År 1971 hittade Ronald Graham och B. L. Rothschild ett partiellt svar på detta problem. De visade att för n=6 är svaret "nej". Men när n är mycket stort, lika stort som Grahams tal eller större, är svaret "ja".

En av anledningarna till att detta partiella svar är viktigt är att det betyder att svaret till slut är "ja" för åtminstone ett visst stort n. Före 1971 visste vi inte ens så mycket.

Det finns en mycket mindre gräns för samma problem som kallas N. Den är lika med f 64 ( 4 ) {\displaystyle f_{64}(4)} , där f ( n ) = 3 ↑ n 3 {\displaystyle f(n)=3\uparrow ^{n}3} . Denna svagare övre gräns för problemet, som tillskrivs ett opublicerat arbete av Graham, publicerades slutligen och namngavs av Martin Gardner i Scientific American i november 1977.

Grahams tal är inte bara för stort för att skriva ner alla dess siffror, det är till och med för stort för att skrivas i vetenskaplig notation. För att kunna skriva ner det måste vi använda Knuths uppåtpilar.

Vi skriver ner en sekvens av tal som vi kallar g1, g2, g3 och så vidare. Varje tal kommer att användas i en ekvation för att hitta nästa. g64 är Grahams nummer.

Här är några exempel på uppåtriktade pilar:

• 3 ↑ 3 {\displaystyle 3\uparrow 3} är 3x3x3 vilket är lika med 27. En pil mellan två tal betyder bara att det första talet multipliceras med sig självt det andra antalet gånger.
• Man kan se 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} som 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)} eftersom två pilar mellan A och B bara betyder att A skrivs ner ett antal gånger med en pil mellan varje A. Eftersom vi vet vad enstaka pilar är, är 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow 3)} 3 multiplicerat med sig själv 3 ↑ 3 {\displaystyle 3\uparrow 3} gånger och vi vet att 3 ↑ 3 {\displaystyle 3\uparrow 3} är tjugosju. Så 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} är 3x3x3x3x3x....x3x3x3, totalt 27 gånger. Det är lika med 7 625 597 484 987.
• 3 ↑↑↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3} är 3 ↑↑ ( 3 ↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)} och vi vet att 3 ↑↑ 3 {\displaystyle 3\uparrow \uparrow 3} är 7,625,597,484,987. Så 3 ↑↑ ( 3 ↑↑↑ 3 ) {\displaystyle 3\uparrow \uparrow (3\uparrow \uparrow 3)} är 3 ↑↑ 7 , 625 , 597 , 484 , 987 {\displaystyle 3\uparrow \uparrow 7,625,597,484,987} . Det kan också skrivas som 3 ↑ ( 3 ↑ ( 3 ↑ ( 3 ↑ ( 3 ↑ . . . ( 3 ↑ ( 3 ↑ ( 3 ↑ ( 3 ↑ 3 ) {\displaystyle 3\uparrow (3\uparrow (3\uparrow (3\uparrow (3\uparrow (3\uparrow ...(3\uparrow (3\uparrow (3\uparrow (3\uparrow 3)} } med totalt 7 625 597 484 987 3s. Detta tal är så enormt att dess siffror, även om de skrivs mycket små, skulle kunna fylla hela det observerbara universumet och bortom det.
• Även om denna siffra kanske redan är obegriplig, är detta knappt början på denna gigantiska siffra.
• Nästa steg är 3 ↑↑↑ ↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} eller 3 ↑↑↑↑ ( 3 ↑↑↑↑ 3 ) {\displaystyle 3\uparrow \uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow \uparrow 3)} . Detta är det tal som vi kallar g1.

Därefter är g2 lika med 3 ↑↑↑↑ ↑↑ ... ↑↑↑↑ ↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} ; antalet pilar i detta antal är g1.

g3 är lika med 3 ↑↑↑ ↑↑ ... ↑↑↑↑ ↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} , där antalet pilar är g2.

Vi fortsätter på detta sätt. Vi slutar när vi definierar g64 som 3 ↑↑↑↑ ↑↑↑ ... ↑↑↑↑ ↑↑ 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} , där antalet pilar är g63.

Detta är Grahams nummer.

• Knuths uppåt-pil notation