Спираль Улама

Визуализация простых чисел, образованных путем расположения целых чисел по спирали

Спираль Улама размером 201×201. Черные точки представляют простые числа. Хорошо видны диагональные, вертикальные и горизонтальные линии с высокой плотностью простых чисел.

Для сравнения: спираль со случайными нечетными числами, окрашенными в черный цвет (при той же плотности простых чисел в спирали 200х200).

Спираль Улама или спираль простых чисел — это графическое изображение набора простых чисел , изобретенное математиком Станиславом Уламом в 1963 году и вскоре популяризированное в колонке Мартина Гарднера «Математические игры» в журнале Scientific American ^{. [1]} Он состоит из записи положительных целых чисел в квадратной спирали и специальной маркировки простых чисел.

Улам и Гарднер подчеркнули поразительное появление в спирали заметных диагональных, горизонтальных и вертикальных линий, содержащих большое количество простых чисел. И Улам, и Гарднер отметили, что существование таких заметных линий не является неожиданным, поскольку линии в спирали соответствуют квадратичным многочленам , и  считается, что некоторые такие многочлены, такие как полином Эйлера, порождающий простые числа x ²  −  x + 41, создают высокую плотность простых чисел. ^{[2] [3]} Тем не менее, спираль Улама связана с основными нерешенными проблемами теории чисел , такими как проблемы Ландау . В частности, никогда не было доказано, что ни один квадратичный многочлен порождает бесконечное количество простых чисел, не говоря уже о том, что он имеет их высокую асимптотическую плотность, хотя существует хорошо обоснованная гипотеза относительно того, какой должна быть эта асимптотическая плотность.

В 1932 году, за 31 год до открытия Улама, герпетолог Лоуренс Клаубер построил треугольную неспиральную решетку, содержащую вертикальные и диагональные линии, демонстрирующие аналогичную концентрацию простых чисел. Как и Улам, Клаубер отметил связь с полиномами, порождающими простые числа, такими как полиномы Эйлера. ^[4]

Строительство

Спираль Улама строится путем записи целых положительных чисел по спирали на квадратной решетке :

а затем отмечаем простые числа:

На рисунке простые числа кажутся сосредоточенными вдоль определенных диагональных линий. На спирали Улама 201×201, показанной выше, четко видны диагональные линии, что подтверждает продолжение узора. Горизонтальные и вертикальные линии с высокой плотностью простых чисел, хотя и менее заметные, также очевидны. Чаще всего числовую спираль начинают с цифры 1 в центре, но можно начинать и с любой цифры, при этом наблюдается одинаковая концентрация простых чисел вдоль диагональных, горизонтальных и вертикальных линий. Начиная с 41 в центре, получается диагональ, содержащая непрерывную строку из 40 простых чисел (начиная с 1523 к юго-западу от начала координат, уменьшаясь до 41 в начале и увеличиваясь до 1601 к северо-востоку от начала координат), самый длинный пример такого рода. ^[5]

История

По словам Гарднера, Улам открыл спираль в 1963 году, рисуя во время презентации «длинной и очень скучной статьи» на научном собрании. ^[1] Эти ручные подсчеты составили «несколько сотен пунктов». Вскоре после этого Улам вместе с коллегами Майроном Стейном и Марком Уэллсом применил MANIAC II в научной лаборатории Лос-Аламоса, чтобы расширить расчет примерно до 100 000 точек. Группа также вычислила плотность простых чисел среди чисел до 10 000 000 как по некоторым линиям с богатым числом простых чисел, так и по некоторым линиям с бедным числом простых чисел. Изображения спирали размером до 65 000 точек были отображены на «прилагаемом к машине телескопе», а затем сфотографированы. ^[6] Спираль Улама была описана в колонке Мартина Гарднера « Математические игры» в журнале Scientific American за март 1964 года и помещена на обложку этого номера. В колонке были воспроизведены некоторые фотографии Штейна, Улама и Уэллса.

В приложении к колонке Scientific American Гарднер упомянул более раннюю статью Клаубера. ^{[7] [8]} Клаубер описывает свою конструкцию следующим образом: «Целые числа расположены в треугольном порядке с 1 в вершине, вторая строка содержит числа от 2 до 4, третья от 5 до 9 и т. д. Когда простые числа имеют было указано, обнаружено, что существуют концентрации в определенных вертикальных и диагональных линиях, и среди них обнаружены так называемые последовательности Эйлера с высокой концентрацией простых чисел». ^[4]

