テキスト(pdf 形式)

1
Groebner 基底
（2016 年 2 学期現代数学特論）
原 信一郎
[email protected]
http://blade.nagaokaut.ac.jp/∼hara/class/groebner/
twitter:hara sin16
2016 年 11 月 23 日版
3
目次
第1章
代数と幾何
1
1
環と体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
1 変数多項式環 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3
イデアルとアフィン多様体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Groebner 基底
19
第2章
1
順序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2
順序に関するディクソンの補題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3
単項式順序と整除
4
ヒルベルトの基底定理とグレブナ基底 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
5
グレブナ基底の性質 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
6
ブッフベルガーのアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Groebner 基底の応用
41
1
計算の実例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
2
拡張定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
第3章
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
付録
51
1
参考書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
2
参考 URL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
索引
53
1
第1章
代数と幾何
まず最初に代数系の基礎を紹介する。
§1
環と体
1.1 環と体の公理
定義 1.1（環と体） 集合 R 上に 2 つの演算
+ : R×R
· : R×R
→
→
R,
R,
(a, b)
(a, b)
7→
7
→
a+b
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 ̸= 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 と書く。
第1章
2
代数と幾何
(7) a · b−1 を a/b と書く。
注1
(1) この文書では「環」といえば「可換環」を指すことにする。
(2) この文書では「体」といえば 0 ̸= 1 を仮定する。
(3) 環 (R, +, ·, 0, 1) を単に R と書くことがある。
定義 1.2（単元, 可逆元） 環 R の要素で逆元を持つものを 単元あるいは 可逆元 という。単元全体を R× と書く。
注2
(1) R が体 ⇐⇒ R× = R − {0}。
(2) R が体 ⇒ (R[x])× = R× 。
命題 1.3（環の性質） 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).
+ a b
· a b
(9) A2 = {a, b}
a
a
b
a
a a において、0 = a, 1 = b としたもの。
b
b
a
b
a
(10) A4 = {a, b, c, d}
b
+ a
b
c
d
·
a
b
c
a
a
b
c
d
a
a
a
a a
b
b
c
d
a
b
a
b
c
d において、0 = a, 1 = b としたもの。
c
c
d
a
b
c
a
c
a
c
d
d
a
b
c
d
a
d
c
b
1.2 準同型
記法 2
• 今後 k で任意の体（例 Q, R, C）を表す。
• {a, b, c} : 順序のない集合。
• (a, b, c) : 順序のある集合。
• 論理記号
d
1 環と体
3
∀x · · ·
:
任意の x について · · · 。
∃x · · ·
:
ある x について · · · 。
P =⇒ Q
:
P ならば Q。
P ⇐⇒ Q
:
P と Q は同値。
P ∨Q
:
P または Q。
P ∧Q
:
P かつ Q。
¬P
:
P でない。
定義 1.4（全射と単射） f : X → Y を写像とするとき、
(1) 「∀y ∈ Y ∃x ∈ Xf (x) = y 」が成り立つ時、f は 全射であるという。
(2) 「∀x, x′ ∈ X(x ̸= x′ ⇒ f (x) ̸= f (x′ ))」が成り立つ時、f は 単射であるという。
(3) f が全射でかつ単射であるとき f は 全単射という。
定義 1.5（準同型） 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.6 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.7（部分環） (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.8（イデアル） R を環、I をその空でない部分集合で、次の条件を満たすとき、I は R のイデアルであると
いう。
第1章
4
代数と幾何
(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) 1 ∈ I は I = R と同値である。
(6) R の部分環 S が R のイデアルなら R = S である。
(7) R が体ならそのイデアルは自明なものしかない。
定義 1.9
S を R の部分集合とするとき
⟨ S ⟩ = {x ∈ R | s1 , s2 , · · · , sn ∈ S と r1 , r2 , · · · , rn ∈ R が存在して x = r1 s1 + r2 s2 + · · · + rn sn }
とおき、これを S で 生成されたイデアルという。S = {s1 , s2 , · · · , sk } と有限集合であるとき、⟨ S ⟩ を単に
⟨ s1 , s2 , · · · , sk ⟩ あるいは Rs1 + Rs2 + · · · + Rsk と書く。一つの要素で生成されるイデアル ⟨ a ⟩ = Ra を 単項イ
デアルという。
注 3 < S > は R のイデアルである。
例 5 Z では、⟨ n ⟩ = nZ。
定義 1.10（剰余類） R を環、I をそのイデアルとするとき、a ∈ R に対して
[a] = {x ∈ R | x − a ∈ I}
と書き、これを a の 剰余類と呼ぶ。また、全ての剰余類の集合 ( 剰余集合) を
R/I = {[a] | a ∈ R}
と書く。
注4
(1) [a] = {a + x ∈ R | x ∈ I} であるので、これを a + I と書くことがある。
(2) a ∈ [a] である。
例 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[x]}.
命題 1.11（剰余類の性質） 以下の条件は全て同値である。
(1) a − b ∈ I.
(2) [a] ∩ [b] ̸= ϕ.
(3) [a] = [b].
(4) a ∈ [b].
定義 1.12
(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 の代表系である。
1 環と体
5
(2) {0, 1, 2, 3} は Z/4Z の代表系である。
(3) {a + bx ∈ k[x] | a ∈ k, b ∈ k} は k[x]/⟨ x2 + 1 ⟩ の代表系である。
定義 1.13（剰余環） 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.14
R を環、I をその R と異なるイデアルとするとき、(R/I, +, ·, 0, 1) は環をなす。標準射影 π : R →
R/I, a 7→ [a] は準同型である。
+
例 8（剰余環の例）
(1) Z/2Z = {[0], [1]},
(2) Z/4Z = {[0], [1], [2], [3]},
·
[0] [1]
[0]
[1]
[0] [0] [1]
[0] [0]
[0]
[1] [1] [0]
[1] [0]
[1]
+
[0] [1] [2] [3]
·
[0]
[1]
[2]
[3]
[0]
[0] [1] [2] [3]
[0]
[0]
[0]
[0]
[0]
[1]
[1] [2] [3] [0] .
[1]
[0]
[1]
[2]
[3] .
[2]
[2] [3] [0] [1]
[2]
[0]
[2]
[0]
[2]
[3] [3] [0] [1] [2]
[3] [0] [3] [2] [1]
(3) R[x]/⟨ x + 1 ⟩ = {[a + bx] | a, b ∈ R} = {a + bi | a, b ∈ R}, a = a · 1, i = [x].
2
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.15（核, 像） f : R → S を環の準同型とするとき、
(1) Imf = {f (x) ∈ S | x ∈ R} を f の 像 (image) という。
(2) Kerf = {x ∈ R | f (x) = 0} を f の 核 (kernel) という。
命題 1.16
(1) Imf は S の部分環である。
(2) Kerf は R のイデアルである。
定理 1.17（準同型定理） f : R → S を環の準同型とするとき、
f : R/Kerf → Imf,
[a] 7→ f (a).
は同型写像である。
[証明] 証明すべき事は (1) well-defined、(2) 全射、(3) 単射、(4) 準同型性である。
(1) Z/2Z ∼
= A2 .
∼
(2) Z/4Z = A4 .
(3) R[x]/⟨ x2 + 1 ⟩ ∼
= C.
系 1.18
1.4 素イデアルと極大イデアル
定義 1.19（整域） 環 R が次の条件を満たすとき、 整域という。
∀a, b ∈ R a · b = 0 =⇒ a = 0 ∨ b = 0.
第1章
6
定理 1.20
代数と幾何
体は整域である。
定義 1.21（素イデアル） R と異なるイデアル I ⊂ R が次の条件を満たすとき、 素イデアルという。
∀a, b ∈ R a · b ∈ I =⇒ a ∈ I ∨ b ∈ I.
命題 1.22
イデアル I ⊂ R に対して R/I が整域であるための必要十分条件は I が素イデアルであることである。
(1) R = Z, I = 3Z のとき、I は素イデアル。
例9
(2) R = Z, I = 4Z のとき、I は素イデアルでない。
定義 1.23（極大イデアル） R と異なるイデアル I ⊂ R が次の条件を満たすとき、 極大イデアルという。
I ⊂ J ⊂ R となるイデアル J は J = I または J = R のみである。
定理 1.24
R を環、I をその R と異なるイデアルとする。剰余環 R/I が体であることは、I が極大イデアルである
ことの必要十分条件である。
[証明]
•（十分性）R/I が体であるとする。J を I より真に大きい R のイデアルとする。a ∈ J − I をとると a ̸∈ I な
ので、 [a] ̸= 0 ここで R/I が体であることから [a] の逆元 [b] が存在する。[a][b] = [1] より [ab − 1] = 0 ゆえ
に ab − 1 ∈ I ⊂ J 。一方 ab ∈ J であるから、1 ∈ J が言える。よって J = R。
•（必要性）I が極大イデアルだと仮定する。I ̸= R より R/I は 0 ̸= 1 の環である。今、[a] ∈ R/I, [a] ̸= 0
を任意にとると、a ̸∈ I より ⟨ a, I ⟩ = R。よってある r ∈ R と s ∈ I で ra + s = 1 となる。このとき、
[r][a] = [1] = 1 すなわち [r] は [a] の逆元となっている。よって、R/I は、体である。
(1) 3Z は Z の極大イデアルであり、Z/3Z は体である。
例 10（極大イデアルの例）
(2) 一般に、p を素数とするとき、Z/pZ は体であり、pZ は Z の極大イデアルである。(例 18 を参照のこと)
(3) R[x]/⟨ x2 + 1 ⟩ ∼
= C は体。よって ⟨ x2 + 1 ⟩ は R[x] の極大イデアル。
定義 1.25
p を素数とするとき、Z/pZ を Fp と書き、標数 p の 素体という。
系 1.26 極大イデアルは素イデアルである。
§2
1 変数多項式環
2.1 定義
今後 k は体とする。実際には k = Q, R, C と思っていてよい。
定義 2.1（多項式環） k[x] = {am xm + am−1 xm−1 + · · · + a0 | ∀i ai ∈ k, m ∈ N} に通常の和と積を定義したもの
を、k 上の (1 変数) 多項式環という。
注 5 N = Z≥0 = {0 以上の整数 }.
定義 2.2
多項式 f = am xm + am−1 xm−1 + · · · + a0 , (am ̸= 0) について、次のように定義する。
• deg(f ) = m
• LC(f ) = am
···
···
次数 (degree)
先頭係数 (leading coefficient)
2 1 変数多項式環
• LM(f ) = xm
• LT(f ) = am xm
7
···
先頭単項式 (leading monomial)
···
• RT(f ) = f − LT(f )
先頭項 (leading term)
···
残余 (rest term)
命題 2.3 f, g ̸= 0 について
(1) deg(f g) = deg(f ) + deg(g).
(2) f + g ̸= 0 ⇒ deg(f + g) ≤ max{deg(f ), deg(g)}.
(3) f + g ̸= 0 かつ deg(f ) ̸= deg(g) ⇒ deg(f + g) = max{deg(f ), deg(g)}.
2.2 割り算アルゴリズム
定義 2.4（整除） f, g ∈ k[x], g ̸= 0 とする。ある q ∈ k[x] が存在して f = g · q となるとき g は f を 割り切ると
いい、g|f と書く。また、q = f /g と書き、これを f の g による 商と言う。
補題 2.5 f, g ̸= 0 とする。
(1) deg(g) ≤ deg(f ) ⇐⇒ LT(g)|LT(f ).
LT(f )
(2) deg(g) ≤ deg(f ), h = f −
g ⇒ h = 0 ∨ (h ̸= 0 ∧ deg(f ) > deg(h)).
LT(g)
定理 2.6（割り算アルゴリズム） f, g ∈ k[x], g ̸= 0 とする。f の g による 割り算とは次の条件を満たすものであ
り、以下に述べるアルゴリズムで得ることができる。
(1) f = g · q + r,
q, r ∈ k[x].
(2) r = 0 ∨ (r ̸= 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 あるいは remainder(f, g) と書く。
第1章
8
注6
代数と幾何
(1) f 7→ (f mod g) は、f に関する k 上の線形写像である。
(2) h ∈ k[x], h ̸= 0 =⇒ h(f mod g) = (hf ) mod (hg).
系 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 ̸= 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, h′ が GCD なら h|h′ かつ h′ |h なので、h′ は h の単元倍しか違わない。
2 1 変数多項式環
9
(3): 略。
例 12
(1) GCD(x4 − 1, x6 − 1) = x2 − 1.
(2) GCD(x5 + 2x3 , x4 + x2 − x) = x.
定義 2.15（素） f, g ∈ k[x] が素であるとは、「h|f かつ h|g ならば h は単元」が言える事である。すなわち、
GCD(f, g) が単元であることである。これは、deg GCD(f, g) = 0、⟨ f, g ⟩ = k[x]、⟨ f, g ⟩ ∋ 1 と同値である。
定理 2.16
f, g, h ∈ k[x]、f と g が素とするとき、以下が成り立つ。
(1) f |h かつ g|h ならば、(f g)|h。
(2) f |(gh) ならば f |h。
[証明]
(1) 1 = af + bg となる a, b ∈ k[x] があるので、h = h · 1 = h(af + bg) = ahf + bhg ここで、hf, hg が f g で割
り切れる。
(2) 同様に、h = ahf + bhg を使って示すことができる。
k[x] で、deg が n より小さいものと 0 をあわせて、k[x](n) と書くことにする。
定理 2.17
f, g ∈ k[x] が素であるとする。m = deg f, n = deg g に対して、
ϕ : k[x](m) ⊕ k[x](n) → k[x](m+n)
(u, v) 7→ gu + f v
と定義すると、これは k 上のベクトル空間の同型である。
[証明] 前定理 (2) より、ϕ は単射であることがわかる。ϕ のソースとターゲットの次元は、どちらも k 上 m + n なの
で、ϕ は同型である。
注7
(1) この定理は、次定理の前半を証明する。
(2) af + bg = 1 となる a, b ∈ k[x] を見つければ、ϕ−1 (w) = (bw mod f,
aw mod g) である。
定理 2.18（拡張されたユークリッドの互除法） f, g ∈ k[x] について、
af + bg = GCD(f, g)
となる a, b が
deg a
deg b
<
<
deg g − deg GCD(f, g),
deg f − deg GCD(f, g).
という条件の下でただ一組存在する。また、a, b は以下のアルゴリズムで求める事ができる:
第1章
10
代数と幾何
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
(
[証明] (存在) fi =
fi
)
fi+1
(
, Qi =
0
1
1 −qi
)
とおくと、fi+2 = fi − qi fi+1 ⇐⇒ fi+1 = Qi fi 。ここで、
(
Ri = Qi−1 Qi−2 · · · Q0 とおけば、fi = Ri f0 。Ri は、R0 = E, Ri+1 = Qi Ri で定められ、Ri =
置けて、ai+2 = ai − qi ai+1 , bi+2 = bi − qi bi+1 , fi+2 = ai fi + bi fi+1 が成り立つ。
(
さて、f0 = f, f1 = g とおくと、ある n があって、fn = GCD(f0 , f1 ), fn+1 = 0。すなわち、
ai
bi
ai+1
bi+1
)
)
GCD(f0 , f1 )
0
と
=
fn = Rn f0 。このとき、GCD(f0 , f1 ) = an f0 + bn f1 , 0 = an+1 f0 + bn+1 f1 である。
また、deg f0 ≥ deg f1 を仮定して良く、このとき、deg qi = deg fi − deg fi+1 。また、帰納的に、deg ai =
deg f1 − deg fi−1 (2 ≤ i ≤ n + 1) と deg bi = deg f0 − deg fi−1 (1 ≤ i ≤ n + 1) が言えるので、i = n とすれば、次
数の条件が言える。
(一意性) GCD(f, g) = 1 としてよい。af + bg = a′ f + b′ g = 1 なら (a − a′ )f = (b′ − b)g なので、定理 2.16 よ
り、f |(b′ − b), g|(a − a′ ) より b′ − b = a − a′ = 0。(多項の場合も OK な別証) a − a′ = a(a′ f + b′ g) − a′ (af + bg) =
(ab′ − a′ b)g ≡ 0( mod g)。
注8
(1) an+1 f0 = −bn+1 f1 = LCM (f0 , f1 ) となっている。
(2) a0 = 1, a1 = 0, a2 = 1, a3 = −q1 , a4 = 1 + q2 q1 , a5 = −q1 − q3 − q3 q2 q1 , a6 = 1 + q2 q1 +
q4 q1 + q4 q3 + q4 q3 q2 q1 , b0 = 0, b1 = 1, b2 = −q0 , b3 = 1 + q1 q0 , b4 = −q0 − q2 − q2 q1 q0 , b5 =
1 + q1 q0 + q3 q1 + q3 q2 + q3 q2 q1 q0 , b6 = −q0 − q2 − q4 − q2 q1 q0 − q4 q1 q0 − q4 q3 q1 − q4 q3 q2 − q4 q3 q2 q1 q0 .
系 2.19 f, g が素であるとき、以下が成り立つ。
b
a
b a
1
= + となる a, b で ,
が「真分数」になるものが一意に存在する。
fg
f
g
f g
b
a
b a
h
= + となる a, b で ,
が「真分数」になるものが一意に存在する。
(2) deg h < deg f + deg g なら、
fg
f
g
f g
(1)
[証明] (1), (2) 共に容易。
例 13
(1) f = x4 − x2 , g = x3 − 1 について、GCD(f, g) = x − 1 = (x + 1)f + (−x2 − x + 1)g.
2 1 変数多項式環
11
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
--0| 1
0
-x -1
----1 |
0
-x -1
-----x + 1
b:
x
-1 | 0
x
-x - 1
---------x |
1
x^2 + x
--------x^2-x+1
各ステージで次が成り立っていることに注目せよ。
x4 − x2
x3 − 1
−x2 + x
x−1
=
=
=
=
1
0
1
(x + 1)
·
·
·
·
(x4 − x2 ) +
(x4 − x2 ) +
(x4 − x2 ) +
(x4 − x2 ) +
0
1
(−x)
(−x2 − x − 1)
·
·
·
·
(x3 − 1)
(x3 − 1)
(x3 − 1)
(x3 − 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 = 13 (2x2 + x + 1) · f − 13 (2x3 + x2 + 3x + 3) · g.
定義 2.20
f1 , f2 , · · · , fs の GCD は次の条件を満たす h である。
(1) h|f1 , f2 , · · · , fs .
(2) ∀p (p|f1 , f2 , · · · , fs ⇒ p|h).
この h を GCD(f1 , f2 , · · · , fs ) と書く。
定理 2.21
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.
第1章
12
代数と幾何
例 15（イデアルへの所属問題） x3 +4x2 +3x−1 は ⟨ x3 −3x+2, x4 −1, x6 −1 ⟩ に属するか？【解答】x3 +4x2 +3x−1
を x − 1 で割った余りが 7 なので、属さない。
2.4 既約元と素元
定義 2.22（既約元） a ∈ R について、
「a の約数は自分自身か 1 のみ」のとき、すなわち「a = bc, (b, c ∈ R) なら
ば b または c は単元」となるとき、a を 既約元という。
例 16
Z における既約元とは素数のことである。
命題 2.23
R = Z あるいは k[x] (k は体) とする。p ∈ R が既約元なら、R/⟨ p ⟩ は体である。
[証明] [f ] ∈ R/⟨ p ⟩, [f ] ̸= 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 よって [a] は [f ] の逆元になっている。
定義 2.24（素元） p ∈ R について「p|(ab), (a, b ∈ R) ならば p|a または p|b」となるとき、p を 素元という。
命題 2.25
p が素元であることと ⟨ p ⟩ は素イデアルであることは、同値である。
命題 2.26
整域において 0 でない素元は既約元である。
[証明] p ̸= 0 を素元、p = ab とする。p|a または p|b なので p|a とすれば、pu = a となる u ∈ R が存在する。
p = pub よって p(1 − ub) = 0 よって ub = 1 すなわち b は単元である。p|b の時も同様。
命題 2.27
P ID において、既約元は素元である。
[証明] p を既約元とし、p|ab かつ p|a でない、とする。PID なので、⟨ p, a ⟩ は一つの要素 h で生成され、
GCD(p, a) = 1 より、h = 1 としてよい。よって、ある k, l が存在して pk + la = 1。両辺に b をかけて
pkb + lab = b。また、 p|ab より、p| 左辺、 すなわち p|b。p|b でない場合も同様。以上より p は素元である。
注 9 上の命題より、k[x] においては既約元と 0 でない素元は一致する。（実は k[x1 , x2 , · · · , xn ] においても既約
元と 0 でない素元は一致する。）
√
√
√
√
√
√
Z[ −5] = {a+b −5 | a, b ∈ Z} では 2, 3, 1+ −5, 1− −5 は既約元であるが、2·3 = (1+ −5)(1− −5)
√
なので、どれも素元ではない。つまり Z[ −5] は P ID でない。
例 17
2.5 ユークリッドの互除法の応用
例 18
F7 = Z/7Z で 3 の逆数を求める。
拡張されたユークリッドの互除法 (整数版) より、7 + (−2)3 = 1。よって、3−1 = −2 = 5。
例 19
Q[x]/⟨ x2 − 2 ⟩ で x2 + x + 1 の逆数を求める。
拡張されたユークリッドの互除法より、(x−2)(x2 −2)+(−x+3)(x2 +x+1) = 7. よって、[x2 +x+1]−1 = 17 [−x+3]。
1
1 √
= (− 2 + 3).
√
7
2 + 2+1
このことから、 √
例 20
2
微分方程式 y ′′ − y ′ − y = x2 の特殊解を求める。
3 イデアルとアフィン多様体
D=
13
d
と置く。D2 − D − 1 と D 3 について、拡張されたユークリッドの互除法により、
dx
(−2D2 + D − 1)(D2 − D − 1) + (2D − 3)D3 = 1.
よってこれを x2 に左から作用させると、
(−2D2 + D − 1)(D2 − D − 1)x2 + (2D − 3)D3 x2 = x2 .
よって、
(D2 − D − 1)(−2D2 + D − 1)x2 = x2 .
すなわち、y = (−2D2 + D − 1)x2 = −4 + 2x − x2 とおけば、
(D2 − D − 1)y = y ′′ − y ′ − y = x2 .
〔練習問題〕y ′′ − y ′ − y = sin x.
§3
(ヒント: (D − 2)(D2 − D − 1) + (−D + 3)(D2 + 1) = 5.)
イデアルとアフィン多様体
記法 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 とみなす。
• X n = {(x1 , x2 , · · · , xn ) | xi ∈ X}
• f : X n → Y, x = (x1 , x2 , · · · , xn ) に対して f (x) = f (x1 , x2 , · · · , xn ) と書く。
定義 3.1（アフィン多様体） n を自然数、k を体とする。f1 , f2 , · · · , fs ∈ k[x1 , x2 , · · · , xn ] に対してその零点
集合:
V(f1 , f2 , · · · , fs ) = {a ∈ k n | fi (a) = 0 (1 ≤ i ≤ s)}
を f1 , f2 , · · · , fs で定義されたアフィン多様体という。
1
0.5
例 21
(1) V(x2 + y 2 − 1).
-1
-0.5
0.5
-0.5
-1
3
2
(2) V(xy − x3 + 1).
1
-3
-1
-2
1
2
-1
2
1
(3) V(y 2 − x3 ).
-2
-1
1
-1
-2
2
3
1
第1章
14
代数と幾何
1
0.5
(4) V(y 2 − x3 − x2 ).
-1
-0.5
0.5
1
-0.5
-1
2
1
0
-1
-2
8
(5) V(z − x2 − y 2 ).
6
4
2
0
-2
-1
0
1
2
2
1
0
-1
-2
(6) V(z 2 − x2 − y 2 ).
2
1
0
-2
-1
0
1
2
(7) V(x2 − y 2 z 2 + z 3 ).
fi
(8) V(x + y + z, x − z, 2x + w).
(9) V(xz, yz).
1
0.75
0.5
0.25
0
1
(10) V(y − x2 , z − x3 ).
0.75
0.5
0.25
0
0
0.25
0.5
0.75
1
命題 3.2
V, W ⊂ k がアフィン多様体なら V ∩ W, V ∪ W もアフィン多様体である。
n
[証 明] 例 と し て V = V(f1 , f2 ), W = V(g1 , g2 ) と す る と 、V ∩ W = V(f1 , f2 , g1 , g2 ), V ∪ W =
V(f1 g1 , f1 g2 , f2 g1 , f2 g2 ) となる。
} 問い
(1) V(f1 , f2 , · · · , fs ) ̸= ϕ の判定。（連立 1 次方程式での解の存在）
(2) 解を求めるアルゴリズムは存在するか？（連立 1 次方程式での掃きだし法と基底）
(3) 次元の定義と決定（行列のランク）
定義 3.3（基底, 有限生成） 環 R のイデアル I が集合 S で生成されているとき、S を I の 基底 という。基底とし
て有限集合が取れるイデアルは 有限生成 であるという。
3 イデアルとアフィン多様体
15
注 10 線形代数では、基底とは「生成して独立」であることを求めるが、環では、生成するだけでよい。
定義 3.4 イデアル I ⊂ k[x1 , x2 , · · · , xn ] に対しその零点集合を
V(I) = {a ∈ k n | f (a) = 0 (∀f ∈ I)}.
と定義し、I で定義された多様体という。
命題 3.5 V(⟨ f1 , f2 , · · · , fs ⟩) = V(f1 , f2 , · · · , fs ). したがって k n の部分集合がアフィン多様体であることと
有限生成イデアルで定義された多様体であることは同値である。
[証明] 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 =
ci fi ∈ ⟨ f1 , f2 , · · · , fs ⟩ について、f (a) = ( ci fi )(a) =
ci fi (a) = 0。よって V(f1 , f2 , · · · , fs ) ⊂
V(⟨ f1 , f2 , · · · , fs ⟩)。
例 22 ⟨ 2x2 +3y 2 −11, x2 −y 2 −3 ⟩ = ⟨ x2 −4, y 2 −1 ⟩ なので、V(2x2 +3y 2 −11, x2 −y 2 −3) = V(x2 −4, y 2 −1) =
{(±2, ±1)}。つまりこれは、図形をイデアル（の基底）で考える方法を与えている。
定義 3.6 S ⊂ k n を部分集合とするとき
I(S) = {f ∈ k[x1 , x2 , · · · , xn ] | f (a) = 0 (∀a ∈ S)}.
と定義し、これを S の零化イデアルという。
補題 3.7 I(S) は k[x1 , x2 , · · · , xn ] のイデアルである。
[証明] 略。
(1) k 2 で I({(0, 0)}) = ⟨ x, y ⟩。
例 23
(2) k n で I(k n ) = {0} となるか？
• k が無限体なら、I(k n ) = {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 )
(2) I ⊂ J ⇒ V(I) ⊃ V(J)
(3) V ⊂ V(I) ⇐⇒ I(V ) ⊃ I
（V, W は k n の部分集合）
（I, J は k[x1 , x2 , · · · , xn ] のイデアル）
（V は k n の部分集合、I は k[x1 , x2 , · · · , xn ] のイデアル）
[証明] (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)).
第1章
16
代数と幾何
[証明] V(I) ⊂ V(I) なので、補題 3.8(3) を V = V(I) として適用して、I(V(I)) ⊃ I 。
注 11
I = I(V(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 , y 2 ⟩ とおくと、V(I) = {(0, 0)} なので、I(V(I)) = I({(0, 0)}) = ⟨ x, y ⟩。
√
• k が代数的閉体（任意の 1 変数の方程式が解を持つ体）なら、I(V(I)) = I が成り立ち、これを強形の零点
√
定理という。ただし I = {f ∈ k | ∃n ∈ Z≥0 f n ∈ I}。
命題 3.10
(1) 任意の集合 V ⊂ k n について
V ⊂ V(I(V )).
(2) 任意のアフィン多様体 V ⊂ k n について
V = V(I(V )).
[証明]
(1) I(V ) ⊂ I(V ) に補題 3.8(3) を I = I(V ) として適用すると、V ⊂ V(I(V ))。
(2) 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) より明らか。
注 12
一般に集合 X, Y のある部分集合族間に写像 V, I があって、
(1) A ⊂ A′
⇒
V(A) ⊃ V(A′ ).
(2) B ⊂ B ′
⇒
I(B) ⊃ I(B ′ ).
(3) 任意の A に対して I(V(A)) ⊃ A.
(4) 任意の A に対して V(I(B)) ⊃ B.
(5) A ⊂ V(B) ⇐⇒ I(A) ⊃ B.
を満たす時、V, I をその集合族間の Galois 接続という。((3)&(4) ⇐⇒ (5) である。) このとき、{A | I(V(A)) = A}
と {B | V(I(B)) = B} の間には、V, I で 1 対 1 対応が付き、これを Galois 対応と言う。
命題 3.12
k が無限体なら I(k n ) = {0}。
3 イデアルとアフィン多様体
17
[証明] 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(k t+1 )
∑
n
n
は f =
n fn (x)y , fn ∈ k[x1 , x2 , · · · , xn ] と書ける。a = (a1 , a2 , · · · , at ) ∈ k を一つ取り、F (y) =
∑
n
n fn (a)y ∈ 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 ⟩ の決定アルゴリズムはあるか？（ある）
• I → I(V(I)) はどうなってるのか？（ほぼわかる）
19
第2章
Groebner 基底
次のような問題を考えよう：
2 次正方行列 A, B があるとする。「AB = E ならば BA = E 」を示せ。
これは、もちろん線形代数学の知識があれば「AB = E だから、B = A−1 。よって、BA = A−1 A = E 。」と答え
るだろう。しかし、これはかなり高度な知識であるし、行列の各成分が体の元であることを仮定しているという点
(
)
(
)
で間違いとも言える。この問題を具体的に書いてみよう。A =
(
AB − E =
ae + bg − 1
af + bh
ce + dg
cf + dh − 1
)
= 0 から BA − E =
a
b
, B=
c d
(
ae + cf − 1
ag + ch
e
f
g
h
と置くとすれば、問題は
be + df
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
ae + cf
be + df
ag + ch
bg + dh
+
=
=
-
bg - 1, af + bh, ce + dg, cf + dh - 1]
1 = [dh, -dg, af, -ae + 1] * F
[-df, de, bf, -be] * F
[-ch, cg, ah, -ag] * F
1 = [-dh + 1, dg, -af, ae] * F
第2章
20
Groebner 基底
これはすなわち次のような恒等式が成り立っていることを示している。
ae + cf − 1 =
dh · (ae + bg − 1) − dg · (af + bh) +
be + df
=
−df · (ae + bg − 1) + de · (af + bh) +
ag + ch
=
−ch · (ae + bg − 1) + cg · (af + bh) +
bg + dh − 1 = (−dh + 1) · (ae + bg − 1) + dg · (af + bh) −
af · (ce + dg) +
bf · (ce + dg) −
ah · (ce + dg) −
af · (ce + dg) +
(−ae + 1) · (cf + dh − 1)
be · (cf + dh − 1)
ag · (cf + dh − 1)
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
が成り立つならば、= は 全順序であると言う。
(1) N = Z≥0 = {0 以上の整数 } とし、= を普通の意味の ≥ と思うと、これは全順序である。
例 24
(2) N に x = y ⇐⇒ y|x と定義すると、これは順序だが全順序でない。
(3) N2 に (x1 , y1 ) = (x2 , y2 ) ⇐⇒ x1 ≥ x2 かつ y1 ≥ y2 と定義すると、これは順序だが全順序でない。
(4) X = { グー, チョキ, パー } に対して x = y ⇐⇒ x は y にアイコであるあるいは勝つ 、と定義すると、これ
は順序ではない。
定義 1.2（順序の拡張） 集合 X に２つの順序 = と ≥ が与えられていて
α≥β ⇒ α=β
が成り立つとき、= は ≥ の 拡張であるという。
例 25
(1) N − {0} に x = y ⇐⇒ y|x と定義すると、普通の順序 ≥ は = の拡張である。
この文書では、2 つの順序を同時に考えるとき = 以外に ≥ という記号も使って区別する。しばしば、抽象的、人
工的な方を = で表し、伝統的な、標準的な順序の方を ≥ で表す。
定義 1.3
(1) x > y とは x = y かつ x ̸= y のこと。
2 順序に関するディクソンの補題
21
(2) x 5 y とは y = x のこと。
(3) x < y とは x 5 y かつ x ̸= y のこと。
1.2 最小と極小
定義 1.4（最小元, 極小元） 順序集合 (X, =) の部分集合と A と a ∈ A に対して、
(1) 「∀x ∈ A (x = a)」が成り立つとき、a を A の 最小元と言う。
(2) 「∀x ∈ A (x < a でない)」が成り立つとき、a を A の 極小元と言う。
注 13 最小元は極小元である。また、全順序集合では極小元は最小元である。
例 26 (N2 , =) において、A = {(0, 1), (1, 0)} における a = (0, 1) は極小元だが最小元でない。
1.3 積順序
定義 1.5（Nn の標準的順序） α = (α1 , α2 , · · · , αn ), β = (β1 , β2 , · · · , βn ) ∈ Nn に対して ≥ を次の様に定義
する。
α ≥ β ⇐⇒ ∀i αi ≥ βi
この ≥ を Nn の 標準的順序あるいは 自然順序という。
注 14 (Nn , ≥) は順序集合である。n ≥ 2 のとき全順序ではない。
定義 1.6（積順序） 2 つの順序集合 (X, =), (Y, =) に対して、順序集合 (X × Y, =) を次のように定義し 積順序と
言う:
(x1 , y1 ) = (x2 , y2 ) ⇐⇒ x1 = x2 かつ y1 = y2 .
注 15 積順序は順序になる。
注 16 Nn の標準的順序 ≥ は、N の標準的順序から、Nn = Nn−1 × N で帰納的に積順序で作ったものである。
§2
順序に関するディクソンの補題
多項式の次数の集合 Nn の性質について調べる。
2.1 Dickson 性
定義 2.1（生成、有限生成）
(1) X の部分集合 A に対し、ある集合 S ⊂ A について、
∀a ∈ A∃s ∈ S a = s.
となるとき、S は A を 張る、 生成する、あるいは S は A の 基底であると言う。
(2) X 部分集合 A に有限基底 (有限集合である基底) が取れるとき A は 有限生成であると言う。
定義 2.2（Dickson 性） 順序集合 (X, =) について、X の任意の部分集合が有限生成であるとき、X は Dickson
的である、あるいは Dickson 性を持つ、と言う。
例 27
(1) N の標準順序で、その任意の部分集合 A は、その最小元 a を取り、S = {a} とすれば、条件をみたす
ので、N は Dickson 的である。
第2章
22
Groebner 基底
(2) N の例 24 の (2) の順序では、N は Dickson 的でない。
補題 2.3
N の任意の数列 n1 , n2 , n3 , · · · には、その部分列で、(広義) 単調増大列になるもの、ni1 , ni2 , ni3 , · · · (i1 <
i2 < i3 < · · · ) が存在する。
[証明] I0 = N と置くと、これは無限集合であり、{ni | i ∈ I0 } の最小値 nk (k ∈ I0 ) が存在する。i1 = k と置く。
I1 = {i ∈ I0 | i1 < i} と置くと、これは無限集合であり、{ni | i ∈ I1 } の最小値 nk (k ∈ I1 ) が存在する。i2 = k
と置く。
I2 = {i ∈ I1 | i2 < i} と置くと、これは無限集合であり、{ni | i ∈ I2 } の最小値 nk (k ∈ I2 ) が存在する。i3 = k
と置く。
以下同様 i4 , i5 , · · · を選べば良い。
定理 2.4
順序集合 (X, =) が Dickson 的なら、(N, ≥) との積順序集合 (X × N, =) も Dickson 的。
[証明]X × N が Dickson 的でないとすると、ある X × N の部分集合 A が存在して、有限生成でない。
(x1 , n1 ) ∈ A を適当に取ると、{(x1 , n1 )} は A を張らないので、ある (x2 , n2 ) ∈ A について (x1 , n1 ) 5
(x2 , n2 ) とならない。{(x1 , n1 ), (x2 , n2 )} も A を張らないので、(x3 , n3 ) ∈ A で (x1 , n1 ) 5 (x3 , n3 ) も
(x2 , n2 ) 5 (x3 , n3 ) が成り立たないものが存在する。同様にして一般に (xi , ni ) ∈ A, i = 1, 2, 3, · · · が
(x1 , n1 ) 5 (xi , ni ),
(x2 , n2 ) 5 (xi , ni ), · · · ,
(xi−1 , ni−1 ) 5 (xi , ni ) のどれも成り立たないように取れる。
さて、補題 2.3 より、n1 , n2 , n3 , · · · には、その部分列で、(広義) 単調増大列になるもの、ni1 , ni2 , ni3 , · · · が
存在するこのとき、任意の s, t (s < t) について、xis 5 xit ではない。
B = {xi1 , xi2 , xi3 , · · · } とすると、明らかにどんな B の有限部分集合も B を生成しない。これは X が Dickson
的であることに矛盾する。
定理 2.5（Nn の順序に関するディクソンの補題） Nn は標準順序 ≥ に関して Dickson 的。
[証明] n = 1 のとき：N では標準順序 ≥ は Dickson 的。n = k の時 Dickson 的であるとすると、定理 2.4 より、
N
k+1
= Nk × N の時も Dickson 的。以上より、任意の n について Nn は Dickson 的。
2.2 整列性
定義 2.6（整列順序） 全順序集合 (X, =) において、任意の部分集合が最小元を持つとき = を 整列順序、(X, =)
を整列順序集合と言う。
注 17
全順序集合では、= が整列順序であることと、Dickson 的であることは同値である。
例 28
(1) (N, ≥) は整列順序。
(2) (Nn , ≥) は n ≥ 2 のとき整列順序でない。（全順序でないから。）
(3) (Z, ≥) は整列順序でない。
(4) (Q≥0 , ≥) は整列順序でない。
(5) { n1 | n = 1, 2, 3, · · · } は整列順序でない。
(6) { n1 | n = 1, 2, 3, · · · } ∪ {0} は整列順序でない。
(7) {− n1 | n = 1, 2, 3, · · · } は整列順序。
前節補題 2.3、定理 2.4、定理 2.5 と同様に以下が成り立つ。
補題 2.7
整 列 集 合 X の 任 意 の 数 列 x1 , x2 , x3 , · · · に は 、そ の 部 分 列 で 、(広 義) 単 調 増 大 列 に な る も の 、
2 順序に関するディクソンの補題
23
xi1 , xi2 , xi3 , · · · が存在する。
注 18 後の定理 2.16 で見るように、X が Dickson 的なら、同様な事が言える。
定理 2.8 順序集合 (X, =) が Dickson 的、順序集合 (Y, =) が整列順序集合なら、(X × Y, =) は Dickson 的。
定理 2.9 順序集合 (X, =) が整列順序集合なら、X n は Dickson 的。
注 19 後の定理 2.17 で見るように、X, Y が Dickson 的なら、X × Y, X n も Dickson 的。
2.3 順序のイデアル
定義 2.10（イデアル） (X, =) を順序集合、A をその部分集合で、次の条件を満たすとき、A は X の イデアルで
あるという。
∀a ∈ A∀x ∈ X(x = a ⇒ x ∈ A).
例 29 {n ∈ N | n ≥ 1} は N のイデアル。
定義 2.11
X 部分集合 S に対し、
⟨ S ⟩ = {x ∈ X | ∃s ∈ S x = s}
とおき、これを S で 生成されたイデアル という。S = {s1 , s2 , · · · , sk } と有限集合であるとき、⟨ S ⟩ を単に
⟨ s1 , s2 , · · · , sk ⟩ と書く。
命題 2.12
S を順序集合 X の部分集合とするとき、以下が言える。
(1) ⟨ S ⟩ は X のイデアルである。
(2) S がイデアル ⇐⇒ ⟨ S ⟩ = S 。
(3) 任意の イデアル A、任意の A の部分集合 S について、⟨ S ⟩ ⊂ A。
(4) S が A を生成する ⇐⇒ S ⊂ A ⊂ ⟨ S ⟩。
∪
(5) ⟨ S ⟩ = s∈S < s > である。特に、⟨ s1 , s2 , · · · , sk ⟩ = ⟨ s1 ⟩ ∪ ⟨ s2 ⟩ ∪ · · · ∪ ⟨ sk ⟩ である。
[証明] 略。
定理 2.13
Dickson 性を持つ順序集合の任意の部分集合 A に対して、ある有限部分集合 A′ ⊂ A が存在して、
⟨ A ⟩ = ⟨ A′ ⟩ となる。
[証明] A に対して、その有限基底を A′ とすると、A ⊂ ⟨ A′ ⟩ 。命題 2.12 より、⟨ A ⟩ ⊂ ⟨ A′ ⟩。よって、⟨ A ⟩ = ⟨ A′ ⟩。
定理 2.14
順序集合は、その任意のイデアルが有限生成であれば、Dickson 性を持つ。逆も言える。
[証明] 順序集合 X の任意のイデアルが有限生成であるとする。X 部分集合 S を取る。イデアル ⟨ S ⟩ は、有限個の
生成元 x1 , x2 , · · · , xn ∈ ⟨ S ⟩ を持つ。任意の i について、si 5 xi となる、s1 , s2 , · · · , sn ∈ S が存在する。この
とき、⟨ S ⟩ = ⟨ x1 , x2 , · · · , xn ⟩ ⊂ ⟨ s1 , s2 , · · · , sn ⟩。よって、s1 , s2 , · · · , sn が S の有限個の生成元になって
いる。
逆は明らか。
第2章
24
定理 2.15
Groebner 基底
X が Dickson 的であるのは次の命題とも同値である。
A1 ⊂ A2 ⊂ A3 ⊂ · · · を X のイデアルの増大列とすると、必ずある N が存在して、∀n ≥ N An = AN 。
∪
∪
[証明] X が Dickson 的であるとする。 i Ai はイデアルである。その有限基底 F ⊂ i Ai を取れば、F の各元毎
にある i が存在して Ai に属する。これらの i の最大のものを N とすると、F ⊂ AN となる。この N が求めるも
のである。
X が Dickson 的でないとし、Y ⊂ X が有限生成でないとする。A1 = {} とする。既に有限生成イデアルの狭義増
大列 A1 $ A2 $ A3 $ · · · $ Ak が作れているとするとき、Y − Ak は空集合でないから、ある x ∈ Y − Ak を取っ
て Ak+1 = ⟨ Ak ∪ {x} ⟩ とおけば、Ak $ Ak+1 である。このようにして作った An , n ≥ 1 は条件を満たさない。
2.4 Dickson 性 (別ルート)
この節では、前と別の方法で Dickson の補題を証明する。今回の講義では、特に読む必要はない。
定理 2.16（Dickson 性の同値命題） 順序集合 (X, =) について、次の 3 つは同値である。
(1) X は Dickson 性を持つ。
(2) X の任意の無限数列 S = (x1 , x2 , · · · ) には、(広義) 単調増大な部分無限数列が存在する。
(3) X の任意の無限数列 S = (x1 , x2 , · · · ) についてある i, j が存在して i < j かつ xi 5 xj となる。
[証明]
(1) ⇒ (2): 仮定より S の有限部分集合 S1 があって、S1 は S を張る。よって、ある xi1 ∈ S1 があって、xi1 5 xi
となる i は無限個になる。すなわち、J(j) = {i | j < i かつ xj 5 xi } とおくと、J(i1 ) は無限集合である。
同様にして、{xi | i ∈ J(i1 )} を張る有限集合 S2 に対し、xi2 ∈ S2 をうまく取ると、J(i2 ) も無限集合になる。以
下同様に i3 , i4 , · · · を取っていけば、i1 < i2 < i3 < i4 < · · · かつ xi1 5 xi2 5 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 が
x1 5 xn , x2 5 xn , · · · , xn−1 5 xn のどれも成り立たないように取れる。このとき、S = (x1 , x2 , · · · ) は、(3) の
条件を満たしていないので矛盾である。
定理 2.17
2 つの順序集合 (X, =), (Y, =) が Dickson 的なら、積順序を与えた (X × Y, =) も Dickson 的。
[証明] (x1 , y1 ), (x2 , y2 ), · · · を X × Y の任意の数列とする。X が Dickson 的なので、定理 2.16 の (2) より
1, 2, · · · の無限部分集合 A で {xi | i ∈ A} が単調増大になるものが取れる。また Y が Dickson 的なので、定理
2.16 の (3) の条件より A の要素 i, j (i < j) で、yi 5 yj となるものが存在する。この時、(xi , yi ) 5 (xj , yj ) が成
り立つ。すなわち、定理 2.16 の (3) が成立するので、X × Y は Dickson 的。
2.5 Noether 性 (参考)
この小節では、Dickson 性より弱い Noether 性について調べるが、この後の議論に用いられる事はない。
定義 2.18（Noether 性） (X, =) の任意の空でない部分集合 S が = に関する極小元を S の中に持つとき = は
Noether 的あるいは Noethoer 性を持つという。
2 順序に関するディクソンの補題
25
例 30 Z, Q, Q>0 は、Noether 的でないが、N は、Noether 的である。
補題 2.19
順序集合 (X, =) が Noether 的であるための必要十分条件は全ての X における狭義単調減少列
x1 > x2 > · · · が必ず有限で終わることである。
[証明] (必要性）定義より明らか。（十分性）X のある空でない部分集合 A に極小元がないとする。まず x1 ∈ A を
適当に選ぶ。A に x1 より小さい元は存在する。（そうでなければ x1 は極小元となる。）よってそれを x2 ∈ A とす
る。以下同様に x1 > x2 > x3 > · · · ∈ A が作れるので、仮定に反する。
補題 2.20
順序集合が Noether 的であるための必要十分条件は、任意の部分集合がその極小点の集合で生成される
ことである。
[証明] (必要性) 順序集合の任意の部分集合を A、その極小点の集合を M とする。M が A を生成しないとすれば、
ある a1 ∈ A が存在して、極小点でない。よって、ある a2 ∈ A が存在して、a1 > a2 である。どんな m ∈ M に対し
ても a1 ≥ m とならないので、a2 も極小点ではない。
同様に a1 > a2 > a3 > . . . となる ai ∈ A が存在する。これは、補題 2.19 より、矛盾である。
(十分性) 空でない部分集合が M で生成されるとき、M は空でない。よって、任意の空でない部分集合がその極小
点の集合 M で生成されていれば、M は空でない。よって Noether 性を持っている。
定理 2.21
Dicskon 的であるための必要十分条件は、Noether 的であり、かつ全ての部分集合の極小元の集合が有限
であることである。
[証明] (必要性) Dicskon 的であるとする。補題 2.19 より、もし Noether 的でなければ、その集合には狭義単調減少
数列があるが、これはあきらかに有限な基底はないので Dickson 的でない。よって Noether 的である。
また、極小元の集合の生成元は、それ自身でなければならないので、有限集合である。
(十分性) Nother 的なので、補題 2.20 より、任意の部分集合はその極小元の集合で生成され、それが有限集合なの
だから、Dickson 的であることになる。
例 31 Noether 的であっても Dickson 的であるとは限らない。例えば無限集合 X 上で = を空（任意の x, y ∈ X
について x > y でない）とすると、これは Noether 的だが Dickson 的でない。
系 2.22 全順序集合では、順序が Noether 的であることと Dickson 的であることは同値である。
[証明] 整列集合であるとする。部分集合の最小元はそれ１つでその部分集合を張っているから Dickson 的である。逆
は補題 2.21 より。
定理 2.23
2 つの順序集合 (X, =), (Y, =) が Noether 的なら、積順序を与えた (X × Y, =) も Noether 的。
[証明] A ⊂ X × Y とする。定理 2.20 より、A の極小点の集合が A を生成していることを言えば良い。
そうでないとする。ある (x1 , y1 ) ∈ A が存在して A の極小点の集合で生成されない。よって、(x1 , y1 ) が極
小でないので、ある点 (x2 , y2 ) ∈ A が存在して、(x1 , y1 ) > (x2 , y2 ) となる。このとき、(x3 , y3 ) も極小でな
いので、ある点 (x3 , y3 ) ∈ A が存在して、(x2 , y2 ) > (x3 , y3 ) となる。以下同様にして、狭義単調減少無限列、
(xi , yi ) ∈ A, i ≥ 1 が存在する。このとき、{xi } と {yi } のいずれかは、無限集合である。{xi } が無限集合だとする
と、この集合に極小点は存在せず、X が Noether 的である事と矛盾する。{yi } が無限集合だとしても同様。
第2章
26
§3
Groebner 基底
単項式順序と整除
3.1 順序集合 Nn の単項式順序
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 の ≥ に関する有限基底 A′ ⊂ A が存
在する。A′ の = に関する最小の元を α0 とする。任意の α ∈ A に対して、ある α′ ∈ A′ があって、α ≥ α′ 。仮定よ
り α = α′ = α0 。すなわち α0 は A の = に関する最小元である。よって = は整列順序である。
(2) ⇒ (3): 整列順序なのに α < 0 となる α が存在したとすると、α > α + α > α + α + α > · · · となり、この数
列に最小が存在せず矛盾する。
(3) ⇒ (1): α ≥ β とすれば、α − β ∈ Nn よって、仮定より α − β = 0。両辺に β を加えて α = β 。よって = は
≥ の拡張である。
定義 3.3（Nn の単項式順序） Nn の 単項式順序（あるいは単に 項順序）とは、順序であって次の条件を満たすもの
を言う。
(1) = は標準的順序の拡張である
(2) = は Nn の全順序
(3) = は + と 両立する
定理 3.4
Nn の単項式順序は整列順序である。
[証明] 定理 3.2 より。
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 は単項式順序である。
3 単項式順序と整除
27
[証明] 明らか。
記法 4
α = (α1 , α2 , · · · , αn ) に対し |α| =
∑
α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 は単項式順序である。
[証明] 明らか。
例 32 {(3, 0, 0), (2, 0, 2), (1, 2, 1)} を大きい順に並べる
lex
(3, 0, 0)
(2, 0, 2)
(1, 2, 1)
grlex
(2, 0, 2)
(1, 2, 1)
(3, 0, 0)
grevlex
(1, 2, 1)
(2, 0, 2)
(3, 0, 0)
注 20 N2 では grlex と grevlex は同じである。
3.3 “単項式の” 単項式順序
定義 3.11（単項式） α = (α1 , α2 , · · · , αn ) に対して xα = x1 α1 x2 α2 · · · xn αn ∈ k[x1 , x2 , · · · , xn ] とおき、これ
を 単項式と言う。
注 21 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γ が成り立つ）。
第2章
28
例 33
Groebner 基底
同じ式の単項式の降べき（大きい順）表示
−5x3 + 7x2 z 2 + 4xy 2 z + 4z 2 (lex)
= 7x2 z 2 + 4xy 2 z − 5x3 + 4z 2 (grlex)
= 4xy 2 z + 7x2 z 2 − 5x3 + 4z 2 (grevlex)
以下、k[x1 , x2 , · · · , xn ] に単項式順序 = を一つ固定する。
定義 3.14
∑
多項式 f =
aα xα について f ̸= 0 のとき次のように定義する。
α∈Nn
• deg(f ) = multideg(f ) = max{α | aα ̸= 0}.
• LC(f ) = adeg(f )
• LM(f ) = x
···
deg(f )
···
• LT(f ) = adeg(f ) x
deg(f )
• RT(f ) = f − LT(f )
···
多重次数
先頭係数 (leading coefficient)
先頭単項式 (leading monomial)
···
···
先頭項 (leading term)
残余 (rest term)
注 22
LT(f )|LT(g) は deg f ≤ deg g と同値となる。
注 23
f, RT(f ) ̸= 0 なら、deg f > deg RT(f )(単項式順序で) である。
例 34
f = −5x3 + 7x2 z 2 + 4xy 2 z + 4z 2 について lex で考えると
• deg(f ) = (3, 0, 0)
• LC(f ) = −5
• LM(f ) = x3
• LT(f ) = −5x3
• RT(f ) = 7x2 z 2 + 4xy 2 z + 4z 2
命題 3.15
f, g ̸= 0 について
(1) deg(f g) = deg(f ) + deg(g).
(2) f + g ̸= 0 ⇒ deg(f + g) 5 max{deg(f ), deg(g)}.
(3) f + g ̸= 0 かつ deg(f ) ̸= deg(g) ⇒ deg(f + g) = max{deg(f ), deg(g)}.
3.4 多変数多項式の整除
定理 3.16（割り算アルゴリズム） f, f1 , f2 , · · · , fs ∈ k[x1 , x2 , · · · , xn ] とする。単項式順序 = を選び固定す
る。f の F = (f1 , f2 , · · · , fs ) による 割り算とは次の条件を満たすものであり、以下に述べるアルゴリズムで得る
ことができる。
(1) f = a1 f1 + a2 f2 + · · · + as fs + r
a1 , a2 , · · · , as , r ∈ k[x1 , x2 , · · · , xn ].
(2) （r = 0） または（r ̸= 0 で、全ての i について LT(fi ) は r のどの単項式も割ることはない。）
(3) ai fi ̸= 0 ならば deg(f ) = deg(ai fi )。
注 24
特に (2) より、全ての i について deg r ̸≥ deg fi である。ここの不等号のみ自然順序 ≥ であり、deg を定め
る方法および、上の (3) の条件は、= で決定されている。
3 単項式順序と整除
29
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 などと書いた。）
例 35 lex での (x2 y + xy 2 + y 2 ) ÷ (xy − 1, y 2 − 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) を使う。
F
定義 3.17（ ,
mod F ） f を被除数 (dividend)、f1 , f2 , · · · , ft あるいは F = (f1 , f2 , · · · , ft ) を除数
(divisor)、a1 , a2 , · · · , at を商 (quotient)、r を余り (remainder) と言う。
rをf
F
あるいは remainder(f, F ) あるいは f mod F と書く。
途中に現れる p を中間被除数 (intermediate dividend) と呼ぶ。
〔練習問題 A〕lex 順序で、x + y を (x + 1, y) で割った、商と余りを求めよ。
〔練習問題 B〕grlex 順序で、x4 + xy 3 を (x3 − xy, x2 y − y 2 , xy) で割った、商と余りを求めよ。
定理 3.18
前定理の a1 , a2 , · · · , at は、条件 (1), (2), (3) に加えて次の条件を満たす。
(4) ∀i 5 s + 1 ai fi ∈ ⟨ fi ⟩ − ⟨ f1 ⟩ − ⟨ f2 ⟩ − · · · − ⟨ fi−1 ⟩.
ただし、fs+1 = 1, as+1 = r と置いた。
また、条件 (1), (2), (3), (4) を満たす。a1 , a2 , · · · , at , r は、唯一である。
[証明] 略。(参考文献『グレブナ基底と代数多様体入門（上）』の P.98 練習問題 11 を参照。) 定理 3.19
任意の F = (f1 , f2 , · · · , fs ) に対し (
F
) は k 上線形である。
第2章
30
Groebner 基底
[証明] 略。(同上練習問題 12 を参照。) 例 36
(1) F の順番によって、余りが変わる。
(xy 2 − x) ÷ (xy − 1, y 2 − 1) = (y, 0)
(xy 2 − x) ÷ (y 2 − 1, xy − 1) = (x, 0)
· · · (−x + y) [lex].
···0
[lex].
(2) 順序の取り方によって、余りが変わる。(lex と grlex)
(xy + y 2 ) ÷ (x + y 2 ) =
(xy + y 2 ) ÷ (x + y 2 ) =
y
1
· · · (−y 3 + y 2 )
· · · (xy − x)
[lex].
[grlex].
(3) 順序の取り方によって、余りが変わる。(x > y と y > x)
(x + y 2 ) ÷ (x + y) =
(y 2 + x) ÷ (y + x) =
注 25
1
y−x
· · · (y 2 − y) [lex, x > y].
· · · (x2 + x) [lex, y > x].
f mod F = 0 ならば f ∈ ⟨ F ⟩ である。一方、例 36 の (1) にあるように、f mod F ̸= 0 だからといって、
f ̸∈ ⟨ F ⟩ とは言えない。
注 26
割り算アルゴリズムには、次の様な流儀もある。ループが 3 段になるが、こちらの方が自然に思えるかもしれ
ない。
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 DO
WHILE p != 0 AND LT(f_i) divides LT(p) DO
a_i := a_i + LT(p) / LT(f_i)
p := p - ( LT(p) / LT(f_i) ) * f_i
sw := True
i := i + 1
IF sw = False THEN
r := r + LT(p)
p := p - LT(p)
このアルゴリズムで得られる商と余りの満たす条件は、定理 3.16 と同じだが、商と余りそのものは、違うものにな
る可能性がある。
例えば、lex で、x2 y + xy 2 を (y 2 , xy − 1) で割ると、定理 3.16 のアルゴリズムでは、商 (x, x) 余り x であるが、
このアルゴリズムでは、商 (0, x + y) 余り x + y である。また、x2 y
§4
F
ヒルベルトの基底定理とグレブナ基底
これ以降、Nn の標準順序の拡張である単項式順序 = を１つ定めておく。
記法 5
F を k[x1 , x2 , · · · , xn ] の部分集合とするとき
deg F
= {deg f |f ∈ F, f ̸= 0}
LT(F ) = {LT(f )|f ∈ F, f ̸= 0}
LM(F ) = {LM(f )|f ∈ F, f ̸= 0}
等々と定義する。
F
= x, xy 2 = 0 なので、線形性も無い。
4 ヒルベルトの基底定理とグレブナ基底
31
命題 4.1 I がイデアルなら deg I も標準順序 ≥ に関するイデアルである。
[証明] (略)。
} 問い 集合 F ⊂ k[x1 , x2 , · · · , xn ] で生成されるイデアル ⟨ F ⟩ に対し、一般に deg ⟨ F ⟩ ⊃ ⟨ deg F ⟩ である。で
は、いったい、いつ
deg ⟨ F ⟩ = ⟨ deg F ⟩
となるか？
定義 4.2（グレブナ基底） ある単項式順序 = を固定し、deg は = で定めるものとする。イデアル I の有限部分集
合Gで
deg I = ⟨ deg G ⟩
となるとき G を I の グレブナ基底あるいは 標準基底と言う。ここで、右辺のイデアルは、標準順序 ≥ によるもの
とする。
命題 4.3 イデアル I の有限部分集合 G が、グレブナ基底であるための必要十分条件は、任意の f ∈ I に対し、ある
g ∈ G が存在して、deg g ≤ deg f となることである。
命題 4.4 イデアル I の有限部分集合 G が、グレブナ基底であるための必要十分条件は、任意の f ∈ I に対し、ある
g ∈ G が存在して、LT(g)|LT(f ) となることである。
定理 4.5 イデアル I のグレブナ基底 G は I の基底である。すなわち I = ⟨ G ⟩ である。
[証明] 定理 3.16 のアルゴリズムで f ∈ I を G = (g1 , g2 , · · · , gt ) によって割った商を a1 , a2 , · · · , at 、余りを r
とする。このとき、r = f − a1 g1 − · · · − at gt ∈ I 。もし r ̸= 0 とすると全ての i について deg gi ̸≤ deg r となり、
G がグレブナ基底であることと矛盾する。
例 37 G が単項式からなる集合であれば、deg ⟨ G ⟩ は deg G で生成されるので、G は ⟨ G ⟩ のグレブナ基底である。
例 38 以下、lex 順序で考える。
(1) F = (x, x + y) とおく。⟨ F ⟩ = ⟨ x, x + y ⟩ = ⟨ x, y ⟩ である。deg ⟨ F ⟩ = ⟨ (1, 0), (0, 1) ⟩、一方、
⟨ deg F ⟩ = ⟨ (1, 0), (1, 0) ⟩ = ⟨ (1, 0) ⟩ なので、F は、⟨ F ⟩ のグレブナ基底でない。
(2) F = (x3 , x2 y + x) とおく。x = y 2 x3 + (1 − xy)(x2 y + x) を考えると、⟨ F ⟩ = ⟨ x ⟩ である。deg ⟨ F ⟩ =
⟨ (1, 0) ⟩、一方、⟨ deg F ⟩ = ⟨ deg(x3 ), deg(x2 y + x) ⟩ = ⟨ (3, 0), (2, 1) ⟩ なので、F は、⟨ F ⟩ のグレブナ
基底でない。
(3) G = (x + y, y − z) とおくと、 これは ⟨ G ⟩ のグレブナ基底である。これを言うためには、deg ⟨ G ⟩ ⊂
⟨ deg(x + y), deg(y − z) ⟩ を言えばよい。そのために、f ∈ ⟨ G ⟩, f ̸= 0 に対して “(1, 0, 0) ≤ deg f または
(0, 1, 0) ≤ deg f ” を言おう。仮に、これが否定されるならば、
LT(f ) は z だけの式。よって、f も z だけ
   
x
−t
   



の式 f (z)。ところで、f は  y  =  t 
 上で 0 であるはず。よって f (t) = 0 これは f ̸= 0 と矛盾する。
z
t
定理 4.6（グレブナ基底の存在定理） 体 k 上の多項式環 k[x1 , x2 , · · · , xn ] の任意のイデアル I (̸= 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. 第2章
32
Groebner 基底
定理 4.7（ヒルベルトの基底定理） 体 k 上の多項式環 k[x1 , x2 , · · · , xn ] の任意のイデアルは有限生成イデアルで
ある。
[証明] 生成元としてそのイデアルのグレブナ基底を取ればよい。
系 4.8 I1 ⊂ I2 ⊂ · · · を k[x1 , x2 , · · · , xn ] のイデアルの増大列とするとき、ある i0 が存在して Ii = Ii0 , (∀i ≥ i0 )
となる。
[証明] (定理 2.15 の証明と同様である。)
∪
i Ii
はイデアルである。その有限基底 F ⊂
∪
i Ii
を取れば、F の各元毎
にある i が存在して Ii に属する。これらの i の最大のものを i0 とすると、F ⊂ Ii0 となる。この i0 が求めるもの
である。
系 4.9 k[x1 , x2 , · · · , xn ] の任意のイデアル I について V(I) = {x ∈ k n | ∀f ∈ I f (x) = 0} はアフィン多様体で
ある。
§5
グレブナ基底の性質
5.1 正規形
定理 5.1
G = (g1 , g2 , · · · , gt ) をイデアル I のグレブナ基底とすれば、任意の f ∈ k[x1 , x2 , · · · , xn ] に対して
次を満たす r がただ１つ存在する。
(1) ある g ∈ I が存在して f = g + r。
(2) r = 0、または r ̸= 0 で r のどの単項式の deg も、どの deg gi より (標準順序 ≥ で) 大きく (あるいは等しく)
ない。
[証明] 存在は G により割り算（定理 3.16）により明らか。
一意性は f = g + r = g ′ + r′ とすると r′ − r = g − g ′ ∈ I であり、これが 0 でないとすると deg(r − r′ ) ∈ deg I ⊂
⟨ deg G ⟩ = ⟨ deg g1 , deg g2 , · · · , deg gt ⟩。よってある i で deg gi ≤ deg(r′ − r)。これは r または r′ のある単項
式の deg が ≥ deg gi となって矛盾である。
定義 5.2（正規形） f ∈ k[x1 , x2 , · · · , xn ] ⊃ I : イデアル で、G = (f1 , f2 , · · · , ft ) が I のグレブナ基底である
とき f
G
は G の中の fi の順番に依存しない。また、定理 5.1 の条件 (1), (2) を満たす r は f
G
である。これを f
の（G による） 正規形という。
系 5.3 G をイデアル I のグレブナ基底とすると
f ∈ I ⇐⇒ f
G
= 0.
[証明] ⇐ は明らか。 ⇒ は f = f + 0 に定理 5.1 を適用して f
G
= 0. } 問い F = (f1 , f2 , · · · , ft ) がグレブナ基底になるのはどんな時か？ F から、⟨ F ⟩ のグレブナ基底をどうやって
見つけるか？
5 グレブナ基底の性質
33
5.2 S-多項式
以下、> と < は、ある固定した単項式順序 = と 5 による不等号とする。
定義 5.4（S-多項式） xγ を LM(f ) と LM(g) の最小公倍数とするとき、
xγ
xγ
f−
g
LT(f )
LT(g)
= f と g の先頭項を相殺させた式
S(f, g) =
を f と g の S 多項式という。
3
例 39 grlex で f = x3 y 2 −x2 y 3 +x, g = 3x4 y +y 2 を考えると xγ = x4 y 2 , S(f, g) = xf − y3 g = −x3 y 3 +x2 − y3 .
注 27 S(f, g) ̸= 0 であるとき、以下が成り立つ。
(1) deg S(f, g) < deg LCM(LT(f ), LT(g)).
(2) deg f = deg g ⇒ deg S(f, g) < deg f .
f
g
(3) deg f = deg g ⇒ S(f, g) =
−
.
LC(f ) LC(g)
(4) c, c′ ∈ k, c ̸= 0, c′ ̸= 0 ⇒ S(c · f, c′ · 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)) とおくと、
(xα f, xβ g) =
xδ · xα f
xδ · xβ g
xγ f
xγ f
δ−γ
−
=
x
(
−
) = xδ−γ S(f, g).
LM(xα f ) LM(xβ g)
LM(f ) LM(g)
定義 5.5 δ ∈ Nn , f1 , f2 , · · · , ft ∈ k[x1 , x2 , · · · , xn ] に対してイデアル ⟨ f1 , f2 , · · · , ft ⟩ の部分ベクトル空
間を
∑
⟨ f1 , f2 , · · · , ft ⟩δ = { i ai fi | ai ∈ k[x1 , x2 , · · · , xn ], ∀i deg(ai fi ) 5 δ}
と定義する。同様に集合 F ⊂ k[x1 , x2 , · · · , xn ] に対して ⟨ F ⟩δ を定義する。
注 28 ⟨ F ⟩ = ⟨ G ⟩ だからといって、⟨ F ⟩δ = ⟨ G ⟩δ となるとは限らない。
注 29 任意の δ ∈ Nn に対して次が言える。
(1) ⟨ F ⟩δ + ⟨ G ⟩δ = ⟨ F ∪ G ⟩δ .
(2) fi | gi (1 ≤ i ≤ t) ⇒ ⟨ g1 , g2 , · · · , gt ⟩δ ⊂ ⟨ f1 , f2 , · · · , ft ⟩δ .
単項式順序 = は整列順序であるから、f ∈ ⟨ F ⟩ となる f に対して、f ∈ ⟨ F ⟩δ となる δ に最小値がある。そこで、
次のように定義する。
定義 5.6 f ∈ ⟨ F ⟩, f ̸= 0 に対し、
degF f = min{δ ∈ N | f ∈ ⟨ F ⟩δ }
注 30 このとき、degF f = deg f である。
注 31 f
F
= 0 のとき、f ∈ ⟨ F ⟩ のみならず、 f ∈ ⟨ F ⟩deg f すなわち、degF f = deg f が言える。
補題 5.7 f ∈ ⟨ F ⟩, f ̸= 0 に対し、degF f = deg f とするとき、次が成り立つ。
(1) ⟨ f ⟩δ ⊂ ⟨ F ⟩δ ,
∀δ ∈ Nn .
(2) deg f ∈ ⟨ deg F ⟩.
第2章
34
af ∈ ⟨ F ⟩δ 。
(2) LT(f ) =
∑
ai fi , fi ∈ F deg(ai fi ) 5 deg f と書けている。
∑
(a ∈ k[x1 , x2 , · · · , xn ]) に対して、af = i aai fi , deg(aai fi ) 5 deg af 5 δ 。よって、
[証明] degF f = deg f なので、f =
(1) 任意の af ∈ ⟨ f ⟩δ
Groebner 基底
∑
deg(ai fi )=deg f
i
LT(ai )LT(fi )。よって deg(ai fi ) = deg f となる i が少なくとも１つ存在するの
で、deg fi ≤ deg f 。
注 32
上の 2 つの結論は、単に f ∈ ⟨ F ⟩ という仮定だけからは言えない。
例: f = y, F = (x + y, x), δ = (0, 1), lex のとき y ̸∈ ⟨ x + y, x ⟩(0,1) = {0}, degF y = (1, 0) であり、
deg(y) ̸∈ ⟨ deg(x + y), deg(x) ⟩ = ⟨ (1, 0) ⟩ でもある。
系 5.8 F が ⟨ F ⟩ のグレブナ基底であるための必要十分条件は、
任意の 0 でない f ∈ ⟨ F ⟩ に対して、degF f = deg f
であることである。
[証明] (必要性)F がグレブナ基底ならば、系 5.3 より、 任意の 0 でない f ∈ ⟨ F ⟩ に対して、f
F
= 0 である。よっ
て、degF f = deg f である (注 31)。
(十分性) 補題 5.7(2) より、f ̸= 0, f ∈ ⟨ F ⟩ について、deg f ∈ ⟨ deg F ⟩。すなわち、deg ⟨ F ⟩ ⊂ ⟨ deg F ⟩ 。よっ
て F はグレブナ基底である。
以下、Nn に対する不等号 < と > は、単項式順序 5 と = に対応するものとする。
補題 5.9
f1 , f2 , · · · , ft は全て deg が δ に等しいとする。f =
∑
i ci fi ,
(ci ∈ k) について deg f < δ とすれば f
は S(fi , fj ) の k 上の 1 次結合である。
∑
= c1 (f1 − f2 ) + (c1 + c2 )(f2 − f3 ) + · · · + (c1 + c2 + · · · +
∑
ct−1 )(ft−1 − ft ) + (c1 + c2 + · · · + ct )ft . 各 fi − fi+1 と
の deg は δ より小さいので c1 + c2 + · · · + ct = 0. ゆ
∑
えに i ci fi = c1 S(f1 , f2 ) + (c1 + c2 )S(f2 , f3 ) + · · · + (c1 + c2 + · · · + ct−1 )S(ft−1 , ft ). [証明] LC(fi ) = 1 としてよい。このとき
定義 5.10
i ci fi
F = {f1 , f2 , · · · , ft } に対して
S(F, F ) =
T (F )
=
{S(fi , fj ) | 1 ≤ i < j ≤ t}
F ∪ S(F, F )
とおく。
補題 5.11
F = {f1 , f2 , · · · , ft }, f ∈ ⟨ F ⟩ とするとき、degF f > deg f =⇒ degF f > degT (F ) f = deg f で
ある。
[証明] δ = degF f とおく。f ∈ ⟨ F ⟩δ なので、f =
のが存在する。
∑
i
ai fi , ai ∈ k[x1 , x2 , · · · , xn ] で、deg(ai fi ) 5 δ となるのも
∑
f=
LT(ai )fi + f ′
deg(ai fi )=δ
と書き直せば、右辺 f ′ の次数は δ より小さいので、
∑
の次数も δ より小さい。よって補題 5.9 より、
S(LT(ai )fi , LT(aj )fj ) の 1 次結合で書けるが、
δ1 = max{deg S(LT(ai )fi , LT(aj )fj ) | i < j, deg(ai fi ) = deg(aj fj ) = δ}
とおくと δ1 < δ であり、かつ、
∑
∈ ⟨ S(LT(ai )fi , LT(aj )fj ) | i < j ⟩δ1
∑
は
6 ブッフベルガーのアルゴリズム
35
である。一方、注 27(5) より、S(fi , fj ) | S(LT(ai )fi , LT(aj )fj ) なので、注 29(2) を使うと、
∑
∈ ⟨ S(fi , fj ) | i < j ⟩δ1 = ⟨ S(F, F ) ⟩δ1
となる。一方、f ′ も ⟨ F ⟩δ2 (δ2 < δ) に含まれるので、δ ′ = max{δ1 , δ2 } < δ とおけば
f ∈ ⟨ S(F, F ) ⟩δ′ + ⟨ F ⟩δ′ = ⟨ T (F ) ⟩δ′
となる。よって、degT (F ) f < degF f である。
定理 5.12（ブッフベルガーの S ペア判定条件） ある単項式順序を固定する。G = (g1 , g2 , · · · , gs ) がイデアル I
の基底であるとき G が I のグレブナ基底であるための必要十分条件は
G
S(gi , gj ) = 0 (全ての i ̸= j について)。
G
[証明] ( ⇒ ) S(gi , gj ) ∈ I = ⟨ G ⟩ より S(gi , gj ) = 0 (系 5.3 より)。
G
( ⇐ ) S(gi , gj )
= 0 より、degG S(gi , gj ) = deg S(gi , gj ) である。補題 5.7(1) より、任意の δ に対して
⟨ S(gi , gj ) ⟩δ ⊂ ⟨ G ⟩δ 。よって、⟨ T (G) ⟩δ = ⟨ G ⟩δ 。従って、任意の 0 でない f ∈ I = ⟨ G ⟩ に対して degG f =
degT (G) f である。よって、補題 5.11 より、degG f = deg f でなければならない。故に、系 5.8 より、G は、グレブ
ナ基底である。
〔練習問題〕G = (x + y, y − z) とおくとき、 これが ⟨ G ⟩ の lex 順序によるグレブナ基底であることを示しなさい。
(c.f. 例 38)
§6
ブッフベルガーのアルゴリズム
6.1 ブッフベルガーのアルゴリズム
定理 6.1（ ブッフベルガーのアルゴリズム） I = ⟨ f1 , f2 , · · · , fs ⟩ について次のアルゴリズムでグレブナ基底を構
成できる。
Input: F = (f_1, f_2, ..., f_s)
Output: G = (g_1, g_2, ..., g_t) : <F>のグレブナ基底
G := F
REPEAT
G’ := G
For each pair {p, q}, p != q, in G’ DO
S := S(p, q) mod G’
IF S != 0 THEN G := G + (S)
UNTIL G = G’
F
[証明] (停止性) S(F, F ) = {S(fi , fj ) | 1 ≤ i < j ≤ s} − {0}, T (F ) = F ∪ S(F, F ) とおくと、REPEAT におけ
i
る G’ から G を作る操作は、G = T (G′ ) と表される。さて、⟨ deg T (F ) ⟩ (i = 0, 1, 2, · · · ) は、イデアルの増大列で
i
i0
あるから、定理 2.15 より、ある i0 が存在して ⟨ deg T (F ) ⟩ (i ≥ i0 ) は全て等しくなる。特に G0 = T (F ) とおけ
ば ⟨ deg T (G0 ) ⟩ = ⟨ deg G0 ⟩、よって、deg S(G0 , G0 ) ⊂ ⟨ deg G0 ⟩。ゆえに S(g, g ′ )
deg は deg G0 のいずれかの元より ≥ となるが、このような元は割り算 G0
G0
(g, g ′ ∈ G0 ) の全ての元の
の性質を考えると存在しない。よっ
て、S(G0 , G0 ) = {}。これはこの REPEAT が i0 回以下で停止する事を意味している。
i0
(正当性) またこのとき 定理 5.12 より、G0 = T (F ) は ⟨ G0 ⟩ = ⟨ F ⟩ のグレブナ基底である。
第2章
36
補題 6.2
(1) f
(2) f
(3) f
F
F
F
Groebner 基底
次が成り立つ。
=0 ⇒ f
F +(g)
=f ⇒ f
F +(f )
=r ⇒ f
[証明] (1) f
F
F +(r)
= 0.
= 0.
= 0.
= 0 なら f
が True になる。よって f
F +(g)
F +(g)
を求める定理 5.1 の割り算アルゴリズムで、LT(g) による割り算をする直前に sw
で起こる割り算は f
F
のそれと全く同じなので、f
F +(g)
= 0。
(2) 割り算アルゴリズム１回目のループで F による商は 0、更に f で商 1 が立って余りが 0 になる。
(3) 余りを求める演算が線形であること (定理 3.19) を利用すると、r = f
よって (1) より f − r
F +(r)
= 0。一方、f − r
F +(r)
=f
F +(r)
F
− rF +(r) = f
ならば f − r
F +(r)
F
F
F
= f −rF = f −r = 0。
(∵ rF = r と (2))。∴ f
F +(r)
= 0.
定理 6.3（ブッフベルガーのアルゴリズムの改良版） ブッフベルガーのアルゴリズム次の方法でもグレブナ基底は求
まる。
Input: F = (f_1, f_2, ..., f_s)
Output: G = (g_1, g_2, ..., g_t) : <F>のグレブナ基底
G := F
B := {(i, j) : 1 <= i < j <= s}
t := s
WHILE B != {} DO
Select (i, j) in B
S := S(f_i, f_j) mod G
IF S != 0 THEN
t := t + 1
f_t := S
G := G + (f_t)
B := B + {(i, t) : 1 <= i < t}
B := B - {(i, j)}
[証明] (停止性) IF の条件部の S ̸= 0 が有限回で終わる。なぜなら、S = ft
G
̸= 0 なら deg(G + (S)) ̸⊂ ⟨ deg G ⟩ な
ので、IF の本体で deg G は真に増加する事になるが、これは定理 2.15 より有限で終わらなければならないからであ
る。一方、WHILE には 1 回毎に B の元を 1 つ減らす動作が入っているので、WHILE は有限回で停止する。
(正当性) WHILE が停止した時の G を G∞ とおく。任意の (i, j) について、IF の条件部でテストが行われた時、も
し S(fi , fj )
G
= 0 であれば、G∞ は G の右に更に項を足したものなので、補題 6.2(1) により、S(fi , fj )
G
いえる。S = S(fi , fj )
G+(S)
̸= 0 であれば、補題 6.2(3) より S(fi , fj )
たものなので、先と同様に S(fi , fj )
G∞
=0が
= 0。G∞ は G + (S) の右に更に項を足し
= 0 が成立する。
G∞
以上より、全ての (i, j) について、S(fi , fj )
例 40
G∞
= 0 なので、定理 5.12 より、G はグレブナ基底である。
R = k[x, y] で x > y の grlex で考えて
f1 = x3 − 2xy
f2 = x2 y − 2y 2 + x
とおくとき、I = ⟨ f1 , f2 ⟩ のグレブナ基底を求めよ。
6 ブッフベルガーのアルゴリズム
37
[解] I のグレブナ基底は G = {f1 , f2 , f3 , f4 , f5 }。 但し、
f3 = −x2
f4 = −2xy
f5 = −2y 2 + x.
(計算の詳細)
Calculation of Groebner Basis of (grlex):
f1 = x^3 - 2xy
f2 = x^2y - 2y^2 + x
----------------------------------------------------------------G = (f1, f2)
= (x^3 - 2xy, x^2y - 2y^2 + x)
B = {(1, 2)}
Round 1
S(f1, f2) = (y) * f1 - (x) * f2 = -x^2.
(-x^2) mod G = -x^2.
Description of mod: (null)
New Generator: f3 = -x^2
----------------------------------------------------------------G = (f1, f2, f3)
= (x^3 - 2xy, x^2y - 2y^2 + x, -x^2)
B = {(1, 3), (2, 3)}
Round 2
S(f1, f3) = (1) * f1 - (-x) * f3 = -2xy.
(-2xy) mod G = -2xy.
Description of mod: (null)
New Generator: f4 = -2xy
----------------------------------------------------------------G = (f1, f2, f3, f4)
= (x^3 - 2xy, x^2y - 2y^2 + x, -x^2, -2xy)
B = {(2, 3), (1, 4), (2, 4), (3, 4)}
Round 3
S(f2, f3) = (1) * f2 - (-y) * f3 = -2y^2 + x.
(-2y^2 + x) mod G = -2y^2 + x.
Description of mod: (null)
New Generator: f5 = -2y^2 + x
----------------------------------------------------------------G = (f1, f2, f3, f4, f5)
= (x^3 - 2xy, x^2y - 2y^2 + x, -x^2, -2xy, -2y^2 + x)
B = {(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)}
Round 4
S(f1, f4) = (y) * f1 - (-1/2x^2) * f4 = -2xy^2.
(-2xy^2) mod G = 0.
Description of mod:
#1 -2xy^2 => a[4] += y
Round 5
S(f2, f4) = (1) * f2 - (-1/2x) * f4 = -2y^2 + x.
(-2y^2 + x) mod G = 0.
Description of mod:
#1 -2y^2 + x => a[5] += 1
Round 6
S(f3, f4) = (-y) * f3 - (-1/2x) * f4 = 0.
(0) mod G = 0.
Description of mod: (null)
Round 7
S(f1, f5) = (y^2) * f1 - (-1/2x^3) * f5 = 1/2x^4 - 2xy^3.
(1/2x^4 - 2xy^3) mod G = 0.
Description of mod:
#1 1/2x^4 - 2xy^3 => a[1] += 1/2x
#2 -2xy^3 + x^2y => a[4] += y^2
#3 x^2y => a[4] += -1/2x
Round 8
S(f2, f5) = (y) * f2 - (-1/2x^2) * f5 = 1/2x^3 - 2y^3 + xy.
(1/2x^3 - 2y^3 + xy) mod G = 0.
Description of mod:
#1 1/2x^3 - 2y^3 + xy => a[1] += 1/2
#2 -2y^3 + 2xy => a[5] += y
#3 xy => a[4] += -1/2
Round 9
S(f3, f5) = (-y^2) * f3 - (-1/2x^2) * f5 = 1/2x^3.
(1/2x^3) mod G = 0.
Description of mod:
#1 1/2x^3 => a[1] += 1/2
第2章
38
Groebner 基底
#2 xy => a[4] += -1/2
Round 10
S(f4, f5) = (-1/2y) * f4 - (-1/2x) * f5 = 1/2x^2.
(1/2x^2) mod G = 0.
Description of mod:
#1 1/2x^2 => a[3] += -1/2
RESULT
G = (
f1 =
f2 =
f3 =
f4 =
f5 =
)
=================================================================
x^3 - 2xy,
x^2y - 2y^2 + x,
-x^2,
-2xy,
-2y^2 + x
〔練習問題〕以下、lex 順序で考える。
(1) F = (x, x + y) に対し、⟨ F ⟩ のグレブナ基底を求めなさい。
(2) F = (x3 , x2 y + x) に対し、⟨ F ⟩ のグレブナ基底を求めなさい。
(c.f. 例 38)
6.2 極小グレブナ基底・簡約グレブナ基底
定義 6.4（極小グレブナ基底, 簡約グレブナ基底） イデアル I ⊂ k[x1 , x2 , · · · , xn ] のグレブナ基底 G が次の条件
(1), (2) を満たすとき、G は 極小グレブナ基底 であるという。
(1) 任意の p ∈ G について LC(p) = 1。
(2) 任意の p ∈ G について deg p ̸∈ ⟨ deg(G − {p}) ⟩。
この (2) の代わりに次の (3) を満たすなら G は 簡約グレブナ基底 であるという。
(3) 任意の p ∈ G について p のどの単項式の deg も ⟨ deg(G − {p}) ⟩ に入らない。
補題 6.5
イデアル I のグレブナ基底を G とするとき、ある p ∈ G に対し deg p ∈ ⟨ deg(G − {p}) ⟩ だとすれば
G − {p} も I のグレブナ基底である。
[証明] deg I = ⟨ deg G ⟩ = ⟨ deg(G − {p}) ⟩ より、グレブナ基底の定義から明らか。
定理 6.6（極小グレブナ基底の存在） 任意のイデアル I ∈ k[x1 , x2 , · · · , xn ] について I の極小グレブナ基底が存
在する。
[証明] p ∈ G に対して deg p が deg(G − {p}) のどれかより ≥ なら、G := G − {p} として繰り返せばよい。
例 41
例 40 の極小グレブナ基底を求めよ。すなわち、R = k[x, y] で x > y の grlex で考えて f1 = x3 − 2xy, f2 =
x2 y − 2y 2 + x とするとき、I = ⟨ f1 , f2 ⟩ のグレブナ基底を求めると f3 = −x2 , f4 = −2xy, f5 = −2y 2 + x とし
て、G = (f1 , f2 , f3 , f4 , f5 ) であった。これから極小グレブナ基底を求めよ。
[解] ここで
deg G = {(3, 0), (2, 1), (2, 0), (1, 1), (0, 2)}
なので、deg f3 ≤ deg f1 , deg f4 ≤ deg f2 だから、G = ⟨ f3 , f4 , f5 ⟩ はグレブナ基底として十分であり、係数を直
せば
1
G = (x2 , xy, y 2 − x)
2
6 ブッフベルガーのアルゴリズム
39
が極小グレブナ基底である。
注 33 x2 = 2y · xy − 2x · (y 2 − 12 x) なので、この極小グレブナ基底は基底として冗長性がある。
定理 6.7（簡約グレブナ基底の存在） 簡約グレブナ基底は次のアルゴリズムで得ることができる。
Input: G = (f_1, f_2, ..., f_s): I の極小グレブナ基底
Output: G~ = (g_1, g_2, ..., g_s) : I の簡約グレブナ基底
i := 1
G~ := G
WHILE i <= s DO
g_i := f_i mod(G~ - {f_i})
G~ := G~ - {f_i} + {g_i}
i := i + 1
[証明] G は極小グレブナ基底なので deg f1 ̸∈ ⟨ deg(G − {f1 }) ⟩。よって、割り算アルゴリズムを考えれば g1 =
f1
G−{f1 }
に対して deg g1 = deg f1 。ゆえに、G̃ = G − {f1 } ∪ {g1 } とおくと、deg G̃ = deg G · · · (∗) となる。また、
g1 のどの単項式の deg も deg(G − {f1 }) = deg(G̃ − {g1 }) のどれとも ≥ となることはない。g1 ∈ I と (∗) より G̃
はグレブナ基底であり、極小グレブナ基底でもある。G から G̃ を作ったように、G̃ から G̃(2) を作り、以下同様に
G̃(3) , . . . , G̃(s) を作ると、deg G = deg G̃ = · · · = deg G̃(s) となる。また、gi = fi
は ⟨ deg(G̃
(i−1)
− {fi }) ⟩ = ⟨ deg(G̃
(s)
− {gi }) ⟩ に属さないので、G̃
(s)
G̃(i−1) −{fi }
の任意の単項式の deg
= ⟨ g1 , g2 , · · · , gs ⟩ は簡約グレブナ基底で
ある。
例 42 例 41 の G = (x2 , xy, y 2 − 21 x) は I = ⟨ G ⟩ の簡約グレブナ基底でもある。しかし例えば G′ = (x2 +
xy, xy, y 2 − 12 x) を取ると、これは I の極小グレブナ基底だが簡約ではない。
定理 6.8（簡約グレブナ基底の一意性） 簡約グレブナ基底は、単項式順序を固定すれば、各イデアルに対して一意に
決まる。
[証明] G, G̃ を簡約グレブナ基底とする。
• G, G̃ は極小グレブナ基底である。
• G, G̃ は極小グレブナ基底であることから deg G = deg G̃ が言える。[証明] g ∈ G とすれば、⟨ deg G ⟩ =
⟨ deg G̃ ⟩ より、ある g̃ ∈ G̃ が存在して deg g̃ ≤ deg g 。同様に、ある g ′ ∈ G が存在して deg(g ′ ) ≤ deg(g̃) ≤
deg g 。もし g ̸= g ′ なら g ′ ∈ G − {g} なので deg g ∈ ⟨ deg g ′ ⟩ ⊂ ⟨ deg(G − {g}) ⟩ となって G の極小性と
矛盾する。よって g = g ′ 。従って deg g = deg g̃ ∈ deg G̃。以上より deg G ⊂ deg G̃。同様に逆向きの包含関
係も言え、両辺は一致する。
• g ∈ G, g̃ ∈ G̃ に対して deg g = deg(g̃) ⇒ g = g̃ 。[証明] 式 f に現れる単項式の集合を T(f ) と
書くことにする。g − g̃ ∈ I より g − g̃
G
= 0 · · · (a) である。一方、deg g = deg(g̃) より T(g − g̃) ⊂
T(RT(g)) ∪ T(RT(g̃)) · · · (b)。ここで T(RT(g)) の各元の deg は、≥ deg g とならず、更にまた簡約性より
deg(G − {g}) のどれとも ≥ とならないので、deg G のどれとも ≥ とならない。同様に T(RT(g̃)) のどの元
の deg も deg G̃ = deg G のどれとも ≥ とならない。よって (b) より T(g − g̃) の全ての元の deg は deg G の
どれとでも ≥ とならない。よって割り算アルゴリズムより、g − g̃
g − g̃ = 0。
• 以上より G = G̃ が言える。
G
= g − g̃ · · · (c) である。(a) と (c) より
40
第2章
Groebner 基底
系 6.9（イデアルの同一性判定アルゴリズム） ２つのイデアルが一致することはそれぞれの簡約グレブナ基底が一致
することと同値である。
41
第3章
Groebner 基底の応用
§1
計算の実例
1.1 連立１次方程式
次の連立 1 次方程式を考える

3 −6 −2
 2 −4 0
1 −2 −1
 
 x
0
y

4 
 z  = 0.
−1
w
(3.1)
これはイデアル
I = ⟨ 3x − 6y − 2z, 2x − 4y + 4w, x − 2y − z − w ⟩
を考えることと同じ。これのグレブナ基底を定理 6.3 の方法で求める。
グレブナ基底は (lex で)
G = (3x − 6y − 2z, 2x − 4y + 4w, x − 2y − z − w, z + 3w)
である。計算の詳細は以下の通り：
Calculation of Groebner Basis of (lex):
f1 = 3x - 6y - 2z
f2 = 2x - 4y + 4w
f3 = x - 2y - z - w
----------------------------------------------------------------G = (f1, f2, f3)
= (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w)
B = {(1, 2), (1, 3), (2, 3)}
Round 1
S(f1, f2) = (1/3) * f1 - (1/2) * f2 = -2/3z - 2w.
(-2/3z - 2w) mod G = -2/3z - 2w.
New Generator: f4 = -2/3z - 2w
----------------------------------------------------------------G = (f1, f2, f3, f4)
= (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w, -2/3z - 2w)
B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}
Round 2
S(f1, f3) = (1/3) * f1 - (1) * f3 =
(1/3z + w) mod G = 0.
Round 3
S(f2, f3) = (1/2) * f2 - (1) * f3 =
(z + 3w) mod G = 0.
Round 4
S(f1, f4) = (1/3z) * f1 - (-3/2x) *
(-3xw - 2yz - 2/3z^2) mod G = 0.
Round 5
S(f2, f4) = (1/2z) * f2 - (-3/2x) *
(-3xw - 2yz + 2zw) mod G = 0.
Round 6
S(f3, f4) = (z) * f3 - (-3/2x) * f4
1/3z + w.
z + 3w.
f4 = -3xw - 2yz - 2/3z^2.
f4 = -3xw - 2yz + 2zw.
= -3xw - 2yz - z^2 - zw.
(3.2)
第3章
42
Groebner 基底の応用
(-3xw - 2yz - z^2 - zw) mod G = 0.
RESULT
G = (
f1 =
f2 =
f3 =
f4 =
)
=================================================================
3x - 6y - 2z,
2x - 4y + 4w,
x - 2y - z - w,
-2/3z - 2w
LT(G) = (3x, 2x, x, z) なので、極小グレブナ基底は
G = (x − 2y − z − w, z + 3w)
x − 2y − z − w
(z+3w)
= x − 2y + 2w, z + 3w
(x−2y−z−w)
= z + 3w なので、簡約グレブナ基底は
G = (x − 2y + 2w, z + 3w)
である。
そして、
(1) 極小グレブナ基底を求める ⇐⇒ 掃きだし法で次のような階段行列に変形する:
 

 x
