Главная » Статьи » Математики не захотели ссылаться на доказанную анонимами с 4chan теорему о суперперестановках аниме

Математики не захотели ссылаться на доказанную анонимами с 4chan теорему о суперперестановках аниме

 

Английский математик Робин Хьюстон рассказал в у себя в Твиттере, что доказанная анонимами с 4chan теорема до сих пор не нашла признания у математиков. Причина в том, что, хотя решение и находится в свободном доступе (и в его истинности может убедиться каждый), оно не было опубликовано в серьезном журнале. Поэтому, как считает Хьюстон, этот результат и использованный в работе метод просто игнорируются учеными.

Задача, о которой идет речь, является вариацией на тему так называемой последовательности де Брейна типа (n, k). Представим, что у нас есть алфавит из k символов. Мы пишем на доске последовательность, состоящую из букв нашего алфавита. Затем выбираем элемент с некоторым номером и, начиная с него, берем последовательно идущие n символов (считаем что номер достаточно маленький и символов взять можно), то есть слова длины n.

Например, пусть у нас k =2, то есть алфавит состоит из двух букв и n = 2, то есть нас интересуют последовательности длины два. Пусть у нас есть последовательность aabb. Тогда, если брать, начиная с первого элемента, то получим слово aa, со второго — получим слово ab, с третьего — слово bb. Если при такой операции все выбранные нами слова длины n различны, то такая последовательность называется последовательностью де Брейна. Как мы только что проверили, наша последовательность из 4 элементов — последовательность де Брейна.

Среди всех последовательностей де Брейна наибольший интерес для математиков представляют последовательности, которые, во-первых, периодичные (то есть с некоторого номера N начинают повторяться), а, во-вторых, в которых все слова длины n встречаются в цикле ровно один раз. Часто в англоязычной литературе под последовательностями де Брейна понимают именно последовательности с этими двумя условиями. Для k = 2 и n = 3 цикл такой последовательности выглядит так aaababbb. Последовательности де Брейна хорошо изучены и на большинство вопросов, связанных с ними, математики ответили еще в 40-х годах прошлого века.

В 1993 году в работе Даниэля Эшлока и Джанетт Тилотсон возникла задача о суперперестановках. Перестановкой из n элементов называется слово длины n, в котором все буквы попарно различны. Например, перестановок из двух букв a и b всего две — ab и ba. Суперперестановкой авторы работы назвали последовательность де Брейна типа (n, n), в которой все перестановки встречаются ровно по одному разу. Суперперестановка из двух элементов в этом случае имеет вид aba. Собственно, задача из работы (она заинтересовала Эшлока и Тилотсон не просто так, а потому что была связана с физикой) звучала так — какова длина суперперестановки для данного n?

В 2011 году на 4chan появился тред, посвященный аниме «Меланхолия Харухи Судзумии» (涼宮ハルヒ Suzumiya Haruhi). Дело в том, что этот сериал основан на серии книг Нагару Танигавы, причем часть серий снималась в 2006-м, а часть — в 2009-м. Сериал 2006-го года состоял из экранизации первой книги Танигавы, а так же нескольких рассказов из третьего, пятого и шестого томов. Серии выходили на экран в неправильном, с точки зрения хронологии, порядке. Всего в нем было 14 серий. В 2009-м году было снято еще 14 серий, призванных заполнить хронологические дыры первого сериала. Учитывая, что внутри самого сериала встречаются путешествия во времени, ситуация с пониманием сюжета для зрителей сложилась довольно непростая.

Фанаты сериала не прошли мимо этой истории и стали предлагать свои собственные варианты прочтения сериала. Суть заключалась в том, чтобы посмотреть серии в некотором произвольном порядке. Тред 2011 года был посвящен именно такому вопросу: как надо смотреть серии, чтобы по ходу просмотра встретились все возможные последовательности серий (разумеется, без повторений). То есть возникла задача о  суперперестановке «Меланхолии Харухи Судзумии». Один из пользователей треда провел доказательство с помощью теории графов и вычислил нижнюю оценку на длину суперперестановки для произвольного n. 

Сам анонимный пользователь 4chan не довел результат до численного значения (и так было ясно, что число очень большое), но The Verge вычисли, что фанатам Харухи придется посмотреть как минимум  93 884 313 611 серий подряд (и это еще не факт, что найдется суперперестановка из 28 элементов нужной длины — возможно она больше). По словам Хьюстона, который, не смотря на то, что два года назад ушел из науки, следит за этой историей достаточно давно, до сих пор метод анонима не нашел признания у других математиков. Про историю Хьустон подробно рассказывал в своем выступлении на научно-практическом фестивале EMF в 2014 году

В 2017 году ученик московской школы номер 179, Дмитрий Захаров, опубликовал на сервере препринтов arxiv.org новый контрпример к гипотезе Данцера и Грюнбаума, связанной с построением остроугольных множеств. Спустя некоторое время новость об этом попала на форум dxdy, пользователи которого усовершенствовали метод Захарова.

Андрей Коняев