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

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что для любого натурального $n\geqslant 2$ найдётся простое число $p$ в интервале $(n;2n).$

Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном (проверившим её до $n=3\cdot 10^{6}$) и доказан в 1852 году Чебышёвым. Рамануджан в 1919 году нашёл более простое доказательство и доказал, что количество простых чисел в интервале $(n;2n)$ можно ограничить снизу неубывающей последовательностью, которая стремится к бесконечности, такой что в простых числах Рамануджана достигается равенство. Эрдёш в 1932 году ещё более упростил доказательство.

Обобщения

Обобщением постулата Бертрана можно считать теорему о том, что для $n\geqslant 2k$ среди чисел $n-k+1,\dots ,n-1,n$ всегда существует число с простым делителем больше $k$. Это утверждение было доказано Сильвестром в 1892 году. При $n=2k$ оно даёт гипотезу Бертрана как частный случай.

Из теоремы о распределении простых чисел следует, что для любого $\varepsilon >0$ существует число $n_{0}$ такое, что для любых $n\geqslant n_{0}$ существует простое число $p$, удовлетворяющее $n<p<(1+\varepsilon )n$. Более того, для фиксированного $\varepsilon$ количество простых чисел в этом интервале стремится к бесконечности с ростом $n$. В частности, например, при $n\geqslant 25$ всегда найдётся простое число между $n$ и ${\frac {6}{5}}n$.

Гипотезы

Гипотеза Лежандра гласит, что для любого $n\geqslant 2$ найдётся простое число $p$ в интервале $n^{2}<p<(n+1)^{2}$. Гипотеза Оппермана и гипотеза Андрицы задают такой же порядок роста интервала, включающего хотя бы одно простое число.

Наиболее сильной является гипотеза Крамера, которая гласит, что

$p_{n+1}-p_{n}=O(\ln ^{2}p_{n}).$

Все эти гипотезы не доказаны и не опровергнуты.

Доказательство

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

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

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

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

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

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

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

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

Лемма

Лемма

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

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

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

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

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

$\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).$

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

${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}}=$

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

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

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

Откуда

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

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

• $n=1$:

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

• $n=2$:

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

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

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

• $n>2$ и $n$ чётно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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).$

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

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

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

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

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

Оценка p^R(p, n)

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

$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.$

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

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

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

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

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

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

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

Перемножение всех p^R(p, n)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Простое число // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 262-263. — 352 с.
• В. И. Зенкин. Распределение простых чисел. Элементарные методы. Калининград, 2008.