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

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

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

Обобщения

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

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

Гипотезы

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

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

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

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

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

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

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

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

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

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

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

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

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

Лемма

Лемма

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

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

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

$(\genfrac{}{}{0ex}{}{2m+1}{m})⩾\prod _{p\in \mathbb{P};m+2⩽p⩽2m+1}p.$

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

$\ln (\genfrac{}{}{0ex}{}{2m+1}{m})⩾\sum _{p\in \mathbb{P};m+2⩽p⩽2m+1}\ln p=\theta (2m+1)-\theta (m+1).$

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

$(\genfrac{}{}{0ex}{}{2m+1}{m})=\frac{(\genfrac{}{}{0ex}{}{2m+1}{m})+(\genfrac{}{}{0ex}{}{2m+1}{m+1})}{2}⩽\frac{\sum _{k=0}^{2m+1}(\genfrac{}{}{0ex}{}{2m+1}{k})}{2}=$

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

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

$\theta (2m+1)-\theta (m+1)⩽\ln 4^m=m\ln 4$

Откуда

$\theta (2m+1)⩽\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)⩽\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⩽n}\ln (p)$). Лемма доказана.

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

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

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

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

Оценим $(\genfrac{}{}{0ex}{}{2n}{n})$.

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

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

$\frac{4^n}{2n+1}⩽(\genfrac{}{}{0ex}{}{2n}{n}).$

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

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

$(\genfrac{}{}{0ex}{}{2n}{n})=\prod _p{p}^{R(p,n)}.$

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

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

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

Величина: каждое слагаемое $\lfloor \frac{2n}{p^j}\rfloor -2\lfloor \frac{n}{p^j}\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$. Поэтому только $\lfloor \frac{\ln (2n)}{\ln (p)}\rfloor$ первых слагаемых имеют шансы быть ненулевыми.

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

$R(p,n)⩽\lfloor \frac{\ln (2n)}{\ln (p)}\rfloor .$

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

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

$p^{R(p,n)}=\exp (R(p,n)\ln p)⩽\exp (\lfloor \frac{\ln (2n)}{\ln (p)}\rfloor \ln p)⩽2n.$

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

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

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

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

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

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

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

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

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

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

$\frac{4^n}{2n+1}⩽(\genfrac{}{}{0ex}{}{2n}{n})⩽(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⩽\frac{\sqrt{2n}}{3}$ (поскольку $n⩾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.$

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

Литература

• Шаблон:Книга
• В. И. Зенкин. Распределение простых чисел. Элементарные методы. Калининград, 2008.