מחשב-על סייע לפתור בעיה מתמטית בת 30 שנה, אך ההישג מעורר מחלוקת בשאלת אופיו של המחקר המתמטי בעתיד
חוקרים מארצות הברית ומאנגליה פרסמו לאחרונה את ההוכחה המתמטית הארוכה ביותר שנכתבה עד כה. ההוכחה היא קובץ שגודלו כ-200 טרה-בייט (TeraByte, או בקיצור TB). כדי להוריד את ההוכחה תצטרכו לצרוב כ-280,000 דיסקים. בניגוד להיקף העצום של ההוכחה, מפתיע לראות כמה קלה להבנה הבעיה שהם פתרו. הסוגיה גם מעוררת שאלה פילוסופית מעניינת: האם מסמך ששום בן אנוש לא יצליח לקרוא מפאת אורכו קביל כהוכחה מתמטית?
השאלה שפתרו החוקרים היא "בעיית השלשות הפיתגוריות" (Boolean Pythagorean triples problem), שהמתמטיקאי האמריקאי רונלד גרהם (Graham) ניסח בשנות השמונים. שלשה פיתגורית היא קבוצה של שלושה מספרים (a, b, c) המקיימים את הקשר המוגדר במשפט פיתגורס: a2 + b2 = c2. למשל: 3, 4, 5 הם שלשה כזו (9+16=25). גרהם שאל אם אפשר לחלק סט של מספרים טבעיים (שלמים וחיוביים) מ-1 עד N לשתי קבוצות כך שאף אחת מהן לא תכלול שלשה פיתגורית. במילים אחרות, אם אפשר לצבוע כל מספר בין 1 ל-N באדום או בכחול כך שכל השלשות הפיתגוריות לא ייצבעו באותו צבע. גרהם אף הציע פרס של 100 דולר למי שיפתור את הבעיה, ואכן נאלץ להעניק את הסכום הזה לקבוצה שפתרה אותה כעת.
מארין יול (Heule) מאוניברסיטת טקסס, ויקטור מארק (Marek) מאוניברסיטת קנטקי ואוליבר קולמן (Kullmann) מאוניברסיטת סוונסי הבריטית הוכיחו שיש פתרון לבעיה עד למספר N = 7,824. כלומר, את אוסף המספרים שבין 1 ל-7,824 אפשר לחלק לשתי קבוצות כך שבכל קבוצה אין שום שלשה פיתגורית. במאמר שפורסם בינתיים רק באתר הפרסום המקדים Arxiv, הם גם הוכיחו כי בעבור N = 7,825 כבר אין פתרון, ואי-אפשר לחלק את קבוצת המספרים בלי לכלול שלשה פיתגורית באותה קבוצה.
מספר האפשרויות של חלוקת 7,824 מספרים לשתי קבוצות הוא 27,824, כלומר בערך 102,300. בעזרת חישובי סימטריה הצליחו החוקרים לצמצם מאוד את מספר האפשרויות, בערך לטריליון אחד (1012). גם סקירת האפשרויות האלה הייתה אמורה להימשך כ-35,000 שעות (כמעט ארבע שנים) בכוח חישוב קונוונציונלי. אך בעזרת מחשב-על של אוניברסיטת טקסס, ובו 800 מעבדים שחישבו בו-זמנית, הצליחו החוקרים לסיים את החישוב ביומיים בלבד.
חשבון נפש
בעיית השלשות הפיתגוריות היא חלק מאוסף של בעיות דומות בתורת רמזי (Ramsey theory), תחום במתמטיקה העוסק בקומבינטוריקה ובמציאת תבניות מתמטיות בקבוצות גדולות של מספרים. בשונה מהוכחות שאנו רגילים אליהן בתחומים כמו גיאומטריה, המורכבות מאוסף של משפטים לוגיים שבני אדם יכולים לקרוא ולהבין, פתרון בעיות בתורת רמזי ובתחומים דומים אחרים מצריך לעתים הוכחות ארוכות המורכבות מחישובים שאפשריים רק באמצעות מחשב.
המחקר החדש פתר את בעיית השלשות הפיתגוריות, ונראה שמחשבים ישובו לפצח שאלות מתמטיות גם בעתיד. קשה שלא לתהות: האם זו אכן מתמטיקה? האם עולם המתמטיקה עוסק באיסוף עובדות על מספרים, כפי שנעשה בפתרון הזה, או בהעמקת הבנתנו את עולם המספרים?
ההוכחה הארוכה ביותר בעולם אינה מסבירה מה מיוחד כל כך במספר 7,825 שדווקא ממנו והלאה אין פתרון לבעיה. נראה שהדיון על תרומתן של הוכחות מסוג זה להתקדמות המתמטיקה יישאר פתוח בזמן הקרוב. מה שבטוח, ההוכחה הארוכה בעולם שווה לפחות 100 דולר, גם בלי הסבר תיאורטי של פתרון הבעיה.
