להלן תובא הוכחתו של פאול ארדש בשינויים קלים. נקדים לה למות אחדות:
למה 1: לכל
n
≥
1
{\displaystyle n\geq 1}
מתקיים
(
2
n
n
)
≥
4
n
2
n
{\displaystyle {\binom {2n}{n}}\geq {\frac {4^{n}}{2n}}}
.
הוכחה:
המקדם הבינומי הזה הוא הגדול מבין 2n המחוברים
(
2
n
k
)
{\displaystyle {\binom {2n}{k}}}
(כאשר שני הקצוות נספרים כמחובר אחד) שסכומם הוא
4
n
{\displaystyle 4^{n}}
; לכן הוא גדול מהממוצע שלהם.
למה 2: (נוסחת לז'נדר ) יהי
p
{\displaystyle p}
מספר ראשוני . נגדיר
R
(
p
,
n
)
=
max
{
r
∈
N
:
p
r
|
(
2
n
n
)
}
{\displaystyle R(p,n)=\max \left\{r\in \mathbb {N} :p^{r}{\Big |}{\binom {2n}{n}}\right\}}
. אזי מתקיים
R
(
p
,
n
)
≤
log
p
(
2
n
)
{\displaystyle R(p,n)\leq \log _{p}(2n)}
. בפרט:
עבור
p
>
2
n
{\displaystyle p>{\sqrt {2n}}}
מתקיים
0
≤
R
(
p
,
n
)
≤
1
{\displaystyle 0\leq R(p,n)\leq 1}
, שכן
p
2
>
2
n
{\displaystyle p^{2}>2n}
.
עבור
2
3
n
<
p
≤
n
{\displaystyle {\frac {2}{3}}n<p\leq n}
אי-זוגי מתקיים
p
≤
n
<
2
p
≤
2
n
<
3
p
≤
3
n
{\displaystyle p\leq n<2p\leq 2n<3p\leq 3n}
, ולכן
R
(
p
,
n
)
=
0
{\displaystyle R(p,n)=0}
.
למה 3: מכפלת הראשוניים שאינם גדולים מ-
n
{\displaystyle n}
אינה גדולה מ-
4
n
{\displaystyle 4^{n}}
.
הוכחה: נשתמש באינדוקציה שלמה . נגדיר
n
#
=
∏
p
≤
n
p
{\displaystyle n\#=\prod _{p\,\leq \,n}p}
.
עבור
n
=
1
{\displaystyle n=1}
מתקיים
1
#
=
1
≤
4
{\displaystyle 1\#=1\leq 4}
(מכפלה ריקה ).
נניח כי הטענה מתקיימת לכל
1
≤
n
≤
2
k
−
1
{\displaystyle 1\leq n\leq 2k-1}
. אזי עבור
n
=
2
k
≥
2
{\displaystyle n=2k\geq 2}
מתקיים
(
2
k
)
#
=
(
2
k
−
1
)
#
≤
4
2
k
−
1
<
4
2
k
{\displaystyle (2k)\#=(2k-1)\#\leq 4^{2k-1}<4^{2k}}
נניח כי הטענה מתקיימת לכל
1
≤
n
≤
2
k
{\displaystyle 1\leq n\leq 2k}
. נרשום
(
2
k
+
1
)
#
=
(
k
+
1
)
#
⋅
(
2
k
+
1
)
#
(
k
+
1
)
#
{\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}}
.
(
2
k
+
1
)
#
(
k
+
1
)
#
{\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}}
מחלק את
(
2
k
+
1
k
)
=
(
2
k
+
1
)
!
k
!
(
k
+
1
)
!
{\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}
, שכן כל הראשוניים
k
+
2
≤
p
≤
2
k
+
1
{\displaystyle k+2\leq p\leq 2k+1}
מופיעים רק במונהו של המקדם הבינומי .
(
2
k
+
1
)
#
(
k
+
1
)
#
≤
(
2
k
+
1
k
)
≤
∑
j
=
0
k
(
2
k
+
1
j
)
=
1
2
∑
j
=
0
2
k
+
1
(
2
k
+
1
j
)
=
1
2
⋅
2
2
k
+
1
=
4
k
(
2
k
+
1
)
#
=
(
k
+
1
)
#
⋅
(
2
k
+
1
)
#
(
k
+
1
)
#
≤
4
k
+
1
⋅
4
k
=
4
2
k
+
1
{\displaystyle {\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
<
2
n
{\displaystyle n<p<2n}
.
מספר הראשוניים שאינם גדולים מ-
n
{\displaystyle n}
מקיים
π
(
n
)
≤
n
−
1
{\displaystyle \pi (n)\leq n-1}
, שכן המספר 1 אינו ראשוני ואינו פריק. עבור
n
>
4
{\displaystyle n>4}
מתקיים
2
n
<
2
3
n
{\displaystyle {\sqrt {2n}}<{\frac {2}{3}}n}
. לכן
4
n
2
n
≤
(
2
n
n
)
=
∏
p
≤
n
p
R
(
p
,
n
)
=
∏
p
≤
2
n
p
R
(
p
,
n
)
∏
2
n
<
p
≤
2
3
n
p
R
(
p
,
n
)
∏
2
3
n
<
p
≤
n
p
R
(
p
,
n
)
∏
n
<
p
<
2
n
p
R
(
p
,
n
)
≤
∏
p
≤
2
n
2
n
∏
2
n
<
p
≤
2
3
n
p
≤
∏
p
≤
2
n
2
n
∏
p
≤
2
3
n
p
≤
(
2
n
)
2
n
−
1
⋅
4
2
n
/
3
{\displaystyle {\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
≤
(
2
n
)
2
n
{\displaystyle 4^{n/3}\leq (2n)^{\sqrt {2n}}}
השקול לאי-שוויון
2
x
≤
x
6
{\displaystyle 2^{x}\leq x^{6}}
כאשר
x
=
2
n
{\displaystyle x={\sqrt {2n}}}
. אך אי-שוויון זה מתהפך עבור
n
>
426
{\displaystyle n>426}
. סתירה.
עבור
n
≤
426
{\displaystyle n\leq 426}
די להראות כי הקטע הפתוח
(
n
,
2
n
)
{\displaystyle (n,2n)}
מכיל לפחות אחד מן הראשוניים
2
,
3
,
5
,
7
,
13
,
23
,
43
,
83
,
163
,
317
,
631
{\displaystyle 2,3,5,7,13,23,43,83,163,317,631}
(אשר כל אחד מהם קטן מפעמיים קודמו).
נימוק היוריסטי
עריכה
קישורים חיצוניים
עריכה
הערות שוליים
עריכה