単項式順序

数学において、単項式順序（たんじょうきょうけい、英: monomial order）とは、与えられた多項式環におけるすべての（モニック）単項式の集合上の全順序であり、乗法を尊重する性質を満たす。すなわち、

• およびが他の単項式である場合、 となります。${\displaystyle u\leq v}$${\displaystyle w}$${\displaystyle uw\leq vw}$

単項式順序は、グレブナー基底と多変数除算で最もよく使用されます。特に、グレブナー基底であるという性質は、常に特定の単項式順序に相対的です。

乗算を尊重することに加えて、単項式順序は整列順序であることがしばしば要求されます。これは、多変数除算手順が終了することを保証するためです。ただし、整列順序ではない単項式の集合上でも、乗算を尊重する順序関係の実用的な応用があります。

有限個の変数の場合、単項式順序の整列性は次の 2 つの条件の結合と同等です。

1. 注文は合計注文です。
2. u が任意の単項式である場合、 .${\displaystyle 1\leq u}$

これらの条件は、明示的な規則によって定義された単項式順序に対して検証する方が、それが整列順序であることを直接証明するよりも簡単な場合があるので、単項式順序の定義では好まれることがあります。

単項式の全順序を選択すると、多項式の項をソートできます。したがって、多項式の 主要項は、（選択された単項式の順序に対して）最大の単項式の項になります。

具体的には、R を任意の多項式環とする。すると、 Rの（単項）単項式の集合M は、係数の体上のベクトル空間として考えれば、Rの基底となる。したがって、 Rの任意の非ゼロ多項式p は、単項式の線形結合 として一意に表現される 。ここで、 SはMの有限部分集合であり、c _{u は}すべて非ゼロである。単項式の順序が選択されると、主単項式はSの最大のu、主係数は対応するc _u、主項は対応するc _u uである。主単項式/係数/項は、「主」の同義語として使用されることがある。一部の著者は、「項」の代わりに「単項式」を、「単項式」の代わりに「べき乗積」を使用する。この記事では、単項式には係数が含まれないと仮定する。 ${\displaystyle p=\textstyle \sum _{u\in S}c_{u}u}$

単項式順序の定義特性は、多項式を単項式で乗算するときに項の順序が維持されることを意味します。また、多項式の積の主要項は、因数の主要項の積です。

任意の1 つの変数xの累乗の集合では、単項式順序は自然な順序 1 <  x  < x ²  < x ³  < ... とその逆順序のみであり、後者は整列順序ではありません。したがって、単項式順序の概念は、複数の変数の場合にのみ興味深いものになります。 ${\displaystyle \left\{x^{n}\mid n\in \mathbb {N} \right\}}$

単項式順序は、個々の不定値に順序があることを意味します。 単項式順序の分類を簡略化するには、考慮する単項式順序に対して不定値が降順でx ₁、x ₂、x _{3 、... と命名され、常に}x ₁ > x ₂ > x ₃ > ...となるものと仮定します。 (不定値が無限にある場合、この規則は順序付けの条件と矛盾するため、逆の順序付けを強いられます。ただし、無限に多くの変数を持つ多項式の場合が考慮されることはほとんどありません。) 以下の例では、x ₁、x ₂、x ₃の代わりにx、y、z を使用します。 この規則を使用すると、異なる単項式順序の例がまだ多数あります。

辞書式順序(lex) では、まず単項式のx ₁の指数を比較し、等しい場合はx ₂の指数を比較する、というように行います。この名前は、単項式が不定値の指数のシーケンスによって表される場合、辞書の辞書学で使用される通常のアルファベット順との類似性に由来しています。不定値の数が固定されている場合 (通常はそうであるように)、辞書式順序は整列順序ですが、さまざまな長さのシーケンスに適用される辞書式順序の場合はそうではありません ( 「辞書式順序 § さまざまな長さのシーケンスの順序付け」を参照)。

2つの不定元における2次以下の単項式について、辞書式順序（）は ${\displaystyle x_{1},x_{2}}$${\displaystyle x_{1}>x_{2}}$

$${\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{1}>x_{2}>x_{2}>1.}$$

グレブナー基底計算では、辞書式順序付けが最もコストがかかる傾向があるため、非常に単純な計算を除いて、可能な限り避けるべきです。

段階的辞書式順序(grlex、または deglex はdegree lexicographic orderの略) は、まず全体の次数 (すべての指数の合計) を比較し、同点の場合は辞書式順序を適用します。この順序付けは適切な順序付けであるだけでなく、任意の単項式の前には有限個の他の単項式しか存在しないという特性もあります。これは、yのすべての (無限個の) 累乗がxより小さい辞書式順序には当てはまりません(辞書式順序が適切な順序付けである理由は、単項式の無限減少チェーンを構築できないことに関係しています)。

2つの不定元における2次以下の単項式について、次数付き辞書式順序（）は ${\displaystyle x_{1},x_{2}}$${\displaystyle x_{1}>x_{2}}$

$${\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}>x_{2}>1.}$$

非常に自然ではありますが、この順序付けはほとんど使用されません。次に示す、次に示す逆辞書式順序のグレブナー基底は計算が簡単で、多項式の入力セットに関する同じ情報を提供します。

