במשך קרוב ל-40 שנה, השערה קטנה ופשוטה יושבת בשקט בפינה של תורת הגרפים, ומתעסקת בעניינים שלה. המכונה "השערת מיטת קומותיים", היא תמיד נראתה די נכונה מובן מאליו - בטח, אף אחד לא יכול היהלְהוֹכִיחַזה, אבל זה היה הגיוני - ובוודאי, אף אחד מעולם לא מצא דוגמה נגדית.
עד עכשיו. בהפתעה כמעט לכולם, קבוצה של מתמטיקאים הודיעה בחודש שעבר על מאמר שלטענתם מוכיח שההשערה שקרית. העיתון, שפורסם כעת בשרת ה-preprint של arXiv, ולפיכך עדיין לא זכה לביקורת עמיתים, בכל זאת כבר מכה גלים בעולם המתמטי - לא רק בגלל ההוכחה עצמה, אלא בגלל מה שהוא אומר על מתמטיקה כמשמעת שלמה.
ההשערה
הונחה לראשונה על ידי הפיזיקאי פיטר קסטליןלעמית ב-1985, השערת מיטת הקומתיים באמת לא קשורה למיטות בכלל. במקום זאת, זה נוגע לגרפים - אלא אם כן אתה מתמטיקאי עובד, כנראה לא מסוג הגרפים שאתה חושב עליהם עכשיו.
"גרף מורכב מחבורה של קודקודים וחבורה של קצוות המחברים את הקודקודים", מסביר Trefor Bazett, עוזר פרופסור להוראה במחלקה למתמטיקה וסטטיסטיקה באוניברסיטת ויקטוריה, ב-סרטון YouTube האחרוןלגבי ההוכחה.
גרף עם שישה קודקודים ושמונה קצוות.
קרדיט תמונה: IFLScience
"אתה יכול לדמיין, אולי,", הוא מציע, "ואז הקשר הוא אם אתם חברים או לא."
הכפילו את הגרף הזה בדיוק, ותוכלו ליצור מה שמכונה גרף מיטת קומותיים: שני גרפים זהים זה על גבי זה, מחוברים באמצעות "פוסטים". תראה, ברגע שאתה רואה את זה באופן אישי, אתה תבין את כל הטרמינולוגיה בנושא.
אותו גרף הוכנס לצורת מיטת קומותיים. הקודקודים הוורודים האלה נקראים עמודי המיטה.
קרדיט תמונה: IFLScience
אז, יש לנו את ההגדרה שלנו - החברות שלנו בין אנשים, או מיקומים על מפה המחוברים ברחובות, או כל מה שאתה מדמיין שהגרף שלך מייצג. עכשיו אנחנו רק הולכים לחשוב איך לעבור דרך הגרף עצמו - אז, נניח שאתה רוצה להגיע מנקודהuלהצביעvבגרף שלנו למעלה, יש לנו את האפשרויות הבאות:
ארבעה מסלולים פוטנציאליים (לא ממצה!) מuאֶלvמודגש באדום.
קרדיט תמונה: IFLScience
איתנו עד כה? נהדר, כי זה המקום שבו הדברים מסתבכים קצת יותר. מה שאנחנו הולכים לעשות עכשיו זה למחוק חלק מהקצוות - לאבד חברים; חסום רחובות, מה שתרצה - ותראה כמה סביר שעוד נוכל להגיע משםuאֶלvלאחר מכן.
אז, עם כל הרקע הזה, אנחנו יכולים עכשיו להגיע להצהרה של השערת מיטת קומותיים, שהיא זו:פ(u↔v) ≥פ(u↔v').
"זה אומר שההסתברות שאני יכול לקבל ממנהuאֶלv– כלומר, ההסתברות שאוכל לנוע לאורך הבסיס – גדולה או שווה להסתברות שאוכל להתחיל בבסיס ואז להגיע לv'[…] על הדרגש העליון", הסביר באזט.
"ההשערה אומרת שזה נכון לכל הגרפים המחוברים, וכל תת-קבוצות של עמודי מיטה, וכל הזוגותuוv."
אינטואיטיבית, זה הגיוני: בוודאי, יהיה קל יותר להגיע לנקודת קצה באותה רמה כמו נקודת ההתחלה שלך מאשר לנקודה שמחייבת אותך לנסוע גם במעלה עמוד המיטה. ניסיון של כמה דוגמאות רק יחזק את האמונה הזאת - אלא אם כן, כלומר, אתה מוכן לבנות גרף עם כמה אלפי קודקודים וקצוות.
ההוכחה
לעתים קרובות, במתמטיקה, להפריך השערה קל יותר מאשר להוכיח אותה. אחרי הכל, כדילְהוֹכִיחַמשהו, אתה צריך להראות שזה נכון עבור כל דוגמה אפשרית, בכל המצבים - כדילְהַפְרִיךזה, אתה רק צריך למצוא דוגמה נגדית אחת.
הבעיה עם השערת מיטת קומותיים הייתה - ובכן, אף אחד לא חיפש את הדוגמה הנגדית הזו. "למה לחפש דוגמה נגדית אם ההשערה כל כך ברורה נכונה?" כתב איגור פאק, פרופסור למתמטיקה ב-UCLA ואחד ממחבריו של המאמר החדש, בפוסט בבלוגעל פריצת הדרך.
"ובכן, כי אתה תמיד צריך," הוא השיב. "לכל השערה. במיוחד אם כל השאר כךבַּטוּחַ, כמו בבטוח לחלוטין ללא ספק, שההשערה נכונה."
עכשיו, זה שנות ה-2020; אתה יודע, וכך גם פאק. "התחלנו עם מספר עצום של ניסויי מחשב שניסו את כל הגרפים הקטנים", כתב. "כאשר אלה נכשלו, ניסינו להשתמש בבינה מלאכותית ובכלים אחרים בעזרת מחשב."
למרות זאת, נראה שלא היו דוגמאות נגדיות - והצוות התחיל לדאוג שגם אם אחת אכן תופיע, זה לא יספיק כדי להפריך לחלוטין את ההשערה. הגרפים שנדגמו על ידי הרשתות העצביות היו כה גדולים באותה נקודה שחישוב ההסתברויות הרלוונטיותבְּדִיוּקיהיה בלתי אפשרי, ולכן כל הוכחה תהיה במקרה הטוב משהו כמו 99.9999 אחוז בטוח שהיא נכונה.
אבל בעוד ש"99.99 אחוז אמון […] עשוי להיות תקן זהב בפיזיקה גרעינית", כתב פאק, "כתבי עת למתמטיקה נוטים להעדיף 100 אחוז נכונות".
"רוב כתבי העת היו מסרבים אפילולִשְׁקוֹלא'חמש סיגמאדוגמה נגדית'", הוסיף.
לכן, במקום להתמיד בטכניקות למידת מכונה שלא נשאו פרי – וייתכן שתוצאותיהן לא יתקבלו גם אם היא הייתה מוצלחת – הצוות לקח צעד אחורה. ואז, ביוני השנה, אנְיָרפגע ב-arXiv ששינה הכל.
"מצאתי את זה בערב, וקראתי את זה עד שלוש לפנות בוקר", סיפרה ניקיטה גלדקוב, אחת הסטודנטיות לתארים מתקדמים של פאק ושותפה למחברת העיתון.קוונטה. "הייתי כמו, 'וואו, זה מטורף. בהחלט מטריף נפש'".
זו לא הייתה הוכחה להשערת מיטת הקומותיים בדיוק, אבל היא הייתה קרובה - ניסוח של ההצהרה שעסק באובייקטים שנקראים היפרגרפים, ולא בגרפים. המחבר, סטודנט לתואר שני באוניברסיטת קיימברידג' וגוגולוגית מוכשרתבשם לורנס הולום, הראה כי בחפצים הללו, השערת מיטת קומותיים הייתה... שקרית.
הולום הציג את עבודתו כניסיון להכליל את השערת מיטת קומותיים - או, כפי שהתברר, להראות שאי אפשר להכליל אותה. עם זאת, בסופו של דבר, המאמר שלו היה זה שיהווה השראה להוכחה של ההשערה המקורית.
על ידי המרת ההיפרגרף של הולום, הצוות יצר גרף שעלול להפריך את השערת מיטת קומותיים. זה היה מפלצתי לחלוטין - 7,222 קודקודים, מחוברים ב-14,442 קצוות - וההבדל בהסתברויות הרלוונטיות היה זעום: "קטן מבחינה אסטרונומית", כתב פאק, "בסדר גודל של -10-6500."
"אבל זה שלילי, וזה כל מה שאנחנו צריכים", הוסיף. ההשערה הייתה שקרית רשמית.
התוצאה
אז מה זה אומר, מלבד המובן מאליו? ובכן, יש כמה אכזבות, במיוחד עבור מתמטיקאים ופיזיקאים שימושיים: אילו השערת מיטת הדרגש הייתה מתבררת כנכונה, היא הייתה מאששת הנחה רווחת לגבי האופן שבו נוזלים עוברים דרך מוצקים, ונותנת אחיזה לחוקרים החוקרים את הפיזיקה של חלחול. .
אבל יותר מזה, יש את ההשפעות המוסריות של פריצת הדרך. האם מתמטיקאים עתידיים צריכים להיות מוכנים יותר לקבל הוכחות הסתברותיות? האם הם יהיו תקפים באותה מידה, או כמו שלמים?
"זו שאלה פילוסופית", אמרה לקוואנטה נגה אלון, פרופסור למתמטיקה בפרינסטון. "איך אנחנו רואים הוכחות שנכונות רק בסבירות גבוהה?"
"אולי הוכחה הסתברותית תיתן לך פחות הבנה או אינטואיציה לגבי מה באמת קורה", אמר.
לבסוף, זו אזהרה למתמטיקאים לא לקבל השערה רק בגלל שהם אוהבים אותה. "אנחנו צריכים להיות חשדניים, אפילו לגבי דברים שנראים אינטואיטיבית מאוד נכונים", אמר אלון.
זה סנטימנט שפאק דוגל בו זמן רב. "חלק מההשערות מונעות על ידי מהות", אמר לקוואנטה, "והשערות אחרות מונעות על ידי משאלת לב".
השערת מיטת הקומתיים, כך נראה, הייתה האחרונה.
ניתן למצוא את המאמר, שעדיין לא עבר ביקורת עמיתים, באתרarXiv.
