таксебемысль 35 про вещественные числа

Задача хоть и неожиданная, но довольно простая. Прямо вот без дураков, можно давать на кружке детям почти любого возраста.

Докажите, что в любом вещественном отрезке [a,b] найдется ровно одно рациональное число p/q с минимальным |p|+|q|.

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

Для этого можно использовать функциональный аналог последовательностей Коши: регулярные функции (термин overused, но увы, не я его придумал). Регулярная функция - это функция f : Q_+ —> Q. Мы говорим, что такая функция представляет вещественное число a, если f(e)∈[a-e,a+e] для любого e. Иными словами, функция хранит рациональные приближения вещественного числа с любой наперед заданной точностью.

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

Поскольку сложность точной арифметики с дробями растет очень быстро относительно размера числителей и знаменателей, осмысленно у рац.чисел минимизировать |p|+|q|. Поэтому полезно на все регулярные функции навесить "аппроксиматор", который не просто выдает рац.число f(e)∈[a-e,a+e], а именно то рац. число, на котором минимизируется |p|+|q| в указанном интервале. С точки зрения функционально-символьной это не сильно усложняет жизнь, процедура вычислимая. Зато упрощает реальные вычисления.

Например, математически было бы естественно хранить вещественное число 6000000/3000001 в виде постоянной регулярной функции, которая выдает его самое при любом e. Но с точки зрения оптимизации, при e>0.000001, можно положить f(e)=2/1, - при грубых округлениях и так сойдет.

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

Подробности см. O'Connor, A Monadic, Functional Implementation of Real Numbers.

PS. Мне вк написали, что числа, которые получаются описанным образом - это наилучшие рац.приближения. Видимо, так оно и есть.

таксебемысль 34 про упаковку шаров

Тут можно было бы написать про результаты Вязовской, - филдсовской лауреатки 2022 - о всюду плотной упаковке в евклидовых пространствах размерности 8 и 24. А можно было про размерность 3: история с гипотезой Кеплера на мой взгляд достаточно иллюстративна, потому что точку в этой истории поставило использование прувера на основе теории типов (хоть и не гомотопической).

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

Оригами. В оригами есть метод дизайна моделей, который называется circle packing. Не уверен, кто придумал идею, и тем более термин, но за подробностями - прошу в книгу Роберта Лэнга Origami Design Secrets: Mathematical Methods for an Ancient Art, где метод впервые был явно объяснен широкой аудитории. 

Забавна предыстория: в Японии в 90-х стала популярна идея математического моделирования оригами - взамен творческому наитию, что породило такую активность как "жучьи войны". Оригамисты соревновались, кто сделает более забористых жучков-паучков с бОльшим числом конечностей. Полагаю, что circle packing был своего рода фольклором в Японии в то время. Лэнг дистанционно участвовал в японских жучьих войнах. В 00-х он окончательно переключился с оригами-как-хобби на оригами-как-профессию, и на английском объяснил суть метода в своей книге.

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

[Суперфомальная формализация, которую вы не просили, но заслужили. Процесс складывания - это 1-липшицево отображение F:S-->M, где S - это исходный лист бумаги с римановой метрикой, а М - это итоговая модель - полиэдр в R^3 с внутренней метрикой. Очевидно, что метрика не увеличивается, потому что в оригами рвать бумагу нельзя. Если F(x)=y, а B_r(x) и B_r(y) - шары в S и M соответственно, то из липшицевости очевидно, что полный прообраз B_r(y) содержит B_r(x). Поскольку в метрическом дереве висячее ребро - это шар с центром в висячей вершине, получаем то, что написано в предыдущем абзаце.]

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

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

Упаковка кругов и реки между ними.

