Итак, сколько же имеется простых чисел, не превышающих некоторую заданную величину? Очень скоро мы это узнаем, но сначала — пятиминутное повторение на тему простых чисел.

Возьмем положительное целое число — для примера, 28. Какие числа делят его нацело? Ответ таков: 1, 2, 4, 7, 14 и 28. Эти числа называются делителями числа 28. Будем говорить, что «28 имеет шесть делителей».

Разумеется, каждое число делится на 1; и каждое делится само на себя. Так что единица и само число — не слишком интересные делители. Если использовать слово, которое математики очень любят, — это «тривиальные» делители. Интересные же делители в нашем случае — это 2, 4, 7 и 14. О них говорят как о собственных делителях.

Получаем, что у числа 28 четыре собственных делителя. Но у числа 29 собственных делителей нет вовсе. Ничто не делит число 29 нацело, кроме, конечно, 1 и 29. Это — простое число. Простое число — это такое, у которого нет собственных делителей.

Приведем все простые числа, не превосходящие 1000.

  2   3   5   7  11  13  17  19

 23  29  31  37  41  43  47  53

 59  61  67  71  73  79  83  89

 97 101 103 107 109 113 127 131

137 139 149 151 157 163 167 173

179 181 191 193 197 199 211 223

227 229 233 239 241 251 257 263

269 271 277 281 283 293 307 311

313 317 331 337 347 349 353 359

367 373 379 383 389 397 401 409

419 421 431 433 439 443 449 457

461 463 467 479 487 491 499 503

509 521 523 541 547 557 563 569

571 577 587 593 599 601 607 613

617 619 631 641 643 647 653 659

661 673 677 683 691 701 709 719

727 733 739 743 751 757 761 769

773 787 797 809 811 821 823 827

829 839 853 857 859 863 877 881

883 887 907 911 919 929 937 941

947 953 967 971 977 983 991 997

Как видно, их 168. В этот момент обычно раздаются возражения, что в список простых чисел не включена единица. Разве единица не удовлетворяет определению? Ну, строго говоря, да — удовлетворяет, и закоренелые педанты могут для своего собственного удовлетворения вписать «1» в начало списка. Однако включение 1 в список простых чисел — серьезная помеха, и современные математики по взаимному согласию этого просто не делают. (Последним из крупных математиков, кто такое делал, был Анри Лебег в 1899 году.) На самом деле даже включение двойки — тоже помеха; однако присутствие 2 в конце концов себя окупает, а присутствие 1 — нет, так что мы ее выбрасываем, и все.

Если посмотреть на список простых чисел повнимательнее, то станет заметно, что они скудеют по мере продвижения вперед по списку. Между 1 и 100 имеется 25 простых; между 401 и 500 их 17; а между 901 и 100 — всего 14. Как видно, число простых в каждом блоке из сотни чисел убывает. Если бы мы продлили список, включив в него все простые числа до миллиона, то обнаружилось бы, что в последнем блоке из сотни чисел (т.е. среди чисел от 999 901 до 1000 000) всего лишь восемь простых. А если продлить до триллиона, то в последнем блоке из сотни чисел нашлись бы только четыре простых (конкретно, они таковы: 999 999 999 937, 999 999 999 959, 999 999 999 961 и 999 999 999 989).

Возникает естественный вопрос: истощатся ли рано или поздно простые числа до конца? Если продолжить список до триллионов триллионов или до триллионов триллионов триллионов триллионов, то дойдем ли мы в конце концов до точки, за которой простых чисел больше нет, так что последнее простое, встреченное нами по пути, окажется наибольшим простым числом?

