таксебемысль 27. Про топологический анализ данных.

Как и большинство математиков, которые в теме, я считаю, что топологический анализ данных - это морская свинка. С точки зрения математики он довольно тоскливый, ну нету там особой науки. А с точки зрения нормальной науки о данных - слишком медленный и проигрывает sota алгоритмам. У ТАД, тем не менее, есть три хорошо зарекомендовавших себя области применения: (1) интерпретируемая визуализация данных в естественных науках, (2) качать баблишко с грантодателей, (3) помогает зятягивать студентов в нормальную математику. Если отдавать себе в этом отчет, то в целом всё не так плохо. Меня лично, правда, больше всего смущает отсутствие в ТАД мало-мальски серьезных открытых математических проблем, гипотез и векторов развития.

Ну, вернее, есть одна идея: я считаю, что устойчивые гомологии были бы куда наукообразнее, если бы кто-то определил их для бесконечных пространств с мерой и метрикой (например, компактного риманова многообразия), например, как стохастический предел устойчивых гомологий выборок, доказал бы по нормальному какие-то связи с систолической геометрией. Только тут надо доказать, что стохастический предел существует. Дальше можно было бы оценивать скорости сходимости. Это была бы хорошая работа, которая позволила бы оценивать статистическую значимость ТАДных результатов, без принятого сейчас рукомахательства типа "посмотрите на диаграмму устойчивости, видно же, что это бутылка Клейна, а если не верите, то вот вам теорема устойчивости, она типа про статистику и типа всё обосновывает".

У меня есть личная теория заговора, почему никто в сторону стохастических пределов активно не думает. Потому что скорее всего окажется, что для обоснованных экспериментальных результатов надо сэмплировать гугол точек - а тогда весь ТАД посыпется к чертям как карточный домик. А это топологам, конечно, не хочется, см. п.1 и 2. Люди из естественных наук в первую очередь молятся на статистику, если поймут, что ТАД официально имеет нулевое статистическое обоснование, - то коллег-топологов со скандалом пошлют нахер. И денег не дадут.

А еще одна занятная частная задача - см. вотэтузадачу 79.

таксебемысль 26. Про вещества, зависимости и ориентированные матроиды.

Когда-то давно наткнулся на эту работу. Не могу оценить, насколько она продвигает высокую науку, в особенности высокую науку геохимии. Но, как мне кажется, она содержит классную методическую идею о том, как правильно рассказывать про двойственность Гейла, ориентированные матроиды и всякие подобные вещи. Причем рассказывать-то можно не только студентам, но и школьникам. Мысль, по большому счету, такова:

"Балансировка химического уравнения = вычисление двойственной по Гейлу конфигурации"

На этой фразе те, кто знает, что такое двойственность Гейла, могут остановится и попробовать самостоятельно догадаться, при чем тут химия. Для остальных мой рассказ.

Прошу прощения за кликбейтный заголовок. Вещества будут - но позже. А сейчас немного элементарной геометрии.

Рассмотрим на плоскости 4 точки P1,P2,P3,P4. Будем для простоты рассмотрения считать, что они в общем положении, то есть никакие 3 не лежат на одной прямой. Какие качественно различные варианты расположения точек бывают? Тут есть такая нехитрая альтернатива:

а) Какие-то 3 точки образуют треугольник, а четвертая лежит внутри него.

б) Точки являются вершинами выпуклого 4-угольника. Говоря иначе, точки можно разбить на две пары, такие что отрезки, соответствующие этим парам, пересекаются.

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

Аналогичное можно сформулировать и в трехмерном пространстве и в d-мерном, см. https://ru.wikipedia.org/wiki/Теорема_Радона

Но мы сейчас двинемся в другую сторону. Допустим у нас есть 4 вектора v1,v2,v3,v4 в R^3, пусть в общем положении, и пусть все их координаты неотрицательны. Пустим вдоль этих векторов лучи и зададимся вопросом, каким может быть взаимное расположение этих лучей. Немного подумав, мы поймем, что это та же задача, что и раньше, просто немного переформулированная.

Действительно, поставим в качестве экрана плоскость x+y+z=1. Тогда каждый луч пересечет эту плоскость в точке, и задача сводится к расположению точек на плоскости. Следовательно, есть альтернатива: либо один из лучей находится внутри трехгранного угла, образованного тремя другими, либо лучи разбиваются на пары, и углы, образованные этими парами, пересекаются.

Но как решить эту задачу алгоритмически? Нужен линал. Надо заметить, что у нас 4 вектора в R3, а значит на них есть ровно одно линейное соотношение, т.е. соотношение вида

a1v1+a2v2+a3v3+a4v4=0.

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

И получается такая альтернатива.

а) Один из коэффициентов ai положительный, а три других отрицательны. Или наоборот: один отрицательный, остальные положительные.

б) Два коэффициента положительные, два отрицательные.

Варианта, что все коэффициенты одного знака нет: поскольку координаты векторов vi неотрицательны, суммируя их с только положительными (или только отрицательными) коэффициентами, - ноль не получишь.

Можно осознать, что эта альтернатива в точности соответствует предыдущей альтернативе. Например, если a1>0, но при этом a2,a3,a4<0, то v1 лежит внутри трехгранного угла на лучах v2,v3,v4. А если коэффициенты разбились по парам одного знака, то эти пары как раз соответствуют пересекающимся уголкам.

Это дает нам алгоритм классификации взаимного расположения четырех неотрицательных лучей в R^3. Достаточно перейти от четырех 3-мерных векторов v1,..,v4 к четырем числам a1,..,a4, решив ОСЛУ, и просто посмотреть на знаки этих чисел. Безусловно, все то же самое можно сделать для n+1 неотрицательных лучей в R^n. И доказать теорему Радона так, например.

Написанное - это частный случай (линейного) преобразования двойственности Гейла. Общий случай выглядит так: имея m векторов v1,..,vm в R^n, можно построить другие m векторов w1,..,wm в пространстве размерности m-n, которые как бы кодируют все возможные линейные соотношения на векторы v1,..,vm.

А теория двойственности Гейла - она про то, что взаимное расположение векторов v1,..,vm характеризуется взаимным расположением векторов w1,..,wm относительно начала координат. В частном случае из предыдущих примеров у нас m-n=1, поэтому двойственные векторы - это просто числа a1,..,a{n+1}, и нужно выяснять, как ноль делит их на две группы.

Строго говоря, формализация фразы "взаимное расположение набора векторов" - эта самая технически сложная часть истории. Для формализации используется такая штука как ориентированный матроид. Матроиды даже и сами по себе малопонятны и неприятны, а абстрактные ориентированные матроиды неприятны вдвойне. Мне никогда не удавалось полностью осознать их определение, не то что воспроизвести, поэтому ничего математичного я про них писать не хочу. Итак, ориентированный матроид - это некая абстракция для фразы "взаимное расположение набора векторов".

Есть операция двойственности ориентированных матроидов, которая на комбинаторном уровне кодирует то, что происходит при двойственности Гейла. В частности, с ее помощью удобно комбинаторно классифицировать конфигурации векторов v1,..,vm в R^n при условии, что m-n достаточно мало, например, 1,2,3. В этом случае двойственная конфигурация - это набор векторов в осязаемом маломерном пространстве, где обычно можно нарисовать картинку и что-то доказать методами элементарной геометрии.

Например, таким образом можно получить полную классификацию выпуклых симплициальных n-мерных комбинаторных многогранников, имеющих n+1,n+2, или n+3 вершины. А еще можно придумать 8-мерный комбинаторный многогранник с 12 вершинами, который существует над R, но не существует над Q. За этим и многим другим - прошу в книгу Grunbaum Convex polytopes. Книга Грюнбаума вообще огонь, рекомендую. Более современными считаются Лекции по многогранникам Циглера, но, честно говоря, пытаться заботать двойственность Гейла по Циглеру - мазохизм, у него там примерно такое же рукомахательство, как у меня в заметке, только заумнее.

Ну да ладно, что там с химией.

Открываем таблицу Менделеева, и видим 118 элементов, запишем их по порядку H, He, Li, Be, B, ... Давайте воспринимать их как базис 118-мерного пространства Хим = R^{118}: e1=H, e2=He,... В такой постановке молекула вещества - это неотрицательный целочисленный вектор в Хим. Например, сода NaHCO3, - это вектор 1H+1C+3O+1Na=(1,0,0,0,0,1,0,3,0,0,1,0,0,0,...).

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

Теперь очевидное наблюдение: уравнение химической реакции - это линейное соотношение на соответствующие векторы. Так

Fe + CuSO4 = FeSO4 + Cu

<--->

v1+v2-v3-v4=0,

где v1=1Fe, v2=1Cu+1S+4O, v3=1Fe+1S+4O, v4=1Cu.

Конечно, нам не нужно 118-мерное пространство для работы с этим набором: четверка лежит в R^4, порожденном Cu,Fe,S,O, реально даже в меньшем векторном пространстве: натянутом на Cu, Fe, S+4O.