Да и вообще, сама формализация оригами - дальше соображений липшицевости - уже вопрос, на мой взгляд, открытый. Демэйны - это такая пара геометров из MIT - много в этой области сделали, но их аксиоматика мне кажется плохо алгоритмизуемой. Не существует такой структуры данных как "оригами-модель" (если что, полиэдры в R^3 не учитывают накладывающиеся слои бумаги). В этом смысле оригами гораздо сложнее музыки, картинок и 3d-графики. Корректно определить тип Оригами и формально доказать какую-нибудь базовую теорему - это реально челлендж. Например, хорошая тестовая теорема: любую модель можно сложить, то есть непрерывно изотопировать из плоского листа.]

После оптимальной упаковки надо задизайнить саму модель - с учетом, что модель - это все же не совсем граф. Тут начинается уже разная жесткая геометрия, отчасти эвристическая. Частично все механизируется, см. например https://langorigami.com/article/treemaker/ Но это отдельная история.

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

Вайфай. Второй сюжет - он про фантазию, которая пока явно не применяется. Но, в принципе, наверное зря и наверное в будущем может. 

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

Для финальных пользователей прогресс в беспроводных технологиях измеряется скоростью соединения. В цепочке gsm-3g-4g-5g-6g она растет прямо ощутимо. Достигается это, помимо улучшения передатчиков и приемников, увеличением окна частот, да и самой частоты. Тут все примерно понятно: чем больше частота, тем больше пакетов можно напихать в единицу времени, а чем больше окно - тем больше пакетов распихивается по частотам. Разрабатываемый 6g движется куда-то в сторону терагерцевого диапазона. 

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

Сигнальное созвездие https://ru.wikipedia.org/wiki/Сигнальное_созвездие - это способ кодировать бинарный сигнал в аналоговом пространстве. Зафиксируем пока что частоту. Рассмотрим плоскость с полярными координатами (амплитуда, сдвиг фазы). На этой плоскости изображается сигнальное созвездие - это облако из 2^k точек, соответствующих битовым строчкам длины k. Если нам надо передать битовую строчку, то мы смотрим, какая точка (r,alpha) созвездия ей соответствует, генерируем сигнал амплитуды r со сдвигом alpha (и фиксированной частоты). Передаем его. Приемник получает сигнал с аналоговыми характеристиками (r',alpha'), находит ближайшую к нему точку сигнального созвездия - по Евклиду. И декодирует ее в битовую строчку. 

И вот если вы посмотрите глазами геометра на примеры сигнальных созвездий, используемые в этих ваших интернетах (например, полистаете википедию), то увидите, насколько они все унылы и скучны. Там используются либо точки в вершинах правильного 2^k-угольника (т.е. одной амплитуды), либо точки в узлах декартовой квадратной сеточки. 

Квадратурная амплитудная модуляция, спертая из википедиев

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

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

Тут, казалось бы, делов-то.

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

- На основании эллипсоидов нормальных распределений задать на плоскости риманову метрику.

- В этой метрике решить задачу оптимальной упаковки шаров.

- Для полученного сигнального созвездия подобрать линейное разрешающее дерево для диаграммы Вороного.

- Спаять это разрешающее дерево из демодуляторов.

- Пропихнуть это в качестве стандарта для 7G.

- Profit!

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

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

таксебемысль 33 о геометрической топологии

В одном из наших лабных чатов обсуждался наивный вопрос, индуцировавший у меня некий поток сознания. Кмк, можно все это вынести на более широкое обозрение/обсуждение. Вопрос:

У каких замкнутых многообразий есть атлас из двух карт?

(ага, типа горжусь, что подобные вопросы обсуждаются на фкн:)

Ответ, очевидно, зависит от того, что понимается под словом карта.

Вариант 1, который, считался дефолтным в обсуждении. Карта - это что-то стягиваемое, типа диска. Тогда это как будто вопрос о категории Люстерника-Шнирельмана (кстати, а это правда?). Хочется сказать, что категория = 2 только у гладких многообразий гомеоморфных сфере, в том числе у экзотических. 

