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

Решена задача на простые числа

В математике постулат Бертрана (теперь теорема ) утверждает, что для каждого существует простое число, такое что . Впервые выдвинутая в 1845 году Жозефом Бертраном ^[1], она была впервые доказана Чебышевым , а более короткое , но также и продвинутое доказательство было дано Рамануджаном ^[2] . ${\displaystyle n\geq 2}$ ${\displaystyle p}$ ${\displaystyle n<p<2n}$

Следующее элементарное доказательство было опубликовано Полом Эрдёшем в 1932 году как одна из его самых ранних математических публикаций. ^[3] Основная идея состоит в том, чтобы показать, что центральные биномиальные коэффициенты должны иметь простой множитель внутри интервала , чтобы быть достаточно большими. Это достигается посредством анализа их факторизаций. ${\displaystyle (n,2n)}$

Основные шаги доказательства следующие. Во-первых, показывается, что вклад каждого простого множителя в разложение центрального биномиального коэффициента на простые числа не превышает ; затем показывается, что каждое простое число, большее, чем , появляется не более одного раза. ${\displaystyle p^{r}}$ ${\displaystyle \textstyle {\binom {2n}{n}}=(2n)!/(n!)^{2}}$ ${\displaystyle 2n}$ ${\displaystyle {\sqrt {2n}}}$

Следующий шаг — доказать, что не имеет простых множителей в интервале . Как следствие этих границ, вклад в размер исходящих от простых множителей, которые не больше , растет асимптотически как для некоторых . Поскольку асимптотический рост центрального биномиального коэффициента не меньше , вывод состоит в том, что, от противного и для достаточно большого , биномиальный коэффициент должен иметь другой простой множитель, который может лежать только между и . ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle ({\tfrac {2n}{3}},n)}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle n}$ ${\displaystyle \theta ^{\!\;n}}$ ${\displaystyle \theta <4}$ ${\displaystyle 4^{n}\!/2n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2n}$

Приведенный аргумент справедлив для всех . Остальные значения  проверяются прямой проверкой, что завершает доказательство. ${\displaystyle n\geq 427}$ ${\displaystyle n}$

Леммы в доказательстве

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

Лемма 1

Для любого целого числа мы имеем ${\displaystyle n>0}$

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}.}$

Доказательство: Применяем биномиальную теорему ,

${\displaystyle 4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}=2+\sum _{k=1}^{2n-1}{\binom {2n}{k}}\leq 2n{\binom {2n}{n}},}$

так как — наибольший член в сумме в правой части, а сумма имеет члены (включая начальный член вне суммирования). ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle 2n}$ ${\displaystyle 2}$

Лемма 2

Для фиксированного простого числа определим как p -адический порядок числа , то есть наибольшее натуральное число , которое делит . ${\displaystyle p}$ ${\displaystyle R=R(n,p)}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle r}$ ${\displaystyle p^{r}}$ ${\displaystyle {\tbinom {2n}{n}}}$

Для любого простого числа , . ${\displaystyle p}$ ${\displaystyle p^{R}\leq 2n}$

Доказательство: Показатель степени в определяется формулой Лежандра ${\displaystyle p}$ ${\displaystyle n!}$

${\displaystyle \sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \!,}$

так

${\displaystyle R=\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)}$

Но каждый член последнего суммирования должен быть либо нулём (если ), либо единицей (если ), а все члены с равны нулю. Поэтому, ${\displaystyle n/p^{j}{\bmod {1}}<1/2}$ ${\displaystyle n/p^{j}{\bmod {1}}\geq 1/2}$ ${\displaystyle j>\log _{p}(2n)}$

${\displaystyle R\leq \log _{p}(2n),}$

и

${\displaystyle p^{R}\leq p^{\log _{p}(2n)}=2n.}$

Лемма 3

Если — нечетное простое число и , то ${\displaystyle p}$ ${\displaystyle {\frac {2n}{3}}<p\leq n}$ ${\displaystyle R(n,p)=0.}$

Доказательство: В числителе выражения есть ровно два множителя , происходящие от двух членов и в , а также два множителя в знаменателе от одной копии члена в каждом из двух множителей . Все эти множители сокращаются, не оставляя множителей в . (Ограничение в предварительных условиях леммы гарантирует, что слишком велико, чтобы быть членом числителя, а предположение о нечетности необходимо для того, чтобы гарантировать, что вносит только один множитель в числитель.) ${\displaystyle p}$ ${\displaystyle {\tbinom {2n}{n}}=(2n)!/(n!)^{2}}$ ${\displaystyle p}$ ${\displaystyle 2p}$ ${\displaystyle (2n)!}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle n!}$ ${\displaystyle p}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle p}$ ${\displaystyle 3p}$ ${\displaystyle p}$ ${\displaystyle 2p}$ ${\displaystyle p}$

Лемма 4

Для изначальной функции указана верхняя граница ,

