単項式順序のソースを表示
←
単項式順序
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、次のグループに属する利用者のみが実行できます:
登録利用者
。
このページのソースの閲覧やコピーができます。
'''単項式順序'''（たんこうしきじゅんじょ、monomial order）は、[[単項式]]を順序付けるものであって、いくつかの性質を満たすものである。例えば1変数多項式を記述する場合、昇冪の順または降冪の順に並べるのが通常であるが、多変数の場合はそう単純ではなく、多くの並べ方が考えられる。一般の2変数2次多項式は :<math>ax^2+bxy+cy^2+dx+ey+f</math> と記述されることが多いが、これは単項式順序の一種である次数付き辞書式順序で並べられている。 単項式順序は、多項式の割り算アルゴリズムや[[グレブナー基底]]の理論において重要な役割を果たす。用いる単項式順序の種類によって、アルゴリズムの効率や得られる結果には違いが生じ得る。 == 定義 == ''k'' を[[可換体|体]]とし、多項式[[環 (数学)|環]] ''k''[''x''<sub>1</sub>, …, ''x''<sub>''n''</sub>] の部分集合 :<math>A:=\{ x_1^{a_1} \cdots x_n^{a_n} \mid a_i \in \mathbb{N} \}</math> （'''N''' は 0 も含むとする）を考える。''A'' における[[順序集合|全順序]] ≤ が'''単項式順序'''であるとは、次の2条件を満たすことをいう。 # ''u'' ≤ ''v'' ならば、''A'' の任意の元 ''w'' に対して ''uw'' ≤ ''vw'' が成り立つ。 # [[整列順序]]である。すなわち、任意の[[空集合|空]]でない単項式の集合は ≤ に関して最小元を持つ。 以上の定義では ''A'' においてのみ順序が定められているが、係数のみ異なる単項式は同一視して、係数が 1 とは限らない単項式に拡張して考えるのが通常である。 ''A'' の元は '''N'''<sup>''n''</sup> の元 (''a''<sub>1</sub>, …, ''a''<sub>''n''</sub>) と1対1に対応する。記述の簡略化のため、α = (''a''<sub>1</sub>, …, ''a''<sub>''n''</sub>) ∈ '''N'''<sup>''n''</sup> に対して ''x''<sup>α</sup> で :<math>x_1^{a_1} \cdots x_n^{a_n}</math> を表すものとする。このとき、≤ が単項式順序であるための条件1は次のように記述される。 * α, β ∈ '''N'''<sup>''n''</sup> が ''x''<sup>α</sup> ≤ ''x''<sup>β</sup> を満たすならば、任意の γ ∈ '''N'''<sup>''n''</sup> に対して ''x''<sup>α+γ</sup> ≤ ''x''<sup>β+γ</sup> が成り立つ。 また、条件1が成立するとき、条件2は次の条件で置き換えることもでき、こちらを用いる方が単項式順序であることの判定が容易である場合がある。 * 任意の不定元 ''x''<sub>''i''</sub> に対して ''x''<sub>''i''</sub> > 1 が成り立つ。 == 例 == 必要ならば不定元の順番を入れ替えることによって、''x''<sub>1</sub> > ''x''<sub>2</sub> > … > ''x''<sub>''n''</sub> として差し支えない。また、α = (''a''<sub>1</sub>, …, ''a''<sub>''n''</sub>) ∈ '''N'''<sup>''n''</sup> に対して、''a''<sub>1</sub> + … + ''a''<sub>''n''</sub> を ''x''<sup>α</sup> の'''全次数''' (total degree) といい、|α| で表すこととする。 '''辞書式順序''' (lexicographic order, lex) は、β - α の 0 でない最初の成分が正である場合に ''x''<sup>α</sup> < ''x''<sup>β</sup> として定義される単項式順序である。素朴に表現するならば、lex 順序はまず最も「上位の」不定元の指数の大きさによって順序付け、それが同じものについては順次「下位の」不定元の指数の大きさによって順序付ける。 '''逆辞書式順序''' (reverse lexicographic order, revlex) は、β - α の 0 でない最後の成分が負である場合に ''x''<sup>α</sup> < ''x''<sup>β</sup> として定義される順序である。ただしこれは整列順序ではなく、先述の意味での単項式順序ではない。素朴に表現するならば、revlex 順序はまず最も「下位の」不定元の指数の小ささによって順序付け、それが同じものについては順次「上位の」不定元の指数の小ささによって順序付ける。 '''次数付き辞書式順序''' (graded lexicographic order, grlex) は、次のいずれかが成り立つ場合に ''x''<sup>α</sup> < ''x''<sup>β</sup> として定義される単項式順序である。 * |α| < |β| * |α| = |β| かつ β - α の 0 でない最初の成分が正 素朴に表現するならば、grlex 順序はまず全次数の大きさによって順序付け、それが同じものについては辞書式順序で順序付ける。 '''次数付き逆辞書式順序''' (graded reverse lexicographic order, grevlex) は、次のいずれかが成り立つ場合に ''x''<sup>α</sup> < ''x''<sup>β</sup> として定義される単項式順序である。 * |α| < |β| * |α| = |β| かつ β - α の 0 でない最後の成分が負 素朴に表現するならば、grevlex 順序はまず全次数の大きさによって順序付け、それが同じものについては逆辞書式順序で順序付ける。 === 具体例 === 3つの単項式 ''x''<sup>2</sup>''yz'', ''x''<sup>3</sup>, ''xy''<sup>3</sup> を考えよう。不定元の間には ''x'' > ''y'' > ''z'' という順序が定まっているとすると、代表的な単項式順序においては、次のように順序付けられる。 * lex 順序では ''x''<sup>3</sup> > ''x''<sup>2</sup>''yz'' > ''xy''<sup>3</sup> となる（''x'' の指数の大きさが順序を決める）。 * grlex 順序では ''x''<sup>2</sup>''yz'' > ''xy''<sup>3</sup> > ''x''<sup>3</sup> となる（まず全次数の大きさが順序を決め、それが同じもの同士については ''x'' の指数の大きさが順序を決める）。 * grevlex 順序では ''xy''<sup>3</sup> > ''x''<sup>2</sup>''yz'' > ''x''<sup>3</sup> となる（まず全次数の大きさが順序を決め、それが同じもの同士については ''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 {{DEFAULTSORT:たんこうしきしゆんしよ}} {{Abstract-algebra-stub}} {{Normdaten}} [[Category:順序構造]] [[Category:数学に関する記事]]
このページで使用されているテンプレート:
テンプレート:Abstract-algebra-stub
(
ソースを閲覧
)
テンプレート:Normdaten
(
ソースを閲覧
)
単項式順序
に戻る。
ナビゲーション メニュー
個人用ツール
ログイン
名前空間
ページ
議論
日本語
表示
閲覧
ソースを閲覧
履歴表示
その他
検索
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
ツール
リンク元
関連ページの更新状況
ページ情報