最小プラス多項式、巡回ゲーム、およびヒルベルトのゼロ定理

このレポートでは、min-plus多項式に関連するアルゴリズムの問​​題について説明します。 より具体的には、線形最小プラス多項式システムの可解性。 この問題は、複雑なクラスNPとcoNPの交差点にあるよく知られた問題である、いわゆる循環ゲーム（平均ペイオフゲーム）で勝者を決定する問題と多項式的に同等であることが判明しました。 レポートで説明されている2番目の結果は、最小プラス代数のヒルベルトのゼロ定理に類似しています。







最小プラス（または熱帯）半環は、2つの演算を伴う有理数のセットです。最小加算とは、最小を取る演算であり、最小加算と乗算は通常の加算です。 最小プラス半環上の多項式は、古典的な多項式との類推によって定義されます。 基本的に、min-plus多項式は、変数の区分的線形関数を定義します。 多項式の根は、この関数の滑らかでない点です。



レポートはYandexの支援を受けて経済学部で開かれたコンピューターサイエンス学部で読まれました。 ウラジミール・ポドルスキー講師-数学研究所主任研究員。 V.A. ステクロフ。 彼はFCSで講義を行い、離散数学コースの一部としてセミナーを実施しています。 レポートは、 Dmitry Grigoryevとの共同研究に基づいています。



カットの下-講義の完全なトランスクリプト。



ミニプラスハーフリング（またはトロピカルリング）とは何ですか？ セットがあり、2つの2項演算があります。セットはarbitrary意的ではありませんが、非常に具体的です（たとえば、実数、有理数、整数など。正の無限大を追加して同じことを検討できます）。 このmin-plusリングでの加算の役割は、最小の通常の演算によって行われ、乗算の役割は、加算の通常の演算によって行われます。 かなり単純な構造：乗算と加算による半環のグループです（逆要素はありません）。 また、無限大を追加すると、最小プラス加算でゼロの意味があります。



この代数構造の多項式を考えます。 それらは、通常の多項式との類推によって決定されます。つまり、min-plus乗算によって単項式を決定することができます（通常の用語で右に書かれています。つまり、単項式は整数係数を持つ単なる線形関数です、つまり、1とnは整数になります）。 スライドに記載されているとおりに指定します。



多項式は、単純にいくつかの単項式の合計です。 従来の表記法では、これは各M _iの最小値です。

単項式の次数は自然な方法で決定されます-ここに含まれるすべての変数の次数の合計。 べき多項式は、その中での最大単項式の次数です。



ここで古典的な多項式と比較して異常になるのは、多項式の根の概念の定義です。 この式に代入することにより、少なくとも2つの異なる単項式（または無限大に等しい）で最小値に達する場合、ポイントAはルートです。



例を考えてみましょう。 （この場合のゼロによる乗算は、ここでの乗算記号は実際には加算であるため、意味があります。）この多項式の根が何であるかを理解してみましょう。 2つの異なる単項式で最小値に到達する必要があります。 根が-2と1であることを理解できます。



別の例を考えてみましょう。 ここにはすでに3つの変数があり、多項式は実際には線形です。 左側にmin-plusの用語で、右側に-通常の用語で書かれています。 多項式は線形です。つまり、多項式の各単項式は線形であり、すでに多くの根を持っています。 3つの単項式すべてが一致する特別なルート（-1、-2、1）があることに注意してください。 そして、そこからすでに多くの他のものを作成することができます。つまり、座標に何かを追加した場合、これが依然としてルートのままであることは明らかです。 また、この場合、何らかのルートがあり、すべての座標に同じ番号を追加すると、これがルートのままになることに注意してください。



このような熱帯多項式に加えて、最小プラス多項式も検討できます。 これはそのような平等です。単項式の合計は左右であり、同じ方法で強力に決定され、根は最も一般的な方法で決定されます。 左右が等しい場合、ポイントAはルートです。 この方法は、最小プラスリングに減算がないという事実によって正当化されます。そのため、ゼロに等しい多項式を両側等式と見なすのが妥当です。ここで、単項式の一部は左側にあり、一部は右側にあります。



