חלוקות וההשערה של רמנוג'אן

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

נתחיל מזה שהכותרת הבומבסטית לא שגויה לחלוטין - אכן, עושה רושם שנתקבלה תשובה כלשהי לתעלומה בת מאה שנים לערך. הכוכבת של התעלומה הזו היא מה שנקרא “פונקציית החלוקה”, \( p\left(n\right) \). פונקציית החלוקה מתאימה לכל מספר טבעי \( n \) את מספר הדרכים שבהן ניתן לתאר אותו כסכום של מספרים טבעיים, בלי חשיבות לסדר שבו הם מופיעים. למשל, את 3 אפשר לתאר גם בתור 3 (סכום שמכיל רק איבר אחד - המספר הטבעי 3), וגם בתור \( 1+1+1 \), וגם בתור \( 1+2 \) וגם בתור \( 2+1 \) אבל שתי החלוקות האחרונות הן אותו הדבר עד כדי שינוי הסדר שבו האיברים מופיעים ולכן הם נספרים פעם אחת. לכן \( p\left(3\right)=3 \).

עבור מספרים גדולים יותר חופש הפעולה שלנו גדול יותר ומתקבלות הרבה יותר חלוקות; למשל, עבור \( 5 \) כבר יש לנו 7 חלוקות:

\( 5=1+1+1+1+1=1+1+1+2=1+2+2=2+3=1+1+3=1+4 \)

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

פונקצית החלוקה מגדירה סדרה של מספרים טבעיים, \( p\left(0\right),p\left(1\right),p\left(2\right),\dots \). הסדרה הזו נראית כך:

\( 1,1,2,3,5,7,11,15,22,30,42,56,77,\dots \)

(היי! 42 בפנים!)

מה שמתמטיקאים אוהבים לעשות עם סדרות שכאלו באופן כללי הוא לגלות את החוקיות בהן. סטודנטים לקומבינטוריקה מקבלים לפעמים רושם שגוי לפיו לבעיות קומבינטוריות אמור להיות פתרון שהוא “נוסחה סגורה” - כלומר, נוסחה קצרה ופשוטה ועם פעולות אלמנטריות בלבד שמערבת את \( n \) ומחזירה בדיוק את המספר שאנו מחפשים. הנוסחה \( {n \choose k}=\frac{n!}{k!\left(n-k\right)!} \) שמתארת את מספר האפשרויות לבחור \( k \) מתוך \( n \) אובייקטים ללא חשיבות לסדר היא דוגמה נאה לנוסחה סגורה שכזו. גם \( 2^{n-1} \) היא נוסחה סגורה נאה למספר החלוקות של \( n \) שבהן יש חשיבות לסדר (תרגיל: הוכיחו את הנוסחה הזו!)

למרבה הצער, ל-\( p\left(n\right) \) אין אף נוסחה סגורה פשוטה. זה לא מקרה חריג; זה מקרה נפוץ ביותר בקומבינטוריקה “אמיתית”. המתמטיקאי לסלו לובאס (László Lovász) פותח את ספרו Combinatorial problems and exercises בשורה

There is no rule which says that enumeration problems, even the simplest ones, must have solutions expressible as closed formulas.

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

כמובן, השאלה הבאה היא איך אני יודע שאין לה נוסחה כזו והיא פשוט טרם נמצאה. ובכן, קצת מביך לומר, אבל אני לא יודע את זה. אני אפילו לא בטוח מה ייחשב “נוסחה פשוטה” בעיני הקורא. יש נוסחאות שדי קל לפסול - למשל, אם \( p\left(n\right) \) הייתה פולינום מדרגה נמוכה היה קל למצוא אותו על ידי אינטרפולציה (בהינתן פולינום מדרגה \( d \) ו-\( d+1 \) ערכים שונים שלו אפשר למצוא את הפולינום במדויק). גם נוסחאות נסיגה לינאריות פשוטות אפשר למצוא אם יש לנו מספיק איברים מהסדרה, ויש עוד תעלולים שלא אכנס אליהם כרגע. כך שאם הנוסחה של \( p\left(n\right) \) הייתה ממש פשוטה, כבר היו מוצאים אותה. אבל הוכחה כללית יותר אני לא מסוגל לתת.