1 −2 −1 −1  
y
0 0
1
3 
 z  = 0.
0 0
0
0
w
(2) 簡約グレブナ基底を求める ⇐⇒ 更に全ての式は他の先頭項による消去がなされている
⇐⇒ 掃きだし法で次のような階段行列に変形する:
 
 x
1 −2 0 2  
 0 0 1 3   y  = 0.
z
0 0 0 0
w

1.2 イデアル所属問題
有限集合 G が I のグレブナ基底なら、f ∈ I であるための必要十分条件は f
G
= 0 である。
これを利用してイデアル I = ⟨ x − 2xy, x y − 2y + x ⟩ に対して、x + 2y と x2 + 2y 3 + y の所属問題を解く。
3
2
2
2
3
前章の例 42 より、I の x > y > z による grlex での（簡約）グレブナ基底 G = ⟨ x2 , xy, y 2 − 12 x ⟩ で割り算して
考えればよい。x2 + 2y 3
G
G
= 0 より x2 + 2y 3 ∈ I 。また、x2 + 2y 3 + y = y ̸= 0 より x2 + 2y 3 + y ̸∈ I 。
1.3 イデアル所属問題その 2
⟨ x3 , x2 y + x ⟩ = ⟨ x ⟩ を示せ。(例 38, 前の〔練習問題〕を参考に。)
1.4 イデアル同一性問題
事象 A, B についての次の条件は 3 つとも A と B が独立であることを意味している。これらが同値であることを
検証する。
(α) P (A ∩ B) : P (A ∩ B) = P (A ∩ B) : P (A ∩ B)
(β) P (A ∩ B) = P (A)P (B)
(γ) P (A ∩ B) = P (A)P (B)
【解】各事象の確率に次のように名前を付ける
1 計算の実例
43
A
A
B
a
b
B
c
d
(α) ⇐⇒ a : b = c : d ⇐⇒ ad − bc = 0
(β) ⇐⇒ a = (a + c)(a + b) ⇐⇒ a2 + ab + ac − a + bc = 0
(γ) ⇐⇒ c = (a + c)(c + d) ⇐⇒ ac + ad + c2 + cd − c = 0
(by lex order)
-----------------f1 = a + b + c + d - 1
f2 = ad - bc
S(f1, f2) = bc + bd + cd + d^2 - d
S(f1, f2) / <f1, f2> =
a1: 0
a2: 0
... bc + bd + cd + d^2 - d
f3 = bc + bd + cd + d^2 - d
S(f1, f3) = -abd - acd - ad^2 + ad + b^2c + bc^2 + bcd - bc
S(f1, f3) / <f1, f2, f3> =
a1: -bd - cd - d^2 + d
a2: 0
a3: b + c + d - 1
... 0
S(f2, f3) = -abd^2 - acd^2 - ad^3 + ad^2 - b^2c^2
S(f2, f3) / <f1, f2, f3> =
a1: -bd^2 - cd^2 - d^3 + d^2
a2: 0
a3: -bc + bd + cd + d^2 - d
... 0
Reduced Groebner Basis = [a + b + c + d - 1, bc + bd + cd + d^2 - d]
-----------------f1 = a + b + c + d - 1
f2 = a^2 + ab + ac - a + bc
S(f1, f2) = ad - bc
S(f1, f2) / <f1, f2> =
a1: d
a2: 0
... -bc - bd - cd - d^2 + d
f3 = -bc - bd - cd - d^2 + d
S(f1, f3) = -abd - acd - ad^2 + ad + b^2c + bc^2 + bcd - bc
S(f1, f3) / <f1, f2, f3> =
a1: -bd - cd - d^2 + d
a2: 0
a3: -b - c - d + 1
... 0
S(f2, f3) = -a^2bd - a^2cd - a^2d^2 + a^2d + ab^2c + abc^2 - abc + b^2c^2
S(f2, f3) / <f1, f2, f3> =
a1: -abd - acd - ad^2 + ad + b^2c + b^2d + bc^2 + 2bcd - bc + 2bd^2 - 2bd + c^2d + 2cd^2 - 2cd + d^3 - 2d^2 + d
a2: 0
a3: b^2 + bc + 2bd - 2b + c^2 + 2cd - 2c + d^2 - 2d + 1
... 0
Reduced Groebner Basis = [a + b + c + d - 1, bc + bd + cd + d^2 - d]
-----------------f1 = a + b + c + d - 1
f2 = ac + ad + c^2 + cd - c
S(f1, f2) = -ad + bc
S(f1, f2) / <f1, f2> =
a1: -d
a2: 0
... bc + bd + cd + d^2 - d
f3 = bc + bd + cd + d^2 - d
S(f1, f3) = -abd - acd - ad^2 + ad + b^2c + bc^2 + bcd - bc
S(f1, f3) / <f1, f2, f3> =
a1: -bd - cd - d^2 + d
a2: 0
a3: b + c + d - 1
... 0
S(f2, f3) = -acd - ad^2 + ad + bc^2 + bcd - bc
S(f2, f3) / <f1, f2, f3> =
a1: -cd - d^2 + d
a2: 0
a3: c + d - 1
... 0
Reduced Groebner Basis = [a + b + c + d - 1, bc + bd + cd + d^2 - d]
注 34 a が現れる度に b + c + d − 1 に置き換えればいいので、これらの同値性の証明を実は優しい。が · · ·
第3章
44
Groebner 基底の応用
1.5 多次元多元連立方程式の解法
連立方程式
 2
 x
