WikiSort.ru - Не сортированное

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что

Для любого натурального n ⩾ 2 найдётся простое число p в интервале n < p < 2n.

Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном (проверившим её до n = 3 000 000) и доказан в 1852 году^[1] Чебышёвым. Рамануджан в 1920 году нашёл более простое доказательство, а Эрдёш в 1932 году — ещё более простое.

Обобщения

Похожая, но недоказанная гипотеза Лежандра гласит, что для любого $n\geqslant 2$ найдётся простое число $p$ в интервале $n^{2}<p<(n+1)^{2}$ .

Обобщением постулата Бертрана можно считать теорему о том, что для $n\geqslant 2k$ среди чисел $n-k+1,\dots ,n-1,n$ всегда существует число с простым делителем больше $k$ . Это утверждение было доказано Сильвестром в 1892 году. При $n=2k$ оно даёт гипотезу Бертрана как частный случай.

Из теоремы о распределении простых чисел следует, что для любого $\varepsilon >0$ существует число $n_{0}$ такое, что для любых $n\geqslant n_{0}$ существует простое число $p$ , удовлетворяющее $n<p<(1+\varepsilon )n$ . Более того, для фиксированного $\varepsilon$ количество простых чисел в этом интервале стремится к бесконечности с ростом $n$ ^[2]. В частности, например, при $n\geqslant 25$ всегда найдётся простое число между $n$ и $(1+1/5)n$ ^[3].

Доказательство

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

Здесь мы приводим доказательство, предложенное Эрдёшем.

Обозначения и определения

В доказательстве мы используем следующие обозначения:

${a \choose b}$ — биномиальный коэффициент или число сочетаний из a по b.
$\left\lfloor x\right\rfloor$ — целая часть x.

Обозначим множество простых чисел через $\mathbb {P}$ и определим $\theta (n)$ как сумму логарифмов простых чисел, не превышающих n:

\theta (n)=\sum _{p\in \mathbb {P} ;\,p\leq n}\ln(p)

Например, $\theta (10)=\ln 2+\ln 3+\ln 5+\ln 7$ .

Эта функция называется θ-функция Чебышёва.

Лемма

Лемма

\theta (n)<n\cdot \ln(4)

для всех

n\geq 1

.

(Интересно, что для доказательства теоремы о том, что простых чисел «не очень мало», нам приходится сначала доказать лемму, гласящую, что простых чисел «не очень много».)

Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного m, биноминальный коэффициент ${2m+1 \choose m}$ делится на все простые числа в интервале [m+2, 2m+1]. В самом деле, ${2m+1 \choose m}={\frac {(2m+1)!}{m!(m+1)!}}$ , a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. Поскольку биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения

{2m+1 \choose m}\geq \prod _{p\in \mathbb {P} ;\,m+2\leq p\leq 2m+1}p

Беря логарифм от обеих частей неравенства, получаем

\ln {2m+1 \choose m}\geq \sum _{p\in \mathbb {P} ;\,m+2\leq p\leq 2m+1}\ln p=\theta (2m+1)-\theta (m+1)

С другой стороны, биноминальный коэффициент ${2m+1 \choose m}$ легко оценить сверху:

{2m+1 \choose m}={\frac {{2m+1 \choose m}+{2m+1 \choose m+1}}{2}}\leq {\frac {\sum _{k=0}^{2m+1}{2m+1 \choose k}}{2}}=

={\frac {(1+1)^{2m+1}}{2}}=4^{m}

.

Объединяя два последних неравенства, получаем

\theta (2m+1)-\theta (m+1)\leq \ln 4^{m}=m\ln 4

Откуда

\theta (2m+1)\leq \theta (m+1)+m\ln 4

Теперь легко доказать лемму по индукции:

n = 1:

\theta (1)=0<1\cdot \ln(4)

n = 2:

\theta (2)=\ln(2)<2\cdot \ln(4)

$n>2$ и n нечётно. Пусть $n=2m+1$ .

\theta (2m+1)\leq \theta (m+1)+m\ln 4<(m+1)\ln 4+m\ln 4=(2m+1)\ln 4=n\ln 4

n > 2 и n чётно.

\theta (n)=\theta (n-1)<(n-1)\cdot \ln(4)<n\cdot \ln(4)

(поскольку любое чётное число, большее 2 — составное, то $\ln(n)$ не входит в сумму $\sum _{p\in \mathbb {P} ;\,p\leq n}\ln(p)$ ). Лемма доказана.

Доказательство основной теоремы

Теперь переходим к доказательству самого постулата. Основная идея доказательства — разложить биноминальный коэффициент $2n \choose n$ на простые множители. Если между n и 2n нет простых чисел, то произведение всех этих простых множителей окажется слишком маленьким.

Доказываем от противного. Допустим, что для некоторого целого n ≥ 2 не существует простого числа p такого, что n < p < 2n.

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

Оценим $2n \choose n$ .

4^{n}=(1+1)^{2n}=\sum _{k=0}^{2n}{2n \choose k}

Поскольку ${2n \choose n}$ - максимальный член суммы, мы имеем:

{\frac {4^{n}}{2n+1}}\leq {2n \choose n}

Определение R(p,n) и его оценка сверху