В размерности 2 это так: у всех поверхностей кроме сферы слишком большая когомологическая длина. В размерности 3 тоже так: например, см.  https://www.sciencedirect.com/science/article/pii/0040938392900097 + Пуанкаре/Перельман. В общей размерности из cat=2 вытекает что когомологическая длина равна 1, а значит многообразие - гомологическая сфера. Что делать с зазором между гомологическими сферами и настоящей сферой - я не знаю, нужны специалисты. Чую, что у нетривиальной гомологической сферы не может быть атласа из двух стягиваемых карт, но доказать не умею.

Вариант 2. Карта - это любое открытое множество U нашего Mⁿ, гомеоморфное области в Rⁿ. Формальное определение атласа именно такое, на самом деле. 

Тут имею сказать интересную вещь. 

Во-первых, любая ориентируемая 2-поверхность имеет атлас из двух карт (например, тор можно склеить из двух аннулюсов, - всратое видео с китайской фабрики не даст соврать https://www.youtube.com/watch?v=QkPqGnXD-yA ). У неориентируемых: атлас из 2 карт есть у поверхностей четного рода, а у неориентируемых нечетного рода как будто нет (задача). 

Во-вторых, у любого трехмерного многообразия есть атлас из двух карт. Возьмем разбиение Хегора и каждую из двух компонент немного утолстим, чтобы получить открытое множество. Получили два множества, каждое из которых - открытый шар с ручками - вполне себе вкладывается в R³. Чем не карты.

В-третьих, кажется, что фокус с разбиением Хегора работает с любым многообразием нечетной размерности >1. Возьмем у (2n+1)-мерного многообразия M триангуляцию K, двойственное ей клеточное разбиение L, и разобьем M в объединение окрестностей n-мерного остова K и n-мерного остова L. Оба остова вкладываются в R²ⁿ⁺¹, уж наверное, их окрестности тоже вложатся. Опять же получили атлас из двух карт.

(про высокомерного Хегора тут обсуждают https://mathoverflow.net/questions/81041/higher-dimensional-heegaard-splittings правда вложимость окрестностей аккуратно проверять надо, например через индуктивное приклеивание ручек. Есть ощущение, что ручки малого индекса, а объемлющее пространство большой размерности. Места для приклейки ручек вроде должно хватить, но это не точно.) 

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

Такая вот задача внезапная.

таксебемысль 32 тропическая

Подумалось, довольно странно, я тут много чего пишу, а вот про тропические штуки ни разу не писал. Надо исправляться. 

Этакие туристические наброски: немного о происхождении видов, об особенностях продажи фруктов, о деревьях, об отличиях тропиков Рака и Козерога, об особенностях работы таксистов и о венгерских мигрантах. Небольшое экзотическое путешествие.

0) Интро. 

Тропическая математика - это тропическая арифметика и тропическая геометрия. Про другие дисциплины, например, тропическую топологию или тервер, никогда не слышал.

Тропическая арифметика - это множество вещественных чисел, на которых определены две арифметических операции: тропическое сложение a⊕b=min(a,b) и тропическое умножение a⊙b=a+b. Приятно проверить, что тропические операции удовлетворяют базовым школьным законам коммутативности, ассоциативности и дистрибутивности.

Алгебраическая мотивация за этим такая. Есть многочлены от одной переменной, их довольно полезно складывать и умножать, в обычном смысле. Можно от многочлена F оставить только младшую степень k(F) входящих в него мономов. Тогда легко заметить, что при умножении многочленов числа k(F) складываются, а при сложении/вычитании - от них берется минимум (*за исключением ситуации, когда младшие члены сокращаются, но такого почти никогда не бывает, и этим пока можно пренебречь). Если вместо k(F) брать порядок нуля в какой-то фиксированной точке, - не только в 0, - то арифметика таких порядков тоже получается тропической. Вместо многочленов F можно брать формальные степенные ряды, многочлены или ряды Лорана, ряды Пюизо, ряды Хана или ряды Новикова - во всех случаях тропикализация состоит во взятии младшего порядка.

В соответствии с общей идеологией, если обычный моном от нескольких переменных - это выражение вида a⋅x^k⋅y^l⋅z^m..., то тропический моном - это a+kx+ly+mz+..., то есть просто линейная функция (с целыми коэффициентами ). Тропический многочлен - это тропическая сумма набора мономов, то есть, говоря по человечески, минимум от конечного числа линейных функций. Можно заметить, что это всегда непрерывная выпуклая вверх кусочно линейная функция.

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

P(x1,...,xn)=⊕{ak⊙x1^k1⊙...⊙xn^kn}=min{ak+k1⋅x1+...+kn⋅xn}

- тропический многочлен, то множество его "нулей" - это множество всех таких x=(x1,...,xn), для которых минимум в правой части достигается хотя бы на двух выражениях одновременно.

Пример. Ноль линейного тропического многочлена P(x)=2⊕(3⊙x) - это точка излома функции min(2,3+x), то есть точка x0=-1 (при которой 2=3+x0).

Аффинное тропическое многообразие - это пересечение конечного числа тропических гиперповерхностей. Это какая-то странная неограниченная кусочно линейная штука в R^n. 

Аффинная тропическая кривая (какая-то, не суть важно)

Почему нули тропических многочленов нужно определять именно так (как множество точек излома) - вопрос довольно естественный. Если вкратце, то история такая. Допустим, что у нас изначально система обычных алгебраических уравнений определена не над полем R или C, а над полем рядов Пюизо от одной переменной. 

Ряды Пюизо - это формальные ряды Лорана от дробных степеней переменной. Ряды Пюизо образуют алгебраически замкнутое поле, - это на самом деле алгебраическое замыкание поля обычных рядов Лорана. Поэтому, в принципе, на ряды Пюизо можно смотреть как на некий функциональный аналог поля C - вся университетская интуиция тут работает, но появляется бонус: у рядов Пюизо можно брать младшую степень k(F), - чего не бывает в C. Так вот, если определить множество настоящих нулей многочлена P(x1,...,xn) над полем рядов Пюизо, и взять у каждого решения F младшую степень k(F), то полученное множество как раз и будет множеством тропических решений соответствующего тропикализованного многочлена.

Пример. Найдем решение уравнения (5t^2-3t^4-t^7)+x(4t^3+8t^5-t^9)=0 относительно x в поле рядов Пюизо от t. Тут даже рядов Пюизо не надо, все решается в обычных степеных рядах x=-(5t^2-3t^4-t^7)/(4t^3+8t^5-t^9)=-(5/4)t^{-1}+[члены старших степеней]. Если от всех формальных выражений оставить только младшие порядки, то останется тропическое уравнение 2⊕(3⊙x)=0 из прошлого примера. То, что мы в прошлом примере получили тропическое решение x0=-1 полностью согласуется с тем фактом, что честное решение исходного уравнения начинается с члена t^{-1}.

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

1) Философия.

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

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

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

