'A-Team' של מתמטיקה מוכיח קשר קריטי בין חיבור לסטים | מגזין קוונטה

בקבוצה של מספרים שנבחרה באקראי, החיבור יכול להשתולל.

תחבר כל זוג מקבוצה כזו, ובסופו של דבר תהיה לך רשימה חדשה שסביר להניח שתכלול הרבה יותר מספרים ממה שהתחלת איתה. התחל עם 10 מספרים אקראיים, והרשימה החדשה הזו (הנקראת sumset) תכלול כ-50 אלמנטים. התחל עם 100 והסכום יהיה כנראה בסביבות 5,000; 1,000 מספרים ראשוניים אקראיים יהפכו סכום באורך של 500,000 מספרים.

אבל אם לקבוצה הראשונית שלך יש מבנה, הסכום יכול להסתיים עם פחות מספרים מזה. שקול עוד קבוצה של 10 מספרים: כל המספרים הזוגיים מ-2 עד 20. מכיוון שזוגות שונים יצטברו לאותו מספר - 10 + 12 זהה ל-8 + 14 ו-6 + 16 - לסכום יש רק 19 מספרים, לא 50. ההבדל הזה הופך עמוק יותר ויותר ככל שהסטים הולכים וגדלים. רשימה מובנית של 1,000 מספרים עשויה לכלול סכום הכולל רק 2,000 מספרים.

בשנות ה-1960, מתמטיקאי בשם גרגורי פריימן החלו לחקור קבוצות עם סכומים קטנים במאמץ לבחון את הקשר בין חיבור למבנה קבוצה - קשר מכריע המגדיר את התחום המתמטי של קומבינטוריקה תוספת. פריימן עשה התקדמות מרשימה, והוכיח שקבוצה עם סכום קטן חייבת להכיל קבוצה גדולה יותר שהאלמנטים שלה מרווחים בתבנית מאוד קבועה. אבל אז התחום עמד בקיפאון. "ההוכחה המקורית של פריימן הייתה קשה במיוחד להבנה, עד לנקודה שבה אף אחד לא באמת היה בטוח לחלוטין שהיא נכונה. אז לא באמת הייתה לזה את ההשפעה שאולי הייתה לו", אמר טימותי גוורס, מתמטיקאי בקולג' דה פראנס ובאוניברסיטת קיימברידג' וזוכה מדליסט פילדס. "אבל אז אימרה רוזסה פרץ למקום."

בסדרה של שתיים ניירות בשנות ה-1990, רוזסה הוכיחה מחדש את משפט פריימן בטיעון חדש ואלגנטי. כמה שנים לאחר מכן, קטלין מרטון, מתמטיקאי הונגרי רב השפעה שמת ב-2019, שיפר את השאלה מה מרמז סכום קטן על מבנה הסט המקורי. היא החליפה את סוגי האלמנטים שהופיעו בסט ואת סוג המבנה שהמתמטיקאים צריכים לחפש, מתוך מחשבה שתאפשר למתמטיקאים להוציא עוד יותר מידע. להשערה של מרטון יש קישורים למערכות הוכחה, לתיאוריית קידוד ולקריפטוגרפיה, והיא תופסת מקום נעלה בקומבינטוריקה הנוספת.

ההשערה שלה "מרגישה כמו באמת אחד הדברים הבסיסיים ביותר שלא הבנו", אמרה בן גרין, מתמטיקאי באוניברסיטת אוקספורד. זה "פשוט עמד בבסיס הרבה דברים שאכפת לי מהם".

גרין איחד כוחות עם גוורס, פרדי מנרס מאוניברסיטת קליפורניה, סן דייגו, ו טרנס טאו, מדליסט פילדס באוניברסיטת קליפורניה, לוס אנג'לס כדי ליצור את מה שהמתמטיקאי והבלוגר הישראלי גיל כלאי נקרא "צוות" של מתמטיקאים. הם הוכיחו גרסה של ההשערה במאמר שותף ב-9 בנובמבר.

נטס כץ, מתמטיקאי באוניברסיטת רייס, שלא היה מעורב בעבודה, מתאר את ההוכחה כ"פשוטה להפליא" - ו"פחות או יותר לגמרי לא ברורה".

