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

Постулат Бертрана, теорема Бертрана — Чебышёва илитеорема Чебышёва гласит, что Для любого натурального n ≥2 найдётся простое число p в интервале n \textlessp \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 \textlessp \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. \}\}