ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC SƯ PHẠM
NGUYỄN DUY ÁI NHÂN
CƠ SỞ GR
¨
OBNER CỦA ĐẠI SỐ TOÀN
PHƯƠNG ĐỐI CHIỀU THẤP
KHÓA LUẬN TỐT NGHIỆP ĐHSP
Chuyên ngành: Đại số
Giảng viên hướng dẫn
TS. PHAN VĂN THIỆN
Huế, Khóa học 2007 - 2011
i
Mục lục
Trang phụ bìa i
Mục lục 1
Lời nói đầu 3
Chương 1 Một số kiến thức chuẩn bị 4
1.1 Vành phân bậc, môđun phân bậc . . . . . . . . . . . . . . . 4
1.2 Đại số phân bậc chuẩn . . . . . . . . . . . . . . . . . . . . . 4
1.3 Iđêan phân bậc . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Chuỗi Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Hàm Hilbert . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Chuỗi Hilbert . . . . . . . . . . . . . . . . . . . . . . 7
Chương 2 Cơ sở Gr¨obner của Iđêan 9
2.1 Thứ tự đơn thức trên K [x
1
, . . . , x
n
] . . . . . . . . . . . . . . 9
2.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Một số thứ tự đơn thức . . . . . . . . . . . . . . . . 9
2.1.3 Bậc của đa thức . . . . . . . . . . . . . . . . . . . . . 10
2.2 Thuật toán chia trong K[x
1
, . . . , x
n
] . . . . . . . . . . . . . . 11
2.3 Iđêan đơn thức và bổ đề Dickson . . . . . . . . . . . . . . . 12
2.4 Định lí cơ bản Hilbert và cơ sở Gr¨obner . . . . . . . . . . . . 16
2.5 Tính chất của cơ sở Gr¨obner . . . . . . . . . . . . . . . . . . 19
2.6 Thuật toán Buchberger . . . . . . . . . . . . . . . . . . . . . 23
Chương 3 Cơ sở Gr¨obner của đại số toàn phương đối chiều
1
thấp 27
3.1 Một số kết quả mở đầu . . . . . . . . . . . . . . . . . . . . . 27
3.2 Định lí chính . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Chứng minh định lí chính . . . . . . . . . . . . . . . . . . . 32
Kết luận 41
Tài liệu tham khảo 42
2
LỜI NÓI ĐẦU
Cơ sở Gr¨obner là cơ sở có những ứng dụng quan trọng trong đại số giao
hoán và đại số máy tính.
Đối với đại số toàn phương đối chiều thấp dạng
R = K[x
1
, . . . , x
n
]/I
thì iđêan xác định I của R luôn tồn tại cơ sở Gr¨obner gồm các phần tử
thuần nhất bậc hai trừ trường hợp I = (x
2
, xy, y
2
− xz, yz). Lúc này, ta nói
R được xác định bởi một cơ sở Gr¨obner các phần tử thuần nhất bậc hai hay
R là G-toàn phương. Trường hợp này là nội dung nghiên cứu chính của khóa
luận.
Nội dung của khóa luận được chia thành 3 chương:
1. Chương 1: Giới thiệu một số kiến thức liên quan đến đại số phân bậc,
iđêan phân bậc, chuỗi Hilbert
2. Chương 2: Xây dựng định nghĩa cơ sở Gr¨obner của iđêan và nêu một
số tính chất.
3. Chương 3: Chứng minh trường hợp đặc biệt được nêu ra ở trên.
Phương pháp nghiêu cứu chung của khóa luận là nghiên cứu các tài liệu liên
quan, tổng hợp và trình bày lại theo cách hiểu của bản thân.
Do trình độ chuyên môn và kinh nghiệm còn hạn chế nên khóa luận này
không tránh khỏi những sai sót, rất mong nhận được sự cảm thông và những
ý kiến nhận xét từ phía người đọc.
Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến các thầy cô và bạn bè
đã tạo điều kiện cho tôi hoàn thành khóa luận, đặc biệt là thầy giáo Phan
Văn Thiện đã giúp đỡ tôi chọn đề tài, hướng dẫn nghiên cứu và cho những
nhận xét đánh giá quý báu.
Huế, tháng 05 năm 2011
Nguyễn Duy Ái Nhân
3
Chương 1
MỘT SỐ KIẾN THỨC CHUẨN BỊ
1.1 Vành phân bậc, môđun phân bậc
1. Vành phân bậc.
Một vành A được gọi là vành phân bậc nếu có sự phân tích thành tổng
trực tiếp của các nhóm Aben
A = ⊕
n≥0
A
n
thỏa mãn A
n
A
m
⊆ A
n+m
với mọi n, m.
2. Môđun phân bậc.
Cho A là vành phân bậc, A-môđun phân bậc M là A-môđun M có sự
phân tích thành tổng trực tiếp
M = ⊕
n≥0
M
n
thỏa mãn A
n
M
m
⊆ M
n+m
với mọi n, m.
3. Mỗi phần tử của A
n
hoặc M
n
được gọi là thuần nhất bậc n.
4. Một môđun con N của M được gọi là môđun con phân bậc nếu N =
⊕
n≥0
(N ∩ M
n
).
1.2 Đại số phân bậc chuẩn
Cho K là một trường.
1. Nếu một K-đại số giao hoán A có sự phân tích thành tổng trực tiếp
thành
A = A
0
⊕ A
1
⊕ A
2
⊕ . . .
4
với A
0
= K và A
i
A
j
⊆ A
i+j
(∀i, j ≥ 0) thì A được gọi là K-đại số phân
bậc và ta viết A =
n≥0
A
n
.
Ví dụ:
Xét K[x] là vành đa thức một biến x trên trường K.
Một đa thức thuộc K[x] có thể viết dưới dạng
a
0
+ a
1
x + a
2
x
2
+ . . . + a
n
x
n
, n ≥ 0, a
i
∈ K ∀i = 1, . . . , n
Như vậy K[x] = A
0
+ A
1
+ A
2
+ A
3
+ . . . với A
0
= {a
0
|a
0
∈ K},
A
1
= {a
1
x|a
1
∈ K},. . .
Mặt khác, A
i
∩A
j
= {0} với i = j nên suy ra K[x] = A
0
⊕A
1
⊕A
2
⊕. .
Ta có A
0
= K và với mọi a
i
x
i
∈ A
i
, a
j
x
j
∈ A
j
thì (a
i
x
i
)(a
j
x
j
) =
(a
i
a
j
)(x
i+j
) ∈ A
i+j
⇒ A
i
A
j
⊆ A
i+j
Như vậy, K[x] là một K-đại số phân bậc.
2. Mỗi a ∈ A
n
được gọi là thuần nhất bậc n và viết deg(a) = n.
Chú ý: 0 có bậc tùy ý.
3. Một K-đại số phân bậc A được gọi là hữu hạn sinh nếu tồn tại một tập
hữu hạn các phần tử thuần nhất {a
i
}
1≤i≤m
thỏa mãn A được sinh như
một không gian vectơ bởi các đơn thức
{a
e
1
1
. . . a
e
m
m
|e
i
∈ N, 1 ≤ i ≤ m}
Nếu deg(a
i
) = 1, ∀i = 1, . . . , m thì A được gọi là một K-đại số phân
bậc chuẩn.
Lúc này, A
i
= {a
e
1
1
. . . a
e
m
m
|e
1
+ . . . + e
m
= i}
Ví dụ:
Xét S = K[x
1
, . . . , x
n
] là vành đa thức n biến trên trường K, deg(x
i
) = 1
với 1 ≤ i ≤ n.
Ta có S là K-đại số phân bậc chuẩn hữu hạn sinh, S =
i≥0
S
i
.
Trong đó
S
i
= {x
α
1
1
. . . x
α
n
n
|α
j
∈ N, 1 ≤ j ≤ n,
n
j=1
α
j
= i}
(Xem [5, Định lí 2.2.5]).
5
1.3 Iđêan phân bậc
1. Cho A =
n≥0
A
n
là một K-đại số phân bậc, một iđêan phân bậc là
một không gian vectơ con có dạng I =
n≥0
I
n
thỏa mãn
(a) ∀n ≥ 0, I
n
⊆ A
n
(b) A
i
I
j
⊆ I
i+j
, ∀i, j ≥ 0
2. Cho A =
n≥0
A
n
là một K-đại số phân bậc, a
1
, . . . , a
m
là các phần tử
của A, iđêan
I = (a
1
, . . . , a
m
) = {
n
i=1
a
i
b
i
|b
i
∈ A, 1 ≤ i ≤ m}
được gọi là iđêan sinh bởi a
1
, . . . , a
m
.
3. Cho A =
n≥0
A
n
là một K-đại số phân bậc, iđêan sinh bởi tập các
phần tử thuần nhất được gọi là iđêan thuần nhất.
Ví dụ: Cho K[x, y] là K-đại số phân bậc, iđêan I = (x
2
, xy) ⊂ K[x, y]
là iđêan thuần nhất (được sinh bởi các phần tử thuần nhất bậc hai).
4. Cho A =
n≥0
A
n
là một K-đại số phân bậc, giả sử a
1
, . . . , a
m
∈ A là
các phần tử thuần nhất với deg(a
i
) = d
i
, 1 ≤ i ≤ m. Lúc này, iđêan
thuần nhất I = (a
1
, . . . , a
m
) là iđêan phân bậc và I =
n≥0
I
n
với
I
n
= A
n
∩ I.
(Xem [3, Định lí 2.1.3], [5, Mệnh đề 2.3.5])
Ví dụ: Cho K[x, y] là K-đại số phân bậc, iđêan I = (x
2
, xy) ⊂ K[x, y]
là iđêan phân bậc I = ⊕
n≥0
I
n
trong đó I
0
= I
1
= 0, I
2
= x
2
, xy, I
3
=
x
3
, x
2
y, xy
2
, . . .
5. Cho A =
n≥0
A
n
là một K-đại số phân bậc, I =
n≥0
I
n
là iđêan
phân bậc. Ta có A/I là K-đại số phân bậc và A/I =
n≥0
(A
n
/I
n
).
(Xem [5, Định lí 2.3.6])
Ví dụ: Cho A = K[x, y] là K-đại số phân bậc và I = (x
2
, xy) là iđêan
phân bậc. Ta có, A/I = ⊕
n≥0
A
n
/I
n
trong đó
A
0
/I
0
= K, A
1
/I
1
= A
1
, A
2
/I
2
= y
2
, A
3
/I
3
= y
3
,
6
1.4 Chuỗi Hilbert
1.4.1 Hàm Hilbert
1. Cho A =
n≥0
A
n
là một K-đại số phân bậc hữu hạn sinh. Hàm Hilbert
của A được định nghĩa như sau
H(A, n) = dim
K
(A
n
)
với dim
K
A
n
là số chiều của không gian vectơ A
n
trên trường K.
Ví dụ: Xét K-đại số phân bậc chuẩn hữu hạn sinh S = K[x
1
, . . . , x
n
],
deg(x
i
) = 1 với 1 ≤ i ≤ n, S =
i≥0
S
i
,với
S
i
= {x
α
1
1
. . . x
α
n
n
|α
j
∈ N, 1 ≤ j ≤ n,
n
j=1
α
j
= i}
Ta có, dim
K
(S
i
) = C
i
n+i−1
=
(n + i −1)!
i!(n −1)!
(xem [5, Mệnh đề 2.2.6]).
Vậy H(S, i) = dim
K
(S
i
) = C
i
n+i−1
=
(n + i −1)!
i!(n −1)!
2. Nếu I =
n≥0
I
n
là một iđêan thuần nhất của A, ta có thể định nghĩa
H(I, n) = dimI
n
Ví dụ: Cho A = K[x, y, z] là vành đa thức theo biến x, y, z trên
trường K, iđêan I = (x
2
, y
2
, xz, yz) ⊂ K[x, y, z] là iđêan thuần nhất.
Ta có, I là iđêan phân bậc, I =
n≥0
I
n
với I
0
= I
1
= 0, I
2
=
x
2
, y
2
, xz, yz, I
3
= x
3
, y
3
, x
2
y, x
2
z, y
2
x, y
2
z, xz
2
, yz
2
, xyz, . . .
Vậy, H(I, 0) = H(I, 1) = 0, H(I, 2) = 4, H(I, 3) = 9, . . .
1.4.2 Chuỗi Hilbert
1. Cho A =
n≥0
A
n
là K-đại số phân bậc hữu hạn sinh, chuỗi Hilbert
của A được định nghĩa như sau
F(A, t) =
∞
n=0
H(A, n)t
n
7
Ví dụ:
Xét K-đại số phân bậc chuẩn hữu hạn sinh A = K[x],
A =
i≥0
A
i
và H(A, i) = dim
K
A
i
= 1, ∀i ≥ 0.
Lúc này, chuỗi Hilbert của A = K[x] là
F(A, t) = 1 + t + t
2
+ t
3
+ . . . =
1
1 −t
2. Nếu I =
n≥0
I
n
là một iđêan thuần nhất của A thì chuỗi Hilbert của
I là
F(I, t) =
∞
n=0
H(I, n)t
n
3. Cho A =
n≥0
A
n
là một K-đại số phân bậc và I =
n≥0
I
n
là một
iđêan phân bậc. Khi đó
F(A/I, t) = F(A, t) −F(I, t)
(Xem [3, Định lí 2.2.2])
8
Chương 2
CƠ SỞ GR
¨
OBNER CỦA IĐÊAN
2.1 Thứ tự đơn thức trên K [x
1
, . . . , x
n
]
2.1.1 Định nghĩa
Một thứ tự đơn thức trên K[x
1
, . . . , x
n
] là một quan hệ > trên Z
n
≥0
thỏa
mãn các tính chất sau:
1. > là một thứ tự toàn phần trên Z
n
≥0
.
2. Nếu α > β và γ ∈ Z
n
≥0
thì α + γ > β + γ.
3. > là thứ tự tốt trên Z
n
≥0
.
(Nghĩa là mọi tập con khác rỗng của Z
n
≥0
đều có phần tử bé nhất theo
quan hệ >.)
2.1.2 Một số thứ tự đơn thức
1. Thứ tự từ điển (>
lex
).
Cho α = (α
1
, . . . , α
n
) và β = (β
1
, . . . , β
n
) ∈ Z
n
≥0
. Ta nói, α lớn hơn β
theo thứ tự từ điển nếu trong vectơ (α − β) ∈ Z
n
thành phần khác 0
đầu tiên bên trái là số dương.
Ta viết x
α
>
lex
x
β
nếu α >
lex
β.
Ví dụ:
(a) (1, 0, 2) >
lex
(0, 1, 2) vì (1, 0, 2) −(0, 1, 2) = (1, −1, 0).
(b) (2, 2, 1) >
lex
(2, 2, 0) vì (2, 2, 1) −(2, 2, 0) = (0, 0, 1).
2. Thứ tự từ điển ngược (>
invlex
).
Cho α = (α
1
, . . . , α
n
) và β = (β
1
, . . . , β
n
) ∈ Z
n
≥0
. Ta nói, α lớn hơn β
theo thứ tự từ điển đảo nếu trong vectơ (α −β) ∈ Z
n
thành phần khác
9
0 đầu tiên bên phải là số dương.
Ta viết x
α
>
invlex
x
β
nếu α >
invlex
β.
Ví dụ:
(a) (1, 0, 3) >
invlex
(0, 1, 2) vì (1, 0, 3) −(0, 1, 2) = (1, −1, 1).
(b) (0, 0, 1) >
invlex
(0, 1, 0) vì (0, 0, 1) −(0, 1, 0) = (0, −1, 1).
3. Thứ tự từ điển phân bậc (>
grlex
).
Cho α, β ∈ Z
n
≥0
. Ta nói, α >
grlex
β nếu
|α| =
n
i=1
α
i
> |β| =
n
i=1
β
i
hoặc |α| = |β| và α >
lex
β.
Ví dụ:
(a) (1, 3, 0) >
grlex
(2, 0, 1) vì |(1, 3, 0)| = 4 > |(2, 0, 1)| = 3.
(b) (3, 1, 2) >
grlex
(3, 0, 3) vì |(3, 1, 2)| = 6 = |(3, 0, 3)| = 6 và (3, 1, 2) >
lex
(3, 0, 3).
4. Thứ tự từ điển ngược phân bậc (>
grevlex
).
Cho α, β ∈ Z
n
≥0
. Ta nói, α >
grevlex
β nếu
|α| =
n
i=1
α
i
> |β| =
n
i=1
β
i
hoặc |α| = |β|
và trong (α −β) ∈ Z
n
thành phần khác 0 đầu tiên bên phải là âm.
Ví dụ:
(a) (3, 2, 1) >
grevlex
(3, 2, 0) vì |(3, 2, 1)| = 6 > |(3, 2, 0)| = 5.
(b) (1, 0, 0) >
grevlex
(0, 0, 1) vì |(1, 0, 0)| = 1 = |(0, 0, 1)| và (1, 0, 0) −
(0, 0, 1) = (1, 0, −1).
2.1.3 Bậc của đa thức
Định nghĩa 2.1.1. Cho f =
a
α
x
α
là một đa thức khác 0 trong K[x
1
, . . . , x
n
]
và > là một thứ tự đơn thức
10
1. Bậc của f là
multideg(f) = max{α ∈ Z
n
≥0
: a
α
= 0}
2. Hệ số dẫn đầu của f (leading coefficient) là
LC(f) = a
multideg(f)
3. Đơn thức dẫn đầu của f (leading monomial) là
LM(f) = x
multideg(f)
4. Hạng tử dẫn đầu của f (leading term) là
LT (f) = LC(f)LM(f)
Ví dụ: Xét f = x
2
yz − 2x
3
+ y
2
z
2
với thứ tự từ điển.
Ta có:
multideg(f) = (3, 0, 0)
LC(f) = −2
LM(f) = x
3
LT (f) = −2x
3
Bổ đề 2.1.2. Cho f, g là hai đa thức khác 0 trên K[x
1
, . . . , x
n
], khi đó
1. multideg(fg) = multideg(f) + multideg(g)
2. Nếu f + g = 0 thì
multideg(f + g) ≤ max{multideg(f), multideg(g)}
Dấu = xảy ra khi multideg(f) = multideg(g).
2.2 Thuật toán chia trong K[x
1
, . . . , x
n
]
Định lí 2.2.1. Với > là một thứ tự đơn thức trên Z
n
≥0
, F = {f
1
, . . . , f
s
}
là tập s đa thức đã được sắp thứ tự trong K[x
1
, . . . , x
n
]. Khi đó mỗi f ∈
11
K[x
1
, . . . , x
n
] đều có thể viết dưới dạng
f = a
1
f
1
+ a
2
f
2
+ . . . + a
s
f
s
+ r
với a
i
, r ∈ K[x
1
, . . . , x
n
], i = 1, s trong đó r = 0 hoặc r là tổ hợp tuyến tính
các đơn thức và r không chia hết cho bất kì LT (f
i
) nào.
Nếu a
i
f
i
= 0 ta luôn có multideg(f) ≥ multideg(a
i
f
i
).
2.3 Iđêan đơn thức và bổ đề Dickson
Định nghĩa 2.3.1. Iđêan I ⊂ K[x
1
, . . . , x
n
] được gọi là iđêan đơn thức nếu
có một tập con hữu hạn A ⊂ Z
n
≥0
sao cho I chứa tất cả các đa thức có dạng
α∈A
h
α
x
α
với h
α
∈ K[x
1
, . . . , x
n
].
Lúc này ta viết I = (x
α
|α ∈ A).
Bổ đề 2.3.2. Cho I = (x
α
|α ∈ A) là một iđêan đơn thức. Khi đó, đơn thức
x
β
thuộc I khi và chỉ khi x
β
chia hết cho một vài x
α
, α ∈ A.
Chứng minh.
1. ⇒) Giả sử x
β
∈ I, theo định nghĩa I ta có x
β
=
s
i=1
h
i
x
α(i)
với h
i
∈
K[x
1
, . . . , x
n
] và α(i) ∈ A. Ta xem h
i
như tổ hợp tuyến tính các đơn
thức h
i
=
n
j=1
a
i
j
x
k
i
j
j
⇒ x
β
=
s
i=1
(
n
j=1
a
i
j
x
k
i
j
j
)x
α(i)
=
n
j=1
(
s
i=1
a
i
j
x
k
i
j
j
x
α(i)
)
Mỗi hạng tử ở vế phải của phương trình trên đều chia hết cho F =
{x
α(i)
, i = 1, s}.
Do đó, ta có x
β
chia hết cho {x
α(i)
, i = 1, s}.
2. ⇐) Giả sử x
β
chia hết cho một vài x
α
, α ∈ A, theo định nghĩa I ta có
x
β
∈ I.
12
Bổ đề 2.3.3. Cho I = (x
α
|α ∈ A) là một iđêan đơn thức, f ∈ K[x
1
, . . . , x
n
].
Khi đó, các mệnh đề sau là tương đương
1. f ∈ I
2. Mỗi hạng tử của f đều nằm trong I
3. f là tổ hợp K tuyến tính các đơn thức của I
Chứng minh.
1. 3 ⇒ 2) Giả sử f =
k
i=1
b
i
x
β(i)
với x
β(i)
∈ I.
Ta có x
β(i)
∈ I ⇒ x
β(i)
=
s
j=1
h
j
i
x
α(j
i
)
, α(j
i
) ∈ A
⇒ b
i
x
β(i)
= b
i
s
j=1
h
j
i
x
α(j
i
)
=
s
j=1
(b
i
h
j
i
)x
α(j
i
)
, α(j
i
) ∈ A.
Như vậy mỗi hạng tử của f đều thuộc I.
2. 2 ⇒ 1) Giả sử mỗi hạng tử của f đều thuộc I, ta có
f =
i
(
s
j=1
a
j
i
x
α(j
i
)
) =
s
j=1
(
i
a
j
i
)x
α(j
i
)
∈ I
3. 1 ⇒ 3) f ∈ I ⇒ f =
k
i=1
h
i
x
α(i)
với α(i) ∈ A.
Do α(i) ∈ A nên ta có x
α(i)
∈ I.
Vì vậy f là tổ hợp k tuyến tính các đơn thức của I.
Hệ quả 2.3.4. Hai iđêan đơn thức bằng nhau khi và chỉ khi chúng chứa các
đơn thức giống nhau.
Định lí 2.3.5. (Bổ đề Dickson)
Mọi iđêan đơn thức I = (x
α
|α ∈ A) ⊂ K[x
1
, . . . , x
n
] đều có thể viết dưới
dạng I = (x
α(1)
, . . . , x
α(s)
) với α(i) ∈ A, i = 1, s, nói cách khác là I có cơ
sở hữu hạn.
Chứng minh. Ta chứng minh quy nạp theo n.
13
1. n = 1.
Giả sử I được sinh bởi x
α
, α ∈ A ⊂ Z
≥0
và đặt β là phần tử nhỏ nhất
của A ⊂ Z
≥0
.
Khi đó ∀ f ∈ I = (x
α
|α ∈ A) ta có f =
s
i=1
h
i
x
α(i)
, α(i) ∈ A.
Do α(i) ∈ A nên suy ra α(i) ≥ β ⇒ α(i) = β + γ(i) (γ(i) ≥ 0)
⇒ f = x
β
s
i=1
h
i
x
γ(i)
∈ (x
β
)
⇒ I ⊂ (x
β
)
Mặt khác ta có (x
β
) ⊂ I, vì vậy I = (x
β
).
2. Giả sử định lí đúng với n − 1 (n > 1), ta chứng minh định lí đúng với
n.
Giả sử I ⊂ K[x
1
, . . . , x
n−1
, y] là iđêan đơn thức. Lúc này tồn tại một
tập A ⊂ Z
n
≥0
hữu hạn sao cho I = (x
α
y
m
|(α, m) ∈ A).
Đặt J là iđêan trong K[x
1
, . . . , x
n−1
] sinh bởi các x
α
mà x
α
y
m
∈ I với
m ≥ 0.
Theo giả thiết quy nạp thì J có cơ sở hữu hạn: J = (x
α(1)
, . . . , x
α(s)
)
Với mỗi 1 ≤ i ≤ s ta có x
α(i)
y
m
i
∈ I, ((α(i), m
i
) ∈ A). Đặt m =
max{m
i
}, với mỗi k ∈ {0, 1, . . . , m − 1} xét iđêan J
k
⊂ K[x
1
, . . . , x
n−1
]
sinh bởi các x
β
(β ∈ Z
n−1
≥0
) thỏa x
β
y
k
∈ I.
Theo giả thiết quy nạp thì J
k
cũng có tập sinh hữu hạn:
J
k
= (x
α
k
(1)
, . . . , x
α
k
(s
k
)
).
Ta nhận thấy I được sinh từ các đơn thức sau:
Từ
J : x
α(1)
y
m
, . . . , x
α(s)
y
m
J
0
: x
α
0
(1)
, . . . , x
α
0
(s
0
)
J
1
: x
α
1
(1)
y, . . . , x
α
1
(s
1
)
y
.
.
.
J
m−1
: x
α
m−1
(1)
y
m−1
, . . . , x
α
m−1
(s
m−1
)
y
m−1
Thật vậy, xét x
α
y
p
∈ I ta có:
(a) p ≥ m thì theo cấu trúc của J ta có x
α
y
p
chia hết cho một vài
x
α(i)
y
m
.
14
(b) p ≤ m − 1 thì theo cách xây dựng J
p
ta có x
α
y
p
chia hết cho một
vài x
α
p
(j)
y
p
.
Theo Bổ đề 2.3.2 ta có các đơn thức của I nằm trong iđêan sinh bởi
các đơn thức ở trên. Như vậy, iđêan sinh bởi các đơn thức ở trên và I
chứa các đơn thức giống nhau, theo Hệ quả 2.3.4 ta có hai iđêan này
bằng nhau.
Viết lại các biến dưới dạng x
1
, . . . , x
n
. Lúc này I = (x
α
|α ∈ A) ⊂
K[x
1
, . . . , x
n
]. Theo chứng minh trên ta có
I = (x
γ(1)
, . . . , x
γ(t)
), x
γ(i)
∈ I, i = 1, t
Do x
γ(i)
∈ I = (x
α
|α ∈ A) nên theo Bổ đề 2.3.2 ta có x
γ(i)
=
s
j=1
h
j
x
α(j)
với α(j) ∈ A
⇒ I = (x
α(1)
, . . . , x
α(s)
) với α(i) ∈ A.
Như vậy định lí đúng với n.
Định lí được chứng minh.
Hệ quả 2.3.6. Cho > là một quan hệ trên Z
n
≥0
thỏa mãn
1. > là thứ tự toàn phần trên Z
n
≥0
.
2. α > β, γ ∈ Z
n
≥0
⇒ α + γ > β + γ
Khi đó > là thứ tự tốt khi và chỉ khi α ≥ 0 với mọi α ∈ Z
n
≥0
.
Chứng minh.
1. ⇒) Giả sử > là thứ tự tốt, α
0
là phần tử bé nhất của Z
n
≥0
.
Giả sử 0 > α
0
, cộng thêm nα
0
vào hai vế ta có
nα
0
> α
0
+ nα
0
⇔ nα
0
> (n + 1)α
0
⇒ α
0
> 2α
0
> . . . > (n + 1)α
0
> . . . Đây là một dãy giảm vô hạn, mâu
thuẫn với giả thiết > là thứ tự tốt.
15
2. ⇒) Giả sử α ≥ 0 ∀α ∈ Z
n
≥0
, A ⊂ Z
n
≥0
là tập khác rỗng, ta cần chỉ ra A
có phần tử nhỏ nhất.
Xét I = (x
α
|α ∈ A) là iđêan đơn thức, theo Định lí 2.3.5 tồn tại
α(1), . . . , α(s) ∈ A sao cho I = (x
α(1)
, . . . , x
α(s)
).
Không mất tính tổng quát ta có thể giả sử
α(s) > α(s −1) > . . . > α(2) > α(1)
Ta chứng minh α(1) là phần tử bé nhất của A, lấy α ∈ A ta có
x
α
∈ I = (x
α(1)
, . . . , x
α(s)
)
Theo Bổ đề 2.3.2 ta suy ra α = α(i) + γ với γ ∈ Z
n
≥0
.
Theo giả thiết ta có γ ≥ 0 nên suy ra α ≥ α(1).
Vậy α(1) là phần tử bé nhất của A hay > là thứ tự tốt.
2.4 Định lí cơ bản Hilbert và cơ sở Gr¨obner
Định nghĩa 2.4.1. Cho I ⊂ K[x
1
, . . . , x
n
] là một iđêan đơn thức khác {0}.
1. Kí hiệu LT (I) là tập các hạng tử dẫn đầu của các phần tử của I.
LT (I) = {cx
α
| ∃f ∈ I : LT (f) = cx
α
}
2. (LT (I)) là iđêan sinh bởi các phần tử của LT (I).
Mệnh đề 2.4.2. Cho I ⊂ K[x
1
, . . . , x
n
] là một iđêan
1. (LT (I)) là một iđêan đơn thức.
2. Tồn tại g
1
, . . . , g
t
∈ I sao cho (LT (I)) = (LT (g
1
), . . . , LT (g
t
))
Chứng minh.
1. Do I là iđêan nên ta có iđêan đơn thức (LM(g) |g ∈ I\{0})
Vì LM(g) và LT (g) sai khác nhau một hằng số khác 0 nên ta có
(LM(g) | g ∈ I\{0}) = (LT (g) |g ∈ I\{0}) = (LT (I))
⇒ (LT (I)) là iđêan đơn thức.
16
2. Theo Định lí 2.3.5, tồn tại g
1
, . . . , g
t
∈ I sao cho
(LM(g) | g ∈ I\{0}) = (LM(g
1
), . . . , LM(g
t
))
⇒ (LT (I)) = (LM(g
1
), . . . , LM(g
t
))
Do LM(g
i
) = cLT (g
i
) nên ta có
(LM(g
1
), . . . , LM(g
t
)) = (LT (g
1
), . . . , LT (g
t
))
Vậy nên (LT (I)) = (LT (g
1
), . . . , LT (g
t
)).
Định lí 2.4.3. ( Định lí cơ bản Hilbert)
Mọi iđêan I ⊂ K[x
1
, . . . , x
n
] đều có một tập sinh hữu hạn, tức là
I = (g
1
, . . . , g
t
) g
i
∈ I, i = 1, t.
{g
1
, . . . , g
t
} được gọi là một cơ sở của I.
Chứng minh. 1. I = {0}. Tập sinh hữu hạn là {0}.
2. Nếu I chứa đa thức khác 0 thì theo Mệnh đề 2.4.2 tồn tại g
1
, . . . , g
t
∈ I
sao cho
(LT (I)) = (LT (g
1
), . . . , LT (g
t
))
Ta có (g
1
, . . . , g
t
) ⊂ I vì g
i
∈ I, ∀i = 1, t.
Lấy tùy ý f ∈ I, gọi r là phần dư của phép chia f cho {g
1
, . . . , g
t
}. Ta
có
r = f − a
1
g
1
− . . . − a
t
g
t
∈ I
Nếu r = 0 suy ra LT(r) ∈ (LT (I)) = (LT (g
1
), . . . , LT (g
t
)).
Theo Bổ đề 2.3.2 ta có LT(r) chia hết cho {LT (g
1
), . . . , LT (g
t
)} điều
này mâu thuẫn với r là phần dư.
⇒ r = 0 ⇒ f = a
1
g
1
+ . . . + a
t
g
t
+ 0 ∈ (g
1
, . . . , g
t
) ⇒ I ⊂ (g
1
, . . . , g
t
).
Vậy I = (g
1
, . . . , g
t
)
17
Định nghĩa 2.4.4. Cố định một thứ tự đơn thức. Một tập con hữu hạn
G = {g
1
, . . . , g
t
} của iđêan I được gọi là một cơ sở Gr¨obner của I nếu
(LT (g
1
), . . . , LT (g
t
)) = (LT (I))
Nói cách khác {g
1
, . . . , g
t
} ⊂ I là một cơ sở Gr¨obner của iđêan I khi và
chỉ khi hạng tử dẫn đầu của mọi phần tử của I chia hết cho một trong các
LT (g
i
).
Hệ quả 2.4.5. Cố định một thứ tự đơn thức, khi đó mọi iđêan I ⊂ K[x
1
, . . . , x
n
] =
{0} đều có một cơ sở Gr¨obner. Hơn nữa, cơ sở Gr¨obner của iđêan I là một
cơ sở của I.
Chứng minh. Cho iđêan I khác {0}. Khi đó, tập G = {g
1
, . . . , g
t
} xây dựng
như trong Định lí 2.4.3 là một cơ sở Gr¨obner của I. Hơn nữa, ta có I =
(g
1
, . . . , g
t
) nên G là một cơ sở của I.
Định lí 2.4.6. Cho I
1
⊂ I
2
⊂ I
3
⊂ . . . là một dây chuyền tăng các iđêan
trong K[x
1
, . . . , x
n
]. Khi đó, tồn tại N ≥ 1 thỏa mãn
I
N
= I
N+1
= I
N+2
= . . .
Chứng minh. Đặt I =
∞
i=1
I
i
, ta chứng minh I cũng là một iđêan của K[x
1
, . . . , x
n
].
Do 0 ∈ I
i
, ∀i nên ta suy ra 0 ∈ I.
Lấy f, g ∈ I bất kì, theo định nghĩa I =
∞
i=1
I
i
cho nên tồn tại I
i
, I
j
sao cho
f ∈ I
i
, g ∈ I
j
.
Giả sử i ≤ j ⇒ f, g ∈ I
j
. Vì I
j
là một iđêan nên ta có f +g ∈ I
j
⇒ f + g ∈ I
Với mọi f ∈ I, r ∈ K tồn tại I
i
sao cho f ∈ I
i
. Lúc này, rf ∈ I
i
⊂ I.
Như vậy I là một iđêan.
Theo Định lí 2.4.3 , iđêan I có một tập sinh hữu hạn. Đặt I = (f
1
, . . . , f
s
).
Với mỗi f
i
, i = 1, . . . , s tồn tại số j
i
nhỏ nhất sao cho f
i
∈ I
j
i
.
Đặt N = max{j
i
|i = 1, . . . , s}, ta có f
i
∈ I
N
, ∀i = 1, . . . , s.
Suy ra I = (f
1
, . . . , f
s
) ⊂ I
N
⊂ I
N+1
⊂ . . . ⊂ I.
Vậy tồn tại N ≥ 1 thỏa mãn I
N
= I
N+1
= I
N+2
= . .
18
2.5 Tính chất của cơ sở Gr¨obner
Mệnh đề 2.5.1. Cho G = {g
1
, . . . , g
t
} là một cơ sở Gr¨obner của iđêan
I ⊂ K[x
1
, . . . , x
n
] và f ∈ I. Khi đó, tồn tại duy nhất r ∈ K[x
1
, . . . , x
n
] thỏa
mãn hai tính chất sau
1. Mọi hạng tử của r đều không chia hết cho bất kì LT (g
i
), i = 1, . . . , n.
2. Tồn tại g ∈ I sao cho f = g + r.
Chứng minh. Sử dụng thuật toán chia đa thức f cho G ta có được
f = a
1
g
1
+ . . . + a
t
g
t
+ r
trong đó r là phần dư, r thỏa mãn điều kiện thứ nhất.
Đặt g = a
1
g
1
+ . . . + a
t
g
t
∈ I, ta có f = g + r.
Ta chứng minh r là duy nhất.
Giả sử tồn tại r
1
, r
2
thỏa hai điều kiện của mệnh đề, lúc này
f = g
+ r
1
= g” + r
2
⇒ g
− g” = r
2
− r
1
∈ I
Nếu r
2
= r
1
ta có LT (r
2
− r
1
) ∈ (LT(I)) = (LT (g
1
), . . . , LT (g
t
)).
Theo Bổ đề 2.3.2 ta có LT (r
2
− r
1
) chia hết cho một vài LT (g
i
).
Mặt khác, không có hạng tử nào của r
1
, r
2
chia hết cho bất kì LT (g
i
) với
1 ≤ i ≤ t.
Do đó r
2
− r
1
= 0 ⇒ r
1
= r
2
.
Hệ quả 2.5.2. Cho G = {g
1
, . . . , g
t
} là một cơ sở Gr¨obner của iđêan I ⊂
K[x
1
, . . . , x
n
] và f ∈ I. Khi đó, f ∈ I khi và chỉ khi phần dư trong phép chia
f cho G bằng 0.
Chứng minh. ⇒) Giả sử f ∈ I, ta có f = f + 0 thỏa mãn Mệnh đề 2.5.1.
Như vậy, phần dư của phép chia f cho G bằng 0.
19
⇐) Giả sử phần dư của phép chia f cho G bằng 0, ta có f =
t
i=1
h
i
g
i
, h
i
∈
K[x
1
, . . . , x
n
]. Như vậy f ∈ I.
Định nghĩa 2.5.3. Cho f, g ∈ K[x
1
, . . . , x
n
] là các đa thức khác 0.
1. Nếu multideg(f) = α và multideg(g) = β, ta đặt γ = (γ
1
, . . . , γ
n
) với
(γ
i
= max{α
i
, β
i
}, i = 1, . . . , n). Khi đó, x
γ
được gọi là bội chung nhỏ
nhất của LM(f) và LM(g) và viết x
γ
= LCM(LM(f), LM(g)).
2. S-đa thức của f và g được định nghĩa như sau
S(f, g) =
x
γ
LT (f)
f −
x
γ
LT (g)
g
Bổ đề 2.5.4. Giả sử ta có một tổng dạng
t
i=1
c
i
x
α(i)
g
i
với c
1
, . . . , c
t
là các hằng
số và α(i)+multideg(g
i
) = δ ∈ Z
n
≥0
khi c
i
= 0. Nếu multideg(
t
i=1
c
i
x
α(i)
g
i
) <
δ thì tồn tại các hằng số c
jk
sao cho
t
i=1
c
i
x
α(i)
g
i
=
j,k
c
jk
x
δ−γ
jk
S(g
j
, g
k
)
trong đó x
γ
jk
= LCM(LM(g
j
), LM(g
k
)). Hơn nữa, mỗi x
δ−γ
jk
S(g
j
, g
k
) có
bậc nhỏ hơn δ.
Chứng minh. Với mỗi i ∈ {1, . . . , t}, ta đặt d
i
= LC(g
i
), β(i) = multideg(g
i
) ⇒
LT (g
i
) = d
i
x
β(i)
.
Ta có c
i
d
i
= LC(c
i
x
α(i)
g
i
).
Do multideg(c
i
x
α(i)
g
i
) = α(i) + β(i) = δ và multideg(
t
i=1
c
i
x
α(i)
g
i
) < δ nên
ta có
t
i=1
c
i
d
i
= 0 và LM(g
i
) = x
β(i)
là ước của x
δ
.
Như vậy x
γ
jk
= LCM(LM(g
j
), LM(g
k
)) cũng là ước của x
δ
. Suy ra x
δ−γ
jk
20
là đơn thức và ta có
x
δ−γ
jk
S(g
j
, g
k
) = x
δ−γ
jk
(
x
γ
jk
LT (g
j
)
g
j
−
x
γ
jk
LT (g
k
)
g
k
)
=
x
δ
d
j
x
β(j)
g
j
−
x
δ
d
k
x
β(k)
g
k
=
x
α(j)
g
j
d
j
−
x
α(k)
g
k
d
k
Đặt p
i
=
x
α(i)
g
i
d
i
, ta suy ra x
δ−γ
jk
S(g
j
, g
k
) = p
j
− p
k
và
t
i=1
c
i
x
α(i)
g
i
=
t
i=1
c
i
d
i
p
i
= c
1
d
1
(p
1
− p
2
) + (c
1
d
1
+ c
2
d
2
)(p
2
− p
3
)
+ . . . + (c
1
d
1
+ . . . + c
t−1
d
t−1
)(p
t−1
− p
t
) + (c
1
d
1
+ . . . + c
t
d
t
)p
t
Kết hợp với kết quả
t
i=1
c
i
d
i
= 0 ta viết lại
t
i=1
c
i
x
α(i)
g
i
dưới dạng
t
i=1
c
i
x
α(i)
g
i
= c
1
d
1
x
δ−γ
12
S(g
1
, g
2
) + (c
1
d
1
+ c
2
d
2
)x
δ−γ
23
S(g
2
, g
3
)
+ . . . + (c
1
d
1
+ . . . + c
t−1
d
t−1
)x
δ−γ
(t−1)t
S(g
t−1
, g
t
)
Vậy
t
i=1
c
i
x
α(i)
g
i
=
j,k
c
jk
x
δ−γ
jk
S(g
j
, g
k
)
Do multideg(p
j
) = multideg(p
k
) = δ và LC(p
j
) = LC(p
k
) = 1 nên ta có
multideg(p
j
− p
k
) < δ, suy ra x
δ−γ
jk
S(g
j
, g
k
) có bậc nhỏ hơn δ.
Định lí 2.5.5. Cho I là một iđêan đa thức, một cơ sở G = {g
1
, . . . , g
t
} của
I là một cơ sở Gr¨obner của I khi và chỉ khi phần dư của phép chia S(g
i
, g
j
)
cho G bằng 0 với mọi i = j.
Chứng minh. ⇒) Giả sử G là cơ sở Gr¨obner của I. Do S(g
i
, g
j
) ∈ I nên áp
dụng Hệ quả 2.5.2 ta có phần dư của phép chia S(g
i
, g
j
) cho G bằng 0.
⇐) Với mỗi đa thức f = 0 thuộc I = (g
1
, . . . , g
t
) tồn tại các đa thức
21
h
i
∈ K[x
1
, . . . , x
n
] sao cho f =
t
i=1
h
i
g
i
.
Theo Bổ đề 2.1.2 ta có multideg(f) ≤ max{multideg(h
i
g
i
)|i = 1, . . . , t}.
Đặt m(i) = multideg(h
i
g
i
), δ = max{m(1), . . . , m(t)} ⇒ multideg(f) ≤ δ.
Với mỗi cách biểu diễn f ta nhận được một δ khác nhau. Do thứ tự đơn
thức là thứ tự tốt nên ta có thể chọn biểu diễn f =
t
i=1
h
i
g
i
sao cho δ nhận
được là nhỏ nhất.
Ta viết lại f dưới dạng
f =
m(i)=δ
h
i
g
i
+
m(i)<δ
h
i
g
i
=
m(i)=δ
LT (h
i
)g
i
+
m(i)=δ
(h
i
− LT(h
i
))g
i
+
m(i)<δ
h
i
g
i
Các đơn thức trong
m(i)=δ
(h
i
−LT(h
i
))g
i
và
m(i)<δ
h
i
g
i
đều có bậc nhỏ hơn δ.
Giả sử multideg(f) < δ ta có multideg(
m(i)=δ
LT (h
i
)g
i
) < δ.
Đặt LT (h
i
) = c
i
x
α(i)
⇒
m(i)=δ
LT (h
i
)g
i
=
m(i)=δ
c
i
x
α(i)
g
i
.
Áp dụng Bổ đề 2.5.4 ta có
m(i)=δ
LT (h
i
)g
i
=
j,k
c
jk
x
δ−γ
jk
S(g
j
, g
k
)
với c
jk
∈ K, x
δ−γ
jk
= LCM(LM(g
j
), LM(g
k
)).
Theo giả thiết phần dư của phép chia S(g
j
, g
k
) cho G bằng 0 nên ta có
S(g
j
, g
k
) =
t
i=1
a
ijk
g
i
với a
ijk
∈ K[x
1
, . . . , x
n
].
Theo Định lí 2.2.1 ta có multideg(a
ijk
g
i
) ≤ multidegS(g
j
, g
k
), ∀i, j, k.
Nhân x
δ−γ
jk
vào S(g
j
, g
k
) ta có
x
δ−γ
jk
S(g
j
, g
k
) =
t
i=1
b
ijk
g
i
trong đó b
ijk
= x
δ−γ
jk
a
ijk
.
⇒ multideg(b
ijk
g
i
) ≤ multideg(x
δ−γ
jk
S(g
j
, g
k
)) < δ.
22
Như vậy ta có
m(i)=δ
LT (h
i
)g
i
=
j,k
c
jk
x
δ−γ
jk
S(g
j
, g
k
)
=
j,k
c
jk
(
i
b
ijk
g
i
) =
i
(
j,k
c
jk
b
ijk
)g
i
=
i
h
i
g
i
trong đó
h
i
=
j,k
c
jk
b
ijk
và multideg(
h
i
) = multideg(
j,k
c
jk
b
ijk
) < δ.
Do đó, ta có f được biểu diễn qua tổ hợp các g
i
mà tất cả các hạng
tử của biểu diễn đều có bậc nhỏ hơn δ. Điều này mâu thuẫn với δ =
max{m(1), . . . , m(t)}.
Suy ra multideg(f) = δ = multideg(h
i
g
i
), ∀i = 1, . . . , t hay LT (f) ∈
(LT (g
1
), . . . , LT (g
t
)).
Vậy (LT (I)) = (LT (g
1
), . . . , LT (g
t
)). Do đó, G là cơ sở Gr¨obner của I.
2.6 Thuật toán Buchberger
Ta kí hiệu f
F
là phần dư của phép chia f cho F .
Định lí 2.6.1. (Thuật toán Buchberger)
Cho I = (f
1
, . . . , f
s
) = {0} là một iđêan đa thức. Đặt G = F = {f
1
, . . . , f
s
}.
Khi đó, ta sẽ xác định được một cơ sở Gr¨obner của I bằng thuật toán sau
1. Đặt G
= G. Với p = q ∈ G
, tính S = S(p, q)
G
.
2. Nếu xuất hiện S = 0 thì xét G = G
∪ {S} và tiến hành lại bước 1.
sau một số hữu hạn lần ta sẽ có được tập G = G
, đây chính là một cơ sở
Gr¨obner của I.
Chứng minh. Trước hết, ta chứng minh G ở mỗi lần thực hiện thuật toán
đều nằm trong I.
Đầu tiên, ta xét G
= F = {f
1
, . . . , f
s
} ⊂ I. Do p = q ∈ G
nên ta có
S(p, q) ∈ I. Suy ra S = S(p, q)
G
∈ I và G = {G
∪ {S}} ⊂ I.
23
Tương tự, với G
⊂ I ta cũng có G = {G
∪ {S}} ⊂ I trong đó S =
S(p, q)
G
, (p = q ∈ G
).
Hơn nữa, ta luôn có F ⊂ G
cho nên G
cũng là một cơ sở của I .
1. Nếu G = G
tức là S(p, q)
G
= 0, ∀p, q ∈ G, theo Định lí 2.5.5 ta có G là
cơ sở Gr¨obner của I.
2. Nếu xuất hiện S = 0 thì xét G = G
∪{S}, ta có (LT (G
)) ⊂ (LT(G)).
Lúc này, LT(S) /∈ (LT (G
)) nhưng LT (S) ∈ (LT (G)) cho nên (LT (G
))
là tập con thật sự của (LT (G)).
Như vậy nếu tiến hành liên tục thuật toán ở định lí thì ta sẽ có được
một dây chuyền tăng các iđêan trong K[x
1
, . . . , x
n
]. Theo Định lí 2.4.6
sau một số hữu hạn lần thực hiện thì sẽ xảy ra trường hợp (LT (G)) =
(LT (G
)). Lúc này, S = 0 và G = G
.
Vậy thuật toán sẽ kết thúc sau một số hữu hạn lần thực hiện và ta thu
được một cơ sở Gr¨obner của I.
Ví dụ
Xét K[x, y] là vành đa thức hai biến x, y với thứ tự từ điển phân bậc và
I = (f
1
, f
2
) = (x
3
− 2xy, x
2
y − 2y
2
+ x).
Đặt F = {f
1
, f
2
}, ta có
LT (f
1
) = x
3
LT (f
2
) = x
2
y
S(f
1
, f
2
) = −x
2
⇒ S(f
1
, f
2
)
F
= −x
2
= 0
Như vậy, F = {f
1
, f
2
} không phải là cơ sở Gr¨obner của I.
Đặt f
3
= −x
2
và xét G = {f
1
, f
2
, f
3
}.
Lúc này
S(f
1
, f
2
) = f
3
⇒ S(f
1
, f
2
)
G
= 0
S(f
1
, f
3
) = −2xy ⇒ S(f
1
, f
3
)
G
= −2xy = 0
24