Эврика! Дом творческих и вдумчивых людей
Добро пожаловать на первый в Латвии мультитематический и межвузовский научный портал!

Сделать стартовой
Добавить в избранное
Контакты
 
   Главная      Эврика      Библиотека      Досуг      Контакты     БДС  

Библиотека : Научно-популярные статьи : Математика





Дон Цагир

Первые 50 миллионов простых чисел

Мне хотелось бы поговорить с вами об одной проблеме, которая, хотя сам я над ней и не работал, всегда меня чрезвычайно привлекала и которая очаровывала математиков, пожалуй, с доисторических времён и до наших дней, – а именно о проблеме распределения простых чисел.

Вам, конечно, известно, что простым числом называется отличное от 1 натуральное число, не делящееся ни на какие иные натуральные числа, кроме 1; во всяком случае, именно такое определение дают специалисты по теории чисел. Правда, другие математики иногда используют и иные определения. Так, для специалиста по теории функций простое число – это целочисленный нуль аналитической функции

1 –  sin  pG(s)

s

 .
sin  p

s


Для алгебраиста – это

«характеристика конечного поля» 1,

или

«точка из spec Z» 2,

или

«неархимедово нормирование» 3.

Для специалиста по комбинаторике простые числа определяются рекуррентной формулой [1]
  n  
 pn+1   1 – log 2  ( 1

2

 +  å å
(–1)r
2  p i1 ...  p ir  – 1
)  
  r = 1      1 £ i1 £ ... £ ir £ n       

где [x] – целая часть числа x 4. И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена [2]

