таксебемысль 14. Про разрешимость геометрических задач.

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

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

Например, утверждение ∀p∀q [(p*p-4*q≥0) => ∃x (x*x+p*x+q=0)] представляет из себя общеизвестный школьный факт, но его истинность можно было бы проверить алгоритмически согласно Тарскому. Равно как и ложность утверждения ∀p∀q [(p*p-3*q≥0) => ∃x (x*x+p*x+q=0)]

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

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

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

Этот факт, конечно, можно доказать приведением конкретного нехитрого примера в размерности 3 (сфера Барнетта). Но классно, что его можно вывести из алгоритмической науки и двух адовых теорем.

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

таксебемысль 13. Конечные топологии.

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

Можно смотреть на конечный симплициальный комплекс как на нормальное такое континуальное топологическое пространство, что обычно все и делают. А можно смотреть на него как на комбинаторную структуру, т.е. конечное частично упорядоченное множество симплексов.

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

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

Короче прикольно, что бывает конечное множество, "похожее" по всем показателям на n-мерную сферу.

Все сие давно известно и шарится по работе McCord Singular homology groups and homotopy groups of finite topological spaces

таксебемысль 12. Периодичность Ботта в детском саду.

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

О бар-конструкции (вернее о том, как ее надо понимать).

Допустим у нас есть моноид M, то есть множество, элементы которого можно умножать, умножение ассоциативно: (ab)c=a(bc), и обладает единицей e: a1=1a=a. До кучи пусть моноид будет топологическим, то есть представляет из себя топологическое пространство, с непрерывным умножением.

Рассмотрим отрезок [0;1] и накидаем туда произвольное конечное число точек (частиц). Каждую частицу снабдим зарядом, принимающим значение в моноиде M. Таким образом у нас есть конечный набор {(t1,g1),...,(tn,gn)}, где ti — координата i-й частицы, а gi — ее заряд. Рассмотрим конфигурационное пространство: разрешим частицам непрерывно летать по отрезку, а также непрерывно менять свой заряд. А также потребуем следующую естественную штуку: когда две частицы слипаются, они превращаются в одну частицу, заряд которой равен произведению зарядов исходных. При этом произведение берется именно в том порядке, в котором столкнулись частицы, что важно, т.к. моноид может не быть коммутативным. Будем также для удобства считать, что все прочие точки отрезка имеют заряды, равные единице моноида (либо, эквивалентно, что точку с зарядом 1 можно просто выкидывать из рассмотрения). Обозначим конфигурационное пространство таких наборов частиц через K.

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

Поставим в левый конец отрезка ловушку: скажем, что если частица попала в точку 0, то ее заряд автоматически обнуляется. Пространство конфигураций частиц с ловушкой в нуле обозначим K_0. Теперь поставим дополнительную ловушку в правый конец. Пространство конфигураций с ловушками в нуле и единице обозначим K_01.

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

Классифицирующее пространства группы G — это по определению пространство орбит свободного правого действия группы G на стягиваемом пространстве. Известно, что все такие пространства BG гомотопны друг к другу, так что определение корректно.

Теперь заметим три вещи. (1) K_0 стягиваемо. Действительно, можно равномерно стянуть отрезок в 0. Всякая заряженная фигня, которая на нем сидит, очевидно, тоже уползает в 0, где успешно дохнет в ловушке. А значит мы получили явное стягивание K_0 в точку. (2) Группа G свободно действует на K_0 справа. Мы просто подкручиваем заряд правого конца отрезка. (3) Пространство орбит — это в точности K_01. Очевидно, т.к. наше действие просто забывает заряд правой точки, что эквивалентно установке ловушки в 1. Таким образом, K_01 = BG.

(Немного покрутившись, можно доказать, что бар-конструкция вот в точности совпадает с конструкцией Милнора для BG через бесконечный джойн).

(Пример. Если моноид - группа из двух элементов Z/2={+,-}, то бар-конструкция K_01 — это в точности RP, бесконечномерное вещественное проективное пространство. Каждая конфигурация представляет из себя конечный набор отрицательно заряженных точек на отрезке, причем эти точки могут либо аннигилировать друг с другом, либо упячиться на концах отрезка. Всевозможные n-точечные наборы ((t1,-),...,(tn,-)) представляют из себя n-симплекс, а приклейка границы этого симплекса к симплексам меньшей размерности — отображение степени 2, ровно как в стандартной клеточной структуре на RP).

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

