Теорема о простых числах (Prime Number Theorem) - Закон, по которому распределение простых чисел приближается к логарифмической функции

Что такое Теорема о простых числах?

Одним из самых красивых результатов в области математики является Теорема о простых числах (Prime Number Theorem, PNT). Она показывает, что простые числа, которые на первый взгляд появляются нерегулярно и случайно, при макроскопическом рассмотрении обладают удивительно плавной закономерностью.

В частности, если обозначить “количество простых чисел, не превышающих некоторое действительное число \(x\)” как \(\pi(x)\) (функция распределения простых чисел), теорема утверждает, что при очень большом \(x\), \(\pi(x)\) асимптотически приближается к \(x / \ln(x)\).

\[ \lim_{x \to \infty} \frac{\pi(x)}{x / \ln(x)} = 1 \]

Здесь \(\ln(x)\) обозначает натуральный логарифм (с основанием \(e\)). Эта теорема утверждает удивительный факт, что распределение простых чисел глубоко связано с натуральным логарифмом.

Функция распределения простых чисел \(\pi(x)\)

Функция распределения простых чисел \(\pi(x)\) — это функция, которая подсчитывает количество простых чисел, не превышающих \(x\). Например:

\(\pi(10) = 4\) (2, 3, 5, 7)
\(\pi(100) = 25\)
\(\pi(1000) = 168\)

По мере увеличения чисел находить простые числа становится сложнее, и интервалы между их появлениями постепенно увеличиваются. Однако “плотность” в целом становится предсказуемой.

  graph TD;
    A["Натуральное число x"] -->|"Подсчет простых чисел"| B["Функция распределения простых чисел π(x)"];
    B -->|"Аппроксимирует"| C["x / ln(x)"];
    C -->|"Повышает точность"| D["Интегральный логарифм Li(x)"];

Исторический контекст: От гипотезы Гаусса до доказательства

История Теоремы о простых числах восходит к концу 18 века. Гениальный математик Карл Фридрих Гаусс, которому было всего 15 лет, изучая таблицы простых чисел, заметил, что частота появления простых чисел связана с логарифмической функцией. Примерно в то же время Адриен-Мари Лежандр независимо выдвинул аналогичную гипотезу.

Однако они не смогли дать строгого доказательства этого.

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

\[ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ простое}} \left(1 - \frac{1}{p^s}\right)^{-1} \]

Эта формула эйлерова произведения (Euler product formula) является очень важным соотношением, связывающим функцию суммы по всем натуральным числам (левая часть) с бесконечным произведением только по простым числам (правая часть).

Впоследствии, в 1896 году, Жак Адамар и Шарль де ла Валле-Пуссен независимо друг от друга завершили доказательство Теоремы о простых числах, основываясь на идеях Римана. Ключом к их доказательству было показать, что “Дзета-функция Римана \(\zeta(s)\) не имеет нулей на прямой \(\operatorname{Re}(s) = 1\) комплексной плоскости”.

Более точная аппроксимация: Интегральный логарифм \(\operatorname{Li}(x)\)

Хотя \(x / \ln(x)\) просто выражает Теорему о простых числах, для аппроксимации фактического количества простых чисел \(\pi(x)\) гораздо лучше подходит интегральный логарифм (Logarithmic Integral, \(\operatorname{Li}(x)\)), введенный Гауссом.

Интегральный логарифм определяется следующим образом:

\[ \operatorname{Li}(x) = \int_{2}^{x} \frac{dt}{\ln(dt)} \]

Теорему о простых числах также можно переписать как \(\pi(x) \sim \operatorname{Li}(x)\).

\[ \lim_{x \to \infty} \frac{\pi(x)}{\operatorname{Li}(x)} = 1 \]

На самом деле, при \(x = 10^{10}\):

\(\pi(10^{10}) = 455,052,511\)
\(10^{10} / \ln(10^{10}) \approx 434,294,481\) (погрешность около 4.5%)
\(\operatorname{Li}(10^{10}) \approx 455,055,614\) (погрешность всего 3103)

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

