Постулат Бертрана | это... Что такое Постулат Бертрана? (original) (raw)

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

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

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

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

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

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

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

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

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

Обозначим множество простых чисел через $\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 нечётно. Пусть 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 < 2_n_.

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