מתמטיקאים מוצאים מבנה נסתר בסוג נפוץ של חלל

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

העיתון היה על ידי פיטר קייבש של אוניברסיטת אוקספורד. נושאו: אובייקטים מתמטיים הנקראים עיצובים.

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

עד מהרה, מתמטיקאים שאלו גרסה כללית יותר לשאלתו של קירקמן: אם יש לך n אלמנטים בסט (15 תלמידות בית הספר שלנו), אתה תמיד יכול למיין אותם לקבוצות בגודל k (שורות של שלוש) כך שכל סט קטן יותר של גודל t (כל זוג בנות) מופיע בדיוק באחת מהקבוצות האלה?

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

אבל הם גם מתקשים מאוד לבנות אותם k ו t לגדול יותר. למעשה, מתמטיקאים עדיין לא מצאו עיצוב עם ערך של t גדול מ-5. ולכן זה הגיע בהפתעה גדולה כאשר, בשנת 2014, Keevash הראה שגם אם אתה לא יודע איך לבנות עיצובים כאלה, הם תמיד קיימים, כל עוד ש n הוא גדול מספיק ועומד בכמה תנאים פשוטים.

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

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

"מעבר למה שמעבר לדמיון שלנו"

במשך עשרות שנים, מתמטיקאים תרגמו בעיות לגבי קבוצות ותת-קבוצות - כמו שאלת העיצוב - לבעיות לגבי מה שנקרא מרחבים וקטוריים ותת-מרחבים.

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

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

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

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

בעיית העיצוב של תת החלל עוסקת n-מרחבים וקטוריים ממדיים ותתי המרחבים שלהם. במרחבים וקטוריים כאלה - שוב, כל עוד n גדול מספיק ועומד בתנאים פשוטים - האם אתה יכול למצוא אוסף של k-תת-מרחבים ממדיים כאלה שכל t-תת-מרחב ממדי כלול בדיוק באחד מהם? אובייקט כזה נקרא (n, k, t) עיצוב תת חלל. זה דומה מבחינה רעיונית לבעיית העיצובים הרגילים, אבל זה כולל סידורים מוגבלים הרבה יותר.

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

ב-50 השנים שחלפו מאז החלו מתמטיקאים לחשוב על הבעיה הזו, הם גילו רק דוגמה אחת לא טריוויאלית (למרות שהם יודעים שקיימים סוגים כלליים יותר של עיצובי תת-מרחב): במרחב וקטורי 13-ממדי, אפשר לכסות תת-מרחבים דו-ממדיים עם תלת-ממדיים בדיוק פעם אחת. התוצאה דרשה הוכחה מסיבית מבוססת מחשב, כי אפילו עבור ערכים קטנים כל כך של n, k ו t, בסופו של דבר אתה עובד עם מיליוני תת-מרחבים. המורכבות של מערכות כאלה "איננה מעבר לדמיון שלנו; זה מעבר למה שמעבר לדמיון שלנו", אמר טובי עציון מהטכניון בישראל, שעזר לגלות את הדוגמה.

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

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

ספוג לשגיאות

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

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

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

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

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

שם נכנסה התבנית לתמונה. הם שברו את התבנית לחתיכות ושילבו חלק מתת-החללים שלה עם תת-החללים ב-hodgepodge - והכניסו אותם היטב לסידורים גדולים יותר שאפשר לכסות אותם כראוי. הם היו צריכים לעקוב בקפידה איך הם עושים זאת כדי לוודא שכל מהלך שהם עשו יוביל למבנה גלובלי יותר. אבל בסופו של דבר, הם הצליחו להשתמש בתבנית כדי למלא את כל החורים שהנשנוש של Rödl לא הצליח לכסות. כמו ספוג, התבנית ספגה את כל השגיאות בעיצוב. (כתוצאה מכך, הטכניקה הכללית הזו נקראת "ספיגה".) "זה כמעט כאילו אתה מנסה לשים שטיח בפינה," אמר סווני. "הוא צץ במקום אחר, ואתה דוחף אותו, ואיכשהו, אחרי 20 דחיפות, השטיח פשוט שטוח."

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

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

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

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