Распределение простых чисел и теорема о распределении простых чисел

Теорема о распределении простых чисел точно описывает интуицию, согласно которой простые числа редеют логарифмически: количество простых чисел до некоторой границы асимптотически равно этой границе, деленной на ее натуральный логарифм.

Definition

Теорема о распределении простых чисел утверждает, что количество простых чисел, не превышающих x, обозначаемое pi от x, асимптотически равно x, деленному на натуральный логарифм x, или, эквивалентно, логарифмическому интегралу от x.

Scope

Эта тема охватывает функцию подсчета простых чисел и ее асимптотику, элементарные границы Чебышева и суммирующие функции пси и тета, теоремы Мертенса, формулировку и аналитическое доказательство теоремы о распределении простых чисел через отсутствие нулей дзета-функции на прямой с действительной частью, равной единице, логарифмически-интегральное приближение, члены ошибок и их связь с гипотезой Римана, а также промежутки между простыми числами и эвристики для простых чисел-близнецов.

Core questions

• Как границы Чебышева и оценки Мертенса ограничивают плотность простых чисел до полной теоремы?
• Почему теорема о распределении простых чисел эквивалентна отсутствию нулей дзета-функции на прямой, где действительная часть равна единице?
• Насколько хорошо логарифмически-интегральное приближение и как член ошибки зависит от гипотезы Римана?
• Что известно и что предполагается о промежутках между последовательными простыми числами, включая простые числа-близнецы?

Key theories

Теорема о распределении простых чисел

Доказанная независимо Адамаром и де ла Валле Пуссеном в 1896 году, она дает ведущую асимптотику для подсчета простых чисел; эквивалентное утверждение для функции Чебышева пси является аналитически естественной формой.

Области без нулей и члены ошибок

Размер области без нулей для дзета-функции слева от прямой с действительной частью, равной единице, контролирует ошибку в теореме о распределении простых чисел; гипотеза Римана дала бы оптимальную ошибку типа квадратного корня.

Промежутки между простыми числами и эвристика Крамера

Средние промежутки около x составляют примерно логарифм x; вероятностные эвристики предсказывают распределение больших и малых промежутков, а достижения в методе решета доказали существование бесконечно многих ограниченных промежутков.

Clinical relevance

Плотность простых чисел, задаваемая теоремой, сообщает криптографам, сколько случайных кандидатов необходимо протестировать, чтобы найти простое число заданного размера, что напрямую определяет эффективность генерации ключей RSA и Диффи-Хеллмана.

History

Гаусс и Лежандр выдвинули гипотезу об асимптотическом подсчете простых чисел около 1800 года. Чебышев установил строгие верхние и нижние границы в 1850-х годах, Риман изложил аналитическую стратегию в 1859 году, а Адамар и де ла Валле Пуссен завершили доказательство в 1896 году. Сельберг и Эрдош позднее представили элементарное доказательство в 1949 году.

Key figures

• Bernhard Riemann
• Pafnuty Chebyshev
• Jacques Hadamard
• Charles-Jean de la Vallee Poussin

Seminal works

• davenport2000

Frequently asked questions

Позволяет ли теорема о распределении простых чисел предсказывать следующее простое число?

Нет. Она описывает среднюю плотность простых чисел на больших интервалах; она не определяет местоположение какого-либо отдельного простого числа, и простые числа остаются нерегулярными в малых масштабах.

Как теорема связана с гипотезой Римана?

Сама теорема безусловна, но гипотеза Римана позволила бы точно определить наименьшую возможную ошибку в приближении, контролируя, насколько фактическое количество простых чисел может отклоняться от логарифмического интеграла.