Мин-плюс многочлены, циклические игры и теорема Гильберта о нулях
В этом докладе рассматриваются алгоритмические задачи, связанные с мин-плюс многочленами. Конкретнее — разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP. Второй результат, который обсуждается в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры.
Мин-плюс (или тропическим) полукольцом называется множество рациональных чисел с двумя операциями: мин-плюс сложением, которая есть просто операция взятия минимума, и мин-плюс умножением, которое есть обычное сложение. Многочлены над мин-плюс полукольцом определяются по аналогии с классическими многочленами. По существу, мин-плюс многочлен задает кусочно-линейную функцию от своих переменных. Корнем многочлена называется точка негладкости этой функции.
Доклад был прочитан на факультете компьютерных наук, открытом в НИУ ВШЭ при поддержке Яндекса. Лектор Владимир Подольский — старший научный сотрудник Математического института им. В.А. Стеклова. На ФКН читает лекции и ведет семинары в рамках курса «Дискретная математика». Доклад основан на совместных работах с Дмитрием Григорьевым.
Под катом — полная расшифровка лекции.
Что такое мин-плюс полукольцо (или тропическое кольцо)? У нас есть множество, есть две бинарные операции, множество не произвольное, а вполне конкретное (например, действительные, рациональные, целые числа и т. д.; и можно рассматривать все то же самое с добавлением положительной бесконечности). Роль сложения в этом мин-плюс кольце играет обыкновенная операция минимума, а роль умножения — обыкновенная операция сложения. Довольно простая структура: она по умножению группа, а по сложению — полукольцо (там нет обратных элементов). И добавление бесконечности имеет смысл нуля по мин-плюс сложению.
Будем рассматривать многочлены в этой алгебраической структуре. Они определяются по аналогии с обычными многочленами, то есть можно определить мономы по мин-плюс умножению (справа записаны в обычных терминах, то есть моном — это просто линейная функция с целыми коэффициентами, иначе говоря, и 1, и n будут целыми). Обозначать их будем так, как написано на слайде.
Многочлен — это просто сумма нескольких мономов. В обычных обозначениях это минимум от каждого Мi.
Степень монома определяется естественным образом — сумма степеней всех входящих сюда переменных. Степенно многочлена — это степень максимального монома в нем.
Что здесь становится необычным по сравнению с классическими многочленами — это определение понятия корня многочлена. Точка А является корнем, если при подстановке ее в это выражение минимум достигается хотя бы на двух разных мономах (либо равен бесконечности).
Рассмотрим пример. (Умножение на ноль в данном случае имеет смысл, потому что знак умножения здесь — на самом деле сложение.) Давайте попробуем понять, какие у этого многочлена корни. Нам нужно, чтобы минимум достигался на двух разных мономах. Можно поподбирать и понять, что корни здесь -2 и 1.
Рассмотрим еще один пример. Здесь уже есть три переменных, и многочлен на самом деле линеен. Слева записан в мин-плюс терминах, справа — в обычных терминах. Многочлен линейный, то есть каждый моном в нем линейный, у него уже корней больше. Нужно заметить, что есть такой особенный корень (-1, -2, 1), в котором совпадают все три монома. И из него можно изготовить уже много других, а именно если к любой координате что-нибудь прибавить, то видно, что это все равно будет оставаться корнем. Ну и еще полезно заметить, что в данном случае если у нас есть какой-то корень и мы ко всем координатам прибавим одно и то же число, то это все равно останется корнем.
Наряду с такими тропическими многочленами можно рассматривать еще мин-плюс многочлены. Это вот такое равенство: слева и справа стоят суммы мономов, и степенно определяется так же, и корень определяется самым обычным образом. Точка А является корнем, если левая и правая части равны. Такой способ оправдан тем, что в мин-плюс кольце нет вычитания, поэтому разумно посмотреть на равенство многочлена нулю как на двустороннее равенство, где часть мономов слева, часть мономов справа.
Откуда это все в принципе возникает? Вариант мин-плюс многочленов возникает обычно из задач комбинаторной оптимизации и из задач теории расписаний. Рассмотрим какой-нибудь взвешенный граф, то есть такой, у которого есть веса на ребрах. Возьмем его матрицу смежности и, допустим, в мин-плюс смысле возведем его в квадрат. Тогда можно немного подумать и понять, что в ячейке такой матрицы будет написана длина кратчайшего пути длины 2 между этими двумя вершинами. Когда мы возводим эту матрицу в мин-плюс смысле в квадрат, то мы берем строку и столбец, умножаем ячейки в мин-плюс смысле, то есть складываем, потом берем минимум. Длина кратчайшего пути и возникает, длина 2. Если брать большие степени, то возникают кратчайшие пути большей длины. В принципе мин-плюс многочлен выглядит более естественно. На самом деле, наверно, сложнее понять, как получается такая странная формулировка, когда у нас есть многочлен и мы хотим, чтобы минимум достигался в двух мономах. Такая формулировка происходит в задачах алгебраической геометрии и других разделах математики.
Как может такая вещь возникать? Посмотрим на рациональные функции над комплексными числами. И давайте алгебраически замкнем это поле. В окрестности нуля такие функции можно представлять рядами Puiseux — такими бесконечными рядами. Степени здесь рациональные, и коэффициенты тоже.
d1 — это самая маленькая степень и называется порядком такого ряда. Теперь над этим полем рассмотрим какой-то многочлен от n переменных. Попробуем понять, что вообще может значить, что какая-то точка в этом поле рациональных функций является корнем такого многочлена от многих переменных. Это значит, что если мы ее туда подставим, то будет 0. Посмотрим, что происходит, когда мы подставляем все это дело в моном: порядки складываются. Когда мы перемножаем такие ряды, то порядки будут складываться. Потом мономы складываем. Если хотим, чтобы в итоге получился 0, необходимо, чтобы моном минимального порядка с чем-то сократился. Значит, их должно быть хотя бы два — минимальный порядок должен происходить хотя бы от двух разных мономов. Примерно так это обычно возникает. Если мы рассмотрим такие многочлены и посмотрим на их порядки и на аналогичные многочлены для их порядков, то окажется, что если у нас есть корень, то порядки этих a1, an должны удовлетворять аналогичному тропическому многочлену.
Классическое приложение науки о тропических многочленах — это задача о подсчете плоских алгебраических кривых.
Пусть у нас есть алгебраические кривые над комплексными числами. Тогда если мы какое-то количество точек зафиксируем и скажем: пусть алгебраическая кривая через них проходит, то таких алгебраических кривых будет не так много, какое-то конечное число. Например, если мы говорим о кривых степени 1, то это просто прямые, и если мы зафиксируем в одном положении две точки, то такая прямая будет ровно одна.
В общем случае рассмотрим кривые степени d. На самом деле еще рассматривают кривые, у которых есть двойные точки, то есть точки, через которые они проходят несколько раз. Зафиксируем также чем-то количество двойных точек. Дальше зафиксируем некое количество точек С на плоскости в общем положении. И если правильно подобрать С, то окажется, что количество кривых, которые проходят через эти точки данной степени и с данным количеством двойных точек, будет равно какой-то ненулевой константе. Если взять С слишком маленьким, то их будет бесконечность, если взять слишком большим — то ноль.
Рассмотрим пример. Кривые степени 2 и с одной двойной точкой. Кривые степени 2 — это эллипсы, параболы, гиперболы. Как у такой кривой степени 2 может быть двойная точка? Значит, это пересечение двух прямых. Сколько здесь всего параметров? Коэффициентов формально шесть, но все их можно умножить на одну константу, на самом деле степеней свободы пять. То, что есть двойная точка, уменьшает это все на единицу, остается четыре степени свободы. Если мы возьмем четыре точки в общем положении, то сколькими способами можно провести через них пару пересекающихся прямых? Если возьмем четырехугольник, то таких пар пересекающихся прямых будет три.
Есть задача о том, чтобы находить, чему равно это число, и решается она переходом к таким тропическим многочленам.
План решения: полезно доказать, что число m, которое мы ищем, то есть число таких кривых, не зависит от точек.
Дальше можно взять точки вот такого вида (точка комплексная, t — действительное число, х/, у/ — тоже действительное, вся комплексность сидит в φ и ψ). А после этого t устремить к бесконечности. Аналогично тому, как было на паре предшествующих слайдов, оказывается, что возникает тропический многочлен от переменных х/, у/, и если понять, сколько решений у него, то мы получим количество вот таких кривых. Решение тропического многочлена получается проще, чем решение изначальной задачи, потому что тропические многочлены простые, там можно что-то рисовать, это уже скорее комбинаторная задача, ее можно делать в том числе алгоритмически.
Давайте называть тропическим линейным многочленом вот такое выражение. В обычных терминах — вот такой минимум. Здесь, по сравнению с общим случаем, всякая переменная обязательно должна входить. Если нет бесконечности, то она входит по существу. Опять же он к тому же еще однородный. Нас интересует корень, который не бесконечность. Аналогично можно рассмотреть линейный мин-плюс многочлен. Самый обычный вопрос для обычных многочленов — это вопрос о разрешимости линейных систем.
Будем рассматривать системы таких многочленов. Для мин-плюс многочленов тоже.
Можно посмотреть на задачу разрешимости. Дана система многочленов, и хочется по ней понять, разрешима она или нет. В классическом случае эта задача полиномиально разрешима, и оказывается, что здесь полиномиальный алгоритм неизвестен. Мы знаем, что она лежит и в классе NP, и в классе coNP.
Есть задача, на которую есть ответы «да» и «нет», в нашем случае — задача разрешимости. Задача лежит в классе NP, если для каждого данного входа есть короткое доказательство, по которому можно за полиномиальное время убедиться, что ответ задачи «да». Задача лежит в coNP, если то же самое для ответа «нет».
Нам хотелось бы, чтобы задача лежала в P, то есть по системе сразу можно было бы сказать, разрешима она или нет. Но вместо этого мы знаем другое: если нам дали такую систему, то мы знаем, что можно придумать такое короткое доказательство, что оно существует, которое за полиномиальное время можно проверить. Доказательство того, что система либо разрешима, либо неразрешима.
Слайд № 13
Коллекция задач, которые лежат на NP, пересеченном с coNP. Некоторые из них лежат еще и в Р.
- Задача линейного программирования: нам дана система обычных линейных неравенств, и нас интересует, есть ли решение. Задача лежит в NP. Простым доказательством того, что есть решение, является само это решение. Нам могут просто дать решение, и мы можем легко подставить и проверить за полиномиальное время, что это действительно решение, а значит, система разрешима. Задача при этом лежит в coNP — это можно понять из двойственности. Для линейной системы есть двойственная: у первой системы есть решение только тогда, когда у второй его нет. Поэтому, для того чтобы доказать, что у системы нет решения, надо предъявить решение для двойственной.
- Задача о проверке числа на простоту: дано простое число, и нам хочется понять, является ли оно простым. Тоже находится в coNP, давно было известно, что она в NP, пересеченном с coNP. Здесь легко предъявить доказательство того, что число не простое, достаточно просто предъявить его разложение на множители, ну или просто два множителя. Сложнее объяснить, как доказывать, что данное число является простым, доказывать так, чтобы это можно было проверить.
- Есть серия задач, которые формулируются как игры. Задачи состоят в том, кто выигрывает. Лежит в NP, пересеченном с coNP.
- Есть задача о проверке квадратичности вычета. То есть дано число, дан вычет по модулю этого числа, и надо понять, квадратичен он или нет. Лежит в NP, пересеченном с coNP.
- Задача о приближении кратчайшего вектора в целочисленной решетке: дана целочисленная решетка с базисом, и нам нужно найти в ней кратчайший вектор. Если нас интересует не сам кратчайший вектор, а приближение к нему с нужными параметрами, то задача тоже попадает в NP, пересеченном с coNP.
- Задача о разрешимости мин-плюс линейных систем.
- И задача о разрешимости тропических линейных систем.
Оказывается, что на самом деле некоторые из этих задач являются одной и той же задачей. То есть они эквивалентны друг другу.
Игры введены в 1979 и 1988 годах. Игра устроена так: у нас есть два игрока, Алиса и Боб, и они двигают какую-то фишку по двудольному графу. В двудольном графе на ребрах написаны числа. Цель Алисы состоит в том, чтобы максимизировать сумму чисел на ребрах, по которым проходит фишка. Боб старается ее минимизировать. Конкретная игра — это последовательность вершин, в которых побывала эта фишка. Значением игры называется усредненное число на ребре — то есть берем t шагов, складываем все числа, которые были на ребрах, по которым прошли, делим на t. Дальше берем предел. В данной конкретной игре можно посмотреть, как выгодно играть игрокам и кто конкретно выигрывает. Что будет, если Алиса пойдет наверх? Боб тут же вернет фишку обратно, то есть суммарно будет значение 1, Бобу это выгодно, поэтому Алисе особого смысла так делать нет. Она по итогам двух ходов возвращается в исходное положение и при этом теряет 1. Поэтому посмотрим, что будет при другом варианте. Она пошла по 0, у Боба теперь есть варианты налево и налево и вниз. Если он пойдет налево и вниз, то у Алисы будет один ход, единственный, и она может пойти только обратно, и по итогам этих двух ходов Боб проиграл бы два. Ему это невыгодно, поэтому так делать не стоит.
Посмотрим, что будет, если он пойдет строго налево. Тогда у Алисы единственный ход, снова они вернулись в ту же точку, снова Алиса приобрела 1. Таким образом, в любом случае здесь все-таки выигрывает Алиса. Ей нужно сначала ходить сюда (2), а потом отвечать своими единственными ходами, и каждые четыре хода она будет выигрывать по 1. Это наилучший для Боба случай, но все равно по итогам она будет накапливать выигрыш.
Алиса выигрывает, если значение игры положительно, а Боб — наоборот. Известно, что у одного из игроков всегда есть выигрышная стратегия. И также известно, что есть позиционная выигрышная стратегия, что в общем-то интуитивно очевидно. Позиционная стратегия — это когда ход игрока зависит только от того, где сейчас находится фишка. Довольно очевидно, что ход не должен зависеть от того, как они раньше ходили.
Так определяются эти игры. Проблема, с ними связанная, — понять, кто выигрывает (вернее даже понять, выигрывает ли Алиса, чтобы ответ был «да»). Эта проблема в NP, потому что если в качестве сертификата дать выигрышную стратегию Алисы, то на самом деле нетрудно проверить, действительно ли эта стратегия является выигрышной. Эта же задача лежит в coNP, потому что сертификатом того, что Боб не проигрывает, будет его стратегия. Если дать стратегию Боба, то можно за полиномиальное время проверить, что, как бы Алиса ни играла, выиграть она не сможет.
Теперь рассмотрим чуть большую задачу, чем задача разрешимости. Также посмотрим на еще две задачи.
- Задача эквивалентности систем. То есть даны две тропические системы, и нужно понять, эквивалентны ли они.
- Задача размерности. На самом деле нужно понять вот что: решение линейного тропического уравнения — это объединение нескольких многогранников, возможно бесконечное. Если мы возьмем их несколько и возьмем систему их, то будет пересечение таких вот объединений многогранников и это все равно объединение нескольких многогранников. Размерность здесь можно корректно определить. То есть если у нас есть какая-то система тропических многочленов, то можно посмотреть на ее решение, найти многогранник максимальной разности и это и назвать размерностью пространства решений.
Задача: дана матрица и дано число, нужно понять, верно ли, что размерность не меньше, чем это число.
Все эти задачи рассматриваются не только на Z, можно рассматривать их на Z с добавлением бесконечности. И все они в классическом случае полиномиально разрешимы.
А в тропическом случае оказывается, что нет. В таблице собраны все результаты. Есть тропический случай, есть мин-плюс случай, три задачи — о разрешимости, эквивалентности и размерности. Оказывается, что задача размерности в тропическом случае просто NP-полна. Есть разные ссылки. Когда стоят две ссылки, это значит, что в первой работе доказывается этот результат над Z, а во второй — над Z∞. Есть существенная разница — если есть бесконечность, то доказывать менее приятно и существенно сложнее. Таким образом, в частности, получается, что все эти задачи эквивалентны друг другу и неважно про какую из них пытаться доказывать, что она лежит в P.
Как на эту картинку можно смотреть? Есть такая старая задача — Mean Payoff Games. И она пока не решена. Мы доказываем, что есть довольно новые задачи, которые ей эквивалентны. Некоторые из них формулируются в неких алгебраических терминах, в некоторой алгебраической структуре. Вот задача о разрешимости систем тропических линейных уравнений. Вполне себе такая задача в некой алгебраической структуре, мы таким образом переформулировали задачу и циклических играх вот в таких новых терминах. И можно надеяться, что удастся развивать науку о тропических многочленах, и, когда она разовьется, окажется, что там мы уже научимся доказывать, что линейные системы можно решать за полиномиальное время.
Что вообще известно в алгебраической теории про тропические многочлены? В линейном случае кое-что известно.
Есть разные аналоги ранга матриц в тропической алгебре. Их на самом деле довольно много, у них есть разный смысл, между ними есть разные неравенства, но тем не менее что-то там изучено и что-то известно. Есть аналог определителя матрицы, и у него там есть тоже хорошие свойства, он тоже связан как-то с линейными системами.
Есть аналог гауссовской треугольной формы матрицы.
В общем случае для произвольных многочленов известно существенно меньше. Есть некоторые работы по изучению радикала, но вот особенно никаких продвижений не видно. Задача разрешимости NP-полна. Система многочленов произвольная, без ограничений на степени. На самом деле многочлены в степени 2. Если у нас дана система тропических многочленов в степени 2, то задача о ее разрешимости NP-полна.
В классическом случае задача уже неразрешима.
Что предлагается делать? В классической алгебре есть очень важный результат теоремы Гильберта о нулях.
Расскажем об аналоге этой теоремы в тропическом случае. Здесь слабая форма теоремы Гильберта о нулях. Эта теорема говорит вот о чем: пусть у нас есть система классических многочленов, и нам хотелось бы понять, что у нее нет решения. Эта теорема говорит, что означает конструктивно, что у системы многочленов нет решений. Оказывается, что у системы многочленов нет общего решения, если есть их алгебраическая комбинация, которая равна тождественно 1. То есть просто многочлен константа 1 выражается как алгебраическая комбинация наших. И есть такой результат, что у системы многочленов нет решения тогда и только тогда, когда есть такая алгебраическая комбинация. В эффективном варианте можно оценить степени этих многочленов g1, gk, можно сказать, что наибольшая степень этих произведений здесь не больше, чем 2dmin (n, k).
Если попытаться просто наивно сформулировать аналог тропических многочленов, то ничего не получится. По той же причине, что нет вычитания. Даже если мы напишем просто два вот таких многочлена, у них общих корней нет. Как бы мы ни старались, какую бы алгебраическую комбинацию ни брали, ноль или единицу, мы в любом случае не получим, потому что вот этот Х ни с чем не сократится. Просто не предусмотрено такой возможности.
Чтобы сформулировать аналог теоремы Гильберта о нулях, нам придется и саму классическую версию немного переформулировать.
Для этого нам придется рассмотреть такую матрицу Macauley. Давайте рассмотрим систему многочленов и вот такую матрицу. N — это некоторый параметр, число. Ее столбцы помечены мономами, степень не больше N, строки помечены многочленами из нашей системы, умноженными на мономы. И тоже степени не больше N. В ячейке матрицы написан коэффициент монома в этом многочлене.
Пример: f1=1+x, f2=2+y, N=2.
Получаются такие строчки, то есть каждый из этих многочленов мы можем множить на какую-то из переменных.
Это на самом деле обобщение матрицы Сильвестра на произвольную систему многочленов.
Сформулируем теорему Гильберта о нулях в двойственной форме. На слайде — сначала в обычной, а потом уже в двойственной. У нас есть система многочленов, переменных n, степень d. И оказывается, что у нее есть общий корень тогда и только тогда, когда есть решение у такой линейной системы.
В принципе, это не сложно понять. Здесь написано вот что: мы взяли многочлены fi, поумножали их на разные мономы, потом сложили. Можно смотреть на многочлен как на вектор его коэффициентов. Когда мы умножаем fi на мономы, мы получаем разные строчки матрицы Macauley. И когда мы их складываем, мы берем линейную комбинацию строчек матрицы Macauley. И мы хотим в конце концов получить единицу. То есть тот факт, что у этой системы есть решение, означает, что нет линейной комбинации строчек матрицы Macauley, которая равна вектору (1,0, …). Это означает, что вектор (1,0, …) не лежит в линейной оболочке строчек нашей матрицы. Значит, можно подобрать вектор, который будет ортогонален всем строчкам нашей матрицы и не будет ортогонален вектору (1,0, …).
Определим матрицу Macauley в тропическом варианте. Она определяется точно так же: у нас есть система многочленов, точно так же столбцы занумерованы мономами, точно так же строчки занумерованы многочленами, умноженными на моном, и в ячейках написано то же самое. Когда монома нет, роль нуля играет бесконечность. Нас интересует тропическая линейная система с матрицей Macauley. При этом нас будут интересовать такие решения, чтобы у1 был не 0, то есть не бесконечность.
Можно сформулировать аналог теоремы Гильберта о нулях в двойственной форме для тропических многочленов. Здесь формулировка точно такая же: система имеет решение тогда и только тогда, когда линейная система с матрицей Macauley имеет решение. Также теорема была доказана, когда переменная одна. Общий случай сформулирован в виде гипотезы.
Теорема о том, что на самом деле это верно. Давайте рассмотрим систему тропических многочленов, через di обозначим их степени, через в — максимальную степень. Окажется, что система имеет решение тогда и только тогда, когда матрица Macauley тоже имеет решение. В качестве N можно взять вот что.
В случае когда у нас нет бесконечности, N — это такая вот штука, можно оценить как N, умноженное на d, умноженное на k.
Когда бесконечность есть, это более сложная штука — это многочлен от n, k (см. слайд). Обе эти оценки до какой-то степени точные. На самом деле это один из тех редких примеров, когда оказывается по существу важным, есть бесконечность или нет.
Есть такой же аналог этой теоремы для мин-плюс случая. Матрицу Macauley можно точно так же определить для мин-плюс случая, теперь их будет две, и нас уже будет интересовать вот такая система, двухсторонняя, мин-плюс линейная система.
Точно так же можно сформулировать аналог теоремы Гильберта о нулях в двойственной форме: у системы мин-плюс многочленов есть решение тогда и только тогда, когда у такой линейной системы с матрицами Macauley (в качестве n нужно брать то же самое, что и раньше).
Изначально эта теорема была двойственной формы — то есть если что-то решения не имеет, то оно имеет что-то другое. Здесь эта теорема такой вид не имеет. Они говорят, что если есть решение, то тогда и там есть решение. Если тут нет решения, то тогда и там нет. Это все-таки не двойственный результат.
Результат двойственного вида тоже удается получить, и выглядит он примерно так. Есть система мин-плюс многочленов, обозначили степени d. Можно сказать, что система имеет решение тогда и только тогда, когда можно собрать такую тропическую алгебраическую комбинацию наших многочленов, что у всякого монома коэффициент слева будет больше коэффициента справа.
Пусть есть система тропических многочленов. И тропических мономов тоже. Рассмотрим алгебраическую комбинацию g. Она устроена так: мы умножили многочлены из f на мономы, а потом все это сложили. И такая алгебраическая комбинация называется невырожденной, если происходит следующее:
- для всякого монома из g есть такой единственный gj, есть такой номер l (M), что коэффициент этого монома в этом gl (M) меньше всех остальных слагаемых,
- надо еще, чтобы для разных мономов эти места были разные.
Пример. Рассмотрим два таких многочлена. И сложим их вот с такими коэффициентами. Это мономы нулевой степени, но они все равно мономы. Сложим, получится такое выражение. И можно увидеть, что у монома константного в левой части коэффициент 0, в правой части коэффициент ½, в левой части он меньше, и это вот такое место, где он меньше. У монома степени 1 справа коэффициент ½, слева коэффициент 0. Теперь справа он меньше, и это единственное место, где он меньше. То есть у этих двух мономов минимум в разных местах. Таким образом, для этих многочленов мы можем построить невырожденную алгебраическую комбинацию.
Оказывается, что существование такой невырожденной алгебраической комбинации — это и есть критерий того, что у системы нет решения. В присутствии бесконечности недостаточно, чтобы просто была невырожденная алгебраическая комбинация, нужно еще, чтобы константный моном был конечен. Иначе в этой алгебраической комбинации будет решение.
Это определение невырожденной алгебраической комбинации хоть и сложное, но проверяемое.
Как связаны между собой тропические и мин-плюс многочлены? Оказывается, что в одну сторону они связаны очень просто: если у нас есть система тропических многочленов, то по ней всегда можно построить систему мин-плюс многочленов с теми же самыми переменными и с тем же самым множеством решений. В обратную сторону такого простого сведения нет. Но оно все равно есть: если у нас есть система мин-плюс многочленов, то можно построить другую тропическую систему многочленов, у которой переменных будет в два раза больше, и при этом можно вложить линейное пространство Qn в линейное пространство Q2n так, что все решения f вложатся ровно в точности во все решения t.
То есть множество решений системы f было неким подмножеством в n-мерном пространстве, а у t множество решений — это какое-то подмножество в 2n-мерном пространстве. Тем не менее можно просто биективно вложить одни решения в другие, они просто друг другу соответствуют.
Эти два соответствия позволяют довольно быстро переходить от мин-плюс многочленов к тропическим многочленам. В тех результатах, которые были перечислены, как только доказана теорема для одного случая, ее сразу можно перевести и для второго типа многочленов.
Как устроено доказательство последней серии результатов? Сначала есть тропическая теорема о нулях в двойственной форме. Она там доказывается геометрически. Все основное содержание второй части на самом деле сидит в этой теореме. Из нее уже не очень сложно перейти к мин-плюс случаю и получить вот такую теорему.
Как осуществляется переход к теореме вне двойственной форме? На самом деле здесь можно воспользоваться линейной двойственностью для тропических линейных систем. Оказывается, что для них тоже можно выписать в простой и понятной форме линейную двойственность и, получив результат, воспользоваться двойственностью для вот этой линейной системы (№ 39), проинтерпретировать двойственную систему в терминах алгебраических комбинаций, и получится вот это (№ 40). Потом из этой теоремы можно, опять же с помощью системы перехода от мин-плюс систем к тропическим, получить (№ 43) тропическую систему вне двойственной формы.
Идея геометрического доказательства теоремы двойственной формы. У системы многочленов на Q есть решение тогда и только тогда, когда есть решение у вот такой линейной тропической системы. И в одну сторону это просто: если у системы многочленов есть решение, то и у тропической линейной системы тоже будет решение. Надо вспомнить, что столбцы Сn матрицы Macauley соответствуют мономам в переменных Х. И если есть какое-то решение для системы многочленов Х, надо положить уi равным этому самому моному, тогда в строчках матрицы Macauley у нас просто будут коэффициенты многочлена f, домноженные на моном. И раз Х был решением многочлена f, то у будет решением линейных уравнений, заданных этими строчками матрицы Macauley.
В другую сторону сложнее. Надо сделать следующее: нам известно, что есть какое-то решение у этой системы, то есть существует какой-то вектор Y. Нам хотелось бы изготовить из него такой вектор, который будет иметь такую вот форму, то есть как бы будет происходить из некоторого Х.
Во-первых, полезно зафиксировать N=2, это весь содержательный случай: как только доказано для двух, для больших n обобщается мгновенно. У нас регулярно возникают вектора, координаты которых занумерованы парами целых неотрицательных чисел. Например, это коэффициенты многочленов. По сути, они занумерованы мономами. Строчки матрицы Macauley и решение ее точно так же.
Можно посмотреть на все эти вектора, на все эти объекты как на множество точек в трехмерном пространстве. Первые две координаты у нас соответствуют координатам векторов, а третья координата соответствует значениям этих координат. Тогда у нас многочленам fi из f будет соответствовать множество точек Pfi — это множество, соответствующее их коэффициентам. Коэффициенты изображаем множеством точек в трехмерном пространстве. Строчкам матрицы Macauley тоже соответствуют какие-то множества. По существу, это сдвиги множеств Pfi. Решение матрицы Macauley тоже соответствует какому-то множеству точек. При этом решение системы уравнений на самом деле соответствует плоскостям в этом трехмерном пространстве.
Мы знаем, что есть решение у матрицы Macauley, а значит, есть и решение, которое является гиперплоскостью. Сделаем замену переменных от у к –у. И тогда у нас во всех линейных системах С+Yi заменится на С-Yi. Теперь можно посмотреть на получившееся уравнение и понять, что вообще здесь написано. Вот есть множество точек Py, соответствующее Y, множество точек Ра, соответствующее А. Пусть Y — решение для этого уравнения. И тогда что это значит? Давайте это отнормируем, то есть будем двигать Py так, чтобы он лежал строго ниже Ра. Это будет означать, что минимум стал равен нулю. То есть, если мы подвинули Py так, что он лежит строго ниже Ра, это значит, что у них будет хотя бы две общие точки. Это и означает, что Y является решением для уравнения А.
Мы знаем, что у нас есть решение Y для некой линейной системы, не так уж и важно — какой. Мы хотим доказать, что есть решение, которое является гиперплоскостью. Рассмотрим произвольное решение и будем его как-то так менять, чтобы из этого получилась гиперплоскость. Не очень ясно, как это делать. На самом деле мы находим это решение исходя не из решения Y, а из самой системы многочленов. Работает это примерно так.
Берем множества точек Pfi для всех многочленов, берем выпуклую оболочку каждого из них, берем сумму Минковского этих многогранников. Дальше утверждается, что одна из граней суммы Минковского и будет этой гиперплоскостью.
Y позволяет понять, какую грань Р нужно выбрать. На самом деле происходит вот что: если мы возьмем Pfi, выпуклую оболочку, сумму Минковского — это линейная комбинация строчек матрицы Macauley. И поэтому если у нас есть решение Y, то оно должно быть и решением для строчки, соответствующей этому многограннику Р. Тогда, в какой грани это решение коснется этого Р, та грань и правильная. Так это работает.
