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

Материал из Википедии — свободной энциклопедии

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

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

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

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

Содержание

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)$

Например, $θ(10) = ln2 + ln3 + ln5 + ln7$ .

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

[править] Лемма

Лемма

$\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+1 < p \le 2m+1} p$

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

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

Oценим $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 )$ .