Ответ на это около 300 года до P.X. дал Эвклид. Нет, простые числа не истончаются до конца. Всегда найдутся еще. Нет наибольшего простого числа. Сколь большое простое число вы бы ни взяли, всегда найдется еще большее. Простые числа продолжаются без конца. Доказательство: пусть число N — простое. Образуем такое число: (1×2×3×…×N) + 1. Оно не делится нацело ни на одно из чисел от 1 до N — в остатке всегда будет единица. Значит, или оно не имеет собственных делителей (и, следовательно, является простым числом, превосходящим N), или же наименьший из его простых делителей — некоторое число, превосходящее само N. Этим результат и доказан, поскольку наименьший собственный делитель любого числа с необходимостью является простым, ведь иначе в нем в свою очередь нашелся бы меньший делитель. Скажем, если N есть 5, то 1×2×3×4×5 + 1 есть 121, и наименьший простой делитель этого числа равен 11. С какого бы простого числа вы ни начали, вы получите большее простое. (Другое доказательство бесконечности числа простых чисел я дам в главе 7.iv, после того как покажу вам Золотой Ключ.)

При том что этот вопрос удалось урегулировать на столь раннем этапе истории математики, следующей по очереди вещью, естественным образом занимавшей головы математиков, была такая проблема: можно ли найти правило, закон для описания того, как именно истончаются простые числа? В пределах сотни имеется 25 простых чисел. Если бы простые числа были распределены строго равномерно, то, разумеется, в пределах тысячи их было бы в 10 раз больше, т.е. 250. Но из-за истончения там в действительности только 168 простых. Почему 168? Почему, скажем, не 158, или 178, или еще сколько-нибудь? Существует ли правило, формула, говорящая, сколько имеется простых чисел, меньших данного числа?

Вот мы и пришли к тому вопросу, с которого, как и Бернхард Риман, мы начали: сколько имеется простых чисел, меньших заданного числа?

А что мы можем выяснить, действуя «от готового»? Я на самом деле знаю ответы на последний вопрос для довольно внушительных чисел. Некоторые из них показаны в таблице 3.1.

Здорово, конечно, но на самом деле не слишком информативно. Да, простые числа истончаются. Если бы они продолжали появляться в том же темпе, что и в первой тысяче, где их 168, то в последней графе их было бы что-то около 168 000 000 000 000 000. Но там в действительности лишь одна седьмая этого значения.

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

Двухколоночная табличка вроде таблицы иллюстрирует понятие функции. «Функция» — одна из важнейших концепций во всей математике, вторая или третья по значимости, на мой взгляд, после «числа» и, возможно, «множества». Основная идея функции состоит в том, что некоторое число (из правой колонки) зависит от другого числа (из левой колонки) в соответствии с некоторым заданным законом или процедурой. Конкретно для таблицы процедура такова: «Посчитать, сколько имеется простых чисел в пределах, определяемых числом в левой колонке».

Другой способ сказать то же самое таков: функция — это способ превратить (математики говорят «отобразить») число в другое число. Функция в таблице согласно выбранной процедуре превращает, или отображает, число 1000 в число 168.

Профессиональные термины здесь таковы. Поскольку слишком утомительно постоянно произносить слова «число в левой колонке» и «число в правой колонке», математики говорят о них соответственно как об «аргументе» и «значении» (или «значении функции»). Итак, суть дела во всякой функции — это получить значение по заданному аргументу, следуя некоторому правилу или процедуре.

И еще один ключевой профессиональный термин. Бывает, что правило, на котором основано определение функции, можно применить к одним числам или к одному типу чисел, но не к другим или другому. Скажем, правило «вычесть из аргумента единицу и взять обратное число» определяет весьма уважаемую функцию — математик сказал бы, что это функция 1/(1 − x), и мы довольно плотно с ней познакомимся в главе 9.iii, — но это правило нельзя применить к аргументу 1, поскольку такая попытка повлекла бы за собой деление на нуль, чего в математике не разрешается. (Нет никакого толка спрашивать: «А что если я попробую?» Нельзя, и все. Это против правил. Если вы попытаетесь, то игра остановится и все вернется в последнюю разрешенную позицию.)