כל זה כמובן לא אומר שלא יודעים כלום על \( p\left(n\right) \). התוצאה הראשונה שמוזכרת בכל ספר לימוד הוא הפונקציה היוצרת הנאה של \( p\left(n\right) \): \( \sum_{n=0}^{\infty}p\left(n\right)x^{n}=\prod_{k=1}^{\infty}\left(\frac{1}{1-x^{k}}\right) \). למי שזה לא אומר לו כלום - לא נורא, לא נשתמש בפונקציה היוצרת כאן, היא פה רק כקוריוז לסקרנים (ואתגר: הוכיחו שזו אכן הפונקציה היוצרת!)

אבל הפונקציה היוצרת לא נותנת לנו הערכה של הגודל של \( p\left(n\right) \) עבור \( n \) נתון. הערכה כזו הוכחה לראשונה בידי הארדי ורמנוג’אן בשנת 1918:

\( p\left(n\right)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}} \)

וזו ההזדמנות לספר משהו על הצמד המוזר הזה, הארדי-רמנוג’אן. הארדי היה מתמטיקאי בריטי מפורסם שפעל בתחילת המאה ה-20. הספר שכתב עם Wright עדיין נחשב לאחד מספרי המבוא הטובים ביותר לתורת המספרים הקיימים ואני בהחלט ממליץ עליו לכל קורא של הבלוג. הארדי גם ידוע בזכות הספרון שלו, “A Mathematician’s Apology” (לא, זו לא התנצלות), שהוא אחד מהתיאורים הטובים ביותר שקראתי של “מה עובר בראש של מתמטיקאי” (ובנוסף, מכיל גם את הבעת האושר של הארדי על כך שלתחום העיסוק שלו - תורת המספרים - לא נמצא שום שימוש מעשי והבעת תקווה שכך יהיה לנצח. ארבעים שנה לאחר מכן הפכה תורת המספרים לכלי חשוב בקריפטוגרפיה).

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

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

The limitations of his knowledge were as startling as its profundity. Here was a man who could work out modular equations and theorems... to orders unheard of, whose mastery of continued fractions was... beyond that of any mathematician in the world, who had found for himself the functional equation of the zeta function and the dominant terms of many of the most famous problems in the analytic theory of numbers; and yet he had never heard of a doubly periodic function or of Cauchy's theorem, and had indeed but the vaguest idea of what a function of a complex variable was...

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

רמנוג’אן כתב למתמטיקאים בריטים, וכפי שבדרך כלל קורה בדברים כאלו, רובם פשוט לא הבינו אותו ומה הוא רוצה. הוא הפציץ אותם בנוסחאות מטורפות לחלוטין וללא הוכחות כלל. לבסוף הוא כתב גם להארדי. הארדי בהתחלה חשב שמדובר ברמאות - חלק מהנוסחאות היו מוכרות לו, וחלק נראו הזויות לחלוטין. עם זאת, הוא השתכנע שכנראה יש בהן משהו ופתח בהתכתבות עם רמנוג’אן, ששיאה בבואו של רמנוג’אן לאנגליה ועבודה משותפת עם הארדי במשך כחמש שנים, בהן הוכיחו יחד השניים רבים ממשפטיו של רמנוג’אן. כאשר הארדי נשאל מה הייתה תרומתו הגדולה ביותר למתמטיקה הוא ענה “גילויו של רמנוג’אן”, ואת התרשמותו ממנו ניתן לראות בכך שב”דירוג מתמטיקאים” שהוא המציא פעם הוא נתן לעצמו 25, להילברט (אחד מגדולי המתמטיקאים של תקופתו, ומתמטיקאי שנחשב כבעל ידע בכל תחום אפשרי של המתמטיקה) נתן 80 ולרמנוג’אן נתן 100.

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

טוב, מספיק עם הסקירה ההיסטורית, בואו נדבר על מה שרמנוג’אן עשה. כבר אמרתי שהוא גילה איכשהו את הנוסחה \( p\left(n\right)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{\frac{2n}{3}}} \), אבל לא על זה מדברים בכתבה של Ynet אלא על תגלית אחרת שלו הקשורה לפונקציה הזו (היו לו כמה וכמה) - נוסחאות שניתן לתאר באופן הבא:

\( p\left(5k+4\right)\equiv0\left(\mbox{mod 5}\right) \)

\( p\left(7k+5\right)\equiv0\left(\mbox{mod 7}\right) \)

\( p\left(11k+6\right)\equiv0\left(\mbox{mod 11}\right) \)

מה זה אומר? ובכן, \( 5k+4 \) בא לייצג את סדרת המספרים \( 5,9,14,19,24,\ldots \) שמתקבלת כאשר מציבים מספר טבעי ב-\( k \). דרך אחרת לנסח את זה היא בתור “מספר כלשהו שכאשר מחלקים אותו ב-5 מקבלים שארית 4”. בדומה, \( 7k+5 \) מייצג כל מספר טבעי שהוא שכאשר מחלקים אותו ב-7 מקבלים 5, וכדומה.