Поскольку вещества не может быть отрицательное количество, вырисовывается интересная закономерность: знаки при коэффициентах в линейном соотношении разбивают вещества в реакции на две группы - со знаком "+" и со знаком "-". То, что с одной стороны в реакции, и то что с другой стороны.

В итоге пример на двойственность Гейла из начала истории дает этакую грубую классификацию реакций в случае 4 веществ:

а) 3 вещества превратились в одно. Или наоборот. Это геометрическая ситуация, когда одна точка лежит в треугольнике из трех других.

б) 2 вещества превратились в два других вещества. Два отрезка пересекаются.

В какую именно сторону потечет реакция, - линал уже ничего не скажет. Ведь если линейную зависимость умножить на -1, то она по прежнему останется линейной зависимостью. Если я правильно понял написанное в статье по ссылке из начала заметки, то реакция течет в ту сторону, где энергия Гиббса при фиксированных температуре и давлении меньше. Но тут не силен, буду рад, если знающие откомментируют.

Так-то получается, что все потенциально возможные комбинаторные типы химических реакций внутри фиксированной системы задаются ориентированным матроидом, двойственным к матроиду веществ, присутствующих в системе. Это ли не прекрасно!

Там дальше идет довольно любопытная история, про то, что всевозможные потенциальные распределения энергий Гиббса дают всевозможные функционалы Минковского на векторном пространстве, где живет двойственная конфигурация, и возникает вторичный веер конфигурации. С его помощью можно интерпретировать и изучать геохимические фазовые диаграммы. Но это вы уж сами почитайте, если интересно.

таксебемысль 25'. Про двойственность Экмана-Хилтона.

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

Двойственность Экмана-Хилтона не утверждает каких-то изоморфизмов (в отличие от более известных топологических двойственностей, кстати). Это, скорее, набор идей о том, что если написать определение какого-нибудь естественного гомотопического понятия на категорном языке, а потом перевернуть в нем все стрелки, то получится определение другого осмысленного топологического понятия. Потенциальная польза от этого в том, что если доказал некоторое гомотопическое утверждение, то можешь "бесплатно" получить двойственное утверждение про двойственные объекты. Хотя я не знаю исторических примеров, когда бы ровно вот так и работало. Я ниже напишу пример двойственных по Э-Х понятий и утверждений.

То есть это все не про изоморфизм объектов, а про соответствие между утверждениями. Гносеологически по сабжу это, кажется, больше похоже на соответствие Карри-Ховарда, упомянутое тут в комментарии ниже. Только Экман-Хилтон бьет из из гомотопической теории в себя же - вот такая странная симметрия есть в теории. Уместна аналогия с проективной геометрией: теоремы Дезарга и Паппа - это разные теоремы про разные объекты, но зная некий таинственный принцип проективной двойственности, можно считать их одной теоремой.

Примеры двойственных по Экману-Хилтону объектов и утверждений:

1) Когомологии <---> гомотопические группы;

2) Расслоения E-->B со слоем F <---> корасслоения A-->X (они же пары Борсука (X,A)) с кослоем X/A;

3) Точная последовательность когомологий пары

...-->H*(X)-->H*(A)-->H^{*+1}(X,A)-->H^{*+1}(X)-->...

соответствует по Э-Х точной последовательности гомотопических групп расслоения

...-->\pi_*(E)-->\pi_*(B)--\pi_{*-1}(F)-->\pi_{*-1}(E)-->...

То есть на самом деле это (внезапно) одна и та же точная последовательность. Хотя тут дьявол в деталях, конечно: в отличие от теорем Дезарга и Паппа, в гомотопической теории надо аккуратнее всё определять - проще доказывать точность обеих последовательностей независимо, чем ссылаться на волшебную двойственность.

4) Надстройка и петли, о которых ты пишешь - тоже сюда ложатся хорошо, вот пример:

"Надстройка сдвигает когомологии на +1 по градуировке"

<--->

"Петлевание сдвигает гомотопические группы на -1 по градуировке".

5) Пространства Мура (те, у которых когомологии сидят в одной градуировке) <---> пространства Эйленберга-Маклейна (те, у которых гомотопическая группа сидит в единственной градуировке).

6) Клеточный комплекс - это пространство, полученное как последовательность корасслоений, у которых все кослои (т.е. последовательные факторы) - это пространства Мура (букеты сфер, говоря по-простому).

<--->

Двойственный объект - это башня Постникова: последовательность расслоений, у которых каждый слой - это пространство Эйленберга-Маклейна.

7) Легко алгоритмически посчитать когомологии клеточного комплекса (на чем сидит TDA и иже с ним) <---> легко алгоритмически посчитать гомотопические группы башни Постникова (хз, может ли это где-то на практике пригодиться).

А вот гомотопические группы пространств Мура считать - это гроб. Когомологии пространств Эйленберга-Маклейна - тоже непросто. Хотя и проще, чем гомотопические группы сфер - тут есть некая асимметрия, которую я плохо понимаю, честно говоря. Сложности - как бы потому, что в утверждениях комбинируются объекты из разных полюсов теории.

таксебемысль 25. Вопрос про функциональное программирование и шейдеры.

Вот есть разные "парадигмы программирования" - понятие, как будто, довольно условное, - его проще познать из собственного чувственного опыта, чем строго определить. Но речь не про то. Среди оных парадигм самая интригующая - это функциональное программирование. Википедия говорит, что под функциональным программированием понимаются две вещи, вероятно, связанные.

1) Теория. Всякий милый "матан", используемый для формализации: лямбда-исчисление, функции высших порядков, карринг, вот это все. Это не основной вопрос, но все же было бы любопытно узнать: есть ли в этой всей теории яркие и понятные простому человеку теоремы и/или проблемы?

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

Так вот вопрос по второму пункту. Верно ли, что идеальный пример функционального программирования - это шейдеры? Как будто, что в gpu засунешь, то он и пожнёт, включая сам шейдер как таковой. Но я не видел, чтобы шейдерные языки причисляли к функциональным. Таки где подвох?

таксебемысль 24. Про теорию представлений или зачем 3d-моделеры ссылаются на квантовую химию.

Решил тут вкусного написать, но надо как-то это упорядочить. Окей, начнем с относительно общеизвестных вещей, а 3d-графон пойдет потом.

В школьной химии нас учили заполнять электронные орбитали атомов: 1 квадратик, 1+3 квадратика, 1+3+5 квадратиков, 1+3+5+7 квадратиков, мы туда радостно рисуем стрелочки (но не больше двух на квадратик!) и с умным видом говорим про форму орбиталей, представляя себе трехмерные блямбы из учебника.

Сильно позже, - и только при условии выживания на первых курсах, и сохранения здравого рассудка на последних, - мы узнаём, что последовательность 1,4,9,16,... - это размерности собственных подпространств оператора Шрёдингера с центрально симметричным квадратично убывающим потенциалом, 1,3,5,7,... - это размерности неприводимых представлений SO(3), на которые разлагается каждое собственное подпространство, стрелочек в квадратик умещается 2 - потому что SO(3) двулистно накрывается группой SU(2), aka 3-сферой единичных кватернионов. А блямбы - это просто визуализация сферических гармоник, домноженных на какую-то радиальную функцию.

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

В жаргоне 3d-моделлеров и дизайнеров игр есть одно странное слово - "запекание". Попробую объяснить, как я это понимаю для чайников вроде себя самого. При отрисовке 3d-объекта на экране мы для каждого экранного пикселя определяем его цвет, для этого мы определяем какому треугольнику 3d-объекта он соответствует, какие у него барицентрические координаты, какой точке на текстурной развертке эти координаты соответствуют, и берем цвет этой текстурной точки. Если у вас была стереометрия, и была по ней пятерка, то базовую машинерию рендеринга вы поймете без труда.

То, что описано выше, - будет, конечно, полным говнищем: потому что мы не учли тени, блики и прочие очевидные элементы художественной 3d-выразительности. Чтобы добавить красоты, мы добавляем в объемную сцену свет: например, в виде бесконечно удаленного источника, то есть просто вектора. Теперь мы можем сделать наш пиксель ярче, если в точке 3d-объекта, которой он соответствует, нормаль к поверхности почти параллельна вектору света. А если эти два вектора составляют угол меньше 90 градусов, то это теневая сторона объекта, и наш пиксель нужно затемнить.

Отлично. Простое рассмотрение нормали в каждой точке дало нам базовые 3d-эффекты. Нормали можно нехитро рассчитать, тут есть два варианта. Если мы хотим рисовать угловатые многогранники, то мы просто для каждого треугольника считаем его настоящую геометрическую нормаль: векторное произведение его сторон. Если мы хотим работать с гладенькими объектами, то нужно нормали непрерывно интерполировать. Для этого мы: (1) снабжаем каждый треугольник настоящей геометрической нормалью (2) для каждой вершины рассчитываем ее "нормаль" как среднее арифметическое нормалей треугольников, которые содержат вершину, (3) для точки треугольника в качестве нормали берем барицентрическое взвешенное "нормалей" его вершин.

