Геометрия
Тропическая геометрия
Цели урока
- Понять тропическое полукольцо (max, +) и тропические многочлены
- Освоить тропические кривые как кусочно-линейные графы с условием баланса
- Знать теорему Михалкина о соответствии тропических и алгебраических кривых
- Увидеть связь тропической геометрии с оптимизацией и алгоритмами
Предварительные знания
- Алгебраические кривые
- Перечислительная геометрия
Как одна и та же алгебра (max, +) связывает алгоритм Дейкстры, счёт алгебраических кривых и задачу Ферма?
- Динамическое программирование: алгоритм Беллмана-Форда - это матричное умножение над тропическим полукольцом (min, +)
- Кратчайшие пути: задача кратчайшего пути в графе = вычисление тропической степени матрицы смежности
- Статистическое обучение: тропическая геометрия применяется в анализе деревьев филогенеза (эволюционных деревьев) - расстояние Гилберта на пространстве деревьев
- Оптимизация: линейное программирование над вещественными числами = тропическая линейная алгебра над (min, +)
От полуколец к геометрии
Имре Симон в 1978 году систематизировал (min, +)-алгебру в контексте теории формальных языков. Максплюс-алгебра применялась в теории дискретных систем. Вирсма и Дезулей в 1990-х начали связывать тропическую алгебру с алгебраической геометрией. Термин 'тропическая' введён Симоном в честь математика Иммермана, работавшего в тропиках (Бразилии). Михалкин в 2003 году доказал теорему соответствия. Спейер и Штурмфельс в 2004 году систематизировали тропическую алгебраическую геометрию. Сейчас тропическая геометрия - активная область с применениями в биологии, экономике и информатике.
Тропическая алгебра и полукольцо
Оптимизация динамическим программированием, кратчайшие пути в графах, задача о назначениях - за всеми этими алгоритмами стоит одна алгебра. Тропическая. Замените умножение на сложение, сложение - на максимум. Алгоритм Дейкстры - это линейная алгебра над тропическим полукольцом.
Что является тропическим нулём многочлена f(x)?
Тропический многочлен f(x) = max(a_n+nx, ..., a_0) - кусочно-линейная функция. Тропические нули - точки излома, где максимум достигается на нескольких мономах одновременно.
Тропические кривые и политопы Ньютона
Тропическая кривая - это граф, вложенный в R^2, где каждое ребро - отрезок с рациональным наклоном. Не гладкая кривая, а кусочно-линейный скелет. Но за этим скелетом - вся геометрия алгебраических кривых, только в пикселях.
Тропическая прямая
Простейшая тропическая кривая
Тропическая прямая f = ax + by + c (тропически: max(a+x, b+y, c)) - это граф с тремя лучами: одним в направлении (-1,0), одним в (0,-1), одним в (1,1). Единственная вершина в точке (b-a, c-b) (при a=b=c=0: в начале координат). Любые две тропические прямые пересекаются ровно в одной точке - это тропическая аналогия теоремы Безу для d1=d2=1: 1*1=1.
Что такое тропическая прямая в R^2?
Тропическая прямая = V(max(x, y, 0)): три луча из одной вершины в направлениях (-1,0), (0,-1) и (1,1). Условие баланса: (-1,0)+(0,-1)+(1,1)=(0,0). Любые две тропические прямые пересекаются в одной точке.
Теорема Михалкина и счёт кривых
2003 год. Григорий Михалкин доказывает теорему соответствия. Число рациональных алгебраических кривых степени d через 3d-1 точек в P^2 равно числу тропических кривых той же степени и рода через те же 3d-1 точки в R^2 - с нужными множителями. Перечислительная геометрия стала комбинаторной.
N_1 = 1 тропически
Тропическая прямая через 2 точки
Тропическая прямая через 2 точки в R^2 в общем положении существует и единственна. Это тропическая версия N_1 = 1. Множитель = 1 (единственная прямая, единственное соответствие). Для N_3 = 12: есть 12 тропических кубических кривых рода 0 через 8 точек (с учётом множителей, каждый равный 1 в этом случае).
Алгоритм Михалкина: задаём 3d-1 точек в общем положении в R^2. Перебираем все тропические кривые степени d и рода 0, проходящие через них. Считаем с множителями. Получаем N_d. Алгоритм работает за конечное время - это конкретная комбинаторная процедура.
Что утверждает теорема Михалкина о соответствии?
Теорема Михалкина: N_d = sum тропических кривых deg d через 3d-1 точек * mult(Gamma). Комбинаторный счёт тропических кривых с множителями равен N_d. Это самый конкретный способ вычислить числа Гуро-Виттена.
Связи с другими темами
Тропическая геометрия соединяет алгебраическую геометрию с комбинаторикой и оптимизацией.
- Алгебраические кривые — Тропические кривые - комбинаторные тени алгебраических кривых при логарифмическом пределе
- Перечислительная геометрия — Тропическая геометрия даёт комбинаторные методы для инвариантов Громова-Виттена
- Арифметическая геометрия — Тропикализация многообразий над неархимедовыми полями - связь с арифметической геометрией
Итоги
- Тропическое полукольцо T: a oplus b = max(a,b), a odot b = a+b
- Тропический многочлен = кусочно-линейная функция; нули = изломы
- Тропическая кривая = граф в R^2 с условием баланса в вершинах
- Политоп Ньютона: выпуклая оболочка носителя; тропическая кривая = двойственный граф разбиения
- Теорема Михалкина: N_d = взвешенная сумма тропических кривых той же степени и рода
- Алгебра (min, +): алгоритм Дейкстры = тропическое матричное умножение
Вопросы для размышления
- Почему тропическая кривая - граф с целочисленными наклонами рёбер - а не произвольная кусочно-линейная кривая?
- Как условие баланса в вершинах тропической кривой аналогично теореме Безу для алгебраических кривых?
- Чем тропикализация похожа на 'скелетирование' алгебраической кривой, и что теряется при переходе к тропическому миру?
Связанные уроки
- geo-24 — Алгебраические кривые - объект тропификации
- geo-25 — Тропические кривые считают числа Гуро-Виттена
- geo-26 — Программа Гросса-Сиберта использует тропическую геометрию
- top-03 — Связность и компактность политопов Ньютона
- geo-28 — Арифметическая геометрия использует тропификацию над p-адическими полями