Энциклопедия целочисленных последовательностей
Продолжить ряд (1, 2, 3, 4, 5, ...) очень просто, ведь это ряд натуральных чисел. Многие, увидев ряд (0, 1, 1, 2, 3, 5, 8, 13, ...), вспомнят имя «Фибоначчи». Но скажет ли вам что-то последовательность (1, 196883, 21296876, ...)? Или (1, 744, 196884, ...)? В зоопарке этих математических сущностей - последовательностей целых чисел - есть множество странных созданий. Некоторые из них известны с античности, некоторые появились только что. По просьбе N + 1 физик-теоретик Андрей Заболотский, старший редактор «путеводителя» по этому зоопарку - Энциклопедии целочисленных последовательностей - рассказывает о ее истории, ее экспонатах, о том, как они выглядят и звучат.
Нейросети, перфокарты, кубометры писем
Молодой математик и инженер Нил Джеймс Александр Слоун начал работу над диссертацией по модной, относительно новой тематике - нейронным сетям. На дворе были не 2010-е, как можно было бы подумать, а 1964 год.
Впереди еще десятки лет развития теории построения искусственных нейросетей и необходимого для их нынешнего расцвета развития компьютерной техники, пока же в этой области есть только самые базовые идеи о моделирование нейронов и их соединений, а работа Слоуна имеет еще более абстрактную направленность: моделью нейросети в ней выступает граф-дерево с выделенной «корневой» вершиной: вершины представляют нейроны, которые передают сигнал в корневой нейрон.
Модель нейросети, которую использовал Слоун: граф с выделенной вершиной-нейроном
Помимо прочего, Слоун вычислил среднее количество шагов, которое должен пройти сигнал в сети, просуммированное по всем возможным формам сети из 1, 2, 3... нейронов. Получились несколько начальных членов некоей последовательности чисел: (0, 1, 8, 78, 944, 13800, 237432, ...). Слоун захотел узнать, какие сведения о свойствах этой последовательности есть в научной литературе, и стал штудировать научные журналы и книги, заодно выписывая и другие последовательности целых чисел, попадавшиеся ему. Так он нашел главное дело своей жизни.
Уже через год-два слух о парне, который коллекционирует последовательности, разошелся по сообществу математиков, и Слоун стал получать письма с новыми экземплярами для своей коллекции. Эти письма потом были отсканированы и опубликованы.
Он так и не встретил тогда ту последовательность, с которой все началось, но в 1967 году успешно защитил диссертацию и вскоре поступил на работу в Лаборатории Белла, став успешным исследователем в области теории кодирования (он сотрудничал и дружил, например, с Джоном Конвеем).
Коллекция перекочевала из блокнотов на перфокарты, затем на магнитную пленку и в конечном итоге превратилась в 200-страничный «Справочник целочисленных последовательностей», вышедший в 1973 году. Книга, в которой было 2372 последовательности, стала очень популярна, а ее автора завалили корреспонденцией: в кабинете Слоуна до сих пор упираются в потолок папки с присланными в те годы статьями и письмами.
Нил Слоун в 1987 году
Konrad Jacobs, Mathematisches Forschungsinstitut Oberwolfach
В 1995 году коллекция превратилась в «Энциклопедию целочисленных последовательностей», в которой было уже почти пять с половиной тысяч экземпляров, причем это были уже не только «обычные» бесконечные последовательности, но и конечные, а также и бесконечные прямоугольные и треугольные таблицы чисел, такие как треугольник Паскаля.
Так первоначально пополнялась коллекция Слоуна: фрагмент письма Джона Риордана, 1974 год
OEIS
На следующий год Слоун открыл сайт - Онлайн-энциклопедию целочисленных последовательностей, OEIS. А в 2009 году он занялся превращением OEIS из своего личного проекта в технически и юридически самостоятельную сущность: для управления Онлайн-энциклопедией был создан фонд, а сам сайт превратили в краудсорсинговый проект, подобный Википедии. Слоун занимал пост президента фонда до конца июня 2021 года, когда его сменил Расс Кокс, программист из компании Google, который в 2007 году написал для OEIS поисковую систему - как по членам последовательностей, так и по тексту записей, - а в 2010-м и весь софт, необходимый для ее работы.
Сегодня Онлайн-энциклопедия редактируется пользователями без обязательного непосредственного участия Слоуна (но с премодерацией выбранными Слоуном редакторами-волонтерами) и доступна по адресу oeis.org. В ней уже больше трети миллиона записей. Но что скрывается в этом гигантском скопище чисел, что там могут найти математики (и обычные люди)?
Соединить концы с концами
Ничего особо необычного в увлечении Слоуна не было. Некоторые коллекционируют крышки от пивных бутылок (и находят единомышленников), а вот он - собирает числа. Азарт коллекционера наверняка играет немаловажную роль и для Слоуна, и для многих из тех, кто присылал и присылает ему новые последовательности. Всегда приятно пополнить коллекцию таким изящным экземпляром, как, например, последовательность Морса-Туэ, в которой «прячется» фрактал.
Но в ней можно найти слова и явления из обычной, нематематической реальности. Так, по запросу «bamboo» - «бамбук» - вы найдете последовательность чисел, в разложении которых на простые множители встречаются только 2, 3 и 5, потому что именно таковы циклы цветения разных видов бамбука (самый длинный из известных составляет ровно 120 лет), и этому, как ни удивительно, есть эволюционное объяснение.
Пушечные ядра обычно складывают пирамидкой, и по запросу «pyramid» Энциклопедия находит несколько последовательностей, например, чтобы сложить пирамиду с квадратным основанием высотой 1, 2, 3, 4... слоя, ядер нужно 1, 5, 14, 30, 55... В Энциклопедии есть даже шведская застольная песня, которая полностью состоит из чисел.
Но, конечно, гораздо чаще в энциклопедии ищут не слова, а числа. Каждая последовательность, которая есть в ней, может быть представителем той или иной задачи - к примеру, задача о расстановке n ферзей на доске n × n может быть представлена последовательностью, содержащей количество решений задачи для разных n.
Скажем, математик работает над задачей, в которой какая-то последовательность возникает естественным путем (как число решений в задаче о расстановке ферзей). И в этом случае запись о ней в картотеке становится «точкой входа» в корпус литературы, посвященной не только и не столько самой последовательности, сколько задачам, связанным с ней.
Поэтому если в математической статье рассматривается, к примеру, подсчет танграмов и других полиформ из квадратов и треугольников, то непременно даются ссылки на соответствующие записи из OEIS.
Эти витражи возникают при решении такой задачи: если мы проведем в n-угольнике все диагонали, сколько получится точек, отрезков, областей? Каждая из этих трех задач порождает свою последовательность. Здесь изображения 23-угольника и 27-угольника
Scott R. Shannon, OEIS
«Справочник» Слоуна заслужил популярность благодаря своей организации: в нем было настолько удобно найти последовательность по нескольким первым членам, насколько это вообще возможно в бумажной книге, задолго до эпохи онлайн-поисковиков, после чего можно было проследовать по ссылке на источник и отыскать таким образом информацию о своей задаче.
Особенно полезным бывает такой поиск, когда последовательность связана с на первый взгляд разными, не связанными между собой задачами из разных областей математики (или хотя бы из разных углов комбинаторики и теории чисел - областей, которые чаще всего имеют дело с целочисленными последовательностями). Ведь самые интересные и амбициозные проекты в современной математике (такие как программа Ленглендса) связаны именно с выявлением неожиданных, неочевидных связей.
Последовательности действительно помогают в этом: если вы обратили внимание на то, что в двух упомянутых нами в самом начале этой статьи последовательностях есть два очень близких числа - 196883 и 196884, - то вы вслед за британским математиком Джоном Маккеем сделали первый шаг к комплексу фактов и гипотез под названием monstrous moonshine, иногда называемому по-русски в популярных источниках «гипотезой чудовищного вздора».
Пояснить ее суть мы можем лишь в общих чертах: это связь между объектами, о которых до Маккея никто не мог подумать, что они связаны: монстром - крупнейшей из спорадических простых групп (о них мы немного рассказывали в тексте о Джоне Конвее) - и j-инвариантом - функцией, которую можно охарактеризовать как простейшую из подчиняющихся уравнению j(τ) = j(τ+1) = j(−1/τ) для всех τ. Идеи из monstrous moonshine потом оказались полезны в теоретической физике при обсуждении квантовой гравитации (мы описывали эту кухню в материале про сложный мем).
В том числе поэтому охват энциклопедии последовательностей, собранной Слоуном, весьма широк: четко очертив тип содержания - последовательности целых чисел и только они, - он собирает последовательности и из чистой математики, и из других наук, и из загадок. Иногда говорят, что подойдет любая последовательность, которая заинтересует кого-то, кроме ее автора. Поэтому безоговорочно принимаются последовательности, опубликованные в научной литературе, но не допускаются последовательности с надуманными, неестественными определениями.
Музыка чисел
Числовые последовательности можно превращать в музыку. Для этого каждому целому числу сопоставляют ноты с шагом в один полутон. В интересных последовательностях часто встречаются регулярные структуры, которые и звучат тоже любопытно. Вот несколько примеров.
(файлы в оригинале статьи по ссылке в конце поста)
Непрошеные подсказки
В реальной научной работе в области комбинаторики и теории чисел OEIS обычно помогает установить связь с существующими работами и иногда предположить явную формулу для той или иной последовательности, возникшей в работе.
Иногда целое математическое исследование возникает благодаря энциклопедии. Так, запрос в OEIS послужил отправной точкой для работы о связи песчаных куч и замощений доминошками.
Специалист по комбинаторике Сергей Китаев с коллегами обнаружил связь между интервальными порядками и определенными перестановками именно благодаря OEIS, что тоже выросло в научную статью и затем в целую небольшую область в комбинаторике интервальных порядков. Интервальный порядок - способ взаимного расположения интервалов (отрезков) на прямой, которые могут обозначать, к примеру, временны́е рамки нескольких длящихся событий: к примеру, два события могут пересекаться по времени, и тогда невозможно успеть посетить сразу оба, а могут следовать одно за другим (возможно, с перерывом) - значит, для 2 интервалов существует два возможных интервальных порядка, так что 2-й член соответствующей последовательности равен двум.
Бывает и так, что сама идея математической работы рождается благодаря коллекции последовательностей. Филипп Дюшон (Philippe Duchon) и Ромарик Дювиньо (Romaric Duvignau) из лаборатории компьютерных исследований в Бордо работали над алгоритмом - сейчас они сами не помнят, в чем именно была точная задача этого алгоритма, но для его работы ученым потребовался набор чисел - вероятностей с определенными свойствами. Они вывели формулы, дававшие нужные числа, но не смогли с ходу доказать, что числа всегда будут получаться неотрицательными, как полагается значениям вероятности. Эти числа составляли не последовательность, а треугольную таблицу, и были не целыми, а рациональными.
Но Дюшон был знаком с Энциклопедией целочисленных последовательностей еще с тех пор, когда она представляла собой бумажную книгу, и знал, как искать в ней рациональные числа, то есть дроби с целым числителем и знаменателем: можно, в частности, привести дроби в каждом ряду треугольной таблицы к общему знаменателю, после чего поискать в OEIS последовательность числителей.
Сделав это в надежде узнать что-то полезное для своей задачи, Дюшон и Дювиньо неожиданно обнаружили, что их числа совпадают с так называемыми числами встреч: число встреч dnk - это количество способов переставить n предметов, оставив на месте ровно k из них, к примеру, d31 = 3, потому что если ровно один из трех предметов остается на месте (его мы можем выбрать тремя способами), то два других уже обязательно нужно поменять местами.
В результате разрабатываемый Дюшоном и Дювиньо алгоритм получил новую интерпретацию, и его удалось применить для эффективной генерации случайных перестановок - задачи, которую решает ваш плеер всякий раз, как вы нажимаете кнопку «перемешать».
Наконец, Онлайн-энциклопедия нередко пригождается любителям математических загадок. Так что если вам предложат продолжить последовательность (1, 3, 6, 10, 15, 21, 28, ...) - вы знаете, где искать подсказку.
Андрей Заболотский
Оригинал статьи на N+1