השערת 3000 הדולר של ארדש

1. המשער הגדול מכולם

המשער הגדול מכולם, והמפורסם מכולם, היה פול ארדש \({(Paul ~~Erdos)}\). הוא שיער בוודאי אלפי השערות, שחלקן זכו לפרסום רב. לפתור השערה של ארדש נחשב לכבוד גדול בין המתמטיקאים. הייתה לו אינטואיציה מופלאה – לא תמיד היה ברור בזמן ניסוח ההשערה מדוע היא חשובה. אבל אם הצהיר על ההשערה שהיא חשובה, בדרך כלל היא התבררה בסופו של דבר ככזו.

כדי לדרג את השערותיו קבע על רוב ההשערות שלו פרסים כספיים. להשערות קלות יחסית הקציב פרס של \({10}\) דולר, ולהשערות שחשב שהן קלות באמת (תרגיל למחשבה ליום או ליומיים) הקציב פרסים בפורינטים, המטבע ההונגרי.

השערה בת פרס של \({100}\) דולר נחשבה כבר לקשה. השערות בעלות חשיבות מיוחדת זכו לפרס של \({1000}\) דולר. ארדש לא טעה אף פעם – לא קרה שהשערה בת \({\$1000}\) התבררה כקלה.

ההשערה היקרה ביותר של ארדש שנפתרה הייתה בעלת פרס של \({\$10,000}\). היא הייתה שהמספרים הראשוניים מתרווחים לפעמים – שלכל מספר קבוע \({C}\) המרחק בין המספר הראשוני ה-\({n}\) לבין המספר הראשוני ה-\({n+1}\) הוא אינסוף פעמים גדול מ)בערך – הביטוי המדויק מסובך( \({C \log n}\). חשבו בעצמכם מדוע אין זה משנה כאן על פי איזה בסיס מחשבים את הלוגריתם. ההשערה הזאת נפתרה ב-\({2014}\) על ידי גרין, פורד, קוניאגין וטאו, ובאופן בלתי תלוי על ידי מיינרד.

ההשערה היקרה ביותר מאז ומעולם היא בעלת פרס של \({\$25000}\).

הוכיחו שיש רק מספר סופי של מספרים ראשוניים \({p}\) המקיימים את התנאי הבא: \({p}\) קטן מן הממוצע של המספר הראשוני הקודם לו והמספר הראשוני הבא אחריו.

זוהי השערה קצת מוזרה, כי על הפרכה שלה (כלומר הוכחה שיש אינסוף מספרים ראשוניים המקיימים את התנאי הזה) הפרס הוא רק \({\$100}\), שפירושו שכנראה ארדש שיער שאכן יש אינסוף מספרים כאלה, כך שמאוד ייתכן שהפרס הזה לא יינתן.

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

2. סדרות חשבוניות ארוכות בתוך קבוצות של מספרים

האם תוכלו למצוא סדרה חשבונית \({a,a+b,a+2b, \ldots ,a+kb}\) בתוך סדרת המספרים \({1,2,4,8,16,\ldots}\) (החזקות של \(2\))? בוודאי – למשל הסדרה בת שני האיברים \({4,32}\) היא סדרה חשבונית. לא ממש חוכמה. אבל האם תצליחו למצוא בסדרה תת סדרה חשבונית עם יותר משני איברים? אשאיר לכם כתרגיל שלא. תת הסדרה החשבונית הארוכה ביותר היא מסדר 2. הסיבה היא שהסדרה דלילה מדי. האיברים לא מספיק צפופים.

מה קורה כשהסדרה צפופה יותר? זו הייתה אחת משאלותיו של ארדש, שנשארה פתוחה במשך זמן רב. איך מודדים צפיפות? זה פשוט: מגדירים גודל שנקרא לו \({d(n)}\) (ה-\({d}\) הוא כאות הראשונה של \({density}\), צפיפות), שהוא מספר האיברים בסדרה הקטנים מ-\({n}\), מחולק ב-\({n}\).

ההשערה של ארדש וחברו טורן \({(Turan)}\) מ-\({1936}\) הייתה שאם קיים מספר חיובי \({c}\) שלאינסוף ערכי \({n}\) מתקיים \({d(n)>c}\) אז יש בסדרה תת סדרות חשבוניות ארוכות כרצוננו: יש תת סדרה חשבונית בעלת \({3}\) איברים, יש תת סדרה חשבונית בעלת \({3}\) איברים, וכו’. למשל, המספרים האיזוגיים מקיימים את התנאי המדובר, עם \({c=\frac{1}{2}}\). ואכן, במספרים האיזוגיים תוכלו למצוא תת סדרות חשבוניות ארוכות כרצונכם. למעשה, זוהי סדרה חשבונית בעצמה.

ב-\({1953}\) הוכיח רוט שבסדרה כזו יש תת סדרה חשבונית מאורך \({3}\). את ההשערה כולה הוכיח סמרדי \({(Szemeredi)}\) ב-\({1975}\). ב-\({1977}\) נתן הילל פירסטנברג הוכחה שמתשמשת בכלים לא אלמנטריים, מתחום שנקרא “תורה ארגודית”. זה היה פתח להתקדמויות מרחיקות לכת.

3. הכללה

האם נחוץ באמת ש-\({d(n)}\) יהיה גדול ממספר קבוע אינסוף פעמים? האם לא מספיק תנאי צפיפות חלש יותר? את השאלה הזאת שאל ארדש את עצמו ואת העולם. התנאי שהציע הוא שסכום ההופכיים של איברי הסדרה הוא אינסופי – מה שאומר שיש “הרבה” מספרים בסדרה. הוא הציע את ההשערה הבאה, שלה הציב כפרס \({3000}\) דולר: אם \({a_1,a_2, \ldots,}\) היא סדרה המקיימת \({\sum_{i <\infty}\frac{1}{a_i}=\infty}\) אז יש בסדרה סדרות חשבוניות ארוכות כרצוננו.

אילו סדרות מקיימות את התנאי הזה? למשל, סדרת הריבועים אינה מקיימת אותו. קל להוכיח (קחו זאת לעצמכם כתרגיל לחשיבה) ש-\({\sum_{i<\infty}\frac{1}{i^2}}\) כלומר \({\frac{1}{1}+\frac{1}{4}+\frac{1}{9}+\ldots}\) הוא סופי. אוילר אפילו הצליח לחשב את הסכום הזה, ולהראות שהוא שווה ל-\({\frac{\pi^2}{6}}\) (מפתיע, לא?).

יש סדרת מספרים חשובה שסכום ההופכיים שלה הוא אינסופי: סדרת המספרים הראשוניים.

\(\displaystyle \sum_{i<\infty}\frac{1}{p_i}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\ldots=\infty\)

נסו להוכיח זאת. אם לא תצליחו – כתבו לנו, ונפרסם את הפתרון באחד הגליונות הקרובים. על כל פנים, אם השערתו של ארדש נכונה כי אז אפשר למצוא סדרות חשבוניות ארוכות כרצונכם של מספרים ראשוניים. קל למצוא סדרה חשבונית באורך \({3}\) שכל איבריה ראשוניים – \({3,7,11}\). האם אתם יכולים למצוא סדרה חשבונית כזו באורך \({4}\)? לגמרי לא פשוט.

ההשערה שבמספרים הראשוניים יש סדרות חשבוניות ארוכות כרצוננו הייתה פתוחה כמאתיים שנים. היא נפתרה לבסוף על ידי גרין וטאו (\({Green, ~Tao}\)) ב-\({2004}\). ההשערה הכללית יותר של ארדש עדיין פתוחה לרווחה. אין יודעים אפילו שבתנאי של ארדש יש בהכרח תת סדרה חשבונית באורך \({3}\).

2 תגובות על השערת 3000 הדולר של ארדש

  • מאת דני‏:

    בהתחלה לא הבנתי את הניסוח בכתבה של ההשערה של ארדש שנפתרה ב-2014, אז למקרה שעוד מישהו מעוניין, הנה ניסוח נוסף:
    נסמן g_n=p_{n+1}-p_n (כלומר g_n הוא ההפרש בין המספר הראשוני ה-n+1 לבין המספר הראשוני ה-n).
    ההשערה (לשעבר) היא שלכל קבוע C, מתקיים g_n>Clogn (הביטוי המדויק מסובך) עבור אינסוף ערכים של n.

    השערה נוספת מאוד מפורסמת לגבי g_n היא ש-g_n=2 עבור אינסוף ערכים של n (כלומר לא משנה כמה רחוק נלך על ציר המספרים, תמיד נוכל למצוא זוג ראשוניים עוקבים שההפרש ביניהם הוא בדיוק 2).
    לאחרונה (מאז 2013 לערך) חלה התקדמות עצומה עם ההשערה הזאת, שנקראת השערת הראשוניים התאומים:
    בהתחלה הוכיח מתמטיקאי בשם Yitang Zhang (אז הוא היה די אלמוני) ש-g_n=70,000,000 עבור אינסוף ערכים של n (כלומר תמיד נוכל למצוא זוג ראשוניים עוקבים שההפרש ביניהם הוא בדיוק 70 מיליון).
    לפני Zhang בכלל לא ידעו להוכיח תוצאה דומה עבור אף מספר קבוע, ולכן התוצאה של 70,000,000 היא מדהימה.
    בהמשך שילבו כוחות מתמטיקאים מכל העולם ושיפרו את הקבוע מ-70,000,000 ל-246, וכרגע זה הקבוע הכי טוב שהצליחו להוכיח עבורו.

    אגב, אם מישהו במקרה מכיר את התוצאות, אני רק רוצה לוודא שלא בלבלתי בתגובה שלי:
    מה שהוכח זה ש-g_n=246 עבור אינסוף ערכים של n, ולא g_n<=246 עבור אינסוף ערכים של n. האם זה מדויק?
    (וכנ"ל עם 70,000,000 במקום 246.)

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

  • מאת אייל‏:

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