演習問題1
lex順序:
a: x3+x2+2x+3y-z2+z, LM(f)=x3,
LT(f)=x3, multideg(f)=(3,0,0)
b: -3x5yz4+2x2y8-xy4+xyz3, LM(f)=x5yz4, LT(f)=-3x5yz4, multideg(f)=(5,1,4)
grlex順序:
a: x3+x2-z2+2x+3y+z,
LM(f)=x3, LT(f)=x3, multideg(f)=(3,0,0)
b: -3x5yz4+2x2y8-xy4+xyz3, LM(f)=x5yz4, LT(f)=-3x5yz4, multideg(f)=(5,1,4)
grevlex順序:
a: x3-z2+x2+z+3y+2x,
LM(f)=x3, LT(f)=x3, multideg(f)=(3,0,0)
b: 2x2y8-3x5yz4+xyz3-xy4, LM(f)=x2y8, LT(f)=2x2y8, multideg(f)=(2,8,0)
演習問題2
a: grlex順序
b: grevlex順序
c: lex順序
演習問題3
lex順序
a: -z2+z+3y+x3+x2+2x, LM(f)=z2,
LT(f)=-z2, multideg(f)=(2,0,0)
b: -3x5yz4+xyz3+2x2y8-xy4, LM(f)=x5yz4, LT(f)=-3x5yz4, multideg(f)=(4,1,5)
grlex順序:
a: x3-z2+x2+z+3y+2x,
LM(f)=x3, LT(f)=x3, multideg(f)=(0,0,3)
b: -3x5yz4+2x2y8+xyz3-xy4, LM(f)=x5yz4, LT(f)=-3x5yz4, multideg(f)=(4,1,5)
grevlex順序:
a: x3+x2-z2+2x+3y+z,
LM(f)=x3, LT(f)=x3, multideg(f)=(0,0,3)
b: 2x2y8-3x5yz4+xyz3-xy4, LM(f)=x2y8, LT(f)=2x2y8, multideg(f)=(0,8,2)
bの全次数5次の2項はgrlexとgrevlexで順序が同じなのか。
演習問題4
(i)
α, β∈ℤn≥0とすると、|α|≠|β|なら、|α|,|β|はℤ≥0の数順序に従い、
これは全順序だから、順序が定まる。
|α|=|β|ならlex順序なので命題4により順序が定まる。
よってgrlex順序は全順序。
(ii)
α, β, γ∈ℤn≥0とし、|α|>grlex|β|とする。
|α|>|β|なら|α+γ|=|α|+|γ|>|β|+|γ|=|β+γ|だから|α+γ|>grlex|β+γ|
|α|=|β|ならlex順序なので命題4により|α+γ|>grlex|β+γ|。
(iii)
grlex順序が整列順序でなかったと仮定する。
全次数はℤ≥0の数順序に従うので整列順序だから、
上の無限狭義減少列で次数がある定まった|α(1)|から、
無限に減少することは出来ない。
故に鳩の巣原理によりある全次数には無限個の元が入り、
これらの元はℤn≥0の同じ全次数の元からなる無限狭義減少列をなす。
ところがgrlex順序では、同じ全次数の元はlex順序で並んでおり、
命題4によりlex順序は整列順序なので、
同じ全次数の無限狭義減少列は存在しないので矛盾。
故にgrlex順序は整列順序。
演習問題5
（定義6の後半のみのルールで順序づける、
次数付きでない逆辞書式順序(revlex順序、演習問題9でいうrinvlex順序)は、
いくらでも大きい全次数の項を後置できるから、整列順序でない。）
(i)
α, β∈ℤn≥0とすると、|α|≠|β|なら、|α|,|β|はℤ≥0の数順序に従い、
これは全順序だから、順序が定まる。
|α|=|β|なら、α-βの0でない一番右の成分は、
全順序であるℤ≥0の数順序に従うから、順序が定まる。
したがってgrevlex順序は全順序。
(ii)
α, β, γ∈ℤn≥0とし、|α|>grevlex|β|とする。
|α|>|β|なら|α+γ|=|α|+|γ|>|β|+|γ|=|β+γ|だから|α+γ|>grevlex|β+γ|。
|α|=|β|のときは、命題4(ii)の証明と同様にして、|α+γ|>grevlex|β+γ|。
(iii)
grevlex順序が整列順序でなかったと仮定する。
このときℤn≥0の元の無限狭義減少列
α(1)>grevlex α(2)>grevlex α(3) >grevlex...が存在する。
全次数はℤ≥0の数順序に従うので整列順序だから、
上の無限狭義減少列で次数がある定まった|α(1)|から、
無限に減少することは出来ない。
故に鳩の巣原理によりある全次数には無限個の元が入り、
これらの元はℤn≥0の同じ全次数の元からなる無限狭義減少列をなす。
すなわちあるlが存在して、i≥lなら|α(i)|=|α(l)|かつα(i)<grevlex α(l)。
ところが文字の数は有限なので、ある定まった|α(l)|に対し、
|α(i)|=|α(l)|なる異なるα(i)の選択の仕方も有限個しかないから、
あるLが存在してi≥Lなら|α(i)|=|α(L)|かつα(i)=α(l)。
これはα(1)>grevlex α(2)>grevlex α(3) >grevlex...が無限狭義減少列であること反する。
したがってgrevlex順序は整列順序。
演習問題6
変数の順序を逆順に置換すれば、lex順序と同じ条件になる。
演習問題7
小問a
定義1(iii)により>は整列順序だから、ℤn≥0は>に関する最小元φを持つ。
φ≠0と仮定すると、0>φなので、定義1(ii)により0+φ=φ>φ+φとなり、
φの最小性に反する。したがってφ=0でなければならない。
故に以下の補題が成り立つ：
α≠0とα>0は同値で、このとき定義1(ii)により、
任意のγ∈ℤn≥0についてα+γ>γ。
逆に任意のγ∈ℤn≥0についてα+γ>γならα≠0だからα>0。
小問b
xαがxβを割り切るなら、
α, β∈ℤn≥0の成分について、βi-αi≥0が全ての1≤i≤nについて成り立つから、
β=α+δなるδ∈ℤn≥0が存在してδi=βi-αi。
故にδ≠0なら小問aの補題によりβ=α+δ>α。
δ=0なら全ての1≤i≤nについてβi=αiだからβ=α。
以上によりβ≥α。
小問c
α>φなるφ∈α+ℤn≥0が存在したとすると、
あるψ∈ℤn≥0が存在してφ=α+ψ。
ψ=0ならα>α+0=αとなり矛盾するからψ≠0。
すると小問aの補題によりψ>0だから、
定義1(ii)によりφ=α+ψ>α+0=αとなり、>が全順序であることと矛盾。
故にα>φなるφ∈α+ℤn≥0は存在しないから、αはα+ℤn≥0の最小元。
演習問題8
えーと、階段形そのものの定義じゃなくて、
階段形だと何が出来るかってことだよね？
(2)の>によって定まる順序の、最も小さい変数の値を決めれば、
その値から順次、より大きい変数の値を決めるアルゴリズムが存在する。
という答えでいいのかな。なんか大雑把すぎる気はするが。
演習問題9
小問a
|α|=|β|のときについて示せば十分。
α>rinvlex βであることは、invlex順序の定義により、
α-βにおいて一番右の0でない項が負であることと同値だから、
|α|=|β|のときのgrevlex順序の順序付けと同値。
小問b
次数付きでないrinvlex順序は、いくらでも大きい全次数を持つ項を後置できるから、
整列順序でないので、単項式順序でない。
演習問題10
ある単項式順序>に対しα>βかつ、
αとβの間に無限個のℤn≥0の元が存在したとすると、
これら無限個の元はすべて互いに等しくないので、
>が全順序であることからαとβの間にℤn≥0の元の無限狭義減少列が存在する。
これは>が整列順序であることに反するから、
αとβの間にはℤn≥0の元は有限個しか存在しない。
したがってgrlex順序でもそうである。
演習問題11
小問a
α, β∈ℤn≥0とし、LT(f)=axα
(a∈k), m=xβとすると、
fの先頭項でない任意の項の単項式xγ (γ∈ℤn≥0)についてα>γなので、
定義1(ii)によりα+β>γ+βだから、LM(mf)=xα+β=xβxα=m·LM(f)。
したがってLT(mf)=axα+β=xβ·axα=m·LT(f)。
小問b
α>βかつγ>δならα+γ>β+γ>β+δだから、
f≠0かつg≠0なら、multideg(LT(f)·LT(g))=multideg(f)+multideg(g)は、
LT(f) ·LT(g)以外の他のすべてのfgの項の多重次数より大きいので、
LT(f·g)= LT(f)·LT(g)。
なおこれより明らかに、f≠0かつg≠0ならLM(f·g)=LM(f)·LM(g)。
f=0またはg=0の時の次数が第1章§1で定義されていないので、
multidegもちゃんと定義されてないと思うが、
f=0ならLT(f)=0と別に定義すればLT(f·g)= LT(f)·LT(g)。
（同じ著者のコックス「ガロワ理論」では、
f=0ならdeg(f)は定義されない流儀を採用しているので、
多分同じ流儀だろうから、LT(0)の定義が別に必要。
LM(0)はたぶん定義できない。）。
小問c
各figi (1≤i≤s)の中で多重次数が最大の項同士が、
∑1≤i≤s figiにおいて全て打ち消しあう場合がありうるので、
一般に等しくならない。
例えば、変数の順序をx>yとしてk[x,y]にlex順序を適用すると、
f1=f2=x+y,
g1=x-y, g2=-x-2y∈k[x,y]なら、
LM(f1)LM(g1)=LM(f2)LM(g2)=x2だが、LM(f1g1+f2g2)=xyなので、
LM(f1g1+f2g2)はLM(f1)LM(g1)ともLM(f2)LM(g2)とも異なる。
演習問題12
小問a
f≠0かつg≠0なら演習問題11小問bによりLM(f·g)=LM(f)·LM(g)だから、
定義7(iii)から補題8(i)は明らか。
multideg(f+g)>max(multideg(f), multideg(g))なら、fとgのいずれかが、
max(multideg(f), multideg(g))より多重次数が大きい項を含まなければならないが、
これはmultideg(f), multideg(g)の定義に反する。
したがってmultideg(f+g)≤max(multideg(f), multideg(g))なので補題8(ii)が示された。
小問b
変数の順序をx>yとしてk[x,y]にlex順序を適用すると、
f=x+y, g=x-yのときmultideg(f)=multideg(g)=(1,0)、
multideg(f+g)=multideg(2x)=(1,0)だから、
max(multideg(f),multideg(g))=multideg(f)=multideg(g)=multideg(f+g)。
f=x+y, g=-x+yのときmultideg(f)=multideg(g)=(1,0)、
multideg(f+g)=multideg(2y)=(0,1)<(1.0)だから、
max(multideg(f),multideg(g))=multideg(f)=multideg(g)>multideg(f+g)。
