Постулат Бертрана - NiNa.Az

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что для любого натурального ${\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)\leq 1}$, что даёт нам ${\displaystyle R(p,\;n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor <\left\lfloor {\frac {2n}{\frac {2n}{3}}}\right\rfloor -2\left\lfloor {\frac {n}{n}}\right\rfloor =3-2=1,}$ откуда ${\displaystyle R(p,\;n)=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.}$

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

Примечания

1. Энциклопедический словарь юного математика, 1985.
2. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, p. 494.
3. J. Nagura. On the interval containing at least one prime number // Proceedings of the Japan Academy, Series A. — 1952. — Vol. 28. — P. 177–181. — doi:10.3792/pja/1195570997.

Литература

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