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

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

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

• — биномиальный коэффициент или число сочетаний из a по b.
• — целая часть x.

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

Например, .

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

Лемма

Лемма

для всех .

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

Заметим — и это главная идея доказательства леммы — что для любого целого неотрицательного m, биноминальный коэффициент делится на все простые числа в интервале [m+2, 2m+1]. В самом деле, , a любое простое число в указанном интервале делит числитель этой дроби и не делит её знаменатель. А коль скоро биноминальный коэффициент делится на все такие простые числа, он не может быть меньше их произведения

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

С другой стороны, биноминальный коэффициент легко оценить сверху:

.

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

Откуда

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

• n = 1:

• n = 2:

• n > 2 и n чётно.

(здесь мы используем, что чётное число, большее 2 - составное и поэтому не входит в сумму ).

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

Лемма доказана.

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

Теперь переходим к доказательству самого постулата. Основная идея доказательства - разложить биноминальный коэффициент на простые множители. Если между 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.

Оценим .

Поскольку - максимальный член суммы, мы имеем:

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

Пускай - степень p в разложении на простые множители.

Поскольку n! для каждого j имеет ровно сомножителей, делящихся на , в разложении n! на простые множители p входит в степени . Поэтому

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

Величина: каждое слагаемое может быть или 0, или 1 (в зависимости от дробной части  : если она меньше , слагаемое равно 0, а если или больше, то 1).

Количество: все слагаемые с равны нулю, потому что для них . Поэтому только первых слагаемых имеют шансы быть ненулевыми.

Итак, - сумма слагаемых, каждое из которых равно 0 или 1. Следовательно,

Оценка

Оценим теперь .

Это была оценка для любых p. Но гораздо лучшую оценку можно получить для . Для таких p, количество слагаемых равно 1, то есть в нашей, с позволения сказать, сумме всего одно слагаемое:

Если это слагаемое равно 1, то . А если оно равно 0, то .

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

А теперь посмотрим, в каком интервале находятся простые делители. не имеет простых делителей p таких, что:

• 2n < p, потому что .
• , потому что мы предположили, что в этом интервале нет простых чисел.
• , потому что (т.к. ), что даёт нам .

Получается, что у нет простых делителей, больших чем .

Перемножение всех

Теперь оценим произведение по всем простым делителям p числа . Для делителей, не больших , произведение не превышает . А для простых делителей, больших , оно не превышает .

Поскольку равен произведению по всем простым p, мы получаем:

Используя нашу лемму :

Поскольку :

Кроме того, (поскольку ):

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

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

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

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

ч.т.д.