В качестве другого примера рассмотрим функцию, действующую по правилу «посчитать, сколько делителей имеет аргумент». Мы видим, что число 28 имеет шесть делителей (будем сейчас включать и тривиальные делители тоже), а 29 — только два. Значит, данная функция превращает 28 в 6, а 29 (как и любое другое простое число) в 2. Это еще одна уважаемая и полезная функция, как правило, обозначаемая как d(N). Однако эта функция осмысленна только для целых чисел — и даже только для положительных целых чисел. Сколько делителей у числа 12⁷/₈? Сколько делителей у числа π? Не спрашивайте. Эта функция — не для них.

Относящийся сюда профессиональный термин — это «область определения». Область определения какой-нибудь функции — это те числа, которые она допускает в качестве аргумента. Функция 1/(1 − x) допускает в качестве аргумента все числа, кроме 1. Функция d(N) допускает в качестве аргумента любое положительное целое число; это и есть ее область определения. Область определения функции √x — все неотрицательные числа, поскольку из отрицательных извлекать квадратный корень нельзя (впрочем, по этому поводу я оставляю за собой право передумать далее по тексту).

Некоторые функции допускают все числа в свою область определения. Функция возведения в квадрат x², например, применима к любому числу. Любое число можно возвести в квадрат (т.е. умножить само на себя). То же верно и для полиномиальных функций (другими словами, многочленов) — т.е. функций, значения которых получаются сложением и вычитанием степеней аргумента. Примером полиномиальной функции может служить 3x⁵ + 11x³ − 35x² − 7x + 4. Область определения полиномиальной функции — все числа. Это обстоятельство сыграет свою роль в главе 21.iii. Но наиболее интересные функции имеют определенные ограничения на свою область определения: или возникают какие-то значения аргумента, при которых правило не действует (обычно из-за того, что пришлось бы делить на нуль), или же правило вообще применимо только к определенному классу чисел.

Важно понимать, что табличка, подобная таблице , — это только модель функции. Сколько имеется простых чисел, меньших числа 31 556 926? Можно было бы ответить, внедряя в табличку дополнительные строки, но с учетом моего намерения удержать число страниц этой книги в некоторых разумных пределах имеется, очевидно, ограничение на то, сколько строк я могу вставить. Приведенная таблица — не более чем модель функции, ее «моментальный снимок», сделанный при определенных аргументах (выбранных с некоторым дальним прицелом).

На самом деле обычно не существует хорошего способа показать функцию во всей ее красе. Иллюстрировать какие-то конкретные свойства функции иногда помогает график, но в данном случае он достаточно бесполезен. Если вы попытаетесь изобразить содержимое таблицы в виде графика, вы быстро поймете, что я имею в виду. Усилия по построению графика дзета-функции, которые будут предприняты в главе 9.iv, прояснят этот момент. Математики обычно получают некоторое общее представление о конкретной функции, тесно работая с ней в течение достаточно длительного времени, наблюдая при этом за всеми ее свойствами и особенностями. С помощью таблицы или графика не часто удается охватить функцию целиком.

Еще о функциях надо заметить, что наиболее важные из них носят имена. А действительно важные обозначаются специальными символами. Функция, модель которой приведена в таблице , носит имя «функции числа простых чисел» и обозначается символом π(N), что читается как «пи от эн».

Знаю, знаю — может возникнуть путаница. Ведь π — это отношение длины окружности к ее диаметру, то самое невыразимое

Но новое использование символа π не имеет к этому числу ровно никакого отношения. В греческом алфавите всего 24 буквы, и к тому времени, как математики собрались дать имя этой функции (лично ответственный за это — Эдмунд Ландау, который ввел такое обозначение в 1909 году, — см. главу 14.iv), все 24 буквы уже были порядком израсходованы, и пришлось пустить их по кругу. Мне жаль, что так получилось, но это не моя вина. Данное обозначение в настоящий момент является абсолютно стандартным, так что его придется терпеть.

(Если вы хоть раз занимались мало-мальски серьезным программированием на компьютере, то вам знакома концепция перегрузки символа. Использование буквы π для двух совершенно различных целей есть некоторое подобие перегрузки этого символа.)

