В математике теорема о простых числах ( PNT ) описывает асимптотическое распределение простых чисел среди натуральных чисел. Он формализует интуитивную идею о том, что простые числа становятся менее распространенными по мере их увеличения, путем точного количественного определения скорости, с которой это происходит. Теорема была независимо доказана Жаком Адамаром [1] и Шарлем Жаном де ла Валле Пуссеном [2] в 1896 году с использованием идей Бернхарда Римана (в частности, дзета-функции Римана ).
Первое найденное такое распределение — π ( N ) ~Н/журнал ( Н ), где π ( N ) — функция подсчета простых чисел (количество простых чисел, меньше или равное N ) , а log( N ) — натуральный логарифм N . Это означает, что для достаточно большого N вероятность того , что случайное целое число, не большее N , является простым, очень близка к 1/log( N ) . Следовательно, случайное целое число, содержащее не более 2 n цифр (при достаточно большом n ), примерно в два раза реже будет простым, чем случайное целое число, содержащее не более n цифр. Например, среди натуральных чисел длиной не более 1000 цифр примерно одно из 2300 является простым ( log(10 1000 ) ≈ 2302,6 ), тогда как среди натуральных чисел длиной не более 2000 цифр примерно одно из 4600 является простым ( log(10 2000 ) ≈ 4605,2 ). Другими словами, средний разрыв между последовательными простыми числами среди первых N целых чисел примерно равен log( N ) . [3]
Пусть π ( x ) — функция подсчета простых чисел , определенная как количество простых чисел, меньших или равных x , для любого действительного числа x . Например, π (10) = 4 , потому что есть четыре простых числа (2, 3, 5 и 7), меньшие или равные 10. Тогда теорема о простых числах утверждает, что x / log x является хорошим приближением к π ( x ) (где log здесь означает натуральный логарифм) в том смысле, что предел частного двух функций π ( x ) и x / log x при неограниченном увеличении x равен 1:
известный как асимптотический закон распределения простых чисел . Используя асимптотические обозначения, этот результат можно переформулировать как
Эти обозначения (и теорема) ничего не говорят о пределе разности двух функций при неограниченном увеличении x . Вместо этого теорема утверждает, что x / log x приближает π ( x ) в том смысле, что относительная ошибка этого приближения приближается к 0 по мере неограниченного увеличения x .
Теорема о простых числах эквивалентна утверждению, что n- е простое число p n удовлетворяет условию
асимптотические обозначения, опять же, означают, что относительная ошибка этого приближения приближается к 0 по мере неограниченного увеличения n . Например,2 × 10 17 -е простое число8 512 677 386 048 191 063 , [4] и (2 × 10 17 )log(2 × 10 17 ) округляет до7 967 418 752 291 744 388 , относительная погрешность около 6,4%.
С другой стороны, следующие асимптотические соотношения логически эквивалентны: [5]
Как указано ниже, теорема о простых числах также эквивалентна формуле
где ϑ и ψ — первая и вторая функции Чебышева соответственно, а
где функция Мертенса .
На основании таблиц Антона Фелькеля и Юрия Веги Адриен-Мари Лежандр в 1797 или 1798 году предположила, что π ( a ) аппроксимируется функцией a /( A log a + B ) , где A и B — неуказанные константы. Во втором издании своей книги по теории чисел (1808 г.) он затем сделал более точную гипотезу с A = 1 и B = -1,08366 . Карл Фридрих Гаусс рассматривал тот же вопрос в возрасте 15 или 16 лет «в 1792 или 1793 году», по его собственным воспоминаниям, в 1849 году. [7] В 1838 году Питер Густав Лежен Дирихле придумал свою собственную аппроксимирующую функцию — логарифмический интеграл li . ( x ) (при несколько ином виде ряда, который он сообщил Гауссу). Формулы Лежандра и Дирихле предполагают одну и ту же предполагаемую асимптотическую эквивалентность π ( x ) и x / log ( x ) , указанную выше, хотя оказалось, что приближение Дирихле значительно лучше, если рассматривать различия вместо частных.
В двух статьях 1848 и 1850 годов русский математик Пафнутий Чебышев попытался доказать асимптотический закон распределения простых чисел. Его работа примечательна использованием дзета-функции ζ ( s ) для действительных значений аргумента « s », как в работах Леонарда Эйлера еще в 1737 году. Статьи Чебышева предшествовали знаменитым мемуарам Римана 1859 года, и ему удалось в доказательстве несколько более слабой формы асимптотического закона, а именно, что если предел при стремлении x к бесконечности для π ( x ) / ( x / log( x )) вообще существует, то он обязательно равен единице. [8] Ему удалось безоговорочно доказать, что это отношение ограничено сверху и снизу двумя явно заданными константами вблизи 1 для всех достаточно больших x . [9] Хотя статья Чебышева не доказала теорему о простых числах, его оценки для π ( x ) были достаточно сильными, чтобы он мог доказать постулат Бертрана о том, что существует простое число между n и 2 n для любого целого числа n ≥ 2 .
Важным документом, посвященным распределению простых чисел, были мемуары Римана 1859 года « О числе простых чисел, меньших заданной величины », единственная статья, которую он когда-либо писал на эту тему. Риман внес в эту тему новые идеи, главным образом, о том, что распределение простых чисел тесно связано с нулями аналитически расширенной дзета-функции Римана комплексной переменной. В частности, именно в этой работе зарождается идея применить методы комплексного анализа к исследованию действительной функции π ( x ) . Развивая идеи Римана, два доказательства асимптотического закона распределения простых чисел были независимо найдены Жаком Адамаром [1] и Шарлем Жаном де ла Валле Пуссеном [2] и появились в одном и том же году (1896 г.). В обоих доказательствах использовались методы комплексного анализа, устанавливающие в качестве основного шага доказательства, что дзета-функция Римана ζ ( s ) отлична от нуля для всех комплексных значений переменной s , которые имеют форму s = 1 + it с t > 0 . [10]
В 20 веке теорема Адамара и Валле Пуссена также стала известна как теорема о простых числах. Было найдено несколько различных доказательств этого, в том числе «элементарные» доказательства Атле Сельберга [11] и Пауля Эрдеша [12] (1949). Оригинальные доказательства Адамара и Валле Пуссена длинные и тщательно продуманные; более поздние доказательства вводили различные упрощения за счет использования тауберовых теорем , но оставались трудными для понимания. Краткое доказательство было обнаружено в 1980 году американским математиком Дональдом Дж. Ньюманом . [13] [14] Доказательство Ньюмана, возможно, является самым простым известным доказательством теоремы, хотя оно и неэлементарно в том смысле, что использует интегральную теорему Коши из комплексного анализа.
Вот набросок доказательства, упомянутого в одной из лекций Теренса Тао . [15] Как и большинство доказательств PNT, оно начинается с переформулировки проблемы в терминах менее интуитивной, но более эффективной функции подсчета простых чисел. Идея состоит в том, чтобы посчитать простые числа (или связанный с ними набор, например набор степеней простых чисел) с весами , чтобы получить функцию с более гладким асимптотическим поведением. Наиболее распространенной такой обобщенной считающей функцией является функция Чебышева ψ ( x ) , определяемая формулой
Иногда это пишут как
где Λ ( n ) — функция Мангольдта , а именно
Теперь относительно легко проверить, что PNT эквивалентно утверждению, что
Действительно, это следует из простых оценок
и (используя обозначение big O ) для любого ε > 0 ,
Следующий шаг — найти полезное представление для ψ ( x ) . Пусть ζ ( s ) — дзета-функция Римана. Можно показать, что ζ ( s ) связана с функцией фон Мангольдта Λ ( n ) и, следовательно, с ψ ( x ) соотношением
Тонкий анализ этого уравнения и связанных с ним свойств дзета-функции с использованием преобразования Меллина и формулы Перрона показывает, что для нецелого числа x уравнение
где сумма ведется по всем нулям (тривиальным и нетривиальным) дзета-функции. Эта поразительная формула является одной из так называемых явных формул теории чисел и уже наводит на мысль о результате, который мы хотим доказать, поскольку член x (который считается правильным асимптотическим порядком ψ ( x ) ) появляется справа. -сторона, за которой следуют (предположительно) асимптотические члены низшего порядка.
Следующий шаг доказательства предполагает исследование нулей дзета-функции. Тривиальные нули −2, −4, −6, −8, ... можно обрабатывать отдельно:
который исчезает при больших x . Нетривиальные нули, а именно нули в критической полосе 0 ⩽ Re( s ) ⩽ 1 , потенциально могут иметь асимптотический порядок, сравнимый с основным членом x , если Re( ρ ) = 1 , поэтому нам нужно показать, что все нули имеют действительные значения. часть строго меньше 1.
Для этого примем как данность, что ζ ( s ) мероморфна в полуплоскости Re( s ) > 0 и аналитична там, за исключением простого полюса в точке s = 1 , и что существует формула произведения
для Re( s ) > 1 . Эта формула произведения следует из существования уникальной простой факторизации целых чисел и показывает, что ζ ( s ) никогда не равняется нулю в этой области, так что ее логарифм определен там и
Напишите s = x + iy ; затем
Теперь обратите внимание на тождество
так что
для всех х > 1 . Предположим теперь, что ζ (1 + iy ) = 0 . Конечно, y не равен нулю, поскольку ζ ( s ) имеет простой полюс в точке s = 1 . Предположим, что x > 1 и пусть x стремится к 1 сверху. Поскольку имеет простой полюс в точке s = 1 и ζ ( x + 2 iy ) остается аналитическим, левая часть предыдущего неравенства стремится к 0, противоречие.
Наконец, мы можем заключить, что PNT эвристически верна. Чтобы строго завершить доказательство, необходимо преодолеть еще серьезные технические трудности, связанные с тем, что суммирование по дзета-нулим в явной формуле для ψ ( x ) сходится не абсолютно, а только условно и в смысле «главного значения». Существует несколько способов решения этой проблемы, но многие из них требуют весьма тонких комплексно-аналитических оценок. В книге Эдвардса [16] приводятся подробности. Другой метод — использовать тауберову теорему Икехары , хотя эту теорему доказать довольно сложно. Дж. Ньюман заметил, что для теоремы о простых числах не требуется полная сила теоремы Икехары, и можно обойтись частным случаем, который гораздо легче доказать.
DJ Ньюман дает быстрое доказательство теоремы о простых числах (PNT). Доказательство является «неэлементарным», поскольку основано на комплексном анализе, но использует только элементарные методы из первого курса предмета: интегральную формулу Коши , интегральную теорему Коши и оценки комплексных интегралов. Вот краткая схема этого доказательства. Подробную информацию см. в [14] .
В доказательстве используются те же предварительные сведения, что и в предыдущем разделе, за исключением того , что вместо функции используется функция Чебышева , которая получается удалением некоторых членов из ряда для . Легко показать, что PNT эквивалентен . Аналогично вместо функции используется отбрасывание некоторых членов ряда для . Функции и отличаются функцией, голоморфной на . Поскольку, как было показано в предыдущем разделе, не имеет нулей на прямой , не имеет особенностей на .
Еще одна часть информации, необходимая для доказательства Ньюмана и являющаяся ключом к оценкам в его простом методе, — это то, что она ограничена. Это доказывается остроумным и простым методом Чебышева.
Интегрирование по частям показывает, как и связаны между собой. Для ,
Метод Ньюмана доказывает PNT, показывая интеграл
сходится, и поэтому подынтегральная функция обращается в ноль при , что и есть PNT. В общем, сходимость несобственного интеграла не означает, что подынтегральная функция обращается в ноль на бесконечности, поскольку она может колебаться, но поскольку она возрастает, это легко показать в этом случае.
Чтобы показать сходимость , пусть
затем
что равно функции, голоморфной на прямой .
Сходимость интеграла и, следовательно, PNT доказывается, показывая, что . Это предполагает изменение порядка пределов, поскольку это можно записать и, следовательно, классифицировать как тауберову теорему.
Разница выражается с использованием интегральной формулы Коши , а затем показывается, что она мала при большом путем оценки подынтегральной функции. Зафиксируйте и такой, который голоморфен в области где , и пусть – граница этой области. Поскольку 0 находится внутри области, интегральная формула Коши дает
где – множитель, введенный Ньюманом, который не меняет интеграл, поскольку целочислен и .
Для оценки интеграла разобьем контур на две части, где и . Тогда где . Поскольку , и, следовательно , ограничено, пусть – верхняя граница абсолютного значения . Эта связь вместе с оценкой для дает, что первый интеграл по абсолютной величине равен . Подынтегральное выражение во втором интеграле является целым , поэтому по интегральной теореме Коши контур можно преобразовать в полукруг радиуса в левой полуплоскости без изменения интеграла, и тот же аргумент, что и для первого интеграла, дает абсолютное значение второго интеграла . Наконец, полагая , третий интеграл обращается в ноль, так как и, следовательно , обращается в ноль на контуре. Объединив две оценки и предел, получим
Это справедливо для любого so , и отсюда следует PNT.
В рукописной заметке к переизданию своей статьи 1838 года « Sur l'usage des infinies dans la theorie des nombres », которую он отправил Гауссу, Дирихле предположил (в несколько иной форме, апеллирующей к ряду, а не к интегралу), что еще лучшее приближение к π ( x ) дается смещенной логарифмической интегральной функцией Li( x ) , определенной формулой
Действительно, этот интеграл убедительно свидетельствует о том, что «плотность» простых чисел вокруг t должна быть 1/log t . Эта функция связана с логарифмом асимптотическим разложением
Итак, теорему о простых числах также можно записать как π ( x ) ~ Li ( x ) . Действительно, в другой работе [17] 1899 г. де ла Валле Пуссен доказал, что
для некоторой положительной константы a , где O ( ...) — это большое обозначение O. Это было улучшено до
В 2016 году Труджиан доказал явную верхнюю границу разницы между и :
для . [19]
Связь между дзета-функцией Римана и π ( x ) является одной из причин, по которой гипотеза Римана имеет большое значение в теории чисел: если она будет установлена, она даст гораздо лучшую оценку ошибки, связанной с теоремой о простых числах, чем доступна сегодня. Более конкретно, Хельге фон Кох показал в 1901 году [20] , что если гипотеза Римана верна, то член ошибки в приведенном выше соотношении можно улучшить до
(последняя оценка фактически эквивалентна гипотезе Римана). Константа, входящая в обозначение большого О , была оценена в 1976 году Лоуэллом Шенфельдом : [21] приняв гипотезу Римана:
для всех x ≥ 2657 . Он также получил аналогичную оценку для функции Чебышева, считающей простые числа ψ :
для всех x ≥ 73,2 . Было показано, что эта последняя граница выражает отклонение от закона средней степени (если рассматривать его как случайную функцию над целыми числами) и1/ ж шума и также соответствовать распределению Пуассона для соединения Твиди . (Распределения Твиди представляют собой семейство масштабно-инвариантных распределений, которые служат фокусами сходимости для обобщения центральной предельной теоремы . [22] ).
Логарифмический интеграл li( x ) больше π ( x ) для «маленьких» значений x . Это потому, что он (в некотором смысле) считает не простые числа, а степени простых чисел, где степень p n простого числа p считается как1/ н простого числа. Это говорит о том, что li( x ) обычно должно быть примерно больше π ( x ) и, в частности, всегда должно быть больше π ( x ) . Однако в 1914 году Дж. Э. Литтлвуд доказал, что меняет знак бесконечно часто. [23] Первое значение x , при котором π ( x ) превышает li ( x ), вероятно, составляет около x ~ 10.316 ; более подробную информациюсм. в статье ономере Скьюза(С другой стороны,смещенный логарифмический интеграл Li( x )меньше π ( x )уже для x = 2; действительно,Li(2) = 0, а π (2) = 1.)
В первой половине двадцатого века некоторые математики (особенно Г.Х. Харди ) полагали, что в математике существует иерархия методов доказательства в зависимости от того, какие виды чисел ( целые , действительные , комплексные ) требуются для доказательства, и что теорема о простых числах (PNT) является «глубокой» теоремой, поскольку требует комплексного анализа . [24] Это убеждение было несколько поколеблено доказательством PNT, основанным на тауберовой теореме Винера , хотя от этого можно было бы отказаться, если бы считалось, что теорема Винера имеет «глубину», эквивалентную таковой у методов комплексных переменных.
В марте 1948 года Атле Сельберг «элементарными» средствами установил асимптотическую формулу
где
для простых чисел p . [11] К июлю того же года Сельберг и Пол Эрдеш [12] получили элементарные доказательства PNT, оба используя асимптотическую формулу Сельберга в качестве отправной точки. [24] [25] Эти доказательства фактически положили конец представлению о том, что PNT был «глубоким» в этом смысле, и показали, что технически «элементарные» методы были более мощными, чем считалось. Об истории элементарных доказательств PNT, включая спор о приоритете Эрдеша-Сельберга , см. статью Дориана Голдфельда . [24]
Существуют некоторые споры о значении результата Эрдеша и Сельберга. В теории чисел не существует строгого и общепринятого определения понятия элементарного доказательства , поэтому неясно, в каком именно смысле их доказательство является «элементарным». Хотя он не использует сложный анализ, на самом деле он гораздо более технический, чем стандартное доказательство PNT. Одно из возможных определений «элементарного» доказательства — это «то, которое может быть выполнено с помощью арифметики Пеано первого порядка ». Существуют теоретико-числовые утверждения (например, теорема Пэрис-Харрингтона ), доказуемые с использованием методов второго , но не первого порядка , но такие теоремы на сегодняшний день редки. Доказательство Эрдеша и Сельберга, безусловно, можно формализовать в арифметике Пеано, а в 1994 году Хараламбос Корнарос и Костас Димитракопулос доказали, что их доказательство можно формализовать в очень слабом фрагменте PA, а именно I ∆ 0 + exp . [26] Однако это не решает вопрос о том, может ли стандартное доказательство PNT быть формализовано в PA.
В 2005 году Авигад и др. использовал средство доказательства теоремы Изабель, чтобы разработать проверенный на компьютере вариант доказательства PNT Эрдеша – Сельберга. [27] Это было первое подтвержденное машиной доказательство PNT. Авигад решил формализовать доказательство Эрдеша-Сельберга, а не аналитическое, потому что, хотя библиотека Изабель в то время могла реализовать понятия предела, производной и трансцендентной функции , в ней почти не было теории интегрирования, о которой можно было бы говорить. [27] : 19
В 2009 году Джон Харрисон использовал HOL Light для формализации доказательства с помощью комплексного анализа . [28] Разработав необходимый аналитический аппарат, включая интегральную формулу Коши , Харрисон смог формализовать «прямое, современное и элегантное доказательство вместо более сложного« элементарного »аргумента Эрдеша-Сельберга».
Пусть π d , a ( x ) обозначает количество простых чисел в арифметической прогрессии a , a + d , a + 2 d , a + 3 d , ... которые меньше x . Дирихле и Лежандр предположили, а де ла Валле Пуссен доказали, что если a и d взаимно просты , то
где φ — функция тотента Эйлера . Другими словами, простые числа распределяются равномерно среди классов вычетов [ a ] по модулю d с НОД( a , d ) = 1 . Это сильнее, чем теорема Дирихле об арифметических прогрессиях (которая лишь утверждает, что в каждом классе существует бесконечное число простых чисел) и может быть доказана с использованием аналогичных методов, использованных Ньюманом для доказательства теоремы о простых числах. [29]
Теорема Зигеля –Вальфиса дает хорошую оценку распределения простых чисел в классах вычетов.
Беннетт и др. В [30] доказана следующая оценка, имеющая явные константы A и B (теорема 1.3): Пусть d — целое число, и пусть a — целое число, взаимно простое с d . Тогда существуют положительные константы A и B такие, что
где
и
Хотя у нас, в частности,
эмпирически простые числа, соответствующие 3, более многочисленны и почти всегда опережают в этой «гонке простых чисел»; первый разворот происходит в точке x = 26861 . [31] : 1–2 Однако в 1914 г. Литтлвуд показал [31] : 2 , что существует бесконечно много смен знака функции
поэтому лидерство в гонке меняется туда и обратно бесконечное число раз. Явление того, что π 4,3 ( x ) большую часть времени опережает, называется смещением Чебышева . Гонка простых чисел распространяется на другие модули и является предметом многочисленных исследований; Пал Туран спросил, всегда ли π ( x ; a , c ) и π ( x ; b , c ) меняются местами, когда a и b взаимно просты с c . [32] Гранвиль и Мартин дают подробное изложение и обзор. [31]
Теорема о простых числах является асимптотическим результатом. Это дает неэффективную оценку π ( x ) как прямое следствие определения предела: для всех ε > 0 существует S такое, что для всех x > S ,
Однако известны лучшие оценки π ( x ) , например , Пьера Дюсара .
Первое неравенство справедливо для всех x ≥ 599 , а второе — для x ≥ 355991 . [33]
Более слабая, но иногда полезная оценка для x ≥ 55 : [34]
В диссертации Пьера Дюсара есть более сильные версии неравенства этого типа, справедливые для больших x . Позже в 2010 году Дюсарт доказал: [35]
Доказательство де ла Валле Пуссена подразумевает следующее: для каждого ε > 0 существует S такое, что для всех x > S ,
Как следствие теоремы о простых числах, получается асимптотическое выражение для n - го простого числа, обозначаемого pn :
Лучшее приближение: [36]
Опять учитывая2 × 10 17 -е простое число8 512 677 386 048 191 063 , это дает оценку8 512 681 315 554 715 386 ; первые 5 цифр совпадают, и относительная ошибка составляет около 0,00005%.
Теорема Россера утверждает, что
Это можно улучшить с помощью следующей пары оценок: [34] [37]
В таблице сравниваются точные значения π ( x ) с двумя приближениями x / log x и li ( x ) . Последний столбец, x / π ( x ) , представляет собой средний разрыв простых чисел ниже x .
Значение π (10 24 ) первоначально было рассчитано с учетом гипотезы Римана ; [38] с тех пор это было подтверждено безоговорочно. [39]
Существует аналог теоремы о простых числах, описывающий «распределение» неприводимых многочленов по конечному полю ; форма, которую он принимает, поразительно похожа на случай классической теоремы о простых числах.
Точнее говоря, пусть F = GF( q ) будет конечным полем с q элементами для некоторого фиксированного q , и пусть N n будет числом монических неприводимых многочленов над F , степень которых равна n . То есть мы рассматриваем полиномы с коэффициентами, выбранными из F , которые нельзя записать как произведения полиномов меньшей степени. В этом случае эти многочлены играют роль простых чисел, поскольку все остальные монические многочлены состоят из их произведений. Тогда можно доказать, что
Если мы сделаем замену x = q n , то правая часть будет просто
что делает аналогию более понятной. Поскольку существует ровно qn монических полиномов степени n (включая приводимые), это можно перефразировать следующим образом: если монический многочлен степени n выбран случайно, то вероятность того, что он будет неприводимым, равна примерно 1/н.
Можно даже доказать аналог гипотезы Римана, а именно, что
Доказательства этих утверждений гораздо проще, чем в классическом случае. Он включает в себя короткий комбинаторный аргумент, который в [40] резюмируется следующим образом: каждый элемент расширения F степени n является корнем некоторого неприводимого многочлена, степень d которого делит n ; подсчитав эти корни двумя разными способами, можно установить, что
где сумма ведется по всем делителям d числа n . Тогда обращение Мёбиуса дает
где µ ( k ) — функция Мёбиуса . (Эта формула была известна Гауссу.) Главный член встречается при d = n , и нетрудно оценить остальные члены. Утверждение «гипотезы Римана» основано на том факте , что наибольший собственный делитель n не может быть больше, чемн/2.