Петли

Пусть Х - пространство с отмеченной точкой, а ΩX — пространство петель на Х, т.е. пространство отображений из окружности S^1 в Х, переводящее отмеченную точку в отмеченную. В ΩX тоже есть отмеченная точка — постоянная петля. Заметим, что если мы нашли расслоение, у которого база — Х, а тотальное пространство стягиваемо, то слоем автоматически будет ΩX (с точностью до гомотопии). Отсюда, в частности, следует, что ΩBG гомотопно G для любой группы G (ровно потому что G — это слой расслоения с базой BG и стягиваемым тотальным пространством). Поэтому классифицирующее пространство группы можно понимать как "распетливание" группы (процедура дает пространство, петли на котором - это исходное G).

Для произвольных моноидов M это неверно. Однако при некоторых технических условиях на М имеется теорема о групповом пополнении, которая утверждает, что ΩBM гомотопно групповому пополнению моноида М (моноид можно канонически превратить в группу, добавив формально обратные элементы). На самом деле, там некая более хитрая штука, которую я не до конца осознаю, честно говоря.

Теперь про периодичность Ботта - один из крутейших фундаментальных фактов.

Рассмотрим группы U(n) унитарных матриц размера nxn. Имеем вложенную цепочку: U(1) c U(2) c U(3) c .... Каждая вкладывается как левый верхний блок в матрицу большего размера. Обозначим объединение всех этих групп через U — это группа всех бесконечных вправо и вниз унитарных матриц, у которых лишь конечный блок может быть нетривиальным, а вне него — единицы на диагонали и нули на всех прочих местах. Будем называть такие матрицы финитными. Иными словами, U — это группа всех унитарных операторов на C^∞, которые тождественны на подпространстве конечной коразмерности.

Периодичность Ботта: ΩΩU = U

(под равенством тут и далее понимается гомотопическая эквивалентность)

Типа доказательство. Стандартный факт: классифицирующее пространство BU(n) унитарной группы U(n) — это грассманиан Gr(n), то есть множество всех n-мерных комплексных подпространств в C^∞ (финитных, т.е. сидящих в каком-то конечном координатном подпространстве C^m). Пусть Gr — дизъюнктное объединение всех грассманианов Gr(n).

Имеется процедура склеивания из двух унитарных матриц одной блочной. Она задает гомоморфизм групп

U(n)xU(m)-->U(n+m)

Этот гомоморфизм индуцирует отображение BU(n)хBU(m)-->BU(n+m). Иными словами, превращает Gr в моноид. Групповое пополнение этого моноида — это пространство BUxZ, где Z — это целые числа. Непосредственно это осознать трудно, но можно заметить, что Gr классифицирует моноид векторных расслоений на любом пространстве X, а BUxZ классифицирует К-теорию на Х, которая есть групповое пополнение моноида векторных расслоений (операция — сумма Уитни, как раз индуцируется из введенной операции на Gr).

Вернемся к конфигурационным пространствам. Накидаем на отрезок [0,1] частиц: каждая частица заряжена финитной плоскостью в C^∞. Наложим также условие, чтобы все эти плоскости были попарно ортогональны. Зададим коллизии как раньше: скажем, что если две плоскости сталкиваются, то они объединяются в одну, равную прямой сумме исходных. Если частица попала в левый или правый конец отрезка, то ее заряд (т.е. плоскость) обнуляется. Обзовем полученное конфигурационное пространство Y.

Более-менее понятно, что Y — это бар-конструкция BGr от моноида Gr.

С другой стороны, легко показать, что Y гомеоморфно U. Действительно, каждой конфигурации точек на отрезке, заряженных плоскостями, т.е. ((t1,V1),...,(tn,Vn)) можно сопоставить финитный унитарный оператор, имеющий собственные подпространства Vk с собственными значениями exp(2\pi i tk), где k=1,..,n. И наоборот, каждый финитный унитарный оператор, согласно спектральной теореме, имеет конечный набор попарно ортогональных финитных собственных подпространств с нетривиальными собственными значениями, лежащими на единичной окружности, а значит определяет конфигурацию из Y.

