ההסתברות של מספרים זרים ואיך פאי נכנס לתמונה

באחת מהתגובות בבלוג שאלו אותי שאלה פשוטה - נניח שאנחנו מגרילים באקראי שני מספרים טבעיים, מה ההסתברות שהם יהיו זרים, כלומר שלא יהיה מספר טבעי גדול מ-1 שמחלק את שניהם גם יחד? התשובה היא \( \frac{6}{\pi^{2}} \), מה שנראה מוזר מאוד במבט ראשון - מה פאי עושה כאן, הרחק מכל מעגל אפשרי?

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

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

מכיוון שהבחירה של שני המספרים נעשית באופן בלתי תלוי (הבחירה במספר אחד לא משפיעה על הבחירה במספר השני), ההסתברות ששניהם יתחלקו ב-\( p \) היא מכפלת ההסתברויות עבור כל אחד מהם להתחלק ב-\( p \). כעת, \( p \) מחלק אחד מכל \( p \) מספרים (2 מחלק כל מספר זוגי; 3 מחלק, ובכן, כל מספר שמתחלק ב-3, וכן הלאה) ולכן ההסתברות לכך שמספר אקראי יתחלק ב-\( p \) היא \( \frac{1}{p} \), ולכן ההסתברות ששני מספרים אקראיים יתחלקו שניהם ב-\( p \) היא \( \frac{1}{p^{2}} \).

כעת, אנחנו רוצים שלמספרים שלנו לא יהיה אף גורם משותף, כלומר שלכל ראשוני \( p \), לא יתקיים ש-\( p \) מחלק את שניהם. אם \( \frac{1}{p^{2}} \) היא ההסתברות ש-\( p \) כן יחלק את שני המספרים האקראיים, אז ההסתברות ה”משלימה”, לכך שהוא לא יחלק את שניהם (כלומר, יחלק רק אחד מהם או לא יחלק אף אחד מהם) היא \( 1-\frac{1}{p^{2}} \). ההסתברות שזה יקרה לכל הראשוניים הקיימים (בהנחה שאיני מוכיח כאן - כפי שתגובות רבות מעירות - שההסתברויות לראשוניים שונים הן בלתי תלויות) היא מכפלת ההסתברויות לכל הראשוניים; מה שמסומן במתמטית בתור \( \prod_{p}\left(1-\frac{1}{p^{2}}\right) \) (\( \Pi \) הוא סימן קיצור מוסכם לכפל, כמו ש-\( \Sigma \) הוא סימן קיצור מוסכם לחיבור; ויש הסכמה על כך שה-\( p \) למטה עובר רק על הראשוניים). המכפלה הזו נראית מוזרה במבט ראשון כי משתתפים בה אינסוף איברים, וצריך להגדיר לה מושג של התכנסות כפי שמוגדר כזה עבור סכום אינסופי, אבל כאמור - אנחנו עכשיו עושים הוכחה בסגנון אוילר.

בשלב הזה אני שולף מהבוידם את התעלול של אוילר שהצגתי כבר בבלוג בעבר: אוילר מראה כי \( \zeta\left(s\right) \), הערך של פונקצית הזטא של רימן בנקודה \( s \) עבור \( s>1 \) ממשי, שמוגדר כ-\( \sum_{n=1}^{\infty}\frac{1}{n^{s}} \), מקיים \( \zeta\left(s\right)=\prod_{p}\left(\frac{1}{1-p^{-s}}\right) \). הרעיון הכללי כאן הוא ש-\( \frac{1}{1-p^{-s}} \) זו בעצם דרך אחרת לכתוב \( 1+p^{-s}+p^{-2s}+p^{-3s}+\dots \), ומכיוון שהכפל רץ על כל הראשוניים ובשל הפירוק היחיד לראשוניים של המספרים הטבעיים, כשמבצעים פתיחת סוגריים מקבלים את כל האיברים מהצורה \( n^{-s} \), לכל \( n \) אפשרי. זהו מעין אפיון אנליטי של המשפט היסודי של האריתמטיקה, ותוצאה יפהפה בכל קנה מידה אפשרי לטעמי.