これはどこから来たのですか？ 多項式のmin-plusバリアントは通常、組み合わせ最適化問題とスケジューリング理論問題から発生します。 いくつかの重み付きグラフ、つまり、エッジに重みがあるグラフを検討してください。 その隣接行列を取り、たとえば、最小プラスの意味で、それを二乗します。 次に、少し考えて、このような行列のセルに、これら2つの頂点間の長さ2の最短パスの長さが書き込まれることを理解できます。 この行列を最小プラスの意味で二乗する場合、行と列を取り、最小プラスの意味でセルを乗算します。つまり、加算し、最小を取ります。 最短経路の長さ、長さ2が生じます。大きな角度をとると、より長い最短経路が生じます。 原則として、min-plus多項式はより自然に見えます。 実際、多項式があり、2つの単項式で最小値を達成する場合、このような奇妙な定式化がどのように得られるかを理解することはおそらく困難です。 そのような定式化は、代数幾何学や数学の他の分野の問題で起こります。



どうしてそんなことが起こるのでしょうか？ 複素数上の有理関数を見てみましょう。 そして、このフィールドを代数的に閉じましょう。 ゼロの近傍では、そのような関数はピュイセの行-無限の行で表すことができます。 次数は合理的であり、係数も同様です。



d ₁は最小の次数であり、そのような系列の順序と呼ばれます。 ここで、このフィールド上で、n変数の多項式を検討します。 有理関数のこの分野のある点が多くの変数のそのような多項式の根であることを一般的に意味するものを理解しようとしましょう。 つまり、そこで代入すると0になります。モノラルですべてを代入するとどうなるか見てみましょう。注文が追加されます。 このようなシリーズを乗算すると、注文が合計されます。 次に、単項式を追加します。 結果を0にしたい場合、最小次数の単項式を何かで減らす必要があります。 これは、それらの少なくとも2つがなければならないことを意味します-最小次数は、少なくとも2つの異なる単項式から来なければなりません。 このような何かが通常発生します。 そのような多項式を検討し、それらの次数とそれらの次数の同様の多項式を見ると、根がある場合、これらのa1の次数は同様の熱帯多項式を満たさなければなりません。



熱帯多項式の科学の古典的な応用は、平面代数曲線を数える問題です。

複素数上の代数曲線があると仮定します。 次に、特定の数の点を固定して、代数曲線がそれらを通過するようにすると、そのような代数曲線はそれほど多くなく、有限の数になります。 たとえば、1次の曲線について話している場合、これらは単なる直線であり、2つのポイントを1つの位置に固定すると、そのような直線は正確に1つになります。



一般的な場合、次数dの曲線を考慮します。 実際、二重のポイント、つまり、複数回通過するポイントを持つ曲線は、まだ考慮されています。 ダブルポイントの数も修正します。 次に、平面上の特定の数の点Cを一般的な位置に固定します。 また、Cを正しく選択すると、これらのポイントを所定の次数で通過し、特定の数の二重ポイントで通過する曲線の数が、ゼロ以外の定数に等しくなることがわかります。 Cを小さくしすぎると無限大になり、大きすぎるとゼロになります。



例を考えてみましょう。 次数2の曲線と1つの二重点。 次数2の曲線は、楕円、放物線、双曲線です。 次数2のこのような曲線はどのように二重点を持つことができますか これが2本の線の交差点です。 パラメーターはいくつありますか？ 正式には6つの係数がありますが、それらのすべてに1つの定数を掛けることができ、実際には5つの自由度があります。 二重点があるという事実は、これをすべて1つ減らします; 4つの自由度が残ります。 一般的な位置で4つのポイントを取得する場合、それらを通るペアの交差する線をいくつの方法で描画できますか？ 四角形をとると、このような交差する線のペアが3つあります。



この数が何に等しいかを見つけることには問題があり、それはそのような熱帯多項式に行くことによって解決されます。



解決策：探しているmの数、つまりそのような曲線の数がポイントに依存しないことを証明することは有用です。