Итого, U=Y=BGr. По теореме о групповом пополнении имеем ΩU=ΩBGr=групповое пополнение Gr=BU x Z. Вешая петли еще раз, получаем ΩΩU=Ω(BU x Z)=Ω(BU)=U, чего и хотелось.

Если совсем короток: BU - это грассманиан. Однако, если заставить толпу грассманианов летать по отрезку, то получается снова U, просто по спектральной теореме. Отсюда и периодичность. Красиво же!

Вообще, тут много всякой замятой лажи, но она отлаживается по статье Bruno Harris Bott Periodicity via Simplicial Spaces.

таксебемысль 11. Торическое.

Вместо мысли - конспект моего курса из прошлого семестра. Хз зачем, но может кому интересно будет. Правда, мне уже предъявили, что там нетипично большая для нашей науки концентрация интегралов получилась, be careful.

таксебемысль 10. Про градуированные алгебры с двойственностью.

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

Рассмотрим алгебру A многочленов от n переменных. Будем считать, что она градуирована, с произвольными степенями порождающих. Рассмотрим произвольный идеал I этой алгебры, порожденный n однородными многочленами, и содержащий все компоненты алгебры достаточно большой степени. Иными словами, число порождающих идеала = числу порождающих алгебры, и фактор A/I есть конечномерное векторное пространство.

Тогда этот самый фактор A/I является алгеброй с двойственностью Пуанкаре, формальной степени d = (сумма степеней порождающих идеала минус сумма степеней порождающих алгебры). В частности dim(A/I)_k = dim (A/I)_{d-k}.

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

таксебемысль 9. Про фракталы, оригами и теорему Нэша.

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

(2) Я когда-то думал о такой задаче, хотя наверняка, я не первый. Склеим два одинаковых квадратных листа из нерастяжимого материала по границе. Насколько большой объем может ограничивать такая штука? Иными словами, насколько много пуха можно запихать в заданную наволочку? Задача кажется гробом. Если посмотреть на туго набитые подушки в отелях, то видно, что на краях подушки имеются вогнутые бороздки (см.фиг.1). Почти уверен, что в идеальной математической подушке эти крупные бороздки порождают перпендикулярные бороздки поменьше и так далее. Иначе нулевая кривизна наволочки потеряется. Короче, ощущение, что, даже если максимум в задаче про наволочку и достигается, то он достигается на какой-то фрактальной штуке, типа изометрично вложенного плоского тора из п.1.

Фиг.1

