Асимптотический закон распределения простых чисел

Асимптотический закон распределения простых чисел (также известный как теорема о распределении простых чисел) — это фундаментальная теорема аналитической теории чисел, описывающая асимптотическое поведение количества простых чисел, не превосходящих заданное число. Теорема устанавливает, что функция π(x), обозначающая количество простых чисел, меньших или равных x, асимптотически равна x / ln(x) при x, стремящемся к бесконечности.

История открытия

Ранние наблюдения

Первые попытки понять закономерность распределения простых чисел относятся к XVIII веку. Леонард Эйлер в 1737 году установил связь между простыми числами и дзета-функцией, показав, что ряд ∑ 1/n^s сходится к произведению ∏ (1 — p^−s)^−1 по всем простым p. Однако точное описание распределения оставалось неизвестным.

В 1790-х годах Карл Фридрих Гаусс, анализируя таблицы простых чисел, эмпирически предположил, что плотность простых чисел вблизи числа x приблизительно равна 1/ln(x). Он также ввёл интегральный логарифм Li(x) = ∫₂^x dt/ln(t) как более точную аппроксимацию. Аналогичные наблюдения независимо сделал Адриен-Мари Лежандр в 1798 году, опубликовав гипотезу, что π(x) ≈ x/(ln(x) — 1,08366).

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

В 1859 году Бернхард Риман в своей знаменитой работе «О числе простых чисел, не превышающих данной величины» связал распределение простых чисел с нулями дзета-функции. Он предложил явную формулу для π(x), выражающую её через сумму по нетривиальным нулям дзета-функции. Однако строгое доказательство асимптотического закона было получено лишь в 1896 году независимо друг от друга Жаком Адамаром и Шарлем Жаном де ла Валле-Пуссеном. Оба доказательства опирались на теорию функций комплексного переменного и тот факт, что дзета-функция Римана не имеет нулей на прямой Re(s) = 1.

Дальнейшее развитие

В 1949 году Атле Сельберг и Пал Эрдёш независимо нашли элементарное доказательство теоремы, не использующее комплексный анализ. Их подход базировался на тождестве Сельберга и методах комбинаторной теории чисел. Это доказательство, хотя и сложное, показало, что теорема о распределении простых чисел может быть выведена без привлечения аналитических функций.

Формулировка теоремы

Основная форма

Пусть π(x) — функция распределения простых чисел, определяемая как количество простых чисел p, таких что p ≤ x. Тогда асимптотический закон распределения простых чисел утверждает:

π(x) ~ x / ln(x) при x → ∞,

где ln(x) — натуральный логарифм, а символ ~ означает, что предел отношения π(x) к x/ln(x) равен 1.

Эквивалентные формы

Теорема может быть записана в нескольких эквивалентных формах:

• π(x) = Li(x) + O(x e^{−c√ln(x)}) для некоторой положительной константы c (форма с остаточным членом, полученная де ла Валле-Пуссеном).
• Предел π(x) / (x/ln(x)) = 1.
• Предел π(x) / Li(x) = 1.

Интегральный логарифм Li(x) даёт более точную аппроксимацию: например, при x = 10^12 значение π(x) = 37 607 912 018, в то время как x/ln(x) ≈ 36 191 206 825, а Li(x) ≈ 37 607 950 281.

Следствия и интерпретации

Плотность простых чисел

Из теоремы следует, что средняя плотность простых чисел в окрестности числа x приблизительно равна 1/ln(x). Это означает, что вероятность того, что случайно выбранное число около x является простым, стремится к нулю при росте x, но убывает очень медленно.

Порядок n-го простого числа

Обозначим p_n как n-е простое число. Из асимптотического закона следует, что p_n ~ n ln(n). Более точная оценка: p_n = n ln(n) + n ln(ln(n)) — n + o(n).

Связь с дзета-функцией Римана

Теорема эквивалентна утверждению, что дзета-функция Римана ζ(s) не имеет нулей на прямой Re(s) = 1. Гипотеза Римана, которая утверждает, что все нетривиальные нули лежат на критической прямой Re(s) = 1/2, дала бы гораздо более точную оценку остаточного члена: π(x) = Li(x) + O(√x ln(x)).

Оценки и уточнения

Остаточный член

Наилучшая известная на сегодняшний день оценка остаточного члена принадлежит И. М. Виноградову и Н. М. Коробову (1958): π(x) = Li(x) + O(x e^{−c (ln x)^{3/5} (ln ln x)^{−1/5}}). Однако при условии гипотезы Римана оценка может быть улучшена до O(√x ln x).

Численные проверки

Таблицы π(x) для больших x подтверждают теорему. Например:

• π(10^9) = 50 847 534, x/ln(x) ≈ 48 254 942, Li(x) ≈ 50 849 235.
• π(10^12) = 37 607 912 018, x/ln(x) ≈ 36 191 206 825, Li(x) ≈ 37 607 950 281.
• π(10^15) = 29 844 570 422 669, x/ln(x) ≈ 28 952 965 460 217, Li(x) ≈ 29 844 571 475 288.

Видно, что Li(x) даёт значительно более точное приближение, чем x/ln(x), и всегда слегка превышает истинное значение π(x) для проверенных диапазонов (хотя известно, что это неравенство нарушается для некоторых очень больших x — так называемое явление Скьюза).

Применения

Криптография

Распределение простых чисел лежит в основе многих криптографических алгоритмов, включая RSA (Rivest–Shamir–Adleman). Для генерации ключей требуются большие простые числа, и знание их плотности позволяет оценить вычислительную сложность поиска.

Теория чисел

Теорема является отправной точкой для многих других результатов, таких как теорема Дирихле об арифметических прогрессиях, теорема Чебышёва о разности между π(x) и Li(x), и гипотеза Харди — Литтлвуда о распределении простых чисел в коротких интервалах.

Вычислительная математика

Асимптотический закон используется для оценки времени работы алгоритмов факторизации и тестирования простоты, таких как тест Миллера — Рабина и алгоритм AKS (Agrawal–Kayal–Saxena).

Интересные факты

• Явление Скьюза: В 1933 году Стэнли Скьюз показал, что существует число, при котором π(x) впервые превышает Li(x). Это число, названное числом Скьюза, оценивается как e^{e^{e^{79}}} и является одним из крупнейших чисел, когда-либо использованных в математических доказательствах.
• Связь с простыми числами-близнецами: Асимптотический закон не даёт информации о распределении пар простых чисел-близнецов, но гипотеза Харди — Литтлвуда предсказывает, что их количество асимптотически равно 2C₂ ∫₂^x dt/(ln t)^2, где C₂ — константа простых чисел-близнецов.
• Элементарное доказательство: Доказательство Сельберга и Эрдёша 1949 года считается одним из самых значительных достижений в теории чисел XX века, так как оно показало, что аналитические методы не являются необходимыми для доказательства фундаментальных результатов.

Источники

• Адамар Ж. Исследование о распределении простых чисел. — 1896.
• де ла Валле-Пуссен Ш. Ж. О функции, определяющей количество простых чисел, не превосходящих данную величину. — 1896.
• Сельберг А. Элементарное доказательство теоремы о распределении простых чисел. — 1949.
• Эрдёш П. О новом методе в теории чисел. — 1949.
• Виноградов И. М., Коробов Н. М. Оценка остаточного члена в теореме о распределении простых чисел. — 1958.
• Риман Б. О числе простых чисел, не превышающих данной величины. — 1859.