מודל של OpenAI הפריך השערה מרכזית בגאומטריה בדידה

במשך כמעט 80 שנה חקרו מתמטיקאים שאלה שנראית פשוטה לכאורה: אם מציבים $n$ נקודות במישור, כמה זוגות של נקודות יכולים להיות במרחק של $1$ בדיוק זה מזה?

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

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

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

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

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

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

נסמן ב-$u(n)$ את המספר המרבי האפשרי של זוגות במרחק יחידה מתוך $n$ נקודות במישור. קל לבנות דוגמאות המשיגות קצב גידול ליניארי: הצבת $n$ נקודות על ישר נותנת $n-1$ זוגות, ואילו סריג ריבועי נותן כ-$2n$ זוגות. הבנייה הטובה ביותר שהייתה ידועה עד כה, המבוססת על סריג ריבועי שקנה המידה שלו שונה, מניבה אף יותר: $n^{1 + C / \log \log(n)}$, עבור קבוע $C$. מכיוון ש-$\log \log(n)$ שואף לאינסוף עם $n$, האיבר הנוסף במעריך שואף ל-$0$. כלומר, הבניות האלה משיגות קצב גידול מהיר רק במעט מגידול ליניארי. במשך עשרות שנים רווחה האמונה שזהו למעשה הקצב הטוב ביותר האפשרי, וששום בנייה לא תוכל לשפר במידה ניכרת את התוצאה של הסריג הריבועי. בניסוח מתמטי, ארדש שיער שקיים חסם עליון של $n^{1+o(1)}$, כאשר התוספת $o(1)$ מציינת איבר השואף ל-$0$ עם $n$.

התוצאה החדשה שלנו מפריכה את ההשערה הזאת. ליתר דיוק, עבור אינסוף ערכים של $n$, ההוכחה בונה סידורים של $n$ נקודות עם לפחות $n^{1+\delta}$ זוגות במרחק יחידה, עבור מעריך קבוע כלשהו $\delta > 0$. (ההוכחה המקורית של הבינה המלאכותית אינה נותנת ערך מפורש ל-$\delta$, אך שיפור שעתיד להתפרסם מאת ויל סאווין, פרופסור למתמטיקה בפרינסטון, הראה שאפשר לבחור $\delta=0.014$.)

ההיסטוריה של הבעיה עוזרת להבין מדוע התוצאה מפתיעה. החסם התחתון הטוב ביותר שהיה ידוע נותר כמעט ללא שינוי מאז הבנייה המקורית של ארדש ב-1946. החסם העליון הטוב ביותר, $O(n^{4/3})$, מקורו בעבודה של ספנסר, סמרדי וטרוטר מ-1984. למרות שיפורים מאוחרים יותר ומחקרים מבניים קשורים של סקיי, כץ וסילייר, פך, רז וסולימושי ואחרים, החסם העליון נותר כמעט ללא שינוי. כעדות התומכת בהשערה, מטושק ואלון–בוצ'יץ'–זאוארמן חקרו את הבעיה עבור מרחקים לא-אוקלידיים במישור, והוכיחו ש״רוב״ המרחקים הלא-אוקלידיים האלה מקיימים את ההשערה במובן מסוים.

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

בקווים כלליים, ההוכחה מתחילה ברעיון גאומטרי מוכר ומפתחת אותו בכיוון לא צפוי.

אפשר להבין את החסם התחתון המקורי של ארדש באמצעות השלמים הגאוסיים: מספרים מהצורה $a+bi$, כאשר $a$ ו-$b$ הם מספרים שלמים ו-$i$ הוא השורש הריבועי של $-1$. השלמים הגאוסיים מרחיבים את המספרים השלמים הרגילים, וכמוהם הם מקיימים תכונות כגון פירוק יחיד לגורמים ראשוניים. הרחבות כאלה של המספרים השלמים הרגילים או של המספרים הרציונליים נקראות שדות מספרים אלגבריים. הטיעון החדש מחליף את השלמים הגאוסיים בהכללות מורכבות יותר מתורת המספרים האלגברית, בעלות סימטריות עשירות יותר, שיכולות ליצור הרבה יותר הפרשים באורך יחידה.

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

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

כפי שכותב תומס בלום בהערות הנלוות:

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

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

בלום מצביע גם על אפשרות רחבה יותר:

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

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

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

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

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

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