F(a, b, с, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
    = {k + 2} {1 – (wz + h + jq)2 – (2n + p + q + ze)2
    – (a2y2y2 + 1 – x2)2 – ({e4 + 2e3}{a + 1}2o2)2
    – (16{k + 1}3{k + 2}{n + 1}2 + 1 – f 2)2
    – ({(a + u4u2a)2 – 1}{n + 4dy}2 + 1 – {x + cu}2)2
    – (ai + k + 1 – li)2
    – ({gk + 2g + k + 1}{h + j} + hz)2
    – (16r2y4{a2 – 1} + 1 – u2)2
    – (pm + l{an – 1} + b{2an + 2an2 – 2n – 2})2
    – (zpm + plap2l + t{2app2 – 1})2
    – (qx + y{ap – 1} + s{2ap + 2ap2 – 2p – 2})2
    – (a2l2l2 + 1 – m2)2 – (n + l + vy)2}.

Но я думаю, вы вполне удовлетворены первым из приведённых мной определений.

Имеются два главных факта о распределении простых чисел, о которых я надеюсь рассказать вам так, чтобы они навек запечатлелись в вашей памяти. Первый: простые числа, при своём таком простом определении и при своей роли кирпичиков, из которых строятся все натуральные числа 5, являются самыми капризными и упрямыми из всех объектов, вообще изучаемых математиками. Они растут среди натуральных чисел как сорная трава, не подчиняясь, кажется, ничему, кроме случая, и никто не может предсказать, где взойдет ещё одно простое, а, увидев число, – определить, простое оно или нет. Другой факт озадачивает ещё больше, так как он состоит в прямо противоположном утверждении, а именно: простые числа демонстрируют удивительную регулярность, они подчиняются законам, и притом с почти педантичной точностью.

Чтобы пояснить первое утверждение, я покажу вам список простых и составных чисел, не превосходящих 100 (табл.1), причём, за исключением числа 2, приведены лишь нечётные числа, а затем список простых из ста натуральных чисел, предшествующих и следующих за 10 000 000 (табл.2).

Таблица 1. Простые и (нечётные) составные числа от 1 до 100.
простые составные
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 
9
15
21
25
27
33
35
39
45
49
51
55
57
63
65
69
75
77
81
85
87
91 
93 
95 
99 

Таблица 2. Простые числа в интервалах длины 1000 слева и справа от 10 миллионов.
между
 9 999 900   и   10 000 000 
между
 10 000 000   и   10 000 100 
9 999 901
9 999 907
9 999 929
9 999 931
9 999 937
9 999 943
9 999 971
9 999 973
9 999 991
10 000 019
10 000 079

Полагаю, вы согласитесь, что нет явно видимой причины, по которой одно число является простым, а другое – нет. Напротив, при взгляде на эти таблицы возникает ощущение, будто стоишь перед непостижимой тайной творения. Что и математики до сих пор ещё не раскрыли эту тайну, пожалуй, наиболее убедительно подтверждает то усердие, с которым они и поныне ищут всё бóльшие простые. Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Например в 1876 г. Люка доказал, что число 2127 – 1 – простое [См. подробности в статье А. Н. Рудакова. – E.G.A.], и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если взглянуть на него:

2127 – 1 = 170141183460469231731687303715884105727.

Только в 1951 г. – после возникновения электронных вычислительных устройств – нашли бóльшее простое число. Сведения о сменявших друг друга числах-рекордсменах вы найдете в табл.3 [3]. В настоящее время рекордсменом является 6002-значное число 219937 – 1 (я бы не хотел его здесь выписывать); счастливчик, оно может гордиться своей славой 6. Кто сомневается в сказанном, может справиться в книге мировых рекордов Гиннесса.

Таблица 3. Наибольшее известное простое число.
p число цифр
в числе p
год
открытия
кто открыл
2127 – 1 39 1876 Люка
(2148 + 1)/17 44 1951 Феррье
114(2127 – 1) + 1
180(2127 – 1)2 + 1
41
79
1951 Миллер + Уиллер + EDSAC 1
2521 – 1
2607 – 1
21279 – 1
22203 – 1
22281 – 1
157
183
386
664
687
1952 Лемер + Робинсон + SWAC
23217 – 1 969 1957 Ризель + BESK
24253 – 1
24423 – 1
1281
1332
1961 Хурвитц + Селфридж + IBM 7090
29689 – 1
29941 – 1
211213 – 1
2917
2993
3376
1963 Гиллис + ILIAC 2
219937 – 1 6002 1971 Таккермэн + IBM 360

Однако гораздо интереснее вопрос о законах, которым подчиняются простые числа. Я привёл вам ранее в табл.1 список простых чисел между 1 и 100. На рис.1 та же информация представлена графически, функция p(x), о которой теперь пойдёт речь, выражает количество простых чисел, меньших или равных x; следовательно, в нуле она имеет значение 0 и скачком увеличивается на 1 в точках x = 2, 3, 5 и т.д., т.е. когда x равно простому числу. Уже из этого графика видно, что растёт p(x), несмотря на малые локальные колебания, в общем, довольно регулярно. Если же увеличить область изменения x до 50 000, то регулярность эта становится настолько отчётливой, что дух захватывает. По-моему, плавность, с которой поднимается эта кривая, следует отнести к числу удивительнейших фактов математики.

Рис.1. Функция p(x) при x £ 100.

Но где закономерность, там и учёные, которые пытаются её разгадать. И данный случай не стал исключением. Нетрудно найти эмпирическую формулу, хорошо описывающую рост количества простых чисел. От 1 до 100 имеется 25 простых чисел, т.е. четверть всех чисел; до 1000 их 168, т.е. около одной шестой; до 10 000 их 1229, т.е. примерно одна восьмая. Продолжая вычисления до 100 000, 1 000 000 и т.д. и определяя каждый раз отношение количества простых к количеству всех натуральных чисел, получим данные, приведённые в табл.4.

Таблица 4.
x  p(x        x/p(x)        
10 4 2,5
100 25 4,0
1 000 168 6,0
10 000 1 229 8,1
100 000 9 592 10,4
1 000 000 78 498 12,7
10 000 000 664 579 15,0
100 000 000 5 761 455 17,4
1 000 000 000 50 847 534 19,7
  10 000 000 000         455 052 512 22,0

(Так скромно выписанные в ней значения p(x) потребовали тысяч часов трудоёмких вычислений.) Видно, что отношение x к p(x) при переходе от данной степени десяти к последующей всё время увеличивается примерно на 2,3. Математики сразу узнают в числе 2,3 логарифм 10 (разумеется, по основанию e). В результате возникает предположение, что

p(x) ~  x

 ln x

,

причем знак ~ означает, что отношение соединённых им выражений с ростом x стремится к 1. Это асимптотическое равенство, впервые доказанное в 1896. г., называется в настоящее время законом распределения простых чисел. Гаусс, величайший из математиков, открыл этот закон в пятнадцатилетнем возрасте, изучая таблицы простых чисел, содержавшиеся в подаренной ему за год до того таблице логарифмов. В течение всей своей жизни Гаусс живо интересовался распределением простых чисел и проводил обширные вычисления для выяснения этого вопроса. В своём письме к Энке [4] Гаусс описывает, как он «очень часто употреблял свободные четверть часа, чтобы то там, то здесь просчитать хилиаду» (т.е. интервал в 1000 чисел), и так до тех пор, пока он не нашёл, наконец, все простые, меньшие трёх миллионов (!), и не сравнил полученные результаты с предполагаемой формулой их распределения.



Рис.3.

Закон распределения простых чисел утверждает, что функция p(x) асимптотически (т.е. с относительной погрешностью [7]   0%) равна x/ln x. Однако если мы сравним графики функций x/ln x и p(x), то увидим, что, хотя функция x/ln x качественно и отражает поведение p(x), но всё же согласуется с ней не с такой точностью, которая позволила бы объяснить плавность графика p(x) (рис.3). Итак, следует поставить вопрос о лучшем приближении. Посмотрев снова на таблицу отношений x/p(x), мы увидим, что это отношение почти точно равно ln x – 1. Проведя более тщательные и полные вычисления, Лежандр [5] в 1808 г. обнаружил, что особенно хорошее приближение получается, если вычесть из ln x не 1, а 1,08366, т.е.

p(x) ~  x

ln x – 1,08366

,

Другое очень хорошее приближение p(x), впервые указанное Гауссом, можно получить, исходя из того эмпирически установленного факта, что плотность простых вблизи очень большого числа x почти точно равна 1/ln x. Поэтому количество простых чисел, не превосходящих x, приблизительно выражается логарифмической суммой

Ls(x) =  1

ln 2

+ 1

ln 3

+ ... + 1

ln x

,

или, что примерно то же самое [6], интегральным логарифмом:
  x  
Li (x) =  ò dt

 ln t

.
  2  

Сравнивая графики Li(x и p(x), приведённые на рис.4, мы видим, что в рассматриваемом диапазоне в пределах точности рисунка они просто совпадают. Картинку для приближения Лежандра не стоит даже показывать, так как в указанном диапазоне значений x оно ещё лучше.



Рис.4.

Существует ещё одно приближение функции p(x), о котором я хотел бы упомянуть. Исследования Римана по простым числам наводят на мысль, что вероятность того, что большое число x является простым, будет с большей точностью задаваться функцией 1/ln x, если учитывать не только сами простые, но и их степени, причём квадрат простого числа считать за половину простого, третью степень – за треть и т.д. Это приводит к следующему приближённому равенству:

p(x) +  1

2

 p(Öx ) +  1

3

 p(Öx ) 3 + ... » Li (x),

или, если «обратить» эту зависимость

p(x) » Li (x) –  1

2

 Li (Öx ) –  1

3

 Li (Öx ) 3 – ... [7].

Функцию, стоящую в правой части последнего равенства, обозначим (в честь Римана) через R(x). Как видно из табл.5, она представляет собой удивительно хорошее приближение к p(x).

Таблица 5.
   x     p(x    R(x)    
100 000 000 5 761 455 5 761 552
200 000 000 11 078 937 11 079 090
300 000 000 16 252 325 16 252 355
400 000 000 21 336 326 21 336 185
500 000 000 26 355 867 26 355 517
600 000 000 31 324 703 31 324 622
700 000 000 36 252 931 36 252 719
800 000 000 41 146 179 41 146 248
900 000 000 46 009 215 46 009 949
   1 000 000 000        50 847 534        50 847 455

Читателю, немного знакомому с теорией функций, могу сказать, что R(x) – целая функция от ln x, задаваемая быстро сходящимся степенным рядом
  ¥  
R(x) = 1 + å 1 

nz(n+1)

(ln x)n

n!

 ,
  n = 1  

где z(n) – дзета-функция Римана [8].

Впрочем, надо подчеркнуть, что приближения Гаусса и Лежандра для p(x) были получены чисто эмпирически и что даже Риман, который пришёл к своей функции R(x) с помощью теоретических рассуждений, не доказал асимптотического закона распределения простых чисел. Это было сделано (на основе исследований Римана) лишь в 1896 г. Адамаром и (независимо) Валле Пуссеном.

Я хотел бы ещё привести несколько численных примеров, показывающих возможность предсказания фактов о простых числах. Как уже было отмечено, вероятность того, что число порядка x является простым, приблизительно равна 1/ln x; это означает, что количество простых в интервале длины a поблизости от x должно быть примерно равно a/ln x, во всяком случае если длина интервала достаточно велика, чтобы имело смысл заниматься статистикой, но достаточно мала по сравнению с величиной x. Например, в интервале между ста миллионами и ста миллионами плюс 150 000, следует ожидать появления около 8142 простых, так как

150000

ln 100000000

 =  150000

18,427...

 » 8142.

Соответственно вероятность того, что два заданных числа вблизи x оба окажутся простыми, приблизительно равна 1/ln² x. Поэтому ожидаемое количество простых чисел-близнецов (т.е. пар простых, отличающихся ровно на 2, вроде 11, 13 или 59, 61) в интервале от x до x + a приблизительно равно a/ln² x. На самом деле ожидаемая величина немного больше, поскольку если уже известно, что число n является простым, то это несколько изменяет шансы, что и n + 2 будет простым; например, n + 2 в этом случае заведомо нечётно. Несложные эвристические рассуждения [9] показывают, что ожидаемое количество простых чисел-близнецов в интервале [x, x+a] равно Ca/ln² x, где C – постоянная, приблизительно равная 1,3 (точнее C = 1,3203236316...). Так, между числами 100 000 000 и 100 150 000 должно быть примерно 1,32´150000/(18,427)² » 584 простых чисел-близнецов. В табл.6 я привожу полученные Джоунзом, Лэлом и Бландоном [10] данные о действительном количестве простых чисел и простых чисел-близнецов в этом и в некоторых других интервалах той же длины около больших степеней десяти. Видно, что реальные значения очень хорошо согласуются с ожидаемым результатом. Это особенно удивительно для простых-близнецов, так как пока не удается доказать даже тот факт, что их бесконечно много, не говоря уже об асимптотическом законе их распределения.

Таблица 6. Простые и простые-близнецы в 8 интервалах длины 150 000.
интервал
[n, n + 150 000]
число
простых
число
простых-близнецов
ожидаемое фактическое ожидаемое фактическое
n = 100 000 000 8142 8154 584 604
n = 1 000 000 000 7238 7242 461 466
n = 10 000 000 000 6514 6511 374 389
n = 100 000 000 000 5922 5974 309 276
n = 1 000 000 000 000 5429 5433 259 276
n = 10 000 000 000 000 5011 5065 211 208
n = 100 000 000 000 000 4653 4643 191 186
n = 1 000 000 000 000 000 4343 4251 166 161

В качестве последнего примера на тему о предсказуемости свойств простых чисел упомяну ещё проблему о «провалах» между ними. Рассматривая таблицу простых чисел, можно заметить, что иногда встречаются особенно большие интервалы (например, между 113 и 127), совсем не содержащие простых. Пусть g(x) – длина наибольшего из интервалов между 1 и x, не содержащих простых чисел 9. Например, для x = 200 самым длинным из них является только что упомянутый интервал от 113 до 127, так что g(200) = 14. Величина g(x) растёт, разумеется, очень неравномерно, однако некоторые эвристические соображения [11] приводят к асимптотической формуле

g(x) ~ ln2 x.

Насколько всё-таки хорошо согласуется с ожидаемым поведением даже эта чрезвычайно сильно скачущая функция g(x), видно из рис.5.



Рис.5.

До сих пор я главное внимание уделял обоснованию утверждения о господствующем среди простых чисел порядке, нежели обоснованию утверждения об их своеволии. Кроме того, я ещё не показал, как было обещано в названии лекции, первые 50 миллионов простых, а привёл данные лишь о нескольких тысячах простых. Так вот, на рис.6 графически представлена функция p(x) в сравнении с приближениями Лежандра, Гаусса и Римана при изменении x до 10 миллионов [12]; так как графики этих четырёх функций почти совпадают между собой (как мы это уже видели на рис.4), то на рис.6 приведены графики соответствующих разностей.



Рис.6. Графики приближений Гаусса    , Лежандра     и Римана    ; значения x отложены в миллионах.

Думаю, уже одна эта картинка ясно показывает, чтó ожидает того, кто решается изучать простые числа.

Как видно из рисунка, приближение Лежандра x/(ln x – 1,08366) при небольших x (примерно до 1 миллиона) значительно точнее приближения Гаусса Li(x), однако начиная с 5 миллионов точнее становится Li(x) и можно показать, что с дальнейшим ростом x это становится всё вернее.

До 10 миллионов имеется примерно 600 000 простых чисел. Чтобы представить все обещанные 50 миллионов простых, следует дойти до 1 миллиарда. График разности R(x) – p(x) в этой области показан на рис.7 [13]. Колебания функции R(x) – p(x) становятся с ростом x всё более сильными, однако не превосходят нескольких сотен даже при таких, почти невообразимо больших x.


Рис.7. График разности R (x) – p (x) на интервале 0 £ x £ 1 000 000 000.

Здесь можно упомянуть ещё один факт о функции p(x). На рис.6 приближение Гаусса Li(x) всюду больше p(x), и это остаётся справедливым и до 1 миллиарда, как явствует из рис.8 (на котором данные отложены в логарифмических шкалах).



Рис.8. Значения x отложены в миллионах.

Последний график, несомненно, создает впечатление, что разность Li(x) – p(x) с ростом x стремится к бесконечности, т.е. что интегральный логарифм Li(x) принципиально переоценивает количество простых, не превосходящих x (и так как R(x) всегда меньше Li(x), то это соответствовало бы утверждению, что R(x) даёт лучшее приближение, чем Li(x). Однако дело обстоит иначе. Можно доказать, что существуют точки, в которых p(x) изменяется настолько резко, что становится больше Li(x). Такие числа до сих пор не найдены и, может быть, никогда и не будут найдены, но Литтлвуд доказал, что они существуют, а Скьюз [14] установил даже, что одно из них не превосходит

1010
1034
.

(По поводу этого числа Харди заметил, что оно, пожалуй, наибольшее из всех, когда-либо служивших в математике какой-нибудь определённой цели.) Во всяком случае, это убедительно показывает, как неразумно делать выводы о свойствах простых, основываясь только на численных данных.

В последней части моего сообщения я хочу рассказать о некоторых теоретических результатах, касающихся p(x), чтобы у вас не сложилось впечатление, будто исследования по простым числам следует отнести исключительно к области экспериментальной математики. Непосвящённому может показаться, что свойство числа быть простым слишком случайно и исключает возможность доказательства каких-либо фактов о таких числах. Этот взгляд был опровергнут уже 2200 лет тому назад Евклидом, доказавшим существование бесконечного множества простых чисел. Его рассуждение укладывается в одну фразу: если бы имелось лишь конечное число простых, то можно было бы их перемножить и, прибавив единицу, получить число, которое не делится ни на одно простое, что невозможно. В XVIII веке Эйлер доказал более сильное утверждение, а именно что ряд, составленный из величин, обратных простым, расходится, т.е. его частичные суммы становятся с ростом количества слагаемых больше любого заданного числа. В его (также очень простом) доказательстве была использована функция

z(s) = 1 +  1

2s

 +  1

3s

 + ...,

роль которой для изучения p(x) была полностью оценена лишь позднее, благодаря работам Римана. В этой связи стоит отметить, что, хотя сумма величин, обратных всем простым, бесконечна, однако сумма величин, обратных всем известным простым (т.е. примерно первым 50 миллионам), меньше четырёх [15].

Только в 1850 г. Чебышёву удалось сделать первый шаг к доказательству закона распределения простых чисел [16]. [«Чебышёв – лидер русских математиков – имел необъяснимую неприязнь к теории функций комплексного переменного и к комплексным числам вообще. ... Эта нелюбовь Чебышёва к комплексным числам вышла ему, так сказать "боком": асимптотический закон распределения простых чисел, к выводу которого Чебышёв подошёл ближе всех, был впервые доказан Валле-Пуссеном и Адамаром именно средствами комплексного анализа.» – цитата из статьи «Софья Ковалевская: математик и человек», УМН, № 6 (2000). – E.G.A.] Он показал, что при достаточно больших x справедлива оценка

0,89  x

 ln x

 < p(x) <  1,11  x

 ln x

,

т.е. что закон распределения простых чисел справедлив с относительной погрешностью, не превосходящей 11%. Его доказательство, использующее биномиальные коэффициенты 13, так красиво, что я не могу устоять перед искушением привести его упрощённый вариант (разумеется, ввиду этого, с несколько худшими постоянными).

Покажем, что выполняется такая оценка сверху:

p(x) <  1,7  x

 ln x

,

Она непосредственно проверяется для x < 1200. Будем рассуждать по индукции 14 и предположим, что наша оценка доказана для всех x £ n. Рассмотрим «центральный» биномиальный коэффициент
( 2n
n
) .
Поскольку
22n = (1 + 1)2n ( 2n
0
) ( 2n
1
) + ... +  ( 2n
n
) + ... +  ( 2n
2n
) ,

он, безусловно, меньше 22n. С другой стороны,

( 2n
n
)  =  (2n)!

(n!)2

 =  (2n)×(2n – 1)× ... ×2×1

(n×(n – 1)× ... ×2×1)2


Каждое простое число p, меньшее 2n, входит в числитель, но, если p больше n, не входит в знаменатель. Поэтому «центральный» биномиальный коэффициент делится на каждое простое, лежащее между n и 2n15

Õ  p   ( 2n
n
)
n<p£2n

В произведении слева p(2n) – p(n) сомножителей, каждый из которых больше n, поэтому

 np (2n) – p (n) £  Õ  p £  ( 2n
n
)  < 22n.
  n<p£2n  

Прологарифмировав, получим

p(2n) – p(n) <  2n ln 2

ln n

 < 1,39  n

 ln n

.

Согласно предположению индукции, теорема верна для n, т.е.

p(n) <  1,7  n

 ln n

.

Складывая два последних неравенства, находим, что

p(2n) < 3,09  n

 ln n

 < 1,7  2n

ln (2n)

  (n > 1200),

т.е. теорема верна и для 2n. Так как

p(2n + 1) £ p(2n) + 1 < 3,09  n

 ln n

 + 1 < 1,7  2n + 1

ln (2n + 1)

  (n > 1200),

то она справедлива и для 2n + 1, чем и завершается шаг индукции.

Для получения оценки снизу нам понадобится следующая простая лемма, которая легко выводится из известной формулы для показателя степени простого числа, с которым оно входит в n! [17]:

ЛЕММА. Пусть р – простое число. Если pv(p) – наибольшая степень р, которая входит в
( n
k
) ,

то pv(p) £ n.

СЛЕДСТВИЕ. Для любого биномиального коэффициента
( n
k
)

справедлива оценка
( n
k
)  =  Õ  pv(p) £ np (n) .
   p £ n  

Применив утверждение этого следствия ко всем биномиальным коэффициентам с заданным n и сложив полученные неравенства, найдём
   n  
2n = (1 + 1)n = å ( n
k
)  £ (n + 1)×np (n) ,
  k = 0  

или, после логарифмирования,

p(n) ³  n ln 2

 ln n

 –  ln (n + 1)

ln n

 >  2

3

n

 ln n

  (n > 200).

В заключение я хочу сказать несколько слов о результатах Римана. Хотя Риман и не доказал асимптотического закона распределения простых чисел, зато он сделал нечто гораздо более удивительное – дал точную формулу для p(x). Эта формула выглядит так:

p(x) +  1

2

 p(Öx ) +  1

3

 p(Öx ) 3 + ... = Li (x) – å  Li (xr),
  r  

где суммирование идет по корням дзета-функции z(s) [18]. Корни эти (помимо так называемых «тривиальных корней» p = –2, –4, –6..., вкладом которых в общую сумму можно пренебречь) являются комплексными числами с вещественной частью, заключённой между 0 и 1; первые 10 из них таковы [19]:

r1 1

2

 + 14,134725 i,     r1 1

2

 – 14,134725 i,
r2 1

2

 + 21,022040 i,     r2 1

2

 – 21,022040 i,
r3 1

2

 + 25,010856 i,     r3 1

2

 – 25,010856 i,
r4 1

2

 + 30,424878 i,     r4 1

2

 – 30,424878 i,
r5 1

2

 + 32,935057 i,     r5 1

2

 – 32,935057 i.

Легко показать, что вместе с каждым r в число корней дзета-функции обязательно входит и комплексно-сопряженное с ним число. А вот знаменитая гипотеза Римана, что вещественная часть корня всегда в точности равна 1/2, ещё никем не доказана, хотя её доказательство имело бы для теории простых чисел в высшей степени важное значение [20]. В настоящее время гипотеза проверена для 7 миллионов корней.

С помощью введённой выше функции R(x) формулу Римана можно записать в виде

p(x) = R(x) –  å  R(xr).
  r  

Это дает в качестве k-го приближения к p(x) функцию

Rk(x) = R(x) + T1(x) + T2(x) + ... Tk(x),

где
  rn   rn  
Tn(x) = – R(x   ) – R(x   )

– слагаемое, отвечающее n-й паре корней дзета-функции; Tn(x) при любом n является гладкой осциллирующей функцией от x. Графики Tn(x) для первых значений n показаны на рис.9 [21].

Вместе с Tn(x) и Rk(x) является гладкой функцией при любом k. С ростом k эта функция приближается к p(x). В качестве иллюстрации на рис.10 приведены графики 10-го и 29-го приближений, а также для сравнения график p(x) на интервале от 0 до 100 (см. рис.1).

Я надеюсь, что после моего рассказа у вас осталось некоторое впечатление о замечательной красоте простых чисел и о тех неисчислимых сюрпризах, которые они нам готовят.

Примечания

[1]

J.M.Gandhi, Formulae for the n-th prime, Proc. Washington State Univ. Conf. on Number Theory, Washington State Univ., Pullman, Wash., 1971, 96-106.

[2]

J.P.Jones, Diophantine representation of the set of prime numbers, Notices of the AMS 22 (1975), A-326.

[3]

К тому что так много чисел из этого списка имеют вид Mk = 2k – 1, существует веская причина: согласно одной теореме, восходящей к Люка, число Мk (k ³ 2) тогда и только тогда является простым, когда оно делит число Lk–1, где числа Ln определяются рекуррентным соотношением: L1 = 4, Ln+1 = Ln2 – 2 (так что L2 = 14, L3 = 194, L4 = 37634, ...) и, таким образом, простоту Mk проверить значительно легче, чем простоту других чисел того же порядка. Простые вида 2k – 1 (в этом случае k само обязательно должно быть простым) называются простыми числами Мерсенна (по имени французского математика, который в 1644 г. указал в большей своей части верный список всех таких простых, меньших 1079). Числа Мерсенна играют важную роль и в некоторых других проблемах теории чисел. Евклид обнаружил, что если число 2p – 1 – простое, то число 2p–1(2p – 1) является «совершенным», т.е. равно сумме своих собственных 16 делителей (например, 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, 496 = 1 + 2 + 4 + 6 + 16 + 31 + 62 + 124 + 248), а Эйлер доказал, что все чётные совершенные числа имеют указанный вид. Неизвестно, существуют ли вообще нечётные совершенные числа; во всяком случае, такие числа должны быть больше 10100. Имеется ровно 24 значения р < 20 000, при которых число 2p – 1 – простое.

[4]

С.F.Gauss, Werke, II, 1872, 444–447. Обсуждение истории вопроса о приближениях p(x) см., например, в статье
L.J.Goldstein, A history of the prime number theorem, Amer. Math. Monthly 80 (1973), 599–615.

[5]

A.M.Legendre, Essai sur la théorie des Nombres, Paris, 1808, стр. 394.

[6]

Точнее, имеют место неравенства

Ls(x) – 1,5 < Li(x) < Ls(x)

т.е. разность Li(x) и Ls(x) ограничена. Отметим, что в настоящее время интегральный логарифм обычно понимается в смысле главного значения:
  x   1 – e   x  
li (x) = V.P. ò dt

ln t

 =  lim ( ò dt

ln t

 +  ò dt

ln t

) ;
  0   e ® 0   0   1 + e  

однако это определение отличается от приведённого в тексте лишь на константу.

[7]

Коэффициент при Li(x1/n) определяется следующим образом: он равен +1/n, если n есть произведение чётного числа различных простых, равен –1/n, если n – произведение нечётного числа различных простых, и равен 0, если n делится на квадрат какого-нибудь простого.

[8]

Эту функцию можно представить и по-другому:
  ¥  
R (x) =  ò  (ln x)t dt

t G(t + 1) z(t + 1)

  0  

(z(s) – дзета-функция Римана, G(s) – гамма-функция) или

R (e2px) @  2

p

{ 2

B2

x 4

3B4

x3 6

5B6

x5 + ...  } 2

p

{ 12x + 40x3 252

5

x5 + ...  }

(Bk – это k-е число Бернулли; знак @ означает, что разность соединённых таким знаком выражений стремится к 0 с ростом x); оба представления указал Рамануджан. См.
G.H.Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, Cambridge University Press, 1940, гл.2.

[9]

А именно: для пары (m, n) случайно выбранных чисел вероятность того, что m и n оба не сравнимы с 0 по модулю p, очевидно, равна ((p – 1)/p)2, а для одного случайно выбранного числа n вероятность того, что n и n + 2 оба не сравнимы с 0 по модулю p, равна 1/2 при р = 2 и (p – 2)/p при p ¹ 2. Поэтому вероятность того, что n и n + 2 представляют собой пару «кандидатов в простые по модулю p», отличается от соответствующей вероятности для двух независимых чисел m и n множителем
p – 2

p

 ×  p²

(p – 1)²

при p ¹ 2 и множителем 2 при p = 2. Таким образом, интересующая нас вероятность отличается от указанной в тексте наличием множителя
C = 2 Õ p² – 2p

p² – 2p + 1

 = 1,32032... .
  p > 2
p – простое
 

Несколько более тщательно эти рассуждения проведены в книге:
G.H.Hardy, Е.М.Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford, 1979, § 22.20, стр. 371–373.

[10]

М.F.Jones, M.Lal, W.J.Blundon, Statistics on certain large primes, Math. Comp. 21 (1967), 103–107.

[11]

D.Shanks, On maximal gaps between successive primes, Math. Comp. 18 (1964), 646–651.
График g(x) построен с использованием таблиц, приведённых в следующих работах:
L.J.Lander, T.R.Parkin, On first appearance of prime differences, Math. Comp. 21 (1967), 483–488.
R.P.Brent, The first occurrence of large gaps between successive primes, Math. Comp. 27 (1973), 959–963.

[12]

Данные для этого графика взяты из таблицы простых чисел Лемера:
D.N.Lehmer, List of Prime Numbers from 1 to 10006721, Hafner Publishing Co., New York, 1956.

[13]

Этот и следующий графики построены по значениям p(x), приведённым в статье
D.C.Mapes, Fast method for computing the number of primes less than a given limit, Math. Comp. 17 (1963), 179–185.
В отличие от данных Лемера, использованных при построении предыдущего графика, эти значения вычислены по одной из формул p(x), а не путём непосредственного подсчёта простых, не превышающих x.

[14]

S.Skewes, On the difference p(x) – li (x). I, J. Lond. Math. Soc. 8 (1933), 277–283.
Приведённую оценку Скьюз сперва доказал в предположении справедливости обсуждаемой далее в тексте гипотезы Римана. Через 22 года он же:
S.Skewes, On the difference p(x) – li (x). II, Proc. Lond. Math. Soc. (3)5 (1955), 48–70.
не используя этой гипотезы, доказал, что существует x, не превосходящее (ещё намного большего) значения

1010
10 964
,

для которого p(x) > Li(x). Эта граница была заменена Коэном и Мейхью на

1010
529,7
,
а Леманом:
Е.Lehman, On the difference p(x) – li (x), Acta Arithm. 11 (1966), 397–410.
на 1,65×101165. Леман даже показал, что между 1,53×101165 и 1,65×101165 имеется интервал, содержащий по меньшей мере 10500 чисел, на котором p(x) больше Li(x). Согласно его исследованиям, очень вероятно, что имеется число x, близкое к 6,663×10370, для которого p(x) > Li(x) и нет ни одного числа, меньшего 1020, с тем же свойством.

[15]

Вообще, имеет место соотношение (предположенное в 1796 г. Гауссом и доказанное в 1874 г. Мертенсом):

å  1

 p

  =  ln ln x + C + e(x),
p < x  

где e(x) ® 0 при x ® ¥ и C – константа, приблизительно равная 0,261497. Это выражение при x = 109 меньше 3,3 и даже при x = 1018 ещё не превосходит 4. [Относительно сходимости рядов по простым числам имеет место любопытная
Теорема (Чебышёв): Если при xx0 функция F(x) положительна и F(x)/ln x монотонно убывает, то ряды
 F(p)     и      F(n)

ln n

p n=2

сходятся или расходятся одновременно.

Например, ряд  1/(p ln p) сходится и его сумма равна 1,63 ± 0.01, тогда как его «натуральный» собрат  1/(n ln n) расходится. – E.G.A.]

[16]

П.Л.Чебышёв, Recherches nouvelles sur les nombres premiers, Paris 1851, С. R. Paris 29 (1849), 397–401, 738–739.
Современное изложение доказательства Чебышёва см. в книге:
А.А.Бухштаб, Теория чисел. М.: Просвещение, 1966.

[17]

Наибольшая степень p, которая делит n!, есть

  [ n

 p

]  +  [ n

 p²

]  + ...  
 p   ,

где [x] обозначает целую часть числа x – наибольшее целое, не превосходящее x; поэтому в обозначениях леммы

v(p) =  å { [  n

 pr

]  –  [  k

 pr

]  –  [  nk

pr

] }.
  r ³ 1  

В этой сумме каждое слагаемое равно 0, или 1, причём заведомо равно 0 при

r  ln n

 ln p

(так как тогда [n/pr] = 0). Значит,

v(p) £  [  ln n

 ln p

]  ,

откуда и следует утверждение леммы.

[18]

Указанное ранее определение z(s) в виде ряда

1 +  1

2s

 +  1

3s

 + ...

имеет смысл лишь тогда, когда s – комплексное число, вещественная часть которого больше 1 (ибо только при таком условии ряд будет сходящимся), и в этой области z(s) не имеет нулей. Функцию z(s) можно, однако, доопределить для всех комплексных чисел и рассматривать её корни в комплексной плоскости. Расширение области определения z(s) до полуплоскости Re(s) > 0 получается особенно просто, если воспользоваться справедливым при Re(s) > 1 тождеством

(1 – 21–s)z(s) = 1 +  1

2s

 +  1

3s

 + ... – 2 ( 1

2s

 +  1

4s

 +  1

6s

 + ... )  = 1 –  1

2s

 +  1

3s

 – ...

и заметить, что стоящий справа ряд сходится при всех s, имеющих положительную вещественную часть. Отсюда легко вывести, что «интересные» корни дзета-функции, т.е. корни вида r = b + ig, 0 < b < 1, задаются двумя уравнениями
¥     ¥  
å (–1)n – 1

nb

cos(g ln n) = 0,   å (–1)n – 1

nb

sin(g ln n) = 0.
n = 1     n = 1  

Ряд по корням r в формуле Римана сходится неабсолютно, и поэтому его члены следует располагать в надлежащем порядке (по возрастанию абсолютного значения Im(r)). Наконец, отметим, что точная формула для p(x) была найдена Риманом ещё в 1859 г., а доказана Мангольдтом лишь в 1895 г.

[19]

Эти корни уже в 1903 г. вычислил Грам:
J.-P.Gram, Sur les zéros de la fonction z(s) de Riemann, Acta Math. 27 (1903), 289–304.
Очень удачное изложение теории дзета-функции Римана и методов вычисления её нулей дано в книге:
H.M.Edwards, Riemann's Zeta Function, Academic Press, New York, 1974.

[20]

А именно, из гипотезы Римана вытекает следующее утверждение (верно и обратное): погрешность приближения p(x) функцией Li(x) не превосходит CÖx ln x, где C – некоторая постоянная; в то же время неизвестно, меньше ли эта погрешность xc при каком-нибудь с < 1.

[21]

Этот график, как и три последующих, заимствован из работы:
H.Riesel, G.Göhl, Some calculations related to Riemann's prime number formula, Math. Comp. 24 (1970), 969–983.



Добавление

Так как приведённый выше текст, представляющий собой точную запись моей вступительной лекции, уже был опубликован ранее (Elemente der Mathematik, Beiheft № 15, 1977 [английский перевод: Mathematical Intelligencer 0 (1977), 7–19]), я почёл за лучшее не пытаться «осовременить» текст, а оставив его без изменений, упомянуть результаты новейших исследований в этом коротком добавлении.

1. К списку необычных определений простых чисел, с которого мы начали наше путешествие, следует добавить еще одно, на этот раз из теории игр. А именно (по Конвею), отправляясь от N = 2, на каждом шаге мы заменяем N на aN, где a – первое из четырнадцати рациональных чисел

17

91

, 78

85

, 19

51

, 23

38

, 29

33

, 77

29

, 95

23

, 77

19

, 1

17

, 11

13

, 13

11

, 15

14

, 15

2

, 55,

для которого число aN – целое. Для получающейся при этом последовательности 2, 15, 825, 725, 1925, ... все фигурирующие в ней степени двойки будут иметь вид 2p, где р – простые, идущие в своём естественном порядке! С помощью хорошего калькулятора можно таким путем за несколько минут отыскать первые 4 или 5 простых чисел.

2. С 1971 г. уже три раза был побит мировой рекорд наибольшего известного простого числа; по указанной в примечании 3 причине каждый раз это было снова число Мерсенна 2p – 1, а именно с p = 21 701, 23 209 и 44 497 18.

3. Данные о количестве простых и простых-близнецов (табл.6) теперь имеются до 1011:

R.Brent, Tables concerning irregularities in the distribution of primes and twin primes to 1011, 12 computer sheets deposited in UMT File 21, Review in Math. Comp. 30 (1976) 379.

Особенно интересна с этой точки зрения статья

R.Е.Grandall, M.A.Penk, A search for large twin prime pairs. Math. Comp. 33 (1979), 383–388.

В ней не только указана наибольшая известная пара близнецов (по 303 цифры в каждом!), но и описана статистическая проверка асимптотической формулы

(число близнецов между х и х + а) ~  1,32...a

ln2 x


для 132947 случайно выбранных чисел от 1049 до 1054 при ожидаемых 245±25 парах близнецов фактически было найдено 249 пар. В настоящее время и о функции «провалов» g(x) имеется больше данных, чем показано на рис.5; см.

R.Brent, The distribution of prime gaps in intervals up to 1016, Review in Math. Comp. 28 (1974), 331.

В качестве ещё одного примера нерегулярности распределения простых чисел следует упомянуть результат Бейза и Хадсона о разности D(x) = p4,3(x) – p4,1(x):

С.Bays, R.Hudson, Math. Comp. 32 (1978), 281–286.

(pa,b(x) обозначает число простых вида an + b, не превосходящих x). Эта разность, которая при малых x всегда положительна и при всех x очень мала (так, p4,1(1010) = 227 523 275, а p4,3(1010) = 227 529 235), согласно результатам Бейза и Хадсона, остаётся положительной до x = 950 000 000, за исключением менее чем одной тысячи значений, однако до x = 2×1010 есть очень большой интервал [1,854×1010, 1,895×1010], на котором она отрицательна, и её минимум в этой области равен D(18 699 356 297) = –2719.

4. Гипотеза Римана проверена уже для 150 миллионов корней, а именно для всех r, у которых |Im r| < 32 585 736,4. См.

R.Brent, On the zeros of the Riemann zeta function in the critical strip. Math. Comp. 33 (1979), 1361–1372.


[Я хотел бы добавить к рассказу Д. Цагира ещё несколько фактов. В 1988 г. вышла «Книга рекордов в области простых чисел». Мне не довелось её полистать, но рецензия на неё, опубликованная в «Бюллетене Американского математического общества», даёт некоторое представление о затрагиваемых вопросах и служит хорошим дополнением к вышеизложенному. – E.G.A.]

Примечания переводчика

1.

См., например, А.Г.Курош, Курс высшей алгебры. – М.: Наука, 1968.

2.

См., например, С.Ленг, Алгебра. – М.: Мир, 1968.

3.

См., например, Н.Коблиц, р-адические числа, р-адический анализ и дзета-функции. – М.: Мир, 1982.

4.

То есть наибольшее целое число, не превосходящее x.

5.

Всякое натуральное число, отличное от 1, можно представить (и притом единственным образом) в виде произведения простых чисел. Доказательство см., например, в книге: А.А.Калужнин, Основная теорема арифметики. – M.: Наука, 1969.

6.

С тех пор этот рекорд был неоднократно побит; см. добавление 2 в конце экскурсии.

7.

Относительной погрешностью называется отношение модуля (абсолютной величины) разности приближённого значения и точного значения к модулю последнего.

8.

С определением и свойствами z-функции можно познакомиться, например, по книге: Е.К.Титчмарш, Теория дзета-функции Римана. – М.: ИЛ, 1953.

9.

Обозначение происходит от английского gap – пропуск, пробел, разрыв.

10.

То есть по осям отложены (в выбранном масштабе) не сами числа, а их логарифмы.

11.

То есть суммы
1

2

+ 1

3

+ 1

5

+ ... + 1

pn

,

где pn – это n-е простое число.

12.

Совсем элементарное доказательство можно найти, например, в книге: А.М.Яглом, И.М.Яглом, Неэлементарные задачи в элементарном изложении. – М.: Гостехиздат, 1954.

13.

По поводу определения и используемых в дальнейшем свойств биномиальных коэффициентов см., например, книгу: Н.Я.Виленкин, Комбинаторика. – М.: Наука, 1969. Наряду с используемым автором обозначением

( n
m
)

для биномиальных коэффициентов употребляется также обозначение

C m
n
.
14.

С этим методом можно познакомиться, например, по книге: И.С.Соминский, Метод математической индукции. – М.: Hayка, 1974.

15.

Запись b|a означает, что a нацело делится на b.

16.

То есть делителей, отличных от самого числа.

17.

То есть не делятся на p.

18.

В январе 1983 г. появилось сообщение, что простым является и 25962-значное число 286243 – 1, найденное Д.Словинским; см., например, журнал «Квант», 1983, № 7, с.16.



Добавлено: 2004-10-05
Посещений текста: 9332

[ Назад ]





© Павел Гуданец 2004-2017 гг.
 инСайт

При информационной поддержке:
Институт Транспорта и Связи