Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что для любого натурального
найдётся простое число
в интервале
Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном (проверившим её до
) и доказан в 1852 году[1] Чебышёвым.
Рамануджан в 1919 году нашёл более простое доказательство и доказал, что количество простых чисел в интервале
можно ограничить снизу неубывающей последовательностью, которая стремится к бесконечности, такой что в простых числах Рамануджана достигается равенство. Эрдёш в 1932 году ещё более упростил доказательство.
Обобщением постулата Бертрана можно считать теорему о том, что для
среди чисел
всегда существует число с простым делителем больше
. Это утверждение было доказано Сильвестром в 1892 году. При
оно даёт гипотезу Бертрана как частный случай.
Из теоремы о распределении простых чисел следует, что для любого
существует число
такое, что для любых
существует простое число
, удовлетворяющее
. Более того, для фиксированного
количество простых чисел в этом интервале стремится к бесконечности с ростом
[2]. В частности, например, при
всегда найдётся простое число между
и
[3].
Гипотеза Лежандра гласит, что для любого
найдётся простое число
в интервале
. Гипотеза Оппермана и гипотеза Андрицы задают такой же порядок роста интервала, включающего хотя бы одно простое число.
Наиболее сильной является гипотеза Крамера, которая гласит, что
![{\displaystyle p_{n+1}-p_{n}=O(\ln ^{2}p_{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e61e005654f4217c83df5c761879172fd2977a)
Все эти гипотезы не доказаны и не опровергнуты.
Здесь мы приводим доказательство, предложенное Эрдёшем.
В доказательстве мы используем следующие обозначения:
Обозначим множество простых чисел через
и определим
как сумму логарифмов простых чисел, не превышающих
:
![{\displaystyle \theta (n)=\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3774aeb391186358cf7c1d234bd754f52fdb0227)
Например,
.
Эта функция называется
-функция Чебышёва.
Лемма
для всех
.
(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)
Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного
, биноминальный коэффициент
делится на все простые числа в интервале
. В самом деле,
, a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. Поскольку биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения
![{\displaystyle {2m+1 \choose m}\geqslant \prod _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}p.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37eb6f2ea082745c4fbf0ae14fbc34cc9a0e8f65)
Взяв логарифм от обеих частей неравенства, получаем
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/782e95fc7b068559f25ad1ab6253af696d1db008)
С другой стороны, биноминальный коэффициент
легко оценить сверху:
![{\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}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a75226de64cc3c67a72bb538959f4897a7e15bda)
![{\displaystyle ={\frac {(1+1)^{2m+1}}{2}}=4^{m}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54e8b6ce6a2bff67a3637bf082a0a19a635a1cf1)
Объединяя два последних неравенства, получаем
![{\displaystyle \theta (2m+1)-\theta (m+1)\leqslant \ln 4^{m}=m\ln 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d08be55445f5d21c5356749a36dfbfe88d64c86d)
Откуда
![{\displaystyle \theta (2m+1)\leqslant \theta (m+1)+m\ln 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0eb3039fe8f42042154290e15cf8b0047508ae4d)
Теперь легко доказать лемму по индукции:
:
![{\displaystyle \theta (1)=0<1\cdot \ln(4).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8440ffea9d2d9de03f404ac9184e26af31378f6b)
:
![{\displaystyle \theta (2)=\ln(2)<2\cdot \ln(4).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f15f5b423eda9de17806a5187caa7cc82eb0ee3)
и
нечётно. Пусть
.
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64118346d6846461464dcdef751a1abfe8d3c44c)
и
чётно.
![{\displaystyle \theta (n)=\theta (n-1)<(n-1)\cdot \ln(4)<n\cdot \ln(4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5dc2d82f71a900789705f90b7a98d5f3bc72706)
(поскольку любое чётное число, большее 2 составное, то
не входит в сумму
). Лемма доказана.
Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент
на простые множители. Если между
и
нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.
Доказываем от противного. Допустим, что для некоторого целого
не существует простого числа
такого, что
.
Если
, то одно из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 и 2503 (каждое последующее меньше удвоенного предыдущего), назовём его
, удовлетворяет неравенству
. Следовательно,
.
Оценим
.
![{\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e431a380f6937b977d8b6029652cbcd19872fba)
Поскольку
— максимальный член суммы, мы имеем:
![{\displaystyle {\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45fde1ef75ebe358cd9da051bddf35b4aef6b62b)
Пускай
— степень
в разложении
на простые множители.
![{\displaystyle {2n \choose n}=\prod _{p}{p^{R(p,\;n)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b46b989bb1c481c0e37e238fac7e1c96f5e7a31e)
Поскольку
для каждого
имеет ровно
сомножителей, делящихся на
, в разложении
на простые множители
входит в степени
. Поэтому
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f64af6548e8f1e85af28c8ea514c85401c27e6cd)
Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.
Величина: каждое слагаемое
может быть или 0, или 1 (в зависимости от дробной части
: если она меньше
, слагаемое равно 0, а если
или больше, то 1).
Количество: все слагаемые с
равны нулю, потому что для них
. Поэтому только
первых слагаемых имеют шансы быть ненулевыми.
Итак,
— сумма
слагаемых, каждое из которых равно 0 или 1. Следовательно,
![{\displaystyle R(p,\;n)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68915aac17836979ef5b74a816a1c95cb83c857e)
Оценим теперь
.
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/146400d8834cd4b6d0b275fe98749d39bb6b0c7f)
Это была оценка для любых
. Но гораздо лучшую оценку можно получить для
. Для таких
, количество слагаемых
равно 1, то есть в нашей сумме всего одно слагаемое:
![{\displaystyle R(p,\;n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d76949a63cf24a95d4b2805e9cd85e8edc96a18)
Если это слагаемое равно 1, то
. А если оно равно 0, то
.
А теперь посмотрим, в каком интервале находятся простые делители.
не имеет простых делителей
таких, что:
, потому что
.
, потому что мы предположили, что в этом интервале нет простых чисел.
, потому что при
(так как
) имеем
, что даёт нам
откуда
.
Получается, что у
нет простых делителей, больших чем
.
Теперь оценим произведение
по всем простым делителям
числа
. Для делителей, не больших
, произведение не превышает
. А для простых делителей, больших
, оно не превышает
.
Поскольку
равен произведению
по всем простым
, мы получаем:
![{\displaystyle {\frac {4^{n}}{2n+1}}\leqslant {2n \choose n}\leqslant (2n)^{\sqrt {2n}}\exp \left(\theta \left({\frac {2n}{3}}\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4459b3f03383eaec35475e3795146f0a8b380215)
Используя нашу лемму
:
![{\displaystyle {\frac {4^{n}}{2n+1}}<(2n)^{\sqrt {2n}}4^{\frac {2n}{3}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a18f226606dd8e64c9c9b84f20e241b4b07f653)
Поскольку
:
![{\displaystyle 4^{\frac {n}{3}}<(2n)^{2+{\sqrt {2n}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b71276b09b2820161f856ed486493025b23f085)
Кроме того,
(поскольку
):
![{\displaystyle 4^{\frac {n}{3}}<(2n)^{{\frac {4}{3}}{\sqrt {2n}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afad54d5abd22a02d26068237675bf4f351d6d7f)
Логарифмируя обе части, получаем
![{\displaystyle {\sqrt {2n}}\ln(2)<4\cdot \ln(2n).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc7cc4b9584804018927b82a8b230513dd5c8107)
Делая подстановку
:
![{\displaystyle {\frac {2^{t}}{t}}<8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f174ab11b97acaf04b00fdb88446c461990dfefe)
Это даёт нам
и противоречие:
![{\displaystyle n={\frac {2^{2t}}{2}}<{\frac {2^{2\cdot 6}}{2}}=2048.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54fac20f186293c218367a73843f0aa2ef9df8a7)
Следовательно, наше допущение было неверно. Что и требовалось доказать