I.Itenberg, L.Katzarkov, G.Mikhalkin, I.Zharkov, Tropical Homology, Mathematische Annalen 374 (2019) и прочий свежачок.

А негативные примеры тут будут мелькать ниже.

2) История.

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

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

Пусть дан "метрический" граф на n вершинах, то есть фиксирована матрица расстояний D=(d[i,j]) где d[i,j] - расстояние от i-й вершины до j-й вершины (расстояния могут быть бесконечными, несимметричными и не удовлетворять неравенству треугольника). Тогда тропический квадрат D⊙D матрицы - это матрица расстояний-за-два-шага в исходном графе (упражнение на осознать). А тропическая k-ая степень матрицы D - это матрица расстояний за k шагов.

Название "тропическая" произошло в честь Имре Симона, который работал в Сан-Паулу, Бразилия, и занимался как раз-таки алгоритмами. Впрочем, сам он был венгром, поэтому не будет большой ошибкой сказать, что тропическая математика - это часть венгерской математики, несмотря на географический диссонанс такого утверждения.

3) Определители.

Обычный определитель матрицы A=(a[i,j]) размера n - это сумма по всем перестановкам s:[n]-->[n] произведений вида a[1,s(1)]⋅a[2,s(2)]⋅...⋅a[n,s(n)] с какими-то знаками. В интернете есть многочисленные треды, где обсуждается, есть ли какая-то польза от определителей больших матриц. Ну то есть для математики, понятно, что есть абстрактная польза, иначе зачем бы мы это учили. Но вот возникает ли где-то на практике необходимость быстро посчитать определитель размера хотя бы 20? Уже вопрос. Ни одного интересного примера я не нашел, как ни странно.

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

