לפני 80 שנה העלה המתמטיקאי פול ארדש השערה שלא זכתה להוכחה או להפרכה. עד שהגיע ה־AI: מודל בינה מלאכותית יוצרת של חברת OpenAI שהתבקש להתמודד עם הטענה, הצליח להפריך אותה!

פרסומת

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

אפשר לנסח את השאלה כך: נניח שיש לנו יד חופשית להציב N נקודות במישור, כאשר המטרה שלנו היא לייצר כמה שיותר זוגות של נקודות שהמרחק ביניהן שווה ל־1. מה המספר המירבי של זוגות כאלה שנצליח לייצר? ואיך הכמות הזאת מתנהגת כאשר N הולך וגדל?

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

איור: שלוש נקודות על ישר יוצרות שני זוגות (למעלה), ושלושת קודקודיו של משולש שווה צלעות יוצרים שלושה זוגות (למטה).

אם נוסיף עוד נקודה על הקו (כך שתהיינה בסך הכול 4 נקודות), נקבל 3 זוגות של נקודות עם מרחק 1 ביניהן. וכך הלאה, בכל הוספת נקודה על הקו, נקבל זוג נוסף למלאי. באופן כללי, אם יש לנו N נקודות מסודרות בצורה זו על קו ישר:
* — * — * — * — ….. — * — *
המבנה הזה יוצר N-1 זוגות של נקודות שהמרחק ביניהן שווה ל־1.

נעיר כי המבנה בדוגמה שלנו הוא לא בהכרח זה שמשיג הכי הרבה זוגות: למשל עבור N=3, אם ניקח משולש שווה צלעות בעל צלע שווה ל־1, שיפרנו את כמות הזוגות ל־3. האם תוכלו לצייר מבנים בעלי זוגות רבים יותר עבור 4 או 5 נקודות?

במתמטיקה מתעניינים בהתנהגות הכללית: איך משתנה הגודל המדובר כאשר המספר N הולך וגדל? האם אותו גודל (כמות הזוגות המקסימלית במקרה שלנו) גדל באותו קצב כמו N? אולי דווקא בקצב ריבועי, כלומר בקירוב כמו N בריבוע? או אולי בקצב מעריכי (למשל כמו 2 בחזקת N)? ואולי הוא דווקא הולך ודועך כמו 1 חלקי N?

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

נדגיש גם שאכפת לנו כאן מסדר הגודל: מבחינתנו אם יש N זוגות או N-1 זוגות או 2N זוגות, זה היינו הך, כי בשני המקרים מדובר בקצב גידול מסדר גודל של N בחזקת 1.

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

וזוהי בדיוק ההשערה שהופרכה כעת בידי מודל בינה מלאכותית יוצרת (Generative AI), להפתעתם של מתמטיקאים רבים [4,3]: המודל יצר הוכחה שמראה שאפשר לייצר מבנים שבהם הגידול הוא N בחזקת 1+קבוע קטן (התוספת ל־1 היא מספר קבוע ולא גודל שדועך ל־0). ההוכחה נבדקה על ידי מתמטיקאים מובילים בתחום, שאף כתבו מאמר שמסביר את הנושא [2], ומרחיב ומפרט לגבי תוצאות מתמטיות קודמות (אנושיות!) שהמודל נשען עליהן. יש לציין שהמודל לא סיפק טענה לגבי אותו קבוע קטן שאפשר להוסיף ל־1, אך מאז הפרסום, מתמטיקאי בשם וויל סאווין התבסס על החידוש וסיפק הוכחה עם קבוע ספציפי במאמר שטרם עבר ביקורת עמיתים [5] (0.014114, אם התעניינתם). כלומר, המכונה שיפרה את ההבנה של בעיה מתמטית ידועה, ומתמטיקאים אנושיים מייד לקחו את השיפור הזה צעד נוסף קדימה.

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

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

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

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

עריכה: שיר רוזנבלום־מן

מקורות וקריאה נוספת:

1. המאמר המקורי של ארדש, On set of distances of n points, שבו הוא מציג את השאלה ומראה חסמים על קצב הגידול
2. מאמר של מתמטיקאים מובילים בתחום שמוודא את ההוכחה של המודל ומרחיב בנושא: REMARKS ON THE DISPROOF OF THE UNIT DISTANCE CONJECTURE
3. פרסום של Open AI לגבי פריצת הדרך של המודל שלהם 
4. המאמר ("מאמר"?) של המודל של Open AI שבו מוצגת ההוכחה: Planar Point Sets with Many Unit Distances 
5. מאמר טרום־פרסום של וויל סאווין המספק הוכחה עם קבוע ספציפי
6. שיחה עם המתמטיקאי טרנס טאו לגבי השימוש ב־AI במתמטיקה
7. לקריאה נוספת: פוסט בבלוג של גיל קלעי בנושא, כולל דיון והפניות נוספות