Хв-плюс многочлени, циклічні ігри і теорема Гільберта про нулях

У цій доповіді розглядаються алгоритмічні задачі, пов'язані з хв-плюс многочленами. Конкретніше — розв'язність систем лінійних хв-плюс многочленів. Ця задача виявляється полиномиально еквівалентної задачі про визначення переможця в так званих циклічних іграх (mean payoff games), відомої задачі, що лежить на перетині сложностных класів NP і coNP. Другий результат, який обговорюється в ході доповіді, це аналог теорема Гільберта про нулях хв-плюс алгебри.



Хв-плюс (або тропічним) півкільцем називається безліч раціональних чисел з двома операціями: хв-плюс складанням, яка є просто операція взяття мінімуму, і хв-плюс множенням, яке є звичайне додавання. Многочлени над хв-плюс півкільцем визначаються за аналогією з класичними многочленами. По суті, хв-плюс многочлен задає кусково-лінійну функцію від своїх змінних. Коренем многочлена називається точка негладкости цієї функції.

Доповідь був прочитаний на факультеті комп'ютерних наук, відкритому в НДУ ВШЕ за підтримки Яндекса. Лектор Володимир Подільський — старший науковий співробітник Математичного інституту ім. В. А. Стеклова. На ФКН читає лекції і веде семінари в рамках курсу «Дискретна математика». Доповідь заснований на спільних роботах з Дмитром Григор'євим.

Під катом — повна розшифровка лекції.

Що таке хв-плюс півкільце (або тропічне кільце)? У нас є безліч, є дві бінарні операції, безліч не довільна, а цілком конкретне (наприклад, дійсні, раціональні, цілі числа і т. д.; і можна розглядати все те ж саме з додаванням позитивної нескінченності). Роль додавання в цьому хв-плюс кільці грає звичайна операція мінімуму, а роль множення – звичайна операція додавання. Досить проста структура: вона по множенню група, а складання – півкільце (там немає зворотних елементів). І додавання нескінченності має сенс нуля за хв-плюс складання.

Будемо розглядати многочлени в цій алгебраїчної структури. Вони визначаються за аналогією зі звичайними многочленами, тобто можна визначити мономы за хв-плюс множенню (праворуч записані у звичайних термінах, тобто моном – це просто лінійна функція з цілими коефіцієнтами, інакше кажучи, і 1 і n будуть цілими). Позначати їх будемо так, як написано на слайді.

Многочлен – це просто сума кількох мономов. У звичайних позначеннях це мінімум від кожного Мі.
Ступінь монома визначається природним чином – сума ступенів усіх входять сюди змінних. Статечно многочлена – це ступінь максимального монома в ньому.

Що тут стає незвичайним порівняно з класичними многочленами – це визначення поняття кореня многочлена. Точка А є коренем, якщо при підстановці її в цей вираз мінімум досягається хоча б на двох різних мономах (або дорівнює нескінченності).

Розглянемо приклад. (Множення на нуль в даному випадку має сенс, тому що знак множення тут – насправді додавання.) Давайте спробуємо зрозуміти, які з цього многочлена коріння. Нам потрібно, щоб досягався мінімум на двох різних мономах. Можна поподбирать і зрозуміти, що коріння тут -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. І виявляється, що у неї є спільний корінь тоді і тільки тоді, коли є рішення у такої лінійної системи.

В принципі, це не складно зрозуміти. Тут написано ось що: ми взяли многочлени fі, поумножали їх на різні мономы, потім склали. Можна дивитися на многочлен як на вектор його коефіцієнтів. Коли ми множимо fі мономы, ми отримуємо різні рядки матриці 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 є рішення тоді і тільки тоді, коли є рішення у такий лінійної тропічної системи. І в одну сторону це просто: якщо у системи многочленів є рішення, то і у тропічній лінійної системи теж буде рішення. Треба згадати, що стовпці Сп матриці Macauley відповідають мономам в змінних Х. І якщо є якесь рішення для системи багаточленів Х, треба покласти уі рівним цьому самому моному, тоді у рядках матриці Macauley у нас просто будуть коефіцієнти многочлена f, домноженные на моном. І раз Х був рішенням многочлена f, то буде рішенням лінійних рівнянь, заданих цими рядками матриці Macauley.

В іншу сторону складніше. Треба зробити таке: нам відомо, що є якесь рішення у цієї системи, тобто існує якийсь вектор Y. Нам хотілося б виготовити з нього такий вектор, який буде мати таку форму, тобто буде відбуватися з деякого Х.

По-перше, корисно зафіксувати N=2, це весь змістовний випадок: як тільки доведено для двох, для великих n узагальнюється миттєво. У нас регулярно виникають вектора, координати яких пронумеровані парами цілих невід'ємних чисел. Наприклад, це коефіцієнти многочленів. По суті, вони пронумеровані мономами. Рядки матриці Macauley і вирішення її точно так само.

Можна подивитися на всі ці вектора, на всі ці об'єкти як на безліч точок в тривимірному просторі. Перші дві координати у нас відповідають координатами векторів, а третя координата відповідає значенням цих координат. Тоді у нас многочленам fі f буде відповідати множина точок Pfi – це безліч, відповідне їх коефіцієнтів. Коефіцієнти зображуємо множиною точок у тривимірному просторі. Рядками матриці Macauley теж відповідають якісь множини. По суті, це зрушення множин Pfi. Рішення матриці Macauley теж відповідає якомусь безлічі точок. При цьому рішення системи рівнянь насправді відповідає площинах у цьому тривимірному просторі.

Ми знаємо, що є рішення у матриці Macauley, а значить, є і рішення, яке є гіперплощиною. Зробимо заміну змінних від у к –у. І тоді у нас у всіх лінійних системах З+Yі заміниться на З-Yi. Тепер можна подивитися на отримане рівняння і зрозуміти, що взагалі тут написано. От є безліч точок Py, відповідне Y, безліч точок Р, відповідне А. Нехай Y – рішення для цього рівняння. І тоді що це означає? Давайте це отнормируем, тобто будемо рухати Py так, щоб він лежав строго нижче Ра. Це буде означати, що мінімум став дорівнює нулю. Тобто, якщо ми посунули Py так, що він лежить строго нижче Р, це означає, що у них буде хоча б дві спільні точки. Це і означає, що Y є рішенням для рівняння А.

Ми знаємо, що у нас є рішення Y для деякої лінійної системи, не так вже й важливо – який. Ми хочемо довести, що є рішення, яке є гіперплощиною. Розглянемо довільне рішення і будемо його як-то так міняти, щоб з цього вийшла гіперплощину. Не дуже зрозуміло, як це робити. Насправді ми знаходимо це рішення виходячи не з рішення Y, а з самої системи многочленів. Працює це приблизно так.

Беремо множини точок Pfi для всіх багаточленів, беремо опуклу оболонку кожного з них, беремо суму Мінковського цих багатогранників. Далі стверджується, що одна з граней суми Мінковського і буде цієї гіперплощиною.

Y дозволяє зрозуміти, яку грань Р потрібно вибрати. Насправді відбувається ось що: якщо ми візьмемо Pfi, опуклу оболонку, суму Мінковського – це лінійна комбінація рядків матриці Macauley. І тому якщо у нас є рішення Y, то воно повинно бути і рішенням для рядка, що відповідає цьому многограннику Р. Тоді, в якій грані це рішення торкнеться цього Р, та межа і правильна. Так це працює.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.