האם רוב הראשוניים הם קטנים?

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

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

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

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

אבל אם אין מושג אבסולוטי של "קטן", איך עדיין אפשר לדבר על ראשוניים קטנים? ובכן, בקלות, ותוך שימוש בטכניקות סטנדרטיות שצצות בניתוח ההתנהגות של ראשוניים. במתמטיקה נהוג להגדיר את הפונקציה \(\pi\left(n\right)\) שעבור כל מספר טבעי \(n\) מחזירה את מספר הראשוניים בקטע \(\left[1,n\right]\) ואז לנתח את ההתנהגות שלה; אחת התוצאות הגדולות של המתמטיקה של המאה ה-19 היא משפט המספרים הראשוניים שאומר בערך ש-\(\pi\left(n\right)\sim\frac{n}{\ln n}\) . כלומר, במקום לדבר על כל אינסוף הראשוניים בבת אחת, אנחנו מגבילים את עצמנו לכמות הסופית הראשוניים בקטע סופי כלשהו ורואים איזו תובנה כללית אפשר לתת על המספר הסופי הזה.

עכשיו, אם ניקח \(n\) כלשהו בתור אנדרה הענק, מה השוורצנגרים שלנו? מה המספרים שנחשבים "קטנים" ביחס אל \(n\) ? הגובה של שוורצנגר היה בערך 84% מהגובה של אנדרה הענק. אז אם נחשוב על כל המספרים שהם קטנים מ-\(\frac{84}{100}n\) בתור "קטנים" כמה ראשוניים יש? אם נספור בפועל עבור \(n=10,000\) נראה שיש 1,051 ראשוניים קטנים ו-178 לא קטנים - רוב מוחץ של קטנים! בעזרת משפט המספרים הראשוניים וכל מני מניפולציות טכניות שאחסוך מאיתנו אפשר לראות שזה לא מקרי ושבאופן כללי, לכל \(n\) , נקבל שרוב הראשוניים בקטע \(\left[1,n\right]\) הם קטנים ביחס ל-\(n\) תחת ההגדרה הזו. אבל זה עבור \(kn\) כאשר \(k=\frac{84}{100}\) . מה עם ערכים אחרים של \(k\) ? זה עובד גם עבורם עד שאנחנו מגיעים אל סביבות \(k=\frac{1}{2}\) . עבור חצי זה עדיין עובד, אבל לערכים קטנים קצת יותר זה כבר נשבר ואנחנו כבר לא מקבלים שכל הראשוניים בקטע הם קטנים ביחס אל \(n\) . זה לא מדויק עבור \(n\) , כי ראשוניים לא באמת מתפזרים בצורה אקראית - יש הטייה קלה לטובת ראשוניים קטנים יותר, וזה בעצם מה שאנחנו רואים כאן.

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

הנה דרך שונה לגמרי להסתכל על זה - מה האופן שבו אנחנו משווים מספרים? כשאנחנו כותבים \(a\le b\) , למה אנחנו מתכוונים, והאם אפשר אחרת?

הנה דרך אחת להגדיר את זה עבור מספרים טבעיים: אם \(a,b\) הם מספרים טבעיים אז \(a\le b\) אם קיים מספר טבעי \(d\) כך ש-\(a+d=b\) . זו הגדרה טובה שמתאימה לאינטואיציה היומיומית שלנו של "\(a\le b\) אומר שאפשר להתחיל מ-\(a\) ולהתקדם כמה צעדים עד שמגיעים אל \(b\) " . עם ההגדרה הזו, היחס \(\le\) מקיים כמה תכונות נחמדות: 1. לכל \(a\) מתקיים \(a\le a\) ("רפלקסיביות")

1. אם \(a\le b\) וגם \(b\le a\) אז \(a=b\) ("אנטי-סימטריות").

2. אם \(a\le b\) וגם \(b\le c\) אז \(a\le c\) ("טרנזיטיביות")

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

אם \(a,b\) הם מספרים טבעיים אז \(a\le b\) אם קיים מספר טבעי \(d\) כך ש-\(a\cdot d=b\) .

כלומר, כל מה שעשינו היה להחליף את פעולת החיבור בפעולת כפל. במבט ראשון זה נראה מאוד הגיוני - למשל, אם יש לנו את \(a=3\) ואנחנו כופלים אותו ב-\(d=5\) ומקבלים \(b=15\) , זה בהחלט תואם את הציפיות שלנו ש-\(15\) יהיה גדול מ-3. אפשר גם להוכיח שכל שלוש התכונות למעלה מתקיימות (תנסו!). רק מה, היחס הזה מתנהג מוזר עם האינטואיציה שלנו.

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

