Википедия

Постулат Бертрана: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
пунктуация, оформление, стилевые правки
м Бот: исключение из Категория:Доказательства; косметические изменения
Строка 28:
:<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>.
 
Эта функция называется ''θ-функция Эрдёша''.
Строка 39:
(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)
 
Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного '''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>
Беря логарифм от обеих частей неравенства, получаем
Строка 56:
* ''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'' чётно.
Строка 67:
== Доказательство основной теоремы ==
 
Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент <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>.
Строка 83:
=== Определение 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>
Строка 94:
'''Величина''': каждое слагаемое <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>
 
Строка 103:
:<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>, потому что мы предположили, что в этом интервале нет простых чисел.
Строка 118:
=== Перемножение всех <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'', мы получаем:
Строка 154:
 
[[Категория:Теоремы о простых числах|Бертрана]]
[[Категория:Доказательства]]
Источник — https://ru.wikipedia.org/wiki/Постулат_Бертрана