次に、この種の点を取ります（複素数点、tは実数、x /、y /も実数、すべての複雑さはφとψにあります）。 そしてその後、無限に突進します。 前のスライドのペアで起こったことと同様に、変数x /、y /から熱帯多項式が生じることがわかります。そして、それが持つ解の数を理解すれば、そのような曲線の数が得られます。 熱帯多項式の解は、元の問題の解よりも単純です。なぜなら、熱帯多項式は単純で、そこに何かを描くことができるからです。これは、アルゴリズムを含めて、より多くの組み合わせ作業です。



この熱帯線形多項式をそのような式と呼びましょう。 通常、これはそのような最小値です。 ここでは、一般的な場合と比較して、すべての変数を含める必要があります。 無限がない場合は、本質的に入ります。 繰り返しますが、これもまた均質です。 無限ではないルートに興味があります。 同様に、線形の最小プラス多項式を考慮することができます。 通常の多項式の最も一般的な問題は、線形システムの可解性の問題です。



このような多項式のシステムを検討します。 最小プラス多項式の場合も。



可解性の問題を見ることができます。 多項式系が与えられ、それからそれが解けるかどうかを理解したい。 古典的な場合、この問題は多項式的に解くことができ、多項式アルゴリズムはここでは不明です。 NPクラスとcoNPクラスの両方にあることがわかっています。



私たちの場合、「はい」と「いいえ」という答えがある問題があります-解決可能性の問題です。 与えられた各入力に対して、問題への答えが「はい」であることを多項式時間で検証できる短い証明がある場合、問題はクラスNPにあります。 「いいえ」という答えも同じであれば、タスクはcoNPにあります。

タスクがPにあることを望みます。つまり、システムはそれが解決可能かどうかをすぐに判断できます。 しかし、代わりに、私たちは何か他のことを知っています。そのようなシステムが与えられた場合、多項式時間で検証できるような存在するという短い証明を思いつくことができることを知っています。 システムが決定可能または解決不可能であることの証明。



スライド番号13

NPにあるタスクのコレクションがcoNPと交差しました。 それらのいくつかはRにもあります。

• 線形計画法のタスク：通常の線形不等式のシステムが与えられ、解決策があるかどうかに興味があります。 タスクはNPにあります。 解決策があるという単純な証拠は、解決策そのものです。 彼らは単純に解決策を与えることができ、これが本当に解決策であることを多項式時間で簡単に置き換えて検証することができます。これは、システムが解けることを意味します。 課題はcoNPにあります-これは二重性から理解できます。 線形システムの場合、デュアルがあります。最初のシステムには2番目のシステムにはない場合にのみ解決策があります。 したがって、システムに解決策がないことを証明するには、デュアルの解決策を提示する必要があります。
• 簡単にするために番号をチェックするタスク：素数が与えられ、それが素数であるかどうかを理解したいと思います。 また、coNPにも含まれており、NPがcoNPと交差していることが長い間知られています。 ここでは、数が素数ではないことを証明するのは簡単です。その因数分解を示すだけで、または2つの要素だけを示します。 与えられた数が素数であることを証明する方法を説明し、検証できるように証明することはより困難です。
• ゲームとして定式化された一連のタスクがあります。 誰が勝つかが課題です。 NPの嘘はcoNPと交差しました。
• 二次演ductionをチェックする問題があります。 つまり、数値が与えられ、この数値を法として演deが与えられ、それが二次かどうかを理解する必要があります。 NPの嘘はcoNPと交差しました。
• 整数格子の最短ベクトルを近似する問題：基底を持つ整数格子が与えられ、その中で最短ベクトルを見つける必要があります。 最短ベクトル自体に興味がないが、必要なパラメーターでそれを近似する場合、問題はcoNPと交差するNPにも分類されます。
• 最小プラス線形システムの可解性の問題。
• そして、熱帯線形システムの可解性の問題。

実際、これらのタスクの一部はまったく同じタスクであることがわかりました。 つまり、それらは互いに同等です。