Математически - получается функция, заданная на поверхности 3d-объекта и возвращающая 3-мерный вектор. В первом случае - она разрывная, а во-втором - непрерывная (но не гладкая). Тем не менее, во втором случае получаются вполне сносные эффекты: шар кажется круглым, как и блики на его поверхности, хотя реально сделан из треугольничков.

Сделаем следующий шаг: разрешим функцию нормалей задавать не из геометрических соображений, а вообще как угодно. Мы все равно храним текстуры, так давайте еще в 2d формате хранить распределение нормалей на поверхности объекта. Эта хрень называется картой нормалей. Чем это нам помогает? А тем, что мы можем искусственно сделать на поверхности бугорок, не делая его в действительности. Просто на соответствующей карте нормалей пошевелим значения нормалей в паре пикселей. В плане ресурсов это оптимальнее, чем добавлять 20 новых треугольников. Особенно если бугорков на модели не один, а десять тысяч.

Ну и вот простейшее запекание - это когда моделер делает высокополигональную модель, а потом оптимизирует ее в низкополигональную так, чтобы мелкие особенности зашились в карту нормалей. Сейчас к такому все привыкли, но когда оно впервые появилось, то производило вау-эффект. Я помню, когда мы в общаге после Морровинда установили обливион, - он кряхтел только на минималках, но мы прямо залипали на бликующие каменные стены в подземельях (сейчас тот графон, конечно, воспринимается весьма топорным).

Можно пойти дальше, и научиться делать анизотропные материалы поверхности - так чтобы они рассеивали свет по разному в разные стороны. Или же наоборот, материал обычный, а вот свет дается не одним или двумя источниками, а целой сценой: разные участки окружающей среды (да и самого объекта, почему нет) вносят свой вклад в освещенность. И тут нам уже недостаточно хранить векторное поле нормалей. Теперь в каждой точке у нас сферическая функция! На самом деле три их, по числу цветовых каналов, но это уже мелочи.

Хранить сферическую функцию "попиксельно" (что бы ни означали сферические пиксели) да еще и в каждой точке объекта или сцены - весьма неэкономно. Любой человек, знающий анализ Фурье, устройство jpeg'ов и вот это вот все сразу скажет, что нужно делать: надо разложить функцию по нескольким первым сферическим гармоникам, и хранить только их коэффициенты. Берут, например, на каждый цветовой канал по 1+3+5 гармоник, и раскладывают: вместо хранения сферической функции, храним в каждой точке объекта 27 чисел, красота. Для качественного рендеринга отражений это, конечно, не годится: слишком неточно приближение по 9 гармоникам. Но красивый рассеянный свет на объектах позволяет сделать - для каких-нибудь хромированных труб сойдет.

Моделеру (3d-редактору, ясное дело) опять же придется сделать предварительное запекание светового фона в разных точках. Математически в данном случае это означает, что он вычисляет коэффициенты разложения световой функции по ортогональным сферическим гармоникам, то есть интегралы от какой-то гадости по 2-сфере. Метод Монте-Карло тут в помощь.

Имея предварительно рассчитанные гармонические коэффициенты светового поля, притороченные к координатам поверхности объекта, мы можем в режиме реального времени быстро рисовать красивый свет на объекте. Однако, нам может приспичить повращать наш объект. Это эквивалентно тому, что для фиксированной точки на поверхности обратным преобразованием вращается окружающий световой фон. Нужно иметь способ быстро пересчитывать новые коэффициенты разложения по сферическим гармоникам, не тратя время на повторное запекание.

А что для этого нужно? То самое ружье, которое висит на верху этого поста: нужно понять как SO(3) действует на векторном пространстве сферических гармоник фиксированной степени, то есть фактически на градуированных компонентах фактор-алгебры R[x,y,z]/(x^2+y^2+z^2). У нас получается действие на 1-мерном пространстве констант, на 3-мерном пространстве линейных гармоник, на 5-мерном пространстве квадратичных гармоник и т.д. А учитывая, что повороты в 3d-графике хранятся в формате кватернионов единичной длины, мы реально даже описываем представления вполне себе односвязной группы SU(2), а не SO(3). Хотя, конечно, поскольку у нас всё вещественное, неприводимые представления SU(2) с нечетным старшим весом (и соответственно четной размерности) в нашем списке отсутствуют.

Вот. В целом, я вдохновлялся вот этой статьей. Статья зело старая, но про то как в более современной графике используются сферические гармоники, вы без труда сами нагуглите. Конечно, представления малых весов, которые реально используются, довольно нехитрые: на константах повороты действуют тривиально, на линейных многочленах - канонически, а на квадратных мономах - это посильное упражнение для тех, кто понял предыдущий абзац. В последнем случае, правда, дьявол в деталях. Расчет коэффициентов по Монте-Карло делается для стандартных сферических гармоник (тех, которые через многочлены Лежандра записываются), потому что они образуют ортогональную систему (а функции x^2, y^2, z^2, xy, xz, yz - нет). А значит действие SO(3) нужно описывать именно в конкретном базисе гармоник. Математики таким заниматься не будут... зато это сделали квантовые химики. Упомянутая выше статья как раз ссылается на какие-то подобные работы.

таксебемысль 23. Разрешающие деревья и топология.

Прочитал тут про еще одно красивое приложение эквивариантной топологии в теоретической информатике. Кому не терпится до сути, то вот прошу, а я напишу, каким боком там топология в меру своего понимания. Довольно длинно получилось, но будем надеяться, что все, кого это смущает, от меня отписались.

Пусть есть некоторое конечное множество M. Свойством подмножеств в M будем называть произвольную булеву функцию f из множества подмножеств 2^M множества M в {0,1}. Если f(I)=1 для подмножества I, то говорим, что I обладает свойством f. Понятно, что свойство f можно отождествить с подмножеством K булева куба - совокупностью всех подмножеств, обладающих свойством f.

Назовем свойство f монотонным (вниз), если из условия, что I обладает свойством f следует, что любое подмножество множества I тоже обладает свойством f. По определению, это означает, что соответствующая совокупность K элементов булева куба является симплициальным комплексом. Поэтому монотонные вниз свойства - это то же самое, что симплициальные комплексы.

Теперь рассмотрим такую задачу. У Алисы есть симплициальный комплекс K. Борис загадывает какое-то подмножество I вершин симплициального комплекса, а задача Алисы - угадать, является ли загаданное множество симплексом комплекса K (т.е. обладает ли загаданное подмножество I нужным Алисе монотонным свойством). Для этого Алиса может задавать Борису вопросы вида "верно ли, что i лежит в I?" для какой-то вершины i из множества M. Более формально, у Алисы должно быть разрешающее бинарное дерево, в узлах которого задаются вопросы вида "iϵI?", а на листьях дается ответ "I - симплекс K" или "I - не симплекс K".

Цель Алисы: задать как можно меньше вопросов, чтобы точно определить, принадлежит ли борисово множество ее симплициальному комплексу. Понятно, что всегда можно задать m=|M| вопросов: попросту побитово выяснить, какое подмножество загадал Борис. Однако иногда можно задать мЕньшее число вопросов. Назовем симплициальный комплекс K простым, если Алиса может гарантированно решить задачу принадлежности, задав меньше чем m=|M| вопросов, т.е. представив разрешающее дерево высоты меньше m.

Пример простого комплекса на картинке. В случае объединения двух треугольников по общему ребру {2,3}, Алиса спрашивает Бориса: верно ли, что 1ϵI? Если нет, то Алиса сразу говорит, что IϵK. Если да, то Алиса спрашивает, верно ли, что 4ϵI? Если нет, то Алиса делает вывод, что IϵK. Если да, то получается, что обе вершины 1 и 4 принадлежат I, а значит I не может быть симплексом K. В итоге Алиса обходится всего двумя вопросами вместо четырех возможных.

Какие комплексы просты?

Пусть K - простой, тогда у Алисы есть разрешающее дерево высоты меньше m. Пусть "jϵI?" - первый вопрос в этом дереве. Если получен ответ "да", то соответствующее поддерево будет разрешающим деревом для комплекса link_K{j}, линка вершины j. Если получен ответ "нет", то соответствующее дерево будет разрешающим для комплекса K\{j} - полного подкомплекса на всех вершинах кроме j-й. И высота поддерева в обоих случаях меньше чем m-1, т.е. меньше чем число вершин в соответствующих комплексах. А это значит, что оба комплекса link_K{j} и K\{j} тоже являются простыми. Ну и, наконец, любой полный симплекс является простым комплексом: в этом случае Алиса говорит, что IϵK независимо от того, что за множество загадал Борис, Алисе вообще ни одного вопроса не надо задавать.

Получаем индуктивное определение простого комплекса:

(1) Полный симплекс - простой,

(2) Если прицепить к простому комплексу (то, что называлось K\{j}) конус вдоль простого подкомплекса (т.е. конус над link_K{j}), то получится простой комплекс.

Все простые комплексы получаются такой процедурой. Тут замята под ковер какая-то техническая возня с призрачными вершинами, но она из под ковра вынимается при желании.

А из такого определения легко доказать по индукции, что:

Любой простой комплекс - стягиваемый.

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

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

Абстрактные комплексы - это прекрасно, но давайте рассмотрим пример поконкретнее.

