単項式順序

単項式順序（たんこうしきじゅんじょ、monomial order）は、単項式を順序付けるものであって、いくつかの性質を満たすものである。例えば1変数多項式を記述する場合、昇冪の順または降冪の順に並べるのが通常であるが、多変数の場合はそう単純ではなく、多くの並べ方が考えられる。一般の2変数2次多項式は

$ax^{2}+bxy+cy^{2}+dx+ey+f$

と記述されることが多いが、これは単項式順序の一種である次数付き辞書式順序で並べられている。

単項式順序は、多項式の割り算アルゴリズムやグレブナー基底の理論において重要な役割を果たす。用いる単項式順序の種類によって、アルゴリズムの効率や得られる結果には違いが生じ得る。

定義

k を体とし、多項式環 k[x₁, …, x_n] の部分集合

$A:=\{x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}\mid a_{i}\in \mathbb {N} \}$

（N は 0 も含むとする）を考える。A における全順序 ≤ が単項式順序であるとは、次の2条件を満たすことをいう。

1. u ≤ v ならば、A の任意の元 w に対して uw ≤ vw が成り立つ。
2. 整列順序である。すなわち、任意の空でない単項式の集合は ≤ に関して最小元を持つ。

以上の定義では A においてのみ順序が定められているが、係数のみ異なる単項式は同一視して、係数が 1 とは限らない単項式に拡張して考えるのが通常である。

A の元は Nⁿ の元 (a₁, …, a_n) と1対1に対応する。記述の簡略化のため、α = (a₁, …, a_n) ∈ Nⁿ に対して x^α で

$x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$

を表すものとする。このとき、≤ が単項式順序であるための条件1は次のように記述される。

• α, β ∈ Nⁿ が x^α ≤ x^β を満たすならば、任意の γ ∈ Nⁿ に対して x^α+γ ≤ x^β+γ が成り立つ。

また、条件1が成立するとき、条件2は次の条件で置き換えることもでき、こちらを用いる方が単項式順序であることの判定が容易である場合がある。

• 任意の不定元 x_i に対して x_i > 1 が成り立つ。

例

必要ならば不定元の順番を入れ替えることによって、x₁ > x₂ > … > x_n として差し支えない。また、α = (a₁, …, a_n) ∈ Nⁿ に対して、a₁ + … + a_n を x^α の全次数 (total degree) といい、|α| で表すこととする。

辞書式順序 (lexicographic order, lex) は、β - α の 0 でない最初の成分が正である場合に x^α < x^β として定義される単項式順序である。素朴に表現するならば、lex 順序はまず最も「上位の」不定元の指数の大きさによって順序付け、それが同じものについては順次「下位の」不定元の指数の大きさによって順序付ける。

逆辞書式順序 (reverse lexicographic order, revlex) は、β - α の 0 でない最後の成分が負である場合に x^α < x^β として定義される順序である。ただしこれは整列順序ではなく、先述の意味での単項式順序ではない。素朴に表現するならば、revlex 順序はまず最も「下位の」不定元の指数の小ささによって順序付け、それが同じものについては順次「上位の」不定元の指数の小ささによって順序付ける。

次数付き辞書式順序 (graded lexicographic order, grlex) は、次のいずれかが成り立つ場合に x^α < x^β として定義される単項式順序である。

• |α| < |β|
• |α| = |β| かつ β - α の 0 でない最初の成分が正

素朴に表現するならば、grlex 順序はまず全次数の大きさによって順序付け、それが同じものについては辞書式順序で順序付ける。

次数付き逆辞書式順序 (graded reverse lexicographic order, grevlex) は、次のいずれかが成り立つ場合に x^α < x^β として定義される単項式順序である。

• |α| < |β|
• |α| = |β| かつ β - α の 0 でない最後の成分が負

素朴に表現するならば、grevlex 順序はまず全次数の大きさによって順序付け、それが同じものについては逆辞書式順序で順序付ける。

具体例

3つの単項式 x²yz, x³, xy³ を考えよう。不定元の間には x > y > z という順序が定まっているとすると、代表的な単項式順序においては、次のように順序付けられる。

• lex 順序では x³ > x²yz > xy³ となる（x の指数の大きさが順序を決める）。
• grlex 順序では x²yz > xy³ > x³ となる（まず全次数の大きさが順序を決め、それが同じもの同士については x の指数の大きさが順序を決める）。
• grevlex 順序では xy³ > x²yz > x³ となる（まず全次数の大きさが順序を決め、それが同じもの同士については z の指数の小ささが順序を決める）。

関連項目

• 辞書式順序

参考文献

• David Cox, John Little and Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 2007. ISBN 978-0387356501
  • 日本語訳『グレブナ基底と代数多様体入門』（上） ISBN 978-4431708230（下）ISBN 978-4431708247