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

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

Обобщения

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

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

Гипотезы

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

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

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

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

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

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

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

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

• ${\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 .}$

Оценка 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}}}$ .

Перемножение всех 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.}$

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

Примечания

Литература

• Простое число // / Сост. А. П. Савин. — М. : Педагогика , 1985. — С. -263. — 352 с.