מבוא
באמצע אוקטובר, ג'סטין גילמר טס מקליפורניה לניו יורק כדי להשתתף בחתונה של חבר. בעודו בחוף המזרחי הוא ביקר את יועצו לשעבר, מייקל סאקס, מתמטיקאי באוניברסיטת רוטגרס, שם קיבל גילמר את הדוקטורט שלו שבע שנים קודם לכן.
סאקס וג'ילמר תפסו בארוחת צהריים, אבל הם לא דיברו על מתמטיקה. למעשה, גילמר לא חשב ברצינות על מתמטיקה מאז שסיים בראטגרס ב-2015. אז הוא החליט שהוא לא רוצה קריירה באקדמיה ובמקום זאת התחיל ללמד את עצמו לתכנת. בזמן שהוא וסאקס אכלו, גילמר סיפר למנטור הוותיק שלו על עבודתו בגוגל, שם הוא עובד על למידת מכונה ובינה מלאכותית.
היה שמש ביום שגילמר ביקר בראטגרס. כשהסתובב, הוא נזכר איך ב-2013 הוא בילה את החלק הטוב ביותר של שנה בהליכה באותם שבילי הקמפוס, וחשב על בעיה שנקראת ההשערה הסגורה של האיגוד. זה היה קיבעון, אם כי עקר: למרות כל מאמציו, גילמר הצליח רק ללמד את עצמו מדוע קשה כל כך לפתור את הבעיה הפשוטה של קבוצות של מספרים.
"אני חושב שהרבה אנשים חושבים על הבעיה עד שהם מרוצים שהם מבינים למה זה קשה. כנראה שביליתי בזה יותר זמן מרוב האנשים", אמר גילמר.
בעקבות ביקורו באוקטובר, קרה משהו בלתי צפוי: הוא קיבל רעיון חדש. גילמר החל לחשוב על דרכים ליישם טכניקות מתורת המידע כדי לפתור את השערת האיחוד הסגור. הוא רדף אחרי הרעיון במשך חודש, בכל שלב ציפה שהוא ייכשל. אבל במקום זאת, הדרך להוכחה המשיכה להיפתח. לבסוף, ב-16 בנובמבר הוא פרסם תוצאה ראשונה מסוגה זה מביא למתמטיקאים חלק גדול מהדרך להוכחת ההשערה המלאה.
העיתון עורר מבול של עבודות המשך. מתמטיקאים מאוניברסיטת אוקספורד, המכון הטכנולוגי של מסצ'וסטס והמכון ללימודים מתקדמים, בין מוסדות אחרים, בנו במהירות על השיטות החדשות של גילמר. אבל לפני שעשו זאת, הם שאלו שאלה משלהם: מי זה הבחור הזה?
חצי מלא
ההשערה הסגורה באיחוד עוסקת באוספים של מספרים הנקראים קבוצות, כגון {1, 2} ו-{2, 3, 4}. אתה יכול לבצע פעולות על סטים, כולל לקיחת האיחוד שלהם, כלומר שילוב ביניהם. לדוגמה, האיחוד של {1, 2} ו-{2, 3, 4} הוא {1, 2, 3, 4}.
אוסף, או משפחה, של סטים נחשבים "סגורים באיחוד" אם האיחוד של שני סטים במשפחה שווה לכל סט קיים במשפחה. לדוגמה, שקול את המשפחה הזו של ארבע קבוצות:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
שלבו כל זוג ותקבלו סט שכבר נמצא במשפחה, מה שהופך את איגוד המשפחה לסגור.
מתמטיקאים שוחחו על גרסאות של השערת האיחוד הסגור עוד בשנות ה-1960, אבל היא קיבלה את ההצהרה הרשמית הראשונה שלה ב-1979, במאמר של פיטר פרנקל, מתמטיקאי הונגרי שהיגר ליפן בשנות ה-1980 ומספר הופעות רחוב בין עיסוקיו.
פרנקל שיער שאם משפחת קבוצות סגורה על ידי איגוד, עליה להיות לפחות אלמנט (או מספר) אחד שמופיע לפחות במחצית הקבוצות. זה היה סף טבעי משתי סיבות.
ראשית, ישנן דוגמאות זמינות למשפחות סגורות באיגודים, שבהן כל האלמנטים מופיעים בדיוק ב-50% מהקבוצות. כמו כל הסטים השונים שאתה יכול לעשות מהמספרים 1 עד 10, למשל. יש 1,024 קבוצות כאלה, היוצרות משפחה סגורה באיחוד, וכל אחד מ-10 האלמנטים מופיע ב-512 מהן. ושנית, בזמן שפרנקל העלה את ההשערה אף אחד מעולם לא הביא דוגמה למשפחה סגורה באיגוד שההשערה בה לא התקיימה.
אז 50% נראו כמו התחזית הנכונה.
זה לא אומר שקל להוכיח. בשנים שחלפו מאז המאמר של פרנקל, היו מעט תוצאות. לפני עבודתו של גילמר, אותם מסמכים הצליחו לקבוע רק ספים שהשתנו עם מספר הסטים במשפחה (בניגוד להיותו אותו סף של 50% עבור משפחות סט בכל הגדלים).
"זה מרגיש שזה צריך להיות קל, וזה דומה להרבה בעיות קלות, אבל זה התנגד להתקפות", אמר וויל סוין מאוניברסיטת קולומביה.
חוסר ההתקדמות שיקף הן את אופייה המסובך של הבעיה והן את העובדה שמתמטיקאים רבים העדיפו לא לחשוב עליה; הם חששו שהם יפסידו שנים מהקריירה שלהם במרדף אחר בעיה מפתה שאי אפשר לפתור. גילמר זוכר יום ב-2013 שבו הלך למשרד של סאקס והעלה את השערת האיגוד הסגור. היועץ שלו - שבעבר נאבק בבעיה בעצמו - כמעט זרק אותו מהחדר.
"מייק אמר, 'ג'סטין, אתה תגרום לי לחשוב על הבעיה הזו שוב ואני לא רוצה לעשות את זה'", אמר גילמר.
תובנה של אי ודאות
לאחר ביקורו בראטגרס, גילמר גילמר את הבעיה במוחו, וניסה להבין מדוע זה כל כך קשה. הוא דחף את עצמו עם עובדה בסיסית: אם יש לך משפחה של 100 סטים, יש 4,950 דרכים שונות לבחור שניים ולקחת את האיחוד שלהם. ואז הוא שאל את עצמו: איך יתכן ש-4,950 איגודים שונים ממפים חזרה ל-100 סטים בלבד אם לא מופיע אלמנט באיגודים האלה בתדירות מסוימת לפחות?
אפילו באותו שלב הוא היה בדרך להוכחה, למרות שעדיין לא ידע זאת. טכניקות מתורת המידע, המספקות דרך קפדנית לחשוב למה לצפות כשמושכים זוג חפצים באקראי, היו לוקחות אותו לשם.
תורת המידע התפתחה במחצית הראשונה של המאה ה-20, המפורסם ביותר עם מאמרו של קלוד שאנון משנת 1948, "תיאוריה מתמטית של תקשורת." המאמר סיפק דרך מדויקת לחישוב כמות המידע הדרושה לשליחת הודעה, בהתבסס על כמות אי הוודאות לגבי מה בדיוק יגיד ההודעה. הקישור הזה - בין מידע לאי ודאות - הייתה התובנה המופלאה והיסודית של שאנון.
כדי לקחת דוגמה צעצוע, דמיינו שאני מטיל מטבע חמש פעמים ושולח אליכם את הרצף שנוצר. אם זה מטבע רגיל, נדרשות חמש סיביות מידע לשדר. אבל אם זה מטבע טעון - נגיד, סבירות של 99% שינחת על ראשים - זה דורש הרבה פחות. לדוגמה, נוכל להסכים מראש שאשלח לך 1 (פיסת מידע בודדת) אם המטבע הנטען ינחת בראש כל חמש הפעמים, מה שסביר מאוד שיעשה. יש יותר הפתעה בתוצאה של הטלת מטבע הוגנת מאשר עם מטבע מוטה, ולכן יותר מידע.
אותה חשיבה חלה על המידע הכלול בקבוצות של מספרים. אם יש לי משפחה של סטים סגורים - נניח 1,024 סטים שנעשו מהמספרים 1 עד 10 - אני יכול לבחור שני סטים באקראי. אז אוכל להעביר לך את המרכיבים של כל סט. כמות המידע שנדרש כדי לשלוח את ההודעה הזו משקפת את כמות אי הוודאות סביב המרכיבים האלה: יש סיכוי של 50%, למשל, שהאלמנט הראשון בקבוצה הראשונה הוא 1 (מכיוון ש-1 מופיע בחצי מהקבוצות ב- המשפחה), בדיוק כפי שיש סיכוי של 50% שהתוצאה הראשונה ברצף של הטלות מטבעות הוגנת היא ראשים.
תורת המידע מופיעה לעתים קרובות בקומבינטוריקה, תחום במתמטיקה העוסק בספירת עצמים, וזה מה שלמד גילמר כסטודנט לתואר שני. אבל כשטס חזרה הביתה לקליפורניה, הוא דאג שהדרך שבה חשב לחבר את תיאוריית המידע להשערת האיגודים הסגורים הייתה תובנה נאיבית של חובבן: בטח מתמטיקאים עובדים נתקלו בעבר בחפץ הנוצץ הזה וזיהו אותו בתור זהב של שוטים. .
"למען האמת, אני קצת מופתע שאף אחד לא חשב על זה קודם", אמר גילמר. "אבל אולי אני לא צריך להיות מופתע, כי אני עצמי חשבתי על זה במשך שנה, והכרתי את תורת המידע".
סביר יותר מאשר לא
גילמר עבד על הבעיה בלילה, לאחר שסיים את עבודתו בגוגל, ובסופי שבוע לאורך המחצית השנייה של אוקטובר ותחילת נובמבר. הוא התעודד מרעיונות שקבוצת מתמטיקאים חקרה שנים קודם לכן שיתוף פעולה פתוח בבלוג של מתמטיקאי בולט בשם טים גוורס. הוא גם עבד עם ספר לימוד לצדו כדי שיוכל לחפש נוסחאות ששכח.
"אתה חושב שמישהו שמגיע לתוצאה מצוינת לא צריך להתייעץ עם פרק 2 של אלמנטים של תורת המידע, אבל עשיתי זאת, "אמר גילמר.
האסטרטגיה של גילמר הייתה לדמיין משפחה סגורה באיגוד שבה אף אלמנט לא הופיע אפילו ב-1% מכל הסטים - דוגמה נגדית שאם היא באמת הייתה קיימת, תזייף את השערתו של פרנקל.
נניח שאתה בוחר שתי קבוצות, A ו-B, ממשפחה זו באקראי ותשקול את האלמנטים שיכולים להיות בקבוצות האלה, אחד בכל פעם. עכשיו שאל: מה הסיכויים שקבוצה A מכילה את המספר 1? וסט ב'? מכיוון שלכל רכיב יש קצת פחות מ-1% סיכוי להופיע בכל סט נתון, לא היית מצפה ש-A או B יכילו 1. מה שאומר שאין הפתעה קטנה - ומעט מידע שהושג - אם תלמד שאף אחד מהם לא למעשה עושה.
לאחר מכן, חשבו על הסיכוי שהאיחוד של A ו-B מכיל 1. זה עדיין לא סביר, אבל סביר יותר מהסיכויים שהוא יופיע בכל אחת מהקבוצות הבודדות. זה סכום הסבירות שהוא מופיע ב-A והסבירות שהוא מופיע ב-B פחות הסבירות שהוא מופיע בשניהם. אז אולי קצת פחות מ-2%.
זה עדיין נמוך, אבל זה קרוב יותר להצעה של 50-50. זה אומר שצריך יותר מידע כדי לשתף את התוצאה. במילים אחרות, אם יש משפחה סגורה באיחוד שבה לא מופיע אלמנט ב-1% לפחות מכל הקבוצות, יש יותר מידע באיחוד של שתי קבוצות מאשר בכל אחת מהקבוצות עצמן.
"הרעיון לחשוף דברים אלמנט אחר אלמנט ולהסתכל על כמות המידע שאתה לומד הוא חכם ביותר. זה הרעיון המרכזי של ההוכחה", אמר ריאן אלוויס מאוניברסיטת פרינסטון.
בשלב זה גילמר התחיל להסתגר על השערתו של פרנקל. הסיבה לכך היא שקל להדגים שבמשפחה סגורה באיגוד, האיחוד של שני סטים מכיל בהכרח פחות מידע מהקבוצות עצמם - לא יותר.
כדי להבין מדוע, חשבו על אותה משפחה סגורה באיחוד המכילה את 1,024 הקבוצות השונות שתוכלו ליצור מהמספרים 1 עד 10. אם תבחרו שתיים מהקבוצות הללו באקראי, בממוצע תקבלו קבוצות המכילות חמישה אלמנטים. (מתוך 1,024 סטים אלה, 252 מכילים חמישה אלמנטים, מה שהופך את זה לגודל הסט הנפוץ ביותר.) סביר להניח שגם תקבל איחוד המכיל כשבעה אלמנטים. אבל יש רק 120 דרכים שונות ליצור סטים המכילים שבעה אלמנטים.
הנקודה היא שיש יותר אי ודאות לגבי התוכן של שתי קבוצות שנבחרו באקראי מאשר לגבי האיחוד שלהם. האיחוד נוטה לסטים גדולים יותר עם יותר אלמנטים, שעבורם יש פחות אפשרויות. כשאתה לוקח את האיחוד של שני סטים במשפחה סגורה, אתה די יודע מה אתה הולך לקבל - כמו כשאתה מניף מטבע מוטה - מה שאומר שהאיחוד מכיל פחות מידע מהקבוצות שמהן הוא מורכב.
עם זה, לגילמר הייתה הוכחה. הוא ידע שאם לא מופיע אלמנט אפילו ב-1% מהקבוצות, האיגוד נאלץ להכיל מידע נוסף. אבל האיגוד חייב להכיל פחות מידע. לכן חייב להיות לפחות אלמנט אחד שמופיע לפחות ב-1% מהקבוצות.
הדחיפה ל-50
כשגילמר פרסם את ההוכחה שלו ב-16 בנובמבר, הוא כלל הערה שלדעתו אפשר להשתמש בשיטתו כדי להתקרב עוד יותר להוכחה של ההשערה המלאה, מה שעלול להעלות את הרף ל-38%.
חמישה ימים לאחר מכן, שְׁלוֹשָׁה אחר קבוצות של מתמטיקאים פרסמו מאמרים תוך שעות אחד מהשני, שנבנו על עבודתו של גילמר לעשות בדיוק את זה. נוסף ניירות בעקבות, אבל נראה שהפרץ הראשוני לקח את שיטותיו של גילמר עד כמה שיגיעו; להגיע ל-50% כנראה ייקח רעיונות חדשים נוספים.
ובכל זאת, עבור חלק ממחברי מאמרי ההמשך, להגיע ל-38% היה פשוט יחסית, והם תהו מדוע גילמר לא עשה זאת רק בעצמו. ההסבר הפשוט ביותר התברר כנכון: אחרי יותר מחצי עשור של מתמטיקה, גילמר פשוט לא ידע איך לעשות חלק מהעבודה האנליטית הטכנית שנדרשה כדי להוציא את זה.
"הייתי קצת חלוד, ולמען האמת, הייתי תקוע", אמר גילמר. "אבל הייתי להוט לראות לאן הקהילה תיקח את זה".
עם זאת גילמר חושב שאותן נסיבות שהותירו אותו מחוץ לעיסוק כנראה אפשרו את ההוכחה שלו מלכתחילה.
"זו הדרך היחידה שאני יכול להסביר מדוע חשבתי על הבעיה במשך שנה בבית הספר לתארים מתקדמים ולא התקדמתי, עזבתי את המתמטיקה לשש שנים, ואז חזרתי לבעיה ועשיתי את פריצת הדרך הזו", אמר. "אני לא יודע איך להסביר את זה מלבד היותי בלמידת מכונה הטיה את החשיבה שלי."
תיקון: ינואר 3, 2023
הכותרת המקורית התייחסה לגילמר כ"מהנדס גוגל". למעשה, הוא חוקר.