К счастью для нас, в курсе линала есть весьма фундаментальная штука - алгоритм Гаусса. В его прикладной ценности сомнений гораздо меньше. Его же можно приспособить для вычисления определителя. Вычисление по Гауссу займет O(n^3) арифметических операций. 

Если долго и целеустремленно копать, то можно отрыть алгоритм вычисления определителя, основанный на константе матричного умножения. Он теоретически работает за O(n^2.37188), но там настолько неописуемо ужасная O-константа, что на практике это не слишком полезно. 

Теперь следите за руками. 

Что такое тропический определитель? Заменим в формуле определителя сумму на минимум, а произведения на суммы, про знаки перестановок просто забудем. Получим, что тропический определитель матрицы A=(a[i,j]) - это минимум по всем перестановкам s:[n]-->[n] сумм вида a[1,s(1)]+a[2,s(2)]+...+a[n,s(n)].

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

Допустим у нас есть n клиентов и n такси, и известно, что отправить i-го таксиста к j-му клиенту стоит a[i,j] денег. Назначение - это биективное соответствие между клиентами и таксистами, то есть попросту перестановка s:[n]-->[n]. Стоимость назначения - это (внезапно) сумма a[1,s(1)]+a[2,s(2)]+...+a[n,s(n)]. Нам надо назначить таксистов клиентам так, чтобы минимизировать стоимость. То есть тропический определитель - это буквально стоимость оптимального назначения.

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

Лучшая известная реализация Венгерского алгоритма имеет сложность O(n^3). Она довольно хитрая, там вообще ни разу не понятно, почему алгоритм сходится, почему имеет такую сложность и т.д. Однако идеологически все не так уж хитро. Алгоритм Гаусса для обычного определителя ведь работает за O(n^3), так сфигали в тропиках будет по-другому?

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

Нюанс. Наивная тропикализация всей программы первого курса линала не работает. Например, элементарная формула TropDet(A⊙B)=TropDet(A)⊙TropDet(B) попросту не верна. What a disgrace!

Вопрос существования Венгерского алгоритма сложности O(n^2.37188) открыт. Возможно, тропическая интуиция тут как-то поможет.

(-) Интерлюдия: тропики Рака и Козерога

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

Разница не существенная: минимум и максимум меняются местами, если все переменные умножить на -1.

4) Коциклы

Начнем с обычного, не тропического сеттинга. Рассмотрим полный граф на n вершинах, и на каждое его ребро {i,j} посадим вещественную переменную d[i,j]. Можно для полноты картины добавить фиктивные переменные d[i,i]=0 и d[j,i]=-d[i,j]. Множество нефиктивных переменных - это вещественное пространство M размерности n(n-1)/2.

Скажем, что набор переменных удовлетворяет условию коцикла, если выполнено соотношение 

d[i,j]+d[j,k]+d[k,i]=0

для любой тройки {i,j,k}. Нехитро показать, что в этом случае d[i,j]=x[j]-x[i] для некоторого набора вещественных чисел x[1],...,x[n]. То есть набор чиселок d[i,j] при i<j - это просто расстояния между набором точек на прямой, с учетом знака. Если вы доказали этот факт, то можете смело хвастаться, что знаете, почему 1-е когомологии симплекса нулевые. 

В итоге условие коцикла выделяет в M векторное подпространство размерности n-1. 

