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

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Доказательство постулата Бертрана»  – Новости  · газеты  · книги  · ученый  · JSTOR (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В математика, Постулат Бертрана (на самом деле теорема ) утверждает, что для каждого ${ Displaystyle п geq 2}$ Существует основной ${ displaystyle p}$ такой, что ${ Displaystyle п <р <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 влево ({ tfrac {2n} {3}}, п вправо)}$. Как следствие этих двух оценок вклад в размер ${ displaystyle { tbinom {2n} {n}}}$ исходящий из всех основных факторов, которые не более ${ displaystyle n}$ асимптотически растет в качестве ${ Displaystyle О ( тета ^ {п})}$ для некоторых ${ 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}}$

, тогда ${ Displaystyle R (p, n) = 0.}$

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

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

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

Доказательство:С ${ Displaystyle х # = 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 м + 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 ^ {2м-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 п = 2 м-1}$, то по полученной оценке и предположению индукции, так как ${ displaystyle m geq 3}$ и ${ Displaystyle м <п}$ это

${ Displaystyle п # = (2 м-1) # <м # cdot 2 ^ {2 м-2} <2 ^ {2 м-3} 2 ^ {2 м-2} = 2 ^ {4 м-5} = 2 ^ {2n-3}.}$

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

${ 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}}$

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

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

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

${ displaystyle n <468.}$

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

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

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

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

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