Итак, функция π(N) определена как число простых чисел до N (включая само N, хотя это довольно редко имеет значение, и я не буду особенно следить за употреблением выражений «меньших, чем» и «не превышающих»). Но вернемся к нашему основному вопросу: есть ли какое-нибудь правило, какая-нибудь изящная формула, которая даст нам значение π(N), избавив от необходимости заниматься счетом?

Позвольте мне устроить небольшой фокус с таблицей . Я поделю первую колонку на вторую — аргументы на значения. Я не гонюсь за безумной точностью. И вообще буду пользоваться карманным калькулятором за 6 долларов, с которым я хожу в супермаркет. Вот что получается: 100 разделить на 168 даст 5,9524; 1 000 000 разделить на 78 498 даст 12,7392. Еще четыре результата подобного же вычисления дают нам таблицу 3.2.

Посмотрим пристально на эти значения. Они всякий раз возрастают на 7. Точнее, на число, которое болтается между 6,8 и 7,0. Может, вам это и не кажется чем-то особенно чудесным, но когда математик видит такую таблицу, над головой у него ярко вспыхивает лампочка и определенное слово приходит ему на ум. Позвольте объяснить.

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

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

Рассмотрим пример. Возьмем правило «вычислить 5×5×5×5×… — выражение, содержащее N пятерок».

Видите, как аргумент каждый раз увеличивается путем прибавления 1, в то время как значения каждый раз увеличиваются путем умножения на 5? Это показательная функция. Аргументы увеличиваются «по сложению», а значения — «по умножению».

Я для удобства выбрал вариант, когда аргумент каждый раз увеличивается путем прибавления 1, и буду придерживаться его и далее. Для данной конкретной функции это приводит к умножению аргумента на 5. Разумеется, в числе 5 нет ничего специального. Можно было бы выбрать функцию, в которой множитель равен 2, или 22, или 761, или 1,05 (что, кстати, дало бы таблицу накопления сложных процентов при ставке в 5%), или даже 0,5. В каждом из случаев мы получим показательную функцию. Вот почему я сказал, что имеется некоторое «семейство функций».

Еще один термин, который математики обожают, — «канонический вид». В ситуации, подобной данной, когда имеется явление (в нашем случае — показательная функция), которое может проявляться многими различными способами, есть, вообще говоря, один способ, которым математики желают представить все явление. В данном случае вот какой. Есть одна показательная функция, которую математики предпочитают всем остальным. Если бы вы принялись угадывать, то, наверное, предположили бы, что это та функция, в которой множителем является число 2 — самое простое в конце концов, на что можно умножить. Но нет! Канонический вид показательной функции, предпочтительный для математиков, имеет множитель 2,718281828459045235. Это еще одно магическое число наряду с π, которое проявляет себя во всех областях математики. Оно уже встречалось нам в этой книге (см. главу 1.vii). Оно иррационально, так что последовательность знаков после запятой никогда не повторяется и его нельзя переписать в виде дроби. Символ e для этого числа был введен Леонардом Эйлером, о котором будет много всего сказано в следующей главе.

Но почему именно это число? Не слишком ли оно неуклюже, чтобы с его помощью определять канонический вид? Разве не много проще было бы с числом 2? Да, наверное, для целей умножения было бы проще. Я не могу объяснить важность числа e, не вдаваясь в вычисления, а я дал торжественный обет объяснить Гипотезу Римана с минимумом вычислений. По этой причине я просто убедительно попрошу вас принять на веру, что e — действительно, действительно важное число и что ни одна другая показательная функция не может и близко сравниться с этой e^N. Вот как выглядит наша таблица:

(здесь точность — 12 знаков после запятой). Основной принцип, конечно, сохраняется — аргументы (левая колонка) растут каждый раз за счет добавления 1; при этом значения в правой колонке каждый раз умножаются на e.

А если наоборот? Представим себе функцию, основанную на таком правиле: когда аргумент растет «по умножению», значения растут «по сложению». Что за функция получится?

