Αριθμός του Γκράχαμ

Ο αριθμός του Γκράχαμ (αγγλικά: Graham's number) είναι ασύλληπτα μεγάλος ακέραιος αριθμός ο οποίος προκύπτει ως το άνω όριο στην απάντηση προβλήματος του μαθηματικού πεδίου της θεωρίας Ράμσεϋ. Ονομάστηκε βάσει του μαθηματικού Ρόναλντ Γκράχαμ ο οποίος χρησιμοποίησε τον αριθμό ως μια απλοποιημένη εξήγηση των άνω ορίων κάποιου προβλήματος στο οποίο εργαζόταν. Το σύνολο των ψηφίων από τα οποία απαρτίζεται ο αριθμός σε τόσο μεγάλη κλίμακα, δεν είναι δυνατό να εκφραστεί με μαθηματικές δυνάμεις ούτε καν υψωμένες διαδοχικά ως $\scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ή τον παραγοντικό τελεστή !, και χρειάζεται ειδική σημειολογία, ενώ δεν είναι δυνατό ούτε να αποτυπωθούν γραπτά καθώς η καταγραφή του συνόλου των ψηφίων θα απαιτούσε μεγαλύτερο χώρο από αυτόν που είναι διαθέσιμος στο παρατηρήσιμο σύμπαν, υποθέτoντας πως το κάθε ψηφίο θα καταλάμβανε τον υπερμικροσκοπικό χώρο του 4.2217 × 10⁻¹⁰⁵ m³ ο οποίος αντιστοιχεί σε μια μονάδα όγκου Πλανκ η οποία είναι η μικρότερη δυνατή μετρήσιμη ποσότητα όγκου. Επίσης, δεν είναι ούτε δυνατό να αναπαρασταθεί γραπτά απλά το σύνολο των ψηφίων του αριθμού αυτού αντί ο ίδιος ο αριθμός. Ωστόσο υπάρχουν τρόποι ώστε να βρεθούν το ποιά είναι τα τελευταία ψηφία του αριθμού, για παράδειγμα τα 12 τελευταία ψηφία του είναι τα ...262464195387.

Ο αριθμός αυτός αργότερα περιγράφθηκε στο επιστημονικό περιοδικό Scientific American το 1977, γνωστοποιώντας τον στο ευρύτερο αναγνωστικό κοινό. Κατά την εποχή όπου διατυπώθηκε, αποτέλεσε τον μεγαλύτερο θετικό ακέραιο ο οποίος χρησιμοποιήθηκε ποτέ σε δημοσιευμένη μαθηματική απόδειξη. Ακολούθως το 1980 ο αριθμός δημοσιεύτηκε στο βιβλίο των Ρεκόρ Γκίνες το 1980 κάνοντας τον ακόμη πιο γνωστό. Κατά τις επόμενες δεκαετίες εμφανίστηκαν ακόμη μεγαλύτεροι ακέραιοι όπως ο TREE(3) οι οποίοι είναι πολύ μεγαλύτεροι ακόμη και από τον αριθμό του Γκράχαμ και έχουν επίσης χρησιμοποιηθεί σε δημοσιευμένες μαθηματικές μελέτες, ή οι αριθμοί busy beaver οι οποίοι είναι τόσο μεγάλοι ώστε δεν μπορούν να παραχθούν βάσει μικρών αναδρομικών μεθόδων για να περιγράψουν κάποιο άνω όριο. Ωστόσο ο αριθμός του Γκράχαμ είναι κατά πολύ μεγαλύτερος από άλλους μεγάλους γνωστούς αριθμούς, όπως ο αριθμός του Σκιούς και ο αριθμός του Μόζερ, οι οποίοι με την σειρά τους είναι κατά πολύ μεγαλύτεροι από το γκούγκολ.

Ο αριθμός είναι δυνατό να αναπαρασταθεί μέσω της ειδικής μαθηματικής σημειολογίας του Ντόναλντ Κνουθ, γνωστής ως σημειολογίας Κνουθ άνω βέλους η οποία χρησιμοποιείται για εξαιρετικά μεγάλους αριθμούς και την οποία χρησιμοποίησε ο ίδιος ο Γκράχαμ κατά την διατύπωση του αριθμού του.

Χρήση

Παράδειγμα δίχρωμου τρισδιάστατου κύβου ο οποίος περιέχει ένα μονοχρωματισμένο ομοεπίπεδο υπογράφο τεσσάρων κορυφών. Ο υπογράφος αναπαριστάται ξεχωριστά κάτω από τον κύβο.

Ο αριθμός του Γκράχαμ σχετίζεται με το παρακάτω πρόβλημα της θεωρίας Ράμσεΐ:

Σύνδεσε κάθε ζεύγος γεωμετρικών κορυφών ενός υπερκύβου σε ν διαστάσεις ώστε να προκύψει ένας ολοκληρωμένος γράφος 2^ν κορυφών. Χρωμάτισε κάθε ένα από τα άκρα του γράφου είτε ερυθρό είτε κυανό. Ποια είναι η μικρότερη τιμή του ν για την οποία κάθε τέτοιος χρωματισμός περιέχει τουλάχιστον έναν μονοχρωματισμένο ολοκληρωμένο υπογράφο σε τέσσερις ομοεπίπεδες κορυφές;

Το 1971, οι Γκράχαμ και Ρόθτσιλντ έλυσαν το πρόβλημα αυτό αποδεικνύοντας πως η λύση είναι N*, όπου ισχύει η συνθήκη ορίου 6 ≤ N* ≤ N, με το N να αποτελεί έναν μεγάλο αλλά ρητά καθορισμένο αριθμό $\scriptstyle F^{7}(12)\;=\;F(F(F(F(F(F(F(12)))))))$, όπου $\scriptstyle F(n)\;=\;2\uparrow ^{n}3$ στη σημειολογία Κνουθ άνω βέλους. Με την εναλλακτική μέθοδο της αλυσιδωτής σημειολογίας βέλους Κόνγουεϊ ο αριθμός είναι μεταξύ 4 → 2 → 8 → 2 και 2 → 3 → 9 → 2. Το 2004 σμικρύνθηκε μέσω των άνω ορίων στον αριθμό Χέιλς-Τζιούετ σε $\scriptstyle N'\;=\;2\;\uparrow \uparrow \uparrow \;6$. Το 2003 το κάτω όριο διαμορφώθηκε από 6 σε 11, και το 2008 σε 13. Έτσι τα εκτιμώμενα όρια για το N* είναι 13 ≤ N* ≤ N'.

Ορισμός

Σημειολογία Κνουθ

Ο αριθμός ορίζεται ως:

$\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 επίπεδα}}$