x2

x
+ y2
+
+
z2
z2
= 1
= y
= z
を機械的に解く。I = ⟨ f1 , f2 , f3 ⟩, f1 = x2 + y 2 + z 2 − 1, f2 = x2 + z 2 − y, f3 = x − z とおき、I のグレブナ基
底を求める。
F = (x2 + y 2 + z 2 − 1, x2 + z 2 − y, x − z)
から、x > y > z による lex グレブナ基底を求めると、
G = (x2 + y 2 + z 2 − 1, x2 + z 2 − y, x − y, y 2 + y − 1, −y + 2z 2 , 4z 4 + 2z 2 − 1).
計算の詳細は以下の通り：
Calculation of Groebner Basis of (lex):
f1 = x^2 + y^2 + z^2 - 1
f2 = x^2 - y + z^2
f3 = x - z
----------------------------------------------------------------G = (f1, f2, f3)
= (x^2 + y^2 + z^2 - 1, x^2 - y + z^2, x - z)
B = {(1, 2), (1, 3), (2, 3)}
Round 1
S(f1, f2) = (1) * f1 - (1) * f2 = y^2 + y - 1.
(y^2 + y - 1) mod G = y^2 + y - 1.
New Generator: f4 = y^2 + y - 1
----------------------------------------------------------------G = (f1, f2, f3, f4)
= (x^2 + y^2 + z^2 - 1, x^2 - y + z^2, x - z, y^2 + y - 1)
B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}
Round 2
S(f1, f3) = (1) * f1 - (x) * f3 = xz + y^2 + z^2 - 1.
(xz + y^2 + z^2 - 1) mod G = -y + 2z^2.
New Generator: f5 = -y + 2z^2
----------------------------------------------------------------G = (f1, f2, f3, f4, f5)
= (x^2 + y^2 + z^2 - 1, x^2 - y + z^2, x - z, y^2 + y - 1, -y + 2z^2)
B = {(2, 3), (1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)}
Round 3
S(f2, f3) = (1) * f2 - (x) * f3 = xz - y + z^2.
(xz - y + z^2) mod G = 0.
Round 4
S(f1, f4) = (y^2) * f1 - (x^2) * f4 = -x^2y + x^2 + y^4 + y^2z^2 - y^2.
(-x^2y + x^2 + y^4 + y^2z^2 - y^2) mod G = 0.
Round 5
S(f2, f4) = (y^2) * f2 - (x^2) * f4 = -x^2y + x^2 - y^3 + y^2z^2.
(-x^2y + x^2 - y^3 + y^2z^2) mod G = 0.
Round 6
S(f3, f4) = (y^2) * f3 - (x) * f4 = -xy + x - y^2z.
(-xy + x - y^2z) mod G = 0.
Round 7
S(f1, f5) = (y) * f1 - (-x^2) * f5 = 2x^2z^2 + y^3 + yz^2 - y.
(2x^2z^2 + y^3 + yz^2 - y) mod G = 4z^4 + 2z^2 - 1.
New Generator: f6 = 4z^4 + 2z^2 - 1
----------------------------------------------------------------G = (f1, f2, f3, f4, f5, f6)
= (x^2 + y^2 + z^2 - 1, x^2 - y + z^2, x - z, y^2 + y - 1, -y + 2z^2, 4z^4 + 2z^2 - 1)
B = {(2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6)}
Round 8
S(f2, f5) = (y) * f2 - (-x^2) * f5 = 2x^2z^2 - y^2 + yz^2.
(2x^2z^2 - y^2 + yz^2) mod G = 0.
Round 9
S(f3, f5) = (y) * f3 - (-x) * f5 = 2xz^2 - yz.
(2xz^2 - yz) mod G = 0.
Round 10
S(f4, f5) = (1) * f4 - (-y) * f5 = 2yz^2 + y - 1.
(2yz^2 + y - 1) mod G = 0.
Round 11
1 計算の実例
S(f1, f6) =
(-1/2x^2z^2
Round 12
S(f2, f6) =
(-1/2x^2z^2
Round 13
S(f3, f6) =
(-1/2xz^2 +
Round 14
S(f4, f6) =
(-1/2y^2z^2
Round 15
S(f5, f6) =
(-1/2yz^2 +
RESULT
G = (
f1 =
f2 =
f3 =
f4 =
f5 =
f6 =
)
45
(z^4) * f1 - (1/4x^2) * f6 = -1/2x^2z^2 + 1/4x^2 + y^2z^4 + z^6 - z^4.
+ 1/4x^2 + y^2z^4 + z^6 - z^4) mod G = 0.
(z^4) * f2 - (1/4x^2) * f6 = -1/2x^2z^2 + 1/4x^2 - yz^4 + z^6.
+ 1/4x^2 - yz^4 + z^6) mod G = 0.
(z^4) * f3 - (1/4x) * f6 = -1/2xz^2 + 1/4x - z^5.
1/4x - z^5) mod G = 0.
(z^4) * f4 - (1/4y^2) * f6 = -1/2y^2z^2 + 1/4y^2 + yz^4 - z^4.
+ 1/4y^2 + yz^4 - z^4) mod G = 0.
(-z^4) * f5 - (1/4y) * f6 = -1/2yz^2 + 1/4y - 2z^6.
1/4y - 2z^6) mod G = 0.
=================================================================
x^2 + y^2 + z^2 - 1,
x^2 - y + z^2,
x - z,
y^2 + y - 1,
-y + 2z^2,
4z^4 + 2z^2 - 1
更に極小グレブナ基底は
1
1
G = (f3 , f5 , f6 ) = (x − z, y − 2z 2 , z 4 + z 2 − )
2
4
である。LT(G) = (x, y, z 4 ) なのでこれは簡約済み。z 4 + 12 z 2 −
√
z=±
−1 ±
4
√
5
1
4
= 0 より、z の値は求めることができて、
.
これから x, y も求めることができる。
1.6 消去法
一応…
命題 1.1 イデアル I の有限部分集合 G が、グレブナ基底であるための必要十分条件は、任意の f ∈ I に対し、ある
g ∈ G が存在して、LT(g)|LT(f ) となることである。
定理 1.2（消去定理 (Elimination Theorem)） I を k[x1 , x2 , · · · , xn ] のイデアル。G を x1 > x2 > · · · > xn による
lex 順序に関する I の Groebner 基底とするとき、G ∩k[xl , · · · , xn ] は k[xl , · · · , xn ] のイデアル I ∩k[xl , · · · , xn ]
の Groebner 基底である。
[証明] 任意の f ∈ I ∩ k[xl , · · · , xn ] に対して、ある g ∈ G が存在して、LT(g)|LT(f )。このとき LT(f ) ∈
k[xl , · · · , xn ] より、LT(g) ∈ k[xl , · · · , xn ] であり、従って順序のつけ方から、g ∈ k[xl , · · · , xn ]。 すなわち、
g ∈ G∩k[xl , · · · , xn ] かつ LT(g)|LT(f ) となる g が存在している。よって、G∩k[xl , · · · , xn ] も I ∩k[xl , · · · , xn ]
の Groebner 基底である。
1.7 陰関数表示
曲線のパラメータ表示:

 x
