פנינים אנליטיות בתורת המספרים – הערכות צ'בישב

איך עובר החג? מעולה? יופי.

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

הדוגמא מבוססת על מאמר קצר שפורסם בThe American Mathematical Monthly, או בקיצור AMM, ירחון מתמטי נפלא ומגוון שתמיד מכיל מאמרים קלילים ומעניינים. יש בו גם פינת בעיות ולעיתים מאמרים לא טכניים, כמו היסטוריה מתמטית וחינוך מתמטי. תקצירי מאמרים אפשר למצוא כאן. אם אתם גולשים מרשת אוניברסיטה שרשומה לירחון אז תוכלו למצוא את המאמרים בJournal Storage, אחרת – בסיכוי גבוה תוכלו למצוא את המאמר בדף הבית של המחבר בחינם.


  • הערכה לפונקציה סופרת-הראשוניים ולכפולה המשותפת המינימלית של 1,2,\cdots,n

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

עוד בסוף המאה ה18 שיערו גאוס ולז'נדר כי \pi(x) \sim \frac{x}{\ln x}! הכוונה היא ש:

הפורטרט המוצלח במתמטיקה

אדריאן-מארי לז'נדר, 1752-1833. את ההשערה גיבשו גאוס ולז'נדר על סמך עדויות אמפיריות בלבד

\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1

כלומר, הצפיפות של המספרים הראשוניים עד n היא בערך (אסימפטוטית) \frac{1}{\ln n}.

צ'בישב2 הוכיח באמצע המאה ה19 כי \pi(x) = \theta(\frac{x}{\ln x}), כלומר כי יש קבועים חיוביים c, C (ספציפית – c<1<C) כך שמתקיים c\frac{x}{\ln x} < \pi(x) < C\frac{x}{\ln x}, וגם הראה שאם קיים הגבול שמחושב בהשערה, אז הוא שווה אחת.  רק ב1896 נמצאה הוכחה להשערה של גאוס ולז'נדר, השערה שנקראת כעת "משפט המספרים הראשוניים". היא נמצאה באופן בלתי-תלוי ע"י הדמר וואלה פוסן (כמו במקרה של המשפט הקטן של פרמה. אמרתי שזה שכיח). ההוכחה הייתה שונה מכל מה שצ'בישב עשה וסבבה סביב פונקציית הזטא של רימן.

במאמר On Chebyshev-Type Inequalities for Primes של M. Nair הוא מוכיח קירובים דומים לשל צ'בישב, אבל בצורה אלגנטית, מפתיעה וקצרה יותר. לשם כך, הוא מגדיר את הסדרה d_n: הכמק"ב של המספרים 1 עד n. כמק"ב הוא הכפולה המשותפת הקטנה ביותר של המספרים (בלעז: LCM – least common multiple) – המספר הקטן ביותר שמתחלק בכל המספרים עבורם הוא מחושב. לדוגמא: הכמק"ב של 10 ו17 הוא 170, כי הוא מתחלק בשניהם ואין מספר קטן יותר שמקיים זאת. הכמק"ב של 4, 6 ו9 הוא 36. אם המספר הזה מוכר לכם, זה בגלל אחת מהשתיים:

  • כשעושים מכנה משותף לשברים, למעשה מחשבים את הכמק"ב של המכנים.
  • זו פונקציה "משלימה" של הממג"ב: המחלק המשותף הגדול ביותר (GCD – greatest common divisor), ואף מתקיימת הזהות הבאה: (a,b)[a,b]=ab כאשר (a,b) זה הGCD ו[a,b] זה הLCM.

הוא פונה להעריך את d_n – הכמק"ב של כל המספרים 1 עד n. הוא עושה זאת בעזרת האינטגרל הבא – מקרה פרטי של פונקציית בטא:

I_n = \int_{0}^{1} x^n(1-x)^n dx =

והוא פותח סוגריים בעזרת הבינום של ניוטון:

= \int_{0}^{1} x^n \sum_{r=0}^{n} \binom{n}{r}(-x)^r dx = \int_{0}^{1} \sum_{r=0}^{n} \binom{n}{r}(-1)^{r}(x)^{r+n} dx = \sum_{r=0}^{n} \binom{n}{r}(-1)^{r} (\int_{0}^{1} x^{r+n} dx)=

ולחשב אינטגרל של \int x^k גם חתול יכול:

=\sum_{r=0}^{n} \binom{n}{r}(-1)^{r} \frac{1}{r+n+1}

כלומר האינטגרל הוא סכום של שברים שהמכנה שלהם נע בין n+1 ל2n+1. בפרט, אם נכפול את האינטגרל בd_{2n+1} שמתחלק בכל המספרים הללו, נקבל מספר שלם, ואף טבעי – כי האינטגרנד (הביטוי עליו עושים אינטגרציה) חיובי: d_{2n+1} I_{n} \ge 1.

מצד שני, אפשר להעריך בגסות את ערך האינטגרל: x(1-x) \le \frac{1}{4} בקטע [0,1], ולכן I_n \le \int_{0}^{1} (\frac{1}{4})^n dx = \frac{1}{4^n}. אם נאגד את שתי התוצאות נקבל:

d_{2n+1} \ge \frac{1}{I_n} \ge 4^{n}=2^{2n}

ומכאן קל לקבל שd_n \ge \frac{1}{4} 2^{n} לכל n טבעי (עשו זאת!). קיבלנו חסם תחתון בדרך כמו-קסומה.

כעת הוא מקשר בין \pi(n) ובין d_n. הוא עושה זאת בדרך הבאה: נסתכל על הפירוק של d_n לחזקות של ראשוניים. לדוגמא: d_5=LCM(1,2,3,4,5)=60=2^{2}3^{1}5^{1}. אם מופיעה חזקה p^k בפירוק הזה, אז בהכרח אחד המספרים שנכללו בחישוב הכמק"ב מתחלק בחזקה הזו: אחרת, אם כל אחד מהמספרים מתחלק בחזקה קטנה יותר, היתה מופיעה בפירוק חזקה קטנה יותר. לכן, p^k \le n (כי p^k מחלקת מספר בין 1 לn).

יש לכל היותר \pi(n) חזקות של ראשוניים בפירוק הזה, כי d_n מתחלק רק בראשוניים הקטנים/שווים לn. הראנו שכל חזקה כזו קטנה/שווה n. ביחד:

d_n \le \underbrace{n \cdot n \cdots \cdot n}_{\pi (n)} = n^{\pi(n)}

ואם נפעיל \ln על שני האגפים ונחלק ב\ln n נקבל:

\pi(n) \ge \frac{\ln d_n}{\ln n} \ge \frac{\ln (\frac{1}{4} \cdot 2^n)}{\ln n} = (\ln 2)\frac{n}{\ln n} - (\frac{\ln 4}{\ln n})

והשגנו חסם תחתון מרשים על כמות הראשוניים! טא-דא. הגורם בסוגריים זניח (שואף ל0).

אם מתעסקים במקום עם I_n עם המשפחה הגדולה יותר I_{n,m} = \int_{0}^{1}x^{m-1}(1-x)^{n-m} dx, אפשר – אם עובדים בדרך הוכחה דומה – להיפטר מהגורם בסוגריים.

בהמשך, המחבר מוכיח תכונות אריתמטיות נוספות של d_n כדי לתת לו חסם עליון (d_n \le 4^n) ואז גם ל\pi(n), אבל זה פחות אינטגרלי.


כמה רחוקה ההערכה לגבי d_n מהאמת? המאמר נותן את החסם 2^n \le d_n \le 4^n. ראינו כבר את החסם \ln d_n \le \pi(n) \ln n. כדי לקבל חסם תחתון, אפשר להגיד שכל ראשוני קטן/שווה לn מחלק את d_n ושd_n חייב להיות גדול/שווה למכפלה שלהם. אם נסמן את סדרת הראשוניים בתור p_i, אפשר לקבל:

d_n \ge \prod_{p_i \le n} p_i = e^{\sum_{p_i \le n} \ln p_i}

מתברר שאת הפונקציה במעריך חקרו – היא נקראת פונקציית צ'בישב ומסומנת \vartheta(n), ומשפט המספרים הראשוניים שקול לכך שהיא אסימפטוטית מתנהגת כמו n. סה"כ קיבלנו:

e^{\vartheta{n}} \le d_n \le e^{\pi(n) \ln n}

ומשפט המספרים הראשוניים גורר ש\ln d_n \sim n, ובמובן (חלש) מתקיים d_n \sim e^n. יאי! (ועל הדרך קיבלנו ש-e הוא מספר בין 2 ל-4.)


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

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


לקריאה נוספת:

On Chebyshev-Type Inequalities for Primes by M. Nairהמאמר עליו התבססתי. קריא, קצר ומעניין. משיג את החסם העליון שבחרתי לא להוכיח כאן.

Explorations in Number Theory – ככה צ'בישב עשה את זה במקור. לא שונה מהותית, אבל פחות מגניב וקצר.


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

(השערה: כל בלוג ממימד n הוא איחוד סופי של פינות ממימד n-1)


פינת החידה הלילית:

חשבו במפורש (ביטוי סגור בלי סכימה) את ערך האינטגרל I_{n,m}.


בברכת "העריכו את הראשוניים",

פרנקו

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה כללי, תורת המספרים. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

3 תגובות על פנינים אנליטיות בתורת המספרים – הערכות צ'בישב

  1. לגבי האינטגרל, אפשר לעשות את I_n ע"י אינטגרציה בחלקים n פעמים כך שבסוף נשארים עם אינטגרל של חזקה של x. אם לא טעיתי בחישוב, יוצא (n עצרת) בריבוע חלקי (2n+1 עצרת). לא עשיתי את אותו הדבר ל-I_n,m מטעמי אלרגיה לריבוי אינדקסים.

  2. רוסו הגיב:

    רק שתדע שנכנסת לרסס שלי, אז אני מצפה לעוד פוסטים =]

  3. פינגבאק: תורת המספרים האנליטית | One and One

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s