${\displaystyle n\#=\prod _{p\,\leq \,n}p,}$

где произведение берется по всем простым числам, меньшим или равным . ${\displaystyle p}$ ${\displaystyle n}$

Для всех , . ${\displaystyle n\geq 1}$ ${\displaystyle n\#<4^{n}}$

Доказательство: Используем полную индукцию .

Ибо у нас есть и . ${\displaystyle n=1,2}$ ${\displaystyle 1\#=1<4}$ ${\displaystyle 2\#=2<4^{2}=16}$

Предположим, что неравенство выполняется для всех . Поскольку является составным, то имеем ${\displaystyle 1\leq n\leq 2k-1}$ ${\displaystyle n=2k>2}$

${\displaystyle (2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.}$

Теперь предположим, что неравенство выполняется для всех . Поскольку — целое число, а все простые числа появляются только в числителе, то имеем ${\displaystyle 1\leq n\leq 2k}$ ${\displaystyle {\binom {2k+1}{k}}={\frac {(2k+1)!}{k!(k+1)!}}}$ ${\displaystyle k+2\leq p\leq 2k+1}$

${\displaystyle {\frac {(2k+1)\#}{(k+1)\#}}\leq {\binom {2k+1}{k}}={\frac {1}{2}}\!\left[{\binom {2k+1}{k}}+{\binom {2k+1}{k+1}}\right]<{\frac {1}{2}}(1+1)^{2k+1}=4^{k}.}$

Поэтому,

${\displaystyle (2k+1)\#=(k+1)\#\cdot {\frac {(2k+1)\#}{(k+1)\#}}\leq 4^{k+1}{\binom {2k+1}{k}}<4^{k+1}\cdot 4^{k}=4^{2k+1}.}$

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

Предположим, что существует контрпример : целое число n  ≥ 2, такое что не существует простого числа p с n  <  p  < 2 n .

Если 2 ≤ n < 427, то p можно выбрать из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 (каждое из которых является наибольшим простым числом, меньшим удвоенного предыдущего), так что n  <  p  < 2 n . Следовательно, n  ≥ 427.

Не существует простых множителей p таких , что: ${\displaystyle \textstyle {\binom {2n}{n}}}$

• 2 n < p , потому что каждый множитель должен делить (2 n )!;
• p = 2 n , так как 2 n не является простым числом;
• n < p < 2 n , поскольку мы предположили, что такого простого числа не существует;
• 2 n  / 3 < p ≤ n : по лемме 3.

Следовательно, каждый простой множитель p удовлетворяет условию p ≤ 2 n  / 3.

Когда число имеет не более одного множителя p . По лемме 2 для любого простого числа p имеем p ^{R ( p , n )} ≤ 2 n , и поскольку 1 не является ни простым, ни составным. Тогда, начиная с леммы 1 и разлагая правую часть на простые множители, и, наконец, используя лемму 4, эти границы дают: ${\displaystyle p>{\sqrt {2n}},}$ ${\displaystyle \textstyle {2n \choose n}}$ ${\displaystyle \pi (x)\leq x-1}$

${\displaystyle {\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}=\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}p^{R(p,n)}\right)\!\!\left(\prod _{{\sqrt {2n}}\,<\,p\,\leq \,2n/3}\!\!\!\!\!\!\!p^{R(p,n)}\right)<\left(\,\prod _{p\,\leq \,{\sqrt {2n}}}\!\!2n\right)\!\!\left(\prod _{p\,\leq \,2n/3}\!\!p\right)\leq (2n)^{{\sqrt {2n}}-1}4^{2n/3}.}$

Поэтому

${\displaystyle 4^{n/3}\leq (2n)^{\sqrt {2n}}}$, что упрощается до ${\displaystyle 2^{\sqrt {2n}}\leq (2n)^{3}.}$

Логарифмирование дает​

${\displaystyle {\sqrt {2n}}\leq 3\log _{2}(2n).}$

В силу вогнутости правой части как функции n последнее неравенство обязательно проверяется на интервале. Поскольку оно справедливо для и не справедливо для , получаем ${\displaystyle n=426}$ ${\displaystyle n=427}$

${\displaystyle n<427.}$

Но эти случаи уже были рассмотрены, и мы приходим к выводу, что контрпример к постулату невозможен.

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

Можно уменьшить границу до . ${\displaystyle n=50}$

Поскольку мы получаем , то можно сказать, что произведение не более , что дает ${\displaystyle n\geq 17,}$ ${\displaystyle \pi (n)<{\frac {n}{2}}-1}$ ${\displaystyle p^{R}}$ ${\displaystyle (2n)^{0.5{\sqrt {2n}}-1}}$

${\displaystyle {\begin{aligned}&{\frac {4^{n}}{2n}}\leq {\binom {2n}{n}}\leq (2n)^{0.5{\sqrt {2n}}-1}4^{2n/3}\\&4^{\sqrt {2n}}\leq (2n)^{3}\\&2{\sqrt {2n}}\leq 3\log _{2}(2n)\end{aligned}}}$

что верно для и ложно для . ${\displaystyle n=49}$ ${\displaystyle n=50}$

Ссылки

1. Бертран, Жозеф (1845), «Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.», Journal de l'École Royale Polytechnique (на французском языке), 18 (Cahier 30) : 123–140.
2. Рамануджан, С. (1919), «Доказательство постулата Бертрана», Журнал Индийского математического общества , 11 : 181–182
3. Эрдеш, Пал (1932), "Beweis eines Satzes von Tschebyschef" [Доказательство теоремы Чебышева] (PDF) , Acta Scientarium Mathematicarum (Szeged) , 5 (3–4): 194–198, Zbl  004.10103

Внешние ссылки

• Теорема Чебышева и постулат Бертрана (Лео Гольдмахер): https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf
• Доказательство постулата Бертрана (UW Math Circle): https://sites.math.washington.edu/~mathcircle/circle/2013-14/advanced/mc-13a-w10.pdf
• Доказательство в системе Мицар : http://mizar.org/version/current/html/nat_4.html#T56
• Вайсштейн, Эрик В. «Постулат Бертрана». MathWorld .