y

z
= t4
= t3
= t2
から陰関数表示を求める。
I = ⟨ f1 , f2 , f3 ⟩, f1 = t4 − x, f2 = t3 − y, f3 = t2 − z とおき、I の t > x > y > z による lex でのグレブナ基
底を求める。
第3章
46
Groebner 基底の応用
G = (t4 − x, t3 − y, t2 − z)
からグレブナ基底は、
G = (t4 − x, t3 − y, t2 − z, ty − x, −x + z 2 , tz − y, −y 2 + z 3 )
である。計算の詳細は:
Calculation of Groebner Basis of (lex):
f1 = t^4 - x
f2 = t^3 - y
f3 = t^2 - z
----------------------------------------------------------------G = (f1, f2, f3)
= (t^4 - x, t^3 - y, t^2 - z)
B = {(1, 2), (1, 3), (2, 3)}
Round 1
S(f1, f2) = (1) * f1 - (t) * f2 = ty - x.
(ty - x) mod G = ty - x.
New Generator: f4 = ty - x
----------------------------------------------------------------G = (f1, f2, f3, f4)
= (t^4 - x, t^3 - y, t^2 - z, ty - x)
B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}
Round 2
S(f1, f3) = (1) * f1 - (t^2) * f3 = t^2z - x.
(t^2z - x) mod G = -x + z^2.
New Generator: f5 = -x + z^2
----------------------------------------------------------------G = (f1, f2, f3, f4, f5)
= (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2)
B = {(2, 3), (1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5)}
Round 3
S(f2, f3) = (1) * f2 - (t) * f3 = tz - y.
(tz - y) mod G = tz - y.
New Generator: f6 = tz - y
----------------------------------------------------------------G = (f1, f2, f3, f4, f5, f6)
= (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2, tz - y)
B = {(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6)}
Round 4
S(f1, f4) = (y) * f1 - (t^3) * f4 = t^3x - xy.
(t^3x - xy) mod G = 0.
Round 5
S(f2, f4) = (y) * f2 - (t^2) * f4 = t^2x - y^2.
(t^2x - y^2) mod G = -y^2 + z^3.
New Generator: f7 = -y^2 + z^3
----------------------------------------------------------------G = (f1, f2, f3, f4, f5, f6, f7)
= (t^4 - x, t^3 - y, t^2 - z, ty - x, -x + z^2, tz - y, -y^2 + z^3)
B = {(3, 4), (1, 5), (2, 5), (3, 5), (4, 5), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6), (1, 7), (2, 7), (3, 7), (4, 7),
(5, 7), (6, 7)}
Round 6
S(f3, f4) = (y) * f3 - (t) * f4 = tx - yz.
(tx - yz) mod G = 0.
Round 7
S(f1, f5) = (x) * f1 - (-t^4) * f5 = t^4z^2 - x^2.
(t^4z^2 - x^2) mod G = 0.
Round 8
S(f2, f5) = (x) * f2 - (-t^3) * f5 = t^3z^2 - xy.
(t^3z^2 - xy) mod G = 0.
Round 9
S(f3, f5) = (x) * f3 - (-t^2) * f5 = t^2z^2 - xz.
(t^2z^2 - xz) mod G = 0.
Round 10
S(f4, f5) = (x) * f4 - (-ty) * f5 = tyz^2 - x^2.
(tyz^2 - x^2) mod G = 0.
Round 11
S(f1, f6) = (z) * f1 - (t^3) * f6 = t^3y - xz.
(t^3y - xz) mod G = 0.
Round 12
S(f2, f6) = (z) * f2 - (t^2) * f6 = t^2y - yz.
(t^2y - yz) mod G = 0.
Round 13
1 計算の実例
47
S(f3, f6) = (z) * f3 - (t) * f6 = ty - z^2.
(ty - z^2) mod G = 0.
Round 14
S(f4, f6) = (z) * f4 - (y) * f6 = -xz + y^2.
(-xz + y^2) mod G = 0.
Round 15
S(f5, f6) = (-tz) * f5 - (x) * f6 = -tz^3 + xy.
(-tz^3 + xy) mod G = 0.
Round 16
S(f1, f7) = (y^2) * f1 - (-t^4) * f7 = t^4z^3 - xy^2.
(t^4z^3 - xy^2) mod G = 0.
Round 17
S(f2, f7) = (y^2) * f2 - (-t^3) * f7 = t^3z^3 - y^3.
(t^3z^3 - y^3) mod G = 0.
Round 18
S(f3, f7) = (y^2) * f3 - (-t^2) * f7 = t^2z^3 - y^2z.
(t^2z^3 - y^2z) mod G = 0.
Round 19
S(f4, f7) = (y) * f4 - (-t) * f7 = tz^3 - xy.
(tz^3 - xy) mod G = 0.
Round 20
S(f5, f7) = (-y^2) * f5 - (-x) * f7 = xz^3 - y^2z^2.
(xz^3 - y^2z^2) mod G = 0.
Round 21
S(f6, f7) = (y^2) * f6 - (-tz) * f7 = tz^4 - y^3.
(tz^4 - y^3) mod G = 0.
RESULT
G = (
f1 =
f2 =
f3 =
f4 =
f5 =
f6 =
f7 =
)
=================================================================
t^4 - x,
t^3 - y,
t^2 - z,
ty - x,
-x + z^2,
tz - y,
-y^2 + z^3
LT(G) = (t4 , t3 , t2 , ty, −x, tz, −y 2 ) であるから、更に極小グレブナ基底は
G = (t2 − z, ty − x, x − z 2 , tz − y, y 2 − z 3 )
(t2 −z, x−z 2 , tz−y, y 2 −z 3 )
である。また、LT(G) = (t2 , ty, x, tz, y 2 ) であるから、必要な簡約は ty − x
= ty − z 2 の
みなので、簡約グレブナ基底は
G = (t2 − z, ty − z 2 , x − z 2 , tz − y, y 2 − z 3 )
である。
従って図形は曲線
x − z2 = y2 − z3 = 0
に含まれる。
1.8 ラグランジュ乗数法
（問題） x2 + y 2 + z 2 = 1 という束縛条件の下で f (x, y, z) = x3 + 2xyz − z 2 の極値を求めよ。
（解）g(x, y, z) = x2 + y 2 + z 2 − 1 と置くと λ をある未知数として、