Рассмотрим все простые графы на 6 вершинах, и рассмотрим свойство планарности таких графов. Очевидно, что это свойство - монотонное вниз: если граф планарен, то и любой его подграф планарен. Граф задается множеством своих ребер, а потому в этом примере M состоит из 15 элементов - это все возможные пары из 6 вершин: каждая такая пара может либо быть ребром графа, либо не быть. В итоге свойство планарности кодируется некоторым симплициальным комплексом K(6,0) на 15 вершинах (6 означает, что мы взяли 6 вершин, 0 - это род 2-мерной сферы).

Что мы можем сказать про комплекс K(6,0)? Можно заметить, что его максимальные по включению симплексы соответствуют планарным графам, в которые невозможно добавить дополнительное ребро, не потеряв планарности. Т.е. макс. симплексы - это триангуляции 2-сферы (если бы была нетреугольная грань, в ней можно было бы провести диагональ). С помощью формулы Эйлера легко посчитать, что в триангуляции сферы на 6 вершинах должно быть ровно 12 ребер. Доказали, что комплекс K(6,0) чистый и имеет размерность 12-1=11.

Возьмем какую-нибудь триангуляцию 2-сферы, и выделим в ней одно ребро e. По этому ребру можно сделать флип: соединить два соседних с e треугольника в 4-угольник, и провести в нем другую диагональ. Получится новая триангуляция сферы, у которой все ребра те же самые, кроме одного. Это означает, что для любого максимального симплекса IϵK(6,0) и любой его гиперграни J существует ровно один другой максимальный симплекс с гипергранью J.

А значит K(6,0) является псевдомногообразием.

А значит у K(6,0) есть фундаментальный класс - сумма всех максимальных симплексов.

А значит, у K(6,0) есть нетривиальная 11-мерная гомология над полем GF(2).

А значит K(6,0) не является простым.

А значит невозможно определить, является ли граф на 6 вершинах планарным, не проверив все его ребра.

*Внимательный читатель заметит, что в рассуждении про флип есть лажа: иногда сделать флип нельзя, потому что добавляемое ребро уже есть в триангуляции. Но эта лажа отлаживается, - над этим приятно подумать самостоятельно.

Ну и очевидно, что это рассуждение обобщается. Рассмотрим свойство простого графа на n вершинах быть вложимым в сферу с g ручками. Это свойство кодируется симплициальным комплексом K(n,g). Комплекс имеет m=n(n-1)/2 вершин (вершины комплекса соответствуют возможным ребрам графа). Будем считать, что свойство нетривиально: т.е. что полный граф на n вершинах НЕ вкладывается в сферу с g ручками. Это условие дается конкретным неравенством между g и n, оценкой Юнгермана-Рингеля, но она сейчас не важна. Если комплекс K(n,g) нетривиален, то те же рассуждения, что и выше, показывают, что K(n,g) - псевдомногообразие, а значит не может быть простым: Алиса не может проверить условие вложимости графа в поверхность, не проверив все ребра графа.

Псевдомногообразия K(n,g) возникли с какой-то чисто утилитарной целью. Но фактически получился прелюбопытный объект: что-то вроде пространства всевозможных триангуляций поверхности рода g с n вершинами. Я не верю, что эти комплексы никто не придумал и не изучал, подходя с точки зрения пространств модулей и всякой подобной науки. Какие-нибудь там канонические классы определить и всё такое. Но конкретных ссылок дать увы не могу.

вотэтазадача 71: верно ли, что K(n,g) - ориентируемое псевдомногообразие?

Дальше можно сосредоточиться на свойствах графов. Когда говорим о монотонных свойствах графов на множестве вершин V - имеются в виду симплициальные комплексы K на множестве M={V \choose 2} всех двухэлементных подмножеств в V. Назовем свойство инвариантным, если оно не зависит от нумерации вершин графа. Более формально, пусть S(V) - группа перестановок множества V. Стандартное действие S(V) на V индуцирует действие S(V) на M. Комплекс K инвариантен, если сохраняется действием S(V) на M.

Вот, например, свойства планарности или вложимости в сферу с g ручками - очевидно не зависят от нумерации вершин, поэтому инвариантны. В частности, это означает что на наших псевдомногообразиях K(n,g) имеется действие группы перестановок S_n.

А вот открытая гипотеза Аандераа-Карпа-Розенберга: любое простое инвариантное монотонное свойство графов - тривиально (т.е. либо все графы обладают этим свойством, либо все - не обладают). Иными словами, любое нетривиальное инвариантное монотонное свойство графа можно проверить, лишь перебрав все ребра графа. Весьма удивительно!

Гипотеза доказана Каном, Саксом и Стертевантом (Kahn, Saks, Sturtevant. A topological approach to evasiveness) в случае, когда число n вершин графа - степень простого числа. Идея топологическая. В группе S(V) можно взять подгруппу G аффинных преобразований поля из n элементов. Группа G действует на множестве M двухэлементных подмножеств транзитивно. С другой стороны, G в некотором смысле достаточно маленькая: для нее выполнен аналог теоремы Брауэра. А именно, раз мы предположили, что свойство K простое (т.е. проверяется менее чем за |M| вопросов), то K - стягиваем. Доказывается, что у действия G на геометрической реализации K есть неподвижная точка. Неподвижная точка лежит внутри некоторого симплекса J. Но раз действие транзитивно на множестве всех вершин, то J обязан совпадать со всем множеством M. Т.е. свойство K - это полный симплекс, все графы обладают этим свойством.

Вообще мне кажется довольно занятным посмотреть на разные естественные свойства графов, и понять, почему соответствующие комплексы непростые. Идея про алгоритмическую непростоту планарности взята из Lenstra, Best, Boas, A sharpened version of the Aanderaa-Rosenberg conjecture, только у них ничего про топологию не говорится. Их результат можно топологически сформулировать так: раз мы знаем, что любой простой комплекс монотонно сдавливается в точку, значит у него есть максимальный симплекс со свободной гипергранью (это тот симплекс, который мы вдавим первым шагом). А значит, если свободных симплексов нет, то комплекс не простой. Этого соображения достаточно, чтобы доказать непростоту комплекса K(n,g), используя трюк с флипами ребер в графе. Фундаментальный цикл - штука прикольная, но она там не особо нужна.

И этого же соображения достаточно, чтобы доказать сложность свойства ацикличности графа. Это свойство довольно любопытное: соответствующий симплициальный комплекс Aс(n) - это комплекс независимых множеств графического матроида полного графа. Известно, что независимые комплексы матроидов гомотопны букетам сфер одной размерности.

В статье Ленстры-Беста-Боаса также оставлено в виде упражнения - доказать, что свойство несвязности графа является сложным. Из их теоремы мне, впрочем, это как-то увидеть не удалось: в соответствующем комплексе DC(n) вполне себе бывают сдавливаемые симплексы. Однако тут можно заметить, что DC(n) гомотопен геометрической реализации решетки разбиений множества [n] (из которой выкинули наименьшее и наибольшее разбиение). Из матроидной теории опять же следует, что геометрическая решетка гомотопна букету сфер. Количество сфер равно значению функции Мебиуса mu(0,1) чума. Конкретно в нашем случае - имеем (n-1)! сфер.

Короче, всякие свойства графов весьма забавны с топологической точки зрения.

таксебемысль 23. Про алгоритмы и гомологии.

Впечатлился когда-то вот этим докладом Бьорнера, решил про него написать.

Есть любопытная деятельность на стыке комбинаторной топологии и теории сложности алгоритмов. На мой взгляд, к ней можно естественно подойти как-то так.

Начнем с баяна: сортировки массива. Пусть дан массив длины n из вещественных чисел. Будем считать пока для простоты, что все элементы массива попарно различны. Надо массив отсортировать. Википедия нам говорит, что наиболее эффективные алгоритмы сортируют массив за время O(n*log n). Почему нельзя быстрее?

Объяснение: сортировка нам в качестве ответа выдает перестановку множества из n элементов. Всего количество возможных перестановок, т.е. потенциальных вариантов ответа на задачу, равно n!. Если мы для решения задали x вопросов типа "Да-Нет" (например, вопросов на сравнение элементов массива), то количество итоговых комбинаций ответов, которые мы сможем получить, равно 2^x. Если мы хотим покрыть все потенциальные возможности ответов, то должно выполняться 2^x>n!, т.е. x>log(n!)=n*log n. Просто и со вкусом.

Теперь рассмотрим такую задачу: дан массив длины n, надо понять, есть ли в нем повторы, т.е. равные элементы. Задача, очевидно, решается за O(n*log n): отсортируем массив, а потом проверим все последовательные пары. Но почему конкретно эту задачу нельзя решить быстрее? Предыдущее рассуждение не применимо: у нас в качестве ответа на задачу получается либо Да (есть повторы), либо Нет (нет повторов). Надо уточнить, что подразумевается под сложностью.