הנה משהו יותר מוזר: אם ניקח מספר \(a\) כלשהו ונכפול אותו ב-0, נקבל \(0\) , אז \(a\le0\) לכל \(a\) . זה בהחלט לא מה שהאינטואיציה שלנו מצפה לו - שאפס יהיה האיבר "הכי גדול" - זה בזמן שביחס הסדר הרגיל אפס הוא הכי קטן ואין בכלל דבר כזה, "הכי גדול".

מי המספר הכי קטן ביחס הסדר החדש? ובכן, 1, כי לכל \(a\) , אם נכפול את \(1\) ב-\(a\) נקבל \(a\) . אבל חוץ מ-1 מי הכי קטן? ובכן, כל מספר ראשוני. כי אם \(p\) ראשוני ואם \(a\le p\) זה אומר שקיים \(d\) כך ש-\(ad=p\) . אבל מכיוון ש-\(p\) ראשוני, \(p=ad\) פירושו ש-\(a=1\) או ש-\(d=1\) (ואם \(d=1\) אז \(a=p\) ) - כלומר, כל הראשוניים הם "קטנים"

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

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

ראשית, למה "כן"? כי בואו ונסתכל על השימוש הפרקטי המפורסם של מספרים ראשוניים בימינו - הצפנה. הזכרתי בבלוג בעבר את שיטת ההצפנה RSA, שמשמשת את האנושות בנאמנות כבר עשורים וכל עוד אין לנו מחשב קוונטי עם תיקון שגיאות משמעותי תישאר איתנו. אני לא אכנס לעומק הפרטים הטכניים של RSA (אבל חלק ממה שיפה פה היא שהפרטים הללו די פשוטים; אפשר להבין מה הולך שם גם בלי ידע עמוק במתמטיקה) אבל חלק מהותי מהשיטה דורש, כשבונים את ה" מפתח" שאיתו אפשר לתקשר באופן מאובטח עם אחרים, לייצר שני מספרים ראשוניים \(p,q\) . את שני המספרים הללו כופלים לקבלת \(N=pq\) , ואת המכפלה \(N\) מפרסמים לכל העולם, והם משתמשים ב-\(N\) הזו כדי להצפין דברים ולשלוח אלינו. אנחנו מפענחים את הדברים הללו עם מידע סודי מסוים שיש לנו, והרעיון הוא שאת המידע הסודי הזה אפשר לחשב מתוך \(p,q\) בזמן שבונים את מערכת ההצפנה, אבל אי אפשר לחשב מתוך \(N\) בלי לעשות משהו ששקול לפירוק לגורמים של \(N\) , כלומר מציאת \(p,q\) מתוך \(N\) . והבעיה הזו, של פירוק לגורמים, היא בעיה קשה מבחינה חישובית (כל עוד אין לנו מחשבים קוונטיים כאמור - זו הסתייגות שעם השנים נהיה יותר ויותר קריטי להוסיף).

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

אבל עכשיו בואו נסבך את הסיפור על ידי הכנסה פנימה של אנדרה הענק. אם הראשוניים של RSA היו שוורצנגר, אז מי שמשמשים בתור אנדרה הענק הם קבוצה קטנה של ראשוניים מאוד מסוימים: ראשוניי מרסן. אלו ראשוניים מהצורה \(2^{n}-1\) , והם נדירים יחסית - כרגע אנחנו מכירים רק 52 כאלו. אבל בגלל המאפיינים המתמטיים הייחודיים של מספרי מרסן, יש אלגוריתם לבדיקת הראשוניות של מספר מרסן שהוא יעיל משמעותית יותר מאלגוריתמי בדיקת הראשוניות ה"כלליים" (סיפרתי על זה כאן). התוצאה היא שמספרי מרסן הגדולים ביותר המוכרים לנו כיום הם עצומים לחלוטין, מגמדים לגמרי את מספרי RSA שדיברתי עליהם. לראשוני מרסן הגדול ביותר שנתגלה עד כה יש 41,024,320 ספרות. כלומר, הוא גדול פי יותר מאשר ארבעים מיליון ממספרים ראשוניים בני אלפי ספרות. יש פער עצום בין ראשוניי מרסן הגדולים וכל ראשוני אחר ששימש את האנושות אי פעם באופן פרקטי. אז במובן הזה רוב הראשוניים "שרלוונטיים לנו" הם קטנים.

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