fx



fy
fz



g
すなわち
=
=
=
=
λgx
λgy
λgz
0

3x2 + 2yz − 2xλ =



2xz − 2yλ =
2xy
−
2z − 2zλ =


 2
x + y2 + z2 − 1 =
0
0
0
0
を解けばよい。これらの左辺で生成されるイデアルの Groebner 基底を lex, λ > x > y > z で求めると、基底の一つ
として z 7 −
1763 5
1152 z
+
655 3
1152 z
−
11
288 z
があるので、これを 0 と置くことにより z が求まり、他の変数の値も求まる。
第3章
48
Groebner 基底の応用
1.9 ３色彩色問題
（問題） 次のグラフの各点に色を塗る。線分で結ばれた２点は必ず異なる色で塗るとするとき、３色で塗ることは
可能か？
（解）各点に F3 = Z/3Z の元を割り当てる。xi と xj の色が異なることは xi = xj + 1 あるいは xi = xj + 2 で表
現できるので、これは (xi − xj − 1)(xi − xj − 2) = 0 すなわち、
xi 2 + xi xj + xj 2 − 1 = 0.
と表現できる。これが、(i, j) ∈ L について成り立てばよい。ここで、L = {(1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 8),
(3, 4), (3, 8), (4, 5), (4, 7), (5, 6), (5, 7), (6, 7), (7, 8)} である。さて、F = {xi 2 + xi xj + xj 2 − 1 | (i, j) ∈ L}
と置けば、１つの３色の各塗り分けは、１つの V(⟨ F ⟩) の要素と１対１対応している。x8 の色を 0 に塗って
しまってよいので、F ′ = F ∪ {x8 }, V(⟨ F ′ ⟩) を考えてもよい。変数に x1 > · · · > x8 で、lex 順序を入れて、
⟨ F ′ ⟩ の簡約グレブナ基底を求めると G = {x1 − x7 , x2 + x7 , x3 − x7 , x4 , x5 + x7 , x6 , x7 2 + 2, x8 } となる。
V(⟨ F ′ ⟩) = V(⟨ G ⟩) が空集合でないことを確かめることができる。
1.10 ヒルベルトの零点定理
定義 1.3（根基,
√
） I を環 R のイデアルとするとき、
√
I = {f ∈ R | ∃n ≥ 0 f n ∈ I}
と定義し、I の根基という。
√
I は R のイデアルになる。
√
(2) R を整域とすれば {0} = {0}。
√
(3)
R = R.
√
(4)
I = R ⇐⇒ I = R.
命題 1.4
(1)
[証明] 略。
定義 1.5（代数的閉体） 任意の k 上の代数方程式 an xn + an−1 xn−1 + · · · + a0 = 0, n > 0, ai ∈ k (0 ≤ i ≤
n), an ̸= 0 が k に解を持つとき、k を代数的閉体という。
例 43
(1) 複素数体 C は代数的閉体である。(代数学の基本定理と呼ばれる。)
(2) F3 は代数的閉体でない。(x2 + 1 = 0 に解はない。)
定理 1.6（ヒルベルトの零点定理 (Hilbert’s Nullstellensatz)） k を代数的閉体、I を R = k[x1 , x2 , · · · , xn ] のイデ
アルとするとき、それで定義されるアフィン多様体 V(I) について、以下の事が言える。
1 計算の実例
49
(1) V(I) = ϕ ⇐⇒ I = R.
√
(2) I(V(I)) = I.
[証明] 略。
系 1.7 k を代数的閉体とするとき、イデアル (f1 , f2 , · · · , fs ) ⊂ k[x1 , x2 , · · · , xn ] の簡約グレブナ基底が (1) で
なければ、連立方程式 f1 = f2 = · · · = fs = 0 には k n 上の解がある。
1.11 ３色彩色問題 (再)
1.9 の問題において、最後に V(⟨ G ⟩) が空集合ではないことを言うために、最後に連立方程式を実際に解く必要が
あったが、それを回避する方法がある。代数的閉体
C において、３つの色を x3 − 1 = (x − 1)(x2 + x + 1) = 0 の
√
解、1, ω, ω 2 (ここで、
ω=
十分条件は
−1 + −3
) で塗り分ける。xi 3 − 1 = xj 3 − 1 = 0 を満たす xi , xj が異なるための必要
2
x2i + xi xj + x2j = 0.
なので、F = {xi 3 − 1 | 1 ≤ i ≤ 8} ∪ {x2i + xi xj + x2j | (i, j) ∈ L} ∪ {x8 − 1} で生成されるイデアル ⟨ F ⟩ の簡約グ
レブナ基底を求めると、G = (x1 − x7 , x2 + x7 + 1, x3 − x7 , x4 − 1, x5 + x7 + 1, x6 − 1, x7 2 + x7 + 1, x8 − 1)
となる。G ̸= (1) なので、ヒルベルトの基底定理より V(⟨ G ⟩) は空集合でない。
1.12 垂心の存在
(問題) 任意の三角形に垂心が存在する。
(解) 三角形の各頂点を A(a1 , a2 ), B(b1 , b2 ), C(c1 , c2 ) とする。垂心を H(x, y) とすると、AH, BH, CH が
BC, CA, AB とそれぞれ垂直であるという条件は、

 f1 = (x − a1 )(b1 − c1 ) + (y − a2 )(b2 − c2 )
