О спирали Улама | Распределение простых чисел и многочлен Эйлера

Рисунок на полях 1963 года

Станислав Улам нашёл спираль в 1963 году во время доклада на научной конференции, который Мартин Гарднер позже назвал длинным и очень скучным. Улам записал натуральные числа по спирали на квадратной сетке и обвёл простые числа. Кружки выстроились в линии. Затем вместе с Майроном Стейном и Марком Уэллсом он расширил картинку примерно до 100 000 точек на компьютере MANIAC II в Лос-Аламосе. Колонка Гарднера «Математические игры» в Scientific American за март 1964 года вынесла спираль на обложку. Эти линии не доказывают, как расположены простые числа. Они позволяют увидеть факт, который теория чисел уже знала в другой форме: некоторые квадратичные многочлены дают простые числа гораздо чаще других.

Как заполняется квадрат

Спираль начинается с 1 в центре. Следующее число стоит на шаг правее, затем путь поворачивает налево, против часовой стрелки, и каждый прямой участок на шаг длиннее предыдущего: шаг, шаг, два, два, три, три и так далее. Первый полный квадрат читается по строкам: 17 16 15 14 13, затем 18 5 4 3 12, затем 19 6 1 2 11, затем 20 7 8 9 10, затем 21 22 23 24 25. Можно начать и не с 1. Появляются такие же линии. Начало с 41 — знаменитый случай.

Линии — это квадратичные многочлены

Каждая диагональ и каждый горизонтальный или вертикальный луч — это ровно множество значений квадратичного многочлена f(n) = 4n² + bn + c. Если b чётно, линия диагональная, а все значения в зависимости от c либо нечётные, либо чётные. Все простые числа, кроме 2, нечётны, поэтому простые лежат на каждой второй диагонали. Некоторые из этих многочленов раскладываются на множители. 4n² + 8n + 3 = (2n + 1)(2n + 3), поэтому эта диагональ почти пуста. Другие удивительно часто дают простые числа. Разница не волшебство. Всё дело в том, как часто многочлен вынужден делиться на малое простое число. Гипотеза F Харди и Литлвуда, частный случай гипотезы Бейтмана — Хорна, предсказывает плотность вдоль ax² + bx + c. Плотность зависит от дискриминанта b² − 4ac. Ни для одного квадратичного многочлена не доказано, что он даёт бесконечно много простых чисел. Это одна из проблем Ландау, и она до сих пор открыта.

Сорок простых чисел Эйлера

Многочлен Эйлера n² + n + 41 даёт простое число при каждом n от 0 до 39. Это сорок простых чисел. При n = 40 он даёт 1681 = 41², и серия обрывается. На спирали эти значения — один многочлен 4n² − 2n + 41, то есть многочлен Эйлера на чётных числах, вместе с противоположным направлением 4n² + 2n + 41. Они складываются в одну прямую диагональ, если в центральной клетке стоит 41, а не 1. Непрерывная серия — это сорок значений от 1523 (девятнадцать шагов к юго-западу от центра) через 41 до 1601 (двадцать шагов к северо-востоку). Следующие клетки, 1681 и 1763, составные, поэтому золотая линия обрывается. Константа Харди и Литлвуда для 4n² − 2n + 41 равна примерно 6,6: по гипотезе эти значения простые почти в семь раз чаще, чем случайные числа того же размера.

Зачем нужна эта картинка

Спираль не решает вопрос о теореме о распределении простых чисел, а длинная диагональ — не доказательство. Это карта. Квадратичные многочлены, богатые и бедные простыми числами, видны с первого взгляда, и именно поэтому Улам, а до него в 1932 году Лоренс Клаубер, взяли на себя труд их нарисовать. Клаубер использовал треугольник, строки которого идут от одного квадрата до следующего. Позже Роберт Сакс разместил целые числа на спирали Архимеда так, что на каждый виток приходится один квадрат; там многочлен Эйлера — кривая, а не два диагональных луча. В квадратной спирали смотреть стоит на формулу линии под пальцем, на то, сколько на ней простых чисел, и как это соотносится с 1 / ln n — вероятностью того, что случайное число такого размера простое.

Исследуйте её в PictorX

Откройте спираль Улама — и увидите классическую картину: квадрат 101×101, простые числа золотом, составные скрыты. Перетаскивайте, чтобы двигать, и прокручивайте, чтобы масштабировать. Избранное «Сетка 5×5» выписывает каждое число, чтобы вы могли сверить путь с квадратом выше. «40 Эйлера» начинает спираль с 41 и рисует 4n² − 2n + 41. «Самая богатая линия» ищет в обоих диагональных направлениях линию с наибольшим числом простых. Нажмите на любую клетку, чтобы увидеть её диагональ с многочленом, самой длинной серией простых и сравнением со случайным числом того же размера. «Остаток mod 4» и «Последняя цифра» перекрашивают простые числа. Сохраните PNG или откройте холст в редакторе PictorX. Сочетайте её с гипотезой Коллатца или муравьём Лэнгтона — ещё простые правила с удивительной картиной.

Часто задаваемые вопросы

Кто открыл спираль Улама?

Станислав Улам в 1963 году, когда рисовал от скуки на научном заседании. Мартин Гарднер популяризировал её в Scientific American в марте 1964 года. Лоренс Клаубер ещё в 1932 году нарисовал родственную треугольную таблицу простых чисел.

Почему простые числа выстраиваются в линии?

Диагональ, строка или столбец квадратной спирали — это квадратичный многочлен 4n² + bn + c. Некоторые из этих многочленов необычно часто делятся на малое простое число, а некоторые почти никогда. Простые числа — это то, что остаётся.

Чем особенен многочлен n² + n + 41?

Он даёт простые числа при n = 0, 1, 2, …, 39 — сорок простых — и составное при n = 40, потому что значение равно 41². Если начать спираль с 41, эта серия станет одной диагональю: от 1523 через 41 до 1601, то есть значения 4n² − 2n + 41.

Доказывает ли спираль, как распределены простые числа?

Нет. Она показывает те колебания, которые пытается предсказать гипотеза F Харди и Литлвуда. Ни для одного квадратичного многочлена не доказано, что он порождает бесконечно много простых чисел.