όπου ο αριθμός βελών σε κάθε επίπεδο ορίζεται από την τιμή του επόμενου επιπέδου κάτω από αυτό, όπως:

$G=g_{64},{\text{ όπου }}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,$

και όπου η εκθετική γραφή περιγράφει το πόσα βέλη χρησιμοποιούνται. Εν τέλει, ο αριθμός Γκράχαμ περιγράφεται σε 64 τέτοια επίπεδα. Το πρώτο βήμα αφορά τον υπολογισμό του g₁ με τέσσερα άνω βέλη μεταξύ των 3αριών, το δεύτερο βήμα είναι ο υπολογισμός του g₂ με g₁ άνω βέλη μεταξύ των 3αριών, και ακολουθείται η ίδια διαδικασία για όλα τα επόμενα επίπεδα μέχρι τον τελικό υπολογισμό του G = g₆₄ με g₆₃ άνω βέλη μεταξύ των 3αριών.

Σημειολογία Κόνγουεϊ

Στην αλυσιδωτή σημειολογία βέλους Κόνγουεϊ ο αριθμός εκφράζεται με την μορφή $\scriptstyle f(n)\;=\;3\rightarrow 3\rightarrow n$, και τα όρια του καθορίζονται ως:

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

Μέγεθος

Προσεγγιστικά, ο αριθμός των 3αριών σε κάθε επίπεδο, αν αναπαριστώνταν σε εκθετική μορφή θα περιείχε το παρακάτω αριθμούς σε κάθε εκθέτη (σύνολο ψηφίων έτσι ώστε να αναπαρασταθεί ο αριθμός του εκθέτη):

ν=1  1ο επίπεδο εκθέτη:  3
     
ν=2  2ο επίπεδο εκθέτη:  3↑3↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 3) = 7625597484987
     
ν=3  3ο επίπεδο εκθέτη:  3↑3↑3↑3↑...↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 7625597484987) = …
     
      ⋮
     
ν=ν g1 = νό επίπεδο:  3↑3↑3↑3↑3↑3↑3↑...↑3 (σύνολο 3αριών από το ν-1ό επίπεδο)

όπου το σύνολο τριαριών για κάθε επίπεδο εκθέτη δίνεται από το αμέσως προηγούμενο επίπεδο. Ακόμη και το ίδιο το ν το οποίο είναι απλώς το σύνολο των επιπέδων εκθέτη, είναι αφάνταστα μεγάλο και δεν μπορεί να αναπαρασταθεί.

Υπολογισμός των τελευταίων ψηφίων