f2 = (x − b1 )(c1 − a1 ) + (y − b2 )(c2 − a2 )

f3 = (x − c1 )(a1 − b1 ) + (y − c2 )(a2 − b2 )
とおくとき、f1 = f2 = f3 = 0 である。
また、A, B, C が一直線上に無い条件は、
1 a1
s = 1 b1
1 c1
a2 b2 c2 とおくとき s ̸= 0 である。ここでは、s − 1 = 0 とする。
I = ⟨ f1 , f2 , f3 , s − 1 ⟩ のグレブナ基底を lex, x > y > a1 > a2 > b1 > b2 > c1 > c2 で求めると

g1 = x + a1 a2 b1 − a1 a2 c1 − a1 b1 c2 + a1 c1 c2 + a22 b2




−a22 c2 − a2 b21 + a2 b1 c1 − a2 b22 + a2 c22 + b21 c2 − b1 c1 c2 − b1 + b22 c2 − b2 c22

g2 = y − a21 b1 + a21 c1 + a1 b21 − a1 c21 − a22 b1 + a22 c1


+a2 b1 b2 + a2 b1 c2 − a2 b2 c1 − a2 c1 c2 − a2 − b21 c1 − b1 b2 c2 + b1 c21 + b2 c1 c2



g3 = a1 b2 − a1 c2 − a2 b1 + a2 c1 + b1 c2 − b2 c1 − 1
g3 = s − 1 なので、g1 = g2 = g3 = 0 の解 (x, y) は存在する。
第3章
50
§2
Groebner 基底の応用
拡張定理
定理 2.1（拡張定理 (Extension Theorem)） k を代数的閉体、I = ⟨ f1 , f2 , · · · , fs ⟩ ⊂ k[x1 , x2 , · · · , xn ] をイデ
アル、I1 = I ∩ k[x2 , · · · , xn ] とする。各 fi を x1 の降べき順に
i
fi = gi (x2 , · · · , xn )xN
1 + · · · , gi ̸= 0.
と書く時、(a2 , · · · , an ) ∈ V(I1 ), (a2 , · · · , an ) ̸∈ V(g1 , g2 , · · · , gs ) ならば、ある a1 ∈ k が存在して
(a1 , a2 , · · · , an ) ∈ V(I) となる。
[証明] (略) 系 2.2 k を代数的閉体、I = ⟨ f1 , f2 , · · · , fs ⟩ ⊂ k[x1 , x2 , · · · , xn ] をイデアル、I1 = I ∩ k[x2 , · · · , xn ] とす
る。ある i に対して fi を x1 の降べき順に
fi = c · x N
1 + · · · , c ∈ k, c ̸= 0, N > 0.
と書く時、(a2 , · · · , an ) ∈ V(I1 ), (a2 , · · · , an ) ̸∈ V(g1 , g2 , · · · , gs ) ならば、ある a1 ∈ k が存在して
(a1 , a2 , · · · , an ) ∈ V(I) となる。
[証明] 前定理より明らか。
51
付録
§1
参考書
グレブナ基底と代数多様体入門 イデアル・多様体・アルゴリズム (上・下)
(著者) コックス/リトル/オシー
(訳者) 落合啓之・示野信一・西山享・室政和・山本敦子
(出版社) 2000 年, シュプリンガー・フェアラーク東京
(価格) 上:3800 円、下:3900 円
共立叢書 現代数学の潮流グレブナー基底とその応用
(著者) 丸山正樹
(出版社) 2002 年, 共立出版
(価格) 3600 円
グレブナー基底（１，２）
(著者) コックス/リトル/オシー
(訳者) 大杉英史・北村知徳・日比孝之
(出版社) 2000 年, シュプリンガー・フェアラーク東京
(価格) 上:4200 円、下:4200 円
新数学講座 12
計算数学
(著者) 和田秀男
(出版社) 2000 年, 朝倉書店
(価格) 3200 円
共立講座 21 世紀の数学 8
環と体の理論
(著者) 酒井文雄
(出版社) 1997 年, 共立出版
(価格) 3000 円
グレブナー基底の計算 基礎編 計算代数入門
(著者) 野呂正行・横山和弘
(出版社) 2003 年, 東京大学出版会
(価格) 4200 円
グレブナー基底の計算 実践編 Risa/Asir で解く
(著者) 齋藤友克・竹島卓・平野輝比古
付録
52
(出版社) 2003 年, 東京大学出版会
(価格) 4200 円
岩波講座 応用数学 [方法 9]
計算代数と計算幾何
(著者) 佐々木、今井、浅野、杉原
(出版社) 1993 年, 岩波書店
(価格) 3600 円
代数学入門第三課
(著者) 一松信
(出版社) 1994 年, 近代科学社
§2
参考 URL
Web ページ: http://blade.nagaokaut.ac.jp/~ hara/class/
メール:
[email protected]
53
索引
+,
≥,
=,
5,
26
20
20
21
F
f , 29
⟨ · · · ⟩δ , 33
イデアル, 23
bar, 7
defdickson, 21
deg, 7, 28
deg, 7
Dickson 性, 21
Dickson 的, 21
div, 7
Fp , 6
GDD, 8, 11
grevlex, 27
grlex, 27
I, 15
LC, 7, 28
lex, 26
LM, 7, 28
LT, 7, 28
mod , 7
mod, 29
multideg, 28
N, 6, 20
Noethoer 性, 24
Noether 的, 24
PID, 8
/, 7
quotient, 7
remainder, 7
√
, 48
RT, 7, 28
S(−, −), 33
S-多項式, 33
V, 13, 15
アフィン多様体, 13
余り, 7
因数定理, 8
埋め込み写像, 3
可換環, 1
可逆元, 2
核, 5
拡張, 20
拡張されたユークリッドの互除法, 9
Galois 接続, 16
Galois 対応, 16
環, 1
簡約グレブナ基底, 38
基底, 14, 21
既約元, 12
極小グレブナ基底, 38
極小元, 21
極大イデアル, 6
グレブナ基底, 31
項順序, 26
公理, 1
互除法, 8
根基, 48
最小元, 21
最大公約数, 8
辞書式順序, 26
次数付き逆辞書式順序, 27
次数付き辞書式順序, 27
自然順序, 21
自明なイデアル, 4
順序, 20
順序集合, 20
準同型写像, 3
商, 7
剰余, 7
剰余環, 5
剰余集合, 4
剰余類, 4
整域, 5
正規形, 32
生成, 21
生成されたイデアル, 4, 23
整列順序, 22
積順序, 21
全射, 3
全順序, 20
全単射, 3
素イデアル, 6
像, 5
素元, 12
素体, 6
体, 1
代数的閉体, 48
代表系, 4
代表元, 4
多項式環, 6
単元, 2
単項イデアル, 4
単項イデアル整域, 8
単項式, 27
単項式順序, 26, 27
単射, 3
直積, 13
54
ディクソンの補題, 22
同型, 3
同型写像, 3
張る, 21
標準基底, 31
標準射影, 4
標準的順序, 21
ヒルベルトの基底定理, 32
ヒルベルトの零点定理, 48
ブッフベルガーのアルゴリズム, 35, 36
部分環, 3
包含写像, 3
有限生成, 14, 21
両立, 26, 27
割り切る, 7
割り算, 7, 28
索引