Что такое тропикализация этого подпространства? В соответсвии с общей идеологией, заменим каждое уравнение d[i,j]+d[j,k]+d[k,i]=0 условием 

"max(d[i,j], d[j,k], d[k,i]) достигается одновременно хотя бы на двух аргументах"

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

Заметим, что такое тропикализованное условие для тройки эквивалентно набору условий d[i,j]≤max(d[j,k], d[k,i]), каждый элемент тройки не больше максимума двух других. И это выполнено для каждой тройки {i,j,k}.

Это же определение ультраметрики! Ну окей, при условии, что d[i,j]>0, это точно определение ультраметрики. Получили 

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

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

Мы не можем заглянуть в прошлое, но у нас есть текущий временной срез, в котором можно проводить любые эксперименты, допустимые нашим уровнем технологий, и предлагать любые интерпретации, допустимые подвешенностью языка экспериментатора. Например, можно взять любые два вида из нашей выборки и оценить их "похожесть", скажем, на основании геномов. Мы получим эмпирический набор положительных чисел. Из общих соображений понятно, что похожие геномы <=> недалекий общий предок. Но как из этого филогенетическое дерево сделать?

Поехали. Заметим, что любое (гипотетическое) филогенетическое дерево задает метрику: d[i,j]="сколько лет назад жил общий предок i-го и j-го вида". И это на самом деле ультраметрика. И наоборот, любая ультраметрика происходит из некоторого филогенетического дерева, упражнение.

Таким образом, если мы хотим восстановить филогенетическое дерево по эмпирическим данным похожести геномов, то надо нашу функцию похожести спроецировать в пространстве M на пространство ультраметрик. То есть на тропическое многообразие 1-коциклов.

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

5) Грассманиан

Историю про связь "Происхождения видов" с тропической математикой я, конечно, не сам выдумал, а взял из статьи 

D.Speyer, B.Sturmfels, The tropical Grassmannian, Adv.Geom.4:3, 2004.

Но там написано несколько другое. Я в прошлом пункте немного упростил картину для первичной ясности. А сейчас справедливость будет восстановлена.

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

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

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

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

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

Обычный грассманиан Gr(q,n) - это многообразие q-мерных подпространств в n-мерном пространстве. Если каждому подпространству П∊Gr(q,n) сопоставить прямую старших внешних форм Λ^qП в Λ^q(R^n) то получим вложение Gr(q,n) в проективное пространство какой-то большой размерности. Образ этого вложения описывается соотношениями Плюккера.

В общем виде нам соотношения Плюккера не понадобятся. В случае Gr(2,n), то есть грассманиана 2-плоскостей, образ вложения задается координатами d[i,j] для всех пар {i,j} из множества {1,..,n}, а соотношения Плюккера имеют вид

+/- d[i,j]d[k,l] +/- d[i,k]d[j,l] +/- d[i,l]d[j,k] = 0

для любой четверки индексов {i,j,k,l}. Знаки в этой формуле нам не особо важны. Но если вам очень надо, - то они такие же, как в теореме Птолемея https://ru.wikipedia.org/wiki/Неравенство_Птолемея . Вообще это отдельная креативная задача (https://vk.com/id3973145?w=wall3973145_1506%2Fall): вывести Плюккера из Птолемея. Или хотя бы наоборот.

 

Давайте тропикализуем соотношения Плюккера. Формула выше превращается в условие

"max(d[i,j]+d[k,l], d[i,k]+d[j,l], d[i,l]+d[j,k]) достигается хотя бы на двух аргументах для любой четверки {i,j,k,l}."

Как и в прошлом пункте, это условие эквивалентно такому

d[i,j]+d[k,l] ≤ max(d[i,k]+d[j,l], d[i,l]+d[j,k]).

Последнее условие хорошо известно, оно называется Four Point Condition. И оно в точности характеризует все древесные метрики. Получили

Тезис. Множество всех древесных метрик на [n] - это тропикализация стандартного плюккерова вложения грассманиана Gr(2,n).

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