ה-\( \equiv0\left(\mbox{mod 5}\right) \) מייצג, במקרה זה, את הטענה “מתחלק ב-5”. למה לכתוב את זה כל כך מסובך? כי לסימון \( a\equiv b\left(\mbox{mod n}\right) \) יש משמעות כללית יותר שאותה רוב המתמטיקאים מכירים, ונוח להשתמש בסימון הזה גם למטרה זו, וגם נראה הרבה משוואות כאלו בהמשך הפוסט. פורמלית, המשמעות של \( a\equiv b\left(\mbox{mod n}\right) \) היא “\( a-b \) מתחלק ב-\( n \)”, או בניסוח שקול - “כאשר מחלקים את \( a \) ב-\( n \) מתקבלת אותה שארית כמו זו שמתקבלת כאשר מחלקים את \( b \) ב-\( n \)”.

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

רמנוג’אן גם הוסיף את ההערה “נראה כי אין תכונות פשוטות דומות עבור אף מודולוס ראשוני פרט לאלו” (מודולוס הוא מה שמופיע אחרי ה-\( \mbox{mod} \) - מה שבודקים את החלוקה בו). ההערה הזו נותרה תעלומה זמן רב - לא ברור כיצד ניתן בדיוק לנסח אותה באופן מתמטי, ואפשר רק לסמוך על האינטואיציה של רמנוג’אן - והכתבה ב-Ynet עוסקת במאמר שבין היתר מציע לה הסבר מסויים.

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

\( p\left(1977147619k+815655\right)\equiv0\left(\mbox{mod 19}\right) \)

ברור כי המשוואה הזו דומה לקודמות שהצגתי, אבל גם ברור שהיא אינה פשוטה כמוה, בגלל שהמודולוס 19 אינו מופיע בתור המקדם של \( k \) באגף שמאל, אלא מספר מסובך יותר.

זה אומר, לצערי, שיש בכתבה ב-Ynet טעות: הטענה שלהם ש-

במילים אחרות, לא קיימת שום סדרת \( p\left(n\right) \)-ים שכל אבריה מתחלקים ב-13, ב-17, ב-19 וכן הלאה. בשנים שחלפו מאז, הוכיחו חוקרים שרמנוג'אן צדק בנוגע לחזקות של 5, 7 ו-11.

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

רמנוג’אן לא הסתפק במשוואות שלעיל, הוא גם שיער משוואה שאפתנית הרבה יותר עבור מספרים שמורכבים מאותם שלושה ראשוניי קסם, 5,7,11. הנוסחה הייתה כדלהלן: אם \( \delta=5^{a}7^{b}11^{c} \), כלומר מספר כלשהו שמורכב משלושת ראשוניי הקסם, וכמו כן \( \lambda \) הוא מספר טבעי המקיים \( 24\lambda\equiv1\left(\mbox{mod }\delta\right) \), אז

\( p\left(\delta k+\lambda\right)\equiv0\left(\mbox{mod }\delta\right) \)

המשוואה הזו מכלילה את קודמותיה; למשל, עבור \( \delta=11 \) (שניתן לכתוב כ-\( 5^{0}7^{0}11^{1} \)) ו-\( \lambda=6 \) אנו מקבלים ש-\( 24\lambda=144\equiv1\left(\mbox{mod }11\right) \) (שכן \( 144-1=143 \) ו-\( 143=11\cdot13 \)), ולכן מקבלים את המשוואה \( p\left(11k+6\right)\equiv0\left(\mbox{mod }6\right) \). המשוואה החדשה הזו של רמנוג’אן אלגנטית ונפלאה ולכן מאוד מצער לגלות שהיא לא נכונה. רמנוג’אן המסכן שיער את השערתו על בסיס בחינת 200 הערכים הראשונים של \( p\left(n\right) \) - כנראה טבלה מקיפה יותר לא הייתה זמינה אז (אילו רק היה רמנוג’אן חי בעידן המחשבים!). שנים לאחר מכן, לאחר שהטבלה הורחבה וכללה 300 ערכים, התגלה כי \( p\left(243\right) \) הוא דוגמה נגדית להשערה של רמנוג’אן - הוא לא התחלק ב-\( 7^{3} \) אף על פי ש-\( 24\cdot243\equiv1\left(7^{3}\right) \). מסתבר שהבעיה היא רק בראשוני הסורר 7, והיא ניתנת לתיקון פשוט יחסית: \( p\left(\delta k+\lambda\right)\equiv0\left(\mbox{mod }\delta^{\prime}\right) \) כאשר \( \delta^{\prime} \) מתקבל מ-\( \delta \) על ידי שינוי החזקה של 7 בתוך \( \delta \) במקרה שבו חזקה זו היא גדולה מ-0: אם \( b \) היא החזקה המקורית, החזקה החדשה תהיה \( b^{\prime}=\left\lfloor b/2\right\rfloor +1 \) (במילים: קחו את \( b \), תחלקו ב-2, תעגלו כלפי מטה ותוסיפו 1 לתוצאה). כבר אמרתי שבמתמטיקה תוצאות “יפות” מושלמות לא תמיד קיימות? אז הנה דוגמה שהפילה אפילו את רמנוג’אן האדיר - מאיפה תיקון מעצבן שכזה חייב לצוץ ולמה דווקא ב-7, אין לי מושג.

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

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

