Постулат Бертрана: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Я оочень люблю википедию..так что вот... |
Sigwald (обсуждение | вклад) м откат правок 83.234.183.3 (обс) к версии 92.242.58.13 |
||
Строка 1:
{{Значения|Бертран}}
'''Постулат Бертрана''', '''теорема Бертрана — Чебышёва''' или '''теорема Чебышёва''' гласит, что
{{рамка}}
Для любого натурального ''n'' ≥ 2 найдётся [[простое число]] ''p'' в интервале ''n'' < ''p'' < 2''n''.
{{/рамка}}
== Обобщения ==
Похожая, но недоказанная [[гипотеза Лежандра]] гласит, что для любого ''n'' ≥ 2 найдётся [[простое число]] ''p'' в интервале ''n<sup>2</sup> < p < (n+1)<sup>2</sup>''.
Обобщением постулата Бертрана можно считать теорему о том, что для <math>n \ge 2k</math> среди чисел <math>n-k+1, \dots, n-1, n</math> всегда существует число с простым делителем больше <math>k</math>. Это утверждение было доказано Сильвестром в 1892 году. При <math>n=2k</math> оно даёт гипотезу Бертрана как частный случай.
== Доказательство ==
{{Hider|
title = Доказательство постулата Бертрана|
hidden = 1 |
title-style = text-align: left; |
content-style = text-align: left; |
content =
Здесь мы приводим доказательство, предложенное [[Эрдёш, Пол|Эрдёшем]].
=== Обозначения и определения ===
В доказательстве мы используем следующие обозначения:
* <math>{a \choose b}</math> — [[биномиальный коэффициент]] или [[число сочетаний]] из ''a'' по ''b''.
* <math> \left \lfloor x \right \rfloor </math> — [[целая часть]] x.
Обозначим множество простых чисел через <math>\Bbb{P}</math> и определим <math>\theta(n)</math> как сумму логарифмов простых чисел, не превышающих '''n''':
:<math> \theta(n) = \sum_{p\in\Bbb{P};\, p\leq n} \ln (p) </math>
Например, <math> \theta(10)=\ln 2 + \ln 3 + \ln 5 + \ln 7 </math>.
Эта функция называется ''θ-функция Чебышёва''.
=== Лемма ===
'''[[Лемма]]'''
:<math> \theta(n) < n \cdot \ln(4) </math> для всех <math> n\ge 1 </math>.
(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)
Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного '''m''', биноминальный коэффициент <math> {2m+1 \choose m} </math> делится на все простые числа в интервале [m+2, 2m+1]. В самом деле, <math> {2m+1 \choose m} = \frac {(2m+1)!} {m!(m+1)!} </math>, a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. Поскольку биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения
::<math> {2m+1 \choose m} \ge \prod_{p\in\Bbb{P};\, m+2 \le p \le 2m+1} p</math>
Беря логарифм от обеих частей неравенства, получаем
::<math> \ln {2m+1 \choose m} \ge \sum_{p\in\Bbb{P};\, m+2 \le p \le 2m+1} \ln p = \theta(2m+1)-\theta(m+1) </math>
С другой стороны, биноминальный коэффициент <math> {2m+1 \choose m} </math> легко оценить сверху:
::<math> {2m+1 \choose m} = \frac {{2m+1 \choose m}+{2m+1 \choose m+1}}{2} \le \frac {\sum_{k=0}^{2m+1}{2m+1 \choose k}} {2} = </math>
::<math> = \frac {(1+1)^{2m+1}}{2} = 4^m </math>.
Объединяя два последних неравенства, получаем
::<math>\theta(2m+1)-\theta(m+1) \le \ln 4^m = m \ln 4 </math>
Откуда
::<math>\theta(2m+1) \le \theta(m+1) + m \ln 4 </math>
Теперь легко доказать лемму по индукции:
* ''n'' = 1:
::<math> \theta(1)= 0 < 1 \cdot \ln(4) </math>
* ''n'' = 2:
::<math> \theta(2)=\ln(2) < 2 \cdot \ln(4) </math>
* <math> n>2 </math> и ''n'' нечётно. Пусть <math> n = 2m+1 </math>.
::<math>\theta(2m+1) \le \theta(m+1) + m \ln 4 < (m+1) \ln 4 + m \ln 4 = (2m+1) \ln 4 = n \ln 4</math>
* ''n'' > 2 и ''n'' чётно.
::<math> \theta(n) = \theta(n-1) < (n-1) \cdot \ln(4) < n \cdot \ln(4) </math>
(поскольку любое чётное число, большее 2 — составное, то <math> \ln (n) </math> не входит в сумму <math> \sum_{p\in\Bbb{P};\, p\leq n} \ln (p) </math>).
Лемма доказана.
<!-- {{Доказательство|title=Доказательство леммы|Вспомогательная лемма постулата Бертрана}} -->
=== Доказательство основной теоремы ===
Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент <math> 2n \choose n </math> на простые множители. Если между ''n'' и ''2n'' нет простых чисел, то произведение всех этих простых множителей окажется ''слишком маленьким.''
Доказываем от противного. Допустим, что для некоторого целого ''n'' ≥ 2 не существует простого числа ''p'' такого, что ''n'' < ''p'' < 2''n''.
Если 2 ≤ ''n'' < 2048, то одно из простых чисел 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 и 2503 (каждое последующее меньше удвоенного предыдущего), назовём его ''p'', удовлетворяет неравенству ''n'' < ''p'' < 2''n''. Следовательно, ''n'' ≥ 2048.
Оценим <math> 2n \choose n </math>.
:<math> 4^n=(1+1)^{2n}=\sum_{k=0}^{2n}{2n \choose k} </math>
Поскольку <math> {2n \choose n} </math> - максимальный член суммы, мы имеем:
:<math> \frac {4^n} {2n+1} \le {2n \choose n} </math>
==== Определение R(p,n) и его оценка сверху ====
Пускай <math> R(p, n) </math> - степень ''p'' в разложении <math> {2n \choose n} </math> на простые множители.
::<math>{2n \choose n} = \prod_p{p^{R(p,n)}}</math>
Поскольку ''n!'' для каждого ''j'' имеет ровно <math> \left \lfloor \frac {n} {p^j} \right \rfloor </math> сомножителей, делящихся на <math>p^j</math>, в разложении ''n!'' на простые множители ''p'' входит в степени <math> \sum_{j=1}^\infty \left \lfloor \frac {n} {p^j} \right \rfloor </math>. Поэтому
:<math> 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) </math>
Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.
'''Величина''': каждое слагаемое <math> \left \lfloor \frac {2n} {p^j} \right \rfloor - 2\left \lfloor \frac {n} {p^j} \right \rfloor </math> может быть или 0, или 1 (в зависимости от дробной части <math> \frac {n} {p^j} </math> : если она меньше <math>\frac{1}{2}</math>, слагаемое равно 0, а если <math>\frac{1}{2}</math> или больше, то 1).
'''Количество''': все слагаемые с <math> j > \frac {\ln(2n)} {\ln(p)} </math> равны нулю, потому что для них <math> \frac {2n} {p^j} < 1 </math>. Поэтому только <math> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math> первых слагаемых имеют шансы быть ненулевыми.
Итак, <math> R(p,n) </math> - сумма <math> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math> слагаемых, каждое из которых равно 0 или 1. Следовательно,
:<math> R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math>
==== Оценка <math> p^{R(p,n)} </math> ====
Оценим теперь <math> p^{R(p,n)} </math>.
:<math>p^{R(p,n)} = \exp \left ( R(p,n) \ln p \right ) \le \exp \left ( \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor \ln p \right ) \le 2n </math>
Это была оценка для любых ''p''. Но гораздо лучшую оценку можно получить для <math> \sqrt {2n} < p \le 2n </math>. Для таких ''p'', количество слагаемых <math> \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor </math> равно 1, то есть в нашей сумме всего одно слагаемое:
:<math> R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor </math>
Если это слагаемое равно 1, то <math> p^{R(p,n)} = p </math> . А если оно равно 0, то <math>p^{R(p,n)} = 1 </math> .
==== В каком интервале могут находиться простые делители? ====
А теперь посмотрим, в каком интервале находятся простые делители. <math> {2n \choose n} </math> не имеет простых делителей ''p'' таких, что:
* 2''n'' < ''p'', потому что <math> R(p,n) \le \left \lfloor \frac {\ln(2n)} {\ln(p)} \right \rfloor = 0 </math>.
* <math> n<p \le 2n </math>, потому что мы предположили, что в этом интервале нет простых чисел.
* <math> \frac {2n} {3} <p \le n </math>, потому что <math> p > \sqrt{2n} </math> (т.к. <math> n \ge 5 </math>), что даёт нам <math> R(p,n) = \left \lfloor \frac {2n} {p} \right \rfloor - 2\left \lfloor \frac {n} {p} \right \rfloor = 2-2 = 0 </math>.
Получается, что у <math> {2n \choose n} </math> нет простых делителей, больших чем <math> \frac {2n} {3} </math>.
==== Перемножение всех <math>p^{R(p,n)}</math> ====
Теперь оценим произведение <math>p^{R(p,n)}</math> по всем простым делителям ''p'' числа <math> {2n \choose n} </math> . Для делителей, не больших <math> \sqrt{2n} </math>, произведение не превышает <math> {(2n)} ^ {\sqrt{2n}} </math> . А для простых делителей, больших <math> \sqrt{2n} </math>, оно не превышает <math> \prod_{p \in \mathbb{P};\, p \leq 2n/3} p = \exp \left ( \theta \left ( \frac {2n} {3} \right ) \right )</math>.
Поскольку <math> {2n \choose n} </math> равен произведению <math> p^{R(p,n)} </math> по всем простым ''p'', мы получаем:
:<math> \frac {4^n}{2n+1} \le {2n \choose n} \le (2n)^\sqrt{2n} \exp \left ( \theta \left ( \frac {2n} {3} \right ) \right ) </math>
Используя нашу лемму <math> \theta(n) < n \cdot \ln(4) </math>:
:<math> \frac {4^n} {2n+1} \le (2n)^\sqrt{2n} 4^{\frac {2n} {3}} </math>
Поскольку <math> (2n+1) < (2n)^2 </math>:
:<math> 4^{\frac {n}{3}} \le (2n)^{2+\sqrt{2n}} </math>
Кроме того, <math> 2 \le \frac {\sqrt{2n}}{3} </math> (поскольку <math> n \ge 18 </math>):
:<math> 4^{\frac {n}{3}} \le (2n)^{\frac {4} {3}\sqrt{2n}} </math>
[[Логарифм]]ируя обе части, получаем
:<math> \sqrt{2n} \ln(2) \le 4 \cdot \ln(2n) </math>
Делая подстановку 2<sup>2''t''</sup> = 2''n'':
:<math> \frac {2^t} {t} \le 8 </math>
Это даёт нам ''t'' < 6 и противоречие:
:<math>n=\frac {2^{2t}} {2}<\frac {2^{2 \cdot 6}} {2}=2048</math>
Следовательно, наше допущение было неверно.
'''[[Q.E.D.]]'''
}}
== История ==
Постулат Бертрана был сформулирован в качестве [[гипотеза|гипотезы]] в [[1845 год]]у французским математиком [[Бертран, Жозеф Луи Франсуа|Бертраном]] (проверившим её до ''n''=3000000) и доказан в [[1852 год]]у{{sfn|Энциклопедический словарь юного математика|1985}} [[Чебышёв, Пафнутий Львович|Чебышёвым]].
[[Сриниваса Рамануджан Айенгор|Рамануджан]] в [[1920 год]]у нашёл более простое доказательство, а [[Эрдёш, Пол|Эрдёш]] в [[1932 год]]у — ещё более простое.
== Примечания ==
{{примечания}}
== Литература ==
* {{книга |ответственный = Сост. А. П. Савин |заглавие = Энциклопедический словарь юного математика |место = М. |издательство = [[Педагогика (издательство)|Педагогика]] |год = 1985 |страниц = 352 |часть = Простое число |страницы = 262-263 |ref = Энциклопедический словарь юного математика}}
[[Категория:Теоремы о простых числах|Бертрана]]
| |||