Объяснение

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

${\displaystyle f(n)=4n^{2}+bn+c}$

где b и c — целочисленные константы. Когда b четно, линии диагональные, и либо все числа нечетные, либо все четные, в зависимости от значения c . Поэтому неудивительно, что все простые числа, кроме 2, лежат на чередующихся диагоналях спирали Улама. Некоторые многочлены, такие как , производя только нечетные значения, факторизуются по целым числам и поэтому никогда не являются простыми, за исключением случаев, когда один из множителей равен 1. Такие примеры соответствуют диагоналям, которые лишены простых чисел или почти таковы. ${\displaystyle 4n^{2}+8n+3}$ ${\displaystyle (4n^{2}+8n+3)=(2n+1)(2n+3)}$

Чтобы понять, почему некоторые из оставшихся нечетных диагоналей могут иметь более высокую концентрацию простых чисел, чем другие, рассмотрим и . Вычислите остатки при делении на 3, поскольку n принимает последовательные значения 0, 1, 2, .... Для первого из этих многочленов последовательность остатков равна 1, 2, 2, 1, 2, 2, ..., а для второго это 2, 0, 0, 2, 0, 0, .... Это означает, что в последовательности значений, принимаемых вторым многочленом, два из каждых трех делятся на 3 и, следовательно, определенно не простое число, в то время как в последовательности значений, принимаемых первым многочленом, ни одно из них не делится на 3. Таким образом, кажется правдоподобным, что первый многочлен будет давать значения с более высокой плотностью простых чисел, чем второй. По крайней мере, это наблюдение не дает оснований полагать, что соответствующие диагонали будут одинаково заполнены простыми числами. Конечно, следует учитывать деление на простые числа, отличные от 3. При рассмотрении делимости на 5 остатки при делении на 15 повторяются по образцу 1, 11, 14, 10, 14, 11, 1, 14, 5, 4, 11. , 11, 4, 5, 14 для первого полинома и с шаблоном 5, 0, 3, 14, 3, 0, 5, 3, 9, 8, 0, 0, 8, 9, 3 для второго, подразумевая что только три из 15 значений во второй последовательности потенциально являются простыми (они не делятся ни на 3, ни на 5), тогда как 12 из 15 значений в первой последовательности потенциально являются простыми (поскольку только три из них делятся на 5 и ни одно не делится на 3). ${\displaystyle 4n^{2}+6n+1}$ ${\displaystyle 4n^{2}+6n+5}$

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

Гипотеза Харди и Литтлвуда F.

В своей статье 1923 года о гипотезе Гольдбаха Харди и Литтлвуд выдвинули ряд гипотез, одна из которых, если она верна, могла бы объяснить некоторые поразительные особенности спирали Улама . Эта гипотеза, которую Харди и Литтлвуд назвали «гипотезой F», является частным случаем гипотезы Бейтмана-Хорна и утверждает асимптотическую формулу для количества простых чисел вида ax ²  +  bx  +  c . Лучи, исходящие из центральной области спирали Улама, составляющие углы 45° с горизонтом и вертикалью, соответствуют числам вида 4 x ²  +  bx  +  c с четным b ; горизонтальные и вертикальные лучи соответствуют числам одного вида с нечетным b . Гипотеза F дает формулу, которую можно использовать для оценки плотности простых чисел вдоль таких лучей. Это означает, что будет значительная изменчивость плотности вдоль разных лучей. В частности, плотность очень чувствительна к дискриминанту полинома b ²  - 16 c .

Простые числа вида 4 x ²  − 2 x  + 41 с x  = 0, 1, 2, ... выделены фиолетовым цветом. Заметная параллельная линия в нижней половине рисунка соответствует 4 x ²  + 2 x  + 41 или, что то же самое, отрицательным значениям x .

