[Перевод] Структура и случайность простых чисел20.10.2017 12:03

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

Но на этом история не заканчивается. Распределение простых чисел выглядит случайным, с неравномерными разрывами и скоплениями, которые выглядят довольно хаотично. Если и существует какая-то схема, то она непостижима. На самом деле, простые числа выглядят достаточно случайными, чтобы можно было сыграть с ними в кости. Создайте список последовательных простых чисел (допустим, начав с 11, 13, 17, 19,…) и разделите их по модулю 7. Другими словами, разделите каждое простое число на 7 и сохраните только остаток. Результатом будет последовательность целых чисел из множества {1, 2, 3, 4, 5, 6}, которая выглядит почти как результат нескольких бросков правильной кости.

$\begin{align*} 11 \bmod 7 & \rightarrow 4 \qquad 47 \bmod 7 \rightarrow 5 \\ 13 \bmod 7 & \rightarrow 6 \qquad 53 \bmod 7 \rightarrow 4 \\ 17 \bmod 7 & \rightarrow 3 \qquad 59 \bmod 7 \rightarrow 3 \\ 19 \bmod 7 & \rightarrow 5 \qquad 61 \bmod 7 \rightarrow 5 \\ 23 \bmod 7 & \rightarrow 2 \qquad 67 \bmod 7 \rightarrow 4 \\ 29 \bmod 7 & \rightarrow 1 \qquad 71 \bmod 7 \rightarrow 1 \\ 31 \bmod 7 & \rightarrow 3 \qquad 73 \bmod 7 \rightarrow 3 \\ 37 \bmod 7 & \rightarrow 2 \qquad 79 \bmod 7 \rightarrow 2 \\ 41 \bmod 7 & \rightarrow 6 \qquad 83 \bmod 7 \rightarrow 6 \\ 43 \bmod 7 & \rightarrow 1 \qquad 89 \bmod 7 \rightarrow 5 \\ \end{align*}$

Поработав с большей выборкой (первым миллионом простых чисел больше $10^7$ ), я подсчитал количество простых чисел с каждым из шести возможных остатков по модулю 7 (также известных как шесть возможных классов конгруэнции по модулю 7). Также я симулировал миллион бросков шестигранной кости. Сможете ли вы сказать, глядя на эти два результата, что из них что?

               1        2        3        4        5        6
         166 787  166 569  166 714  166 573  166 665  166 692
             120      -98       47      -94       -2       25

               1        2        3        4        5        6
         166 768  166 290  166 412  166 638  167 282  166 610
             101     -377     -255      -29      615      -57

В каждой таблице первая строка означает количество результатов $x$ в каждом из шести классов. Во второй строке показана разность $x - \bar{x}$ , где $\bar{x}$ — среднее значение $1 000 000 / 6 = 166 667$ . В обоих случаях кажется, что числа распределены довольно равномерно, без очевидных смещений. В первой таблице представлены остатки простых чисел от деления по модулю 7. Их распределение немного более плоское по сравнению с симулированной костью и с меньшими отклонениями от среднего; стандартное отклонение двух выборок равно соответственно 84 и 346. Судя по этим таблицам, похоже, что любой из процессов можно использовать для обеспечения случайности, необходимой в обычной игре в кости.