Ο πύργος εκθετών του αριθμού Γκράχαμ είναι της μορφής 3↑↑ν (όπου το ν είναι ένας πάρα πολύ μεγάλος αριθμός), έτσι τα πλέον δεξιά ψηφία του ικανοποιούν ορισμένα χαρακτηριστικά τα οποία είναι κοινά σε όλα τα επίπεδα του εκθετικού πύργου. Μια από αυτές τις ιδιότητες είναι ότι όλα τα επίπεδα τα οποία έχουν ύψος μεγαλύτερο από ψ, διαθέτουν την ίδια ακολουθία ψ των πλέον δεξιών ψηφίων. Αυτή είναι ειδική περίπτωση μιας πιο γενικής ιδιότητας, πως τα ψ πλέον δεξιά στοιχεία όλων αυτών των επιπέδων με ύψος μεγαλύτερο από ψ+2, είναι ανεξάρτητα από τα κορυφαία 3 στον πύργο, δηλαδή τα κορυφαία 3 μπορούν να αλλαχτούν σε οποιονδήποτε μη αρνητικό ακέραιο χωρίς να επηρεαστούν τα δ πλέον δεξιά ψηφία.

Για ένα ορισμένο ύψος εκθετικού πύργου και σύνολο ψηφίων ψ, το πλήρες εύρος των αριθμών με ψ-ψηφία (10ψ από αυτά) δεν διαδραματίζεται, ωστόσο μια ορισμένη μικρότερη υποομάδα των τιμών αυτών επαναλαμβάνεται κυκλικά. Το μήκος του κύκλου αυτού και κάποιες από τις τιμές (σε παρένθεση) είναι όπως παρακάτω:

Αριθμός διαφορετικών πιθανών τιμών για το 3↑3↑…3↑x όταν όλα εκτός από τα d τελευταία ψηφία αγνοούνται

Αριθμός ψηφίων (ψ)	3↑x	3↑3↑x	3↑3↑3↑x	3↑3↑3↑3↑x	3↑3↑3↑3↑3↑x
1	4 (1,3,9,7)	2 (3,7)	1 (7)	1 (7)	1 (7)
2	20 (01,03,…,87,…,67)	4 (03,27,83,87)	2 (27,87)	1 (87)	1 (87)
3	100 (001,003,…,387,…,667)	20 (003,027,…387,…,587)	4 (027,987,227,387)	2 (987,387)	1 (387)

Τα συγκεκριμένα πλέον δεξιά ψ ψηφία είναι τα ίδια με όλα τα επίπεδα του εκθετικού πύργου, και αναπτύσσονται περαιτέρω καθώς το ύψος αυξάνει.

Ένας απλός αλγόριθμος για τον υπολογισμό των ψηφίων αυτών είναι:

• για χ = 3,
• επανέλαβε, ψ φορές την ανάθεση χ = 3^χ mod 10^ψ.
• παρέλειψε τα όποια μηδενικά προκύπτουν στην αρχή του αριθμού,
• η τελική τιμή που προκύπτει για το χ αποτελείται από τα ψ πλέον δεξιά δεκαδικά ψηφία το 3↑↑ν, όπου ν > ψ. (αν η τελική τιμή του χ έχει λιγότερα από ψ ψηφία, τότε ο απαιτούμενος αριθμός 0 στην αρχή του αριθμού πρέπει να προστεθεί)
• όρισε το k ως την πληθικότητα των σταθερών αυτών στοιχείων, τα οποία ικανοποιούν την μαθηματική αναλογία G(mod 10^k)≡[G^G](mod 10^k).

k=t-1, όπου G(t):=3↑↑t. Συνεπάγεται πως g₆₃ ≪ k ≪ g₆₄.

Ο παραπάνω αλγόριθμος παράγει τα 500 πλέον δεξιά (τελευταία) ψηφία του αριθμού του Γκράχαμ:

  …02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387

Σχετική βιβλιογραφία

• Gardner, Martin (November 1977). «Mathematical Games». Scientific American 237: 18–28. doi:10.1038/scientificamerican1177-18. http://www.nature.com/scientificamerican/journal/v237/n5/pdf/scientificamerican1177-18.pdf. ; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6. 
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 0-393-02023-1. 
• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey's Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159: 257–292. doi:10.2307/1996010. http://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf.  The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
• Graham, R. L.· Rothschild, B. L. (1978). «Ramsey Theory». Στο: Rota, G-C. Studies in Combinatorics (MAA Studies in Mathematics). 17. Mathematical Association of America. σελίδες 80–99. ISBN 0-88385-117-2.  On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.

Εξωτερικοί σύνδεσμοι

• Graham's number- Mathworld
• Padilla, Tony· Parker, Matt. «Graham's Number». Numberphile. Brady Haran. Αρχειοθετήθηκε από το πρωτότυπο στις 27 Μαΐου 2014.