Гипотеза F касается многочленов вида ax ²  +  bx  +  c , где a , b и c — целые числа, а a — положительное число. Если коэффициенты содержат общий делитель больше 1 или если дискриминант Δ =  b ²  − 4 ac является полным квадратом , многочлен факторизуется и, следовательно, дает составные числа, поскольку x принимает значения 0, 1, 2, ... (кроме возможно, для одного или двух значений x , где один из множителей равен 1). Более того, если a  +  b и c оба четны, полином дает только четные значения и, следовательно, является составным, за исключением, возможно, значения 2. Харди и Литтлвуд утверждают, что, за исключением этих ситуаций, ax ²  +  bx  +  c принимает простые значения. бесконечно часто, когда x принимает значения 0, 1, 2, ... Это утверждение является частным случаем более ранней гипотезы Буняковского и остается открытым. Харди и Литтлвуд далее утверждают, что асимптотически число P ( n ) простых чисел вида ax ²  +  bx  +  c и меньше n определяется выражением

${\displaystyle P(n)\sim A{\frac {1}{\sqrt {a}}}{\frac {\sqrt {n}}{\log n}}}$

где A зависит от a , b и c, но не от n . По теореме о простых числах эта формула с набором A , равным единице, представляет собой асимптотическое число простых чисел меньше n , ожидаемое в случайном наборе чисел, имеющем ту же плотность, что и набор чисел вида ax ²  +  bx  +  c . Но поскольку А может принимать значения больше или меньше 1, то некоторые многочлены, согласно гипотезе, будут особенно богаты простыми числами, а другие – особенно бедны. Необычайно богатый полином 4 x ²  − 2 x  + 41 образует видимую линию в спирали Улама. Согласно гипотезе , константа A для этого многочлена равна примерно 6,6, а это означает, что, согласно гипотезе, генерируемые им числа почти в семь раз чаще оказываются простыми, чем случайные числа сопоставимого размера. Этот конкретный многочлен связан с полиномом Эйлера, порождающим простые числа x ²  −  x  + 41, путем замены x на 2 x или, что то же самое, путем ограничения x четными числами. Константа A задается произведением всех простых чисел:

${\displaystyle A=\prod \limits _{p}{\frac {p-\omega (p)}{p-1}}~}$,

где — число нулей квадратичного полинома по модулю p и поэтому принимает одно из значений 0, 1 или 2. Харди и Литтлвуд разбивают произведение на три множителя как ${\displaystyle \omega (p)}$

${\displaystyle A=\varepsilon \prod _{p}{\biggl (}{\frac {p}{p-1}}{\biggr )}\,\prod _{\varpi }{\biggl (}1-{\frac {1}{\varpi -1}}{\Bigl (}{\frac {\Delta }{\varpi }}{\Bigr )}{\biggr )}}$.

Здесь множитель ε, соответствующий простому числу 2, равен 1, если a  +  b нечетно, и 2, если a  +  b четно. Первый индекс произведения p пробегает конечное число нечетных простых чисел, делящих и a , и b . Для этих простых чисел , поскольку p не может делить c . Второй индекс продукта охватывает бесконечное количество нечетных простых чисел, не делящих число . Для этих простых чисел оно равно 1, 2 или 0 в зависимости от того, равен ли дискриминант 0, ненулевому квадрату или неквадратному модулю p . Это объясняется использованием символа Лежандра , . Когда простое число p делит a , но не делит b, имеется один корень по модулю p . Следовательно, такие простые числа не вносят вклада в произведение. ${\displaystyle \omega (p)=0}$ ${\displaystyle \varpi }$ ${\displaystyle \omega (p)}$ ${\displaystyle \left({\frac {\Delta }{\varpi }}\right)}$

Квадратичный полином с A ≈ 11,3, самым высоким известным на данный момент значением, был обнаружен Джейкобсоном и Уильямсом. ^{[9] [10]}

Варианты

В статье Клаубера 1932 года описывается треугольник, в котором строка n содержит числа ( n   − 1) ²  + 1 до n ² . Как и в спирали Улама, квадратичные многочлены порождают числа, лежащие на прямых линиях. Вертикальные линии соответствуют числам вида k ²  −  k  +  M . На рисунке видны вертикальные и диагональные линии с высокой плотностью простых чисел.

Роберт Сакс разработал вариант спирали Улама в 1994 году. В спирали Сакса неотрицательные целые числа отображаются на архимедовой спирали , а не на квадратной спирали, используемой Уламом, и расположены так, что при каждом полном обороте возникает один идеальный квадрат. . (В спирали Улама при каждом вращении возникают два квадрата.) Полином Эйлера, порождающий простые числа, x ²  −  x  + 41, теперь выглядит как одна кривая, поскольку x принимает значения 0, 1, 2, ... Эта кривая асимптотически приближается к горизонтальной линии в левой половине рисунка. (В спирали Улама полином Эйлера образует две диагональные линии: одну в верхней половине рисунка, соответствующую четным значениям x в последовательности, другую в нижней половине рисунка, соответствующую нечетным значениям x в последовательности. .)