בואו נעבור לתאר את אחת מהתוצאות של המשפט, לה הם קוראים משפט 1.1. בפשטות, הם אומרים שעבור ראשוניים שגדולים מאותם 5,7,11 הקסומים אבל קטנים או שווים ל-31 מתקיימות משוואות מודולריות דומות לאלו של רמנוג’אן, פרט לכך שבאגף ימין של המשוואה אין אפס, אלא מעין “עותק קטן יותר” של אגף שמאל. למה הכוונה? הנה משוואה לדוגמה:

\( p\left(13^{3}n+1007\right)\equiv6\cdot p\left(13n+6\right)\left(\mbox{mod 13}\right) \)

זו משוואה עבור הראשוני 13. היא אומרת שמודולו 13, יש סדרה של ערכים של \( p\left(n\right) \) עם הפרש של \( 13^{3} \), שנראית בדיוק כמו סדרת ערכים מסויימת של \( p\left(n\right) \) עם הפרש של 13, כאשר אותה סדרת ערכים מוכפלת ב-6. אתם מוזמנים לעשות את החישוב, זה עובד.

הטענה הכללית יותר מנוסחת באופן קצת יותר מסורבל ועמוס הנחות, אבל ככה זה - כאמור, אל תצפו שהכל יהיה נוסחאות נוצצות ופשוטות. אצטט אותה מהמאמר: עבור ראשוניים \( 5\le l\le31 \) (למה \( l \) ולא \( p \), שבדרך כלל מסמן ראשוני? ובכן, כי \( p \) מסמן את פונקציית החלוקה ואנחנו לא רוצים להתבלבל) וחזקה \( m\ge1 \) מתקיים שאם \( b_{1}\equiv b_{2}\left(\mbox{mod }2\right) \) עבור טבעיים \( b_{2}>b_{1}\ge2m-1 \) אז עבור מספר \( A \) מסויים שתלוי ב-\( l,b_{1},b_{2},m \) מתקיימת המשוואה

\( p\left(\frac{l^{b_{2}}k+1}{24}\right)\equiv A\cdot p\left(\frac{l^{b_{1}}k+1}{24}\right)\left(\mbox{mod }l^{m}\right) \), לכל \( k \) טבעי שעבורו השבר יוצא מספר שלם (אין משמעות לפונקצית החלוקה על שברים…)

בדוגמה שלעיל \( b_{2}=3 \) ו-\( b_{1}=1 \) ו-\( m=1 \) ו-\( l=13 \), ואז יוצא ש-\( A=6 \). תרגיל למתקדמים: נסו להבין כיצד ה-1007 וה-6 נובעים מהדרישה שלנו להצטמצם למקרים שבהם החלוקה ב-24 אינה מניבה שבר.

כעת אני מקווה שקצת יותר ברורות הפסקאות הבאות של המאמר:

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

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

ההערה של רמנוג’אן על כך שאין נוסחאות פשוטות דומות עבור ראשוניים גדולים מ-11 באה לידי ביטוי במאמר שאותו \( A \) במשפט שלעיל יהיה 0 כאשר הראשוני הוא 5,7 או 11, אבל יהיה שונה מ-0 עבור ראשוניים גדולים יותר. המאמר גם נכנס להסבר עמוק יותר של הסיבה לכך אבל אני לא מבין כלום - וגם את מה שאני מבין, אני לא מבין איך להסביר.

אם כן, נעבור הלאה אל סוף המאמר ב-Ynet, בו אומרים כי