Пускай $R(p,n)$ - степень p в разложении ${2n \choose n}$ на простые множители.

{2n \choose n}=\prod _{p}{p^{R(p,n)}}

Поскольку n! для каждого j имеет ровно $\left\lfloor {\frac {n}{p^{j}}}\right\rfloor$ сомножителей, делящихся на $p^{j}$ , в разложении n! на простые множители p входит в степени $\sum _{j=1}^{\infty }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor$ . Поэтому

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)

Чтобы узнать об этой сумме побольше, оценим, с одной стороны, насколько велики её слагаемые, а с другой — их количество.

Величина: каждое слагаемое $\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor$ может быть или 0, или 1 (в зависимости от дробной части ${\frac {n}{p^{j}}}$ : если она меньше ${\frac {1}{2}}$ , слагаемое равно 0, а если ${\frac {1}{2}}$ или больше, то 1).

Количество: все слагаемые с $j>{\frac {\ln(2n)}{\ln(p)}}$ равны нулю, потому что для них ${\frac {2n}{p^{j}}}<1$ . Поэтому только $\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor$ первых слагаемых имеют шансы быть ненулевыми.

Итак, $R(p,n)$ - сумма $\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor$ слагаемых, каждое из которых равно 0 или 1. Следовательно,

R(p,n)\leq \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor

Оценка $p^{R(p,n)}$

Оценим теперь $p^{R(p,n)}$ .

p^{R(p,n)}=\exp \left(R(p,n)\ln p\right)\leq \exp \left(\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln p\right)\leq 2n

Это была оценка для любых p. Но гораздо лучшую оценку можно получить для ${\sqrt {2n}}<p\leq 2n$ . Для таких p, количество слагаемых $\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor$ равно 1, то есть в нашей сумме всего одно слагаемое:

R(p,n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor

Если это слагаемое равно 1, то $p^{R(p,n)}=p$ . А если оно равно 0, то $p^{R(p,n)}=1$ .

В каком интервале могут находиться простые делители?

А теперь посмотрим, в каком интервале находятся простые делители. ${2n \choose n}$ не имеет простых делителей p таких, что:

2n < p, потому что $R(p,n)\leq \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor =0$ .
$n<p\leq 2n$ , потому что мы предположили, что в этом интервале нет простых чисел.
${\frac {2n}{3}}<p\leq n$ , потому что $p>{\sqrt {2n}}$ (т.к. $n\geq 5$ ), что даёт нам $R(p,n)=\left\lfloor {\frac {2n}{p}}\right\rfloor -2\left\lfloor {\frac {n}{p}}\right\rfloor =2-2=0$ .

Получается, что у ${2n \choose n}$ нет простых делителей, больших чем ${\frac {2n}{3}}$ .

Перемножение всех $p^{R(p,n)}$

Теперь оценим произведение $p^{R(p,n)}$ по всем простым делителям p числа ${2n \choose n}$ . Для делителей, не больших ${\sqrt {2n}}$ , произведение не превышает ${(2n)}^{\sqrt {2n}}$ . А для простых делителей, больших ${\sqrt {2n}}$ , оно не превышает $\prod _{p\in \mathbb {P} ;\,p\leq 2n/3}p=\exp \left(\theta \left({\frac {2n}{3}}\right)\right)$ .

Поскольку ${2n \choose n}$ равен произведению $p^{R(p,n)}$ по всем простым p, мы получаем:

{\frac {4^{n}}{2n+1}}\leq {2n \choose n}\leq (2n)^{\sqrt {2n}}\exp \left(\theta \left({\frac {2n}{3}}\right)\right)

Используя нашу лемму $\theta (n)<n\cdot \ln(4)$ :

{\frac {4^{n}}{2n+1}}<(2n)^{\sqrt {2n}}4^{\frac {2n}{3}}

Поскольку $(2n+1)<(2n)^{2}$ :

4^{\frac {n}{3}}<(2n)^{2+{\sqrt {2n}}}

Кроме того, $2\leq {\frac {\sqrt {2n}}{3}}$ (поскольку $n\geq 18$ ):

4^{\frac {n}{3}}<(2n)^{{\frac {4}{3}}{\sqrt {2n}}}

Логарифмируя обе части, получаем

{\sqrt {2n}}\ln(2)<4\cdot \ln(2n)

Делая подстановку 2^2t = 2n:

{\frac {2^{t}}{t}}<8

Это даёт нам t < 6 и противоречие:

n={\frac {2^{2t}}{2}}<{\frac {2^{2\cdot 6}}{2}}=2048

Следовательно, наше допущение было неверно.

Q.E.D.

Примечания

↑ Энциклопедический словарь юного математика, 1985.
↑ G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, p. 494.
↑ J. Nagura. On the interval containing at least one prime number // Proceedings of the Japan Academy, Series A. — 1952. — Vol. 28. — P. 177–181. — DOI:10.3792/pja/1195570997.

Литература

Простое число // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 262-263. — 352 с.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[_0d03cead6ed18a91-1] Энциклопедический словарь юного математика, 1985.

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008, p. 494.

[3] J. Nagura. On the interval containing at least one prime number // Proceedings of the Japan Academy, Series A. — 1952. — Vol. 28. — P. 177–181. — DOI:10.3792/pja/1195570997.