הוכחת אוילר לקיום אינסוף ראשוניים

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

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

לצורך הבנת ההוכחה צריך להכיר את התיאוריה הבסיסית שמאחורי טורים אינסופיים, שכבר הצגתי כאן פעם ואזכיר בקצרה: ניקח סדרה של מספרים ממשיים שתסומן כ-\( a_{1},a_{2},a_{3},\dots \) (\( a_{1} \) הוא האיבר הראשון, \( a_{2} \) הוא השני וכו’). כעת נסתכל על סכום אברי הסדרה, ובאופן פרטני - סכום \( N \) האיברים הראשונים, מה שמסומן כ-\( S_{N}=\sum_{n=1}^{N}a_{n} \). לסכום הזה קוראים “סכום חלקי” של הסדרה - כלומר, מהסדרה \( a_{1},a_{2},a_{3},\dots \) קיבלנו סדרת סכומים חלקיים \( S_{1},S_{2},S_{3},\dots \). כעת, מגדירים את סכום הסדרה כולה להיות הגבול של סדרת הסכומים החלקיים, כלומר מסמנים \( \sum_{n=1}^{\infty}a_{n}=\lim_{N\to\infty}S_{N} \). לא אציג כאן שוב את ההגדרה הפורמלית ל”גבול” - אינטואיטיבית, אפשר לחשוב עליו בתור מספר שאברי הסדרה הולכים ומתקרבים אליו “עד כמה שנרצה” ככל שמתקדמים בסדרה.

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

דוגמה פשוטה לטור שמתכנס לאינסוף הוא הטור שמתקבל מהסדרה שכל איבריה הם 1, כלומר \( 1+1+1+\dots \). באותו אופן, כל טור של סדרה קבועה וחיובית מתבדר לאינסוף, ומכך נובע שכל טור שאפשר לחסום את כל האיברים בו מלמטה עם מספר חיובי כלשהו גם כן מתבדר לאינסוף (למשל, הטור \( \sum_{n}\left(1+\frac{1}{n}\right) \) מתבדר לאינסוף כי אפשר לחסום כל אחד מהאיברים שבו מלמטה על ידי 1). לכן מלכתחילה שאלות של התכנסות הן מעניינות רק על טורים שהאיבר הכללי שלהם שואף לאפס; והסדרות הפשוטות ביותר שהאיבר הכללי שלהן שואף לאפס הן מהצורה \( \frac{1}{n^{s}} \), כאשר \( s>0 \). אחת מהשאלות הראשונות ששואלים על טורים היא מהם הערכים של \( s \) שעבורם הטור \( \sum_{n=1}^{\infty}\frac{1}{n^{s}} \) מתכנס למספר סופי. התשובה היא אולי מפתיעה למדי במבט ראשון: אם \( s>1 \), הטור מתכנס; ואילו אם \( s\le1 \) הטור אינו מתכנס (כלומר, הוא מתבדר לאינסוף). מכאן שהנקודה \( s=1 \), שמניבה את הטור \( \sum_{n=1}^{\infty}\frac{1}{n} \) (שנקרא “הטור ההרמוני”) היא מעין נקודת גבול בין המתכנס והמתבדר. זה בדיוק המחקר של נקודת הגבול הזו שמוביל לתוצאות שאני רוצה לדבר עליהן.

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

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

נתחיל מתזכורת מבית הספר: טור הנדסי הוא טור מהצורה \( \sum_{n=0}^{\infty}a_{0}q^{n} \) עבור \( q \) ממשי כלשהו. למשל, \( 1+2+4+8+16+\dots \) הוא טור הנדסי שכזה. תוצאה בסיסית בחשבון אינפיניטסימלי מראה כי אם \( \left|q\right|<1 \), אז סכום הטור הזה הוא \( \frac{a_{0}}{1-q} \) (אם \( \left|q\right|\ge1 \) הטור מתבדר). בפרט, אם ניקח מספר ראשוני \( p \) כלשהו, הרי שלכתוב \( \frac{1}{1-p^{-1}} \) יהיה אותו הדבר בדיוק כמו לכתוב \( 1+p^{-1}+p^{-2}+p^{-3}+\dots \).