(3) Есть такая деятельность, как оригами с непрямыми складками (см.фиг.2-4). Очень эффектно и весьма нетривиально в исполнении (довольно долго продолбался с простейшей ерундовиной https://vk.com/photo3973145_116292676 и получилось кривовасто, фиг.5). А еще якобы используется при разработке обшивки для авианосцев. Но.

Фиг.2    

Фиг.3

Фиг.4

Фиг.5

Кажется, что теоретически все эти штуки просто не существуют, по крайней мере в 2-гладкой категории. Каждый участок между складками представляет из себя поверхность нулевой кривизны, а значит соответствующий участок в исходном листе разбивается на отрезки прямых (интегральные траектории ядра второй квадратичной формы) - получается линейчатая структура. Немного подолбался с дифгемом второго курса, и у меня получилось, что линейчатая структура с одной и другой стороны от складки втыкается в линию складки под дополнительными углами. Иными словами излома траекторий на развернутом листе на месте складки происходить не должно (впрочем, в выкладках я вероятно налажал: буду благодарен, если кто-то это утверждение проверит). Если же вглядется в реальные модели оригами, то видно, что на различных участках линейчатые структуры могут быть не согласованы. Получается одно из трех. (а) Я таки налажал. (б) Мат. моделью для оригами с непрямыми складками является C^1-гладкая геометрия (траблы в вычислениях у меня пошли, когда начал работать с 2-ой кв.формой и кручением складок - объектами более-чем-первого порядка гладкости). (в) Нормальной мат.модели для такого оригами нет вообще - а существуют такие штуки исключительно благодаря деформируемости бумаги в малых масштабах. Бумага все стерпит. Пункт (в) все же сомнителен ввиду теоремы Нэша-Кёйпера. Если верно (б), то складки в таком оригами вполне могут быть фрактальным ужасом.

таксебемысль 8. Про роботов и функториальность гомологий.

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

Есть прикольная штука, взятая, кажется, из книжки Зомородиана по applied topology, которая призвана продемонстрировать, зачем нужна алгебраическая топология и функториальность (!) для повышения этих ваших надоев молока.

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

Допустим теперь, что на конце руки торчит ортогональный репер. Пространство всевозможных ортогональных реперов - это группа SO(3), что топологически есть не что иное, как проективное пространство RP^3. Каждая конфигурация шарниров задает некое положение репера. Таким образом, имеется непрерывное отображение

f: T^n —> SO(3)

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

g: SO(3) —> T^n

что fg=id_{SO(3)}.

Такого не бывает. Действительно, перейдем к гомологиям. Первые гомологии T^n - это Z^n, первые гомологии SO(3) - это Z/2Z. Получаем, что g_*=0, поскольку в гомологиях тора нет кручения. Значит, f_*g_* равно нулю, и не равно id_{H_1(SO(3))}, противоречие. Тут функториальность гомологий прямо-таки по существу.

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

таксебемысль 7. Про хроматические многочлены и алгебраическую геометрию.

Есть одна классная штука: гипотеза Хоггара (Роты-Уэлша-Герона). Элементарно формулируется и доказана несколько лет назад с помощью адского ада. Обычно во всяких популяризаторских сми особенно гремят результаты в теории чисел - там формулировки понятны школьнику, а доказательства - хорошо если специалист за полгода разберется. В комбинаторике подобного добра тоже хватает, но ее меньше жалуют по непонятным мне причинам (вообще, многие не воспринимают комбинаторику всерьез - это они зря). Короче, мне нравится комба, не нравится тч, пишу про комбу.

Хроматические многочлены.

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

Можно показать (и это хорошее упражнение), что P(q) - многочлен от q. Он называется хроматическим многочленом графа Г.

Пример: сколько способов покрасить путь из 3 вершин в q цветов? Для первой вершины есть q вариантов выбора цвета, для второй: q-1 (т.к. цвет первой вершины уже нельзя использовать), для третьей тоже q-1. В итоге хроматический многочлен = q(q-1)^2.

Для пути из n вершин по тем же причинам получится q(q-1)^{n-1}.

И такой же ответ получается для любого дерева на n вершинах (упражнение).

Пример еще: для полного графа на n вершинах получаем P(q)=q(q-1)(q-2)...(q-n+1), поскольку первую вершину можно покрасить в q цветов, вторую в q-1, третью в q-2 и т.д.

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

У любого многочлена есть коэффициенты: P(q)=a_n q^n+a_{n-1} q^{n-1}+...+a_1q+a_0. Известно (это уже посложнее, называется теоремой Роты), что у коэффициентов хроматического многочлена чередуются знаки: при старшей степени стоит положительный коэффициент (на самом деле a_n=1 всегда), при следующем члене отрицательный, и так далее.

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

(a_i)^2 больше или равно a_{i-1}a_{i+1} для всех i.

Такое свойство последовательности чисел называется логарифмической вогнутостью (ратую за введение термина логнутость).

Вот например, для полного графа получается многочлен q(q-1)...(q-n+1). Его коэффициенты называются числами Стирлинга первого рода. Они логнутостью обладают (хотя даже это не очевидно).

А для дерева получаются биномиальные коэффициенты - они тоже логнутые.

Гипотезу Хоггара недавно доказал американец June Huh. На самом деле он доказал также более общее утверждение - про характеристический многочлен представимого матроида.

(*Не знаю, как правильно читать фамилию этого чувака. Если считать, что он кореец, то она должна читаться как Ха. Знакомый американец называл его Хью, но, кажется, не был до конца уверен, что это правильно)

Матроиды.

Пусть фиксировано конечное множество [m]={1,2,...,m}. Симплициальным комплексом называется любой набор подмножеств множества [m], который вместе с множеством A содержит также и все его подмножества.

Например, на множестве [4]={1,2,3,4} можно рассмотреть такой симплициальный комплекс {пустое множество, {1},{2},{3},{4},{1,2},{1,3},{2,3},{2,4},{3,4},{1,2,3}}. Можно представлять себе симплициальный комплекс геометрически: для каждого одноэлементного подмножества рисуем точку, для каждого двухэлементного {a,b} рисуем отрезок между a и b, для каждого трехэлементного {a,b,c} рисуем треугольник между точками a,b,c, и т.д. Подмножества симплициального комплекса называются симплексами.

Матроид - это симплициальный комплекс K с дополнительным свойством. Это называется свойством обмена: если А, B - два симплекса K, и в B больше элементов, чем в А, то какой-то из элементов B, скажем b, можно перекинуть в А. То есть b не лежит в А, и А вместе с b - это снова симплекс K. На матроидном языке симплексы называются независимыми множествами.

Надои молока.

Я фермер, и я хочу прикупить себе коров. У продавца есть m коров, но всех сразу он не готов продать. Зато у него есть перечень, какие наборы коров он может продать. Допустим, что продавец адекватный: если он готов продать некое множество коров, то он также готов продать и любое его подмножество. Это означает, что у продавца есть симплициальный комплекс, кодирующий, какие совокупности коров он готов продать.

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

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

Понятно, что жадный алгоритм не всегда дает оптимальный ответ (есть в этом какой-то морально-философский смысл). Например, продавец готов продать корову 1 жирности 10 и коров {2,3} в совокупности, каждая жирности 9. По жадному алгоритму я отхвачу одну жирную, и больше мне ничего не светит. А мог бы взять 2-ую и 3-ю и поиметь гораздо больший профит. Увы.

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

Откуда брать матроиды - фермерам на заметку.

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

Пусть есть последовательность векторов v1,...,vm в векторном пространстве над произвольным полем F (допускаются нулевые векторы, допускаются повторы). Рассмотрим симплициальный комплекс, у которого вершины - это векторы v1,...,vm, а симплексы - это линейно независимые наборы векторов. Упражнение: такой симплициальный комплекс является матроидом. Матроиды, полученные таким образом, называются представимыми над полем F. Вся матроидная терминология мотивирована этим классом примеров: именно в связи с линейной алгеброй независимые множества матроида называются независимыми множествами, и отсюда же проистекает созвучие слов матроид и матрица.

Упражнение: графический матроид представим над любым полем. Это классное упражнение, поверьте.

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

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

Короче говоря, все матроиды являются комплексами Коэна-Маколея.

Характеристический многочлен матроида.

Можно определить такую штуку как характеристический многочлен матроида (отсылаю к https://en.wikipedia.org/wiki/Matroid ибо тут формулы смотрятся погано). Для графических матроидов - это то же, что и хроматический многочлен с точностью до всяких мелочей.

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

Коэффициенты характеристического многочлена

тоже знакопеременны. И, предположительно, образуют логнутую последовательность. Это гипотеза Роты-Уэлша-Герона, обобщающая гипотезу Хоггара про хроматический многочлен графа. Huh доказал гипотезу для представимых матроидов.

Пермутоэдрическое многообразие и представимые классы.

n-мерный пермутоэдр - это выпуклая оболочка точек, координаты которых - все возможные перестановки чисел 0,1,2,...,n. Это простой многогранник: у него каждая вершина содержится ровно в n гипергранях. Нормальный веер к пермутоэдру совпадает с совокупностью камер Вейля для системы корней A_n. Гладкое проективное торическое многообразие X_n, соответствующее пермутоэдру называется пермутоэдрическим многообразием.

Huh заметил, что любой матроид (в том числе и непредставимый), имеющий n вершин и ранг r+1, задает некий класс 2r-мерных гомологий пермутоэдрического многообразия X_n. Эта конструкция основана на понятии веера Бергмана - штуки из тропической геометрии (грубо говоря, веер Бергмана - это тропикализация линейного подпространства в алгебраическом торе).

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

Дальше можно заметить, что пермутоэдр можно выродить до симплекса двумя различными способами. Каждый из способов дает бирациональную эквивалентность (последовательность сдутий) из пермутоэдрического многообразия в проективное пространство P^n. Склеив эти два отображения в одно, получим отображение f из пермутоэдрического многообразия в P^n x P^n.

Любой гомологический класс пермутоэдрического многообразия можно индуцированным отображением f_* зашвырнуть в гомологии P^n x P^n. Любой 2r-мерный класс гомологий в P^n x P^n имеет вид

A=a_r[P^r x P^0]+a_{r-1}[P^{r-1} x P^1]+...+a_0[P^0 x P^r]

т.е. определяется последовательностью целых чисел a_i. Оказывается, если пнуть класс матроида из гомологий пермутоэдрического многообразия в гомологии P^n x P^n, то полученная последовательность коэффициентов a_i - это в точности модули коэффициентов характеристического многочлена матроида.

И теперь катарсис. Huh доказал, что если цикл A в H_*(P^n x P^n) представим алгебраическим подмногообразием, то его коэффициенты a_i образуют логнутую последовательность. Это утверждение как-то хитро выводится из выпуклой геометрии: к чему-то (я пока не понял, к чему) применяется конструкция тел Ньютона-Окунькова, и для них используется неравенство Брунна-Минковского.

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

Собирая все воедино, получаем то, что надо. Если матроид представимый, то его гомологический класс в пермутоэдрическом многообразии представим алгебраическим подмногообразием, значит, если его отправить в гомологии P^n x P^n, то получится тоже представимый класс, значит коэффициенты последнего, которые суть коэффициенты характеристического многочлена, образуют логнутую последовательность.

Если чуваку, который все это придумал, не дадут Филдса, то это будет совсем печально. Вот его хоумпейдж https://web.math.princeton.edu/~huh/

таксебемысль 5. Про равносоставленность и мотивы.

Я хз как правильно переводить scissors congruence на русский, но для многогранников используется слово равносоставленность. Эта идея кажется офигенно важной, интересной и старой.

Идея, собственно, такова: допустим у нас есть объекты определенного вида, которые можно разбивать на кусочки (которые суть тоже объекты того же вида), и, допустим, определены допустимые обратимые преобразования объектов. Тогда два объекта А,Б называются равносоставленными, если А можно разбить на кусочки, каждый из кусочков преобразовать допустимым образом, и собрать из полученных кусочков объект Б.

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

Теорема Бойяи-Гервина утверждает, что верно и обратное: если два многоугольника имеют одинаковую площадь, то они равносоставленны. Поэтому равносоставленность многоугольников на плоскости не очень интересна.

3-я проблема Гильберта (имхо, самая понятная из всех его проблем) спрашивает, верен ли аналогичный факт в трехмерном пространстве. Если два многогранника имеют одинаковые объемы, верно ли, что один из другого получается перекладыванием кусочков? У вопроса есть исторический подтекст: известно, что древние греки (Евдокс и Архимед таки) посчитали объемы всяких неочевидных штук, типа пирамиды, конуса и шара, но для этого им пришлось изобрести зачатки матана. Чтобы посчитать объем пирамиды, надо просуммировать бесконечно много бесконечно малых кусочков - срезов пирамиды, то есть взять интеграл. Вопрос Гильберта был в том, смогли бы древние греки вычислить объем пирамиды без матана: т.е. смогли бы они разрезанием и перекладыванием получить из пирамидки кирпич (прямоугольный параллелипипед), объем которого уже и ежу понятен.

Теорема Дена дает отрицательный ответ на вопрос Гильберта. Правильный тетраэдр не равносоставлен кирпичу, даже если их объемы совпадают. Я считаю как теорему, так и доказательство одними из самых клевых математических штук - именно такие вещи надо рассказывать школьникам, чтобы продемонстрировать красоту математики. Оказывается, помимо объема у многогранников есть еще одна характеристика - псевдообъемы, или "инвариант Дена", - которая неизменна при разрезании-перекладывании-собирании-кусочков. У кирпича инвариант Дена равен 0, а у тетраэдра не равен, откуда и получается теорема.

А вот уже более поздняя теорема Сидлера (1965) говорит, что если у двух многогранников совпадают объемы и инварианты Дена, то они равносоставлены. Ее доказательство тоже однозначно ня - там возникают модули кэлеровых дифференциалов, и прочая бешенная гомологическая алгебра и К-теория. Именно такие вещи надо рассказывать студентам математических факультетов, чтобы продемонстрировать красоту математики (хотя им, наверное, поздно - уже попались).

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

Можно еще рассматривать плоские фигуры, разбивать их на подфигуры, но разрешить каждый кусочек не просто двигать, но еще и гомотетировать. Получается довольно забавное отношение равносоставленности: например, круг равносоставлен квадрату - см.рисунок (заскринен из абсолютно великолепной книги Игоря Пака Lectures on discrete and polyhedral geometry, которую всем читать).

Разных других объектов, которые можно разбивать на куски, перекладывать и собирать обратно, можно придумать чертову уйму. Из важных: можно вместо многогранников брать алгебраические многообразия - в этом случае классы равносоставленности называются мотивами. Насколько мне хватает скудных познаний в этой области, профит в том, что многие разнородные классические инварианты многообразий являются инвариантами мотивов. Сюда относятся и топологические (эйлерова характеристика), и комплексные (многочлены Ходжа-Делиня, что есть в гладко-проективном случае просто числа Ходжа), и теоретико-числовые (число точек многообразия над конечным полем). Ну а мотивы как бы позволяют все это изучать одновременно, что круто.

Например, если обозначить через L - мотив аффинной прямой, а Pn - мотив n-мерного проективного пространства, то имеем нехитрое мотивное равенство

Pn = 1+L+L^2+...+L^n

(поскольку можно из проективного пространства вырезать аффинный кусок L^n, и останется проективное пространство на 1 меньшей размерности, ну а дальше по индукции). Теперь, если в выражение справа подставить вместо L формальную переменную t, то получится производящая функция для диагональных чисел Ходжа (они же в данном случае числа Бетти) комплексного проективного пространства. В частности, подставляя вместо L единицу, получим эйлерову характеристику. А если вместо L подставить простое число p, то получится количество точек проективного пространства над конечным полем F_p. Ну и всякое такое.

Вместо проективного пространства можно взять гладкое проективное торическое многообразие X. Тогда получится симпатичная мотивная формула

[X]=h_0+h_1L+h_2L^2+...+h_nL^n,

где {h_i} - h-числа соответствующего X простого многогранника.

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

таксебемысль 4. Про локализацию.

Есть волшебный класс формул, которые позволяют считать разные хитрые интегралы (вроде Хариш-Чандры-Ицыксона-Зюбера, помянутого ниже) - формулы локализации. Интересно, что их можно приспособить для решения вполне прикладной задачи: вычисление точного значения объема многогранника/интеграла от произвольной аналитической функции по многограннику. Это в каком-то роде фольклор: команда из 5 американцев это опубликовала в 2012 году, однако в давних работах Хованского и Ко это в неявном виде содержится, а скорее всего было кому-то известно и до.

Пусть P - многогранник размерности n, у которого в каждой вершине x сходится ровно n ребер. Такие многогранники называются простыми. Куб - простой. Октаэдр - не простой. Любой многоугольник - простой.

Для вершины x рассмотрим векторы v_{x1},...,v_{xn}, направленные вдоль выходящих из x ребер и имеющие определитель 1. Тогда объем многогранника равен

Volume(P) = (1/n!) сумма по всем вершинам x выражений (x^n/v_{x1}...v_{xn})

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

Пример вычисления на картинке. Многоугольник взят целочисленным, чтобы можно было заценить правильность ответа по формуле Пика.

Опечатка: в третьем слагаемом должно быть (-a-b)b в знаменателе.

Можно похожим волшебным образом посчитать центр масс однородного многогранника. Известно, что центр масс = (интеграл по P от xdx)/Volume(P). Так вот

Интеграл по P от xdx = (1/(n+1)!) Cумма по вершинам x выражений (x^{n+1}/v_{x1}...v_{xn})

Тут суммируются рац.функции формальной степени 1, и утверждается, что в результате получится нечто без знаменателя - т.е. многочлен степени 1, то есть вектор из V - объемлющего пространства многогранника. Как и положено.

Пример на другой картинке.

Тут тоже опечатка: в третьем слагаемом должно быть (-a-b)b в знаменателе.

Для невыпуклых эти формулы тоже работают, только надо в невыпуклых точках правильно ставить знаки +/- при суммировании.

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

UPD. Со знаками налажал. Там, кажется, в обеих формулах должно быть еще (-1)^n.