Дополнительную структуру можно увидеть, когда составные числа также включены в спираль Улама. Число 1 само по себе имеет только один множитель; каждое простое число имеет два делителя: само себя и 1; составные числа делятся как минимум на три различных множителя. Используя размер точки, представляющей целое число, для обозначения количества факторов и раскрашивая простые числа в красный цвет, а составные числа в синий, можно получить показанную фигуру.

Спирали, следующие за другими мозаиками плоскости, также образуют линии, богатые простыми числами, например шестиугольные спирали.

• 
  Треугольник Клаубера с выделенными простыми числами, порожденными полиномом Эйлера x ²   −   x   + 41.
• 
  Спираль Сакса.
• 
  Спираль Улама размером 150×150, показывающая как простые, так и составные числа.
• 
  Шестиугольная спираль чисел с простыми числами зеленого цвета и более сложными числами более темных оттенков синего.
• 
  Числовая спираль с 7503 простыми числами, видимыми в правильном треугольнике.
• 
  Спираль Улама с 10 миллионами простых чисел.

Смотрите также

• Распознавание образов
• Главный k-кортеж

Рекомендации

1. Гарднер 1964, с. 122.
2. Штейн, Улам и Уэллс 1964, с. 517.
3. Гарднер 1964, с. 124.
4. Даус 1932, с. 373.
5. Моллин 1996, с. 21.
6. Штейн, Улам и Уэллс 1964, с. 520.
7. Гарднер 1971, с. 88.
8. Хартвиг, Дэниел (2013), Путеводитель по документам Мартина Гарднера, Интернет-архив Калифорнии, стр. 117.
9. Джейкобсон-младший, MJ; Уильямс, Х.К. (2003), «Новые квадратичные многочлены с высокой плотностью простых значений» (PDF) , Mathematics of Computation , 72 (241): 499–519, Бибкод : 2003MaCom..72..499J, doi : 10.1090 /S0025-5718-02-01418-7
10. Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer, стр. 8, ISBN 978-0-387-20860-2

Библиография

• Даус, PH (1932), «Мартовское собрание секции Южной Калифорнии», American Mathematical Monthly , Mathematical Association of America, 39 (7): 373–374, doi : 10.1080/00029890.1932.11987331, JSTOR  2300380
• Гарднер, М. (март 1964 г.), «Математические игры: замечательные знания о простых числах», Scientific American , 210 : 120–128, doi : 10.1038/scientificamerican0364-120
• Гарднер, М. (1971), Шестая книга Мартина Гарднера математических отклонений от Scientific American , University of Chicago Press, ISBN 978-0-226-28250-3
• Харди, GH; Литтлвуд, Дж. Э. (1923), «Некоторые проблемы Partitio Numerorum; III: О выражении числа как суммы простых чисел», Acta Mathematica , 44 : 1–70, doi : 10.1007/BF02403921
• Хоффман, Пол (1988), Месть Архимеда: радости и опасности математики , Нью-Йорк: Фосетт Коломбина, ISBN 0-449-00089-3
• Моллин, Р.А. (1996), «Квадратичные многочлены, производящие последовательные, различные простые числа и группы классов комплексных квадратичных полей» (PDF) , Acta Arithmetica , 74 : 17–30, doi : 10.4064/aa-74-1-17-30
• Пегг-младший, Эд (17 июля 2006 г.), «Простые порождающие полиномы», Math Games , Математическая ассоциация Америки , получено 1 января 2019 г.
• Штейн, МЛ; Улам, С.М.; Уэллс, МБ (1964), «Визуальное отображение некоторых свойств распределения простых чисел», American Mathematical Monthly , Mathematical Association of America, 71 (5): 516–520, doi : 10.2307/2312588, JSTOR  2312588
• Штейн, М.; Улам, С.М. (1967), «Наблюдение за распределением простых чисел», American Mathematical Monthly , Mathematical Association of America, 74 (1): 43–44, doi : 10.2307/2314055, JSTOR  2314055