1979年と1988年に導入されたゲーム。 ゲームは次のように構成されています。アリスとボブの2人のプレーヤーがいて、2部グラフに沿って何らかのチップを移動します。 二部グラフでは、数字がエッジに書き込まれます。 アリスの目標は、チップが通過するエッジの数の合計を最大化することです。 ボブは彼女を最小化しようとします。 特定のゲームは、このチップが訪れた一連のピークです。 ゲームの価値は、エッジの平均数です。つまり、t歩進み、エッジを通過したすべての数を合計して、tで除算します。 その後、制限を取ります。 この特定のゲームでは、プレイヤーがプレーすることの利益と、誰が特に勝つかを見ることができます。 アリスが2階に行くとどうなりますか？ ボブはすぐにチップを戻します。つまり、合計は1になり、ボブは利益を上げるので、アリスはこれを行う意味がありません。 2つの動きの結果に基づいて、彼女は開始位置に戻り、同時に1を失います。したがって、他のオプションで何が起こるかがわかります。 彼女は0になり、ボブは現在、左と左と下のオプションを持っています。 彼が左と下に行くと、アリスは1つだけの動きを持ち、彼女は戻ることができます、そしてこれらの2つの動きの結果によると、ボブは2つを失います。 これは彼にとって有益ではないため、実行する価値はありません。



彼が厳密に左に行くとどうなるか見てみましょう。 その後、アリスに唯一の動きがあり、再び同じポイントに戻り、再びアリスが1を獲得しました。したがって、いずれにしても、アリサはここで勝ちます。 彼女は最初にここに行く必要があり（2）、それから彼女の唯一の動きで答え、4動きごとに1を獲得します。

ゲームの価値が正の場合、アリスが勝ち、ボブが反対の場合。 プレイヤーの一人が常に勝利戦略を持っていることが知られています。 また、一般的に直感的に明らかな位置的勝利戦略があることも知られています。 位置戦略は、プレーヤーのターンがチップの現在の位置にのみ依存する場合です。 移動が以前の方法に依存してはならないことは明らかです。

したがって、これらのゲームは定義されています。 それらに関連する問題は、誰が勝つかを理解することです（むしろ、アリスが勝つかどうかを理解することで、答えが「はい」になります）。 この問題はNPにあります。アリスの勝利戦略を証明書として与えると、この戦略が本当に勝利戦略かどうかを確認するのは非常に簡単だからです。 同じタスクはcoNPにあります。ボブが失くさない証明書は彼の戦略だからです。 ボブの戦略を与えると、アリスがどのようにプレイしても、彼女が勝てないことを多項式時間でチェックできます。



次に、可解性の問題よりもわずかに大きな問題を考えます。 さらに2つのタスクも見てください。

• システムの等価問題。 つまり、2つの熱帯システムが与えられ、それらが同等であるかどうかを理解する必要があります。
• 寸法の問題。 実際、これを理解する必要があります。線形熱帯方程式の解は、複数の多面体の結合であり、無限大である可能性があります。 それらのいくつかを取り、それらのシステムを取る場合、多面体のそのような結合の交差点があり、これはいくつかの多面体の結合とまったく同じです。 ここでの寸法は正しく決定できます。 つまり、ある種の熱帯多項式のシステムがある場合、その解を見て、最大差の多面体を見つけることができ、これを解空間の次元と呼びます。

問題：行列が与えられ、数値が与えられます。次元がこの数値以上であることが真実かどうかを理解する必要があります。

これらの問題はすべて、Zだけでなく、無限大を追加してZで考慮することができます。 そして、古典的な場合のそれらはすべて多項式的に解ける。



しかし、熱帯の場合、それはないことが判明しました。 テーブルにはすべての結果が含まれます。 熱帯の場合があり、最小プラスの場合があり、3つのタスクは、可解性、等価性、および次元に関するものです。 熱帯の場合の次元の問題は、単にNP完全であることがわかります。 さまざまなリンクがあります。 2つの参照がある場合、これは、最初の作業でこの結果がZで証明され、2番目の作業でZ∞で証明されることを意味します。 大きな違いがあります-無限がある場合、証明はあまり楽しくなく、はるかに困難です。 したがって、特に、これらの問題はすべて互いに同等であり、Pにあることを証明しようとする問題はどちらでもないことがわかります。



