Удивительное поведение рекурсивных последовательностей | Журнал Кванта

В математике простые правила могут открыть для себя сложные и красивые вселенные. Возьмем знаменитую последовательность Фибоначчи, которая определяется следующим образом: она начинается с 1 и 1, и каждое последующее число представляет собой сумму двух предыдущих. Первые несколько цифр:

1, 1, 2, 3, 5, 8, 13, 21, 34…

Да, простой, но этот скромный рецепт порождает закономерность далеко идущего значения, которая, кажется, вплетена в саму ткань мира природы. Это видно по мутовкам раковин наутилусов, костям наших пальцев и расположению листьев на ветвях деревьев. Его математический охват распространяется, среди прочего, на геометрию, алгебру и теорию вероятности. Спустя восемь столетий с тех пор, как эта последовательность была представлена ​​на Западе (индийские математики изучали ее задолго до Фибоначчи), числа продолжают привлекать интерес исследователей, что является свидетельством того, насколько математическая глубина может лежать в основе даже самой элементарной числовой последовательности.

В последовательности Фибоначчи каждый член основан на предшествующих ему членах. Такие рекурсивные последовательности могут демонстрировать широкий спектр поведения, некоторые из которых удивительно противоречат здравому смыслу. Возьмем, к примеру, любопытное семейство последовательностей, впервые описанное в 1980-х годах американским математиком. Майкл Сомос.

Как и последовательность Фибоначчи, последовательность Сомоса начинается с ряда единиц. Сомос-k последовательность начинается с k из них. Каждый новый срок Сомос-k последовательность определяется путем объединения предыдущих членов в пары, умножения каждой пары вместе, сложения пар и последующего деления на член k позиции назад в последовательности.

Последовательности не очень интересны, если k равно 1, 2 или 3 — это просто серия повторяющихся единиц. Но для k = 4, 5, 6 или 7 последовательности обладают странным свойством. Несмотря на то, что здесь много делений, дроби не появляются.

«Обычно у нас не бывает такого рода явлений», — сказал Сомос. «Это обманчиво простое повторение, похожее на Фибоначчи. Но за этой простотой кроется очень многое».

Другие математики продолжают открывать поразительные связи между последовательностями Сомоса и, казалось бы, несвязанными областями математики. В одной статье, опубликованной в июле, они используются для создавать решения до системы дифференциальных уравнений, используемой для моделирования всего: от взаимодействия хищник-жертва до волн, распространяющихся в высокоэнергетической плазме. Они также используются для изучения структуры математических объектов, называемых кластерные алгебры и подключены к эллиптические кривые — которые стали ключом к разгадке Великой теоремы Ферма.

Дженис Малуф, аспирант Университета Иллинойса, опубликовал первое доказательство того, что последовательности Сомос-4 и Сомос-5 являются неотъемлемой частью (то есть все их термины являются целыми числами) в 1992 году. Другие доказательства одного и того же результата разных математиков появилось примерно в одно и то же время вместе с доказательствами того, что последовательности Сомос-6 и Сомос-7 являются целыми.

Это странное свойство последовательностей Сомоса поразило математиков. «Последовательности Сомоса заинтриговали меня, как только я о них узнал», — сказал Джеймс Пропп, профессор математики Массачусетского университета в Лоуэлле. «Тот факт, что Сомос-4–Сомос-7 всегда выдает целые числа, независимо от того, насколько далеко вы заходите, кажется чудом, если смотреть на вещи с наивной точки зрения. Поэтому требовалась другая точка зрения».

Пропп нашел новую перспективу в начале 2000-х годов, когда он и его коллеги обнаружили, что числа в последовательности Сомос-4 на самом деле что-то подсчитывают. Члены последовательности соответствуют структурам, обнаруженным в определенных графах. Для некоторых графов можно соединить вершины (точки) с ребрами (линиями) так, чтобы каждая вершина была соединена ровно с одной другой вершиной — нет непарных вершин и ни одной вершины, соединенной более чем с одним ребром. Термы в последовательности Сомос-4 подсчитывают количество различных идеальных паросочетаний для конкретной последовательности графов.