כעת נעבור לתזכורת אחרת מבית הספר: מה הערך של \( \left(1+x\right)\left(1+y\right) \) כאשר \( x,y \) הם מספרים? אחרי שנפתח את הסוגריים, נקבל \( 1+x+y+xy \). מאחורי הביטוי השרירותי הזה יש הרבה הגיון: קיבלנו סכום בן ארבעה מחוברים, כך שכל איבר התקבל באופן הבא: ראשית, בחרנו אחד משני האיברים בסוגר \( \left(1+x\right) \); שנית, בחרנו אחד משני האיברים בסוגר \( \left(1+y\right) \); שלישית, כפלנו את האיברים שבחרנו, והוספנו לסכום. כך למשל האיבר \( 1 \) שבסכום התקבל מבחירת 1 משני הסוגריים; האיבר \( y \) התקבל מבחירת 1 בסוגר הראשון, ו-\( y \) בשני, וכן הלאה. זה מסביר מדוע יש ארבעה איברים בסכום - זהו שיקול קומבינטורי טהור: יש 2 בחירות אפשריות מהסוגר הראשון, ו-2 בחירות אפשריות מהשני, וכל בחירה שכזו תיתן לנו איבר אחר של הסכום, ועל כן יש לנו סכום בן ארבעה איברים. אותו ההגיון תקף גם למשהו כמו \( \left(1+x\right)^{2}=\left(1+x\right)\left(1+x\right)=1+x+x+x^{2}=1+2x+x^{2} \) - כאן המקדם 2 של ה-\( x \) בא להראות לנו שישנם שני מחוברים בעלי הערך \( x \) בסכום הסופי. מכאן קצרה הדרך להבנת נוסחת הבינום של ניוטון, אך לא אכנס לכך כעת.

מה יקרה אם נגדיל את מספר האיברים בכל סוגר? או שנגדיל את מספר הסוגריים? הרעיון יישאר אותו רעיון - נקבל סכום של איברים, שבו כל איבר הוא מכפלה של איבר מכל סוגר. ומה יקרה אם הסכום שיש בכל סוגר הוא אינסופי? אז נקבל סכום שגם הוא אינסופי, אבל אנחנו יודעים בדיוק מי הם אבריו; אנסה לתת לכך דוגמה. נניח ש-\( p,q \) הם ראשוניים, ונתבונן במכפלה \( \left(1+p^{-1}+p^{-2}+\dots\right)\left(1+q^{-1}+q^{-2}+\dots\right) \). מהדיון הקודם ברור שכשנפתח את המכפלה, נקבל סכום של איברים, כך שכל איבר הוא מהצורה \( p^{-i}q^{-j} \) עבור \( i,j \) טבעיים כלשהם (כולל אפס). עד כאן הכל בסדר? אז בואו רק נשים לב לכך שניתן להציג את המכפלה של שני הסכומים הללו בדרך קומפקטית יותר: \( \left(\frac{1}{1-p^{-1}}\right)\left(\frac{1}{1-q^{-1}}\right) \).

כעת אוילר לוקח את הרעיון הזה לשלב הבא - מה יקרה אם נכפול זה בזה לא רק שניים, אלא מספר אינסופי של סכומים? אז נקבל סכום אינסופי, שכל איבר בו הוא בעצמו מכפלה אינסופית. מבלבל? אז בואו נראה את זה בעיניים. מה שאוילר מציע לעשות הוא להתבונן במכפלה \( \prod_{i=1}^{\infty}\left(1+p_{i}^{-1}+p_{i}^{-2}+\dots\right) \) (הסימן \( \prod \) מציין מכפלה מקוצרת, בדומה לסימן \( \sum \) המציין סכום), כך ש-\( p_{i} \) הוא הראשוני ה-\( i \) במספר בסדרת הראשוניים (כלומר, \( p_{1}=2,p_{2}=3,p_{3}=5 \) וכו’). אם נפתח את המכפלה הזו, נקבל סכום של איברים, כך שכל איבר הוא מהצורה \( \prod_{i=1}^{\infty}p^{-k_{i}} \), כאשר \( -k_{i} \) הוא החזקה ש”בחרנו” עבור הראשוני ה-\( i \) במכפלה.

