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

У этого термина существуют и другие значения, см. Бертран.

Постулат Бертрана, теорема Бертрана — Чебышева или теорема Чебышева гласит, что

Для любого натурального n ≥ 2 найдётся простое число p в интервале n < p < 2n.

Такая гипотеза была выдвинута в 1845 году французским математиком Бертраном (проверившим её до n=3000000) и доказана в 1850 году Чебышевым. Рамануджан в 1920 году нашёл более простое доказательство, а Эрдёш в 1932 году — ещё более простое.

Похожая, но недоказанная гипотеза Лежандра гласит, что для любого n ≥ 2 найдётся простое число p в интервале n² < p < (n+1)².

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

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

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

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

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

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

$\theta(n) = \sum_{p\in\Bbb{P};\, p\leq n} \ln (p)$

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

Эта функция называется θ-функция Эрдёша.

Лемма

Лемма

$\theta(n) < n \cdot \ln(4)$ для всех $n\ge 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} \ge \prod_{p\in\Bbb{P};\, m+2 < p \le 2m+1} p$

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

$\ln {2m+1 \choose m} \ge \sum_{p\in\Bbb{P};\, m+2 < p \le 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} \le \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) \le \ln 4^m = m \ln 4$

Откуда

$\theta(2m+1) \le \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 чётно.

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

(здесь мы используем, что чётное число, большее 2 - составное и поэтому не входит в сумму $\sum_{p\in\Bbb{P};\, p\leq x} \ln (p)$).

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

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

Лемма доказана.

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

Теперь переходим к доказательству самого постулата. Основная идея доказательства - разложить биноминальный коэффициент $2n \choose 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.

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

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

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

$\frac {4^n} {2n+1} \le {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) \le \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 ) \le \exp \left ( \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor \ln p \right ) \le 2n$

Это была оценка для любых p. Но гораздо лучшую оценку можно получить для $\sqrt {2n} < p \le 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) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor = 0$.
• $n<p \le 2n$, потому что мы предположили, что в этом интервале нет простых чисел.
• $\frac {2n} {3} <p \le n$, потому что $p > \sqrt{2n}$ (т.к. $n \ge 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} }^{\frac {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} \le {2n \choose n} \le (2n)^\sqrt{2n} \exp \left ( \theta \left ( \frac {2n} {3} \right ) \right )$

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

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

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

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

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

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

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

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

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

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

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

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

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

ч.т.д.