Доказательство постулата Бертрана - Proof of Bertrands postulate

В математика, Постулат Бертрана (на самом деле теорема ) утверждает, что для каждого ${\displaystyle n\geq 2}$ Существует основной ${\displaystyle p}$ такой, что ${\displaystyle n<p<2n}$. Впервые это было доказано Пафнутый Чебышев, и короткое, но подробное доказательство было дано Шриниваса Рамануджан.^[1] Суть следующего элементарного доказательства обусловлена ​​тем, что Пол Эрдёш. Основная идея доказательства - показать, что некий центральный биномиальный коэффициент необходимо иметь главный фактор в пределах желаемого интервала, чтобы быть достаточно большим. Это стало возможным благодаря тщательному анализу факторизации центральных биномиальных коэффициентов на простые множители.

Основные этапы доказательства следующие. Во-первых, показано, что каждый основная сила фактор ${\displaystyle p^{r}}$ входящего в простое разложение центрального биномиального коэффициента ${\displaystyle {\tbinom {2n}{n}}:={\frac {(2n)!}{(n!)^{2}}}}$ самое большее ${\displaystyle 2n}$. В частности, каждое простое число больше ${\displaystyle {\sqrt {2n}}}$ может войти в это разложение не более одного раза; то есть его показатель ${\displaystyle r}$ самое большее. Следующий шаг - доказать, что ${\displaystyle {\tbinom {2n}{n}}}$ вообще не имеет простых множителей в интервале разрыва ${\displaystyle \left({\tfrac {2n}{3}},n\right)}$. Как следствие этих двух оценок вклад в размер ${\displaystyle {\tbinom {2n}{n}}}$ исходящий из всех основных факторов, которые не более ${\displaystyle n}$ асимптотически растет в качестве ${\displaystyle O(\theta ^{n})}$ для некоторых ${\displaystyle \theta <4}$. Поскольку асимптотический рост центрального биномиального коэффициента не меньше ${\displaystyle 4^{n}/2n}$, можно сделать вывод, что для ${\displaystyle n}$ достаточно большой, биномиальный коэффициент должен иметь другой простой множитель, который может находиться только между ${\displaystyle n}$ и ${\displaystyle 2n}$Действительно, делая эти оценки количественными, получается, что этот аргумент справедлив для всех ${\displaystyle n\geq 468}$. Остальные меньшие значения${\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: верхняя оценка степеней простых чисел, делящих центральные биномиальные коэффициенты

Для фиксированного простого числа ${\displaystyle p}$, определять ${\displaystyle R:=R(p,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}$) или 1 (если ${\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(p,n)=0.}$

Доказательство: Есть ровно два фактора ${\displaystyle p}$ в числителе выражения ${\displaystyle {\tbinom {2n}{n}}={\frac {(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 x\#=\prod _{p\leq x}p,}$

где продукт берется за все основной числа ${\displaystyle p}$ меньше или равно действительному числу ${\displaystyle x.}$

Лемма: Для всех реальных чисел ${\displaystyle x\geq 3}$, ${\displaystyle x\#<2^{2x-3}.}$

Доказательство:С ${\displaystyle x\#=\lfloor x\rfloor \#}$ и ${\displaystyle 2^{2\lfloor x\rfloor -3}\leq 2^{2x-3}}$, достаточно доказать результат в предположении, что ${\displaystyle x=m}$ целое число, ${\displaystyle m\geq 3.}$ С ${\displaystyle {\binom {2m-1}{m}}}$ целое число и все простые числа ${\displaystyle m+1\leq p\leq 2m-1}$ появляются в его числителе, но не в знаменателе, мы имеем

${\displaystyle {\frac {(2m-1)\#}{m\#}}\leq {\binom {2m-1}{m}}={\frac {1}{2}}\left({\binom {2m-1}{m-1}}+{\binom {2m-1}{m}}\right)<{\frac {1}{2}}(1+1)^{2m-1}=2^{2m-2}.}$

Доказательство проводится полная индукция на ${\displaystyle n.}$

• Если ${\displaystyle n=3}$, тогда ${\displaystyle n\#=6<8=2^{2n-3}.}$
• Если ${\displaystyle n=4}$, тогда ${\displaystyle n\#=6<32=2^{2n-3}.}$
• Если ${\displaystyle n\geq 5}$ странно, ${\displaystyle n=2m-1}$, то по полученной оценке и предположению индукции, так как ${\displaystyle m\geq 3}$ и ${\displaystyle m<n}$ это

${\displaystyle n\#=(2m-1)\#<m\#\cdot 2^{2m-2}<2^{2m-3}2^{2m-2}=2^{4m-5}=2^{2n-3}.}$

• Если ${\displaystyle n=2m}$ даже и ${\displaystyle n\geq 6,}$ то по полученной оценке и предположению индукции, так как ${\displaystyle m\geq 3}$ и ${\displaystyle n-1<n}$ это

${\displaystyle n\#=(2m)\#=(2m-1)\#=(n-1)\#<2^{2(n-1)-3}<2^{2n-3}.}$

Таким образом, лемма доказана.

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

Предположим, что есть контрпример: целое число п ≥ 2 таких, что нет простого п с п < п < 2п.

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

Нет простых факторов п из ${\displaystyle \textstyle {\binom {2n}{n}}}$ такой, что:

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

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

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

${\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 {\frac {2n}{3}}}p^{R(p,n)}\right)<(2n)^{\sqrt {2n}}\prod _{1<p\leq {\frac {2n}{3}}}p=(2n)^{\sqrt {2n}}{\Big (}{\frac {2n}{3}}{\Big )}\#\leq (2n)^{\sqrt {2n}}4^{2n/3}.}$

Логарифм дает

${\displaystyle {\frac {\log 4}{3}}n\leq ({\sqrt {2n}}+1)\log 2n\;.}$

По вогнутости правой части как функции п, последнее неравенство обязательно проверяется на интервале. Поскольку это верно для n = 467 и это не для n = 468, мы получаем

${\displaystyle n<468.}$

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

Рекомендации

1. Рамануджан, С. (1919), «Доказательство постулата Бертрана», Журнал Индийского математического общества, 11: 181–182

• Айгнер, Мартин, Г., Гюнтер М. Циглер, Карл Х. Хофманн, Доказательства из КНИГИ, Четвертое издание, Springer, 2009. ISBN  978-3-642-00855-9.

внешняя ссылка

• Доказательство в Система Мицар: http://mizar.org/version/current/html/nat_4.html#T56