שימו לב שאם \( k_{i}>0 \) אז \( p^{-k_{i}}<1 \). לא קשה להראות שמכפלה של אינסוף איברים שקטנים מ-1 שואפת לאפס, ולכן רוב האיברים בסכום נעלמים - היחידים ששורדים הם אלו שמהווים מכפלה של ראשוניים כך שהחל ממקום מסויים במכפלה, כל החזקות \( k_{i} \) שנבחרו הם 0. למשל: \( 2^{-1}\cdot3^{0}\cdot5^{0}\cdot7^{0}\cdots=2^{-1} \). מכאן שכל איבר בסכום, בסופו של דבר, יהיה ניתן לתיאור בתור \( \prod_{i=1}^{n}p^{-k_{i}} \) עבור \( n \) סופי כלשהו (לאיברים אחרים יהיו \( n \)-ים אחרים). למעשה, אפשר להוציא את המינוס החוצה, ולקבל שהאיבר יהיה מהצורה \( \left(\prod_{i=1}^{n}p^{k_{i}}\right)^{-1} \). אם כן, כדי להבין את המכפלה \( \prod_{i=1}^{\infty}\left(1+p_{i}^{-1}+p_{i}^{-2}+\dots\right) \) מספיק להבין מהם האיברים מהצורה \( \prod_{i=1}^{n}p^{k_{i}} \) - אבל מה הם באמת? הם בדיוק כל המספרים הטבעיים, וכל אחד מהם מופיע בדיוק פעם אחת, כי לכל מספר פירוק יחיד לגורמים כמכפלה של ראשוניים (מכפלה שניתן לחשוב עליה כמכפלת כל אינסוף הראשוניים, בתנאי שכולם פרט למספר סופי הם בעלי החזקה 0). זה לב לבו של העניין - כאן נכנס המשפט היסודי של האריתמטיקה לתמונה.

את כל הדיון הזה אפשר לצמצם לכדי הנוסחה הבאה: \( \prod_{p}\frac{1}{1-p^{-1}} = \sum_{n=1}^{\infty}\frac{1}{n} \)

המכפלה שבאגף שמאל היא המכפלה שעליה דיברנו, כשהיא נלקחת על כל הראשוניים (השימוש ב-\( p \) באינדקס, כדי לציין “האינדקס רץ על פני כל המספרים הראשוניים” הוא סטנדרטי ומקובל), בהצגה הקומפקטית שבה \( 1+p_{i}^{-1}+p_{i}^{-2}+\dots \) מוצג בתור \( \frac{1}{1-p^{-1}} \). באגף ימין יש לנו את סכום כל האיברים ש”שרדו”, שכאמור הם בדיוק כל הטבעיים, בחזקת המינוס 1 שהוצאנו החוצה. כלומר, אפשר להציג את הטור ההרמוני בתור מכפלה - ולא סתם מכפלה, כזו שנלקחת בדיוק על המספרים הראשוניים.

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

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

\( \zeta\left(s\right) = \sum_{n=1}^{\infty}\frac{1}{n^{s}}=\prod_{p}\frac{1}{1-p^{-s}} \)

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

כאן נגמר אוילר, אבל דיריכלה רק מתחיל, ואותו אתאר בפעם הבאה. מטרתו של דיריכלה הייתה יותר שאפתנית משל אוילר - להראות לא רק שיש אינסוף ראשוניים, אלא שבכל סדרה חשבונית מהצורה \( a,a+d,a+2d,\dots \) כך שאין מחלק משותף ל-\( a \) ול-\( d \) יש אינסוף ראשוניים. ההוכחה מתבססת על חקירת ההתנהגות בסביבות הנקודה 1 של פונקציות דומות מאוד לפונקצית הזטא של רימן - פונקציות ה-\( L \) של דיריכלה.