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

Теорема о распределении простых чисел — это фундаментальный результат аналитической теории чисел, описывающий асимптотический закон, которому подчиняется количество простых чисел, не превосходящих заданную границу. Теорема устанавливает, что функция распределения простых чисел \(\pi(x)\) (количество простых чисел, меньших или равных \(x\)) асимптотически эквивалентна отношению \(x / \ln x\) при \(x \to \infty\). Иными словами, доля простых чисел среди всех натуральных чисел, не превышающих \(x\), стремится к \(1 / \ln x\) по мере роста \(x\).

¶История

¶Ранние наблюдения и гипотезы

Первые попытки понять закономерность распределения простых чисел восходят к античности. Евклид в III веке до н. э. доказал бесконечность множества простых чисел. В XVIII веке Леонард Эйлер, изучая дзета-функцию \(\zeta(s) = \sum_{n=1}^\infty n^{-s}\), установил связь между простыми числами и аналитическими функциями. Он показал, что произведение по всем простым числам \(\prod_{p} (1 - p^{-s})^{-1}\) равно \(\zeta(s)\) для \(\Re(s) > 1\), что стало основой для аналитического подхода.

В конце XVIII века Карл Фридрих Гаусс, анализируя таблицы простых чисел, эмпирически заметил, что плотность простых чисел вблизи числа \(x\) приблизительно равна \(1 / \ln x\). Он предложил более точную аппроксимацию в виде интегрального логарифма \(\operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}\). Аналогичные наблюдения сделал Адриен-Мари Лежандр, который в 1798 году опубликовал гипотезу о том, что \(\pi(x) \approx x / (\ln x - 1.08366)\).

¶Формальное доказательство

В 1859 году Бернхард Риман в своей знаменитой работе «О числе простых чисел, не превышающих заданной величины» связал распределение простых чисел с нулями дзета-функции. Он вывел точную формулу для \(\pi(x)\) через сумму по нетривиальным нулям \(\zeta(s)\), что заложило основу для будущего доказательства.

Первое строгое доказательство теоремы было независимо получено в 1896 году Жаком Адамаром и Шарлем де ла Валле-Пуссеном. Оба математика использовали методы комплексного анализа, доказав, что дзета-функция Римана не имеет нулей на прямой \(\Re(s) = 1\). Это ключевое свойство позволило установить асимптотику \(\pi(x) \sim x / \ln x\). В 1949 году Атле Сельберг и Пал Эрдёш предложили элементарное доказательство, не использующее комплексный анализ, хотя оно было значительно сложнее аналитического.

¶Формулировка

¶Основная теорема

Теорема о распределении простых чисел утверждает: \[ \pi(x) \sim \frac{x}{\ln x} \quad \text{при } x \to \infty, \] где \(\pi(x)\) — количество простых чисел \(p \le x\), а \(\ln x\) — натуральный логарифм. Символ \(\sim\) означает, что предел отношения \(\pi(x) / (x / \ln x)\) равен 1.

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

Существует несколько эквивалентных форм записи:

• \(\pi(x) = \operatorname{Li}(x) + O(x e^{-c\sqrt{\ln x}})\) (с интегральным логарифмом, дающим более точную аппроксимацию).
• \(\pi(x) \sim \operatorname{Li}(x)\), где \(\operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}\).
• Для \(n\)-го простого числа \(p_n\) выполняется \(p_n \sim n \ln n\).

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

¶Аналитический подход

Доказательство Адамара и Валле-Пуссена опирается на свойства дзета-функции Римана. Основные шаги:

1. Связь с дзета-функцией: Используется тождество Эйлера \(\zeta(s) = \prod_{p} (1 - p^{-s})^{-1}\) для \(\Re(s) > 1\).
2. Логарифмическая производная: \(\frac{\zeta'(s)}{\zeta(s)} = -\sum_{p} \frac{\ln p}{p^s - 1}\).
3. Формула Перрона: Позволяет выразить \(\pi(x)\) через контурный интеграл от \(\frac{\zeta'(s)}{\zeta(s)} \cdot \frac{x^s}{s}\).
4. Отсутствие нулей на \(\Re(s) = 1\): Доказывается, что \(\zeta(1 + it) \neq 0\) для всех \(t \in \mathbb{R}\). Это ключевой момент, так как полюс в \(s=1\) даёт главный член асимптотики.
5. Оценка остатка: Сдвиг контура интегрирования влево от прямой \(\Re(s) = 1\) с учётом нулей дзета-функции даёт оценку погрешности.

¶Элементарное доказательство

Элементарное доказательство Сельберга и Эрдёша (1949) не использует комплексный анализ, но основано на комбинаторных тождествах, в частности на неравенстве Сельберга: \[ \sum_{p \le x} \ln^2 p + \sum_{pq \le x} \ln p \ln q = 2x \ln x + O(x), \] где сумма берётся по простым числам \(p\) и \(q\). Из этого неравенства выводится, что \(\pi(x) \sim x / \ln x\) без привлечения дзета-функции.

¶Уточнения и обобщения

¶Оценка погрешности

Точная оценка разности между \(\pi(x)\) и \(\operatorname{Li}(x)\) зависит от распределения нулей дзета-функции. При условии гипотезы Римана (о том, что все нетривиальные нули \(\zeta(s)\) лежат на прямой \(\Re(s) = 1/2\)) получается: \[ \pi(x) = \operatorname{Li}(x) + O(\sqrt{x} \ln x). \] Без гипотезы Римана наилучшая известная оценка (Валле-Пуссен, 1899) имеет вид: \[ \pi(x) = \operatorname{Li}(x) + O(x e^{-c\sqrt{\ln x}}), \] где \(c\) — положительная константа.

¶Теорема о простых числах в арифметических прогрессиях

Обобщение теоремы на простые числа, принадлежащие арифметическим прогрессиям \(a \mod q\) с \(\gcd(a, q) = 1\), утверждает, что простые числа распределены равномерно по всем допустимым классам вычетов. Для функции \(\pi(x; q, a)\) — количества простых чисел \(p \le x\) с \(p \equiv a \pmod{q}\) — выполняется: \[ \pi(x; q, a) \sim \frac{1}{\varphi(q)} \cdot \frac{x}{\ln x}, \] где \(\varphi(q)\) — функция Эйлера. Это было доказано Валле-Пуссеном в 1896 году для фиксированных \(q\) и позже обобщено на \(q\), растущие с \(x\).

¶Теорема о простых числах в коротких интервалах

Более тонкие результаты касаются распределения простых чисел в интервалах вида \((x, x + h(x))\). При \(h(x) = x^\theta\) с \(\theta > 0\) известно, что для \(\theta > 1/2\) (при гипотезе Римана) или \(\theta > 0.525\) (без неё) в таких интервалах всегда есть простые числа для достаточно больших \(x\).

¶Применение

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

Распределение простых чисел лежит в основе криптосистем с открытым ключом, таких как RSA, где безопасность основана на сложности разложения больших чисел на простые множители. Теорема гарантирует, что для генерации ключей достаточно большие простые числа существуют в изобилии: вероятность того, что случайное число около \(x\) является простым, составляет примерно \(1 / \ln x\).

¶Теория чисел

Теорема является краеугольным камнем аналитической теории чисел. Она используется для оценки сумм, связанных с простыми числами, например, суммы \(\sum_{p \le x} 1/p \sim \ln \ln x\) (теорема Мертенса).

¶Вычислительные алгоритмы

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

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

• Ошибка аппроксимации: Несмотря на асимптотическую эквивалентность, функция \(\operatorname{Li}(x)\) всегда больше \(\pi(x)\) для всех проверенных значений \(x\) до \(10^{25}\). Однако в 1914 году Джон Литлвуд доказал, что знак разности \(\operatorname{Li}(x) - \pi(x)\) меняется бесконечно много раз. Первое такое изменение, по оценкам, происходит при \(x\) около \(10^{316}\).
• Скорость сходимости: Отношение \(\pi(x) / (x / \ln x)\) стремится к 1 очень медленно. Например, при \(x = 10^9\) оно равно примерно 1.053, а при \(x = 10^{12}\) — 1.031.
• Рекорды вычислений: На 2024 год наибольшее значение \(\pi(x)\) вычислено для \(x = 10^{28}\) (около \(1.6 \times 10^{27}\) простых чисел). Эти вычисления используются для проверки гипотезы Римана.

¶Критика и открытые вопросы

Несмотря на доказательство теоремы, остаются нерешённые проблемы:

• Гипотеза Римана: Если она верна, то оценка погрешности теоремы может быть значительно улучшена. Это одна из важнейших нерешённых задач математики.
• Распределение простых чисел-близнецов: Теорема не даёт информации о парах простых чисел, отличающихся на 2 (например, 11 и 13). Гипотеза о бесконечности таких пар остаётся недоказанной.
• Простые числа в коротких интервалах: Неизвестно, всегда ли существует простое число между \(n^2\) и \((n+1)^2\) для всех \(n\) (гипотеза Лежандра).

¶Источники

• Адамар Ж., Валле-Пуссен Ш. Доказательство теоремы о распределении простых чисел (1896).
• Риман Б. «О числе простых чисел, не превышающих заданной величины» (1859).
• Сельберг А. «Элементарное доказательство теоремы о распределении простых чисел» (1949).
• Эрдёш П. «О новом методе в теории чисел» (1949).
• Карацуба А. А. «Основы аналитической теории чисел» (1975).
• Иванс М. «Теорема о распределении простых чисел: история и современное состояние» (2003).