Но условием случайности является не только равномерное распределение результатов в допустимом интервале. Кроме того, отдельные события в последовательности должны быть независимы друг от друга. Один бросок кости не должен влиять на результат следующего броска. Для проверки независимости можно взглянуть на последовательные события. Сколько раз за единицей идёт ещё одна единица, или двойка, или тройка, и так далее? Запишем в матрицу $6 × 6$ количество всех 36 возможных пар. Если процесс действительно случаен, все 36 пар должны иметь одинаковую частотность, если не принимать во внимание небольшие статистические флуктуации. Можно превратить матрицу в цветную «тепловую карту», в которой ячейки с количеством выше среднего будут отображены в тёплых оттенках розового и красного, а ниже среднего — залиты более холодными оттенками синего. (Вносимые количества являются не действительным количеством $x$ , а нормализованной переменной $w = (x_{i,\,j} - \bar{x}, /\, \bar{x}$ , где $\bar{x}$ — это снова среднее значение, в нашем случае $1 000 000 / 36 = 27 778$ .) Вот тепловая карта симулированной правильной кости:

Рисунок 1.

Здесь нет ничего интересного. Почти все количества настолько близки к среднему значению, что ячейки матрицы кажутся нейтрально серыми, только немногие оказались бледно-розовыми или голубыми. Именно такого результата и ждёшь, когда последовательные броски кости не коррелируют друг с другом, и все возможные пары одинаково вероятны.

Теперь перейдём к соответствующей матрице последовательных простых чисел по модулю 7:

Рисунок 2.

Ого! Похоже мы покинули Страну случайных чисел, здесь старое серое кино превратилось в Technicolor. На тепловой карте появилась голубая полоса вдоль основной диагонали (из левого верха в правый низ), означающая, что последовательные пары простых чисел, имеющие одинаковое значение остатка от деления на 7, очень маловероятны. Другими словами, пары $(1, 1), (2, 2), \ldots (6, 6)$ возникают реже, чем это было бы в действительно случайной последовательности. Наддиагональ (прямо над основной диагональю) имеет более светлый голубой цвет. Это означает, что пары $(i, j)$ , где $j=i+1$ , возникают немного реже, чем средняя частота. Например, $(2, 3)$ и $(5, 6)$ имеют немного отрицательные значения нормализованной частоты. С другой стороны, поддиагональ (под основной диагональю) полностью розовая и красная; такие пары как $(3, 2)$ или $(5, 4)$ , где $j=i-1$ , возникают с частотой выше средней. Вдали от диагонали, в верхнем правом и нижнем левом углу мы видим пастельный шахматный узор.

Если вы предпочитаете иметь дело с числами, а не с цветными квадратами, то вот вам матрица значений:

           пары последовательных простых чисел mod 7
                   1      2      3      4      5      6
          1    15656  24376  33891  29964  33984  28916
          2    37360  15506  22004  32645  25095  33959
          3    25307  41107  14823  22747  32721  30009
          4    32936  26183  37129  14681  21852  33791
          5    24984  34207  26231  41154  15560  24529
          6    30543  25190  32636  25382  37453  15488

Отклонения от единообразия можно назвать какими угодно, но не «незначительными». В третьем ряду, например, видно, что если вы только что встретили 3 в последовательности простых чисел mod 7, то следующее число с намного большей вероятностью будет 2, а не ещё одна 3. Если бы вы играли в игру с костями из простых чисел, то такое смещение колоссально повлияло бы на результат. Кости на простых числах — «заряженные» кости!

Эти примечательно сильные корреляции в парах были открыты Робертом Дж. Лемке-Оливером и Каннаном Соундарараджаном из Стэнфордского университета. Они обсуждали их в препринте, опубликованном на arXiv в марте этого года. Для меня самым удивительным в этом открытии стало то, что никто за долгие годы не заметил эти структуры. Они довольно очевидны, если знать, где из искать.

Думаю, нельзя винить Евклида, за то что он их не нашёл: в античности не были развиты идеи случайности и вероятности. Но как насчёт Гаусса? Он был знатоком таблиц простых чисел, и создал собственные списки тысяч простых чисел. В юности он писал: «одним из моих первых проектов стало наблюдение за уменьшающейся частотой простых чисел, для чего я высчитал несколько тысяч простых чисел…» Более того, Гаусс практически изобрёл идею классов конгруэнции и модульной арифметики. Но очевидно, он никогда не подозревал, что в конгруэнциях пар последовательных простых чисел может таиться что-то странное.

В 1850-х российский математик Пафнутий Львович Чебышев указал на незначительное искажение в простых числах. Деление нечётных простых чисел по модулю 4 разбивает их на два подмножества. Все простые числа в ряду 5, 13, 17, 29, 37,… конгруэнтны 1 по модулю 4; в ряду 3, 7, 11, 19, 23, 31,… конгруэнтны 3 по модулю 4. Чебышев заметил, что простые числа во второй категории кажутся более многочисленными. Например, среди первых 10 000 нечётных простых чисел есть 4 943 конгруэнтных 1 и 5 057 конгруэнтных 3. Однако это воздействие мало по сравнению с неравномерностями, замеченными в парах последовательных простых чисел.

В наше время несколько авторов увидели намёк на феномен последовательных простых чисел. Лемке-Оливер и Соундарараджан упоминают о трёх таких свидетельствах. (См. список справочных материалов в конце статьи.) В 1950-х и 60-х Станислав Кнаповски и Пал Туран исследовали различные аспекты остатков от деления простых чисел по модулю m. В одной статье, посмертно опубликованной 1977 году, они рассматривали деление последовательных простых чисел по модулю 4 с остатками 1 или 3. Они «предположили», что последовательные пары с одинаковым остатком и пары с отличающимися остатками «не равновероятны». В 2002 году Чун-Мин Ко исследовал ряды последовательных простых чисел (не только их пар) и создал проработанные фрактальные паттерны на основе их меняющихся частот. Затем в 2011 году Авнер Эш с коллегами опубликовал подробный анализ «Частоты последовательных пар остатков простых чисел», в том числе несколько матриц, в которых диагональное снижение чётко заметно.

С учётом этих прецедентов были ли Лемке-Оливер и Соундарараджан на самом деле открывателями корреляций последовательных простых чисел? По моему мнению, ответ должен быть положительным. Хотя другие и видели эти паттерны ранее, они не описывали их так, чтобы те зафиксировались в сознании математического сообщества. На самом деле, когда Лемке-Оливер и Соундарараджан объявили о своих находках, реакцией стало удивление, граничащее с недоверием. Эрика Кларарайх в статье для Quanta процитировала реакцию оксфордского теоретика чисел Джеймса Мэйнарда:

Когда Соундарараджан впервые сказал Мэйнарду об открытии пары, Мэйнард сказал «Я поверил ему только наполовину. Как только я вернулся к себе в офис, я провёл численный эксперимент, чтобы убедиться в этом самому».

Очевидно, что такой была всеобщая реакция. Эвелин Лэмб в статье для Nature цитирует Соундарараджана: «Каждый, кому мы рассказывали об этом, в конце концов писал свою компьютерную программу, чтобы убедиться в этом самому».

Так же поступил и я! За последние несколько недель я написал кучу строк кода для анализа деления простых чисел по модулю m. Моя статья — это отчёт о моим попытках разобраться в том, откуда взялись эти паттерны. Мои методы больше вычислительные и визуальные, чем математические, я не могу ничего доказать. Лемке-Оливер и Соундарараджан применили более строгий и аналитический подход, в конце этой статьи я расскажу немного больше об их результатах.

Если вы хотите начать собственное расследование, то можете взять за основу мой код. Он написан на языке программирования Julia, упакован в Jupyter notebook и доступен на GitHub. (Так получилось, что эта программа стала моим первым нетривиальным экспериментом с Julia. В другой статье я расскажу подробнее о моей работе с языком.)

Во всех представленных выше примерах приведено деление простых чисел по модулю 7, но в числе 7 нет ничего особенного. Я выбрал его просто потому, что шесть возможных остатков {1, 2, 3, 4, 5, 6} соответствуют граням обычной кубической кости. Другие модули дают схожие результаты. Лемке-Оливер и Соундарараджан бо́льшую часть анализа провели над делением простых чисел по модулю 3, при котором есть только два класса конгруэнции: простое число больше 3 должно при делении на 3 иметь остаток 1 или 2. Вот матрица количеств пар для первого миллиона простых чисел больше $10^7$ :

                             1       2
                    1   218578  281453
                    2   281454  218514

Рисунок 3.

Паттерн довольно минималистичен, но всё равно узнаваем: элементы вне диагонали для последовательностей $(1, 2)$ и $(2, 1)$ больше, чем элементы на диагонали для $(1, 1)$ и $(2, 2)$ .

Простые числа по модулю 10 имеют четыре класса конгруэнции: 1, 3, 7, 9. Чтобы увидеть это, работая в десятичной нотации, нам даже не нужна арифметика. Когда числа записываются по основанию 10, каждое простое число больше 5 имеет конечную цифру 1, 3, 7 или 9. Вот частоты для 16 пар последовательных конечных цифр:

                          1      3      7      9
                 1    43811  76342  78170  51644
                 3    58922  41148  71824  78049
                 7    64070  68542  40971  76444
                 9    83164  63911  59063  43924

Рисунок 4.

Чётко видна голубая полоса по основной диагонали, хотя в других местах матрицы паттерн немного ослаблен и смазан.

Я обнаружил, что корреляции между последовательными простыми числами проявляются наиболее чётко, когда сам модуль является простым числом, и при этом не слишком маленьким. Посмотрите на тепловые карты для последовательных простых чисел mod 13 и mod 17:

Рисунок 5.

Рисунок 6.

А как насчёт модуля 31?

Рисунок 7.

Из этих матриц получится отличный узор для килта или мозаичного пола, правда? И во всех них видны интересные закономерности. Диагональные полосы выделяются не только на основной диагонали, но и во всей матрице. Такие полосы также создают узор шахматной доски. Вдоль любой строки или столбца ячейки обычно попеременно красные и синие. Более незаметной особенностью является приблизительная двухсторонняя симметрия вдоль противоположной диагонали (идущей из левого низа в правый верх). Если сложить по этой линии квадрат, то соединённые вместе ячейки будут примерно одного цвета. (Этот факт заметил Эш и его соавторы.)

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

Рисунок 8.

Как понять смысл того, что мы видим? Мы начнём наблюдения с того, что все простые числа в нашей выборке являются нечётными, а потому все интервалы между этими простыми являются чётными числами. Для любого заданного простого $p$ следующими кандидатами на звание простого числа становятся $p+2, p+4, p+6, \ldots$ . Связано ли это как-то с рисунком шахматной доски? Если шаги между простыми числами должны быть кратными 2, это определённо может создать корреляции между каждой второй ячейкой любого столбца или строки. (И в самом деле, корреляции с ячейкой через раз должны быть чётко заметны — все чётные элементы должны равняться нулю, если модуль был бы чётным числом. Чётные ячейки можно заполнить только «циклическим возвратом» края матрицы к нечётной границе.)

Диагональные полосы в матрице предполагают наличие сильной корреляции между всеми парами, разделёнными определённым числовым интервалом. Например, самая тёмно-синяя диагональ и самая ярко-красная диагональ состоят из ячеек, разделённых шестью элементами вдоль оси j. В первой строке находятся ячейки 1 и 7, потом 2 и 8, 3 и 9, и так далее. Мне показалось, что эту взаимосвязь проще воспринимать, если «изогнуть» матрицу, чтобы диагонали стали столбцами. Идея заключается в том, чтобы применить к каждой строке циклический сдвиг, все значения в строке сместятся влево, а те, которые «упадут» с левого края, будут вставлены справа. Первая строка смещается на ноль позиций, следующая — на одну позицию, и так далее. (Есть ли название для такого преобразования? Я просто буду называть его «изгиб».)

Затем я написал код для этого преобразования, но в результате получил не совсем то, что ожидал:

Twisted nz heatmap 8 digit primes 1000001 mod 19

Рисунок 9.

Что это за зигзаги вдоль обратной диагонали? Я предположил, что совершил ошибку и сместил на один лишний элемент. И корень проблемы действительно оказался в этом, но «баг» находится не в алгоритме, а в самих данных. Матрицы, показанные мной во всех предыдущих рисунках, являются только частичными, они отбрасывают пустые классы конгруэнции. В частности, матрица для пар простых чисел по модулю 19 игнорирует все простые числа, конгруэнтные 0 по модулю 19 на том логичном основании, что таких простых чисел нет. В конце концов, если $p > 19$» /> и <img src= , то $p$ не может быть простым, потому что оно делится на 19. Тем не менее, строка и столбец для $p \equiv 0 \bmod 19$ являются действительной частью матрицы. Если их добавить, то наше табло с цветовой кодировкой будет выглядеть так:

Рисунок 10.

Присутствие нулевой строки и столбца делает определение преобразования изгибом более аккуратным: для каждой строки $i$ применяем циклический сдвиг влево на $i$ мест. Получившаяся изогнутая матрица тоже выглядит опрятнее:

Twisted z heatmap 8 digit primes 1000001 mod 19

Рисунок 11.

О чём нам говорят эти вертикальные полосы? В исходной матрице элемент $i, j$ представлял собой частоту, с которой за $i \bmod 19$ следует $j \bmod 19$ . Здесь цвет ячейки $i, j$ обозначает частоту, с которой за $i \bmod 19$ следует $(i + j) \bmod 19$ . Другими словами, каждый столбец объединяет элементы с одинаковым интервалом mod 19 между двумя простыми числами. Например, самый левый столбец содержит все пары, разделённые интервалом длиной $0 \bmod 19$ , а ярко-красный столбец в $j = 6$ учитывает все случаи, когда последовательные простые числа отделены друг от друга $6 \bmod 19$ .

Цветовое кодирования даёт нам качественное представление о том, какие интервалы появляются более или менее часто. Для более точного количественного измерения мы можем суммировать вдоль столбцов и отобразить результаты в столбчатом графике:

Column sums twisted 8 digit primes 1000001 mod 19

Рисунок 12.

Три наблюдения:

Замеченная выше неравномерность чётных-нечётных чисел явно заметна и на графике. За исключением 0, каждый чётный интервал выделяется на фоне его нечётных соседей.
Интервал между простыми числами mod 19, равный 6 — самый популярный из всех. Числа, кратные 6 (а именно 12 и 18) тоже часты, но хоть и в меньшей степени.
Интервал между простыми числами mod 19, равный 0, примечательно непопулярен. Это элементы вдоль основной диагонали исходной матрицы, поэтому неудивительно, что их сумма находится на нижней части, однако дефицит сильнее, чем я предполагал.

Я хотел разобраться с источниками этих паттернов. Что делает интервал 6 таким притягательным для пар последовательных простых чисел, и почему почти все простые числа сторонятся бедного интервала 0?

У меня уже есть отдалённая догадка относительно популярности 6. В 1990-х Эндрю Одлыжко, Майкл Рубинштейн и Марек Вулф выполнили вычислительное исследование «чемпионов по прыжкам» среди простых чисел:

Целое число D называется чемпионом по прыжкам, если его наиболее часто возникающая разность между последовательными простыми числами ≤ x для некоторого x.

Среди наименьших простых чисел (x меньше, чем примерно 600), чемпионом по прыжкам обычно является 2, но потом выигрывает 6 и доминирует на довольно большом интервале числовой оси. Примерно возле $x = 10^{35}$ число 6 уступает чемпионство числу 30, которое со временем уступает 210. Одлыжко с коллегами оценили, что этот последний переход происходит примерно около $x = 10^{425}$ . Числа в этой последовательности чемпионов по прыжкам — 2, 6, 30, 210, … — являются праймориалами; n-ный праймориал является произведением первых n простых чисел.

Почему праймориалы становятся предпочтительными интервалами между последовательными простыми числами? Если $p$ является достаточно большим простым числом, то $p + 2$ не может делиться на 2, $p + 6$ не может делиться на 2 и 3, $p + 30$ не может делиться на 2, 3 и 5, и в целом $p + P_{n}$ , где $P_{n}$ — это n-ный праймориал, не делится ни на один из первых n простых чисел. Разумеется $p + P_{n}$ всё равно может делиться на какое-то большое простое число, или может существовать другое простое число между $p$ и $p + P_{n}$ , такое, что интервал между простыми числами не гарантированно является праймориалом. Но эти интервалы имеют преимущество перед остальными претендентами.

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

Рисунок 13.

Снова явно выделяется интервал 6, насчитывающий 13,7% от общего количества, бо́льшие кратные числа 6 тоже выделяются среди своих непосредственных соседей. Стоит заметить и общую форму распределения: скопление слева (с пиком на числе 6) с последующим плавным снижением. Тренд похож на распределение Пуассона, и на самом деле это можно считать верным описанием.

Цветовая схема разрезает множество данных на доли по 19 значений в каждой. Голубая доля, в которую входят интервалы между простыми числами длиной от 0 до 18, насчитывает 68 процентов от всех интервалов, присутствующих в выборке из миллиона простых чисел; золотая доля добавляет ещё 23 процента. Остальные 9 процентов распределены широко и равномерно. На графике показаны не все интервалы: спектр продолжается до 210. (Одна пара последовательных простых чисел в выборке имеет расстояние 210, а именно 20 831 323 и 20 831 533.)

Похоже, на Рисунке 13 показана бо́льшая часть паттерна последовательных простых чисел по модулю19. Я могу сделать график ещё более информативным, внеся простое изменение. Начнём сдвигать каждую долю из 19-элементов, пока она не выровняется с долей 0, собираясь в столбики, находящиеся в одном столбце. Поскольку вторая (золотая) доля перемещается влево, пока столбик 19 не выровняется с столбцом 0, а третья (розовая) доля соединяет столбик 38 со столбиком 0. Физически этот процесс можно представить как вращение графика вокруг цилиндра с длиной окружности 19. Математически он составляет деление интервалов между простыми числами по модулю 19.

Diffs 8 digit primes 1000001 color stacked mod 19

Рисунок 14.

Если не обращать внимание на слишком яркие цвета, Рисунок 14 аналогичен Рисунку 12: высоты всех столбиков совпадают. Это не должно нас удивлять. На Рисунке 12 мы делим простые числа по модулю 19, а затем берём разности между последовательными разделёнными простыми числами. На Рисунке 14 мы берём разности между самими простыми числами, а затем делим эти разности по модулю 19. Две процедуры аналогичны:

$(p \bmod 19 - q \bmod 19) \bmod 19 = (p - q) \bmod 19.$

Изучив цвета, мы можем расставить все фрагменты головоломки на места. Почему простые числа mod 19 так часто разделены интервалом 6? Ну, на самом деле mod 19 имеет с этим мало общего; само число 6 в этой выборке является наиболее частым интервалом между простыми числами. Единственный другой существенный взнос в $\delta \equiv 6 \bmod 19$ возникает из третьей доли, особенно несколько пар простых чисел с расстоянием в 44.

Превосходство первой доли также объясняет неравенство между чётными и нечётными интервалами. Все интервалы в первой доле обязательно чётные, нечётные интервалы (mod 19) начинают появляться только во второй доле (интервалы от 19 до 37) и только по этой причине они менее часты. Для восьмиразрядных простых чисел выборки больше двух третей последовательных пар ближе, чем на 19 единиц, и поэтому оказываются в первой доле. (Медианное расстояние между простыми числами равно 12. Средний интервал равен 16,68, что близко к теоретическому предсказанию в 16,72.)

Наконец, Рисунок 14 может кое-что нам рассказать и о редкости интервалов 0 mod 19. Никакие два последовательных простых числа не могут попасть в один класс конгруэнции mod 19, если только они не разделены расстоянием 38 или числом, кратным 38. Поэтому такие пары не выходят на сцену до начала третьей доли, и в ней их не может быть слишком много. Выборка из миллиона простых чисел содержит 8 384 последовательных пар с расстоянием 38 — меньше одного процента от общего числа. И это основная причина того, что кость простых чисел так часто выпадает одной и той же гранью дважды подряд. В этом заключается причина появления голубой диагональной полосы во всех матрицах.

Я нахожу очень интересным то, что мы можем объяснить так много о паттерне последовательных простых чисел mod m, не углубляясь в подробности и не рассматривая особые свойства простых чисел. На самом деле мы можем воссоздать значительную часть паттерна вообще без использования простых чисел.

Две сотни лет назад Гаусс и Лежандр заметили, что по соседству с числом $x$ доля всех целых чисел, являющихся простыми, составляет примерно $1 / \log x$ . В 1936 году шведский математик Харальд Крамер предпожил интерпретировать эту долю как вероятность. Идея заключалась в том, чтобы пройти по всем целым числам по порядку, приняв каждое $x$ с вероятностью $1 / \log x$ . Числа в принятом множестве не будут являться простыми, кроме как по совпадению, но они будут иметь то же крупномасштабное распределение, что и распределение простых чисел. Вот несколько первых элементов списка миллиона таких «простых чисел Крамера», где процесс случайного выбора начинается с $x = 10^7$ :

Теперь предположим, что мы пропустим эти числа через тот же механизм, который применяли к простым числам. Мы поделим каждое простое число Крамера по модулю 19, а затем создадим матрицу последующих чисел $19 × 19$ :

Рисунок 15.

Выделяющиеся диагональные особенности выглядят похожими, но они гораздо проще, чем в соответствующих графиках простых чисел. Для любого простого числа Крамера p mod 19, наиболее вероятным последователем будет p + 1 mod 19, а наименее вероятным — p + 19 mod 19. Между этими предельными случаями находится плавный градиент частоты или вероятности со всего лишь несколькими небольшими флуктуациями, которые скорее всего можно списать на статистический шум.

В этой матрице отсутствует только шахматный узор. Мы можем частично восстановить его структуру, сгенерировав новое множество чисел, которое я называю «полупростыми числами Крамера». Они создаются тем же вероятностным просеиванием целых чисел, но в этот раз мы рассматриваем в качестве кандидатов только нечётные числа и изменим вероятность на $2\, / \log x$ , чтобы сохранить ту же плотность:

Heatmap 8 digit semicramers 1000001 mod 19

Рисунок 16.

Вот так лучше! При исключении из последовательности чётных чисел минимальный интервал между полупростыми числами равен 2, и это также является наиболее вероятным расположением.

Добавив ещё одно изменение, мы ещё сильнее приблизимся к имитации к матрице истинных простых чисел. Кроме исключения всех целых чисел, кратных 2, мы избавимся ещё и от кратных 3 и соответствующим образом изменим вероятность выборки. Назовём получившиеся числа «полуполупростыми числами Крамера».

Heatmap 8 digit demisemicramers 1000001 mod 19

Рисунок 17.

Заметьте, что 6 mod 19 — наиболее вероятный интервал между полуполупростыми числами Крамера, как и между истинными простыми числами, и что присутствуют те же отголоски на интервалах 12 и 18. И в самом деле, единственная очевидная разница между этой матрицей и Рисунком 10 (соответствующий график для истинных простых чисел) находится в столбце и строке для чисел, конгруэнтных 0 по модулю 19. Среди простых чисел таких чисел быть не может. Если мы устраним их и из чисел Крамера, то две матрицы становятся почти неотличимыми. Вот они обе:

Рисунок 18.

Если присмотреться, то можно найти различия — посмотрите на расширение диагонали на юго-восток от строки 1, столбца 15 —, но в целом эти модифицированные числа Крамера на удивление хорошо имитируют простые числа. На обеих диаграммах даже заметна симметрия относительно обратной диагонали. И не забывайте, что эти два множества содержат в общем только 19 процентов их значений: числа Крамера включают в себя 189 794 истинных простых чисел.

Я хочу добавить к этой истории ещё один поворот сюжета. Все приведённые выше примеры основаны на простых числах (или их аналогах) из восьми десятичных цифр, или, другими словами, числами по соседству с $10^7$ . Справедливы ли те же результаты для простых чисел с бо́льшими значениями? Рассмотрим таблицу, созданную из последовательных пар миллиона 40-разрядных простых чисел, взятых по модулю19. Паттерн оказывается знакомым, но более бледным:

Рисунок 19.

Перейдём к простым числам из 400 разрядов, снова поделённые по модулю 19, и получим цвета, выцветшие почти до неузнаваемости:

Рисунок 20.

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

Итак, похоже, что для пар последовательных простых чисел размер имеет значение. Чтобы разобраться в причинах этого, давайте посмотрим на группу различий между последовательными простыми числами в 40-разрядной выборке:

Рисунок 21.

По сравнению с распределением интервалов для восьмиразрядных простых чисел (Рисунок 13), спектр намного шире и более плоский. В этой форме график усекается на интервале 240; длинный «хвост» на самом деле растягивается далеко вправо, а наибольший разрыв между последовательными простыми числами находится в 1 328. Также, как предсказал Одлыжко с его коллегами, наиболее частый интервал между 40-разрядными простыми числами является не 6, а 30.

Из-за более широкого распределения интервалов, первая доля не может доминировать над поведением системы так, как она это делает сре