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

Спираль Улама или первичная спираль — это графическое изображение множества простых чисел , придуманное математиком Станиславом Уламом в 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}$

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

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

Гипотеза 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 . Но поскольку A может принимать значения больше или меньше 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 \омега (п)}$

${\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 . Второй индекс произведения пробегает бесконечное число нечетных простых чисел, не делящих a . Для этих простых чисел равен 1, 2 или 0 в зависимости от того, является ли дискриминант 0, ненулевым квадратом или неквадратом по модулю p . Это объясняется использованием символа Лежандра , . Когда простое число p делит a, но не b, то есть один корень по модулю p . Следовательно, такие простые числа не вносят вклад в произведение.${\displaystyle \омега (p)=0}$${\displaystyle \varpi}$${\displaystyle \омега (п)}$${\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-кортеж

На Викискладе есть медиафайлы по теме «Спираль Улама» .