Если под сложностью понимать количество произвольных "Да-Нет"-вопросов, требуемых для ответа на поставленный вопрос, то сложность будет равна 1. Действительно, можно обойтись всего одним вопросом: верно ли, что произведение П разностей (a[i]-a[j]) по всем парам индексов i<j равно 0? Иными словами, с математической точки зрения мы можем просто спросить: правда ли, что n-мерный вектор (a[1],...,a[n]) лежит в конфигурации диагональных гиперплоскостей X(n), т.е. в объединении гиперплоскостей вида x_i=x_j? Это, конечно, совершенно бессмысленная трактовка задачи: на практике мы кучу времени потратим на вычисление "дискриминанта" П, там ведь порядка n^2 умножений.

Поэтому давайте ограничимся вопросами следующего вида. Разрешим (мгновенно) вычислять любую линейную функцию от элементов массива, и сравнивать результат ее вычисления с нулем. Таким образом, мы строим тернарное дерево решений, у которого в каждом узле происходит сравнение некоторой линейной функции с нулем: ответами могут быть <,=,>. Сложностью алгоритма будем называть высоту такого дерева, т.е. максимальное количество произведенных сравнений.

Обобщим задачу: пусть M - подмножество в R^n, и требуется решить задачу принадлежности массива (a[1],...,a[n]) подмножеству M с помощью описанного выше дерева решений с линейными вопросами. Очевидно, что задача в принципе разрешима только если множество M является объединением конечного числа полиэдров (было бы странно пытаться выяснить принадлежность точки параболе, задавая лишь линейные вопросы).

Так вот Добкин-Липтон'75 доказали, что сложность задачи принадлежности массива множеству M ограничена снизу числом log c(M), логарифмом числа компонент связности множества. Возвращаясь к задаче о повторах в массиве: нам нужно выяснить, принадлежит ли массив (a[1],...,a[n]) диагональной конфигурации X(n). Или, эквивалентно, принадлежит ли массив дополнению R^n\X(n)? Но дополнение до диагональной конфигурации - это объединение открытых камер Вейля типа А - их столько же, сколько и перестановок, то есть n!. Поэтому в задаче о повторах в массиве опять же получаем оценку снизу для сложности log(n!)=n*log(n).

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

Однако Бьорнер-Ловаш'92-94 доказали, что число компонент связности из оценки Добкина-Липтона можно заменить на модуль эйлеровой характеристики. А потом еще усилили: можно вообще взять сумму всех чисел Бетти.

Это можно применить к задаче наличия k-кратных повторов в массиве. В этой задаче нужно определить принадлежность массива дополнению до конфигурации X(n,k) плоскостей вида x_{i_1}=...=x_{i_k}, где i_1<...<i_k пробегает по всем возможным k-подмножествам индексов. При k>2 тут опять же Добкин-Липтон не работают: плоскости имеют коразмерность, бОльшую единицы, а значит их дополнение - связно. Естественно оценивать через числа Бетти.

Числа Бетти дополнения до произвольной конфигурации плоскостей можно вычислить по формуле Горески-Макферсона, это отдельная история. Бьорнер-Ловаш посчитали числа Бетти дополнения до X(n,k) всякими страшными комбинаторными ухищрениями (лексикографические шеллинги). И в итоге для задачи о k-кратных повторах в массиве опять же получили оценку O(n*log n), т.е. асимптотически ничего лучше, чем отсортировать массив и проверить все окошки из k подряд идущих чисел, - сделать нельзя. Гомологии дополнения до конфигурации мешают!

А теперь план, как доказать неравенство классов P и NP - из слайдов Бьорнера. Учитывая давность доклада, и того, что задача тысячелетия по прежнему открыта, надо полагать, дело не выгорело. Хотя, возможно, просто никто это до ума не довел.

Забудем про вещественные числа, будем работать с булями. Рассмотрим задачу о принадлежности булевой строчки некоторому подмножеству M булева куба {0,1}^n. Собственно, произвольные задачи в теории сложности как-то так и формализуются, как будто. Подмножество M можно рассматривать как алгебраическое многообразие над конечным полем F_2. У этого многообразия (или у его дополнения) можно определить этальные когомологии с коэффициентами в l-адических числах, для нечетных l. Можно определить этальные числа Бетти (на этальных когомологиях еще и автоморфизм Фробениуса действует, и там всякие дзета-функции возникают, но эти ужасы, авось, и не пригодятся). План Бьорнера:

(1) Доказать, что сложность выполнения алгоритма ограничена чем-то зависящим от суммы этальных чисел Бетти. Логарифмом, например, как в случае вещественных чисел и сингулярных гомологий.

(2) Взять какую-нибудь NP-полную задачу, формализовать в виде алгебраического многообразия M над F_2.

(3) Посчитать этальные когомологии M, убедиться, что числа Бетти дофига какие большие.

(4) Значит задача быстро не решается. Profit!

таксебемысль 22. Первоапрельское про квантовых пчёл.

Контакт предлагает поделиться чем-нибудь радостным и веселым (в связи с началом локдауна), посему настало время математической истории столь же прекрасной сколь и упоротой. Впрочем, надеюсь, что отдельные ее части окажутся познавательными в разных смыслах.

Про квантовых пчел: пчелиные танцы, многообразие флагов, квантовая хромодинамика.

Я уже писал тут раньше, что умение пчел конструировать правильную шестиугольную структуру сот, - это факт достойный восхищения. Однако есть в поведении пчел и еще более удивительный факт: пчелиные танцы. Я тут вкратце перескажу о чем речь, но вообще вот вам теория, а вот демонстрация. Не очень понятно, можно ли считать пчелиные танцы полноценным языком с точки зрения философии (с синтаксисом, семантикой и всем таким). Однако пчелы вполне способны передавать некоторую геометрическую информацию с помощью танца.

Итак, пчела-фуражир нашла нектар в точке с полярными координатами (d,alpha), где начало координат - это улей, а угол отмеряется относительно направления на солнце по часовой стрелке. Тогда пчела пытается сообщить эту информацию другим пчелам, производя определенные телодвижения. Она садится на вертикальную стенку улья и движется по восьмерке, вернее по чему-то вроде буквы тета Θ. По перекладине буквы Θ пчела всегда проходит в одном направлении, чередуя левые и правые повороты. Проходя по перекладине, пчела вибрирует жопой, - чтобы соплеменникам было понятнее, где в ее танце перекладина, а где вспомогательные круги.

Координаты (d,alpha) источника пищи кодируются следующим образом: alpha - это угол наклона перекладины Θ относительно вертикали. А d прямо пропорционально длине перекладины.

За описанную выше расшифровку танца пчел (среди прочего) Карл фон Фриш получил Нобелевскую премию в 1973 году. Тема, судя по всему, оказалась богатая: там есть много всяких тонкостей, которые можно погуглить. Вроде как, в танце кодируются и другие параметры, например количество и качество пищи в локации как-то коррелирует с частотой и амплитудой жопной вибрации. Ну и всякое такое. Правда, судя по википедии, последние исследования говорят, что коммуникационная эффективность пчелиного танца не такая уж высокая. Нет такого, что пчелы увидели танец своего сородича и автоматически ломанули в рекомендованном направлении. Но с другой стороны, многие ли москвичи самоизолировались три недели назад, когда отдельные знающие люди про это настоятельно танцевали?

Еще пара удивительных фактов. Чтобы отмерить угол alpha, пчела должна знать, где находится солнце. У нее есть для этого всякие хитрые органы, в частности, она чувствует поляризацию солнечного света. Поэтому солнце она может найти даже в пасмурную погоду. Но круче другое. После того, как пчела нашла источник пищи, она может танцевать достаточно долго, и положение солнца на небе успевает смениться. Так вот, пчела подстраивает свой танец под актуальное положение солнца, меняя угол наклона восьмерки. То есть, если ее коллега решит воспользоваться информацией только через 4 часа, она, то есть коллега, все равно сможет найти источник пищи. Это вообще фантастика какая-то. Вот вы попробуйте рассчитать изменение азимута солнца через 4 часа (не имея смартфона или хотя бы астролябии). А пчела как-то умеет. Хрен пойми как именно, учитывая что у нее в мозгу порядка миллиона нейронов - не астрономически много, прямо скажем.

И напоследок еще один факт, который правда, согласно википедии, в последнее время оспорили. Если расстояние d до источника пищи слишком маленькое, его изображать, тряся жопой, во время прохождения по перекладине буквы Θ, становится несподручно. Поэтому форма танца при маленьких d перестраивается. Траектория становится похожей на букву V, где каждая черточка - это вырожденная окружность. Ну и в ней как-то тоже координаты закодированы.

А теперь, собственно, сказ про квантовых пчел. Интернет сохранил вот эту популярную статью. Предыстория была такая.

Есть некая американская математик Барбара Шипмэн. Где-то в конце 90-х она защитила Ph.D. по математике, посвященную всяческим потокам Тоды на многообразиях флагов (мат.часть я приложил в виде pdf-ки). По тому, что я смог о ней найти в интернете, - вполне активный и адекватный математик, сейчас она занимается, судя по всему, примерно той же темой. Математические публикации у нее выходят не очень часто, но они вполне содержательные и претензий не вызывают.

