|
Professor Seleznov
|
Меня часто спрашивают, почему для математиков так важны простые числа. Роль, которую они играют в математике, сравнима с ролью атомов в химии. Это фундаментальные строительные блоки целых чисел, по крайней мере, когда дело касается умножения, и довольно часто решение какой-то задачи можно редуцировать до решения её сначала для простых. Но если честно, во многом математики интересуются простыми числами из-за того, что их сложно понять. В математике куча нерешённых задач о простых числах, поэтому для тех, кого привлекают сложные головоломки, простые числа обладают определённой привлекательностью, которая почти не зависит от их практической важности в математике и связанных с ней областях наподобие криптографии.
Во многом красота математики заключается в том, что благодаря произвольному выбору можно связать две кажущиеся далёкими концепции. Впервые я увидел этот паттерн в вопросе на Math Stack Exchange. Его задал пользователь dwymark, а ответил на него Грег Мартин; вопрос связан с распределением простых чисел, а также с рациональными аппроксимациями
.
Этот пользователь баловался с созданием графиков данных в полярных координатах, то есть нанесением точек в 2D-пространстве, но не по обычным координатам XY, а по расстоянию от точки начала координат, обычно называемому
(радиус), и по углу прямой относительно горизонтали, обычно называемому «тета»,
.
Image
Этот угол обычно задаётся в радианах; это значит, что угол
радиан — это половина окружности, а угол
— полная окружность. Стоит отметить, что полярные координаты не уникальны в том смысле, что прибавление
не меняет местоположения точки.
Какая из перечисленных точек в полярных координатах не равна точке
?
Проверить ответ
Последний ответ правильный,
. Прибавление или вычитание
из угла даёт тот же угол.
Паттерн, который мы будем рассматривать, связан с точками, обе координаты которых задаются одним простым числом.
Нет никакой практической причины заниматься этим. Это просто увлекательно! Мы резвимся в песочнице визуализации данных. Давайте пока начнём с целых чисел, не ограничиваясь простыми. Точка
находится на расстоянии 1 от точки начала координат с углом в 1 радиан.
имеет вдвое больший угол и вдвое большее расстояние. Аналогично, чтобы добраться до (3, 3), нужно выполнить поворот ещё на один радиан, получив суммарный угол чуть меньше
, и сделать ещё один шаг от точки начала координат.
Убедитесь, что понимаете принцип построения графика, потому что остальное будет зависеть этого понимания. Каждый шаг вперёд похож на поворот стрелки часов на 1 радиан и отдаление от центра на 1 единицу. Если продолжить дальше, эти точки будут спиралью расходиться наружу, образуя так называемую архимедову спираль.
Если исключить из построений все значения, кроме простых чисел, то поначалу график будет выглядеть довольно случайным. В конце концов, простые числа знамениты своим хаотичным и труднопредсказуемым поведением. Но при отдалении будут проявляться похожие на галактики спирали. Странно то, что некоторые рукава у них отсутствуют.
Отодвинувшись ещё дальше, мы увидим, что эти спирали начинают создавать другой паттерн: множество исходящих наружу лучей. Похоже, в основном эти лучи группируются по четыре, иногда пропуская участки, как будто расчёска, у которой нет некоторых зубьев.
Возникает логичный вопрос: что тут вообще происходит? Откуда берутся эти спирали и почему при большом масштабе мы получаем прямые линии? Можно подсчитать, что спиралей 20, а если отдалиться и пересчитать каждый луч, то мы получим ровно 280. Но, разумеется, всё это приводит к новым вопросам о происхождении этих чисел и о том, как они появились из простых.
Эти паттерны, конечно, красивы, но не содержат скрытого божественного послания о простых числах. Должен сказать сразу: то, что автор вопроса на Math Stack Exchange перешёл напрямую к простым, немного сбивает нас с пути. Если мы взглянем на все целые числа, а не на одни простые, то увидим очень похожие спирали.
Они гораздо чётче и их теперь 44, но это значит, что вопрос о происхождении спиралей совершенно отдельный от того, что происходит, если мы ограничиваемся только простыми (да, это может кого-то разочаровать).
Но не торопитесь расстраиваться: вопрос о том, почему мы вообще наблюдаем спирали — это тоже замечательная головоломка. И если даже их причина не простые числа, вопрос о том, что произойдёт, если мы отфильтруем только простые, на самом деле приведёт к одной из важнейших теорем о распределении простых чисел — к теореме Дирихле.
Ингредиенты спирального пи
Заметили ли вы, что при гораздо меньшем масштабе у нас было 6 маленьких спиралей? С этого можно начать объяснение, что происходит в двух паттернах большего размера. Обратите внимание, что один из рукавов спирали образует числа, кратные 6. Следующая — это каждое число на единицу больше числа, кратного 6, а после неё идёт рукав, включающий в себя числа, кратные 6 плюс 2 и так далее. Почему так получается?
Вспомним, что на каждом шаге последовательности необходимо выполнить поворот на один радиан, то есть когда мы досчитаем до 6, совершится поворот на 6 радиан, что чуть меньше
, то есть полного оборота. То есть каждый раз, когда мы досчитаем до 6, произойдёт почти полный оборот, но ненамного меньше. Спустя ещё шесть шагов угол будет слегка меньше; угол будет немного меняться, создавая иллюзию одной кривой.
Если ограничиться простыми числами, то все рукава спирали, кроме двух, пропадут. Задумайтесь об этом: простое число не может быть кратным 6. Не может оно и быть на 2 больше числа, кратного 6, если только это не 2, как и не может быть на 4 больше числа, кратного 6, потому что всё это чётные числа. Также оно не может быть на 3 больше числа, кратного 6 (если это не само число 3), потому что все эти числа кратны 3.
Пока мы не перешли к сложному контексту, я введу некоторые термины, используемые математиками. Каждая из этих последовательностей, которые мы отсчитываем вверх с шагом 6, называется «классом вычетов по модулю 6». Слово «вычет» в этом контексте означает «остаток», а под модулем n (mod) подразумевается «от деления на n». Обозначение «класс вычетов по модулю 6» означает «множество остатков от деления на 6».
Image
Например, 6 помещается в 20 три раза с остатком 2, поэтому 20 имеет «вычет 2 по модулю 6».
Image
Со всеми остальными числами с остатком 2 при делении на 6 оно образует полный «класс вычетов». Да, это выглядит, как самый претенциозный способ сказать «всё, что на 2 больше чисел, кратных 6», но так и есть! Впрочем, это стандартный жаргон, позволяющий объяснять идеи в одинаковой терминологии.
Итак, в этой терминологии каждая из рукавов спирали соответствует классу вычетов по модулю 6, и причина этого в том, что 6 близка к
; поворот на 6 радиан почти равен полному обороту. А причина, по которой мы видим только два рукава при выборе простых чисел, заключается в том, что все простые числа или на 1, или на 5 больше чисел, кратных 6 (за исключением 2 и 3). Остальные четыре класса вычетов содержат числа, которые или чётные, или кратны трём.
К какому классу вычетов по модулю 6 относится число 381?
Проверить ответ
Правильный ответ: результат деления на 6 число 381 равен 63, а остаток равен 3, поэтому оно относится к классу вычетов
.
Пока это был только разогрев. Давайте теперь поразмыслим о паттернах большего масштаба. Аналогично тому, что 6 шагов были близки к полному обороту, 44 шага очень близки и целому количеству оборотов.
Image
Так как на оборот получается
радиан, 44 шага даёт суммарно
оборота, что оказывается лишь ненамного больше 7 полных оборотов. Можно также записать это, показав, что
— это близкая аппроксимация
; некоторые читатели могут увидеть в этом знаменитую аппроксимацию
числа
.
То есть если посчитать в диаграмме по количеству чисел, кратных 44, то окажется, что каждая точка находится почти под тем же углом, что и предыдущая, только ненамного больше, поэтому добавляя точки, мы получим плавную спираль. Все числа на 1 больше чисел, кратных 44, образуют похожую спираль, но повёрнутую на радиану против часовой стрелки. Аналогично для чисел, на 2 больше чисел, кратных 44, и так далее.
Если сформулировать это более строгим математическим языком, то каждый из этих рукавов спирали оказывается классом вычетов по модулю 44. Возможно, вы уже поняли, что произойдёт, если мы ограничимся только простыми числами.
Простые числа не могут быть кратными 44, поэтому этот рукав не будет виден. Аналогично, мы не увидим простые числа на 2 больше чисел, кратных 44, или на 4 больше и так далее, потому что все эти классы вычетов состоят лишь из чётных чисел.
Из всех классов вычетов по модулю 44 при фильтрации по простым числам остаются видимыми только 20 рукавов.
Аналогично, ни одно число, кратное 11, не может быть простым, за исключением самого числа 11, поэтому спираль чисел на 11 больше чисел, кратных 44, не будет видна, как не будет видна и спираль чисел на 33 больше чисел, кратных 44. Все оставшиеся спирали будут классом вычетов, не имеющим никаких общих делителей с 44. В каждом из этих рукавов простые числа кажутся распределёнными достаточно случайно, но это мы пока оставим на будущее.
Здесь нам снова стоит познакомиться с жаргоном, которым пользуются математики. Для нас важны все числа от 0 и 43, не имеющие никаких простых делителей, общих с 44, то есть нечётные и не делящиеся на 11. Два числа, не имеющие общих составляющих их делителей, называются взаимно простыми.
Мы можем подсчитать, что от 1 до 44 есть 20 взаимно простых с 44 чисел. В теории чисел это компактно записывается следующим образом:
Греческая буква «фи» (
) здесь обозначает функцию Эйлера. Она определяется как количество целых чисел от 1 до
, которые являются взаимно простыми с
.
Если объяснять вкратце, то пользователь Math Stack Exchange наблюдал два не связанных друг с другом элемента теории чисел, проиллюстрированных одним изображением: во-первых,
как близкую рациональную аппроксимацию
, что приводит к чёткому отделению классов вычетов по модулю 44. Во-вторых, многие из этих классов вычетов содержат 0 или 1 простых чисел, поэтому не видны на графиках, в то время как простых чисел в оставшихся 20 классах вычетов достаточно много для того, чтобы эти спиральные рукава были видны.
Наверно, теперь вы сможете предсказать, что происходит в более крупных масштабах. Аналогично тому, что 6 радиан приблизительно равны полному обороту, а 44 радианы достаточно близки к 7 полным оборотам, получается, что 710 радиан крайне близки к целому количеству оборотов.
Если конкретнее, 710 радиан — это
оборотов, что равно 113 запятая ноль ноль ноль ноль ноль девять. Это эквивалентно заявлению, что
— это очень близкая рациональная аппроксимация
, что можно распознать, как известную аппроксимацию
числа
.
Если вы хотите понять, откуда берутся подобные рациональные аппроксимации и почему они могут считаться «необычно хорошими», то предлагаю вам посмотреть замечательное видео mathologer.
Это означает, что при движении вперёд с шагом 710 угол каждой новой точки будет почти таким же, как предыдущий, только на микроскопическую часть больше. Даже при очень больших масштабах такая последовательность кажется прямой. И, разумеется, другие классы вычетов по модулю 710 тоже образуют почти прямые линии.
710 радиан так близки к целому количеству оборотов, что класс вычетов 710k кажется почти полностью находящимся на оси X
Всего их 710, а пикселей на экране ограниченное количество, поэтому различить их будет довольно сложно. Поэтому в этом случае лучше ограничиться только простыми, для которых классов вычетов не так много.
В каком квадранте находился бы класс
на показанном выше графике?
Проверить ответ
, а
, поэтому начало кривой будет находиться в третьем квадранте. Если ваш калькулятор находится в режиме градусов, то вы по ошибке могли получить первый квадрант!
На самом деле, отдалившись ещё немного, мы сможем разглядеть в них плавную спираль, однако то, что для её проявления нужен такой большой масштаб — замечательная иллюстрация того, насколько хороша аппроксимация
значения
1.
1 Число
в этом отношении немного необычно. Если взять другие известные иррациональные числа, например,
,
или
, и попытаться аппроксимировать их дробью с не очень большим знаменателем (скажем, не больше 200), то подобной точности и близко не добиться. Разумеется, любое иррациональное число можно аппроксимировать с произвольной точностью при помощи дробей, только для хорошей точности обычно требуется довольно сложная дробь, то есть имеющая большой знаменатель.
Чтобы понять, что произойдёт при фильтрации одних простых чисел, нужно проделать полностью аналогичный предыдущему процесс. Простые делители 710 — это 71, 5 и 2. Поэтому если остаток делится на одно из этих чисел, то это наше число.
Если взять все классы вычетов с нечётными числами, то это будет выглядеть, как каждый луч в нашей заполненной точками картине. Из тех, что остались, это единственные числа, кратные пяти, которые красиво и равномерно распределены по каждой пятой прямой. Стоит отметить, что отсутствие в них простых чисел объясняет этот паттерн линий, сгруппированных по четыре. А из этих оставшихся есть четыре класса вычетов, кратных 71, поэтому простые числа в них встречаться не будут. Это объясняет, почему в некоторых группах из четырёх как будто отсутствует зубец.
Слева вверху показан график всех классов вычетов. На каждом последующем графике по одному отфильтровываются простые делители
Из этого следует встречавшееся нам выше число 280: мы получаем его, подсчитав все числа от 1 до 710, не имеющие общих делителей с 710; это те числа, которые мы не можем исключить.
Функция Эйлера
Разумеется, это не гарантирует, что в каждой конкретной кривой будут находиться простые числа, но если взглянуть на изображение, то можно увидеть, что в этих оставшихся классах простые числа распределены довольно равномерно.
Мы видим все цвета радуги, и это показывает, что в каждом оставшемся классе вычетов примерно одинаковая плотность простых чисел
Теорема Дирихле
На самом деле, наше последнее замечание связано с довольно глубоким свойством, известным в теории чисел как «теорема Дирихле». Чтобы взять пример попроще, выберем классы вычетов по модулю 10, а не 710. Так как мы записываем числа в десятичной системе, это эквивалентно группированию чисел по их последней цифре. То есть числа, заканчивающиеся на 0, образуют один класс вычетов, числа, заканчивающиеся на 1, другой и так далее.
За исключением числа 2, простые числа не могут иметь в последнем разряде чётную цифру, иначе бы они были чётными. Аналогично, ни одно простое число больше 5 не может заканчиваться на 5. В этом нет ничего удивительного: простые числа больше 5 должны заканчиваться на 1, 3, 7 или 9.
Как будут распределены простые числа между классами вычетов 0 по модулю 2 и 1 по модулю 2?
Проверить ответ
Все простые числа, за исключением 2, будут находиться в классе вычетов 1 по модулю 2, потому что он содержит все нечётные числа. Класс 0 по модулю 2 содержит все чётные числа, а единственное простое чётное — это 2.
Гораздо более тонкий вопрос заключается в том, как простые числа распределены по оставшимся четырём группам. Давайте создадим небольшую гистограмму, подсчитав все целые числа и показав в ней долю простых чисел с соответствующей последней цифрой. Можете спрогнозировать, что будет происходить при добавлении новых простых чисел?
Доля второго и пятого классов вычетов при добавлении новых простых чисел стремится к нулю
При добавлении на гистограмму новых простых чисел они довольно равномерно распределяются по этим четырём классам, примерно по 25% в каждом. Возможно, именно этого вы и ожидали. В конце концов, почему бы простые числа предпочитали какую-то одну последнюю цифру вместо другой? Но крайне неочевидно, как доказать это утверждение. Да и как нам сформулировать строгим математическим языком, что именно мы хотим доказать?
Математик мог бы подойти к этому таким образом: если мы возьмём все простые числа меньше
для какого-то большого
и рассмотрим, какая их доля, допустим, на единицу больше чисел, кратных 10, то при стремлении
к бесконечности эта доля должна стремиться к
.
Аналогично для всех остальных допустимых классов вычетов 3, 7 и 9. И, разумеется, в числе 10 нет ничего особенного, аналогичное утверждение должно быть справедливым для всех других чисел.
Вернёмся к нашим старым друзьям — классам вычетов по модулю 44. Например, создадим похожую гистограмму, показав долю простых чисел, встречающихся в каждом из них. Здесь мы снова будем наблюдать, что они равномерно распределяются по 20 допустимым классам, то есть каждый рукав спирали в нашей диаграмме будет содержать примерно то же количество простых чисел, что и другие. И, как вы, наверно, могли догадаться, это ужасно сложно доказать математически.
Все чётные классы и 11 + 33 быстро снижаются до нуля, пропадая из списка рукавов спирали.
Сколько простых чисел будет в 71-м столбце гистограммы для спирального паттерна большего размера (r mod 710)?
Проверить ответ
Всего одно! 71 — это единственный из простых делителей 710, поэтому после размещения в столбце числа 71 за ним не появится никаких новых простых чисел.
Гистограммы наглядно показывают то, что мы подразумеваем под равномерным распределением, но будет познавательно сформулировать его в математической терминологии. По сути, это то, что мы наблюдали для 10, только в более общем виде. Снова рассмотрим все простые числа до какой-то границы
, но теперь зададимся вопросом, не какая их доля имеет вычет, допустим, 1 по модулю 10, а какая доля имеет вычет
по модулю
, где
— это любое число, а
— любое взаимно простое с
число.
Напомню, что «взаимно простые» означает, что числа не имеют общих делителей, за исключением 1. Доля таких чисел стремится не к
, а к
, где
— это упомянутая мной выше специальная функция, возвращающая количество взаимно простых с
вычетов. Например:
На случай, если вам слишком уж всё понятно, скажу, что в записи используется специальная функция подсчёта простых чисел, которая имеет сбивающее с толку название
, никак не связанное с числом
.
У нас кончаются символы!
Чему равно это уравнение?
Проверить ответ
, а из подсчёта видимых рукавов самой маленькой спирали мы знаем, что
Оказывается, таким образом довольно сложно доказать, что простые числа распределены равномерно по классам вычетов. В 1837 году Густав Лежён Дирихле опубликовал результат своей работы, который был достаточно близок к этому, но в нём использовалось немного иное определение плотности. Вместо простого подсчёта простых чисел до определённой границы в нём применялось сложение всех простых значений
для вещественного числа
. В частности, в этой записи плотность простых чисел
по модулю
выглядит так:
Она кажется более сложной, но если воспользоваться применённым Дирихле подходом, математически с ней управиться проще. Однако подлинная ценность этого результата заключалась в том, что он впервые показал, что в любом классе вычетов есть бесконечно большое количество простых чисел (при условии, что
и
взаимно простые).
Например, вам нужно доказать, что на цифру 1 заканчивается бесконечно большое количество простых чисел. Для этого можно показать, что на 1 заканчивается четверть от всех простых чисел. С сочетанием с известным со времён Евклида фактом, что простых чисел существует бесконечное количество, это даёт нам гораздо более сильное и интересное утверждение.
Как же Дирихле это доказал? Доказательство будет гораздо сложнее, чем я мог бы здесь привести; однако стоит сказать, что в нём активно используется комплексный анализ, то есть математический анализ с функциями, входными и выходными данными которых являются комплексные числа. Это может показаться неожиданным, ведь простые числа как будто никак не связаны с непрерывным миром матанализа, не говоря уже о внезапном появлении на сцене комплексных чисел. Но ещё с начала 19-го века это абсолютно согласовалось с процессом исследования распределения простых чисел.
И это не просто устаревшая технология. Подобный анализ распределения простых чисел в классах вычетов остаётся актуальным и в современных исследованиях2. Часть недавних открытий, связанных с малыми расстояниями между простыми числами и приближающихся к постоянно ускользающему доказательству гипотезы о простых числах-близнецах, основана на понимании распределения простых чисел между подобными классами вычетов.
От произвольного к важному
Под конец я хочу кое-что подчеркнуть. В каком-то смысле, та визуализация данных, которая привела к появлению этих паттернов... не имеет значения. Она никому не интересна. Нет ничего естественного в создании графиков
в полярных координатах, и по большей мере загадка этих спиралей возникла из-за артефактов, проявляющихся из-за того, что мы работали с целым числом радиан.
С другой стороны, подобные игры, очевидно, стоили конечного результата: последовательности вопросов, приведших нас к теореме Дирихле, которая на самом деле важна, особенно если она вдохновит вас разобраться с тактикой получения её доказательства.
И нет ничего случайного в том, что достаточно случайный вопрос может привести нас к важному и сложному математическому факту. Степень важности математического знания определяется его связью с другими темами. Поэтому даже при таких произвольных исследованиях чисел (при условии, если они выбраны не совсем произвольно) высока вероятность наткнуться на что-то существенное.
Моя точка зрения: важность определяется количеством связей
Да, можно получить гораздо более сконцентрированную дозу важных фактов, прочитав учебник или курс, не зайдя при этом в такое количество неинтересных тупиков. Но в самостоятельном открытии таких тем есть что-то необычное. Если вы заново изобрели функцию Эйлера, ещё не зная, как она определяется, или начали задаваться вопросами о рациональных аппроксимациях, ещё не зная о непрерывных дробях, или серьёзно исследовали распределение простых чисел по классам вычетов, ничего не слышав о Дирихле, то вы по-настоящему изучите эти темы и они станут вам близкими друзьями, а не какими-то произвольными определениями.
Сложное исследование
Чтобы продемонстрировать, на что похоже исследование произвольного пути в математике, давайте расширим эту задачу на три измерения. Сферические координаты позволяют задавать расположение точек в 3D-пространстве при помощи расстояния от точки начала координат, угла от оси
и угла от оси
. В сжатом виде формула выглядит так:
Если мы возьмём первые несколько тысяч простых чисел и создадим их график в полярных координатах, то какой паттерн проявится?
Спиральная галактика, которую мы видели в 2D, по-прежнему присутствует, но теперь она похожа на какую-то спираль в виде знака бесконечности, в которой рукава пронизывают друг друга. 11-й и 33-й классы так же отсутствуют по обе стороны от центра. В оригинале статьи изображение интерактивно, так что можете изучить его самостоятельно.
2D-график вызвал у нас вопросы наподобие: «Почему здесь есть спирали?» и «Почему в некоторых рукавах простые числа отсутствуют?». При взгляде на 3D-график возникает вопрос: «Почему спираль имеет паттерн символа бесконечности?». Как и первые два вопроса, этот тоже не связан ни с одним из предыдущих вопросов. Попробуйте сами объяснить, почему в сферических координатах проявляется эта форма. Рекомендую обсудить этот новый вопрос с сообществом математиков. Какие важные темы поднимаются при исследовании этих произвольно выбранных построений? Продолжив своё путешествие в мир математики, помните, что иногда головоломку следует разбить на более простые компоненты, с которыми легче разбираться по отдельности.
Связь со скатертью Улама
Возможно, вы видели замечательное видео Numberphile под названием Prime Spirals, в котором Джеймс Граймс описывает похожий, но отличающийся паттерн простых чисел. Если вы его ещё не видели, то рекомендую посмотреть. Идея заключается в том, чтобы записывать все числа в сетке, начиная от центра и по спирали, обводя при этом все простые. Получившийся паттерн называется «скатерть Улама»; она названа в честь Станислава Улама, впервые заметившего его, когда он чертил линии, слушая какой-то скучный доклад.
Можно заметить, что при большом масштабе паттерн смещается к отдельным полосам. В нашем примере спирали и лучи соответствуют определённым линейным функциям наподобие
и
, где вместо
подставлено какое-то целое число. Паттерн скатерти Улама, о котором рассказывается в видео Numberphile, демонстрирует нечто более сложное: определённые квадратные функции как будто имеют больше простых чисел, чем другие. Существует аналог теоремы Дирихле — теорема Чеботарёва о плотности, формулирующая ожидаемую плотность простых чисел в определённых паттернах многочленов наподобие этого. Подробности теоремы слишком сложны для нашей статьи. В целом же из неё можно заключить не только то, что в простых числах есть множество паттернов, но и то, что математики достаточно хорошо поняли многие из этих паттернов, несмотря на то, что простые числа имеют репутацию крайне загадочных.-Источник
|