לאחר מכן טאו התחיל במאמץ להמציא את ההוכחה להישען, שפת תכנות המסייעת למתמטיקאים לאמת משפטים. תוך מספר שבועות בלבד, המאמץ הזה הצליח. מוקדם בבוקר יום שלישי של 5 בדצמבר, הכריז טאו כי Lean הוכיח את ההשערה ללא כל "סליחה" - ההצהרה הסטנדרטית המופיעה כאשר המחשב אינו יכול לאמת שלב מסוים. זהו השימוש בעל הפרופיל הגבוה ביותר בכאלה כלי אימות מאז 2021, ומסמן נקודת פיתול בדרכים שבהן מתמטיקאים כותבים הוכחות במונחים שמחשב יכול להבין. אם הכלים האלה יהיו קלים מספיק למתמטיקאים להשתמש בהם, הם עשויים להיות מסוגלים להחליף את תהליך ביקורת עמיתים הממושך והמכביד, אמר גוורס.

מרכיבי ההוכחה רתחו במשך עשרות שנים. גוורס הגה את צעדיו הראשונים בתחילת שנות ה-2000. אבל לקח 20 שנה להוכיח את מה שקלאי כינה "גביע קדוש" של התחום.

ה-In-Group

כדי להבין את ההשערה של מרטון, זה עוזר להכיר את המושג קבוצה, אובייקט מתמטי המורכב מקבוצה ומפעולה. חשבו על המספרים השלמים - קבוצה אינסופית של מספרים - ועל פעולת החיבור. בכל פעם שאתה מוסיף שני מספרים שלמים יחד, אתה מקבל מספר שלם נוסף. הוספה מצייתת גם לכמה כללים אחרים של פעולות קבוצתיות, כמו אסוציאטיביות, המאפשרת לשנות את סדר הפעולות: 3 + (5 + 2) = (3 + 5) + 2.

בתוך קבוצה, לפעמים אתה יכול למצוא סטים קטנים יותר המספקים את כל מאפייני הקבוצה. לדוגמה, אם תוסיף שני מספרים זוגיים כלשהם, תקבל עוד מספר זוגי. המספרים הזוגיים הם קבוצה בפני עצמה, מה שהופך אותם לתת-קבוצה של המספרים השלמים. המספרים האי-זוגיים, לעומת זאת, אינם תת-קבוצה. אם אתה מחבר שני מספרים אי-זוגיים, תקבל מספר זוגי - לא בסט המקורי. אבל אתה יכול לקבל את כל המספרים האי-זוגיים פשוט על ידי הוספת 1 לכל מספר זוגי. תת-קבוצה מוזזת כמו זו נקראת coset. אין לה את כל המאפיינים של תת-קבוצה, אבל היא שומרת על המבנה של תת-הקבוצה שלה במובנים רבים. לדוגמה, בדיוק כמו המספרים הזוגיים, המספרים האי-זוגיים כולם מרווחים באופן שווה.

מרטון הניח שאם יש לך סט שנתקשר A מורכב ממרכיבי קבוצה שסכומם אינו גדול בהרבה מ A עצמו, אז קיימת תת-קבוצה כלשהי - קרא לזה G - עם נכס מיוחד. מִשׁמֶרֶת G כמה פעמים כדי ליצור cosets, ואלו cosets יכילו, ביחד, את הסט המקורי A. יתרה מכך, היא הניחה שמספר הקוסטים לא גדל הרבה יותר מהר מגודל הסכום - היא האמינה שיש לקשור אותו על ידי גורם פולינומי, בניגוד לצמיחה מעריכית מהירה בהרבה.