この写真の見方は？ そのような古いタスクがあります-平均ペイオフゲーム。 そして、それはまだ解決されていません。 それに相当するかなり新しいタスクがあることを証明します。 それらのいくつかは、いくつかの代数的用語、いくつかの代数的構造で定式化されています。 ここに、熱帯線形方程式のシステムの可解性の問題があります。 特定の代数構造では非常に大きな問題なので、このような新しい用語で周期ゲームの問題を再定式化しました。 そして、熱帯多項式の科学が発展することを望み、それが発展するとき、線形システムが多項式時間で解けることを証明する方法を学ぶことがわかります。



熱帯多項式に関する代数理論で一般的に知られていることは何ですか？ 線形の場合、何かが知られています。

熱帯代数の行列のランクにはさまざまな類似物があります。 実際、それらは非常に多く、意味が異なり、それらの間には不平等がありますが、それでも、そこで何かが研究され、何かが知られています。 行列の行列式に類似したものがあり、そこにも優れた特性があり、何らかの形で線形システムに接続されています。

マトリックスのガウス三角形の類似物があります。



一般的な場合、任意の多項式についてはあまり知られていない。 急進派の研究に関するいくつかの作品がありますが、ここでは特に進展は見られません。 可解性の問題はNP完全です。 多項式系は任意であり、次数の制限はありません。 実際、次数2の多項式。次数2の熱帯多項式系がある場合、その可解性の問題はNP完全です。

古典的な場合、問題はすでに解決不可能です。



何をすることが提案されていますか？ 古典代数では、ヒルベルトのゼロ定理の非常に重要な結果があります。

熱帯の場合のこの定理の類似物について話しましょう。 以下は、ヒルベルトのゼロ定理の弱い形式です。 この定理はこれを言います：古典的な多項式のシステムを持ちましょう、そしてそれが解を持たないことを理解したいと思います。 この定理は、多項式系に解がないことを建設的に意味することを意味します。 1に等しい代数的組み合わせがある場合、多項式系は一般的な解を持たないことがわかります。つまり、単に多項式定数1は、私たちの代数的組み合わせとして表されます。 そして、そのような代数的組み合わせがある場合にのみ、多項式システムが解を持たないという結果があります。 効果的なバージョンでは、これらの多項式の次数g ₁ 、g _kを推定できます。これらの積の最大次数は2 ^{dmin（n、k）}以下であると言えます。



単純に熱帯多項式のアナログを単純に定式化しようとすると、何も機能しません。 控除がないという同じ理由で。 このような多項式を2つだけ記述しても、共通の根はありません。 どんなに一生懸命やろうと、どんな代数的組み合わせをとっても、0でも1でも、このXは何も減らされないので、とにかく得られません。 それは単にそのような機会のために提供されていません。

ヒルベルトのゼロ定理の類似物を定式化するには、古典的なバージョン自体を少し再定式化する必要があります。



これを行うには、このようなマコーレー行列を考慮する必要があります。 多項式とそのような行列のシステムを見てみましょう。 Nはパラメーター、数です。 その列は単項式でラベル付けされ、次数はNより大きくなく、行はシステムの多項式でラベル付けされ、単項式で乗算されます。 また、次数はN以下です。行列のセルには、この多項式の単項係数が書き込まれます。



例：f ₁ = 1 + x、f ₂ = 2 + y、N = 2。

そのような線が得られます。つまり、これらの多項式のそれぞれは、いくつかの変数で乗算できます。

これは実際には、シルベスター行列を任意の多項式系に一般化したものです。



ヒルベルトのゼロ定理を双対形式で定式化します。 スライド上-最初は通常、次にデュアル。 多項式、変数n、次数dのシステムがあります。 そして、そのような線形システムに解決策がある場合にのみ、彼女には共通のルートがあることがわかります。



