Теория чисел/Постулат Бертрана

Постулат Бертрана (теорема Бертрана — Чебышёва, теорема Чебышёва) — в теории чисел утверждение о том, что при натуральном n > 3 между числами n и (2n − 2) существует по крайней мере одно простое число. Постулат был сформулирован как гипотеза в 1845 году Бертраном, который проверил его до $n=3\cdot 10^{6}$.

Другие формулировки:

• при любом n > 1 имеется простое число, принадлежащее интервалу (n, 2n)
• для n ≥ 1: p_n+1 < 2p_n, p_n
• для n ≥ 1: π(2n) − π(n) ≥ 1

В 1852 году постулат был доказан Чебышёвым. По другим источникам - в 1850 году.

В дальнейшем несколько математиков предложили более простые варианты доказательства:

• Рамануджан в 1919 году

• Эрдёш в 1932 году

• Мозер в 1949 году

• Стечкин в 1968 году
• Генри Рикардо и Ёсихиро Танака в 2005 году, доказательство основано на гипотезе Гольдбаха, но бинарная проблема Гольдбаха в свою очередь пока не доказана

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

Доказательство Эрдёша^{[источник?]}

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

• ${a \choose b}$ — биномиальный коэффициент или число сочетаний из $a$ по $b$.
• $\left\lfloor x\right\rfloor$ — целая часть $x$.

Обозначим множество простых чисел через $\mathbb {P}$ и определим $\theta (n)$ как сумму логарифмов простых чисел, не превышающих $n$:

$\theta (n)=\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p).$

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

Эта функция называется $\theta$-функция Чебышёва.

Лемма

$\theta (n)<n\cdot \ln(4)$ для всех $n\geqslant 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}\geqslant \prod _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 2m+1}p.$

Взяв логарифм от обеих частей неравенства, получаем

$\ln {2m+1 \choose m}\geqslant \sum _{p\in \mathbb {P} ;\,m+2\leqslant p\leqslant 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}}\leqslant {\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)\leqslant \ln 4^{m}=m\ln 4$

Откуда

$\theta (2m+1)\leqslant \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$ нечётно. Пусть $n=2m+1$.

$\theta (2m+1)\leqslant \theta (m+1)+m\ln 4<(m+1)\ln 4+m\ln 4=(2m+1)\ln 4=n\ln 4$

• $n>2$ и $n$ чётно.

$\theta (n)=\theta (n-1)<(n-1)\cdot \ln(4)<n\cdot \ln(4)$

(поскольку любое чётное число, большее 2 составное, то $\ln(n)$ не входит в сумму $\sum _{p\in \mathbb {P} ;\,p\leqslant n}\ln(p)$). Лемма доказана.

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

Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент $2n \choose n$ на простые множители. Если между $n$ и $2n$ нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.

Доказываем от противного. Допустим, что для некоторого целого $n\geqslant 2$ не существует простого числа $p$ такого, что $n<p<2n$.

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

Оценим $2n \choose n$.

$4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}.$

Поскольку ${2n \choose n}$ — максимальный член суммы, мы имеем:

${\frac {4^{n}}{2n+1}}\leqslant {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)\leqslant \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)\leqslant \exp \left(\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln p\right)\leqslant 2n.$

Это была оценка для любых $p$. Но гораздо лучшую оценку можно получить для ${\sqrt {2n}}<p\leqslant 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)\leqslant \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor =0$.
• $n<p\leqslant 2n$, потому что мы предположили, что в этом интервале нет простых чисел.
• ${\frac {2n}{3}}<p\leqslant n$, потому что при $p>{\sqrt {2n}}$ (так как $n\geqslant 5$) имеем $R(p,\;n)\leq 1$, что даёт нам $R(p,\;n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor <\left\lfloor {\frac {2n}{\frac {2n}{3}}}\right\rfloor -2\left\lfloor {\frac {n}{n}}\right\rfloor =3-2=1,$ откуда $R(p,\;n)=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} ;\,p\leqslant 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}}\leqslant {2n \choose n}\leqslant (2n)^{\sqrt {2n}}\exp \left(\theta \left({\frac {2n}{3}}\right)\right).$

Используя нашу лемму $\theta (n)<n\cdot \ln(4)$:

${\frac {4^{n}}{2n+1}}<(2n)^{\sqrt {2n}}4^{\frac {2n}{3}}.$

Поскольку $(2n+1)<(2n)^{2}$:

$4^{\frac {n}{3}}<(2n)^{2+{\sqrt {2n}}}.$

Кроме того, $2\leqslant {\frac {\sqrt {2n}}{3}}$ (поскольку $n\geqslant 18$):

$4^{\frac {n}{3}}<(2n)^{{\frac {4}{3}}{\sqrt {2n}}}.$

Логарифмируя обе части, получаем

${\sqrt {2n}}\ln(2)<4\cdot \ln(2n).$

Делая подстановку $2^{2t}=2n$:

${\frac {2^{t}}{t}}<8$

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

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

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

Что и требовалось доказать.

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

1. Если 𝑛 < 𝑝 ⩽ 2⁢𝑛, то 𝑝 встречается ровно один раз в ${2n \choose n}$
2. Если 𝑛 ⩾ 3, ${\frac {2n}{3}}$ < 𝑝 < 𝑛, то 𝑝 не встречается в ${2n \choose n}$
3. Если 𝑝² > 2⁢𝑛, то 𝑝 встречается не более одного раза в${2n \choose n}$
4. Если 2^𝛼 ⩽ 2⁢𝑛 < 2^𝛼+1, то 𝑝 встречается не более 𝛼 раз раз в ${2n \choose n}$

Если 2^𝛼 < 2⁢𝑛 ⩽ 2^𝛼+1, то предположим, не существует простого числа 𝑝, такого что 𝑛 < 𝑝 < 2⁢𝑛, (1)

тогда

${2n \choose n}$ ⩽ ${2a_{1} \choose a_{1}}$${2a_{2} \choose a_{2}}$...${2 \choose 1}$$\left({2a_{k} \choose a_{k}}{2a_{k+1}) \choose a_{k+1}}...{2 \choose 1}\right)^{\alpha }$, (2)

где a₁ = $\left[{n+1 \over 3}\right]$, k = $\left[{{\alpha }+1 \over 2}\right]$и a_i = $\left[{a_{i-1}+1 \over 3}\right]$ для i = 2, 3, ... .

Согласно 1, 2, 3 и (1), каждое простое число, которое появляется слева от (2) появляется также справа; и те простые числа, которые слева встречаются с кратностью больше, чем 1, появляются справа с кратностью не менее 2⁢𝛼 + 1, что согласно 4 не меньше кратности, с которой они появляются в левой части.

С другой стороны, очевидно, что

2⁢𝑛 > 2⁢𝑎₁ + 2⁢𝑎₂ + ⋯ + 2 + 𝛼 ⁢(2⁢𝑎_𝑘 + 2⁢𝑎_𝑘+1 + ⋯ + 2) (3)

для 𝑛 >2¹¹. Следовательно, неравенство в (2) должно быть обратным. Таким образом, для 𝑛 >2¹¹, мы получаем противоречие, которое доказывает постулат Бертрана для этих значений 𝑛.

Что и требовалось доказать.

Доказательство с учетом гипотезы Гольдбаха

Примерно в 2005 году Генри Рикардо и Ёсихиро Танака (Ricardo 05) заметили, что постулат Бертрана следует из гипотезы Гольдбаха.

Если гипотеза Гольдбаха верна, то существуют простые числа p₁ и p₂ такие, что 2n = p₁ + p₂. Мы должны иметь ввиду, что по крайней мере одно из p₁ и p₂ больше или равно n. Без потери общности предположим, что p₁ обладает этим свойством.

Если n не является простым числом, то следует, что n < p₁ < 2n, как и требуется доказать. Предположим вместо этого, что n является простым числом. Тогда n + 1 является составным числом, поскольку оно должно быть кратно 2.

Еще раз по гипотезе Гольдбаха, существуют простые числа p'₁ и p'₂ такие, что 2(n + 1) = p'₁ + p'₂. Как указано выше, по крайней мере одно из p'₁ и p'₂ должно быть больше или равно n + 1. Не умаляя общности, предположим, что p'₁ обладает этим свойством.

Тогда, поскольку n + 1 не является простым числом, мы получаем, что n + 1 < p'₁ < 2(n + 1), а значит, что n < p'₁ < 2(n + 1)

Теперь p'₁ не равно 2n + 1, поскольку это означало бы, что p'₂ = 1, а это невозможно. Более того, p'₁ не равно 2n, поскольку 2n не является простым числом. Отсюда следует, что p'₁ < 2n.

Что и требовалось доказать.