זה אולי נשמע כמו קוריוז טכני מאוד. אבל בגלל שזה מתייחס למבחן פשוט - מה קורה כשמוסיפים רק שני אלמנטים לסט? - למבנה הכולל של תת-קבוצה, זה חשוב מאוד למתמטיקאים ומדעני מחשב. אותו רעיון כללי מופיע כאשר מדעני מחשב מנסים להצפין הודעות כך שתוכל לפענח רק חלק מההודעה בזמן. היא מופיעה גם בהוכחות הניתנות לבדיקה הסתברותית, סוג של הוכחה שמדעני מחשבים יכולים לאמת על ידי בדיקת רק כמה פיסות מידע בודדות. בכל אחד מהמקרים האלה, אתה עובד רק עם כמה נקודות במבנה - פענוח רק כמה סיביות מהודעה ארוכה, או אימות חלק קטן מהוכחה מסובכת - ומסיק משהו לגבי מבנה גדול יותר, ברמה גבוהה יותר.

"אתה יכול להעמיד פנים שהכל הוא תת-קבוצה גדולה של קבוצה", אמר טום סנדרס, סטודנט לשעבר של Gowers שכיום הוא עמיתו של גרין באוקספורד, או שאתה יכול, "לשיג את כל מה שרצית מקיומם של צירופי מקרים רבים. שתי נקודות המבט הללו מועילות."

רוזסה פרסם את השערתו של מרטון ב-1999, נותן לה קרדיט מלא. "היא הגיעה להשערה הזו ללא תלות בי ובפריימן, וכנראה לפנינו", אמר. "בגלל זה, כשדיברתי איתה, החלטתי לקרוא לזה השערה שלה." ובכל זאת, מתמטיקאים מתייחסים אליו כעת כאל השערת פריימן-רוזה הפולינומית, או PFR.

אפסים ואחדים

קבוצות, כמו אובייקטים מתמטיים רבים, לובשות הרבה צורות שונות. מרטון הניחה שההשערה שלה נכונה לכל הקבוצות. זה עדיין לא הוצג. המאמר החדש מוכיח זאת עבור סוג מסוים של קבוצה, אשר לוקחת כמרכיביה רשימות של מספרים בינאריים כמו (0, 1, 1, 1, 0). מכיוון שמחשבים עובדים בבינארי, לקבוצה זו יש חשיבות מכרעת במדעי המחשב. אבל זה היה שימושי גם בקומבינטוריקה הוספה. "זה כמו מסגרת הצעצוע הזו שבה אתה יכול קצת לשחק ולנסות דברים", אמר סנדרס. "האלגברה הרבה הרבה יותר נחמדה" מאשר עבודה עם מספרים שלמים, הוא הוסיף.

