השערת ברטראן

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

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

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

הוכחה

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

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

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

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

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

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

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

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

${\frac {(2k+1)\#}{(k+1)\#}}$ מחלק את ${\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}$, שכן כל הראשוניים $k+2\leq p\leq 2k+1$ מופיעים רק במונהו של המקדם הבינומי.

${\begin{aligned}&{\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}\leq \sum _{j\,=\,0}^{k}{\binom {2k+1}{j}}={\frac {1}{2}}\sum _{j\,=\,0}^{2k+1}{\binom {2k+1}{j}}={\frac {1}{2}}\cdot 2^{2k+1}=4^{k}\\\\&(2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}\cdot 4^{k}=4^{2k+1}\end{aligned}}$

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

${\begin{aligned}{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\prod _{p\,\leq \,n}p^{R(p,n)}&=\prod _{p\,\leq \,{\sqrt {2n}}}\!\!p^{R(p,n)}\!\!\!\!\!\!\prod _{{\sqrt {2n}}\,<\,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\,<\,2n}\!\!\!\!p^{R(p,n)}\\\\&\leq \prod _{p\,\leq \,{\sqrt {2n}}}\!\!\!2n\!\!\prod _{{\sqrt {2n}}\,<\,p\,\leq \,{\frac {2}{3}}n}\!\!\!\!\!\!\!\!p\quad \leq \prod _{p\,\leq \,{\sqrt {2n}}}\!\!\!2n\prod _{p\,\leq \,{\frac {2}{3}}n}\!\!p\\\\&\leq (2n)^{{\sqrt {2n}}-1}\cdot 4^{2n/3}\end{aligned}}$

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

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

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

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

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

$\pi ((1+\epsilon )n)-\pi (n)\sim {\frac {(1+\epsilon )n}{\ln((1+\epsilon )n)}}-{\frac {n}{\ln(n)}}={\frac {n}{\ln(n)}}\left({\frac {1+\epsilon }{(\ln(1+\epsilon )+\ln(n))/\ln(n)}}-1\right)={\frac {n}{\ln(n)}}\left({\frac {1+\epsilon }{1+\ln(1+\epsilon )/\ln(n)}}-1\right)\sim {\frac {\epsilon n}{\ln(n)}}$

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

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

• השערת ברטראן, באתר MathWorld (באנגלית)

הערות שוליים

 

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.