段階的逆辞書式順序(grevlex、または次数逆辞書式順序の degrevlex ) では、まず全体の次数を比較し、次に辞書式順序をタイブレーカーとして使用しますが、辞書式比較の結果を逆にして、同じ次数で辞書式順序で大きい単項式は degrevlex 小さいと見なされます。最終的な順序が不定値の従来の順序x ₁ > x ₂ > ... > x _nを示すためには、さらに、反転前のタイブレーカー辞書式順序が最後の不定値x _{n を}最大と見なす必要があり、つまり、その不定値から開始する必要があります。したがって、段階的逆辞書式順序の具体的なレシピは、まず総次数で比較し、次に最後の不定値x _nの指数を比較しますが、結果は逆にします（したがって、指数が小さい単項式の方が順序付けでは大きくなります）。続いて（常に同点の場合のみ）x _{n −1}を同様に比較し、これを繰り返してx ₁で終了します。

次数付き辞書式順序と次数付き逆辞書式順序の違いは微妙で、実際には 1 および 2 の不定値については一致する。最初の違いは 3 不定値の次数 2 の単項式で、次数付き辞書式順序では となるが、次数付き逆辞書式順序ではとなる。一般的な傾向として、逆順序では任意の次数の小さな単項式内のすべての変数が表示されるのに対し、非逆順序では任意の次数の最小の単項式の区間は最小の変数からのみ形成される。 ${\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}}$${\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}}$

ブロック順序または消去順序(lexdeg) は任意の数のブロックに対して定義できますが、簡単にするために、2 つのブロックの場合のみを検討します (ただし、ブロックの数が変数の数に等しい場合、この順序は単に辞書式順序になります)。この順序付けでは、変数が 2 つのブロックx ₁、...、x _hとy ₁、...、y _kに分割され、各ブロックに対して単項式順序 (通常は段階的逆辞書式順序) が選択されます。2 つの単項式は、 x部分を比較して比較され、同点の場合はy部分を比較します。この順序付けは、代数幾何学の射影に対応する操作である 消去を可能にするため重要です。

重みの順序は、重みベクトルと呼ばれるベクトルに依存します。まず、単項式の指数シーケンスのドット積をこの重みベクトルと比較し、同点の場合は他の固定された単項式順序を使用します。たとえば、上記の段階的順序は、「合計次数」重みベクトル (1,1,...,1) の重み順序です。a i が有理的に独立した数である場合(_つまり、特にそれらのいずれもゼロではなく、すべての分数が無理数である場合)、同点は決して発生せず、重みベクトル自体が単項式順序を指定します。逆の場合、別の重みベクトルを使用して同点を解消することができます。n 個の線形独立重みベクトルを使用した後は、同点が残ることはありません。実際、重みベクトルのシーケンスによって任意の単項式順序を定義できます( Cox ら、pp. 72–73)。たとえば、lex の場合は (1,0,0,...,0)、(0,1,0,...,0)、... (0,0,...,1)、grevlex の場合は (1,1,1,...,1)、(1,1,..., 1,0)、... (1,0,...,0) です。 ${\displaystyle (a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}}$${\displaystyle {\tfrac {a_{i}}{a_{j}}}}$

たとえば、単項式、、、およびを考えます。上記の単項式順序では、これら 4 つの単項式は次のように順序付けられます 。${\displaystyle xy^{2}z}$${\displaystyle z^{2}}$${\displaystyle x^{3}}$${\displaystyle x^{2}z^{2}}$

• レックス: (支配の力)。${\displaystyle x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}}$${\displaystyle x}$
• Grlex: (合計次数が優勢。最初の 2 つの間の同点を破ったのは、より高いパワー)。${\displaystyle x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}}$${\displaystyle x}$
• Grevlex: (総次数が優勢。最初の 2 つの間の同点を破ったパワーが低い)。${\displaystyle xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}}$${\displaystyle z}$
• 重みベクトル (1,2,4) を使用した重み順序: (ドット積 10>9>8>3 では、ここで決着がつくことはありません)。${\displaystyle x^{2}z^{2}>xy^{2}z>z^{2}>x^{3}}$

• 消去順序は、不定値の集合のいずれかを含む単項式が、それらのいずれも含まない単項式よりも常に大きくなることを保証します。
• 積順序は消去順序のより簡単な例です。これは、不定値の互いに素な集合の単項式順序をそれらの和集合の単項式順序に組み合わせることです。これは、最初の集合の不定値の指数を最初の単項式順序を使用して単純に比較し、次に 2 番目の集合の不定値に対する別の単項式順序を使用して同点を判定します。この方法は、明らかに不定値の集合の互いに素な和集合に一般化できます。辞書式順序は、単一集合 { x ₁ }、{ x ₂ }、{ x ₃ }、... (各単一集合の一意の単項式順序を使用) からこのように取得できます。

単項式順序を使用してグレブナー基底を計算する場合、順序が異なると結果が異なり、計算の難しさも大幅に変わる可能性があります。たとえば、段階的逆辞書式順序は、ほとんどの場合、計算が最も簡単なグレブナー基底を生成するという評判があります (これは、イデアル上のかなり一般的な条件下では、グレブナー基底の多項式の次数が変数の数に対して最大でも指数的であるという事実によって強化されます。他の順序では、このような複雑さの結果は存在しません)。一方、消去順序は、消去問題と相対問題に必要です。

• デビッド・コックス、ジョン・リトル、ドナル・オシェイ（2007年）。『イデアル、多様体、アルゴリズム：計算代数幾何学と可換代数の入門』。シュプリンガー。ISBN 978-0-387-35650-1。