Постулат Бертрана

Здесь мы приводим доказательство, предложенное Эрдёшем.

Обозначения и определения

В доказательстве мы используем следующие обозначения:

• ${\displaystyle {a \choose b}}$ — биномиальный коэффициент или число сочетаний из ${\displaystyle a}$ по ${\displaystyle b}$.
• ${\displaystyle \left\lfloor x\right\rfloor }$ — целая часть ${\displaystyle x}$.

Обозначим множество простых чисел через ${\displaystyle \mathbb {P} }$ и определим ${\displaystyle \theta (n)}$ как сумму логарифмов простых чисел, не превышающих ${\displaystyle n}$:

${\displaystyle \theta (n)=\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p).}$

Например, ${\displaystyle \theta (10)=\ln 2+\ln 3+\ln 5+\ln 7}$.

Эта функция называется ${\displaystyle \theta }$-функция Чебышёва.

Лемма

Лемма

${\displaystyle \theta (n)<n\cdot \ln(4)}$ для всех ${\displaystyle n\geqslant 1}$.

(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)

Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного ${\displaystyle m}$, биноминальный коэффициент ${\displaystyle {2m+1 \choose m}}$ делится на все простые числа в интервале ${\displaystyle [m+2,\;2m+1]}$. В самом деле, ${\displaystyle {2m+1 \choose m}={\frac {(2m+1)!}{m!(m+1)!}}}$, a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. Поскольку биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения

${\displaystyle {2m+1 \choose m}\geqslant \prod _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}p.}$

Взяв логарифм от обеих частей неравенства, получаем

${\displaystyle \ln {2m+1 \choose m}\geqslant \sum _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}\ln p=\theta (2m+1)-\theta (m+1).}$

С другой стороны, биноминальный коэффициент ${\displaystyle {2m+1 \choose m}}$ легко оценить сверху:

${\displaystyle {2m+1 \choose m}={\frac {{2m+1 \choose m}+{2m+1 \choose m+1}}{2}}\leqslant {\frac {\sum _{k=0}^{2m+1}{2m+1 \choose k}}{2}}=}$

${\displaystyle ={\frac {(1+1)^{2m+1}}{2}}=4^{m}.}$

Объединяя два последних неравенства, получаем

${\displaystyle \theta (2m+1)-\theta (m+1)\leqslant \ln 4^{m}=m\ln 4}$

Откуда

${\displaystyle \theta (2m+1)\leqslant \theta (m+1)+m\ln 4}$

Теперь легко доказать лемму по индукции:

• ${\displaystyle n=1}$:

${\displaystyle \theta (1)=0<1\cdot \ln(4).}$

• ${\displaystyle n=2}$:

${\displaystyle \theta (2)=\ln(2)<2\cdot \ln(4).}$

• ${\displaystyle n>2}$ и ${\displaystyle n}$ нечётно. Пусть ${\displaystyle n=2m+1}$.

${\displaystyle \theta (2m+1)\leqslant \theta (m+1)+m\ln 4<(m+1)\ln 4+m\ln 4=(2m+1)\ln 4=n\ln 4}$

• ${\displaystyle n>2}$ и ${\displaystyle n}$ чётно.

${\displaystyle \theta (n)=\theta (n-1)<(n-1)\cdot \ln(4)<n\cdot \ln(4)}$

(поскольку любое чётное число, большее 2 — составное, то ${\displaystyle \ln(n)}$ не входит в сумму ${\displaystyle \sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p)}$). Лемма доказана.

Доказательство основной теоремы

Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент ${\displaystyle 2n \choose n}$ на простые множители. Если между ${\displaystyle n}$ и ${\displaystyle 2n}$ нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.

Доказываем от противного. Допустим, что для некоторого целого ${\displaystyle n\geqslant 2}$ не существует простого числа ${\displaystyle p}$ такого, что ${\displaystyle n<p<2n}$.

Если ${\displaystyle 2\leqslant n<2048}$, то одно из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 и 2503 (каждое последующее меньше удвоенного предыдущего), назовём его ${\displaystyle p}$, удовлетворяет неравенству ${\displaystyle n<p<2n}$. Следовательно, ${\displaystyle n\geqslant 2048}$.

Оценим ${\displaystyle 2n \choose n}$.

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}.}$

Поскольку ${\displaystyle {2n \choose n}}$ — максимальный член суммы, мы имеем:

${\displaystyle {\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}.}$

Определение R(p, n) и его оценка сверху

Пускай ${\displaystyle R(p,\;n)}$ — степень ${\displaystyle p}$ в разложении ${\displaystyle {2n \choose n}}$ на простые множители.

${\displaystyle {2n \choose n}=\prod _{p}{p^{R(p,\;n)}}.}$