בתוצאה נפרדת שגם היא הוכרזה בינואר, תיארו אונו ושותף אחר שלו את הנוסחה הראשונה שמחשבת את \( p\left(n\right) \) לכל n, מבצע שחמק מתיאורטיקנים של תורת המספרים במשך מאות שנים.

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

\( p\left(n\right)=\frac{1}{24n-1}\cdot\mbox{Tr}\left(n\right) \)

טוב, זה לא אומר כלום, נכון? מהו \( \mbox{Tr}\left(n\right) \)? המאמר מגדיר אותו כ-\( \sum_{Q\in Q_{n}}P\left(\alpha_{Q}\right) \), אבל מי שינסה להבין את זה בלי הרקע המתאים עוד יותר יצא מדעתו - אני לא אנסה לתת הסבר שאני חצי מבין כאן. השורה התחתונה מבחינתנו היא שמדובר על סכום סופי (ותלוי ב-\( n \)) של מספרים אלגבריים - כלומר, מספרים מרוכבים שקיים פולינום במקדמים רציונליים שמאפס אותם. זה שיפור ביחס לנוסחה הטובה ביותר שהייתה ידועה עד היום, שעירבה סכומים אינסופיים; אבל האם זה באמת משפר את יכולת החישוב שלנו ביחס לאלגוריתמים שיש היום (ואינם רעים עד כדי כך)? לא יודע, אבל נראה לי שלא; לא הצלחתי למצוא ניתוח סיבוכיות במאמר. והאם הנוסחה היא “פשוטה”? כנראה לא באופן שחשבתם שהיא תהיה. אני לא אומר זאת כדי להמעיט מגודל ההישג, חלילה; רק כדי למנוע יצירת רושם שגוי לגביו.

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

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

השיא הוא בטוקבק הבא:

המספרים הראשוניים הם הבסיס לרוב אלגוריתמי ההצפנה שמשתמשים בהם היום. למצוא חוקיות למספרים ראשוניים (ז"א בהינתן מספר, לבדוק בצורה יעילה האם הוא ראשוני ולמצוא את הראשוני הקטן ביותר שגדול ממנו, והראשוני הגדול ביותר שקטן ממנו) - זו אחת מהבעיות המרכזיות במתמטיקה ובמדעי המחשב היום. חוקיות של חלוקות זו בעיה רחבה יותר שבאמצעותה אפשר להוכיח ראשוניות - כי לפי הגדרה, מספר שלא קיימת לו חלוקה בה כל המחלקים שווים ושונים מ1 הוא ראשוני. נוסחה מפורשת למציאה של מספר החלוקות של המספר N+1 בהינתן מספר החלוקות של N, או בהינתן המספר הראשוני P למצוא את הראשוני הראשון Q כך שQ גדול מP, וכו' - ישפרו קודם כל את סיבוכיות זמן הריצה של אלגוריתמי קידוד והצפנה, ו"על הדרך" גם יוכיחו שיש בעיות NP-קשות שיש להן אלגוריתם פתרון פולינומי, וזה כבר פתרון ל "שאלת מיליון הדולר" P=NP שיהיה מפתח לכמות בלתי נתפסת של שינויים בתחומי המתמטיקה, מדעי המחשב והמדע באופן כללי.

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

אז כמה הבהרות פשוטות:

1. קיים אלגוריתם יעיל מאוד (מילר-רבין) לבדיקת ראשוניות, גם של ראשוניים בני מאות ספרות. אז בדיקה האם מספר הוא ראשוני - בעיה זו פתורה. בהינתן מספר, למצוא את הראשוני הקטן ביותר שגדול ממנו - גם זו לא ממש בעיה (פשוט בודקים אחד אחד את הבאים אחריו). אלו לא מהבעיות המרכזיות במתמטיקה ובמדעי המחשב היום. וכן, מילר-רבין הסתברותי, ויש גם אלגוריתמים לא הסתברותיים, פרקטיים פחות אבל לא יותר מדי פחות. מה שהיא כן בעיה פתוחה חשובה היא בעיית הפירוק לגורמים של מספר; זה ממש לא אותו דבר.
2. אמנם, מספר שלא קיימת לו חלוקה בה כל המחלקים שווים ושונים מ-1 הוא ראשוני, אבל אני לא מכיר אלגוריתמים לבדיקת ראשוניות/פירוק לגורמים שמסתמכים על חלוקות.
3. פתרון בעיית הראשוניות לא יוכיח ש-P=NP (למעשה, כאמור, בעיית הראשוניות כבר נפתרה). אפילו פירוק יעיל לגורמים לא יוכיח ש-P=NP.

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