Здесь мы вступаем в царство обратных функций. Математики имеют особое пристрастие к тому, чтобы обращать самые разные вещи — выворачивать их наизнанку. Если у есть 8 умножить на x, то как выразить x через y? Понятно, что это y/8. Деление обратно умножению. Еще есть такое любимое нами действие, как возведение в квадрат, когда мы умножаем число само на себя. И каково же его обращение? Если y = x², то чему равен x в терминах y? Ну да, это квадратный корень из y. Если вы немного знакомы с анализом, то знаете, что есть действие, называемое «дифференцированием», которое позволяет превратить функцию f в другую функцию — g, говорящую о том, какова мгновенная скорость изменения функции f при каждом ее аргументе. И каково же действие, обратное дифференцированию? Это интегрирование. Ну и так далее. Обращение станет ключевой темой позднее, когда мы вникнем в работу Римана 1859 года.

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

(Я полагаю, что вы помните о правиле знаков, так что −3 умножить на −3 дает 9, а не −9). А теперь поменяем колонки местами и получим обратную функцию:

Но постойте-ка! Каково же значение функции при аргументе, равном 9? Это −3 или 3? Похоже, что эта функция принимает такой вид:

Так дело не пойдет — слишком путано. Вообще-то… вообще-то существует математическая теория многозначных функций. Бернхард Риман был знатоком этой теории, и мы познакомимся с его идеями в главе 13.v. Но сейчас не время и не место для этого, и я не собираюсь тащить сюда сундук, набитый подобными вещами. Во всяком случае, что касается меня, то железное правило состоит в том, что на один аргумент — самое большее одно значение (ни одного значения, разумеется, если аргумент не лежит в области определения функции). Квадратный корень из 1 равен 1, квадратный корень из 4 равен 2, квадратный корень из 9 равен 3. Означает ли это, что я не признаю того факта, что −3 умножить на −3 даст 9? Разумеется, я его признаю, я просто не включаю его в мое определение «квадратного корня». Вот мое определение квадратного корня (по крайней мере на данный момент): квадратный корень из N есть единственное неотрицательное число (если таковое имеется), которое при умножении само на себя дает N.

По счастью, показательная функция не доставляет нам подобных хлопот. Вы можете шутя обратить ее и получить функцию, которая при выборе аргументов, получаемых друг из друга умножением, дает значения, получаемые друг из друга сложением. Разумеется, как и в случае показательных функций, обратные им функции также образуют семейство, зависящее от множителя; и, как и с показательной функцией, математикам намного, намного больше всех остальных нравится та, к значениям которой прибавляется единица, когда аргументы умножаются на e. Получаемую функцию называют логарифмической, а обозначают ln. «Логарифм!» — вот слово, которое возникло в голове математика при вспышке лампочки, когда он увидел таблицу . Если y = e^x, то x = ln y. (Отсюда, кстати, путем простой подстановки следует, что для любого положительного числа у выполнено y = e^ln y — факт, которым мы не преминем как следует воспользоваться в дальнейшем.)

В математических сюжетах, имеющих отношение к данной книге — то есть к Гипотезе Римана, — логарифмическая функция присутствует повсеместно. Мы поговорим о ней куда более подробно в главах 5 и 7, и она будет играть роль настоящей звезды нашего рассказа, когда в главе 19 мы повернем наконец Золотой Ключ. Пока же давайте примем на веру, что это — функция в только что описанном смысле, по-настоящему важная математическая функция, и при этом обратная к показательной функции: если y = e^x, то x = ln y.

Теперь я перейду прямо к сути дела и покажу вам логарифмическую функцию, но вместо того, чтобы двигаться вперед шагами, соответствующими умножению на e, давайте умножать аргументы на 1000. Как мы уже говорили, когда функцию представляют в виде таблицы, надо выбрать аргументы (а также число знаков после запятой — в нашем случае четыре). Клянусь, что это та же самая функция. Чтобы лучше было видно, что тут происходит, я справа добавил в таблицу еще две колонки: первая из них — это просто правая колонка из таблицы , а вторая выражает в процентах отклонение нашей колонки номер 2 от колонки номер 3. Результат приведен в таблице 3.3.