6) Аукционы

Десертом нашего сегодняшнего тропического пиршества будет менее серьезный сюжет, о котором мне три года назад рассказал Никита Калинин. Это история про то, "как тропическая геометрия спасла Банк Англии от финансового кризиса". 

Тропические геометры спасают Англию от экономического кризиса. (с)перто из интернетов.

Отличная иллюстрация тезиса, что лучшая реклама микроскопа - та, в которой им забивают гвозди. Если вы, читая предыдущие пункты, не могли избавиться от ощущения, что сову натягивают на глобус, то, чтож... Hold my beer!

Рассказ следует работе, P.Klemperer, The Product-Mix Auction: a New Auction Design for Differentiated Goods, Journal of the European Economic Association, 2010. 

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

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

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

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

Дальше участники аукциона делают ставки. Каждая ставка имеет вид "готов купить А по цене x, B по цене y, всего куплю v фруктов". Каждый участник может сделать таких ставок сколько угодно. Ставки публичны. Каждую ставку можно изобразить на плоскости с координатами А-Б точкой (x,y) с весом v.

Когда прием ставок заканчивается, аукционер выбирает реальную стоимость продажи (x0,y0) апельсинов и бананов. Через некоторое время станет понятно, как он это делает. Допустим пока, что стоимость выбрана. Какой алгоритм выбора покупателей: 

1) Выкинем все ставки из прямоугольника (x<x0)&(y<y0). Это лузеры, которые не угадали.

2) Оставшуюся область разделим пополам прямой x-x0=y-y0. Если для данной ставки выполнено x-x0>y-y0, скажем, что этот чувак будет покупать только апельсины, а если y-y0>x-x0 - только бананы. Ну типа логично, если чувак установил цену на апельсины сильно выше, чем их реальная цена продажи (которую он, впрочем, не знает), то наверное апельсинов ему больше хочется...

3) Продаем бананы и апельсины по цене (x0,y0) в количестве указанном во всех отобранных ставках.

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

Алгоритм отбора покупателей, и что именно они будут покупать вроде нехитрый. Теперь как выбирается стоимость (x0,y0). А очень просто: на основании изначально озвученных ограничений аукционера. 

Допустим аукционер сказал, что продаст 1000 фруктов. Он посчитал сколько всего фруктов во всех ставках и получилось 5000 фруктов. Это значит, что в первом пункте алгоритма нужно отсечь ставок суммарно на 4000 фруктов. То есть аукционер подбирает (x0,y0) так, чтобы прямоугольник (x<x0)&(y<y0) содержал ставок ровно на 4000, ну или чуть больше. 

Заметим, что таких прямоугольников аж однопараметрическое семейство, что-то вроде угловатой гиперболы, см. скопипащенный рис. из статьи ??. Чтобы однозначно выбрать на этой кривой точку, надо вспомнить о нашей договоренности по соотношению А/Б. Утверждается, что найдется ровно одна точка, для которой выполнено требуемое соотношение. Это такое базовое упражнение на непрерывность, по типу теоремы о бутерброде с колбасой. Вот эту точку аукционер и берет в качестве (x0,y0).

*Точка, конечно, может быть не единственной. Но единственным будет выбор - кого отсекать, кому продавать апельсины, а кому бананы.

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

А причем тут тропическая геометрия? Да тупо при том, что линия, по которой аукционер разделяет лузеров, которые уйдут ни с чем, покупателей апельсинов и покупателей бананов - это тропическая прямая max(0, x-x0, y-y0), т.е. множество точек, где максимум принимается дважды.

Если бы фруктов было не 2, а n, то абсолютно аналогично можно было бы провести аукцион, используя в качестве критерия отбора разделение пространства R^n на (n+1) камеру тропической гиперплоскостью. 

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

E.Baldwin, P.Klemperer, Tropical geometry to analyse demand

тропическим матаном аж на 83 страницы обмазываются. Вдруг кому интересны подробности.