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

Ο αριθμός του Γκράχαμ (αγγλικά: Graham's number) είναι ασύλληπτα μεγάλος ακέραιος αριθμός ο οποίος προκύπτει ως το άνω όριο στην απάντηση προβλήματος του μαθηματικού πεδίου της θεωρίας Ράμσεϋ. Ονομάστηκε βάσει του μαθηματικού Ρόναλντ Γκράχαμ ο οποίος χρησιμοποίησε τον αριθμό ως μια απλοποιημένη εξήγηση των άνω ορίων κάποιου προβλήματος στο οποίο εργαζόταν. Το σύνολο των ψηφίων από τα οποία απαρτίζεται ο αριθμός σε τόσο μεγάλη κλίμακα, δεν είναι δυνατό να εκφραστεί με μαθηματικές δυνάμεις ούτε καν υψωμένες διαδοχικά ως ή τον παραγοντικό τελεστή !, και χρειάζεται ειδική σημειολογία, ενώ δεν είναι δυνατό ούτε να αποτυπωθούν γραπτά καθώς η καταγραφή του συνόλου των ψηφίων θα απαιτούσε μεγαλύτερο χώρο από αυτόν που είναι διαθέσιμος στο παρατηρήσιμο σύμπαν, υποθέτoντας πως το κάθε ψηφίο θα καταλάμβανε τον υπερμικροσκοπικό χώρο του 4.2217 × 10⁻¹⁰⁵ m³ ο οποίος αντιστοιχεί σε μια μονάδα όγκου Πλανκ η οποία είναι η μικρότερη δυνατή μετρήσιμη ποσότητα όγκου. Επίσης, δεν είναι ούτε δυνατό να αναπαρασταθεί γραπτά απλά το σύνολο των ψηφίων του αριθμού αυτού αντί ο ίδιος ο αριθμός. Ωστόσο υπάρχουν τρόποι ώστε να βρεθούν το ποιά είναι τα τελευταία ψηφία του αριθμού, για παράδειγμα τα 12 τελευταία ψηφία του είναι τα ...262464195387.  
Ο αριθμός αυτός αργότερα περιγράφθηκε στο επιστημονικό περιοδικό Scientific American το 1977, γνωστοποιώντας τον στο ευρύτερο αναγνωστικό κοινό. Κατά την εποχή όπου διατυπώθηκε, αποτέλεσε τον μεγαλύτερο θετικό ακέραιο ο οποίος χρησιμοποιήθηκε ποτέ σε δημοσιευμένη μαθηματική απόδειξη. Ακολούθως το 1980 ο αριθμός δημοσιεύτηκε στο βιβλίο των Ρεκόρ Γκίνες το 1980 κάνοντας τον ακόμη πιο γνωστό. Κατά τις επόμενες δεκαετίες εμφανίστηκαν ακόμη μεγαλύτεροι ακέραιοι όπως ο TREE(3) οι οποίοι είναι πολύ μεγαλύτεροι ακόμη και από τον αριθμό του Γκράχαμ και έχουν επίσης χρησιμοποιηθεί σε δημοσιευμένες μαθηματικές μελέτες, ή οι αριθμοί busy beaver οι οποίοι είναι τόσο μεγάλοι ώστε δεν μπορούν να παραχθούν βάσει μικρών αναδρομικών μεθόδων για να περιγράψουν κάποιο άνω όριο. Ωστόσο ο αριθμός του Γκράχαμ είναι κατά πολύ μεγαλύτερος από άλλους μεγάλους γνωστούς αριθμούς, όπως ο αριθμός του Σκιούς και ο αριθμός του Μόζερ, οι οποίοι με την σειρά τους είναι κατά πολύ μεγαλύτεροι από το γκούγκολ.   
Ο αριθμός είναι δυνατό να αναπαρασταθεί μέσω της ειδικής μαθηματικής σημειολογίας του Ντόναλντ Κνουθ, γνωστής ως σημειολογίας Κνουθ άνω βέλους η οποία χρησιμοποιείται για εξαιρετικά μεγάλους αριθμούς και την οποία χρησιμοποίησε ο ίδιος ο Γκράχαμ κατά την διατύπωση του αριθμού του.

Χρήση

Ο αριθμός του Γκράχαμ σχετίζεται με το παρακάτω πρόβλημα της θεωρίας Ράμσεΐ:
Σύνδεσε κάθε ζεύγος γεωμετρικών κορυφών ενός υπερκύβου σε ν διαστάσεις ώστε να προκύψει ένας ολοκληρωμένος γράφος 2ν κορυφών. Χρωμάτισε κάθε ένα από τα άκρα του γράφου είτε ερυθρό είτε κυανό. Ποια είναι η μικρότερη τιμή του ν για την οποία κάθε τέτοιος χρωματισμός περιέχει τουλάχιστον έναν μονοχρωματισμένο ολοκληρωμένο υπογράφο σε τέσσερις ομοεπίπεδες κορυφές;
Το 1971, οι Γκράχαμ και Ρόθτσιλντ έλυσαν το πρόβλημα αυτό αποδεικνύοντας πως η λύση είναι N*, όπου ισχύει η συνθήκη ορίου 6 ≤ N* ≤ N, με το N να αποτελεί έναν μεγάλο αλλά ρητά καθορισμένο αριθμό , όπου  στη σημειολογία Κνουθ άνω βέλους. Με την εναλλακτική μέθοδο της αλυσιδωτής σημειολογίας βέλους Κόνγουεϊ ο αριθμός είναι μεταξύ 4 → 2 → 8 → 2 και 2 → 3 → 9 → 2. Το 2004 σμικρύνθηκε μέσω των άνω ορίων στον αριθμό Χέιλς-Τζιούετ σε . Το 2003 το κάτω όριο διαμορφώθηκε από 6 σε 11, και το 2008 σε 13. Έτσι τα εκτιμώμενα όρια για το N* είναι 13 ≤ N* ≤ N'.

Μέγεθος

Προσεγγιστικά, ο αριθμός των 3αριών σε κάθε επίπεδο, αν αναπαριστώνταν σε εκθετική μορφή θα περιείχε το παρακάτω αριθμούς σε κάθε εκθέτη (σύνολο ψηφίων έτσι ώστε να αναπαρασταθεί ο αριθμός του εκθέτη):
ν=1  1ο επίπεδο εκθέτη:  3
     
ν=2  2ο επίπεδο εκθέτη:  3↑3↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 3) = 7625597484987
     
ν=3  3ο επίπεδο εκθέτη:  3↑3↑3↑3↑...↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 7625597484987) = …
     
      ⋮
     
ν=ν g₁ = νό επίπεδο:  3↑3↑3↑3↑3↑3↑3↑...↑3 (σύνολο 3αριών από το ν-1ό επίπεδο)
όπου το σύνολο τριαριών για κάθε επίπεδο εκθέτη δίνεται από το αμέσως προηγούμενο επίπεδο. Ακόμη και το ίδιο το ν το οποίο είναι απλώς το σύνολο των επιπέδων εκθέτη, είναι αφάνταστα μεγάλο και δεν μπορεί να αναπαρασταθεί.