מספר גרהאם

מספר גרהאם הוא מספר גדול ששימש כחסם עליון לבעיה בקומבינטוריקה בהוכחה של המתמטיקאי רונלד גרהאם (אנ'). המספר התפרסם בקרב חובבי המתמטיקה לאחר שמרטין גרדנר כתב עליו בטור הפופולרי שלו Mathematical Games בירחון "סיינטיפיק אמריקן" בנובמבר 1977. המספר תואר על ידי גרדנר בתור "המספר הגדול ביותר שאי-פעם שימש בהוכחה מתמטית רצינית".

מספר גרהאם גדול משמעותית ממספרים גדולים אחרים כגון גוגול ( $\ 10^{100}$ ), גוגולפלקס ( $10^{10^{100}}$ ) ואפילו ממספר סקיוז הראשון ( $e^{e^{e^{79}}}$ ). אין מספיק מקום ביקום הנראה כדי לכתוב את מספר גראהם בכתיב עשרוני. אפילו אם ננסה לכתוב את המספר כמגדל חזקות וכל ספרה תהיה בסדר גודל של אורך פלאנק לא יהיה לכך די מקום ביקום. במהדורת ספר השיאים של גינס משנת 1980 הוכר מספר גרהאם כמספר הגדול ביותר בעל שימוש, אולם מאז פורסמו הוכחות בהן הופיעו מספרים גדולים אף יותר.

בעיית גרהאם

מקורו של מספר גרהאם בבעיה הבאה מתורת רמזי:

בהינתן היפרקובייה n-ממדית (הכללה של קובייה) מחברים את כל הקודקודים שלה כדי לקבל גרף שלם בעל $\ 2^{n}$ צמתים ( $\ K_{2^{n}}$ ). עתה צובעים כל קשת בגרף בצבע אדום או שחור. מהו הערך המינימלי של $\ n$ כך שלכל צביעה אפשרית של הגרף בהכרח יהיה קיים תת-גרף שלם עם ארבעה קודקודים, הנמצאים באותו המישור בהיפר-קובייה, שכולו צבוע באותו הצבע?

גרהאם וברוס לי רוטשילד הוכיחו ב-1971 כי לבעיה קיים פתרון $\ N^{*}$ והוכיחו כי $\ 6\leq N^{*}\leq N$ כאשר $\ N=F^{7}(12)$ תחת ההגדרה $F(n)=2\uparrow ^{n}3$ ( $\uparrow ^{n}$ הוא החץ של קנות' ו- $\ F^{m}(n)$ הוא הרכבת $\ F(n)$ על עצמו m פעמים). החסם התחתון שופר בשנת 2003 והחסמים העדכניים הם $\ 13\leq N^{*}\leq N$ .

מספר גרהאם שסומן ב- $\ G$ גדול בהרבה מ- $\ N$ שהופיע במאמר על הבעיה, והוא הופיע בעבודות מוקדמות יותר של גרהאם כחסם עליון ל- $\ N^{*}$ .

הגדרת מספר גרהאם

לא ניתן להגדיר ביעילות את מספר גרהאם בעזרת כתיב עשרוני או חזקות. אולם הדבר אפשרי בעזרת סימון החץ של קנות' והרכבת פונקציות. אם מגדירים $f(n)=3\uparrow ^{n}3$ אז ניתן להגדיר את מספר גרהאם: $\ G=f^{64}(4)$ . או בעזרת נוסחת נסיגה: אם מגדירים סדרה $g_{n}=3\uparrow ^{g_{n-1}}3$ כאשר תנאי ההתחלה הוא $g_{1}=3\uparrow ^{4}3$ אז מספר גרהאם הוא $\ G=g_{64}$ . כלומר:

\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 ^{4}3\end{matrix}}\right\}{\text{64 layers}}

בעזרת החץ של קונוויי ניתן גם לחסום בצורה נוחה את מספר גרהאם. מתקיים: $3\rightarrow 3\rightarrow 64\rightarrow 2=f^{64}(1)<G<f^{64}(27)=3\rightarrow 3\rightarrow 65\rightarrow 2$ . הדבר מדגים את כוחה של שיטת הסימון של קונוויי שמסוגלת בקלות לייצג מספרים גדולים מאוד שלא ניתן לייצג ביעילות באף דרך אחרת שיש בה שימוש.