原則として、これを理解することは難しくありません。 これはここに書かれています：多項式f _iを取り、それらを異なる単項式で乗算し、それらを追加しました。 多項式は、係数のベクトルとして見ることができます。 f _iに単項式を掛けると、マコーレー行列の異なる行が得られます。 そして、それらを積み重ねるとき、マコーレー行列ステッチの線形結合を取ります。 そして、最終的には1つを取得します。 つまり、このシステムに解決策があるということは、ベクトル（1,0、...）に等しいマコーレー行列線の線形結合がないことを意味します。 これは、ベクトル（1,0、...）が行列の線の線形シェルにないことを意味します。 したがって、マトリックスのすべての行に直交し、ベクトル（1,0、...）に直交しないベクトルを選択できます。



トロピカルバージョンでマコーレー行列を定義します。 同じように定義されます：多項式のシステムがあり、同じ方法で列に単項式が番号付けされ、まったく同じ行に多項式が単項式を掛けた番号が付けられ、同じことがセルに書き込まれます。 単項式がない場合、無限はゼロの役割を果たします。 マコーレー行列を持つ熱帯線形システムに興味があります。 同時に、 _1に 0がない、つまり無限ではないようなソリューションに興味があります。



ヒルベルトのゼロ定理の類似物を、熱帯多項式の双対形式で定式化できます。 ここで、言い回しはまったく同じです。マコーレー行列をもつ線形システムに解がある場合にのみ、システムに解があります。 また、変数が1の場合に定理が証明されました。 一般的なケースは仮説として定式化されています。



これが実際に正しいという定理。 熱帯多項式のシステムを考えてみましょう。diでその次数、inで最大次数を示します。 マコーレー行列にも解がある場合にのみ、システムに解があることがわかります。 Nの場合、これを取ることができます。



無限がない場合、Nはそのようなものであり、N x d、x kとして推定できます。

無限大がある場合、これはより複雑なものです-それはn、kの多項式です（スライドを参照）。 これらの推定値はどちらも多少正確です。 実際、これは、無限があるかどうかが本質的に重要であることが判明した、まれな例の1つです。



min-plusの場合、この定理に類似した類似物があります。 Macauley行列は、min-plusの場合と同じ方法で定義できますが、現在は2つあり、このようなシステム、双方向、min-plus線形システムに既に興味があります。



同様に、ヒルベルトのゼロ定理の類似体を双対形式で定式化できます：多項式の最小プラスシステムは、マコーレー行列を含む線形システム（以前と同じものをnとする必要がある場合）の場合にのみ解を持ちます。



当初、この定理は二重形式でした-つまり、解決策がない場合は別の問題があります。 ここで、この定理にはこの形式はありません。 彼らは、解決策があれば、解決策があると言います。 解決策がない場合、解決策はありません。 これはまだ二重の結果ではありません。



デュアルタイプの結果も取得でき、これは次のようになります。 次数dで示される最小プラス多項式のシステムがあります。 すべての単項式について左の係数が右の係数よりも大きくなるような多項式の熱帯代数的組み合わせを収集できる場合にのみ、システムに解があると言えます。



熱帯多項式のシステムがあるとします。 そして、熱帯の単項動物も。 代数的組み合わせgを考えます。 これはこのように構成されています。fの多項式に単項式を乗算し、それをすべて加算しました。 そして、そのような代数的組み合わせは、以下が起こる場合、非縮退と呼ばれます：

• gのすべての単項式には、そのような一意のg _jがあり、このg _l（M）のこの単項式の係数が他のすべての項よりも小さくなるような数l（M）があります。
• 異なる単項式では、これらの場所が異なることも必要です。

例。 このような2つの多項式を考えます。 そして、そのような係数でそれらをここに追加します。 これらは次数0の単項式ですが、まだ単項式です。 この式を追加しましょう。 そして、単項定数の左側の係数は0、右側の係数は½、左側の係数は小さく、これが小さい場所であることがわかります。 次数1の単項式の係数は右側が½、係数が左側が0になりますが、右側は小さくなり、これだけが小さくなりました。 つまり、これら2つの単項式には少なくとも異なる場所があります。 したがって、これらの多項式について、非縮退代数の組み合わせを構築できます。