לרשימות יש אורכים קבועים, וכל ביט יכול להיות 0 או 1. אתה מחבר אותם יחד על ידי הוספת כל ערך למקביל שלו ברשימה אחרת, עם הכלל ש-1 + 1 = 0. אז (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR הוא ניסיון להבין איך קבוצה יכולה להיראות אם היא לא ממש תת-קבוצה אבל יש לה כמה תכונות דמויות קבוצתיות.

כדי לדייק את ה-PFR, דמיינו שיש לכם קבוצה של רשימות בינאריות שנקראות A. עכשיו קח כל זוג אלמנטים מ A ולחבר אותם. הסכומים המתקבלים מהווים את הסכום של A, הנקרא A + A. אם האלמנטים של A נבחרים באופן אקראי, אז רוב הסכומים שונים זה מזה. אם יש k אלמנטים ב A, זה אומר שיהיו בסביבה k²/2 אלמנטים בסכום. מתי k הוא גדול - נניח, 1,000 - k²/2 הוא הרבה יותר גדול מ k. אבל אם A היא תת-קבוצה, כל אלמנט של A + A הוא ב A, כלומר A + A זהה בגודל כמו A עצמו.

PFR מחשיב קבוצות שאינן אקראיות, אך אינן גם תת-קבוצות. בקבוצות אלה, מספר האלמנטים ב A + A הוא מעט קטן - נגיד, 10k, או 100k. "זה ממש שימושי כשהמושג שלך של מבנה הוא הרבה יותר עשיר מאשר רק להיות מבנה אלגברי מדויק," אמר שחר לובט, מדען מחשבים באוניברסיטת קליפורניה, סן דייגו.

כל הקבוצות שידעו המתמטיקאים שצייתו למאפיין הזה "די קרובים לתת-קבוצות ממשיות", אמר טאו. "זו הייתה האינטואיציה, שלא היו עוד סוגים של קבוצות מזויפות ששוכבות בסביבה." פריימן הוכיח גרסה של הצהרה זו ביצירתו המקורית. בשנת 1999 הרחיבה רוזסה את משפט פריימן מהמספרים השלמים להגדרת רשימות בינאריות. הוא הוכיח כי כאשר מספר האלמנטים ב A + A הוא כפולה קבועה של הגודל של A, A כלול בתוך תת-קבוצה.

אבל המשפט של רוזסה דרש שתת-הקבוצה תהיה עצומה. התובנה של מרטון הייתה להניח את זה במקום להיות כלול בתת-קבוצה ענקית אחת, A יכול להיות כלול במספר פולינומי של קבוצות משנה של תת-קבוצה שאינה גדולה מהקבוצה המקורית A.

'אני יודע רעיון אמיתי כשאני רואה רעיון אמיתי'

בסביבות תחילת המילניום, גוארס נתקל בהוכחות של רוזסה למשפט פריימן תוך כדי לימוד בעיה אחרת לגבי קבוצות המכילות מחרוזות של מספרים ברווח שווה. "הייתי צריך משהו כזה, סוג של קבלת מידע מבני ממידע הרבה יותר רופף על סט מסוים", אמר גוורס. "היה לי מזל שזמן לא רב לפני כן, רוזסה הפיקה את ההוכחה המדהימה הזו".

גוורס החל למצוא הוכחה פוטנציאלית לגרסה הפולינומית של ההשערה. הרעיון שלו היה להתחיל עם סט A שהסכום שלו היה קטן יחסית, ואז לבצע מניפולציות בהדרגה A לתוך תת-קבוצה. אם יוכל להוכיח שתת-הקבוצה שהתקבלה דומה לסט המקורי A, הוא יכול היה להסיק בקלות שההשערה נכונה. גוורס שיתף את הרעיונות שלו עם עמיתים, אבל אף אחד לא הצליח ליצור מהם הוכחה מלאה. אף על פי שהאסטרטגיה של גאוארס הצליחה בחלק מהמקרים, במקרים אחרים המניפולציות לקחו A רחוק יותר מהמסקנה הרצויה של השערת הפולינום פריימן-רוזה.

בסופו של דבר, התחום המשיך הלאה. בשנת 2012, סנדרס כמעט הוכיח PFR. אבל מספר תת-הקבוצות המוזזות שהיה צריך היה מעל לרמת הפולינום, אם כי רק במעט. "ברגע שהוא עשה את זה, זה אומר שזה הפך לדבר פחות דחוף, אבל עדיין בעיה ממש נחמדה שיש לי חיבה גדולה אליה", אמר גוורס.

אבל הרעיונות של גאוארס חיו בזיכרונותיהם ובדיסקים הקשיחים של עמיתיו. "יש שם רעיון אמיתי," אמר גרין, שהיה גם תלמידו של גוורס. "אני יודע רעיון אמיתי כשאני רואה רעיון אמיתי." הקיץ הזה, גרין, נימוסים וטאו סוף סוף שיחררו את רעיונותיו של גאוארס מבית המצרף שלהם.

גרין, טאו ומיינרס היו בעומק של 37 עמודים בשיתוף פעולה לפני שחשבו לחזור לרעיונות בני ה-20 של גוורס. ב-23 ביוני מאמר, הם השתמשו בהצלחה במושג מתורת ההסתברות שנקרא משתנים אקראיים כדי לחקור את המבנה של קבוצות עם סכומים קטנים. על ידי ביצוע המעבר הזה, הקבוצה יכולה לתמרן את הסטים שלה ביתר עדינות. "ההתמודדות עם משתנים אקראיים היא איכשהו הרבה פחות נוקשה מהתמודדות עם סטים", אמר מאנרס. עם משתנה אקראי, "אני יכול לצבוט אחת מההסתברויות בכמות קטנה, וזה עשוי לתת לי משתנה אקראי טוב יותר."

באמצעות פרספקטיבה הסתברותית זו, גרין, נימוסים וטאו יכלו לעבור מעבודה עם מספר האלמנטים בקבוצה למדידה של המידע הכלול במשתנה אקראי, כמות הנקראת אנטרופיה. אנטרופיה לא הייתה חדשה בקומבינטוריקה הנוספת. למעשה, טאו ניסו להפוך את הרעיון לפופולארי בסוף שנות ה-2000. אבל אף אחד עדיין לא ניסה להשתמש בו בהשערת הפולינום פריימן-רוזה. גרין, גינרס וטאו גילו שזה חזק. אבל הם עדיין לא הצליחו להוכיח את ההשערה.

כשהקבוצה לעסה את התוצאות החדשות שלהם, הם הבינו שהם סוף סוף בנו סביבה שבה הרעיונות הרדומים של גוורס יכולים לפרוח. אם הם מדדו את גודלה של קבוצה באמצעות האנטרופיה שלה, ולא מספר האלמנטים שלה, הפרטים הטכניים עשויים להסתדר הרבה יותר טוב. "בשלב מסוים הבנו שלמעשה הרעיונות הישנים האלה של טים מלפני 20 שנה יצליחו יותר מאלה שניסינו", אמר טאו. "ואז החזרנו את טים ​​לפרויקט. ואז כל החלקים מתאימים זה לזה בצורה מפתיעה".

ובכל זאת, היו הרבה פרטים שצריך להבין לפני שהוכחה התכנסה. "זה היה טיפשי שכולנו היינו עסוקים בצורה מדהימה בדברים אחרים", אמר מנרס. "אתה רוצה לפרסם את התוצאה הנהדרת הזו ולספר לעולם, אבל אתה בעצם עדיין צריך לכתוב את מדדי האמצע שלך." בסופו של דבר, הקבוצה דחפה, וב-9 בנובמבר, הם פרסמו את העיתון שלהם. הם הוכיחו שאם A + A אינו גדול מ k פעמים בגודל של A, לאחר מכן A יכול להיות מכוסה על ידי לא יותר מאשר בערך k¹² משמרות של תת-קבוצה שאינה גדולה מ A. זהו מספר פוטנציאלי עצום של משמרות. אבל זה פולינום, אז הוא לא גדל מהר יותר באופן אקספוננציאלי כמו k נהיה גדול יותר, כפי שהיה קורה אילו k היו במעריך.

כמה ימים לאחר מכן, טאו התחיל ל למסד את ההוכחה. הוא ניהל את פרויקט הפורמליזציה בשיתוף פעולה, תוך שימוש בחבילת בקרת הגרסה GitHub כדי לתאם תרומות מ 25 מתנדבים ברחבי העולם. הם השתמשו בכלי שנקרא תכנית אב פותח על ידי פטריק מאסו, מתמטיקאי באוניברסיטת פריז-סקליי, לארגן את המאמצים לתרגם ממה טאו נקרא "אנגלית מתמטית" לקוד מחשב. Blueprint יכולה, בין היתר, ליצור א תרשים המתאר את השלבים ההגיוניים השונים הכרוכים בהוכחה. ברגע שכל הבועות כוסו במה שטאו כינה "גוון מקסים של ירוק", הצוות הסתיים. הם גילו כמה שגיאות הקלדה קלות מאוד בעיתון - במאמר מקוון הודעה, טאו ציין כי "החלקים המעניינים ביותר מבחינה מתמטית של הפרויקט היו פשוטים יחסית לפורמליזציה, אבל הצעדים הטכניים ה'ברורים' הם שנמשכו הכי הרבה זמן".

מרטון מתה רק שנים ספורות לפני שהוכחה ההשערה המפורסמת שלה, אבל ההוכחה מהדהדת אותה מפעל חיים על אנטרופיה ותורת המידע. "הכל עובד הרבה יותר טוב כשאתה עושה את זה במסגרת האנטרופיה הזו מאשר במסגרת שניסיתי לעשות את זה", אמר גוורס. "לי, זה עדיין נראה קסום משהו."

Quanta עורכת סדרה של סקרים כדי לשרת טוב יותר את הקהל שלנו. קח את שלנו סקר קוראי מתמטיקה ותוכלו לזכות בחינם Quanta סחורה.