Однако в конце 90-х эта самая Барбара умудрилась опубликовать одну статью про многообразие флагов в журнале с броским названием American Bee Journal. Сам факт доставляет, чего уж. Такой журнал, разумеется, никакими сай-хабами не ищется, и даже абстракта статьи ни в каких системах я найти не смог. На мою просьбу поделиться статьей автор не отреагировала. Поэтому содержание статьи - лишь моя догадка, отчасти основанная на популярном тексте в Discover (по ссылке выше).

Итак, вначале описание для тех кто знает, что такое многообразие флагов. Рассмотрим многообразие F_3 полных комплексных флагов в пространстве C^3. Это алгебраическое многообразие комплексной размерности 3, то есть вещественной размерности 6. Оно проективное, значит симплектическое. На нем имеется гамильтоново эффективное действие 2-мерного тора (индуцированное стандартным действием тора на C^3). Гамильтонианы векторных полей, порожденных этим действием, задают отображение моментов из F_3 на вещественную плоскость R^2. Образ отображения моментов - это выпуклый многогранник, в нашем случае, это попросту шестиугольник P_6. Итак, есть проекция mu: F^3 —> P_6 из 6-мерного многообразия комплексных флагов на шестиугольник.

На многообразии флагов, вернее на многообразии матриц с фиксированным спектром, можно задать динамическую систему, так называемый поток полной симметричной цепочки Тоды. Еще там есть поток замкнутой цепочки Тоды. Так вот, по-видимому, статья Шипмэн в пчелином журнале была про то, что если траектории потока Тоды (то ли открытого, то ли замкнутого) спроецировать на шестиугольник отображением моментов mu, то получатся картинки, дофига напоминающие пчелиные танцы. Причем в зависимости от параметров динамической системы могут получатся как Θ-образные танцы (waggle dance) так и V-образные танцы (round dance).

Для тех, кто не знает слов выше, но знает, что такое дифференциальное уравнение и собственные значения матрицы, написан текст во вложении. Там объясняется, что такое отображение моментов, поток Тоды и вот это вот все.

Увидеть пчелиные танцы в потоках Тоды я не смог. Если бы речь шла про поток открытой цепочки Тоды, то там все траектории стремятся к диагональным матрицам. А значит ни периодичности, ни квазипериодичности у потока нет, и моделировать периодический танец пчелы таким потоком как-то сомнительно. На картинках прикинуто, как могут выглядеть траектории открытой цепочки Тоды. При большом желании восьмерку можно увидеть, правда она составлена из двух различных траекторий. Если поменять симплектическую форму на многообразии флагов (т.е. изменить собственные значения всех рассматриваемых матриц), то восьмерка вытянется и как будто превратится в букву V, что вроде как соответствует переходу от Θ-образного танца к V-образному. Но имеется во всем этом натяжка.

Меня однако, заинтересовало, как будет выглядеть проекция траектории потока замкнутой цепочки Тоды на 6-угольник. Эта динамическая система по сути моделирует движение трех взаимодействующих частиц на окружности. Наверное, точную траекторию можно было бы и явно построить с помощью несложного скрипта. Но у меня руки в смысле моделирования из неправильного места растут, поэтому я ограничился примерным эскизом (зелененькая). Получается что-то вроде трехлистного клевера. На пчелиные танцы вообще не похоже.

Но история-то про пчел на многообразии флагов не заканчивается.

У этой Барбары Шипмэн, как выяснилось, отец - то ли физик, то ли пчеловод. И он, по-видимому, как и многие физики, фанател от нефальсифицируемой идеи Пенроуза о квантовой природе сознания. Ну и, судя по всему, убежден, что она (квантовая природа сознания то есть) есть в пчелах. Даже какие-то статьи про это писал.

А тут такая благодатная тема: пчелиные танцы моделируются потоками на многообразии флагов! В общем, примерно понятно, в каком направлении дальше всё понеслось. Ну не может же пчела обрабатывать своим примитивным мозгом диффуры на 6-мерном многообразии! Наверное, есть у ней внутри какая-нибудь квантовая хрень, которая сводит все эти танцы к минимизации функционала действия.

Многообразие флагов в C^3 - это не то, чтобы какая-то суперважная вещь в квантовой механике. Я бы предположил, что единственный способ ее привязать к чему-то общезначимому таков. Многообразие флагов - это фактор группы SU(3) по максимальному тору T^2. А группа SU(3) - это калибровочная группа в квантовой хромодинамике (это такая наука, которая кварки изучает). Таким образом, F_3 параметризует способы выбора хроматического базиса с точностью до "сдвига фаз", что бы это ни значило.

Раз уж мы приняли тезис о квантовой природе пчелиных мозгов, то придется поверить и в то, что пчела танцует опредленным образом, потому что у нее в голове отдельные кварки чешутся. Вот даже не отдельные протончики и электрончики, а кварки. Кварки, Карл! Хоть открывай фабрику по добыче кварков из пчелиных мозгов, - на коллайдерах можно сэкономить.

Бред какой-то. Но, надеюсь, что это было интересно. Если хотите занятие на остаток 1-го апреля - погуглите разных фриков, которые пытаются эту тему с квантовыми пчелами дальше двигать. Только не давайте их кваркам съесть ваш мозг.

таксебемысль 21'. Пчёлки, мышки и кристаллография.

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

1) Есть статья https://elifesciences.org/articles/05979 , за ссылку спасибо Косте Сорокину. Там люди теоретизируют, что для мозга оптимальна - с некоторой точки зрения, вроде максимизации хранимой информации, - решетка, соответствующая максимально плотной упаковке шаров. И это во всех размерностях работает. Тут можно было бы подискутировать, что если бы существо было 8-мерным, то решетка была бы E_8 (оптимальность решетки E_8 в плане упаковки - результат 2016 года, гугл в помощь, ссылка на ссылки http://mathworld.wolfram.com/HyperspherePacking.html). Но к нейронам это притягивается с натяжкой: если бы мозги млекопитающих были заточены на обработку чего-то 8-мерного, думаю, наблюдались бы более высокие результаты по ЕГЭшной стереометрии.

Возвращаясь в реальный трехмерный мир, мы имеем кубическую гранецентрированную решетку. Это то, что возникает, если оптимальным образом паковать апельсины. Например, уложить первый слой апельсинов в узлы квадратной решетки, следующий - в выемки между апельсинами первого слоя и т.д. Или первый слой - в узлы правильной треугольной решетки, а последующие - в выемки от предыдущих. На первый взгляд эти способы разные, но на самом деле отличаются лишь поворотом в пространстве (хорошее упражнение на геометрическое воображение). Так что формально решетка там одна и та же, хотя и ориентирована по разному. Точечная кристаллографическая группа у нее - группа октаэдра, из кристаллографических групп самая большая и интересная.

И вот, вроде как, пространственная решетка, где активируются нейроны решетки, должна быть кубической гранецентрированной, согласно упомянутой статье. Они там пишут в абстракте, что "This prediction could be tested experimentally in flying bats, arboreal monkeys, or marine mammals". Склонен перевести это как "мы экспериментально не проверяли, но кто-нибудь, проверьте, пожалуйста". Проверил ли кто-нибудь - я не знаю. У меня сложилось скептическое впечатление, что соответствующие эксперименты, особенно с летучими мышками, дофига дорогие и непростые, и, раз нет возможности получить новый сенсационный результат, их проводить не будут. Надеюсь, впрочем, что это неправда.

Я хотел вкратце написать отступление про аналогию вопросов о клетках решетки и вопроса о форме пчелиных сот. Но потом Остапа понесло, текст разросся, и я решил, что про пчёлок будет отдельным постом.

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

таксебемысль 21. Пессимистичная про пчёлок.

Вернее про общие вопросы, почему что-то в природе устроено так, а не иначе. У меня иногда мелькает мысль, что некоторые подобные вопросы, несмотря на то, что у всех на слуху, должного ответа не получают. Даже когда ответ, вроде как, всем понятен. Потому что математик дает ответ в духе "этот объект реализуется в дикой природе, потому что именно такой объект оптимизирует чего-нибудь". А биолог такой думает "окей, мы наблюдаем это на практике, а математик умеет как-то явление объяснять, вопрос закрыт". Но оно ведь по всякому бывает: биология все же не физика, чтобы все сводить к минимизации функционала действия.

Вот, например, какого чёрта пчелиные соты представляют из себя идеально ровное замощение плоскости шестиугольниками? Математик может сказать, например, "гексагональное замощение возникает из оптимальной упаковки кругов на плоскости". Но даже если предположить, что пчела цилиндрична как гренландский кит, воспетый Арнольдом, трудно поверить, что пчелы строят соты, пытаясь коллективно и оптимально запихнуться в заданный кусок плоскости. Поэтому это так себе объяснение. Еще математик может сказать "стенки правильного гексагонального разбиения плоскости представляют из себя минимальную сеть. Пчела просто минимизурует количество воска для строительства". Это уже больше похоже на вразумительное объяснение. А особенно если вспомнить, что пчелиные соты на самом деле представляют из себя трехмерную структуру: у них две стороны, между ними внутренняя стенка. Совокупность всех перегородок там образует что-то вроде минимальной поверхности, "мыльной пленки". И все равно остаются вопросы.