このような非縮退代数の組み合わせの存在は、システムに解決策がないという基準であることがわかります。 無限の存在下では、単に非縮退代数の組み合わせがあるだけでは十分ではありません。また、定数の単項式が有限であることも必要です。 そうでなければ、この代数的な組み合わせで解決策があります。

非縮退代数の組み合わせのこの定義は、複雑ではあるが検証可能です。



熱帯多項式と最小プラス多項式はどのように関係していますか？ これらは非常に簡単な方法で一方向に接続されていることがわかります。熱帯多項式のシステムがある場合、常に同じ変数と同じ解のセットを持つ多項式の最小プラスシステムを構築できます。 逆の方向では、そのような単純な情報はありません。 しかし、それはまだ存在します：多項式の最小プラスシステムがある場合、2倍の変数を持つ別の熱帯の多項式システムを構築でき、同時に線形空間Qnを線形空間Q2nに埋め込むことができ、すべての解がfすべてのソリューションに正確に埋め込むt。



つまり、システムfの解の集合はn次元空間の特定のサブセットであり、tの場合、解の集合は2n次元空間の一部のサブセットです。 それにもかかわらず、1つのソリューションを別のソリューションに全単射で投資するだけでよく、それらは単純に互いに対応しています。



これらの2つの対応により、最小プラス多項式から熱帯多項式にすばやく切り替えることができます。 1つのケースについて定理が証明されるとすぐにリストされた結果では、2番目のタイプの多項式にすぐに変換できます。



最後の一連の結果の証明はどのように整理されますか？ 第一に、双対形式の熱帯零点定理があります。 幾何学的に証明されています。 第二部の主要な内容全体が実際にこの定理に含まれています。 それから最小プラスケースに渡してそのような定理を得るのはもはや難しくありません。



定理への移行は二重形式の外でどのように行われますか？ 実際、ここでは、線形双対性を熱帯線形システムに使用できます。 彼らにとっては、線形双対性をシンプルで理解可能な形で書き出すことができ、結果を得て、この線形システムに双対性を使用し（No.39）、代数的組み合わせの観点から二重系を解釈し、これを取得します（No.40） そして、この定理から、再びミニプラスシステムから熱帯への移行システムの助けを借りて、デュアルフォームのない熱帯システムを得ることができます（No.43）。



双対定理の幾何学的証明のアイデア。 Qの多項式システムは、そのような線形熱帯システムの解がある場合にのみ解を持ちます。 そして、一方向では簡単です。多項式系に解がある場合、熱帯線形系にも解があります。 マコーレー行列の列Cnは変数Xの単項式に対応することを覚えておく必要があります。また、多項式Xのシステムに何らかの解がある場合、 _iをこの単項式に等しくする必要があり、マコーレー行列の行には多項式fモノム Xは多項式fの解であるため、yはマコーレー行列のこれらの線で与えられる線形方程式の解になります。



他の方法は難しいです。 次のことを行う必要があります。このシステムには何らかの解決策があること、つまり何らかの種類のベクトルYが存在することを知っています。 X.



まず、N = 2を修正すると便利です。これは実質的なケースです。2が証明されるとすぐに、nが大きいと即座に一般化されます。 座標に負でない整数のペアで番号が付けられたベクトルが定期的にあります。 たとえば、これらは多項式係数です。 実際、それらは単項式によって番号が付けられています。 マコーレー行列の行とその解はまったく同じです。



これらのすべてのベクトルを、すべてのオブジェクトを3次元空間の点のセットとして見ることができます。 最初の2つの座標はベクトルの座標に対応し、3番目の座標はこれらの座標の値に対応します。 f _i f P _fi – , . . Macauley - . , P _fi . Macauley - . .



, Macauley, , , . –. +Y _i -Yi. , . P _y , Y, , . Y – . ? , Py , . , . , P _y , , , . , Y .



, Y , – . , , . - , . , . Y, . このように動作します。



P _fi , , . , .



Y , . : P _fi , , – Macauley. Y, , . , , . .