Это открытие не только открыло новый взгляд на последовательности Сомоса, но и открыло новые способы мышления и анализа преобразований графов. Пропп и его ученики отпраздновали результат, вывесив результат на Футболки.

«Для меня большая часть привлекательности математики заключается в том, что вы приходите в один и тот же пункт назначения разными путями, и кажется, что происходит что-то чудесное или глубокое», — сказал Пропп. «Самое интересное в этих последовательностях то, что существуют различные точки зрения, объясняющие, почему вы получаете целые числа. Там есть скрытые глубины».

История меняется для последовательностей Сомоса с более высокими номерами. Первые 18 членов Сомоса-8 — целые числа, а 19-й член — дробь. Каждая последовательность Сомоса после этого также содержит дробные значения.

Другой тип последовательностей, разработанный немецким математиком Фрицем Гёбелем в 1970-х годах, представляет собой интересный контрапункт последовательностям Сомоса. n-й член последовательности Гёбеля определяется как сумма квадратов всех предыдущих членов плюс 1, разделенная на n. Как и последовательности Сомоса, последовательность Гёбеля предполагает деление, поэтому можно ожидать, что члены не останутся целыми числами. Но какое-то время — по мере того, как последовательность становится огромной — кажется, что так оно и есть.

10-й член последовательности Гёбеля равен примерно 1.5 миллионам, 11-й 267 — примерно миллиарду. 43-й член слишком велик для расчета — он содержит около 178 миллиардов цифр. Но в 1975 году голландский математик Хендрик Ленстра показал, что в отличие от первых 42 членов этот 43-й член не является целым числом.

Последовательности Гебеля можно обобщить, заменив квадраты в сумме кубами, четвертыми степенями или даже более высокими показателями. (Согласно этому соглашению, его исходная последовательность называется последовательностью 2-Гёбеля.) Эти последовательности также демонстрируют удивительную тенденцию начинаться с расширенного диапазона целочисленных членов. В 1988 году Генри Ибстедт показал что первые 89 членов последовательности 3-Гебеля (в которой вместо квадратов используются кубы) являются целыми числами, а 90-е — нет. Последующие исследования других последовательностей Гебеля обнаружили еще более длинные отрезки. Например, последовательность 31-Гёбеля начинается с целых 1,077 членов.

В июле математики Университета Кюсю Ринноске Мацухира Тошики Мацусака и Коки Цучида поделился бумагой показывая это для k-Последовательность Гебеля, независимо от выбора k, первые 19 членов последовательности всегда являются целыми числами. На изучение этого вопроса их вдохновила японская манга под названием Сейсу-тан, что переводится как «Сказка о целых числах». А кадр в комиксе попросил читателей определить минимально возможное значение N_k, точка, в которой k-Последовательность Гебеля перестает производить целочисленные члены. Трое математиков решили ответить на этот вопрос. «Неожиданное сохранение целых чисел в течение столь длительного времени противоречит нашей интуиции», — сказал Мацусака. «Когда происходят явления, противоречащие интуиции, я считаю, что всегда присутствует красота».

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

Подробный взгляд на последовательность N_k раскрывает еще один сюрприз: N_k является простым гораздо чаще, чем можно было бы ожидать, если бы оно было чисто случайным. «С k-Последовательность Гебеля, замечательно не только то, что они целые числа», — сказал Ричард Грин, математик из Университета Колорадо. «Что примечательно, так это то, что простые числа встречаются так часто. Это создает впечатление, что происходит что-то более глубокое».

Хотя новая статья представляет доказательство того, что N_k всегда не меньше 19, неизвестно, всегда ли оно конечно или существует ли k для которого последовательность содержит целые числа бесконечно. «N_k ведет себя загадочно. … Существует фундаментальное желание понять лежащую в его основе закономерность», — сказал Мацусака. «Это может быть похоже на радость, которую я испытывал в детстве, решая головоломки, которые давали учителя. Даже сейчас чувства того времени сохраняются во мне».

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