Поскольку ${\displaystyle n!}$ для каждого ${\displaystyle j}$ имеет ровно ${\displaystyle \left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$ сомножителей, делящихся на ${\displaystyle p^{j}}$, в разложении ${\displaystyle n!}$ на простые множители ${\displaystyle p}$ входит в степени ${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$. Поэтому

${\displaystyle R(p,\;n)=\sum _{j=1}^{\infty }\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\sum _{j=1}^{\infty }\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right).}$

Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.

Величина: каждое слагаемое ${\displaystyle \left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$ может быть или 0, или 1 (в зависимости от дробной части ${\displaystyle {\frac {n}{p^{j}}}}$ : если она меньше ${\displaystyle {\frac {1}{2}}}$, слагаемое равно 0, а если ${\displaystyle {\frac {1}{2}}}$ или больше, то 1).

Количество: все слагаемые с ${\displaystyle j>{\frac {\ln(2n)}{\ln(p)}}}$ равны нулю, потому что для них ${\displaystyle {\frac {2n}{p^{j}}}<1}$. Поэтому только ${\displaystyle \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }$ первых слагаемых имеют шансы быть ненулевыми.

Итак, ${\displaystyle R(p,\;n)}$ — сумма ${\displaystyle \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }$ слагаемых, каждое из которых равно 0 или 1. Следовательно,

${\displaystyle R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor .}$

Оценка ${\displaystyle p^{R(p,\;n)}}$

Оценим теперь ${\displaystyle p^{R(p,n)}}$.

${\displaystyle p^{R(p,\;n)}=\exp \left(R(p,\;n)\ln p\right)\leqslant \exp \left(\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln p\right)\leqslant 2n.}$

Это была оценка для любых ${\displaystyle p}$. Но гораздо лучшую оценку можно получить для ${\displaystyle {\sqrt {2n}}<p\leqslant 2n}$. Для таких ${\displaystyle p}$, количество слагаемых ${\displaystyle \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }$ равно 1, то есть в нашей сумме всего одно слагаемое:

${\displaystyle R(p,\;n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor .}$

Если это слагаемое равно 1, то ${\displaystyle p^{R(p,\;n)}=p}$ . А если оно равно 0, то ${\displaystyle p^{R(p,\;n)}=1}$.

В каком интервале могут находиться простые делители?

А теперь посмотрим, в каком интервале находятся простые делители. ${\displaystyle {2n \choose n}}$ не имеет простых делителей ${\displaystyle p}$ таких, что:

• ${\displaystyle 2n<p}$, потому что ${\displaystyle R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor =0}$.
• ${\displaystyle n<p\leqslant 2n}$, потому что мы предположили, что в этом интервале нет простых чисел.
• ${\displaystyle {\frac {2n}{3}}<p\leqslant n}$, потому что ${\displaystyle p>{\sqrt {2n}}}$ (так как ${\displaystyle n\geqslant 5}$), что даёт нам ${\displaystyle R(p,\;n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor =2-2=0}$.

Получается, что у ${\displaystyle {2n \choose n}}$ нет простых делителей, больших чем ${\displaystyle {\frac {2n}{3}}}$.

Перемножение всех ${\displaystyle p^{R(p,\;n)}}$

Теперь оценим произведение ${\displaystyle p^{R(p,\;n)}}$ по всем простым делителям ${\displaystyle p}$ числа ${\displaystyle {2n \choose n}}$ . Для делителей, не больших ${\displaystyle {\sqrt {2n}}}$, произведение не превышает ${\displaystyle {(2n)}^{\sqrt {2n}}}$ . А для простых делителей, больших ${\displaystyle {\sqrt {2n}}}$, оно не превышает ${\displaystyle \prod _{p\in \mathbb {P} ;\,p\leqslant 2n/3}p=\exp \left(\theta \left({\frac {2n}{3}}\right)\right)}$.

Поскольку ${\displaystyle {2n \choose n}}$ равен произведению ${\displaystyle p^{R(p,\;n)}}$ по всем простым ${\displaystyle p}$, мы получаем:

${\displaystyle {\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}\leqslant (2n)^{\sqrt {2n}}\exp \left(\theta \left({\frac {2n}{3}}\right)\right).}$

Используя нашу лемму ${\displaystyle \theta (n)<n\cdot \ln(4)}$:

${\displaystyle {\frac {4^{n}}{2n+1}}<(2n)^{\sqrt {2n}}4^{\frac {2n}{3}}.}$

Поскольку ${\displaystyle (2n+1)<(2n)^{2}}$:

${\displaystyle 4^{\frac {n}{3}}<(2n)^{2+{\sqrt {2n}}}.}$

Кроме того, ${\displaystyle 2\leqslant {\frac {\sqrt {2n}}{3}}}$ (поскольку ${\displaystyle n\geqslant 18}$):

${\displaystyle 4^{\frac {n}{3}}<(2n)^{{\frac {4}{3}}{\sqrt {2n}}}.}$

Логарифмируя обе части, получаем

${\displaystyle {\sqrt {2n}}\ln(2)<4\cdot \ln(2n).}$

Делая подстановку ${\displaystyle 2^{2t}=2n}$:

${\displaystyle {\frac {2^{t}}{t}}<8}$

Это даёт нам ${\displaystyle t<6}$ и противоречие:

${\displaystyle n={\frac {2^{2t}}{2}}<{\frac {2^{2\cdot 6}}{2}}=2048.}$

Следовательно, наше допущение было неверно.

Ч.т.д.