Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

Для любого натурального 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)

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

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

Лемма Править

Лемма

 \theta(n) < n \cdot \ln(4) для всех  n\ge 1 .

(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».) Шаблон:Доказательство

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

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

Поскольку  {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)

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

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

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

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

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

ч.т.д.pl:Twierdzenie Czebyszewa simple:Bertrand's postulate sl:Bertrandova domneva sr:Бертранов постулат vi:Định đề Bertrand

Викия-сеть

Случайная вики