ゴルダンの補題

ゴルダンの補題は凸幾何学と代数幾何学における補題である。いくつかの方法で表現できる。

• を整数行列とする。をの非負整数解の集合とする。すると にはベクトルの有限部分集合が存在し、 のすべての要素はこれらのベクトルの非負整数係数の線形結合となる。^[1]${\displaystyle A}$${\displaystyle M}$${\displaystyle A\cdot x=0}$${\displaystyle M}$${\displaystyle M}$
• 有理凸多面体円錐の積分点の半群は有限生成である。[ 2 ^]
• アフィントーリック多様体は代数多様体です（これは、そのような半群の半群代数の素スペクトルが、定義により、アフィントーリック多様体であるという事実から導かれます）。

この補題は数学者ポール・ゴーダン(1837-1912) にちなんで名付けられました。著者の中にはこれを「ゴードンの補題」と誤って綴った人もいます。

位相的証明と代数的証明があります。

を与えられた有理多面体錐の双対錐とする。を となる積分ベクトルとする。すると の双対錐 を生成する。実際、の双対錐を生成する錐をC と書くと、 となり、これは等式でなければならない。ここで、x が半群に属する 場合、${\displaystyle \sigma}$${\displaystyle u_{1},\dots ,u_{r}}$${\displaystyle \sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.}$${\displaystyle u_{i}}$${\displaystyle \sigma ^{\vee}}$${\displaystyle u_{i}}$${\displaystyle \sigma \subset C^{\vee}}$

${\displaystyle S_{\sigma }=\sigma ^{\vee }\cap \mathbb {Z} ^{d},}$

と書くことができる。

${\displaystyle x=\sum _{i}n_{i}u_{i}+\sum _{i}r_{i}u_{i},}$

ここで、は非負の整数、 です。しかし、xと右辺の最初の和は整数なので、2 番目の和は境界領域内の格子点となり、2 番目の和には有限個の可能性しかありません (位相的な理由)。したがって、は有限生成です。 ${\displaystyle n_{i}}$${\displaystyle 0\leq r_{i}\leq 1}$${\displaystyle S_{\sigma}}$

証明^{[3]は、半群}Sが有限生成であるための必要十分条件は、その半群代数が 上の有限生成代数であるという事実に基づいている。ゴルダンの補題を帰納法で証明するには（上記の証明を参照）、次の命題を証明すれば十分である：の任意の単位部分半群Sに対して、 ${\displaystyle \mathbb {C} [S]}$${\displaystyle \mathbb {C} }$${\displaystyle \mathbb {Z} ^{d}}$

Sが有限生成であれば、積分ベクトルv は有限生成です。${\displaystyle S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\}}$

を置きます。これは基底 を持ちます。これは次のように表される -次数を 持ちます。${\displaystyle A=\mathbb {C} [S]}$${\displaystyle \chi ^{a},\,a\in S}$${\displaystyle \mathbb {Z} }$

${\displaystyle A_{n}=\operatorname {span} \{\chi ^{a}\mid a\in S,\langle a,v\rangle =n\}}$。

仮定により、A は有限生成であり、したがってネーターです。以下の代数補題から、 は上の有限生成代数であることがわかります。ここで、半群は線型射影によるSの像であるため、有限生成であり、したがって は有限生成です。したがって、は有限生成です。 ${\displaystyle \mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}}$${\displaystyle A_{0}}$${\displaystyle S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}}$${\displaystyle A_{0}=\mathbb {C} [S_{0}]}$${\displaystyle S^{+}}$

補題: A を-次数環とする。A がネーター環であれば、は有限生成-代数である。 ${\displaystyle \mathbb {Z} }$${\displaystyle A^{+}=\oplus _{0}^{\infty }A_{n}}$${\displaystyle A_{0}}$

証明: I を、Aの正の次数のすべての同次元によって生成されるAのイデアルとします。Aはネーターなので、I は実際には有限個の正の次数同次によって生成されます。 f が正の次数同次であれば、同次と書くことができます。fの次数が十分に大きい場合、各 の次数は正で、 fの次数よりも厳密に小さくなります。また、各次数ピースは有限生成 - 加群です。(証明:をの有限生成サブ加群の増加チェーンと和集合とします。すると、イデアルのチェーンは有限ステップで安定し、チェーン も有限ステップで安定します。) したがって、次数に関する帰納法により、は有限生成 -代数であることがわかります。 ${\displaystyle f_{i}'s}$${\textstyle f=\sum _{i}g_{i}f_{i}}$${\displaystyle g_{i}}$${\displaystyle g_{i}}$${\displaystyle A_{n}}$${\displaystyle A_{0}}$${\displaystyle N_{i}}$${\displaystyle A_{n}}$${\displaystyle A_{n}}$${\displaystyle N_{i}A}$${\displaystyle N_{i}=N_{i}A\cap A_{n}.}$${\displaystyle A^{+}}$${\displaystyle A_{0}}$

ある集合上の多重ハイパーグラフは、の部分集合の多重集合です(各ハイパーエッジが複数回出現することがあるため、「多重ハイパーグラフ」と呼ばれます)。すべての頂点の次数が と同じ場合、多重ハイパーグラフは正則と呼ばれます。 正則な適切な空でない部分集合がある場合、多重ハイパーグラフは分解可能と呼ばれます。任意の整数nに対して、をn頂点上の分解不可能な多重ハイパーグラフの最大次数とします。ゴルダンの補題は が有限であることを意味します。^[1]証明: 頂点の各部分集合Sに対して、変数x _S (非負の整数) を定義します。 別の変数d (非負の整数) を定義します。 次のn方程式の集合 (頂点ごとに 1 つの方程式) を考えます。すべての解 ( x、d ) は 上の正則多重ハイパーグラフを表します。ここで、x はハイパーエッジを定義し、d は次数です。ゴルダンの補題により、解の集合は有限の解の集合によって生成されます。つまり、多重ハイパーグラフの有限の集合が存在し、各正則多重ハイパーグラフは のいくつかの要素の線形結合になります。分解不可能な多重ハイパーグラフはすべて になければなりません(定義により、他の多重ハイパーグラフによって生成できないため)。したがって、分解不可能な多重ハイパーグラフの集合は有限です。 ${\displaystyle V}$${\displaystyle V}$${\displaystyle D(n)}$${\displaystyle D(n)}$ $${\displaystyle \sum _{S\ni v}x_{S}-d=0{\text{ すべての }}v\in V に対して}$$${\displaystyle V}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$

• バーコフのアルゴリズムは、双確率行列 (特定の方程式のセットを解く行列) が与えられたときに、それを積分行列に分解するアルゴリズムです。このアルゴリズムは、これらの行列の集合が有限の積分行列の集合によって生成されることを示す点で、ゴルダンの補題と関連しています。

• ディクソンの補題