1
Groebner
基底
（
2005
年
1
学期現代数学特論）
原 信一郎
[email protected]
http://blade.nagaokaut.ac.jp/˜ hara/
2005
年
7
月
19
日版
3
目次
第1章 代数と幾何 1 1 環と体 . . . 1 2 1変数多項式環 . . . 6 3 イデアルとアフィン多様体. . . 11 第2章 Groebner基底 15 1 順序. . . 16 2 順序に関するディクソンの補題 . . . 17 3 単項式順序と整除 . . . 20 4 ヒルベルトの補題とグレブナ基底 . . . 24 5 グレブナ基底の性質 . . . 25 6 ブッフベルガーのアルゴリズム . . . 27 第3章 Groebner基底の応用 33 1 計算の実例 . . . 33 2 拡張定理 . . . 40 付録 43 1 参考書 . . . 43 2 参考URL . . . 441
第
1
章
代数と幾何
まず最初に代数系の基礎を紹介する。§1
環と体
1.1
環と体の公理
定義 1.1 (環と体) 集合R上に2つの演算 + : R × R → R, (a, b) 7→ a + b · : R × R → R, (a, b) 7→ a · b が定義されているとする。更に 2つの要素0, 1 ∈ R が定められているとする。 これらが、以下の条件（環の公理）を満たしているとき、(R, +, ·, 0, 1)は 環であるという。 (1) 【結合則】 任意のa, b, c ∈ Rについて(a + b) + c = a + (b + c). (2) 【交換則】 任意のa, b ∈ Rについてa + b = b + a. (3) 【零元の存在】任意のa ∈ Rについて a + 0 = a, 0 + a = a. (4) 【負元の存在】 任意のa ∈ Rについて、あるb ∈ Rが存在してa + b = b + a = 0. (5) 【結合則】 任意のa, b, c ∈ Rについて(a · b) · c = a · (b · c). (6) 【単位元の存在】任意のa ∈ Rについてa · 1 = a, 1 · a = a. (7) 【分配則】 任意のa, b, c ∈ Rについてa · (b + c) = a · b + a · c, (a + b) · c = a · c + b · c. 更に (8) 【交換則】 任意のa, b ∈ Rについてa · b = b · a. が成り立つならば、 可換環であると言う。 また、更に (9) 【逆元の存在】 任意のa ∈ Rについて、a 6= 0ならば、あるb ∈ Rが存在してa · b = b · a = 1. が成り立つならば、 体であると言う。 記法 1 (1) +, ·をRの加法、乗法と呼ぶ。 (2) 0, 1をRの零元、単位元と呼ぶ。 (3) a · bはしばしば·を省略してabと書く。 (4) 定義1.1の(4)のbをaの負元と言い、−aと書く。 (5) a + (−b)をa − bと書く。 (6) 定義1.1の(9)のbをaの逆元と言い、a−1 と書く。(7) a · b−1 をa/bと書く。 注 1 (1) この文書では「環」といえば「可換環」を指すことにする。 (2) 環(R, +, ·, 0, 1) を単にR と書くことがある。 命題 1.2 (環の性質) Rを環とするとき以下が成り立つ。 (1) Rの零元は一意的である。 (2) Rの単位元は一意的である。 (3) a ∈ Rの負元は一意的である。 (4) a ∈ Rの逆元は存在すれば一意的である。 (5) a · 0 = 0. (6) a · (−b) = −(a · b). 例 1 (環と体の例) (1) 【整数環】(Z, +, ·, 0, 1). (2) 【有理数体】(Q, +, ·, 0, 1). (3) 【実数体】(R, +, ·, 0, 1). (4) 【複素数体】(C, +, ·, 0, 1). (5) (Z[√d], +, ·, 0, 1)、ただし、dを整数とする。 (6) 【多項式環】(k[x1, x2, · · · , xn], +, ·, 0, 1). ただし kを環とする。（以下同様） (7) 【正方行列環】(Mn(k), +, ·, O, E)（非可換）. (8) 【対角行列環】(Dn(k), +, ·, O, E). (9) A2= {a, b} + a b a a b b b a · a b a a a b a b において、0 = a, 1 = bとしたもの。 (10) A4= {a, b, c, d} + a b c d a a b c d b b c d a c c d a b d d a b c · a b c d a a a a a b a b c d c a c a c d a d c b において、0 = a, 1 = bとしたもの。
1.2
準同型
記法 2 • 今後kで任意の体（例Q, R, C）を表す。 • {a, b, c} : 順序のない集合。 • (a, b, c) : 順序のある集合。 • 論理記号 ∀x · · · : 任意のxについて· · ·。 ∃x · · · : あるxについて· · ·。 P =⇒ Q : P ならば Q。 P ⇐⇒ Q : P とQは同値。 P ∨ Q : P または Q。 P ∧ Q : P かつQ。 定義 1.3 (全射と単射) f : X → Y を写像とするとき、 (1)「∀y ∈ Y ∃x ∈ Xf (x) = y」が成り立つ時、f は 全射であるという。 (2)「∀x, x0∈ X(x 6= x0 ⇒ f (x) 6= f (x0))」が成り立つ時、f は 単射であるという。 (3) f が全射でかつ単射であるときf は 全単射といういう。1 環と体 3 定義 1.4 (準同型) R, S を環とし、写像f : R → Sに対して次の条件が成り立つとき、f はRからS への準同型 写像という。 (1) ∀a, b ∈ R f (a + b) = f (a) + f (b) (2) ∀a, b ∈ R f (a · b) = f (a) · f (b) (3) f (1) = 1 また更にf が全単射であるとき、f はR からS への 同型写像であるという。環Rと S の間に少なくとも一つ同 型写像がある時、RとS は 同型 であるといい、R ∼= Sと書く。 命題 1.5 f : R → S を環の準同型とするとき以下が成り立つ。 (1) f (0) = 0. (2) f (−a) = −f (a). (3) f (a−1) = f (a)−1, (a−1が存在するとき). (4) f が同型ならf−1 も同型。 代数学は同型で不変な性質を研究する。 例 2 (1) 任意の環Rについて、その恒等写像i : R → R, x 7→ xは同型。 (2) f : A2→ A4, f (a) = a, f (b) = cは単射準同型。 (3) g : A4→ A2, g(a) = a, g(b) = b, g(c) = a, g(d) = bは全射準同型。 定義 1.6 (部分環) (R, +, ·, 0, 1) を環、S がその部分集合で、同じ+, ·, 0, 1で環になっているとき、S をRの 部分環 という。このとき恒等写像j : S → R, x 7→ x は準同型であり、これを 包含写像あるいは 埋め込み写像と いう。 例 3 (1) ZはQの部分環。 (2) QはRの部分環。 (3) RはCの部分環。 (4) Dn(k)はMn(k)の部分環。
1.3
イデアルと剰余環
定義 1.7 (イデアル) R を環、I をその空でない部分集合で、次の条件を満たすとき、I はR のイデアルであると いう。 (1) ∀x, y ∈ I x + y ∈ I. (2) ∀x ∈ R ∀y ∈ I x · y ∈ I. 例 4 (1) Rと{0}はR のイデアル。これらを 自明なイデアルという。 (2) nZ = {n · m | m ∈ Z}はZのイデアル。 (3) A4 の中でI = {a, c}はイデアルである。 (4) 多項式環R = k[x]の中で、x2+ 1 の倍数の集合I = <x2+ 1>はイデアルである。 (5) Rの部分環S がR のイデアルならR = S である。 (6) Rが体ならそのイデアルは自明なものしかない。 定義 1.8 SをR の部分集合とするとき <S> = {x ∈ R | s1, s2, · · · , sn∈ S とr1, r2, · · · , rn∈ Rが存在してx = r1s1+ r2s2+ · · · + rnsn}とおき、これを S で 生成されたイデアルという。S = {s1, s2, · · · , sk} と有限集合であるとき、<S> を単に <s1, s2, · · · , sk>あるいはRs1+ Rs2+ · · · + Rsk と書く。一つの要素で生成されるイデアル<a> = Ra を 単項 イデアルという。 注 2 < S >はRのイデアルである。 例 5 Zでは、<n> = nZ。 定義 1.9 (剰余類) Rを環、I をそのイデアルとするとき、a ∈ Rに対して [a] = {x ∈ R | x − a ∈ I} と書き、これをaの 剰余類と呼ぶ。また、全ての剰余類の集合(剰余集合)を R/I = {[a] | a ∈ R} と書く。 注 3 [a] = {a + x ∈ R | x ∈ I}であるので、これをa + I と書くことがある。 例 6 (剰余類の例) (1) Z/2Z = {[0], [1]}, [0] = {· · · , −2, 0, 2, 4, · · · }, [1] = {· · · , −1, 1, 3, 5, · · · }. (2) Z/4Z = {[0], [1], [2], [3]}, [0] = {· · · , −4, 0, 4, 8, · · · }. (3) k[x]/<x2+ 1>, [0] = {a(x2+ 1) ∈ k[x] | a ∈ k}. 命題 1.10 (剰余類の性質) 以下の条件は全て同値である。 (1) a − b ∈ I. (2) [a] ∩ [b] 6= φ. (3) [a] = [b]. (4) a ∈ [b]. 定義 1.11 (1) xを剰余類x ∈ R/I とするとき、a ∈ xとなる aをxの 代表元 という。
(2) a1, a2, · · · ∈ Rについて、[a1] ∪ [a2] ∪ · · · = R かつ、各 [a1], [a2], · · · に交わりがないとき、{a1, a2, · · · }
をR/I の 代表系という。 (3) 写像π : R → R/I, a 7→ [a]を 標準射影 という。 例 7 (代表系の例) (1) {0, 1}はZ/2Zの代表系である。 (2) {0, 1, 2, 3}はZ/4Zの代表系である。 (3) {a + bx ∈ k[x] | a ∈ k, b ∈ k}はk[x]/<x2+ 1>の代表系である。 定義 1.12 (剰余環) Rを環、I をそのRと異なるイデアルとするとき、R/I に演算+, ·と元0, 1を次のように定 義する。(これを 剰余環という。) (1) x + y = [a + b]だだし、a ∈ x, b ∈ y とする。 (2) x · y = [a · b]だだし、a ∈ x, b ∈ y とする。 (3) 0 = [0]とする。 (4) 1 = [1]とする。
定理 1.13 (R/I, +, ·, 0, 1)は環をなす。標準射影π : R → R/I, a 7→ [a]は準同型である。
例 8 (剰余環の例) (1) Z/2Z = {[0], [1]}, + [0] [1] [0] [0] [1] [1] [1] [0] · [0] [1] [0] [0] [0] [1] [0] [1]
1 環と体 5 (2) Z/4Z = {[0], [1], [2], [3]}, + [0] [1] [2] [3] [0] [0] [1] [2] [3] [1] [1] [2] [3] [0] [2] [2] [3] [0] [1] [3] [3] [0] [1] [2] . · [0] [1] [2] [3] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [2] [0] [2] [0] [2] [3] [0] [3] [2] [1] . (3) R[x]/<x2+ 1> = {a + bi | a, b ∈ R}, i = [x]. 0 = 0 + 0i, 1 = 1 + 0i,
(a + bi) + (c + di) = (a + c) + (b + d)i, (a + bi) · (c + di) = (ac − bd) + (ad + bc)i. 定義 1.14 (核, 像) f : R → Sを環の準同型とするとき、 (1) Imf = {f (x) ∈ S | x ∈ R}をf の 像(image)という。 (2) Kerf = {x ∈ R | f (x) = 0}をf の 核(kernel)という。 命題 1.15 (1) Imf はS の部分環である。 (2) Kerf はRのイデアルである。 定理 1.16 (準同型定理) f : R → Sを環の準同型とするとき、 f : R/Kerf → Imf, [a] 7→ f (a). は同型写像である。 [証明]証明すべき事は(1) well-defined、(2)全射、(3)単射、(4)準同型性である。¤ 系 1.17 (1) Z/2Z ∼= A2. (2) Z/4Z ∼= A4. (3) R[x]/<x2+ 1> ∼= C.
1.4
素イデアルと極大イデアル
定義 1.18 (整域) 環Rが次の条件を満たすとき、 整域という。 ∀a, b ∈ R a · b = 0 =⇒ a = 0 ∨ b = 0. 定理 1.19 体は整域である。 定義 1.20 (素イデアル) Rと異なるイデアルI ⊂ Rが次の条件を満たすとき、 素イデアルという。 ∀a, b ∈ R a · b ∈ I =⇒ a ∈ I ∨ b ∈ I. 命題 1.21 イデアルI ⊂ Rに対して R/I が整域であるための必要十分条件はI が素イデアルことである。 例 9 (1) R = Z, I = 3Zのとき、I は素イデアル。 (2) R = Z, I = 4Zのとき、I は素イデアルでない。 定義 1.22 (極大イデアル) R と異なるイデアルI ⊂ Rが次の条件を満たすとき、 極大イデアルという。 I ⊂ J ⊂ RとなるイデアルJ はJ = IまたはJ = Rのみである。定理 1.23 剰余環 R/I が体である必要十分条件はI が極大イデアルであることである。 [証明]
•（必要性）R/I 6= {0} より R 6= I。また、J を I より真に大きい R のイデアルとする。a ∈ J − I をと
るとa 6∈ I なので、 [a] 6= 0ここで R/I が体であることから[a] の逆元 [b]が存在する。[a][b] = [1] より
[ab − 1] = 0ゆえに ab − 1 ∈ I ⊂ J。一方ab ∈ J であるから、1 ∈ J が言える。よってJ = R。
•（十分性）I が極大イデアルだと仮定する。I 6= R よりR/I は環である。今、[a] ∈ R/I, [a] 6= 0 を任意にと
ると、a 6∈ Iより<a, I> = R。よってあるr ∈ Rとs ∈ I でra + s = 1となる。このとき、[r][a] = [1] = 1
すなわち[r]は[a]の逆元となっている。 ¤ 例 10 (極大イデアルの例) (1) 3ZはZの極大イデアル。よってZ/3Zは体。 (2) R[x]/<x2+ 1> ∼= Cは体。よって<x2+ 1>はR[x]の極大イデアル。 定義 1.24 pを素数とするとき、Z/pZを Fp と書き、標数pの 素体という。 系 1.25 極大イデアルは素イデアルである。 定義 1.26 (単元, 可逆元) 環Rの要素で逆元を持つものを 単元あるいは 可逆元 という。単元全体をR× と書く。 注 4 (1) Rが体 ⇐⇒ R×= R − {0}。 (2) Rが体 ⇒ (R[x])×= R×。
§2
1
変数多項式環
2.1
定義
今後kは体とする。実際にはk = Q, R, Cと思っていてよい。 定義 2.1 (多項式環) k[x] = {amxm+ am−1xm−1+ · · · + a0 | ∀i ai ∈ k, m ∈ N} に通常の和と積を定義したもの を、(1変数)多項式環という。 注 5 N = Z≥0 = {0以上の整数}. 定義 2.2 多項式 f = amxm+ am−1xm−1+ · · · + a0, (am6= 0)について、次のように定義する。 • deg(f ) = m · · · 次数(degree) • LC(f ) = am · · · 先頭係数(leading coefficient) • LM(f ) = xm · · · 先頭単項式(leading monomial) • LT(f ) = amxm · · · 先頭項(leading term) • RT(f ) = f − LT(f ) · · · 残余(rest term) 命題 2.3 f, g 6= 0について (1) deg(f g) = deg(f ) + deg(g).(2) f + g 6= 0 ⇒ deg(f + g) ≤ max{deg(f ), deg(g)}.
2 1変数多項式環 7
2.2
割り算アルゴリズム
定義 2.4 (整除) f, g ∈ k[x], g 6= 0とする。あるq ∈ k[x]が存在してf = g · q となるときg はf を 割り切ると いい、g|f と書く。また、q = f /gと書き、これをf のgによる 商と言う。 補題 2.5 f, g 6= 0とする。 (1) deg(g) ≤ deg(f ) ⇐⇒ LT(g)|LT(f ). (2) deg(g) ≤ deg(f ), h = f −LT(f ) LT(g)g ⇒ h = 0 ∨ (h 6= 0 ∧ deg(f ) > deg(h)). 定理 2.6 (割り算アルゴリズム) f, g ∈ k[x], g 6= 0 とする。f のg による 割り算とは次の条件を満たすものであ り、以下に述べるアルゴリズムで得ることができる。 (1) f = g · q + r, q, r ∈ k[x]. (2) r = 0 ∨ (r 6= 0 ∧ deg r < deg g). Input : f, g Output : q, r q := 0; r := f WHILE r != 0 AND LT(g) | LT(r) DO q := q + LT(r) / LT(g) r := r - ( LT(r) / LT(g) ) * g また、(1), (2)を満たすq, rは一意である。 例 11 f = x3+ 2x2+ x + 1をg = 2x + 1 で割る過程を示す。 1/2x^2 + 3/4x + 1/8 ... 商 ---2x + 1 |x^3 + 2x^2 + x + 1 x^3 + 1/2x^2 ---3/2x^2 + x + 1 3/2x^2 + 3/4x ---1/4x + 1 1/4x + 1/8 ---7/8 ... 余り 定義 2.7 (商と余り) 上のアルゴリズムで求めたq, rに対し、qを 商と言い、f div g あるいはquotient(f, g)と書 く。また、rを 余りあるいは 剰余と言い、f mod gあるいはramainder(f, g)と書く。 [証明][定理2.6]略。¤ 系 2.8 g|f ⇐⇒ f mod g = 0. [証明] ⇐ は明らか。⇒ は、定理2.6の一意性より得られる。¤ 系 2.9 (因数定理) (1) f mod (x − a) = f (a). (2) (x − a)|f ⇐⇒ f (a) = 0. 系 2.10 (根の数) f (x) = 0の根の数はdeg f 以下である。 定理 2.11 (1変数多項式環のイデアルの性質) k[x]の任意のイデアルは単項イデアルである。[証明] Iをk[x]の{0}でない任意のイデアルとする。I − {0}の中でdegが最小のものをhとすると、I = <h>で ある。なぜなら、<h> ⊂ I は明らか。I ⊂ <h>は、任意のf ∈ I について、r = f mod hとすると、r ∈ I。もし
r 6= 0 なら、deg r < deg hとなってdeg hの最小性に矛盾。よってr = 0がいえるから h|f。すなわちf ∈ <h>。
すなわちI ⊂ <h>。¤
定義 2.12 (単項イデアル整域, PID) 任意のイデアルが単項イデアルである整域を単項イデアル整域あるいは、PID
(Principal Ideal Domain)と言う。
2.3 GCD
定義 2.13 f, g ∈ k[x]について、f, g の 最大公約数GCD(f, g) (gratest common devisor)とは、以下の条件を 満たす hのことを言う。 (1) h|f, h|g. (2) ∀p (p|f, p|g ⇒ p|h). 定理 2.14 (ユークリッドの互除法) f, g ∈ k[x]について以下が成り立つ。 (1) GCD(f, g)が存在してk[x]の単元を除いて一意である。 (2) <f, g> = <GCD(f, g)>. (3) 次のアルゴリズムでGCD(f, g)を求める事ができる。 Input : f, g Output : h h := f s := g WHILE s != 0 DO r := remainder(h, s) h := s s := r [証明] (1), (2): イデアル<f, g>は単項イデアルなので、<f, g> = <h>となるhが存在する。このhはfとg のGCD である。なぜなら、f, g ∈ <h>より、h|f, h|g。また、もしp|f, p|g ならば、<f, g> ⊂ <p>。よって p|h。また、h, h0 がGCDならh|h0かつh0|hなので、h0 はhの単元倍しか違わない。 (3): 略。¤ 例 12 (1) GCD(x4− 1, x6− 1) = x2− 1. (2) GCD(x5+ 2x3+ x, x4+ x2− x) = x. 定義 2.15 (素) f, g ∈ k[x] が素であるとは、「h|f かつ h|g ならば h は単元」が言える事である。すなわち、 GCD(f, g) が単元であることである。すなわち、deg GCD(f, g) = 0であることである。 定理 2.16 f, g, h ∈ k[x]について、 f |g · hかつf とgが素、ならばf |h となる。 [証明] 1 = af + bgとなるa, b ∈ k[x]があるので、f |ghよりf |bgh = (1 − af )h = h − af h。よってf k = h − af h となる kが存在する。このとき、f · (k + ah) = hすなわち、f |h。¤
2 1変数多項式環 9
定理 2.17 (拡張されたユークリッドの互除法) f, g ∈ k[x]について、
af + bg = GCD(f, g)
となる a, bが
deg a < deg g − deg GCD(f, g), deg b < deg f − deg GCD(f, g).
という条件の下でただ一組存在する。また、a, bは以下のアルゴリズムで求める事ができる: Input : f, g (!= 0) Output : h, a, b h, s := f, g a, b, c, d = 1, 0, 0, 1 WHILE s != 0 DO q := quotient(h, s) r := h - qs r0 := a - qc r1 := b - qd h, s := s, r a, c := c, r0 b, d := d, r1 [証明]（略）¤ 例 13 (1) f = x4− x2, g = x3− 1について、GCD(f, g) = x − 1 = (x + 1)f + (−x2− x − 1)g. x ---x^3-1 | x^4-x^2 x^4 - x -x - 1 --- ---x^2+x | x^3 - 1 x^3-x^2 ---x^2 - 1 x^2 - x -x ---x - 1 | ---x^2 + ---x -x^2 + x ---0 a: x b: x --- --0| 1 1 | 0 0 -x -1 x -x - 1 - --- -- ---1 | 0 -x | 1 -x -1 x^2 + x --- ---x + 1 -x^2-x-1 (2) f = x4− 1, g = x6− 1 について、GCD(f, g) = x2− 1 = x2· f + 1 · g. (3) f = x5+ 2x3, g = x4+ x2− x について、GCD(f, g) = x = x2· f + (−x3− x − 1) · g. 定義 2.18 f1, f2, · · · , fsのGCDは次の条件を満たす hである。
(1) h|f1, f2, · · · , fs. (2) p|f1, f2, · · · , fs ⇒ p|h. このhをGCD(f1, f2, · · · , fs)と書く。 定理 2.19 s ≥ 0, f1, f2, · · · , fs∈ k[x]について以下が成り立つ。 (1) GCD(f1, f2, · · · , fs)は存在し、単元を除いて一意的。 (2) <GCD(f1, f2, · · · , fs)> = <f1, f2, · · · , fs>. (3) GCD(f1, f2, · · · , fs) = GCD(f1, GCD(f2, · · · , fs)). (4) GCD(f1, f2, · · · , fs)を求めるアルゴリズムがある。 [証明] (1), (2): k[x]のイデアル<f1, f2, · · · , fs>は単項イデアルで、その生成元をhとすれば、定理2.14と 同じ。 (3), (4): h = GCD(f2, · · · , fs)とすると、(2)より<h> = <f2, · · · , fs>なので、<f1, h> = <f1, <h>> = <f1, <f2, · · · , fs>> = <f1, f2, · · · , fs>である。GCDの一意性よりGCD(f1, h) = GCD(f1, f2, · · · , fs)。 また、これはGCD(f1, f2, · · · , fs)を求めるアルゴリズムを与えている。¤ 例 14 GCD(x3− 3x + 2, x4− 1, x6− 1) = GCD(x3− 3x + 2, x2− 1) = x − 1. 例 15 (イデアルへの所属問題) x3+ 4x2+ 3x − 1 は <x3− 3x + 2, x4− 1, x6− 1> に属するか？【解答】 x3+ 4x2+ 3x − 1をx − 1 で割った余りが7なので、属さない。
2.4
既約元と素元
定義 2.20 (既約元) a ∈ Rについて、「aの約数は自分自身か1 のみ」のとき、すなわち「a = bc, (b, c ∈ R)なら ばbまたは cは単元」となるとき、aを 既約元という。 例 16 Zにおける既約元とは素数のことである。 命題 2.21 R = Zあるいはk[x] (kは体)とする。p ∈ Rが既約元なら、R/<p>は体である。 [証明] [f ] ∈ R/<p>, [f ] 6= 0とする。p|f ではないので、GCD(f, p) = 1である。（なぜなら、h = GCD(f, p)と すると、h|p, h|f。h|pよりh = 1またはh = p。h = pとするとp|f で矛盾。よってh = 1。）よってaf + bp = 1 となる a, b ∈ Rが存在する。このとき[a][f ] = 1よって[f ] は[a] の逆元になっている。¤ 例 17 F7= Z/7Zで3の逆数をもとめる。 ユークリッドの互除法より、7 + (−2)3 = 1。よって3−1= −2 = 5。 例 18 Q[x]/<x2− 2>でx2+ x + 1 の逆数を求める。 (x − 2)(x2− 2) + (−x + 3)(x2+ x + 1) = 7. よって[x2+ x + 1]−1 =1 7[−x + 3]。 このことから、√ 1 22+√2 + 1 = 1 7(− √ 2 + 3).定義 2.22 (素元) p ∈ Rについて「p|(ab), (a, b ∈ R)ならばp|aまたはp|b」となるとき、pを 素元という。 命題 2.23 pが素元であることと<p>は素イデアルであることは、同値である。
3 イデアルとアフィン多様体 11
[証明] pを素元、p = abとする。p|aまたはp|bなのでp|aとすれば、p = auとなるu ∈ R が存在する。p = pub
よって p(1 − ub) = 0よってub = 1 すなわちbは単元である。p|bの時も同様。¤ 命題 2.25 P IDにおいて、既約元は素元である。 [証明] pを既約元とし、p|abとする。p|aでないとすれば、GCD(p, a) = 1よりあるk, lが存在してpk + la = 1 よって pkb + lab = bまたp|abよりp|左辺 すなわちp|b。p|bの場合も同様。以上よりpは素元である。¤ 注 6 上の命題より、k[x]においては既約元と素元は一致する。（実はk[x1, x2, · · · , xn]においても既約元と素元は 一致する。） 例 19 Z[√−5] = {a+b√−5 | a, b ∈ Z}では2, 3, 1+√−5, 1−√−5は既約元であるが、2·3 = (1+√−5)(1−√−5) なので、どれも素元ではない。つまりZ[√−5]はP IDでない。
§3
イデアルとアフィン多様体
記法 3 (集合の直積) • X × Y = {(x, y) | x ∈ X, y ∈ Y } • X × Y × Z = {(x, y, z) | x ∈ X, y ∈ Y, z ∈ Z} • (X × Y ) × Z = X × (Y × Z) = X × Y × Z とみなす。 • Xn = {(x1, x2, · · · , x n) | xi∈ X} • f : Xn→ Y, x = (x 1, x2, · · · , xn)に対してf (x) = f (x1, x2, · · · , xn)と書く。 定義 3.1 (アフィン多様体) nを自然数、k を体とする。f1, f2, · · · , fs∈ k[x1, x2, · · · , xn]に対して V(f1, f2, · · · , fs) = {a ∈ kn| fi(a) = 0 (1 ≤ i ≤ s)} をf1, f2, · · · , fsで定義されたアフィン多様体という。 例 20 (1) V(x2+ y2− 1). -1 -0.5 0.5 1 -1 -0.5 0.5 1 (2) V(xy − x3+ 1). -3 -2 -1 1 2 3 -1 1 2 3 (3) V(y2− x3). -2 -1 1 2 -2 -1 1 2(4) V(y2− x3− x2). -1 -0.5 0.5 1 -1 -0.5 0.5 1 (5) V(z − x2− y2). -2 -1 0 1 2 -2 -1 0 1 2 0 2 4 6 8 -2 -1 0 1 2 -2 -1 0 1 2 (6) V(z2− x2− y2). -2 -1 0 1 2 -2 -1 0 1 2 0 1 2 -2 -1 0 1 2 -2 -1 0 1 2 (7) V(x2− y2z2+ z3). fi (8) V(x + y + z, x − z, 2x + w). (9) V(xz, yz). (10) V(y − x2, z − x3). 0 0.25 0.5 0.75 1 0 0.25 0.5 0.75 1 0 0.25 0.5 0.75 1 0 0.25 0.5 0.75 1 0 0.25 0.5 0.75 1 命題 3.2 V, W ⊂ kn がアフィン多様体ならV ∩ W, V ∪ W もアフィン多様体である。 [証 明] 例 と し て V = V(f1, f2), W = V(g1, g2) と す る と 、V ∩ W = V(f1, f2, g1, g2), V ∪ W = V(f1g1, f1g2, f2g1, f2g2)となる。¤ } 問い (1) V(f1, f2, · · · , fs) 6= φの判定。（連立1次方程式での解の存在） (2) 解を求めるアルゴリズムは存在するか？（連立1次方程式での掃きだし法と基底） (3) 次元の定義と決定（行列のランク） 定義 3.3 (基底,有限生成) 環R のイデアルI が集合S で生成されているとき、S をI の 基底 という。基底とし て有限集合が取れるイデアルは 有限生成 であるという。
3 イデアルとアフィン多様体 13
定義 3.4 イデアル I ⊂ k[x1, x2, · · · , xn]に対し次のように定義し、I で定義された多様体という。
V(I) = {a ∈ kn| f (a) = 0 (∀f ∈ I)}.
命題 3.5 V(<f1, f2, · · · , fs>) = V(f1, f2, · · · , fs). したがってkn の部分集合がアフィン多様体であることと 有限生成イデアルで定義された多様体であることは同値である。 [証明] fi ∈ <f1, f2, · · · , fs> なので、a ∈ V(<f1, f2, · · · , fs>) なら a ∈ V(f1, f2, · · · , fs)。すなわち V(<f1, f2, · · · , fs>) ⊂ V(f1, f2, · · · , fs)は明らか。逆にすべての i についてfi(a) = 0 とすれば、全ての f =Pcifi ∈ <f1, f2, · · · , fs>について、f (a) = ( P cifi)(a) = P cifi(a) = 0。よってV(f1, f2, · · · , fs) ⊂ V(<f1, f2, · · · , fs>)。¤
例 21 <2x2+3y2−11, x2−y2−3> = <x2−4, y2−1>なので、V(2x2+3y2−11, x2−y2−3) = V(x2−4, y2−1) =
{(±2, ±1)}。つまりこれは、図形をイデアル（の基底）で考える方法を与えている。
定義 3.6 S ⊂ kn を部分集合とするとき
I(S) = {f ∈ k[x1, x2, · · · , xn] | f (a) = 0 (∀a ∈ S)}.
と定義し、これをS の零化イデアルという。 補題 3.7 I(S)はk[x1, x2, · · · , xn]のイデアルである。 [証明]略。¤ 例 22 (1) k2でI({(0, 0)}) = <x, y>。 (2) kn でI(kn) = {0}となるか？ • k が無限体なら、I(kn) = {0}（命題3.12）。 • k = F2 のときI(k) = <x(x − 1)>。 (3) I(φ) = k[x1, x2, · · · , xn]. 以下、 V : {イデアル} −→ {多様体}. I : {多様体} −→ {イデアル}. の関係を調べる。 補題 3.8 (V とI の性質) (1) V ⊂ W ⇒ I(V ) ⊃ I(W ) （V, W はkn の部分集合） (2) I ⊂ J ⇒ V(I) ⊃ V(J) （I, J はk[x1, x2, · · · , xn]のイデアル） (3) V ⊂ V(I) ⇐⇒ I(V ) ⊃ I （V はkn の部分集合、Iはk[x1, x2, · · · , x n]のイデアル）
[証明] (1), (2)は明らか。(3)は、V ⊂ V(I) ⇐⇒ ∀a ∈ V ∀f ∈ I f (a) = 0 ⇐⇒ ∀f ∈ I ∀a ∈ V f (a) = 0 ⇐⇒ I(V ) ⊃ I. ¤
命題 3.9 任意のイデアルI ⊂ k[x1, x2, · · · , xn]について
I ⊂ I(V(I)).
[証明] V(I) ⊂ V(I)なので、補題3.8(3)をV = V(I)として適用して、I(V(I)) ⊃ I。¤
• 成り立つ例：R3でI = <y − x2, z − x3>とおく。I(V(I)) ⊂ Iを示す。f ∈ I(V(I)) = I(V(y − x2, z − x2)) とすると、あるh1, h2∈ R[x, y, z], r ∈ R[x]を用いてf = h1(y − x2) + h2(z − x3) + rと書ける。（なぜな
ら、一般にxαyβzγ = xα(x2+ (y − x2))β(x3+ (z − x3))γ と書いて右辺を展開すればよいから。)
よって、V(I)のパラメータ表示(x, y, z) = (t, t2, t3) t ∈ Rを用いると、r(t) = 0 (∀t ∈ R)。よってr = 0。
• 成り立たない例: R2でI = <x2, y2>とおくと、V(I) = {(0, 0)}なので、I(V(I)) = I({(0, 0)}) = <x, y>。
• k が代数的閉体（任意の1変数の方程式が解を持つ体）なら、I(V(I)) =√Iが成り立ち、これを強形の零点 定理という。ただし√I = {f ∈ k | ∃n ∈ Z≥0 fn∈ I}。
命題 3.10 任意のアフィン多様体V ⊂ kn について
V = V(I(V )).
[証明] V ⊂ V(I(V ))であること: I(V ) ⊂ I(V ) に補題3.8(3)をI = I(V )として適用すると、V ⊂ V(I(V ))。
V ⊃ V(I(V )) であること: V はアフィン多様体なので V = V(I) となるイデアルI がある。命題3.9より、
I ⊂ I(V(I)) であり、補題3.8(2)より、V(I) ⊃ V(I(V(I)))。すなわちV ⊃ V(I(V ))。¤
命題 3.11 V, W をアフィン多様体とする。
(1) V ⊂ W ⇐⇒ I(V ) ⊃ I(W ). (2) V = W ⇐⇒ I(V ) = I(W ).
(3) I : {アフィン多様体} → {イデアル} は単射。 [証明] (1) ( ⇒ ) 補題3.8(1)より。
( ⇐ ) I(V ) ⊃ I(W )とする。両辺にVをすると、補題3.8(2)よりV(I(V )) ⊂ V(I(W ))。V, W はアフィン多様 体なので、命題3.10よりV ⊂ W。 (2)は(1)より明らか。(3)は(2)より明らか。¤ 命題 3.12 kが無限体ならI(kn) = {0}。 [証明] n = 1のとき: ∀a ∈ k f (a) = 0ここでもしf = 0でなければ、因数定理（系2.9）より任意のx − aを因数 に持つことになり、矛盾する。よってf = 0。 n = t のときOKとし、n = t + 1 のときを考える。x = (x1, x2, · · · , xt), y = xt+1 とおく。f ∈ I(kt+1)
は f = Pnfn(x)yn, fn ∈ k[x1, x2, · · · , xn] と書ける。a = (a1, a2, · · · , at) ∈ kn を一つ取り、F (y) =
P
nfn(a)yn ∈ k[y]と置くと、∀b ∈ k F (b) = 0。よって1変数の場合になりF = 0。すなわち∀n fn(a) = 0。aは
任意だったからn = tの場合の仮定よりfn= 0。よってf = 0。¤
} 問い
• イデアルはいつ有限生成になるか？（いつでも）
• f ∈ <f1, f2, · · · , fs>の決定アルゴリズムはあるか？（ある）
15
第
2
章
Groebner
基底
次のような問題を考えよう： 2次正方行列A, Bがあるとする。「AB = EならばBA = E」を示せ。 これは、もちろん線形代数学の知識があれば「AB = E だから、B = A−1。よって、BA = A−1A = E。」と答え るだろう。しかし、これはかなり高度な知識であるし、行列の各成分が体の元であることを仮定しているという点 で間違いとも言える。この問題を具体的に書いてみよう。A = Ã a b c d ! , B = Ã e f g h ! と置くとすれば、問題は AB − E = Ã ae + bg − 1 af + bh ce + dg cf + dh − 1 ! = 0からBA − E = Ã ae + cf − 1 be + df ag + ch bg + dh − 1 ! = 0を導けというこ とだ。 これは純粋に多項式の話であり、中学校の知識で間に合うはずだ。そして証明は、多項式の範囲で、つまり割り算 を用いないで得られるに違いない。 しかし、そういう証明を考えようとすれば、かなり手間と時間がかかり、余程の計算上手でも手に余るだろう。ま た、結局線形代数で行われた議論をうまく分母を払って焼きなおしたようなものになってしまうだろう。 ところが最近はこの程度のことなら計算機がしてくれる: require "algebra" P = MPolynomial(Rational) a,b,c,d,e,f,g,h = P.vars("abcdefgh") M = SquareMatrix(P, 2) A, B = M[[a,b],[c,d]], M[[e,f],[g,h]] C, D = A*B - 1, B*A - 1 F = C.flatten cb = Groebner.basis_coeff(F) puts "F = #{F.inspect}" D.each do |row| row.each do |g| q, r = g.div_cg(F, cb)puts "#{g} = #{q.inspect} * F" if r.zero? end end このプログラムで得られる出力は次のようなものだ。 F = [ae + bg - 1, af + bh, ce + dg, cf + dh - 1] ae + cf - 1 = [dh, -dg, af, -ae + 1] * F be + df = [-df, de, bf, -be] * F ag + ch = [-ch, cg, ah, -ag] * F bg + dh - 1 = [-dh + 1, dg, -af, ae] * F
これはすなわち次のような恒等式が成り立っていることを示している。
ae + cf − 1 = dh · (ae + bg − 1) − dg · (af + bh) + af · (ce + dg) + (−ae + 1) · (cf + dh − 1)
be + df = −df · (ae + bg − 1) + de · (af + bh) + bf · (ce + dg) − be · (cf + dh − 1)
ag + ch = −ch · (ae + bg − 1) + cg · (af + bh) + ah · (ce + dg) − ag · (cf + dh − 1)
bg + dh − 1 = (−dh + 1) · (ae + bg − 1) + dg · (af + bh) − af · (ce + dg) + ae · (cf + dh − 1)
これはまさにAB = E という式からBA = E が「書ける」ことを示している。良く見ると左辺は2次式なのに、右 辺では一度4次式にまで持ち上げて計算している。しかし、一度このような式が得られれば、式の証明は展開、整理 するだけだから、容易に証明可能なのだ。すなわち、計算機はブラックボックスではあるが、純粋に発見的な推論に のみ用いられ、数学的厳密さを損なわせることはない。 かつては、このような式変形は「ひらめき」が必要な一種の職人芸であり、計算の達人にのみが可能な高度な技で あった。しかし、今では計算機が１秒もかからずにやってしまうのである。 さて、こうしてみると次のような疑問をもつだろう。「計算機の中で何が行われているのか？」、「この問題が解けた のは偶然なのか？」回答はこうである。「この手の問題を解くアルゴリズムが存在する。」「『この手の問題』が厳密に 定義でき、解けるなら必ず解くことができる。」つまり、背景には式変形に関する一般的な数学的理論があるのであ る。この2章ではそれを紹介する。
§1
順序
1.1
順序
定義 1.1 (順序) 集合X 上の関係 =が 順序である、あるいは(X, =)が 順序集合であるとは (1) x = x. (2) x = y, y = z ⇒ x = z. (3) x = y, y = x ⇒ x = y. が任意のx, y, z ∈ X について成り立つときに言う。また、さらに (4) 任意のx, y ∈ X に対してx = y またはy = x が成り立つならば、=は 全順序であると言う。 例 23 (1) N = Z≥0 = {0以上の整数}とし、=を普通の意味の≥と思うと、これは全順序である。 (2) Nにx = y ⇐⇒ y|xと定義すると、これは順序だが全順序でない。 定義 1.2 (順序の拡張) 集合X に２つの順序=と≥が与えられていて α ≥ β ⇒ α = β が成り立つとき、=は≥の 拡張であるという。 例 24 (1) N − {0} にx = y ⇐⇒ y|xと定義すると、普通の順序≥は=の拡張である。 この文章では、2つの順序を同時に考えるとき =以外に ≥という記号も使って区別する。しばしば、抽象的、人 工的な方を =で表し、伝統的な、標準的な順序の方を≥で表す。 定義 1.3 (1) x > yとはx = yかつx 6= yのこと。 (2) x 5 yとはy = xのこと。 (3) x < yとはx 5 yかつx 6= yのこと。2 順序に関するディクソンの補題 17
1.2
積順序
定義 1.4 (Nnの標準的順序) α = (α1, α2, · · · , α n), β = (β1, β2, · · · , βn) ∈ Nn に対して ≥を次の様に定義 する。 α ≥ β ⇐⇒ ∀i αi≥ βi この≥をNn の 標準的順序あるいは 自然順序という。 注 8 (Nn, ≥)は順序集合である。n ≥ 2 のとき全順序ではない。 定義 1.5 (積順序) 2つの順序集合(X, =), (Y, =)に対して、順序集合(X × Y, =) を次のように定義し 積順序と 言う: (x1, y1) = (x2, y2) ⇐⇒ x1= x2 かつy1= y2. 注 9 積順序は順序になる。 注 10 Nn の標準的順序≥は、Nの標準的順序から、Nn= Nn−1× Nで帰納的に積順序で作ったものである。§2
順序に関するディクソンの補題
多項式の次数の集合Nn の性質について調べる。2.1 Dikson
性
定義 2.1 (イデアル) (X, =) を順序集合、Aをその部分集合で、次の条件を満たすとき、AはX の イデアルであ るという。∀a ∈ A∀x ∈ X(x = a ⇒ x ∈ A).
例 25 {n ∈ N | n ≥ 1}はNのイデアル。 定義 2.2 (生成、有限生成) Sを順序集合X の部分集合とする。 (1) X の部分集合Aに対し、ある集合S ⊂ Aが存在して ∀a ∈ A∃s ∈ S a = s. となるとき、S はA を 張る、 生成する、あるいはS はAの 基底であると言う。 (2) X 部分集合S に対し、 <S> = {x ∈ X | ∃s ∈ S x = s} とおき、これをS で 生成されたイデアル という。S = {s1, s2, · · · , sk} と有限集合であるとき、<S>を 単に<s1, s2, · · · , sk>と書く。 (3) X 部分集合A の基底として有限集合が取れるときAは 有限生成であると言う。 命題 2.3 (1) <S>はX のイデアルである。 (2) Sがイデアル ⇐⇒ <S> = S。 (3) SがAを生成する ⇐⇒ A ⊂ <S>。 [証明]略。¤
定義 2.4 (Dickson性) 順序集合 (X, =)について、X の任意の部分集合が有限生成であるとき、X は Dickson 的である、あるいは Dickson性を持つ、と言う。 注 11「任意の部分集合が有限生成」のかわりに「任意のイデアルが有限生成」としても同値になる。 例 26 (1) Nの標準順序で、その任意の部分集合はその最小元で生成されるから、NはDickson的である。 (2) Nの例23の(2)の順序では、NはDickson的でない。 定理 2.5 (Dickson性の同値命題) 順序集合 (X, =)について、次の3つは同値である。 (1) X はDickson性を持つ。 (2) X の任意の無限数列S = (x1, x2, · · · )には、単調増大な部分無限列が存在する。 (3) X の任意の無限数列S = (x1, x2, · · · )についてあるi, j が存在してi < j かつxi5 xj となる。 [証明] (1) ⇒ (2):仮定よりS の有限部分集合S0 があって、S のどの元もS0 のどれかの元より =となる。S は 無限集合なので、あるS0 の元i1 があって、xi1 より大きいS の元は無限個。すなわち、S(k) = {xi ∈ S | k < iか つxk 5 xi} とおくと、S(i1)は無限集合である。同様にして xi2 を S(i1) を張る有限集合の元のどれかに取ると、 S(i2)も無限集合になる。以下同様にxi3, xi4, · · · を取っていけば、xi1 5 xi25 xi3 5 xi4 5 · · · となる。 (2) ⇒ (3):明らか。 (3) ⇒ (1): 仮にDickson 的でないとする。ある X の部分集合 A で有限生成でないものがある。x1 ∈ A を適当に取ると、{x1} は A を張らないので、ある x2 ∈ A について x1 5 x2 とならない。{x1, x2} も A を張らないので、x3 ∈ A で x1 5 x3 も x2 5 x3 が成り立たないものが存在する。同様にして一般に xn が x15 xn, x25 xn, · · · , xn−15 xn のどれも成り立たないように取れる。このとき、S = (x1, x2, · · · )は、(3)の 条件を満たしていないので矛盾である。¤ 定理 2.6 X がDickson的であるのは次の命題とも同値である。 A1⊂ A2⊂ A3⊂ · · ·をX のイデアルの増大列とすると、必ずあるN が存在して、∀n ≥ N An = AN。 [証明] X がDickson的であるとする。SiAiはイデアルである。その有限基底F ⊂ S iAi を取れば、F の各元毎 にあるi が存在してAi に属する。これらのiの最大のものを nとすると、F ⊂ An となる。このn が求めるもの である。 X がDickson的でないとする。A1= {}とする。既に有限生成イデアルの狭義増大列A1$ A2$ A3$ · · · $ Ak が作れているとするとき、X − Ak は空集合でないから、あるx ∈ X − Ak を取ってAk+1= <Ak∪ {x}>とおけ ば、Ak $ Ak+1である。このようにして作ったAn, n ≥ 1は条件を満たさない。¤
定理 2.7 2つの順序集合(X, =), (Y, =)がDickson的なら、積順序を与えた(X × Y, =)もDickson的。 [証明] (x1, y1), (x2, y2), · · · をX ×Y の任意の数列とする。XがDickson的なので、定理2.5の(2)より1, 2, · · · の無限部分集合Aで{xi| i ∈ A}が単調増大になるものが取れる。またY がDickson的なので、定理2.5の(3)の
条件よりA の要素i, j (i < j)で、yi5 yj となるものが存在する。この時、(xi, yi) 5 (xj, yj)が成り立つ。すな
わち、定理2.5の(3)が成立するので、X × Y はDickson的。¤
定理 2.8 (Nnの順序に関するディクソンの補題) Nn は標準順序 ≥に関してDickson性を持つ。特に、Nn の任意
のイデアル<A>に対してある有限部分集合A0⊂ Aが存在して、<A> = <A0>となる。
[証明] n = 1 のとき：Nでは標準順序 ≥はDickson的。n = k の時Dickson的であるとすると、定理2.7 より、 Nk+1= Nk× Nの時もDickson的。以上より、任意のnについてNn Dickson的。
2 順序に関するディクソンの補題 19
任意の集合 Aに対して、その有限基底を A0 とすると、A ⊂ <A0> 。両辺のイデアルをとると、命題2.3 より、
<A> ⊂ <<A0>> = <A0>。A ⊃ A0 なので、<A> = <A0>。¤
2.2
整列性
定義 2.9 (最小元, 極小元) 順序集合(X, =)の部分集合とA とa ∈ A に対して、 (1)「∀x ∈ A (x = a)」が成り立つとき、aをAの 最小元と言う。 (2)「∀x ∈ A (x < aでない)」が成り立つとき、aをAの 極小元と言う。 注 12 最小元は極小元である。また、全順序集合では極小元は最小元である。 例 27 (N2, ≥)において、A = {(0, 1), (1, 0)}におけるa = (0, 1)は極小元だが最小元でない。 定義 2.10 (整列順序) 全順序集合 (X, =)において、任意の部分集合が最小限を持つとき=を 整列順序、(X, =) を整列順序集合と言う。 注 13 全順序集合では、=が整列順序であることと、Dickson的であることは同値である。 例 28 (1) (N, ≥)は整列順序。 (2) (Nn, ≥)はn ≥ 2 のとき整列順序でない。（全順序でないから。） (3) (Z, ≥)は整列順序でない。 (4) (Q≥0, ≥)は整列順序でない。2.3 Noether
性
(参考) この小節では、Dickson性より弱いNoether性について調べるが、この後の議論に用いられる事はない。 定義 2.11 (Noether性) (X, =)の任意の空でない部分集合 S が=に関する極小元を S の中に持つとき =は Noether的あるいはNethoer性を持つという。 補題 2.12 順 序 集 合 (X, =) が Noether 的 で あ る た め の 必 要 十 分 条 件 は 全 て の X に お け る 狭 義 単 調 減 少 列 x1> x2> · · · が必ず有限で終わることである。 [証明] (必要性）定義より明らか。（十分性）X のある空でない部分集合Aに極小元がないとする。まずx1∈ Aを 適当に選ぶ。Aにx1 より小さい元は存在する。（そうでなければ x1 は極小元となる。）よってそれを x2∈ Aとす る。以下同様にx1> x2> x3> · · · ∈ Aが作れるので、仮定に反する。¤ 補題 2.13 Dicskon性を持てばNoether性を持つ。 [証明]補題2.12より、もしNoether性を持たなければ、その集合には狭義単調減少数列があるが、これはあきらか に有限な基底はないのでDickson性を持たないから。¤ 例 29 Noether性を持ってもDickson性を持つとは限らない。例えば無限集合X 上で =を空（任意のx, y ∈ X について x > yでない）とすると、これはNoether性を持つがDickson性を持たない。 系 2.14 全順序集合では、順序がNoether性を持つこととDickson性を持つことは同値である。[証明]整列集合であるとする。部分集合の最小元はそれ１つでその部分集合を張っているからDickson性を持つ。 逆は補題2.13より。¤
定理 2.15 2つの順序集合(X, =), (Y, =)がNoether的なら、積順序を与えた(X × Y, =)もNoether的。 [証明]略。¤
§3
単項式順序と整除
3.1 “
単項式
”
順序
Nn の加法とは、α = (α1, α2, · · · , α n), β = (β1, β2, · · · , βn) ∈ Nn に対して α + β = (α1+ β1, α2+ β2, · · · , αn+ βn) と定義されたものとする。 定義 3.1 (両立) (Nn, =)が+と 両立しているとは、 α = β ⇒ ∀γ ∈ Nn α + γ = β + γ が成り立つことである。 定理 3.2 (Nn, =)を全順序で、+と両立しているとする。このとき、次の３つの条件は同値である。 (1) =は標準的順序≥の拡張である。 (2) =は整列順序。 (3) ∀α ∈ Nn α = 0. [証明] (1) ⇒ (2): 任意のA ⊂ Nn について、ディクソンの補題よりあるAの≥に関する有限基底A0⊂ Aが存 在する。A0 の=に関する最小の元をα0とする。任意のα ∈ Aに対して、あるα0∈ A0 があって、α ≥ α0。仮定よ りα = α0 = α0。すなわちα0 はAの=に関する最小元である。よって=は整列順序である。 (2) ⇒ (3):整列順序なのにα < 0となるαが存在したとすると、α > α + α > α + α + α > · · · となり、この数 列に最小が存在せず矛盾する。 (3) ⇒ (1): α ≥ βとすれば、α − β ∈ Nn よって、仮定よりα − β = 0。両辺にβ を加えてα = β。よって=は ≥の拡張である。¤ 定義 3.3 (単項式順序) Nn の 単項式順序（あるいは単に 項順序）とは、順序であって次の条件を満たすものを言う。 (1) =は標準的順序の拡張である (2) =はNn の全順序 (3) =は+と 両立する 定理 3.4 Nn の単項式順序は整列順序である。 [証明]定理3.2より。¤3 単項式順序と整除 21
3.2
さまざまな単項式順序
以下、Nn の単項式順序を複数作って行く。
定義 3.5 (辞書式順序, lex, lexcographic order, >lex) α = (α1, α2, · · · , αn), β = (β1, β2, · · · , βn)とする
とき、 α >lexβ ⇐⇒ αi, βi を左から見ていって最初の異なるαi, βi でαi> βi. 命題 3.6 lexは単項式順序である。 [証明]明らか。¤ 記法 4 α = (α1, α2, · · · , αn)に対し|α| = P αi とおく。
定義 3.7 (次数付き辞書式順序, grlex, graded lexcographic order, >grlex)
α >grlexβ ⇐⇒ (|α| > |β|)または(|α| = |β| かつα >lexβ).
命題 3.8 grlexは単項式順序である。 [証明]明らか。¤
定義 3.9 (次数付き逆辞書式順序, grevlex, graded reverse lexcographic order, >grevlex) α = (α1, α2, · · · , αn),
β = (β1, β2, · · · , βn)とするとき、
α >grevlexβ ⇐⇒ (|α| > |β|)または(|α| = |β|かつαi, βi を右から見ていって最初の異なるαi, βi でαi< βi).
命題 3.10 grevlexは単項式順序である。 [証明]明らか。¤
例 30 {(0, 0, 3), (2, 0, 2), (1, 2, 1)}を大きい順に並べる
lex grlex grevlex
(3, 0, 0) (2, 0, 2) (1, 2, 1) (2, 0, 2) (1, 2, 1) (2, 0, 2) (1, 2, 1) (3, 0, 0) (3, 0, 0) 注 14 N2ではgrlexとgrevlexは同じである。
3.3
単項式順序
定義 3.11 (単項式) α = (α1, α2, · · · , αn)に対してxα= x1α1x2α2· · · xnαn∈ k[x1, x2, · · · , xn]とおき、これ を 単項式と言う。 注 15 xα| xβ ⇐⇒ α ≤ β (標準順序). 定義 3.12 (単項式の順序) Nn に順序=を一つ定めたとき、α = (α1, α2, · · · , α n), β = (β1, β2, · · · , βn) ∈ Nn とするとき、単項式 xα とxβ の間の順序を xα= xβ ⇐⇒ α = β と定義する。Nn の単項式順序=で決められた単項式の順序を単に 単項式順序という。Nn の単項式順序の定義3.3より、次が成り立つ。 命題 3.13 (単項式順序) k[x1, x2, · · · , xn]の単項式について、 (1) xα≥ xβ ⇒ xα= xβ (2) =は単項式の間の全順序 (3) =は積と 両立する（すなわちxα= xβ ⇒ xαxγ = xβxγ が成り立つ）。 例 31 同じ式の単項式の降べき（大きい順）表示 −5x3+ 7x2z2+ 4xy2z + 4z2(lex) = 7x2z2+ 4xy2z − 5x3+ 4z2(grlex) = 4xy2z + 7x2z2− 5x3+ 4z2(grevlex) 定義 3.14 多項式 f =Pαaαxα についてf 6= 0のとき次のように定義する。
• deg(f ) = multideg(f ) = max{α | aα6= 0}. · · · 多重次数
• LC(f ) = adeg(f ) · · · 先頭係数(leading coefficient)
• LM(f ) = xdeg(f ) · · · 先頭単項式(leading monomial)
• LT(f ) = adeg(f )xdeg(f ) · · · 先頭項(leading term)
• RT(f ) = f − LT(f ) · · · 残余(rest term) 注 16 LT(f )|LT(g)はdeg f ≤ deg g と同値となる。 例 32 f = −5x3+ 7x2z2+ 4xy2z + 4z2 についてlexで考えると • deg(f ) = (3, 0, 0) • LC(f ) = −5 • LM(f ) = x3 • LT(f ) = −5x3 • RT(f ) = 7x2z2+ 4xy2z + 4z2 命題 3.15 f, g 6= 0について (1) deg(f g) = deg(f ) + deg(g).
(2) f + g 6= 0 ⇒ deg(f + g) ≤ max{deg(f ), deg(g)}.
(3) f + g 6= 0かつdeg(f ) 6= deg(g) ⇒ deg(f + g) = max{deg(f ), deg(g)}.
3.4
多変数多項式の整除
定理 3.16 (割り算アルゴリズム) 単項式順序=を選び固定する。f のF = (f1, f2, · · · , fs)による 割り算とは次 の条件を満たすものであり、以下に述べるアルゴリズムで得ることができる。 (1) f = a1f1+ a2f2+ · · · + asfs+ r. （ai を 商、rを 余りあるいは 剰余という。） (2)（r = 0） または（r 6= 0で、全てのiについてLT(fi)はrのどの単項式も割ることはない。） (3) aifi6= 0ならば deg(f ) ≥ deg(aifi)。3 単項式順序と整除 23
Input : f, f_1, f_2, ... , f_s Output : a_1, a_2, ... , a_s, r
a_1 := 0; a_2 = 0; ... ; a_s := 0; r := 0 p := f
WHILE p != 0 DO i := 1
sw := False
WHILE i <= s AND sw = False DO IF LT(f_i) divides LT(p) THEN
a_i := a_i + LT(p) / LT(f_i) p := p - ( LT(p) / LT(f_i) ) * f_i sw := True ELSE i := i + 1 IF sw = False THEN r := r + LT(p) P := p - LT(p) （ただしここでfi をf_iなどと書いた。） 例 33 lexでの(x2y + xy2+ y2) ÷ (xy − 1, y2− 1) = (x + y, 1) · · · x + y + 1. の計算過程を示す。 xy - 1 | x + y r: x + y + 1 y^2 - 1| 1 ---x^2y + xy^2 + y^2 x^2y - x ---xy^2 + x + y^2 xy^2 - y ---x + y^2 + y --> x y^2 - 1 ---y + 1 --> ---y 1 --> 1 0 [証明]略。ただし、ループの停止性には単項式順序が整列順序であること(定理3.4)を使う。¤ 定義 3.17 ( F, mod F ) f ∈ k[x1, x2, · · · , xn], F = (f1, f2, · · · , ft)に対してf をF で割った余りrを fF あるいはremainder(f, F )あるいはf mod F と書く。 定理 3.18 任意の F = (g1, g2, · · · , gt)に対し( ) F はk上線形である。 [証明]略。¤ 例 34 (1) F の順番によって、余りが変わる。
(xy2− x) ÷ (xy − 1, y2− 1) = (y, 0) · · · (−x − y) [lex].
(xy2− x) ÷ (y2− 1, xy − 1) = (x, 0) · · · 0 [lex].
(2) 順序の取り方によって、余りが変わる。(lexとgrlex)
(xy + y2) ÷ (x + y2) = y · · · (−y3+ y2) [lex].
(xy + y2) ÷ (x + y2) = 1 · · · (xy − x) [grlex].
(3) 順序の取り方によって、余りが変わる。(x > y とy > x)
(x + y2) ÷ (x + y) = 1 · · · (y2− y) [lex, x > y].
注 17 f mod F = 0ならば f ∈ <F >である。一方、例34の(1)にあるように、f mod F 6= 0だからといって、 f 6∈ <F >とは言えない。
§4
ヒルベルトの補題とグレブナ基底
これ以降、Nn の標準順序の拡張である単項式順序=を１つ定めておく。 記法 5 F をk[x1, x2, · · · , xn] の部分集合とするとき deg(F ) = {deg(f )|f ∈ F, f 6= 0} LT(F ) = {LT(f )|f ∈ F, f 6= 0} LM(F ) = {LM(f )|f ∈ F, f 6= 0} 等々と定義する。 命題 4.1 I がイデアルならdeg(I)も標準順序≥に関するイデアルである。 [証明] (略)。¤ 以下、順序のイデアルは標準順序≥によるものとする。 }問い 集合 F ⊂ k[x1, x2, · · · , xn] で生成されるイデアル<F > に対し、一般にdeg(<F >) ⊃ < deg(F )>であ る。では、いったい、いつ deg(<F >) = < deg(F )> となるか？ 例 35 f1 = x3, f2 = x2y + x とし、F = {f1, f2}, <F > = <f1, f2>とおく。x2= −yf1+ xf2∈ <F >. 以下lex順序とする。(2, 0) = deg x2 ∈ deg(<F >). 一方、< deg(F )> = < deg(f1), deg(f2)> = <(3, 0), (2, 1)>。
∴ deg x26∈ < deg(F )>つまり、deg(<F >) % < deg(F )>。(因みに<F > = <x>である。)
定義 4.2 (グレブナ基底) イデアル Iの有限部分集合Gで
deg(I) = < deg(G)> となるときGをI の グレブナ基底あるいは 標準基底という。
定理 4.3 イデアル Iのグレブナ基底GはIの基底である。すなわちI = <G>である。
[証明]定理3.16のアルゴリズムでf ∈ I をG = (g1, g2, · · · , gt)によって割った商をa1, a2, · · · , at、余りを r
とする。このとき、r = f − a1g1− · · · − atgt∈ I。もしr 6= 0 とすると全てのiについてdeg(gi) 6≤ deg(r)。よっ
て、< deg(G)> 63 deg(r) ∈ deg(I)。これはdeg(I) = < deg(G)>と矛盾する。¤
例 36 lexでG = (x + y, y − z) はI = <G>のグレブナ基底である。
[証明] deg(I) ⊂ < deg(x + y), deg(y − z)>をいえばよい。つまり、f ∈ I, f 6= 0に対して“(1, 0, 0) ≤ deg(f )ま たは(0, 1, 0) ≤ deg(f )”をいう。仮に、これが否定されるならばLT(f )はz だけの式。よって、f もz だけの式 f (z)。一方 f ∈ I ならf は x y z = −t t t 上で0 であるはず。よってf (t) = 0これはf 6= 0 と矛盾。¤
5 グレブナ基底の性質 25
定理 4.4 (グレブナ基底の存在定理) 体k上の多項式環k[x1, x2, · · · , xn] の任意のイデアルI (6= 0)には、グレ
ブナ基底が存在する。
[証明]ディクソンの補題より、イデアルdeg(I)には有限な生成元deg(g1), deg(g2), · · · , deg(gt), (gi∈ I)が存在
する。G = (g1, g2, · · · , gt)とおけば、< deg(G)> = < deg(g1), deg(g2), · · · , deg(gt)> = deg(I). ¤
定理 4.5 (ヒルベルトの基底定理) 体k 上の多項式環k[x1, x2, · · · , xn]の任意のイデアルは有限生成イデアルで ある。 [証明]生成元としてそのイデアルのグレブナ基底を取ればよい。¤ 系 4.6 I1⊂ I2⊂ · · · をk[x1, x2, · · · , xn]のイデアルの増大列とするとき、あるi0が存在してIi= Ii0, (∀i ≥ i0) となる。 [証明]定理2.6の証明と同様である。¤ 系 4.7 k[x1, x2, · · · , xn]の任意のイデアル IについてV(I) = {x ∈ kn| ∀f ∈ I f (x) = 0}はアフィン多様体で ある。
§5
グレブナ基底の性質
5.1
正規形
定理 5.1 G = (g1, g2, · · · , gt)をイデアルI のグレブナ基底とすれば、任意のf ∈ k[x1, x2, · · · , xn]に対して 次を満たすrがただ１つ存在する。 (1) r = 0、または r 6= 0でrのどの単項式のdegも、どの deg(gi)より大きく(≥)ない。 (2) あるg ∈ I が存在してf = g + rとなる。 [証明]存在は Gにより割り算（定理3.16）により明らか。 一意性は f = g + r = g0+ r0 とすると r0− r = g − g0 ∈ I であり、これが 0 でないとするとdeg(r − r0) ∈deg(I) ⊂ < deg(G)> = < deg(g1), deg(g2), · · · , deg(gt)>。よってあるi でdeg(gi) ≤ deg(r0− r)。これは rま
たはr0 のある単項式のdeg が≥ deg(gi)となって矛盾である。¤ 定義 5.2 (正規形) f ∈ k[x1, x2, · · · , xn] ⊃ I :イデアル で、G = (f1, f2, · · · , ft)がI のグレブナ基底である ときfG はGの中のfi の順番に依存しない。また、定理5.1の条件(1), (2)を満たすrはf G である。これをf の（Gによる） 正規形という。 系 5.3 GをイデアルI のグレブナ基底とすると f ∈ I ⇐⇒ fG= 0. [証明] ⇐ は明らか。⇒ はf = f + 0に定理5.1を適用してfG= 0. ¤ } 問いF = (f1, f2, · · · , ft)がグレブナ基底になるのはどんな時か？
5.2 S-
多項式
定義 5.4 (S-多項式) xγ をLM(f )とLM(g)の最大公約数とするとき、 S(f, g) = x γ LT(f )f − xγ LT(g)g = fとgの先頭項を相殺させた式 をf とgのS 多項式という。 例 37 grlexでf = x3y2− x2y3+ x, g = 3x4y + y2を考えるとxγ= x4y2, S(f, g) = xf −y 3g = −x3y3+ x2− y3 3. 注 18 (1) deg S(f, g) < deg LCM(LT(f ), LT(g)). (2) deg f = deg g ⇒ deg S(f, g) < deg f .(3) deg f = deg g ⇒ S(f, g) = f LC(f ) − g LC(g). (4) c, c0 ∈ k, c 6= 0, c06= 0 ⇒ S(c · f, c0· g) = S(f, g). (5) S(f, g) | S(xαf, xβg). ∵ xδ = deg LCM(LM(xαf ), LM(xβg)), xγ = LCM(LM(f ), LM(g)) と お く と 、S(xαf, xβg) = xδ·xαf LM(xαf )− x δ·xβg LM(xβg) = xδ−γ( x γf LM(f )− xγf LM(g)) = xδ−γS(f, g)。 定義 5.5 δ ∈ Nn, f1, f2, · · · , f t∈ k[x1, x2, · · · , xn]に対してイデアル<f1, f2, · · · , ft>の部分空間を <f1, f2, · · · , ft>δ = { P iaifi| ∀i deg(aifi) ≤ δ} と定義する。同様に集合F ⊂ k[x1, x2, · · · , xn]に対して<F >δ を定義する。 注 19 任意のδ ∈ Nn に対して次が言える。 (1) <F >δ+ <G>δ = <F ∪ G>δ. (2) fi | gi (1 ≤ i ≤ t) ⇒ <g1, g2, · · · , gt>δ ⊂ <f1, f2, · · · , ft>δ. 補題 5.6 f ∈ <F >deg f とするとき、次が成り立つ。 (1) <f >δ ⊂ <F >δ, ∀δ ∈ Nn. (2) deg(f ) ∈ < deg(F )>. [証明] F = (f1, f2, · · · , ft)とすれば、f = P iaifi, deg(aifi) ≤ deg f と書ける。 (1) 任意のaf ∈ <f >δ (a ∈ k[x1, x2, · · · , xn])に対して、af = P iaaifi, deg(aaifi) ≤ deg af ≤ δ。よっ て、af ∈ <F >δ。
(2) LT(f ) =Pdeg(aifi)=deg fLT(ai)LT(fi)。よって deg(aifi) = deg f となる i が少なくとも１つ存在するの
で、deg(fi) ≤ deg(f )。¤
注 20 (1) fF = 0 のときf ∈ <F >deg f となる。
(2) 上の2つの結論は、単に f ∈ <F > という仮定だけからは言えない。（例: f = y, F = (x + y, x), δ = (0, 1), lexのとき y 6∈ <x + y, x>(0,1)= {0}であり、deg(y) 6∈ < deg(x + y), deg(x)> = <(1, 0)>でも ある。）
補題 5.7 f1, f2, · · · , ftは全てdeg がδに等しいとする。f =
P
icifi, (ci∈ k) についてdeg f < δ とすればf
