単項式順序の例

グレブナー基底大好きbot @groebner_basis

【単項式順序の例①】 私立グレブナー中学校（ぶな中）に通うぶなっしーは先生に次のような問題を出されたぶなよっ！ 先生「３つの３変数単項式 x^2*y*z^2,x^2*y^2*z,xyz があります。これをいい感じに並べてください。」 つまり大きい順に並べて欲しいらしいぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例②】 ぶなっしーは、昨日勉強した「単項式順序」を使って並べたいと思うぶなよっ！単項式順序≧とは、 ①全順序である ②X^(a,b)≧X^(c,d) ⇒ X^(a+e,b+f)≧X^(c+e,d+f) ③整列順序である を満たす単項式の順序だったぶなっ

グレブナー基底大好きbot @groebner_basis

【単項式順序の例③】 でもどんな順序が単項式順序ぶなか？とりあえず x^2*y*z^2, x^2*y^2*z, xyz をx>y>zの順に重要視して並べてみたいと思うぶなっ！まず、xの次数に着目すると、左からx^2,x^2,xぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例④】 xの次数が大きい方が大きいと考えると、x^2*y*z^2, x^2*y^2*z ≧ xyz と見れるぶなっ！でも、最初の二つは、xの次数は同じ2ぶなからどちらが大きいか決めかねるぶなね。そこで、その二つのyの次数に注目するぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑤】 yの次数はそれぞれ、yとy^2 ぶなね。よって、yの次数が大きい方が偉いとして、 x^2*y*z^2≦x^2*y^2*z と考えることにするぶなっ！したがって、並べなおすと x^2*y^2*z ≧ x^2*y*z^2 ≧ xyz になるぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑥】 このように、「xの次数を比べる」（同じだったら）→「yの次数を比べる」（同じだったら）→「zの次数を比べる」という風に比較する順序のことを「辞書式順序」と呼ぶぶなっ！左から大きい順に並べていくのが辞書の並べ方に似てるぶなねっ！（りんご→りんす、など。）

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑦】 少し、厳密に定義すると次のようになるぶな。(a,b,c)をそれぞれx,y,zの次数とするぶな！ 【定義】 (a,b,c)≧(d,e,f) ：⇔　(a-d,b-e,c-f) の最も左の0でない項が正。 によって定義される順序≧を辞書式順序と呼ぶ。

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑧】 少し難しく見えるかもぶなけど、意味は同じぶなっ！例えば、さっきx^2*y^2*z ≧ x^2*y*z^2 としたぶなけど、それぞれ(2,2,1)と(2,1,2) で、(2-2,2-1,1-2)=(0,1,-1)となり、確かに最も左の0でない項は1>0ぶな！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑨】 とりあえず、なんか自然に単項式の間に辞書式順序という順序を考えられたぶなけど、これが本当に「単項式順序」になっているか、確認する必要があるぶなねっ！まず、条件①ぶなっ！二つの多項式の次数(a,b,c),(d,e,f)があるとするぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑩】 (a,b,c)-(d,e,f) の最も左の0でない項を考えるぶな！「0でない」項と言っているので、正か負ぶなね。もし、正だった場合(a,b,c)≧(d,e,f)が成り立つぶなっ！もし、負だと(d,e,f)-(a,b,c)の最も左の0でない項が正になるぶなっ

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑪】 よって、この場合,(d,e,f)≧(a,b,c)が成り立つぶなっ！したがって「(a,b,c)≧(d,e,f)または(d,e,f)≧(a,b,c)」が成り立つから、辞書式順序は全順序ぶなっ！次に②を確認するぶな！もう一つの単項式の次数を(g,h,i)とするぶな

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑫】 (a,b,c)≧(d,e,f)を仮定するぶな。{(a,b,c)+(g,h,i)}-{(d,e,f)+(g,h,i)}=(a,b,c)-(d,e,f)なので、この最も左の0でない項は正ぶなから「(a,b,c)+(g,h,i)≧(d,e,f)+(g,h,i)」

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑬】 よって、②はオッケーぶな！（注:最初に書いた単項式順序の定義は2変数の場合で、今は３変数で考えてるぶなよ）最後に③を確認するブナ！(a_1,b_1,c_1)≧(a_2,b_2,c_2)≧…なる次数の無限減少列を考えるぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑭】 整列順序であることを示すには、あるnがあって、...≧(a_n,b_n,c_n)=(a_{n+1},b_{n+1},c_{n+1})=...となればよかったぶなね！つまり、あるところから、真に小さくなることは出来ないことを示せばいいぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑮】 今、xの次数a_mだけを考えるぶな。辞書式順序の定義から、a_1≧a_2≧a_3…が成り立つぶなね（この≧は整数の間の普通の不等号ぶな）。a_m は非負整数ぶなから、あるiで、a_i=a_{i+1}=...になるぶなよ！（確認してみるぶなっ！）

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑯】 この i 以降は、辞書式順序の定義から、b_i≧b_{i+1}≧...になっているぶなから、同じ議論で、あるjでb_j=b_{j+1}=になるぶな！c_j≧c_{j+1}も同様に、あるnでc_n=c_{n+1}=...になるぶなっ！よって、③が示せたぶな！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑰】 ようやく、我々は「辞書式順序」という単項式順序を一つ手にすることができたぶなね！でも実は、多変数の場合、単項式順序は無限に存在するぶなっ！（示せるぶなか？笑）最後に、よく使われる単項式順序を紹介して終わりにするぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑱】 次のような順序≧"を次数付き辞書式順序と呼ぶ (a,b,c) ≧" (d,e,f) ：⇔ a+b+c≧d+e+f または a+b+c=d+e+f かつ 辞書式順序で(a,b,c)≧(d,e,f) これは、まず次数の和で比べ、その後辞書式に比べる順序ぶな

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑲】 最初のx^2*y*z^2,x^2*y^2*z,xyzをこの順序で並べてみても、辞書式順序の時と同じになるぶな。しかし、この順序は次数に重きを置いているので、辞書式では貧弱っ貧弱っな z^100という単項式は、次数付きでは、上の三つよりはるかに強くなるぶな！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例⑳】 次の順序≧*を「次数付き逆辞書式順序」と呼ぶぶな！ (a,b,c)≧*(d,e,f) ：⇔ a+b+c≧d+e+f または a+b+c=d+e+f かつ (a,b,c)-(d,e,f)の最も右の0でない項が負 つまり、次数で比べて逆の辞書で比べるぶなっ！

グレブナー基底大好きbot @groebner_basis

【単項式順序の例㉑】 少し分かりづらいので、同値な定義を書くブナ。 (a,b,c)≧*(d,e,f) ⇔ a≧d かつ a+b≧d+e かつ a+b+c≧d+e+f 対称群の表現のヤング図形を勉強したことがある人は、これと似たようなものを見たことがあるかもぶなね。

グレブナー基底大好きbot @groebner_basis

【訂正】 どうやら同値じゃなさそうなのでこれは忘れてくださいぶな。

グレブナー基底大好きbot @groebner_basis

【単項式順序の例㉒】 この順序で最初の単項式を並べると、x^2*y*z^2,x^2*y^2*z,xyz になるぶなっ！この「次数付き逆辞書式順序」は一見するとすごく変な感じのする単項式順序ぶなけど、実は他の二つに比べグレブナー基底がうまく計算できるので、非常によく使われるものぶな

グレブナー基底大好きbot @groebner_basis

【今日のまとめ】 「人生いろいろ、単項式順序もいろいろ。」 ぶなっ！