Во-первых, минимальных сетей бывает много - собственно, любое разбиение плоскости на 6-угольники с углами 120 градусов - это минимальная сеть (можно ли любую такую сеть продолжить в 3D до мыльной пленки - скажу честно, не знаю). Почему именно правильные 6-угольники?

Во-вторых, откуда чёртова пчела знает, что для оптимальности затрачиваемого материала надо строить углы в 120 градусов? Она что, про оптимальность точки Ферма-Торричелли на маткружке ботала? Есть, конечно, универсальный ответ, что так оно эволюционно сложилось. Но все же (а) удивительно, что ей хватает мозгов для столь точных построений; (б) по прежнему не ясно, какой именно процесс в ее голове заставляет ее делать так а не иначе, да и собственно, как железо для этого процесса передается генетически. Дарвина мы все любим, но всё же, между естественным отбором и гексагональным замощением, на мой взгляд, лежит некоторая пропасть. Вот как так случилось, что неправильные пчёлы, которые делают неправильные соты, повымирали? И какой именно генетический "признак" выделяет правильных пчел?

В случае с формой пчелиных сот можно удовлетвориться таким комбинированным объяснением, на генетику не особо завязанным. Пчела делает соту круглой. Таки потому что пчела цилиндрична, она крутится и возводит вокруг себя стенки. А поскольку в улье стоит немного повышенная температура, восковые стенки чуть-чуть подтаивают. И принимают форму минимальной поверхности за счет поверхностного натяжения. Т.е. пчеле не нужно быть особо сообразительной, за нее отчасти работает физика. Случайно наткнулся на статью в Популярной механике с таким объяснением. Но тут опять возникают вопросы.

Во-первых, толпа пчел начинает строить свои цилиндрические соты в разных местах. Почему оно всё у них правильно стыкуется? С одной пчелой такой проблемы нет, она просто заполняет плоскость кружочками, надстраивая их один на другой, как таджик тротуарную плитку. Но как множество пчел согласует процесс? Если два таджика начинают класть плитку с разных концов улицы, то, как бы идеально они это не делали, их встреча, скорее всего, будет омрачена некой ожидаемой проблемой.

