השערת ברטראן

השערת ברטראן (על שם המתמטיקאי הצרפתי ז'וזף ברטראן) טוענת כי לכל מספר טבעי $n > 3$ קיים לפחות מספר ראשוני אחד $n < p < 2 n - 2$ .

גרסה חלשה יותר לטענה: לכל $n \geq 2$ קיים לפחות מספר ראשוני אחד $n < p < 2 n$ .

ברטראן העלה השערה זו לראשונה ב-1845, ואף וידא את תקפותה לכל $2 \leq n \leq 3 \cdot 1 0^{6}$ . למעשה השם "השערה" אינו מתאר נכונה טענה זו, שכן בשנת 1850 הציג המתמטיקאי הרוסי פפנוטי צ'בישב הוכחה מלאה לטענה, ועל כן היא בגדר משפט. לפיכך, היא נקראת לעיתים "משפט ברטראן–צ'בישב" או "משפט צ'בישב". המתמטיקאי ההודי סריניוואסה רמנוג'אן הציג בשנת 1919 תבנית:הערה הוכחה פשוטה יותר למשפט, הנעזרת בתכונות של פונקציית גמא, ופאול ארדש הציג בשנת 1932 הוכחה פשוטה מזותבנית:הערה, הנעזרת בפונקציית צ'בישב תבנית:הערה ובמקדמים בינומיים.

הוכחה

להלן תובא הוכחתו של פאול ארדש בשינויים קלים. נקדים לה למות אחדות:

למה 1: לכל $n \geq 1$ מתקיים $(\binom{2 n}{n}) \geq \frac{4^{n}}{2 n}$ .תבנית:ש הוכחה: המקדם הבינומי הזה הוא הגדול מבין 2n המחוברים $(\binom{2 n}{k})$ (כאשר שני הקצוות נספרים כמחובר אחד) שסכומם הוא $4^{n}$ ; לכן הוא גדול מהממוצע שלהם.

למה 2: (נוסחת לז'נדר) יהי $p$ מספר ראשוני. נגדיר $R (p, n) = \max {r \in ℕ : p^{r} | (\binom{2 n}{n})}$ . אזי מתקיים $R (p, n) \leq \log_{p} (2 n)$ . בפרט:תבנית:ש

עבור $p > \sqrt{2 n}$ מתקיים $0 \leq R (p, n) \leq 1$ , שכן $p^{2} > 2 n$ .
עבור $\frac{2}{3} n < p \leq n$ אי-זוגי מתקיים $p \leq n < 2 p \leq 2 n < 3 p \leq 3 n$ , ולכן $R (p, n) = 0$ .תבנית:ש

למה 3: מכפלת הראשוניים שאינם גדולים מ- $n$ אינה גדולה מ- $4^{n}$ .תבנית:ש הוכחה: נשתמש באינדוקציה שלמה. נגדיר $n # = \prod_{p \leq n} p$ .תבנית:ש עבור $n = 1$ מתקיים $1 # = 1 \leq 4$ (מכפלה ריקה).תבנית:ש

נניח כי הטענה מתקיימת לכל $1 \leq n \leq 2 k - 1$ . אזי עבור $n = 2 k \geq 2$ מתקיים

(2 k) # = (2 k - 1) # \leq 4^{2 k - 1} < 4^{2 k}

נניח כי הטענה מתקיימת לכל $1 \leq n \leq 2 k$ . נרשום $(2 k + 1) # = (k + 1) # \cdot \frac{(2 k + 1) #}{(k + 1) #}$ .

\frac{(2 k + 1) #}{(k + 1) #}

מחלק את

(\binom{2 k + 1}{k}) = \frac{(2 k + 1)!}{k! (k + 1)!}

, שכן כל הראשוניים

k + 2 \leq p \leq 2 k + 1

מופיעים רק במונהו של המקדם הבינומי.תבנית:ש תבנית:ש

\begin{matrix} \frac{(2 k + 1) #}{(k + 1) #} \leq (\binom{2 k + 1}{k}) \leq \sum_{j = 0}^{k} (\binom{2 k + 1}{j}) = \frac{1}{2} \sum_{j = 0}^{2 k + 1} (\binom{2 k + 1}{j}) = \frac{1}{2} \cdot 2^{2 k + 1} = 4^{k} \\ (2 k + 1) # = (k + 1) # \cdot \frac{(2 k + 1) #}{(k + 1) #} \leq 4^{k + 1} \cdot 4^{k} = 4^{2 k + 1} \end{matrix}

נניח בשלילה כי אין ראשוניים $n < p < 2 n$ .תבנית:ש מספר הראשוניים שאינם גדולים מ- $n$ מקיים $π (n) \leq n - 1$ , שכן המספר 1 אינו ראשוני ואינו פריק. עבור $n > 4$ מתקיים $\sqrt{2 n} < \frac{2}{3} n$ . לכן

\begin{matrix} \frac{4^{n}}{2 n} \leq (\binom{2 n}{n}) = \prod_{p \leq n} p^{R (p, n)} & = \prod_{p \leq \sqrt{2 n}} p^{R (p, n)} \prod_{\sqrt{2 n} < p \leq \frac{2}{3} n} p^{R (p, n)} \prod_{\frac{2}{3} n < p \leq n} p^{R (p, n)} \prod_{n < p < 2 n} p^{R (p, n)} \\ \leq \prod_{p \leq \sqrt{2 n}} 2 n \prod_{\sqrt{2 n} < p \leq \frac{2}{3} n} p \leq \prod_{p \leq \sqrt{2 n}} 2 n \prod_{p \leq \frac{2}{3} n} p \\ \leq (2 n)^{\sqrt{2 n} - 1} \cdot 4^{2 n / 3} \end{matrix}

קבלנו את האי-שוויון $4^{n / 3} \leq (2 n)^{\sqrt{2 n}}$ השקול לאי-שוויון $2^{x} \leq x^{6}$ כאשר $x = \sqrt{2 n}$ . אך אי-שוויון זה מתהפך עבור $n > 426$ . סתירה.תבנית:ש

עבור $n \leq 426$ די להראות כי הקטע הפתוח $(n, 2 n)$ מכיל לפחות אחד מן הראשוניים $2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631$ (אשר כל אחד מהם קטן מפעמיים קודמו).

נימוק היוריסטי

ממשפט המספרים הראשוניים נובעת טענה חזקה בהרבה: לכל $ϵ > 0$ , אם $n$ גדול מספיק אז יש ראשוניים בקטע $(n, n + ϵ n)$ . הסיבה לכך היא שלפי המשפט, מספר הראשוניים שאינם גדולים מ- $x$ הוא בקירוב $π (x) \sim \frac{x}{\ln (x)}$ – כאשר $\ln (x)$ פונקציית הלוגריתם הטבעי ו- $π (x)$ פונקציית מספר הראשוניים שאינם גדולים מ- $x$ .

המשפט מאפשר לחשב בקירוב את מספר הראשוניים בקטע. נקבל:

π ((1 + ϵ) n) - π (n) \sim \frac{(1 + ϵ) n}{\ln ((1 + ϵ) n)} - \frac{n}{\ln (n)} = \frac{n}{\ln (n)} (\frac{1 + ϵ}{(\ln (1 + ϵ) + \ln (n)) / \ln (n)} - 1) = \frac{n}{\ln (n)} (\frac{1 + ϵ}{1 + \ln (1 + ϵ) / \ln (n)} - 1) \sim \frac{ϵ n}{\ln (n)}

כאשר $n$ שואף לאינסוף, ההפרש – מספר הראשוניים בקטע – שואף לאינסוף.

קישורים חיצוניים

תבנית:MathWorld

הערות שוליים

תבנית:הערות שוליים

תבנית:קצרמר

השערת ברטראן

תוכן עניינים

הוכחה

נימוק היוריסטי

קישורים חיצוניים

הערות שוליים

תפריט ניווט

השערת ברטראן

הוכחה

נימוק היוריסטי

קישורים חיצוניים

הערות שוליים

תפריט ניווט

חיפוש