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

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что Для любого натурального n ≥ 2 найдётся простое число p в интервале n \textless p \textless 2n. Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном (проверившим её до ) и доказан в 1852 году Чебышёвым. Рамануджан в 1920 году нашёл более простое доказательство, а Эрдёш в 1932 году — ещё более простое.

Обобщения


 Похожая, но недоказанная гипотеза Лежандра гласит, что для любого n2 найдётся простое число p в интервале n2<p<(n+1)2.
 Обобщением постулата Бертрана можно считать теорему о том, что для n2k среди чисел nk+1,,n1,n всегда существует число с простым делителем больше k. Это утверждение было доказано Сильвестром в 1892 году. При n=2k оно даёт гипотезу Бертрана как частный случай.
 Из теоремы о распределении простых чисел следует, что для любого ε>0 существует число n0 такое, что для любых nn0 существует простое число p, удовлетворяющее n<p<(1+ε)n. Более того, для фиксированного ε количество простых чисел в этом интервале стремится к бесконечности с ростом n. В частности, например, при n25 всегда найдётся простое число между n и (1+1/5)n.

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


 \{2\} =


=(1+1)2m+12=4m.

 Объединяя два последних неравенства, получаем


θ(2m+1)θ(m+1)ln4m=mln4

 Откуда


θ(2m+1)θ(m+1)+mln4

 Теперь легко доказать лемму по индукции:

  • n = 1:



θ(1)=0<1ln(4)


  • n = 2:



θ(2)=ln(2)<2ln(4)


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



θ(2m+1)θ(m+1)+mln4<(m+1)ln4+mln4=(2m+1)ln4=nln4


  • n \textgreater 2 и n чётно.



θ(n)=θ(n1)<(n1)ln(4)<nln(4)

 (поскольку любое чётное число, большее 2 — составное, то ln(n) не входит в сумму pP;pnln(p)). Лемма доказана.

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


 Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент (2nn) на простые множители. Если между n и 2n нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.
 Доказываем от противного. Допустим, что для некоторого целого n ≥ 2 не существует простого числа p такого, что n \textless p \textless 2n.
 Если 2 ≤ n \textless 2048, то одно из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 и 2503 (каждое последующее меньше удвоенного предыдущего), назовём его p, удовлетворяет неравенству n \textless p \textless 2n. Следовательно, n ≥ 2048.
 Оценим (2nn).
4n=(1+1)2n=k=02n(2nk)

 Поскольку (2nn) - максимальный член суммы, мы имеем:
4n2n+1(2nn)


agraphОпределение R(p,n) и его оценка сверху
 Пускай R(p,n) - степень p в разложении (2nn) на простые множители.


(2nn)=ppR(p,n)

 Поскольку n! для каждого j имеет ровно npj сомножителей, делящихся на pj, в разложении n! на простые множители p входит в степени j=1npj. Поэтому
R(p,n)=j=12npj2j=1npj=j=1(2npj2npj)

 Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.
Величина: каждое слагаемое 2npj2npj может быть или 0, или 1 (в зависимости от дробной части npj : если она меньше 12, слагаемое равно 0, а если 12 или больше, то 1).
Количество: все слагаемые с j>ln(2n)ln(p) равны нулю, потому что для них 2npj<1. Поэтому только ln(2n)ln(p) первых слагаемых имеют шансы быть ненулевыми.
 Итак, R(p,n) - сумма ln(2n)ln(p) слагаемых, каждое из которых равно 0 или 1. Следовательно,
R(p,n)ln(2n)ln(p)


agraphОценка pR(p,n)
 Оценим теперь pR(p,n).
pR(p,n)=exp(R(p,n)lnp)exp(ln(2n)ln(p)lnp)2n

 Это была оценка для любых p. Но гораздо лучшую оценку можно получить для 2n<p2n. Для таких p, количество слагаемых ln(2n)ln(p) равно 1, то есть в нашей сумме всего одно слагаемое:
R(p,n)=2np2np
Если это слагаемое равно 1, то pR(p,n)=p . А если оно равно 0, то pR(p,n)=1 .

agraphВ каком интервале могут находиться простые делители?
 А теперь посмотрим, в каком интервале находятся простые делители. (2nn) не имеет простых делителей p таких, что:

  • 2n \textless p, потому что R(p,n)ln(2n)ln(p)=0.
  • $n

  • $\frac {2n} {3}

    \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$.


 Получается, что у (2nn) нет простых делителей, больших чем 2n3.

agraphПеремножение всех pR(p,n)
 Теперь оценим произведение pR(p,n) по всем простым делителям p числа (2nn) . Для делителей, не больших 2n, произведение не превышает (2n)2n . А для простых делителей, больших 2n, оно не превышает pP;p2n/3p=exp(θ(2n3)).
 Поскольку (2nn) равен произведению pR(p,n) по всем простым p, мы получаем:
4n2n+1(2nn)(2n)2nexp(θ(2n3))

 Используя нашу лемму θ(n)<nln(4):
4n2n+1<(2n)2n42n3

 Поскольку (2n+1)<(2n)2:
4n3<(2n)2+2n

 Кроме того, 22n3 (поскольку n18):
4n3<(2n)432n

 Логарифмируя обе части, получаем
2nln(2)<4ln(2n)

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

 Это даёт нам t \textless 6 и противоречие:
n=22t2<2262=2048

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