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

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

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

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

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

Содержание

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

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

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

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

Обозначим множество простых чисел через \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 сомножителей, делящихся на pj, в разложении 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

Оценка pR(p,n)

Оценим теперь pR(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, то pR(p,n) = p . А если оно равно 0, то pR(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}.

Перемножение всех pR(p,n)

Теперь оценим произведение pR(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} равен произведению pR(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)

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

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

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

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

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

ч.т.д.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home