Во-вторых, объяснение через поверхностное натяжение восковых стенок критикуется (источники луркаются по аглицкой википедии https://en.wikipedia.org/wiki/Honeycomb). 1) Температура плавления воска все-таки существенно выше, чем температура улья. Иначе бы края стенок, очевидно, оплавлялись. 2) Углы на внутренних стыках стенок не идеальные. Т.е. это все-таки не мыльная пленка. А будь там задействовано поверхностное натяжение, всё должно быть идеально. 3) И наконец - бумажные осы. Они, собственно, делают почти то же самое, что и пчелы, но только не из воска, а из волокон целлюлозы. И у них тоже получаются довольно ровненькие шестиугольники, хотя бумага, ясное дело, растопиться ну никак не может. На мой взгляд, осиные гнезда вполне могут оспорить у пчелиных сот статус самой сложноорганизованной структуры, построенной насекомыми. Фактически бумажные осы делают такие миниатюрные кусудамы, хотя по механике это больше похоже на папье-маше. Но я все равно чувствую с ними некую оригамистскую близость.

А вывод у всего этого такой. Хотя вопрос о сотах весьма затаскан, к общепринятому ответу - "экономия стройматериала, сложилось эволюционно" - зануда может прикопаться по всем пунктам. Но согласитесь, трудно поверить, что вот некто освоит грант, произведет полномасштабное исследование и напишет статью "Why honeycomb is regular hexagonal?". В Nature такое не опубликуют. Потому что и факт общеизвестный и объяснение в целом тоже. Ну, положа руку на сердце, вряд ли предложение "экономия стройматериала, сложилось эволюционно" окажется совсем нерелевантным. Скорее всего, полное объяснение будет представлять собой некоторую надстройку над этим предложением.

Кажется, что все, что можно было пронаблюдать в поведении пчёл, просто наблюдая за пчёлами, уже было пронаблюдено за столько-то лет. Углы между восковыми стенками и температуры в ульях просчитаны до долей градуса. Получить принципиально новые результаты про соты можно только высокотехнологичными экспериментами: отследить, какие феромоны они используют для "межличностного" взаимодействия, залезть пчеле в мозг, померить нейроны.

Пчела не млекопитающее, но, может быть, и у ней внутре ̶н̶е̶о̶н̶к̶а̶ тоже есть нейрон решетки? И она понимает, что соту надо строить только там, где этот нейрон свербит? На практике это фиг проверишь, потому что денег на эксперимент надо много. А денег жалко. Звучит задача некруто (чай не коллайдер), и, в общем-то, пользы от ответа на вопрос не предвидится.

таксебемысль 20. Про топологические матроиды?

Прелюдия описана в вотэтойзадаче 68. А вот вопрос.

Ну а мысль такова: можно ли получить теорему Бьорнера и теорему Васильева как частные случаи какой-нибудь общей теоремы про топологические матроиды? С наскоку мне придумать не удалось.

таксебемысль 19. Про порядок m и n.

Тут вообще был соц.опрос, ну да ладно.

Допустим есть два натуральных числа, из которых одно очевидно больше чем другое. Какое вы обозначите за n, а какое за m? 

С этим связана такая история. У нас как-то так сложилось, что n обозначает размерность многогранника, а m - число его гиперграней, то есть очевидно, что m>n. У меня эта конвенция, возможно, в силу привычки, ни вопросов ни отторжения не вызывает. На одном из семинаров кто-то в шутку спросил докладчика, почему m>n, ведь в алфавите буква m идет перед буквой n. Виктор Матвеевич не растерялся и мгновенно ответил, что в типографском деле принят не алфавитный порядок, а такой, в котором буквы упорядочены по сложности написания.

Я не знаю, правда ли это про типографские порядки. Но мне кажется очевидным, что m>n, ровно потому что буква "m" выглядит больше чем буква "n". Это примерно про то же самое. Однако, догадываюсь, что кому-то проще наоборот: восприять порядок букв в алфавите, нежели их размер. Интересно стало проверить, вот.

По результатам можно будет судить, кто тут геометр, и лучше воспринимает пространство, а кто алгебраист, и лучше ощущает порядок (т.е. время, если по Канту).

таксебемысль 18. Узлы, триангуляции Делоне, эллиптические кривые и теорема Ботта.

Об описанных окружностях, узлах-трилистниках, эллиптических кривых и пространстве модулей (о теореме Ботта).

Я когда-то думал эту мысль, а потом оказалось, что она уже была подумана весьма геометрично тут.

Теорема Ботта утверждает, что

exp_3(S^1)=S^3

пространство всех не-более-чем-3-х-элементных подмножеств на окружности гомеоморфно трехмерной сфере. Иными словами конфигурационное пространство троек точек на окружности, в котором точки могут слипаться (без образования кратности), есть трехмерная сфера.

Это не очевидно, но и не то чтобы очень сложно, если это доказывать элементарно-топологически. Факт, однако, оброс дополнительными подробностями.

Во-первых, если вращать тройку точек на окружности как единое целое, то получим замкнутую кривую в нашем конфигурационном пространстве S^3. Эта кривая - узел-трилистник, за исключением конфигурации из двух диметрально противоположных точек, и конфигурации из трех точек, лежащих в вершинах правильного треугольника. В этих исключительных случаях соответствующие кривые в S^3 незаузлены. Таким образом, S^3 оказывается расслоена на двупараметрическое семейство трилистников, вырождающееся в двух местах. (Понимая, что трилистник - это торический узел, и зная, как устроено расслоение Хопфа, можно догадаться, как топологически устроено это слоение 3-сферы на трилистники)

Во-вторых, интересно посмотреть на пространство, параметризующее это семейство трилистников. Можно рассматривать все эти кривые как орбиты действия S^1 на S^3, которое прокручивает тройку точек как единое целое. Пространство орбит этого действия - это двумерная сфера с двумя коническими особенностями. Особенности - это как раз исключительные конфигурации: пары противоположных точек дают особенность с группой изотропии Z/2 (поскольку каждая такая пара переходит в себя при полуобороте), а тройки точек в вершинах правильного треугольника дают особенность с группой изотропии Z/3 (поскольку такие треугольнички переходят в себя при треть-обороте).

В этой сфере искушенный человек узнает пространство модулей кривых рода 1 с одной отмеченной точкой, или, что почти то же самое, пространство комплексных структур на торе, или, что почти то же самое, пространство решеток на плоскости, с точностью до поворотов и гомотетий. Кажется, что это неспроста. И это неспроста.

Каждой решетке на плоскости (с точностью до гомотетии) можно сопоставить тройку точек на окружности следующим образом. Рассмотрим для данной решетки триангуляцию Делоне. Для любого треугольника из этой триангуляции рассмотрим прямые, идущие из центра описанной окружности в вершины треугольника. Такая тройка прямых будет одна и та же для всех треугольников триангуляции Делоне (заметим, что все треугольники либо совпадают с данным, либо ему зеркальны). Эта тройка прямых задает тройку элементов RP^1=S^1 - то, что нужно. Наоборот, по тройке прямых можно однозначно восстановить пару зеркальных треугольников, а значит и триангуляцию Делоне, и решетку - упражнение.

В случае, когда решетка прямоугольная, пары зеркальных треугольников Делоне слипаются в один прямоугольник: он определяет пару прямых, идущих из его центра в уголки, т.е. пару точек на окружности (видно, что слипание прямых, идущих из центра описанной окружности в вершины происходит, когда центр описанной окружности оказывается на одной из сторон треугольника, что выполнено в точности для прямоугольных треугольников). Одноэлементные подмножества окружности получаются из вырожденных решеток.

Пространство решеток на плоскости с точностью до гомотетий оказывается трехмерной сферой. Просто потому, что каждая такая решетка задает комплексный тор, т.е. эллиптическую кривую. Запишем эллиптическую кривую в нормальной форме Вейерштрасса. Нормированная пара коэффициентов этой формы дает точку на трехмерной сфере.

Прокручивание тройки точек на окружности соответствует повороту решетки. При таком повороте коэффициенты эллиптической кривой умножаются один на t^2, другой на t^3. Отсюдова и слоение сферы на трилистники. И вообще, используя всё это, можно для тройки точек на окружности явно записать ее координаты в S^3.

Красота.

таксебемысль 17. Поток сознания про грассманианы.

Мне тут недавно рассказали клёвый факт (который, видимо, стыдно было не знать, но я не знал): квадрика в CP^n-1 - это просто грассманиан G₊(2,n) ориентированных 2-плоскостей в Rⁿ.

Доказательство: выберем положительный ортонормированный базис {u,v} в 2-плоскости П и сопоставим ему вектор z=u+iv из Cⁿ. Тогда сумма квадратов координат z равна нулю, а неоднозначность в выборе базиса отвечает домножению на комплексное число, т.е. в CP^n-1 все корректно.

Примеры:

(1) В случае n=4, получается, что G₊(2,4) диффеоморфен произведению двух 2-сфер, поскольку квадрика в CP³ это еще и вложение Сегре.

(2) А в случае n=6, получается, что G₊(2,6) диффеоморфен комплексному грассманиану G_C(2,4), поскольку последний тоже является квадрикой в CP⁵, заданной единственным соотношением Плюккера.

Заметим, что на G₊(2,n) есть свободная инволюция, меняющая ориентацию. Фактор этой инволюции - это неориентированный вещественный грассманиан G(2,n), очевидно.

Из первого примера получается, что G(2,4) двулистно накрывается произведением двух сфер.

Во втором примере можно заметить, что инволюция, меняющая ориентацию на G₊(2,6) соответствует инволюции на G_C(2,4), которая сопоставляет 2-плоскости в C⁴ ее ортогонал (хорошее упражнение, для которого, наверное, потребуется унитарная версия вотэтойзадачи 23 если оно вообще верно). Значит вещественный грассманиан G(2,6) совпадает с G_C(2,4)/σ, "пространством пар ортогональных 2-подпространств в C⁴".

А еще у G_C(2,4)/σ можно посчитать рациональные когомологии, и они окажутся такими же как у HP₂. И ГКМ-графы для действия тора на том и другом совпадают. Короче, если забить на кручение, то все эти штуки еще и похожи на кватернионную плоскость.

таксебемысль 16. Теоремы Кёйпера-Масси и Васильева.

Занятный факт, который, вроде как, общеизвестный, но мне до недавнего времени не известный. Я проникся, короче. В России особенно популяризован Арнольдом (Арнольд, впрочем, утверждает, что Рохлин утверждает, что этот факт был известен еще Понтрягину в 30х годах).

Теорема: CP^2/conj = S^4 (фактор комплексной проективной плоскости по комплексному сопряжению гомеоморфен 4-мерной сфере). Иными словами, множество комплексно сопряженных пар прямых в C^3 является сферой.

Доказательство не менее красивое, чем само утверждение, - его вполне можно рассказывать на первом курсе мехмата. Рассмотрим все вещественные квадратичные формы от трех переменных. Они образуют 6-мерное векторное пространство. Рассмотрим все неотрицательно определенные квадратичные формы. Они образуют строго выпуклый 6-мерный конус в этом пространстве. Граница этого конуса, очевидно, состоит из неотрицательно определенных квадратичных форм, у которых есть ядро. Заметим, что каждая такая форма после линейной замены координат имеет вид либо 0, либо x^2, либо x^2+y^2=(x+iy)(x-iy), в зависимости от размерности ядра. Ноль нам не интересен - это просто вершина конуса. Возвращаясь к исходным координатам, получаем, что ненулевая форма, лежащая на границе конуса, имеет вид

(ax+by+cz)^2

или

(ax+by+cz)^2+(dx+ey+fz)^2=[(a+di)x+(b+ei)y+(c+fi)z]*[(a-di)x+(b-ei)y+(c-fi)z]

В первом случае соответствующая квадрика - двойная вещественная прямая (что есть частный случай комплексно сопряженной пары прямых), во втором - пара комплексно сопряженных различных прямых в C^3. Таким образом, пространство пар комплексно сопряженных прямых в C^3 отождествляется с пространством лучей, лежащих на границе конуса неотрицательно определенных форм. Ну а, ясное дело, что лучи, образующие границу выпуклого 6-мерного конуса, образуют четырехмерную сферу.

Дальше больше. Если взять конус неотрицательно определенных квадратичных форм в произвольном R^n, то его граничные лучи по-прежнему образуют сферу. С другой стороны, каждую такую квадратичную форму можно рассматривать как симметричную матрицу с неотрицательными собственными числами. Сопоставив матрице флаг ее собственных подпространств, и нормированный набор собственных значений, можно в одну строчку вывести теорему Васильева о том, что когерентный джойн грассманианов - это сфера. Подробности восстанавливаются по статье Шапиро "Обобщение теоремы Кёйпера-Масси".

У меня есть смутное ощущение, что всё это связано с бесконечными грассманианами, летающими по отрезку, возникающими при доказательстве периодичности Ботта (таксебемысль 12). Выглядит, во всяком случае, похоже.

А еще у Арнольда есть обобщение, согласно которому фактор кватернионной проективной плоскости по окружности - это семимерная сфера. Вот оно-то мне и интересно.

таксебемысль 15. Драконья лемма Холла.

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

В драконьей лемме Холла есть n+1 девушка, n юношей и 1 дракон. У юношей и девушек есть по прежнему двудольный граф преференций. Дракон прилетает и упячивает одну из девушек. Оставшуюся молодежь надо успешно обвенчать. Драконий Холл дает необходимые и достаточные условия, при которых это можно сделать независимо от того, кого упячил дракон.

При чем тут пермутоэдр? Его объем можно вычислить, просуммировав определенные мономы по множеству драконьих паросочетаний. Взято из статьи Постникова "PERMUTOHEDRA, ASSOCIAHEDRA, AND BEYOND".

таксебемысль 15. Еще про матрицы.

Теорема Хорна-Шура утверждает, что множество диагоналей всевозможных (n+1)x(n+1)-матриц с фиксированными попарно различными собственными значениями, например, 0,1,2,...,n, является n-мерным пермутоэдром. Т.е. выпуклым многогранником, вершины которого - точки (σ(0),...,σ(n)), для всевозможных перестановок σ(n+1)-элементного множества собственных значений.

Каждому графу Г на n+1 вершине можно сопоставить множество М(Г) симметричных матриц, у которых на позиции i,j стоит ноль, если (i,j) не является ребром графа Г. Иллюстрации в предыдущей заметке. Если граф - простой путь, то получается множество трехдиагональных матриц. Если граф - звезда, то получается множество симметричных матриц, у которых ненулевые числа допускаются только на диагонали, первой строке и первом столбце. Для произвольного графа Г можно задаться вопросом, как выглядит множество диагоналей матриц из М(Г), имеющих фиксированные собственные значения 0,1,...,n. Это и есть вотэтазадача 56. Очевидно, что это какое-то подмножество пермутоэдра.

Скрафтил, как выглядит ответ в случае n=3 для графа пути и звездочки на 4-х вершинах. Для звездочки, т.е. матриц 4х4 с диагональю, первой строкой и первым столбцом, получается браслет из 6 кубиков. Для него сделал кусудаму, получилось массивно и приятно на ощупь, но без клея все-таки не держится. Альтернативная моделька - с зеленым контуром объемлющего пермутоэдра.

А с трехдиагональными матрицами тоже любопытно. Известно (Томеи), что множество трехдиагональных симметричных матриц с заданным спектром и неотрицательными числами вне диагонали само изоморфно пермутоэдру как многообразие с углами. Если взять у этих матриц диагональ, получаем отображение одного пермутоэдра в другой. Отображение задает биекцию вершин, но сам пермутоэдр при этом адово колбасит. В итоге вторая моделька (с синим контуром) - это на самом деле пермутоэдр в пермутоэдре, только с кучей перекруток и самопересечений.

таксебемысль 15. Алгебраическое сангаку.

 Смотри!