השערת הרץ הבודד

בשנת 1998 התפרסם מאמר נישתי למדי בתורת הגרפים. באחת ההוכחות השתמש המאמר בהשערה מתורה המספרים מ-1967. אבל אם ב-1967 נוסחה ההשערה במונחים מתמטיים יבשים ("איך להעריך מספר לא רציונלי בעזרת סכום של שברים") – הכותבים של 1998 מצאו לה ניסוח ציורי: ניסוח של תחרות ריצה.

התוצאה היא השערת הרץ הבודד:

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

השערת הרץ הבודד אומרת ככה: אם הרצים ירוצו מספיק סיבובים – יהיה לכל רץ רגע בו הוא רחוק מכל שאר הרצים האחרים. כמה רחוק? תלוי במספר הרצים. אם זה שני רצים: 500 מטר. שלושה רצים? 333 מטר. ארבעה רצים – 250 מטר. חמישה רצים?! 200 מטר. ובאמירה כללית: אם יש N רצים, כל רץ יהיה ברגע מסוים במרחק 1000 חלקי N משאר הרצים."

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

[הדמייה של Rocini לשישה רצים, רשיון CC]

המקרה של שני רצים הוא טריוויאלי. זה שרץ מהר יותר צובר עוד ועוד מרחק מהרץ האיטי עד שנוצר ביניהם פער של 500 מטר.

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

המקרה של ארבעה רצים הוכח ב-1972. חמישה רצים, ב-1984. המקרים של שישה ושבעה רצים הוכחו רק ב-2001 ו-2008 בהתאמה. כל הוכחה השתמשה בשיטות אחרות לגמרי שהתאימו למקרה עצמו. מה שאומר שאי אפשר היה למצוא הוכחה כללית לכל מספר של רצים.

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

כלומר, לא קידמה עד לפני כמה חודשים.

[(Estafiers Romains (1670, נחלת הכלל. חתכתי וצבעתי את המקור]

איך ניגשים לפתור בעיה כמו השערת הרץ הבודד?

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

צעד שני: בודקים רק למהירויות נמוכות. ב-2015 הוכיח טרנס טאו שאם השערת הרץ הבודד נכונה למהירויות נמוכות (לדוגמא –  למהירויות של פחות מ-100 קמ"ש), הן נכונות לכל מהירות. עד כמה נמוכות המהירויות? זה תלוי במספר הרצים. אבל בכל מקרה זה אומר שמספיק לבדוק מספר סופי של קומבינציות. שזה נשמע טוב מאשר לבדוק אינסוף אפשרויות.

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

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

הוכחה לתשעה ועשרה רצים. סטודנט לתואר ראשון מאוקספורד, פול טראקולטונגצ'אי (Paul Trakulthongchai) ראה את המאמר של רוזנפלד ואמר לעצמו, "הממ, אני יכול לעשות יותר טוב!". במרץ של אדם צעיר הוא הצליח תוך כמה שבועות לשפר את החישובים ולהוכיח למספר של תשעה ועשרה רצים. רוזנפלד עצמו עשה את אותן ההוכחות כמה ימים מאוחר יותר – והתאכזב לראות שמישהו הקדים אותו.

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

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

השערה הרץ הבודד הייתה אלמונית למדי בפעם הראשונה שנתקלתי בה, לפני +15 שנים בערך – אבל הולכת והופכת להשערה מיתולוגית עם הזמן. זה שילוב של שני גורמים. האחד הוא שההשערה לא פתורה כבר הרבה זמן, והשני הוא שההשערה כל כך קלה להבנה. איך זה שהאנושות, עם כל כוחה, התקדמותה וה-AI שלה, לא יכולה להוכיח משהו פשוט כל כך?

לפעמים נדמה לי שאני הרבה יותר נהנה מהתעלומות הקיימות האלה מאשר מאלו שכבר נפתרו.

לקריאה נוספת: כתבה ב-Quanta על ההתקדמות בפתרון ההשערה.