הביטוי שלנו די דומה: השוו את \( \prod_{p}\left(1-\frac{1}{p^{2}}\right) \) עם \( \prod_{p}\left(\frac{1}{1-p^{-2}}\right) \). איך עוברים מאחד לשני? ובכן:

\( \prod_{p}\left(1-\frac{1}{p^{2}}\right)=\prod_{p}\left(1-p^{-2}\right)=\prod_{p}\left(\frac{1}{1-p^{-2}}\right)^{-1}=\left[\prod_{p}\left(\frac{1}{1-p^{-2}}\right)\right]^{-1}=\zeta\left(2\right)^{-1}=\frac{6}{\pi^{2}} \)

וזה סוף הסיפור.

למה הסיפור בכל זאת לא נגמר כאן? כי כאמור, קצת רימיתי בהתחלה. כשאני אומר ש”מספר טבעי נבחר באקראי”, מה זה אומר? אם רוצים לדבר פורמלית צריך להסביר מהי ההסתברות שיש לכל מספר טבעי להיבחר, וההנחה הסמויה כאן היא שההסתברות של כל מספר טבעי היא שווה. נאמר, \( a \), כש-\( a \) הוא מספר גדול מ-0 וקטן מ-1. מייד אנחנו רואים שיש כאן בעיה כי אחרי \( \frac{1}{a} \) מספרים, ההסתברות שאחד מהם יצא תהיה גדולה כבר מ-1…

לדוגמה, אם אני אומר שכל מספר טבעי נבחר באותה הסתברות - \( \frac{1}{5} \) - אז אני אומר שגם 1, וגם 2, וכדומה עד 6 - כולם נבחרים בהסתברות \( \frac{1}{5} \). אז ההסתברות שאחד מהם ייבחר היא \( \frac{1}{5}+\dots+\frac{1}{5}=\frac{6}{5} \), ומספר זה כבר גדול מ-1. זה פשוט לא עובד. אין התפלגות אחידה על כל הטבעיים.

אפשר כמובן להגדיר התפלגויות לא אחידות (למשל, המספר \( n \) נבחר בהסתברות \( \frac{1}{2^{n}} \)) אבל אז כל הניתוח ההסתברותי שעשינו למעלה והניח שלכל מספר טבעי אותה הסתברות להיבחר יורד לטמיון. אז מה עושים?

הפתרון הוא כזה: קובעים \( N \) גדול כלשהו, ומגרילים רק מספרים בין 1 ל-\( N \), כשכל אחד מהם נבחר בהסתברות \( \frac{1}{N} \). כעת חוזרים על ההוכחה שלמעלה; לצורך נוחות טכנית אפשר לבחור את \( N \) תמיד להיות כפולה של כל הראשוניים עד לראשוני מסויים, ואז רק הם משתתפים במשחק ואף ראשוני אחר לא. מה שנקבל בסוף הוא את המכפלה \( \prod_{p}\left(1-\frac{1}{p^{2}}\right) \) כשהיא אינה נלקחת על כל הראשוניים אלא רק עד גבול מסויים; אבל ככל שנגדיל את \( N \) כך המכפלה הזו תשאף לערך של המכפלה האינסופית, שהוא \( \frac{6}{\pi^{2}} \) המבוקש. לכן הניסוח המדויק של השאלה מתחילת הפוסט הוא זה “כאשר בוחרים מספרים טבעיים באקראי מתחום גדול מאוד, מה בערך ההסתברות שהם יהיו זרים?” ולמי שזה לא מספיק פורמלי עבורו, “לאן שואפת ההסתברות ששני מספרים טבעיים שנבחרו בהתפלגות אחידה מתוך \( \left[1,\dots,N\right] \) יהיו זרים כאשר \( N \) שואף לאינסוף”?

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