Глубокая связь с гипотезой Римана

Неразрывно с Теоремой о простых числах связана гипотеза Римана (Riemann Hypothesis), которая считается самой важной нерешенной проблемой в математике.

Гипотеза Римана утверждает, что “все нетривиальные нули дзета-функции Римана \(\zeta(s)\) лежат на прямой, действительная часть которой равна \(1/2\) (критической прямой)”.

Если гипотеза Римана будет доказана как верная, мы получим сильнейшую оценку остаточного члена в Теореме о простых числах (разницы между \(\pi(x)\) и \(\operatorname{Li}(x)\)). В частности, известно, что существует некоторая константа \(C\), такая что:

\[ |\pi(x) - \operatorname{Li}(x)| \le C \sqrt{x} \ln(x) \]

Это означает, что “простые числа распределены настолько исключительно регулярно, что это неотличимо от совершенно случайного распределения”. Другими словами, Теорема о простых числах говорит о “среднем” распределении простых чисел, а гипотеза Римана говорит о пределе этого “колебания (погрешности)”.

Проверка Теоремы о простых числах с помощью Python

Давайте на практике с помощью программирования понаблюдаем за поведением Теоремы о простых числах.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import math
import matplotlib.pyplot as plt

def sieve_of_eratosthenes(limit):
    """
    Использование решета Эратосфена для перечисления простых чисел
    """
    is_prime = [True] * (limit + 1)
    p = 2
    while (p * p <= limit):
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1
    
    primes = [p for p in range(2, limit) if is_prime[p]]
    return primes

def pi(x, primes):
    """
    Возвращает количество простых чисел, не превышающих x
    """
    import bisect
    return bisect.bisect_right(primes, x)

limit = 1000000
primes = sieve_of_eratosthenes(limit)

x_values = [10**i for i in range(1, 7)]
pi_values = [pi(x, primes) for x in x_values]
approx_values = [x / math.log(x) for x in x_values]

print(f"{'x':<10} | {'π(x)':<10} | {'x / ln(x)':<15} | {'Отношение'}")
print("-" * 55)
for i in range(len(x_values)):
    x = x_values[i]
    pi_x = pi_values[i]
    approx = approx_values[i]
    ratio = pi_x / approx
    print(f"{x:<10} | {pi_x:<10} | {approx:<15.2f} | {ratio:.4f}")

Если выполнить этот код, можно наблюдать, как по мере увеличения \(x\) отношение \(\pi(x) / (x/\ln(x))\) приближается к 1. Это является одним из веских доказательств Теоремы о простых числах.

Применение в современной криптографии

Свойства простых чисел являются не просто интересным объектом в чистой математике, но и важным элементом, поддерживающим основы безопасности современного общества.

Алгоритмы криптографии с открытым ключом, такие как RSA, используют свойство “чрезвычайной сложности факторизации огромных целых чисел”. Теорема о простых числах гарантирует, с какой вероятностью можно найти “простое число подходящего размера”, необходимое для генерации криптографического ключа.

Например, вероятность того, что случайное 1024-битное нечетное число является простым, оценивается примерно как \(1 / (1024 \times \ln(2) / 2) \approx 1 / 355\). Это означает, что если выполнить несколько сотен проверок на простоту, можно с высокой вероятностью найти необходимое огромное простое число, и без Теоремы о простых числах построение эффективных криптографических систем было бы невозможно.

Заключение

Теорема о простых числах — одна из самых красивых теорем, олицетворяющих “порядок в хаосе” в математике. Тот факт, что за казалось бы случайным распределением простых чисел скрывается фундаментальный закон природы — логарифмическая функция, продолжает очаровывать многих математиков.

Эта область, открытая гениями Гауссом, Риманом и Адамаром, до сих пор остается на переднем крае современной математики благодаря огромной нерешенной проблеме — гипотезе Римана. Загадки простых чисел глубоки, и наши исследования будут продолжаться до того дня, пока мы не поймем их картину в полном объеме.