Представляется разумным следующее утверждение: N/π(N) близко к ln N, причем тем ближе, чем больше становится N.

У математиков есть специальная запись для этого: N/π(N) ~ ln N. (Читается так: «N, деленное на π(N), асимптотически стремится к ln N»). Волнистый знак в этой формуле по науке называется «тильда», однако, судя по моему опыту, математики нередко называют его просто «волной».

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

Разумеется, мы эту теорему не доказали — мы просто увидели, что такое утверждение правдоподобно. Это очень важный результат, настолько важный, что он называется Теоремой о распределении простых чисел. Это не какая-то там теорема о распределении простых чисел, нет, а Теорема о Распределении Простых Чисел. Специалисты по теории чисел нередко пишут просто «ТРПЧ», и в этой книге мы так и будем поступать.

И наконец, получим два следствия из ТРПЧ (в предположении, конечно, что она верна). Чтобы вывести эти следствия, сначала заметим, что в некотором смысле (логарифмическом смысле!) при работе со всеми числами вплоть до некоторого большого N большинство из этих чисел вполне сравнимы по величине с самим N. Например, среди всех чисел от 1 до одного триллиона более 90 процентов имеют 12 или более разрядов и в этом смысле вполне сравнимы с триллионом (у которого 13 разрядов), а не, скажем, с одной тысячей (с ее четырьмя разрядами).

Если на интервале от 1 до N имеется N/ln N простых чисел, то средняя плотность простых в этом интервале составляет 1/ln N. А поскольку большинство чисел в этом интервале сравнимы по размеру с числом N в том грубом смысле, который я только что описал, то справедливым будет заключение, что в районе числа N плотность простых чисел есть 1/ln N. Именно так и есть. В конце первого раздела данной главы мы подсчитали число простых в каждом блоке из 100 чисел, предшествующих 100, 500, 1000, 1 миллиону и 1 триллиону. Результаты этих подсчетов были такими: 25, 17, 14, 8 и 4. Соответствующие значения выражения 100/ln N (т.е. его значения при N = 100, 500 и т.д). с точностью до ближайшего целого числа таковы: 22, 16, 14, 7 и 4. Другой способ выразить то же самое — это сказать, что в окрестности большого числа N вероятность того, что некоторое число окажется простым, ~ 1/ln N.

Руководствуясь той же грубой логикой, можно оценить величину N-го простого числа. Рассмотрим отрезок числового ряда от 1 до K для какого-нибудь большого числа K. Если в этом интервале простых чисел, то в среднем следует ожидать, что первым простым, которое мы встретим, будет число К:C, вторым — число 2K:C, третьим — 3K:C и т.д. N-е простое будет находиться где-то около числа NK:C, а C-е (другими словами, последнее простое в этом интервале) окажется около числа K:C, что, понятно, равно просто K. И вот, если верна ТРПЧ, то количество простых чисел C есть К/ln K, а потому N-е простое в действительности встретится вблизи числа NK:(К/ln K), или, другими словами, вблизи числа Nln K. Поскольку большинство чисел в этом интервале сравнимы по величине с числом K, здесь можно поменять местами N и K, а потому N-е простое есть по величине ~ N/ln N. Я знаю, что такое рассуждение выглядит небольшим жульничеством, но в действительности оно дает неплохую оценку, которая к тому же становится все лучше и лучше «по принципу волны». Эта оценка предсказывает, например, что триллионное простое число равно 27 631 021 115 929, а на самом деле триллионное простое число есть 30 019 171 804 121, так что ошибка составляет 8 процентов. Выраженные в процентах ошибки для тысячного, миллионного и миллиардного простого числа равны соответственно 13, 10 и 9.

Эти утверждения не просто следуют из ТРПЧ; сама ТРПЧ также следует из них. Если математически доказать справедливость любого из них, то в качестве следствия получится ТРПЧ. Каждый из этих результатов равносилен ТРПЧ, и его можно считать просто альтернативной формулировкой этой теоремы. В главе 7.viii мы познакомимся с другим, более важным способом переформулировать ТРПЧ.