BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Đỗ Thị Phương Thanh
CƠ SỞ GRöBNER TRONG VÀNH ĐA THỨC
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thành phố Hồ Chí Minh - 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Đỗ Thị Phương Thanh
CƠ SỞ GRöBNER TRONG VÀNH ĐA THỨC
Chuyên ngành: Đại số và lí thuyết số
Mã số: 60 46 01 04
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. TRẦN HUYÊN
Thành phố Hồ Chí Minh - 2014
Lời cảm ơn
Để hoàn thành luận văn này, tôi đã nhận được sự giúp đỡ của nhiều thầy
cô giáo, gia đình và bạn bè.
Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới Tiến sĩ Trần Huyên,
người thầy đã tận tình hướng dẫn và truyền đạt cho tôi những kiến thức và kinh
nghiệm quý báu trong suốt quá trình thực hiện luận văn.
Tôi xin chân thành gởi lời cảm ơn tới các thầy cô khoa Toán trường Đại
học Sư Phạm thành phố Hồ Chí Minh đã tận tình giảng dạy và truyền thụ kiến
thức cho tôi trong quá trình học tập tại trường.
Cuối cùng, tôi xin gởi lời cảm ơn tới gia đình và bạn bè, những người đã
luôn động viên, khuyến khích và giúp đỡ tôi trong suốt quá trình hoàn thành luận
văn.
TP. Hồ Chí Minh – Tháng 9 năm 2014
Đỗ Thị Phương Thanh.
MỤC LỤC
Trang phụ bìa
Lời cảm ơn
Bảng kí hiệu
Lời nói đầu ...................................................................................................................... 1
Chương 1. KIẾN THỨC CHUẨN BỊ ........................................................................... 3
§1: VÀNH ĐA THỨC ............................................................................................... 3
§2: MODULE .......................................................................................................... 10
Chương 2. CƠ SỞ GRöBNER .................................................................................... 13
§1: IDEAL ĐƠN THỨC ......................................................................................... 13
§2: IDEAL KHỞI ĐẦU ........................................................................................... 23
§3: CƠ SỞ GRöBNER ............................................................................................. 30
§4: VAI TRÒ CỦA CƠ SỞ GRöBNER TRONG VIỆC XÁC ĐỊNH
PHẦN TỬ CỦA IDEAL ................................................................................... 34
§5: THUẬT TOÁN BUCHBERGER ..................................................................... 39
Kết luận ......................................................................................................................... 48
Tài liệu tham khảo ....................................................................................................... 49
Bảng kí hiệu
Kí hiệu Ý nghĩa
( )K x
[ K x
]
1,...,
x n
f
Vành đa thức nhiều biến .
f
f 1,...,
.n
1,..., f
n
Ideal sinh bởi
lex≤
Thứ tự từ điển.
glex≤
Thứ tự từ điển phân bậc.
rlex≤
( )G I
Thứ tự từ điển ngược.
Tập hợp tất cả các đơn thức sinh tối tiểu I .
.f
( in f
)
Từ khởi đầu của đa thức
.f
( lm f
)
Đơn thức đầu của
.f
( lc f
)
( ) in I
Hệ số đầu của
S − đa thức của f và
.g
) ( S f g ,
I R
I là ideal của R .
Ideal khởi đầu của ideal I .
⊆
Tập con thực sự.
Tập con nhỏ hơn hoặc bằng.
■ Kết thúc một chứng minh
1
Lời nói đầu
=
Một trong các bài toán quan trọng trong vành đa thức
là: Cho
[ R K x
]
1,...,
x n
=
f
I
f
R
,
R∈ và
xác định xem f có thuộc I hay không?. Điều đó
f 1,...,
s
=
f
+ + ...
.
Để có biểu diễn
đòi hỏi f phải biểu diễn được dưới dạng
q f 1 1
q f s
s
f
này, một cách tự nhiên, ta lấy f chia cho
Đối với vành một biến thì R
f 1,...,
.s
là vành chính nên ideal I sẽ là ideal chính, theo định lí chia đa thức một biến thì
đa thức dư là duy nhất. Tuy nhiên, khi mở rộng lên vành đa thức nhiều biến, khi
chia theo những cách khác nhau thì đa thức dư cũng khác nhau, hơn nữa một đa
thức f
I∈ thì đa thức dư khi áp dụng một thuật toán nào đó chia f cho
f 1,...,
f s
2
2
2
=
+
=
=
+
=
y f ,
xy
x .
f
2 x y
x
xf
+ Ta có
hay
có thể khác 0. Ví dụ Cho
2
2
2
2
=
+
−
∈
f
x
y
f
,
f
nhưng
tức đa thức dư của f khi chia cho
yf 1
,f 1
f là 2
f 1
2
f 1 (
2 x y )
2
2
=
−
r
x
y
0.
≠ Vấn đề đặt ra là liệu có một hệ sinh
g 1,...,
g của I mà khi chia f t
cho
g theo bất kỳ thuật toán nào thì đa thức dư cũng là duy nhất và do đó
g 1,...,
t
nếu f
I∈ thì đa thức dư luôn bằng 0. Điều đó dẫn tới khái niệm cơ sở Gröbner
và thuật toán Buchberger giúp ta tìm cơ sở Gröbner từ một hệ sinh. Nội dung của
luận văn gồm:
Chương 1. Kiến thức chuẩn bị
Chương này gồm 2 tiết: Vành đa thức và module. Chương này cung cấp
những kiến thức cơ bản của vành đa thức một biến và nhiều biến. Đồng thời đưa
ra một số tính chất của một số module đặc biệt: module tự do, module hữu hạn
sinh, module Noether.
2
Chương 2. Cơ sở Gröbner
Chương này là phần chính của luận văn. Chương này chia làm 5 tiết.
Tiết 1: Ideal đơn thức
Trình bày định nghĩa và các tính chất cơ bản của ideal đơn thức và một vài lớp
ideal đặc biệt trong ideal đơn thức.
Tiết 2: Ideal khởi đầu
Trình bày định nghĩa ideal khởi đầu và các tính chất cơ bản của ideal khởi đầu.
Tiết 3: Cơ sở Gröbner
Trình bày định nghĩa cơ sở Gröbner và các loại cơ sở Gröbner.
Tiết 4: Vai trò của cơ sở Gröbner trong việc xác định phần tử của ideal
Trình bày định lí thuật toán chia và vai trò của cơ sở Gröbner trong việc ổn đinh
đa thức dư trong phép chia đa thức.
Tiết 5: Thuật toán Buchberger
Trình bày khái niệm S − đa thức và thuật toán Buchberger để tìm một cơ sở
Gröbner.
Luận văn chỉ xét đến vành đa thức trên một trường. Cho nên khi nói đến vành đa
thức mà không nói gì thêm thì ta hiểu đó là vành đa thức trên một trường.
3
Chương 1. KIẾN THỨC CHUẨN BỊ
Chương này trình bày một số tính chất cơ bản nhất của vành đa thức để làm
tiền đề nghiên cứu chương sau.
§1: VÀNH ĐA THỨC
1. Vành đa thức một biến
n
2
n
i
+
+ + ...
a 0
+ a x a x 1
2
a x n
= ∑ . a x i
=
0
i
=
=
=
=
0,...,
,
...
0
n
Cho R là một vành và x là biến. Ta gọi đa thức là một tổng có dạng:
= thì đa thức
a 0
a 11,
a n
, ia i
là những số thực. Nếu
n
m
i
j
≠
0
trong đó các được kí hiệu là 1.
( ) f x
( ) g x
)
a i
b≠ 0, i
= ∑ và a x i
= ∑ ( b x j
=
=
j
0
0
i
Hai đa thức được xem là bằng nhau
a=
i
j= .
a i
j
với nếu m n= và
n
m
m
i
j
k
+
=
+
a
.
Phép cộng đa thức được định nghĩa như sau:
m n> )
.
(
a x i
b x j
k
) b x k
∑
∑
∑
=
=
i
j
k
0
0
= 1
( giả sử
n
m
+ n m
i
j
k
=
.
.
Phép nhân đa thức được định nghĩa như sau:
c k
j
a x i
b x j
c x k
= ∑ a b i
∑
∑
∑
=
=
=
i
+ = j k
i
0
j
0
k
0
với
Định nghĩa 1.1.1: Với hai phép toán cộng đa thức và nhân đa thức nêu trên có thể kiểm tra tập tất cả đa thức lập thành vành giao hoán có phần tử đơn vị là đa thức 1. Tập
[ ]. K x
này được kí hiệu là vành
Sau khi định nghĩa được đa thức một biến, việc sắp thứ tự các số hạng trong đơn thức là cần thiết nên liền xuất hiện khái niệm bậc đa thức:
Định nghĩa 1.1.2: Bậc của đa thức khác 0
0
n
− 1
n
=
+
+ + ...
( ) f x
a x 0
a x − 1 n
a x n
4
Như vậy ta chỉ định nghĩa bậc của đa thức khác 0. Đối với đa thức không ta bảo nó không có bậc.
g x là hai đa thức khác 0.
( )
( ) f x và
Định lí 1.1.3: Giả sử
g x , thì ta có:
( )
+
≠ và bậc (
g x
( ) f x
( ) g x ).
≠
(i) Nếu bậc của
( ) f x , bậc thì ta có:
g x , và nếu thêm nữa
0,
( ) f x khác bậc ( ) ( ) + g x f x ( ) f x = bậc
0 ( )
+
Nếu bậc ( )) max = ( ) + f x (bậc ( ) g x
g x
( )) max ≤
( ) f x
( ), f x bậc
( ) g x ).
(bậc Bậc (
g x ≠ 0,thì ta có bậc (
( )
( ) g x ).
( ) f x
( ) f x + bậc
g x là hai đa thức khác 0 của
(ii) Nếu
0
( ) f x g x ≠ và bậc
( )
( ) g x .
( ) f x + bậc
[ ], K x thì
= bậc vành
( ) ( ) g x ) ≤ bậc f x ( ) ( ) Định lí 1.1.4: Nếu K là một miền nguyên f x và ) ( ) ( ) f x g x
(
[ ]K x cũng là miền nguyên.
f
} .n
f 1,...,
=
Hệ quả 1.1.5: Nếu K là miền nguyên, thì
( ) f x phải được biểu diễn
Nếu Để giải quyết vấn đề đặt ra: một đa thức f có thuộc một ideal I sinh bởi một hệ đa [ ]K x là vành một biến, K là thức { ( ). g x . Để có biểu diễn này Trong trường hợp đặc biệt, vành [ ]K x là vành chính thì I là ideal chính sinh bởi một đa thức ( ) f x
( ) ( ) q x g x . g x , để đảm bảo có phép chia, ta có định lí chia đa thức:
I∈ thì ( ) f x chia cho
( )
trường, khi đó ( ) f x ta phải lấy
K x thế thì bao
0
( ) f x và
( )
[ ];
=
+
( ) q x và với bậc
0.
( ) r x thuộc ( ) r x < bậc
g x ≠ của vành [ ]K x sao cho ( ) ( ) r x ≠ g x nếu
Định lí 1.1.6: Giả sử K là một trường,
( ) ( ) g x q x
( ) f x
( r x
giờ cũng có hai đa thức duy nhất ),
g x bằng 0.
( ) f x cho
( )
Do đa thức dư và đa thức thương duy nhất nên điều kiện cần và đủ để f thuộc I là dư của phép chia
5
f
f
[ ] K x∈
1,...,
n
Định nghĩa 1.1.7: Ước chung lớn nhất của các đa thức là đa thức h
=
=
∈
f
sao cho:
f
f
,...,
,...,
[ ] K x
1,...,
f , nghĩa là n
n
n
q n
1
q h 1
q h q ; 1
f
(i) h chia hết
1,...,
f , thì p chia hết h . n
=
f
(ii) Nếu p là đa thức khác chia hết
( h UCLN f
1,...,
) .n
∈
≥ Khi đó:
Trong trường hợp đó ta viết
f
f
,
2.
[ ] K x n
n
1,...,
f
Mệnh đề 1.1.8:Cho
( UCLN f
)
1,...,
n
=
(i) tồn tại và duy nhất với sai khác một hằng số khác 0 của K .
f
,...,
f
,...,
f
)
)
( ( UCLN f
)
1
n
1
n
=
. (ii) (
n ≥ thì 3
f
f
f
,...,
,...,
,
( UCLN f
)
)
( ( UCLN UCLN f
)
1
n
1
n
− 1
n
(iii) Nếu .
UCLN f g ta thực hiện lần lượt các
,
(
)
Thuật toán 1.1.9: (Thuật toán Euclide) để tìm
phép chia đa thức một biến:
+ = f ,
+ = g ,
+ = , p g 0 p s 1 0 p s 2 1 s 0 s 1 s 2
s 0 ......,
=
p
0
thì đến một lúc nào đó ta được
,
( UCLN f g
)
s +=
s m
s+ 1 m
m
+ 1
ms + = ) và thuật toán dừng với
2
m
1
(ở đây
2. Vành đa thức nhiều biến
) 1
n
là các biến. Ta gọi đơn thức là một biểu thức có Cho R là một vành và
( x n ≥ n )
a 1,...,
na n
=
1,..., x x ,trong đó ( a 1 ... x 1 = a
....
0
a ∈ được gọi là bộ số mũ của đơn thức. Nếu n = , thì đơn thức được kí hiệu là 1. Phép nhân trên tập các đơn thức được
n
a 1
dạng
định nghĩa như sau:
n
n
b n
=
...
...
...
.
x
x
x +
a x 1 1
b x 1 1
+ a b x 1 1 1
a n
b n n
a n
(
)(
)
6
Ra∈ được gọi là hệ số của từ. Thông
na n
a xa x 1 ... 1
,trong đó
na n
a xa x 1 ... 1
x
Từ là biểu thức có dạng thường các phần tử của R gọi là phần tử vô hướng. Hai từ khác không
na n
a β 1 ... x 1 phần tử vô hướng a là từ
.1.a
a
=
=
=
a
a
x
x
,...,
,...,
,
và là đồng dạng với nhau. Như vậy có thể xem đơn thức là từ với hệ số là 1, và
x
x
)
(
(
)
n
a 1
x 1
a 1 ... x 1
na n
Để cho tiện ta kí hiệu . Đa thức n
n ∈ và n x trên vành K là một tổng hình thức của các từ: n
x 1,...,
a
,
( ) f x
xa a
= ∑
n
∈ a
a
0
biến
aa ≠ . Từ 0
aa ≠ được gọi là từ của
a xa với
Trong đó chỉ có một số hữu hạn hệ số
ax là đơn thức của
( ) f x .
a
a
đa thức và
( ) f x
( ) g x
xβ a
xa a
aa β=
a
= ∑
= ∑
n
n
∈ a
∈ a
n
và được xem là bằng nhau, nếu Hai đa thức
a ∈ .
với mọi
a
a
a
+
=
x
x
x
)
a a
β a
( a β + a
a
∑
∑
∑
n
n
n
∈ a
∈ a
∈ a
Phép cộng đa thức được định nghĩa như sau:
a
a
a
=
x
x
x
a a
β a
γ a
∑
∑
∑
n
n
n
∈ a
∈ a
∈ a
.
Phép nhân đa thức được định nghĩa như sau:
γ a
aβ b
c
= ∑
∈
b c ,
;n
+ = b c a
trong đó
[ ]K x
[ K x
]
1,...,
x n
Định nghĩa 1.1.10: Với hai phép toán cộng đa thức và nhân đa thức nêu trên có thể kiểm tra tập tất cả đa thức lập thành vành giao hoán với phần tử đơn vị là đơn thức 1 . Tập này được kí hiệu là vành hay
≠
=
+ + ...
max
deg
7
( ) f x
{ a 1
a a | n a
} 0 . Đối với đa thức một biến, bậc tổng thể chính là bậc thông thường. Đôi khi bậc tổng thể của đa thức nhiều biến cũng được gọi tắt là bậc, nếu như không có sự hiểu nhầm nào xảy ra.
Định nghĩa 1.1.11: Bậc tổng thể của đa thức
( ) f x khác không, ta sắp xếp theo các thứ tự
Để sắp xếp các hạng tử của một đa thức
của các từ được gọi là thứ tự từ:
[ ]K x thỏa mãn các tính chất sau:
≤
,1
Định nghĩa 1.1.12: Thứ tự từ ≤ là một thứ tự toàn phần trên tập M tất cả các đơn thức của
(i)
∈ m M ,
m m≤ 1 2
mm mm≤ 2. 1
1
2
Với mọi , . m m m m M∈ mà thì (ii) Nếu
Từ định nghĩa trên ta thấy ngay trên vành đa thức một biến chỉ có một thứ tự từ. Đó là thứ tự xác định bởi bậc đơn thức. Dưới đây ta sẽ thấy có nhiều cách định nghĩa thứ tự từ khi số biến từ hai trở lên. Trước hết ta thiết lập một số tính chất chung của thứ tự từ.
>
>
> ...
m m m 2 3
1
Mệnh đề 1.1.13: Một thứ tự toàn phần ≤ trên M là thứ tự tốt khi và chỉ khi mọi dãy đơn thức thực sự giảm:
sẽ dừng (sau hữu hạn phần tử).
Mệnh đề 1.1.14: Mọi thứ tự từ là thứ tự tốt. Ngược lại mọi thứ tự tốt trên M thỏa điều kiện (ii) của định nghĩa 1.1.12 là thứ tự từ.
Một số thứ tự từ
>
>
>
...
x
x
x 1
2
.n
Cho ≤ là một thứ tự từ. Sau khi đổi chỉ số các biến luôn có thể giả thiết:
n
1
<
...
...
x
lex≤ xác định như sau:
aβ x 1 1
n
lex −
−
Sau đây là một số thứ tự từ quan trọng:
)
aβ x x n n 1 a β a β 1,..., n
1
n
là Định nghĩa 1.1.15:Thứ tự từ điển là thứ tự nếu thành phần đầu tiên khác không kể từ bên trái của vector (
=
,
≤ < sao cho
8
n
= a β aβ 1,...,
1
i
i
nhưng
1.)
1
i
i
một số âm. (Nói cách khác, nếu tồn tại 0 i a β+ +<
Thứ tự từ điển tương tự như cách sắp xếp các từ trong từ điển, và do đó có tên gọi như vậy.
n
1
1
<
<
...
x
xác định như sau: Định nghĩa 1.1.16: Thứ tự từ điển phân bậc là thứ tự
deg
...
...
x
aβ x 1 1
aβ x n n
glex
n
aβ x 1 1
a x n n
β n n
x 1
)
(
n
1
=
...
deg
x 1
aβ x n n
n
x 1 )
glex≤ ) ( deg ) và thành phần đầu tiên khác không kể từ bên trái của
n
1
<
( −
−
...
...
x
nếu hoặc
1
aβ x n n
glex
n
aβ x 1 1
x 1
n
1
<
=
<
a
a
n + + ...
+ + ...
+ + ...
... x ) hoặc
là một số âm. (Nói cách khác, nếu
x
...
...
... ( aβ deg x 1 1 vector ( + + a ... 1
a β a β 1,..., n β 1
β n
n
a 1
n
β 1
β n
aβ x n n
lex
n
aβ x 1 1
x 1
và .)
rlex≤
n
1
<
<
Định nghĩa 1.1.17: Thứ tự từ điển ngược là thứ tự
...
x
deg
...
...
x
a x 1 1
rlex
n
aβ x n n
aβ x 1 1
x 1
a x n n
β n n
)
(
n
1
=
...
deg
aβ x n n
n
x 1
β x 1 1 )
nếu hoặc
n
( −
−
<
xác định như sau: ( ) deg ) và thành phần đầu tiên khác không kể từ bên trái của
...
x
a x 1 1
β x 1 1
n
=
1 + + ...
a
+ + ...
aβ x n n rlex và tồn tại 0 i
là một số dương. (Nói cách khác,
n
β n
... ( aβ deg x 1 1 vector ( a nếu 1
n β 1
β 1
=
,
... ≤ < sao n
a hoặc 1 +> a β+
i
i
+ + ... 1.)
1
i
i
... x ) a β a β 1,..., n + + < β a ... n n = a β aβ 1,...,
1
nhưng cho
Mệnh đề 1.1.18: Ba thứ tự kể trên là các thứ tự từ.
Sau khi sắp xếp được các hạng tử của đa thức, ta sẽ mở rộng phép chia đa thức nhiều biến sẽ xét ở chương sau. Trước tiên, ta thấy vành đa thức nhiều biến cũng có một số tính chất được mở rộng trực tiếp từ vành đa thức một biến.
[ ]K x cũng là miền nguyên.
Mệnh đề 1.1.19: Nếu K là miền nguyên thì vành đa thức
( ) ( ) f x g x ,
[ ] R x∈
đều Mệnh đề 1.1.20: Nếu K là miền nguyên, thì với mọi đa thức
=
+
deg
deg
deg
( ) ( ) f x g x
( ) f x
( ) g x
(
)
có:
và
+
≤
deg
,deg
( ) f x
( ) g x
( ) f x
(
)
{ max deg
} ( ) g x
=
9
deg
deg
( ) f x
( ) g x
f
g= −
Hơn nữa, ta có bất đẳng thức chặt khi và chỉ khi và
deg
deg
( ) f x
( ) g x
.
10
§2: MODULE
Với định nghĩa module và các tính chất cơ bản của module đã học ở đại số đồng điều, tiết này ta xem xét một vài module đặc biệt.
Tập các phần tử Định nghĩa 1.2.1: Cho
1. Module tự do và module hữu hạn sinh .
S M⊆
∈
∈
∈
+ + ...
,
,...,
,...,
S
}
{ r s 1 1
r s n | n n
r 1
r n
R s ; 1
s n
lập thành module con của M gọi là module con sinh bởi S và kí hiệu là S .
S M
∅ ≠ ⊆ được gọi là tập sinh hay hệ sinh của M nếu M S=
Tập con .
Tập được gọi là tập sinh tối tiểu (hay hệ sinh tối tiểu) nếu nó không thực sự chứa một hệ sinh khác của M .
=
S
Ta gọi M là module hữu hạn sinh nếu nó có một hệ sinh hữu hạn.
{ }i e ∈ i I là tập sinh của M và mỗi phần tử m M∈ có thể biểu diễn duy nhất dưới dạng:
m
= ∑ re i i
∈ i I
0
i
I∈ .
Định nghĩa 1.2.2: Họ phần tử được gọi là cơ sở của R − module M nếu nó
ir = trừ một số hữu hạn chỉ số
trong đó ir R∈ và
Khác với không gian vector, không phải module nào cũng có cơ sở. Một module có cơ sở là module tự do. Nếu e F∈ là một phần tử của cơ sở của module tự do F thì module con Re R≅ . Khi đó ta có ngay:
R= với mọi i
e ∈ khi và chỉ khi F đẳng cấu i I I∈ .
iR∈⊕
i I
iR
Mệnh đề 1.2.3: F là R − module tự do với cơ sở { }i với tổng trực tiếp ,trong đó
Module tự do có cơ sở hữu hạn thì số phần tử của một cơ sở là không thay đổi:
11
Mệnh đề 1.2.4: Cho R là vành không tầm thường và F là mdule tự do với cơ sở hữu hạn. Khi đó mọi cơ sở của F cũng hữu hạn và hai cơ sở tùy ý của F có số phần tử như nhau.
,
1,..., x
Hệ quả 1.2.5: Mọi module hữu hạn sinh đều đẳng cấu với module thương của module nR n ≥ nào đó. 0
= M trên
/R M . Do vậy mọi tập
M M
M
/
x là tập sinh của không gian vector n
x 1,..., sinh tối tiểu của M có số phần tử như nhau.
Định lí 1.2.6: Giả sử R là vành chỉ có một ideal cực đại duy nhất M và M là R − module hữu hạn sinh. Khi đó x là tập sinh của M khi và chỉ khi ảnh n
2. Module Noether
Định nghĩa 1.2.7: Cho R là một vành và M là module trên R . Các điều kiện sau là tương đương:
(i) Mọi tập khác rỗng các module con của M đều có phần tử cực đại (đối với
⊆
quan hệ bao hàm thức).
⊆ M M
⊆ ⊆ ...
⊆ ...,
M + 1 n
2
1
n
= . ...
(ii) Mọi dây chuyền tăng các module con của M M
k
= M M + k 1
đều dừng sau hữu hạn bước, tức là tồn tại k để
(iii) Mọi module con của M đều hữu hạn sinh.
Module thỏa mãn một trong ba điều kiện trên được gọi là module Noether.
Từ định nghĩa ta suy ra ngay: R là vành Noether nếu và chỉ nếu nó là module Noether trên chính nó.
/M N là R − module Noether.
Mệnh đề 1.2.8: Cho M là module trên vành R và N là module con. M là module Noether khi và chỉ khi cả hai module N và
(
Định lí 1.2.9: R − module M là Noether khi và chỉ khi M là hữu hạn sinh và ) /R Ann M là Noether.
Từ bổ đề và định lí suy ra: nếu R là vành Noether thì mọi vành thương của nó cũng là Noether.
12
Định lí Hilbert về cơ sở: Cho K là vành Noether và x là tập n biến. Khi đó vành [ ]K x cũng là vành Noether.
[ ]K x trên trường K là hữu hạn
Khi đó ta có ngay hệ quả: Mọi ideal của vành đa thức
sinh.
Q
Định nghĩa 1.2.10:
Q của R sao cho:
1,...,
n
Q
Một ideal I của một vành R được gọi là có sự phân tích nguyên sơ nếu có hữu hạn ideal
Q là các ideal nguyên sơ.
1,...,
n
= ∩ ∩
...
i)
Q .n
I Q 1
ii) `
Định lý 1.2.11 (Lasker-Noether):
Trong một vành Noether mọi ideal thực sự đều có sự phân tích nguyên sơ.
Định nghĩa 1.2.12:
= ∩ thì I M=
Một ideal thực sự của một vành R được gọi là bất khả quy nếu nó không phải là giao của 2 ideal chứa nó thực sự.
.
hay Nói cách khác ideal I của R là bất khả quy khi và chỉ khi I R≠ và với mọi ideal I N= ,M N nếu I M N
Mệnh đề 1.2.13:
Mỗi ideal thực sự của một vành nơte R là giao của một số hữu hạn ideal bất khả quy.
Mệnh đề 1.2.14:
(i) Nếu ideal 0 trong vành Noether là bất khả quy thì nó là ideal nguyên sơ.
(ii) Mỗi ideal bất khả quy trong vành Noether là nguyên sơ.
13
Chương 2. CƠ SỞ GRöBNER Chương này chủ yếu giải quyết bài toán đặt ra trên vành đa thức nhiều biến. Để có khái niệm cơ sở Gröbner, ta cần nghiên cứu ideal đơn thức, ideal khởi đầu. Sau khi có khái niệm cơ sở Gröbner, ta sẽ tìm hiểu vai trò của nó trong việc xác định phần tử của một ideal. Từ đó, ta có thuật toán tìm cơ sở Gröbner để giải quyết hoàn toàn bài toán đặt ra.
§1: IDEAL ĐƠN THỨC
Trong các lớp ideal của vành đa thức nhiều biến, có một lớp ideal rất quan trọng là ideal đơn thức, là cơ sở giúp ta đưa ra các khái niệm ideal khởi đầu hay cơ sở Gröbner được trình bày trong các mục sau.
=
I
;a x a A
Định nghĩa 2.1.1: Ideal I được gọi là ideal đơn thức nếu nó sinh bởi các đơn thức.
∈ ,trong đó
.n
A ⊆ Chú ý rằng
Như vậy một ideal đơn thức có dạng
trong định nghĩa này không yêu cầu tập A hữu hạn. Tuy nhiên các kết quả sau đây cho ta các thông tin chính xác hơn về số phần tử của tập sinh của nó.
1. Tập sinh của ideal đơn thức
Nghiên cứu một đơn thức thì dễ dàng và đơn giản hơn đa thức. Chẳng hạn, xét quan hệ chia hết của hai đa thức ta cần làm phép chia đa thức, đối với đơn thức ta chỉ cần xét số mũ của các biến và giữa hai đa thức có thể không tồn tại ướcchung lớn nhất nhưng đối với đơn thức thì luôn có ước chung lớn nhất. Cụ thể ta có:
≥
≥
.
Mệnh đề 2.1.2:
ax khi và chỉ khi 1 b
a 1,...,
b n
a n
a
b
{ a b , n n
bx chia hết cho đơn thức } { } a b , 1 1
=
,
...
.
(i)
min x 1
min x n
}
a
b
{ a b , n n
{ } a b , 1 1
=
,
...
.
(ii)
max x n
max x 1
) )
(iii) Đơn thức ( UCLN x x ( BCNN x x
Chứng minh:
cx sao cho
+
+ a c
b
b
c
c n
=
=
14
⇔ = ⇔ x
...x
ax khi và chỉ khi tồn tại đơn thức ...x
bx chia hết cho đơn thức b x x 1 1
+ a c x 1 1 1
b n n
a n n
=
+
≥
a 1
c 1
a 1
⇔
=
+
a
a
n
c n
n
b 1 ... b n
b 1 ... b n
a
b
c
=
≥
≥
c x UCLN x x
,
.
. Suy ra: (i) Đơn thức a x x x .
x
|c
a x và
x
b x suy ra
,
|
a 1
c 1,...,a n
c n
)
≥ (
≥
≥
a x và
c x nghĩa là nếu
≥
≥
(ii) Gọi Khi đó và
n
b 1 a 1
n
c thì 1
|d |d b x thì x x ≥ ≥ d d 1,...,cn
n
=
b và 1 =
min
min
,...,
.Vậy
|d x ≥ d }
1,..., bn c d 1,...,a n {
c n d }
c 1
c n
a b , 1 1
. . Mặt khác nếu ≥ d 1,..., bn { a b , n n
;a x a A
I
∈ là ideal đơn thức. Đơn thức
bx
I∈ khi và chỉ khi
bx chia hết cho một đơn thức
ax với a A∈ nào đó.
bx
ax với a A∈ .
=
bx chia hết cho một đơn thức [x ]
bx
1,...,
s
i
(iii) Tương tự (ii) ta có điều phải chứng minh. ■ = Mệnh đề 2.1.3: Cho
I∈ thì tồn tại
A∈ ,
( )a i
I∈ nếu ih K∈
s
( ) a i
b
x
Chứng minh: Rõ ràng Ngược lại nếu và sao cho:
h x . i
= ∑
= 1
i
.
ih như tổng hữu hạn của các từ và khai triển vế phải của đẳng thức trên ta thấy
( )a ix
Xem
mỗi từ của nó phải chia hết cho
bx phải có tính chất của những từ đó, tức là chia hết cho
bx . Vậy
nào đó. Sau khi giản ước, một trong số đó còn lại ( )a ix
và phải bằng nào đó. ■
[ ]. f K x∈
Các điều kiện sau là tương Mệnh đề 2.1.4: Cho I là ideal đơn thức và
I∈
đương:
(a) f
(b) Mọi từ của f thuộc I .
(c) f là tổ hợp tuyến tính trên K của các đơn thức thuộc I .
a
(
( ) b
( )
15
). ⇒ ⇒ Đối với ( a
)
Chứng minh: Hiển nhiên có ( ) c
c⇒ nhận xét rằng tương ax với a A∈ .I Do đó mỗi từ của f là tích của
ax lại thuộc
tự như chứng minh mệnh đề trên ta có mỗi từ của f phải chia hết cho
nào đó. Mà mọi đơn thức chia hết cho một đơn thức I và một phần tử từ K , tức là có ( ).c ■
I∈ , các từ của f
Hệ quả 2.1.5: Hai ideal đơn thức trong một vành đơn thức bằng nhau nếu chúng chứa cùng một tập đơn thức.
Mệnh đề 2.1.6: Ideal I là ideal đơn thức khi và chỉ khi với mọi f đều thuộc I .
Chứng minh: Điều kiện cần suy ra từ mệnh đề 2.1.4. Từ giả thiết suy tập các đơn thức của các đa thức trong I sẽ sinh ra I . Do đó điều kiện đủ được chứng minh. ■
Theo định nghĩa, ideal đơn thức được sinh bởi các đơn thức, nhưng tập này có thể không hữu hạn. Nhưng định lí Hibert về cơ sở đã cho ta một kết quả đẹp là mọi ideal [ ]K x với K là trường đều hữu hạn sinh. Vậy một ideal đơn thức là của vành đa thức
=
I
;a x a A
hữu hạn sinh. Điều đó được phát biểu dưới dạng một bổ đề sau:
∈ bao giờ cũng viết
a
( ) a s
=
Mệnh đề 2.1.7: (Bổ đề Dickson) Mọi ideal đơn thức
I
( ) 1 ,...,
x
x
,
.
a
A∈ Nói riêng I là hữu hạn
( ) 1 ,...,
( ) a s
được dưới dạng trong đó
.
sinh.
1n = ta có
A ⊆ Chọn b A∈ là số nhỏ nhất. Khi đó
1
I
x=
.b
ax với a A∈ . Từ đó có ngay
Chứng minh: (ta sẽ chứng minh trực tiếp bổ đề Dickson) Chứng minh bằng quy nạp bx chia hết theo số biến n . Khi
1
'
=
x
,...,
cho mọi đơn thức
1n≤ − biến. Kí hiệu
(
)
x 1
x − 1 n
− 1n
'
a
x xa
Giả sử bổ đề đã được chứng minh đối với
[ ]K x có thể viết dưới dạng
,q n
.
∈ và 'x a sao cho tồn tại
q ∈ Gọi J là ideal của vành
]'K x sinh ra bởi các đơn thức
[
'
.
Ia ∈ Theo giả thiết qui nap, J sinh ra bởi hữu hạn đơn thức như vậy, tức là
m nx x
a '
a '
( ) 1
( ) s
=
J
x
,...,
x
.
Như vậy mỗi đơn thức trong trong đó
a '
i =
1,..., s
.
x
I
16
∈ Giả sử
( ) i m x i n
=
=
im ∈ sao cho ⊆
p
0,...,
m
1,
m
max
,...,
.
tồn tại Theo định nghĩa với mỗi
− xét ideal
{
}
[ K x
]'
pJ
m 1
m s
I
.
'x β sao cho
β ∈ Lại theo giả thiết qui nạp, p ' x x n
s
a ' p
p
)
(
a ' p
=
=
x
( ) 1 ,...,
x
,
p
0,...,
m
− 1.
pJ
Với mỗi sinh bởi các đơn thức
a '
a '
( ) 1
( ) s
x
x
,...,
,
Ta sẽ chứng tỏ I sinh ra bởi các đơn thức
:J )
m x n
m x n
'
(
)
0
s 0
a ' 0
x
( ) 1 ,...,
x a
,
(từ
0 :J
( ) 1
(
)
a ' 1
a ' 1
s 1
,...,
,
x
x
(từ )
1 :J )
x n
x n
(từ
(
)
( ) 1
− 1
1
− 1
− 1
a ' m
s m
− 1
a ' m
,...,
x
x
…
− .
1 :mJ −
m x n
m x n
'
q m≥ ,
'x a phải chia hết cho
,J
(từ )
'
q m≤
a ∈ nếu ' q theo cách xây dựng . x x I n x xa chia hết cho một đơn thức ở dòng thứ nhất ở trên. Nếu
( ) ix a − 1
Thật vậy, giả sử
q n
'
2q + ở trên. Theo mệnh đề 2.1.3 và Hệ
nào đó, và do đó
q n
thì
x xa chia hết cho một đơn thức ở dòng thứ .I
quả 2.1.5 các đơn thức liệt kê ở trên sinh ra
( )jxβ
( ) ( ) xβ β . Sử dụng mệnh đề 2.1.3 1 ,..., x r ( )jxγ
A .
Như vậy I sinh bởi một tập hữu hạn các đơn thức
γ ∈ Từ đó có
( ) j
( ) r
=
lần nữa, ta thấy mỗi đơn thức chia hết cho nào đó với
I
γ x
γ x
( ) 1 ,...,
.
G I
■ ngay
( ).
Khi đó ta có mỗi ideal đơn thức I có một tập sinh tối tiểu gồm các đơn thức. Tập sinh này được gọi là tập sinh đơn thức tối tiểu của I . Ta kí hiệu tập này là Mỗi đơn
.I Khi đó:
thức trong tập sinh này được gọi là đơn thức sinh của
( )G I không có ước thực sự trong I .
Mệnh đề 2.1.8: Các đơn thức sinh trong tập
17
( )G I có ước thực sự v trong
.I Khi đó ( )G I (mâu thuẫn tính sinh tối tiểu của u ). Vậy các đơn thức sinh trong tập
v thuộc ( )G I không có ước thực sự trong I . ■
Chứng minh: Giả sử đơn thức sinh u trong
=
=
u
Mệnh đề 2.1.9: Mỗi ideal đơn thức I có một tập sinh đơn thức tối tiểu duy nhất.
.I
}
}
v s
G 1
{ u 1,...,
r
G 2
{ v 1,...,
,
và là hai tập sinh tối tiểu của ideal Chứng minh: gọi
I∈ nên tồn tại
jv sao cho
= 1wi v u
j
iu
=
=
.
.
v
Vì với đơn thức
1w nào đó. Tương tự tồn tại i=
w u 2
k
j
u w w u 1 i 2
k
,ku w sao cho
v G
Suy ra Vì
2.
u i
= ∈ j
w = vì thế 1 1,
1G là tập sinh tối tiểu của I nên k G G⊂ 2.
1
2
Vậy Tương tự như vậy ta cũng có và
2 w w = Vậy 1. 1 G⊂ 1.
G 2
■
)
a 1,...,
≥
≥
.I Mỗi đơn thức .n Khi đó đơn thức hay tương đương điểm (
)
b 1,..., n
b 1,..., n a
a n
b 1
a
Chú ý: Để mô tả ideal đơn thức I chỉ cần chỉ rõ tập tất cả các đơn thức thuộc I hoặc ax có thể biểu diễn bởi điểm có ax bx chia hết cho đơn thức chỉ ra tập sinh đơn thức tối tiểu của tọa độ ( a trong không gian n
a 1,...,
b nằm trong khối ) .n
a
( ) a s
=
khi và chỉ khi vuông đầu tiên của hệ tọa độ Đề Các thông thường với gốc tọa độ là điểm (
I
( ) 1 ,...,
x
x
a
A∈ ,thì tất cả các đơn thức của I là
( ) 1 ,...,
( ) a s
)
(
,A và tập các
Như vậy nếu với
.I
những điểm nguyên nằm trong các khối vuông có đỉnh là các điểm thuộc đỉnh này là tập sinh đơn thức tối tiểu của
2. Các tính chất ideal đơn thức
J∩ và
:I J là các ideal
=
=
Mệnh đề 2.1.10: Cho
m
,I J là hai ideal đơn thức. Khi đó I và I ,
n m n ,
J
1,...,
m r
n 1,...,
s
i
j
I
∩ = J
,
|1
≤ ≤ i
r
;1
≤ ≤ i
j
.
đơn thức. Hơn nữa, nếu là các đơn thức, thì:
i
j
( BCNN m n
)
=
I n :
m UCLN m n
/
,
|1
≤ ≤ i
r
.
(a)
:I J có thể tính được theo công thức
j
i
i
j
(
)
s
(b) Do đó
I J :
I n :
j
(
)
j
= 1
=
và (a).
= ∩
I J :
I n :
.
18
J∩ là ideal đơn
= 1
s j
j
(
)
I
J
)a và ( )b đúng. Cho f
m I
J
∈ ∩ và m là một từ của f . Vì ∈ ∩ m J∈ Do đó . .
Chứng minh: Ta có Do đó chỉ cần chứng minh I
J∩ là ideal đơn thức.
) ,a nhận xét rằng bao hàm thức ⊇ là hiển nhiên. Cho đơn thức
thức, và các công thức tính ở ( ,I J là các ideal đơn thức nên theo mệnh đề 2.1.6 m I∈ và Lại theo mệnh đề 2.1.6, I
m I
J
.
∈ ∩ Theo mệnh đề 2.1.3, m chia hết cho
jn nào đó. Do đó m chia hết cho
im và
∈
m BCNN m n
,
|1
≤ ≤ i
;1
j
,
Để chứng minh (
)a . Chứng minh
BCNN m n . Suy ra j
,i
i
j
(
)
(
)
=
,
,
.
và ta có (
( )b tương tự nếu để ý rằng
i
i
m n i
j
j
) UCLN m n BCNN m n j
(
r (
≤ ≤ i )
■
a 1
=
kf
,
+ ∈ ...
f
cx
I
c K
I∈ vì I là ideal đơn thức
a r
=
S
a 1 ,...,
x
x
Mệnh đề 2.1.11: Căn của một ideal đơn thức là một ideal đơn thức.
.I Gọi
.f Bao lồi
≠ ∈ Ta có . }
n
Chứng minh: Lấy kf nên mọi từ của đều thuộc là tập các đơn thức của với 0 {
}
a ⊂ là một đa giác lồi. Ta có thể giả sử
1a là một đỉnh của đa giác
a 1,...,
r
.
của tập {
{
}
a 2,...,
a r
k
k
k
2
k 1
r
a 1
a 1
a 2
a r
=
=
+
...
.
x
x
x
x
...
.
k
k
bao lồi của tập
k< Vì thế
k 1
2
k 1
+ + và k r
(
)
1a hay Ta giả sử (
)
(
r
r
−
=
=
−
k
k
/
1.
/
k
k
với không ( ) thuộc )
(
)
(
(
)
(
)1 ) k
a 1
k 1
i
a i
i
∑
∑
=
=
2
i
2
i
k
với
)1 ax
k
.kf
kf
kf
I∈
Vì vậy không
1a không là một đỉnh của đa giác lồi (mâu thuẫn). Vậy đơn thức ( nên (
)1 ax
k
a 1
−
∈
.
a 2 ,...,
x
f
cx
I
.
1ax
I∈
I∈ Vì vậy
thể biểu diễn qua các từ khác trong là một đơn thức của Mà
a x ta sẽ có mọi từ r
)1 ax
I vì thế
I là một ideal đơn thức.
và Tiếp tục với nên (
của f đều thuộc
a
u
u
x=
Căn của một ideal đơn thức có thể được tính một cách tường minh thông qua
= ∏ với x i
i a ,
≠ 0i
là một đơn thức.■
} ( ) :u u G I∈
. Mệnh đề 2.1.12: Cho I là một ideal đơn thức. Căn của I được sinh bởi tập {
⊂
:
I
.
19
I là một ideal đơn thức, điều này đủ
{
} ( ) ∈ u u G I
I∈
u G I∈
Chứng minh: Dễ thấy Vì
( ).
kv
wu=
kv
k ≥
0,
I∈
để chứng tỏ mỗi đơn thức u là một tích của một vài phần tử u với
I∈ với
thì vì thế với w là một đơn thức. Vậy
Thật vậy, nếu v ta có điều phải chứng minh.■
3. Ideal đơn thức nguyên tố, ideal bất khả quy và sự phân tích
nguyên sơ
A. Ideal đơn thức nguyên tố
=
S
G I
m
Mệnh đề 2.1.13: I là ideal đơn thức nguyên tố khi và chỉ khi I sinh bởi các biến.
)⇒ gọi
( ) { =
{
}
}
1,...,
m r
1,..., x
x n
1,
S=
I
S⊂
.
, gọi là tập các biến sinh ra các Chứng minh: (
s∈ . Ta chứng minh I
S∈ thì tồn tại
kx
im i ,
phần tử . Dễ thấy Lấy
im I∈ hoặc
= m q x k
i
∀ ∈
.
k I∈ Nhưng
sao cho với
kx
kq là một đơn thức. Vì I là ideal nguyên tố nên ( ) im G I
.
S
không có ước thực sự trong I nên
u K∈ Vậy .
I⊂ .
im suy ra
m ux= k
i
kx
=
I
.
với
I∈ suy ra mỗi từ của
( ) ( ) f x g x
kq kq cũng không là một I∈ Suy ra ( ) ( ) f x g x chia hết cho
x s
∈
.
Lấy
f x và một từ
1,.., x }
( ) f x g x là tích của một từ của
( )
( )
ix với
1,..., x
x s
x i
g x nên từ của
f x chia hết cho
g x chia hết cho
Mà mỗi từ của ước thực sự của )⇐ Ta có ( {
( )
( )
( )
ix hoặc từ của
.ix Vậy
I∈ hoặc
I∈ . Vậy I là một ideal nguyên tố.■
( ) f x
( ) g x
của
=
Như vậy mỗi ideal đơn thức nguyên tố đều hữu hạn sinh, đặc biệt đối với vành đa thức n biến thì số ideal đơn thức nguyên tố là hữu hạn.
[ R K x
1,...,
] x ,n
n − 1.
R là 2
Mệnh đề 2.1.14: Cho vành số ideal đơn thức nguyên tố trong vành
1
.I
Chứng minh: Theo mệnh đề 2.1.13 thì ideal đơn thức nguyên tố I sinh bởi các biến. Ta có:
nC ideal
• Nếu I sinh bởi 1 biến thì có
2
.I
nC ideal
n
.I
20
nC ideal
n
n
=
−
=
• Nếu I sinh bởi 2 biến thì có • …….. • Nếu I sinh bởi n biến thì có
− ideal đơn thức nguyên tố. ■
C
C
+ + ...
2
1
) ( + 1 1
2 n
1 + C C n
n n
0 n Trong số các ideal đơn thức nguyên tố trên vành đa thức n biến thì ideal nào là ideal tối đại. Ta có mệnh đề:
=
=
Vậy ta có
I
[ R K x
1,...,
] x ,n
1,..., x
x n
Mệnh đề 2.1.15: Cho vành ideal là ideal tối đại đơn
thức duy nhất.
,...,
]
[ K x 1
x n
R
≅
=
K
Chứng minh: Ta có I là ideal đơn thức nguyên tố (theo mệnh đề). Ta lại có
I
,...,
x 1
x n
là trường nên I là ideal tối đại. Vậy I là ideal đơn
thức tối đại. ■
R là vành đa thức trên trường nên là vành Noether. Theo định lí Lasker-Noether, mỗi ideal trên vành Noether đều có phân tích nguyên sơ. Cho nên ta xét sự phân tích nguyên sơ của các ideal đơn thức.
m
I
:
I
B. Ideal bất khả quy và sự phân tích nguyên sơ
i
Q=
1
i
=
iQ nào có thể lược bỏ trong biểu diễn này. Ta có định lí nền tảng sau:
m
⊂ =
I
I
Một phân tích nguyên sơ của ideal được goi là tối giản nếu không ideal
[ ] S K x
i
iQ được
Q=
1
i
=
=
,...,
Định lí 2.1.16: Cho là một ideal đơn thức. Khi đó với
Q i
a x k i k
a x 1 i 1
sinh bởi lũy thừa của các biến nghĩa là . Hơn nữa sự phân tích nguyên
sơ này là duy nhất.
1
,
Chứng minh: Để chứng mịnh định lí này trước tiên ta chứng minh bổ đề sau:
,m n là hai đơn thức có
UCLN m n = (không chứa biến chung)
)
(
=
∩
m
m là các đơn thức. Khi đó
Bổ đề 2.1.17: Giả sử
,...,
m mn ,
,...,
,...,
r
1,...,
m 1
r
m 1
m m , r
m 1
m n , r
và
21
.⊇ Nếu
∩
i
∈ u m
m mn ,
.
,...,
,...,
Chứng minh bổ đề: Chỉ đơn
r≤ thì ,
1,...,
r
∈ u m 1
m m , r
m 1
m n , r
∈ u m
,
cần chia hết cho thức chứng minh im nào đó,
.m u |
m m , r
1,...,
|
∈ u m
m mn ,
.
Trong trường hợp ngược lại, vì nên theo mệnh đề 2.1.3 phải có
,m n không chứa biến chung nên
mn u Do đó .
1,...,
r
G I
u
Vì
}
r
( ) { = u 1,...,
vw=
Chứng minh định lí: Lấy và giả sử
1u không là một lũy thừa của các ,v w là những đơn thức nguyên tố cùng nhau. Áp
1u
=
=
I
v u ,
,...,
u
,...,
.
I
, w u
u
biến. Khi đó ta có thể viết với
= ∩ với I 2
I 1
I 1
2
r
2
2
r
và có
.I
Nếu hoặc chứa phần tử không là lũy thừa của các biến thì tiếp tục làm ta )2G I ( dụng bổ đề )1G I (
như trên. Sau hữu hạn bước ta sẽ được một phân tích của I bằng giao của cái ideal đơn thức sinh bởi lũy thừa của các biến. Loại bỏ các ideal chứa giao của các ideal khác, ta được một phân tích nguyên sơ tối giản của
...
...
∩ ∩ = ∩ ∩ là hai phân tích nguyên sơ tối giản của
.I Ta sẽ chỉ ra
Bây giờ ta đi chứng minh sự phân tích nguyên sơ tối giản này là duy nhất.
Q 1
' Q Q 1
r
' Q s
j
1,
1, r
Q
.
Lấy
i ∈ thì tồn tại
s∈ sao cho
' j
Q⊂ i
1,
1,
l
r∈ sao cho
rằng mỗi Tương tự ta cũng chỉ ra với mỗi
s= và
' . Q Q⊂ k
l
,...,
,...,
.
' Q s
Q r
k { Q 1
s∈ thì tồn tại } } { ' = Q 1
=
.
s .
i
r∈ 1,
.
Q
Điều này sẽ dẫn tới r
Q i
ka x k
a x 1 ,..., 1
' j
Q⊂/ i
j
=
∈
.
,...,
.
k∈/ 1,
Ta có thể giả sử Giả sử Với Thật vậy, lấy
b
.
b x s l
jl
b x l
' \ Q Q j i
j
a< l
∀ ∈ 1, j }
s
j
j
s
∈
⊂
.
u
Q
i ∈
1, k
mỗi j tồn tại Suy ra hoặc Lấy Ta có với { b u BCNN x 1 l 1
' j
Q i
ia ix chia hết u (điều này không thể). Vậy
j
= 1
Vì thế tồn tại sao cho
ta có điều phải chứng minh. ■
Một ideal được gọi là bất khả quy nếu nó không thể viết được như hai giao thật sự của hai ideal đơn thức. Nó được gọi là khả quy nếu nó không bất khả quy.
Hệ quả 2.1.18: Một ideal đơn thức là bất khả quy nếu và chỉ nếu nó được sinh bởi lũy thừa của các biến.
=
Q
,...,
,
22
= ∩ với J
,I J là những ideal đơn thức
a x k i k
a x 1 i 1
r
s
'
I
J
Chứng minh: Lấy và cho Q I
.Q Theo định lí trên ta có
i
' j
jQ Q sinh bởi lũy
,i
Q=
Q=
1
j
1
i
=
=
r
s
=
Q
Q
.
thật sự chứa và với
' j
Q i
Bởi việc loại bỏ những ideal
i
j
= 1
= 1
thừa của các biến. Vì thế ta có biểu diễn:
.Q Do tính
Q Q=
có sẵn trong giao ở vế phải, ta sẽ có sự phân tích nguyên sơ tối giản của
j nào đó
Q Q= i
' j
hoặc với ,i duy nhất của sự phân tích nguyên sơ tối giản ta có
vw=
1v
1
(mâu thuẫn).
UCLN v w = và ,
≠ ≠ , Áp w
)G Q chứa một đơn thức u
(
(
)
với Ngược lai, nếu
=
I
,
,
,
.
dụng bổ đề Q có thể được viết bằng giao thật sự của các ideal đơn thức. ■
2 2 2 x x x x x x x 1 3 2 3
2 1
2 2
2
=
,
,
,
,
I
2 2 2 , x x x x x x 1 3 2 3
2 1
2 2
2 2 , x x x x x x 2 3 2 3
2 1
2 2
=
,
2 2 2 , x x x x 1 2 2 3
2 2 , x x x 2 1 3
=
,
,
2 2 , x x x 1 2 2
2 2 2 , x x x 1 2 3
2 , x x 1 2
2 , x x 2 3
=
,
.
2 2 2 , x x x 1 2 3
2 , x x 1 2
2 , x x 2 3
Ví dụ: Cho Theo quá trình trên ta có:
I
Mỗi ideal đều có sự phân tích nguyên sơ, vậy ideal có mang tính chất của các thành phần nguyên sơ. Mệnh đề sau cho ta kết quả nếu các thành phần nguyên sơ không chứa trong một ideal thì ideal ban đầu cũng không chứa trong ideal đó.
I là các ideal đơn thức chỉ sinh bởi lũy thừa của các
I
I
.
1,..., I ,...,
Mện đề 2.1.19: Giả sử
⊆ /
,r I ⊆ /
I biến. Giả sử rằng 1
r
I
...
I
I
.
∩ ∩ ⊆/
1
r
,
I
I⊆
.
i
Khi đó:
r≤ vì ,
...
I⊆/
iI
I 1
r
a i
Chứng minh : Giả sử ngược lại Với mỗi có thể chọn
.I Vì
iI sao cho nó không
i
a
,...,
x
...
I
,...,
x
thức sinh dạng thuộc
∈ nên
r
I 1
kx
)
jx của ( BCNN x
)
a 1 j 1
a r j r
a 1 j 1
a r j r
chia hết cho một đơn thức sinh
k= và
1a là số lớn nhất trong
.I Không mất tính tổng quát có thể giả thiết 1j
được đơn ( BCNN x nào đó của
,...,
.
x
.
23
k= Khi đó
kx trong
ia mà
ij
1a là lũy thừa của biến
( BCNN x
)
a 1 j 1
a r j r
I
.
.
.
tất cả các số Từ
a≥ Suy ra
...
I⊆/
a 1
I I∈ Vô lí. Vậy 1
r
a jx 1
1
=
,
,
,
đó phải có ■
⊆/
2 3 x x , 1 2
2 2 x x x , 1 2 3
2 3 x x x , 1 2 3
2 3 x x , 1 2
2 2 3 x x x , 1 2 3
,
,
,
,
Ví Dụ: Ta có . Ta có và
⊆/
⊆/
2 3 x x x , 1 2 3
2 2 x x x , 1 2 3
2 2 3 , x x x 1 2 3
2 2 , x x x 1 2 3
nên .
§2: IDEAL KHỞI ĐẦU
Trong tiết mở đầu, khi đề cập đến vành đa thức nhiều biến, ta đã đưa ra một số thứ tự
=
=
từ để sắp xếp thứ tự các từ của đa thức. Điều đó giúp ta có được khái niệm sau:
x
[ ] R K x
[ K x
]
1,...,
n
∈ =
Như thường lệ, kí hiệu và M là tập đơn thức của nó.
1. Từ khởi đầu, đơn thức đầu Định nghĩa 2.2.1: Cho ≤ là một thứ tự từ và
f
x
[ R K x
1,...,
] .n
Từ khởi đầu của
,f kí hiệu là
in
f
.≤
(
),
≤
a
a
=
a
=
x
in
f
a x
,0
,
≠ ∈ thì K
= được gọi là hệ số đầu và
là từ lớn nhất của đa thức f đối với thứ tự từ
)
(
)
(
) f a
≤
( lm f ≤
lc ≤
là Nếu
.≤
đơn thức đầu của f đối với thứ tự từ
,
)
( in f
( lc f
)
( lm f
)
)
(tương ứng thay Nếu thứ tự từ ≤ đã được ngầm định, ta sẽ viết
in
f
f
,
).
(
)
(
)
)
≤
lc ≤
( lm f ≤
(tương ứng cho
Từ khởi đầu của đa thức 0 được xem là không xác định (có thể nhận giá trị tùy ý).
Từ khởi đầu còn được gọi là từ đầu hay từ đầu tiên. Như vậy nếu trong biểu diễn của
( in f
)
sẽ xuất hiện đầu tiên. Đương đa thức f ta viết các từ theo thứ tự giảm dần, thì
nhiên cách viết này cũng như từ khởi đầu của f phụ thuộc vào thứ tự từ đã chọn.
5
2
8
=
+
−
24
> > thì z
y
f
4 x y
4
3 x y
7
xyz
.
5
8
=
4 x y
= − 7
.
xyz
Ví dụ: Cho Đối với thứ tự từ điển x
)
( in f
( in f
)
, đối với thứ tự từ điển phân bậc thì
Một số tính chất cơ bản của các từ khởi đầu với một thứ tự từ ≤ nào đó trong quan hệ
với các phép toán trong vành đa thức.
,f g R∈ và
m M∈
.
=
Mệnh đề 2.2.2: Cho Khi đó:
(i)
) ) =
≤
+
,
g
(ii)
)
( lm g
} ) .
( . m in f ( ) in f ) = −
) . ( ). in g { ( lm f
)
max ( ). in g
Dấu < xảy ra khi và chỉ khi (iii)
( in mf ( in fg ( lm f ( in f Chứng minh:
=
+
f
;
,
( in f
)
)
( < m m in f i
i
∑
=
+
<
g
Giả sử:
( in g
)
) ,
( in g
j
n n ; j
và
im và
∑ jn là các từ có thể bằng 0. Khi đó:
+
=
+
= m f m
f
m m m
f
.
.in
.in
.
trong đó
(
)
(
)
)
i
m m . i
( < im in f
∑ .
∑
=
∀ Vậy
.
.
,
i .
.
.
)
( in mf
)
( m in f
)
( < im m m in f
=
+
+
+
f g .
.
Vì nên (i) Ta có:
( in f
)
( in g .
)
( n in f .
)
( m in g .
)
j
i
m n i
j
∑
∑ <
<
(ii) Ta có:
∑ )
)
) ( in g in f .
(
( in g
)
( jn in f .
jn
⇒
<
m in g .
.
( < m in f
)
(
)
( in f
)
( in g .
)
i
i
<
⇒
<
,
n
.
( < m in f
)
( in g
)
( in f
)
( in g .
)
i
j
m n . i
j
=
⇒ Ta có:
.
( in fg
)
( in f
)
( in g .
)
Suy ra:
≥
>
25
).
( in g
( in f
)
( in f
)
( in g
)
+
+
f
+ = g
n
(iii) Không mất tính tổng quát, ta có thể giả thiết Nếu
( in f
)
( in g
)
m i
j
≥
>
thì:
n
n>
+∑ ∑ . )
( in f
)
( in f
)
( in g
.j
j
nên Theo định nghĩa từ khởi đầu lại có Ta có
( in f
)
( in f
)
m> .i
+
≤
g
max
,
Vậy từ lớn nhất trong tổng trên và không giản ước được với các từ
)
( lm g
( lm f
)
{ ( lm f
} ) .
≠ −
=
khác, nên
( lm f
( lc f
)
( lc g
)
)
( lm g
)
+
+
f
+ = g
n
)
(
( lc f
)
(
) ( ) lc g lm f
m i
j
+∑ ∑ .
>
=
>
+
Nếu và thì
n
≠ và 0
)
( lm g
)
)
( m lm f
)
( lc g
)
( lm f
( lc f
,i
j
+
=
=
g
max
,
)
)
( lm g
)
( lm f
( lm f
{ ( lm f
} ) .
= −
.
f
+ = g
n
f
g+ =
0,
nên lại có Do
( in f
)
( in g
)
m i
j
+
=
<
+
=
<
g
thì hoặc Nếu
g
j
)
( lm f
)
( lm f
),
( lm g
) ( , i
)
( lm f
( lm m i
j
+∑ ∑ Như vậy hoặc ( lm n
)
hoặc nào đó). Vì
+
<
g
max
,
vậy:
( lm f
)
)
( lm g
{ ( lm f
} ) .
■
+
≤
g
max
,
( in f
)
)
( in g
{ ( in f
} ) ,
=
max
,
Chú ý rằng bất đẳng thức ở khẳng định (iii) ở trên cũng được viết dưới dạng:
in g được hiểu như
)
(
( lm f
)
( lm g
)
( .lm fa
)
{ ( in f
} )
0
Ka≠ ∈ nào đó.
thì với Trong đó khi
2. Ideal khởi đầu
26
,I
Khái niệm ideal khởi đầu sẽ là xuất phát điểm hình thành khái niệm cơ sở Gröbner.
Định nghĩa 2.2.3: Cho I là ideal của R và ≤ là một thứ tự từ. Ideal khởi đầu của
,I nghĩa là
( ),
in I≤
=
f
f
∈ I .
(
) |
( ) in I ≤
in ≤
kí hiệu là là ideal của R sinh bởi các từ đầu của các phần tử của
( ) in I
( ) in I≤
=
∈
f
I
,
Cũng như trên ta sẽ viết thay vì nếu ≤ đã xác định.
( ) in I
( lm f
) |
( ) in I
nên là ideal đơn thức. Rõ ràng cũng có
,I J là hai ideal của
.R Khi đó:
Cho ≤ là một thứ tự từ và
|
f
Nhận xét 2.2.3:
)
( ) in I
{ ( lm f
} I∈ .
I= .
(i) Tập tất cả các đơn thức trong là tập
( ) in I
(ii) Nếu I là ideal đơn thức thì
=
Thật vậy:
',
( m lm f m
).
=
=
(i) Nếu là một đơn thức, thì theo mệnh đề 2.1.3
m f '
f
.
m lm f m lm m f .
'
'
(
)
(
)
∈
|
f
I
∈ Điều ngược lại luôn luôn đúng.
Theo mệnh đề 2.2.2 (i) và trong đó I∈ .
( ) ∈ m in I I∈ và m M∈ ' { ) ( m lm f
} .
⊆
=
∈
∈
( ).
in I
I
Vậy
,
,
(
)
Nếu f
I⊆ tức là
I=
,
.
( in f
2.1.3, nên ( ) in f ( ) in I (ii) Vì I là ideal đơn thức, nên I sinh bởi tập hợp đơn thức A nào đó. Với mỗi I∈ là phần tử tùy ý, thì theo các ( ) m A m in m in I chia hết cho đơn thức m A∈ nào đó. Lại theo mệnh đề mệnh đề 2.1.3 và 2.1.4, )
in I có thể xem là một xấp xỉ của I bởi mệnh đề sau:
( )
Ideal khởi đầu
⊆
=
27
J⊆ thì
J⊆ và
( ) in I
( in J
)
( ) in I
( in J
).
Mệnh đề 2.2.4: Nếu I Hơn nữa nếu I
I
J=
.
thì
⊆
=
Chứng minh:
J⊆ kéo theo
( ) in I
( in J
).
( ) in I
( in J
).
∈
,
I
J≠
f
\ J I
Giả sử Nếu Theo định nghĩa rõ ràng I
=
∈
∈
=
min
|
g
J I \
do mọi thứ tự từ là thứ tự tốt nên ta có thể chọn được để
I∈ sao cho
in I
( lm f
)
)
( lm f
)
( in J
)
( ),
{ ( lm g
} .
=
Vì nên tồn tại g
f
/
,
/
( lm f
)
( lm g
).
( lc f
)
( ) g lc g
=
=
h
f
,f g
= Đặt
− Vì . g
J∈ nên
I∉ và g
I∈ nên
h
J∈ Nhưng f
.
lc f (
)
1.
( lc g
)
∈
<
Thay f,g bằng ta có thể giả thiết
h
I∉ Vậy
.
h
J I \
.
( ) lm h
( lm f
).
Mặt khác, theo mệnh đề 2.2.2(iii) ta lại có Điều
.f Vậy
I
J= ■ .
này mâu thuẩn với việc chọn
in I
( ).
Nếu cho Mệnh đề trên cho ta lấy được thông tin của ideal I từ ideal khởi đầu
in I
in I sẽ có hệ sinh đơn thức tối tiểu
( ),
( )
( ( ) G in I
).
khi đó Ta lấy ideal khởi đầu
=
I⊆ và
các đa thức trong I sao cho từ khởi đầu của nó là một đơn thức tối tiểu trong
in I
( in J
)
( ).
( ( ) G in I
).
Gọi J là ideal sinh bởi các đa thức này. Rõ ràng J
I
J=
.
Như vậy từ ideal khởi đầu ta có thể tìm lại thông tin ngược của ideal ban Vậy
đầu nhưng rõ ràng ideal khởi đầu dễ nghiên cứu hơn vì nó là ideal đơn thức.
Ta xét tính chất của ideal khởi đầu trong quan hệ các phép toán trên ideal:
⊆
Mệnh đề 2.2.5:
( ( ) in I in J
)
( in IJ
).
+
⊆
+
(i)
J
( ) in I
( in J
)
( in I
).
(ii)
Chứng minh:
28
J∈ và theo
)
(
)
),
=
⊆
( ) mệnh đề 2.2.2 (ii) ta có
in I in J sinh bởi các từ ( in f
( in fg
)
( in f ( ) in g
I∈ và ( in g trong đó f ( ) ), ) ( nên ta có in I in J
g ( in I J
, ).
⊂
+
(i) Vì
I
J J ,
I
J
( ) in I
( in I
)
⊆
+
+
⊂
+
và
J
J
⊂ + nên theo định nghĩa ta có ( in I
J ( ) in I
( in J
).
)
( in J
⊂ + I ).
k
=
Suy ra ■ (ii) Ta có ) ( in I
x
:a
[ R K x
]
a ∈ là cơ sở của
1,...,
x k
}
.R Cho I là ideal của R nên I là không gian véc tơ con của
.R Ta
Ta có là K − không gian véc tơ và tập {
a
a
a
a
a
k
=
=
∈
∉
∈
⊕
R
x
:
a
x
:
x
x
:
x
{
{
{
} ( ) in I
a
a
=
⊕
=
∉
không gian véc tơ có:
B
/
.
B≅
B
x
:
x
.
} ( ) in I ( ) R in I
( ) R in I
} } ( ) in I
{
/R I là không gian véc tơ
Gọi Vậy ta có suy ra Định lý
Macaulay sẽ cho ta biết không gian véc tơ đẳng cấu với nào?
,≤ tập B tất cả các đơn thức của /R I
in
( ) I≤
lập thành một hệ đại diện cơ sở của không gian véc tơ
a a ∈
+ + ...
= :
m
f
m B∈ và
trên trường Định lí 2.2.6 (Định lý Macaulay) Với mọi thứ tự từ M nằm ngoài .K
0
{ } \ 0
s
a 1
m 1
a s
s
s K
1,...,
1,..., R I / ).
sao cho và Chứng minh: Trước hết ta chứng tỏ tập B độc lập tuyến tính. Giả sử tồn tại m f = (trong
s≤ nào đó. Do đó
( in f
)
( ),
∈ im in I
ma= i i
/
,R I hay tương đương B I∪ sinh ra
im B∈ Bây . .R Kí hiệu E Do thứ tự từ là thứ tự tốt
.K Giả sử
E R≠ .
∈
R E \
f
Khi đó trái với giả thiết với i
=
∈
min
|
\
g R E
( lm f
)
)
{ ( lm g
} .
∈
−
giờ ta chứng tỏ B là hệ sinh của là tập các tổ hợp tuyến tính của B I∪ trên nên ta có thể chọn được sao cho
R E \
f
B∈ thì ,
E∈ và do đó
( in f
)
( in f
)
) ( lm f ( ) (theo mệnh đề 2.2.2(iii) ). Vô lí. Vậy phải có in f
=
) I
f
Nếu
I∈ sao cho
( in g
).
( in f
)
hơn xét 2.2.3(i) tìm được g Vì g có từ khởi đầu thực sự bé ( ( ). ∈ lm f in I ∈ ⊆ và E Theo nhận E∉ nên
− ∈
<
h
= :
f
g R E
\
.
29
( ) lm h
( lm f
),
E R=
,
Mặt khác theo mệnh đề 2.2.2(iii) lại có trái với
.f Suy ra phải có
.R I ■
/
≠
cách chọn tức B là hệ sinh của
I
.
/ R I
B≅
( ) in I
Như vậy, mặc dù nhưng chúng chung phần bù để lấy tổng Vậy
.R Ta có ngay hệ quả:
/R in I hữu hạn chiều,
=
R I
.
trực tiếp bằng
( dim /
( ) R in I
/R I và ( dim /
( ) )
thì không gian kia cũng hữu hạn chiều và Hệ quả 2.2.7: Nếu một trong hai không gian vector )
s ∈ kí hiệu ,
sR≤ là tập các đa thức trong J bậc nhỏ
Cho J là ideal của
.s Ta có:
.R Với mỗi sJ ≤ là tập các đa thức trong J bậc nhỏ hơn hoặc bằng
hơn hay bằng s và
R⊆ và ≤ là một thứ tự từ trên
.R Khi đó:
Định lí 2.2.7: Cho ideal I
s ∈ thì ,
=
dim
/
I
dim
/
.
(
)
R ≤
≤
R ≤
( ) in I ≤
(
)
K
s
s
s
(
)
≤
s
Nếu ≤ là một thứ tự từ phân bậc và
Chứng minh:
in I
( ).
sB≤ là tập tất cả đơn thức bậc không quá s và nằm ngoài
,
B R I , ,
Kí hiệu Khi đó với
,B R S thay bằng
≤
≤
s
s
I
một thay đổi nhỏ -
.
≤ Mặt s
cho phép ta khẳng định
/s .
/
R ≤
≤ - chứng minh của định lí trên cũng s sB≤ là hệ đại diện cơ sở của không gian vector R ≤ ) ( ) in I ≤
(
sB≤ là hệ đại diện cơ sở của không gian vector
s
≤
s
khác, rõ ràng Từ đó ta
có đẳng thức cần chứng minh. ■
30
§3: CƠ SỞ GRöBNER
f 1,...,
=
Như đã nói tới trong lời mở đầu, việc thực hiện chia một đa thức nhiều biến f cho một f có thể thực hiện theo nhiều cách khác nhau và dẫn tới việc có hệ các đơn thức s
I
f
1,..., f
s
g
g theo cách nào thì đa thức dư là duy
thể có các đa thức dư khác nhau. Vì vậy việc kiểm tra một đa thức f cho trước có thuộc gặp nhiều khó khăn. Vấn đề đặt ra ở đây là có một hệ sinh phù
1,..., g
g của I sao cho dù chia f cho 1,...,
t
t
hợp
g
.R Tập hữu hạn các I∈ được gọi là một cơ sở Gröbner của I đối với thứ tự
s
g 1,...,
nhất. Hệ sinh như thế sẽ được thấy trong tiết này và được gọi là cơ sở Gröbner và được định nghĩa như sau:
=
.
)
( ) in I ≤
( in g ≤
( in g ≤
s
) 1 ,...,
g
I∈ được gọi là một cơ sở Gröbner, nếu nó là cơ sở Gröbner của ideal
Định nghĩa 2.3.1: Cho ≤ là một thứ tự từ và I là một ideal của đa thức khác không ≤ nếu
g 1,...,
s
Tập
sinh bởi chính các phần tử này.
.R Nếu
Với định nghĩa như trên, các từ khởi đầu của cơ sở Gröbner của I sinh ra ideal khởi .I Vậy tương ứng cơ sở Gröbner có sinh ra ideal I ? Để trả lời câu hỏi đó ta xét đầu mệnh đề sau:
g 1,...,
g là cơ sở Gröbner của I s
Mệnh đề 2.3.2: Cho I là một ideal tùy ý của
.I
1,..., g
g là cơ sở của s
đối với một thứ tự từ nào đó, thì
⊆
⊆
=
=
⊆ Vì
Chứng minh:
,
J
g
I
.
( in g
)
( in J
)
( ) in I
( in g
s
) 1 ,...,
s
=
nên
( ) in I J= ■ .
I
in I
)
g 1,..., ( ).
.I
Theo mệnh đề 2.2.4, Đặt ( in J
>
=
> > ...
.
,...,
Ngược lại, một cơ sở của I thì có thể không là cơ sở Gröbner của
x 1
x 7
=
−
x 7 −
=
=
=
f
g
g
f
.
I
f g ,
Ví dụ: Xét Lấy
x 2 Lấy
(
)
)
in <
x x 1 4
x x 2 3
[ R K x 1 = x x 4 7
] x x 5 6
x x in , < 1 4
x x 4 7
l
ex
l
ex
và . Khi đó . và thứ tự từ điển phân bậc với (
−
=
−
=
I
,
∈ nhưng
in <
x g 1
x x x 1 5 6
x x x 2 3 7
l
ex
( ) h ∉
g
f
,
31
x x x 1 5 6 (
)
)
(
in <
in <
in <
in <
in <
ex
ex
ex
l
l
l
exl
exl
≠
f
g
,
.
, vì thế .Do đó
g (
( ) ( h },f g là cơ sở của I nhưng không là
in <
in <
l
l
ex
ex
ex
l
in < .I
) cơ sở Gröbner của Như vậy việc xác định ideal khởi đầu tương đương với việc tìm một cơ sở Gröbner của I (đối với một thứ tự từ nào đó). Tuy nhiên việc này không đơn giản vì không phải mọi cơ sở của I là cơ sở Gröbner của .I Hơn nữa, một cơ sở đã cho của I có thể là cơ sở Gröbner đối với thứ tự này, nhưng không là cơ sở Gröbner với thứ tự khác.
3
I
xy
=
=
−
,
vaø
xy f ,
xy y ,
.
x
.
3 y Cho
y> Khi đó
f 1
2
f
xy
=
,
) hay ( Khi đó { },f g không là cơ sở Gröbner của I với thứ tự từ điển phân bậc. Thật vậy, đa = x f h thức không chia hết cho 7 ) ( ) f ( ) I Hay nói cách khác {
lex
lex
in ≤
in ≤=
2
f 1
1
(
xy
I
=
.
,
không phải là cở sở Gröbner của I đối với thứ Ví dụ: Cho )
glex
rlex
⊆ nên { in ≤
in ≤
in ≤=
f 1
l ex
f 1
(
)
(
)
3
I
y
f
f
=
= nên
tự
f là cở sở Gröbner của
2,f
1
rlex
glex
rlex
in ≤=
in ≤
in ≤=
in ≤
lg ex
2
2
= ) ex , vì )
( l≤ (
K x y } f 2;f ( ) I = Tuy nhiên ( ) ( ) I I I đối với thứ tự từ điển phân bậc, cũng như đối với thứ tự từ điển ngược.
và từ điển ) (
Khi cố định một thứ tự từ thì cơ sở Gröbner không xác định duy nhất, bởi vì khi thêm một số phần tử vào cơ sở Gröbner đã biết, thì sẽ được một cơ sở Gröbner mới. Bởi vậy ta có khái niệm sau:
Định nghĩa 2.3.3: Cơ sở Gröbner tối tiểu của I đối với một thứ tự từ đã cho là một cơ sở Gröbner G I⊂ thỏa mãn các tính chất sau:
g G∈ .
lc g = với mọi
) 1
(
'g G∈ để
(i)
'
|
( in g
)
( in g .
)
(ii) Với mọi g G∈ không tồn tại
Vì mỗi ideal đơn thức chỉ có duy nhất một tập sinh đơn thức tối tiểu, nên ta có hệ quả sau:
Hệ quả 2.3.4: Cho ≤ là một thứ tự từ. Khi đó mọi ideal đều có cơ sở Gröbner tối tiểu và mọi cơ sở Gröbner tối tiểu của cùng một ideal đều có chung số lượng phần tử và chung tập từ khởi đầu.
32
I
=
,
xy y ,
Nhưng cơ sở Gröbner tối tiểu vẫn không là duy nhất.
K x y ⊆
trong ví dụ nêu trên và thứ
3
3
y
+
( =
axy a K ,
.
Ví dụ: Chẳng hạn xét ideal đơn thức
∈ và
glex≤
f 1
)3 xy f = − 2,
,xy y là cở sở .I Như vậy, ngay trong trường hợp đơn giản này, I có vô số cơ
tự từ điển phân bậc Khi đó
Gröbner tối tiểu của sở Gröbner tối tiểu nếu K vô hạn.
Thay đổi định nghĩa một chút, ta sẽ được một cơ sở Gröbner xác định duy nhất.
g G∈ .
Định nghĩa 2.3.5: Cơ sở Gröbner rút gọn của ideal I đối với một thứ tự từ đã cho là một cơ sở Gröbner G của I thỏa mãn các tính chất sau:
lc g = với mọi
) 1
(
∈
(i)
\
'
|
{ } g G g
)' in g m .
(
để (ii) Với mọi g G∈ và mọi từ m của g không tồn tại
0.
I ≠
Rõ ràng mọi cơ sở Gröbner rút gọn là cơ sở Gröbner tối tiểu. Kết quả sau đây nói rằng cơ sở Gröbner rút gọn tồn tại và duy nhất.
Khi đó đối với mỗi thứ tự từ, I có duy nhất một cơ sở
Mệnh đề 2.3.6: Cho Gröbner rút gọn.
.I Ta nói ,g trừ từ khởi đầu của nó, chia
=
∈ f G
|
Chứng minh:
( in G
)
)
{ ( in f sao cho cuối cùng sẽ nhận được cơ sở Gröbner mà mọi phần tử của nó đều rút gọn.
hết cho các từ khởi đầu trong Mục đích của ta là thay đổi G Trước hết ta chứng minh sự tồn tại. Cho G là cơ sở Gröbner tối tiểu của rằng g G∈ rút gọn trong G nếu không có từ nào của } .
Nhận xét rằng nếu g rút gọn trong G thì g cũng rút gọn trong mọi cơ sở Gröbner tối ,G 'G chứa g của I (bởi vì định nghĩa chỉ liên quan đến các từ khởi đầu trong
'G có chung tập các từ khởi đầu).
tiểu trong khi G và
∈
∈
≠
K m M
,
0
)
>
≥
a= −
Giả là một phần tử không rút gọn trong
.G Chọn từ ≠ ∈ để ' g G g nên theo bổ đề 2.2.2(iii),
m in g
.
in g m Đặt |
g
( in g
)' ,
) ' .
(
)
≠ (
g 1
Vì lớn nhất của g sao cho tồn tại ( mg in g '/ sử g G∈ )( ( a a m in g )'
=
∪
=
=
33
.
)
( in g
)
)
( lm g
(
) { } G g \
G 1
( in g 1
Do đó
),
<
nữa, nếu kí hiệu đơn thức m xác định như trên là
.
)
)
( s g
1g không rút gọn. Nếu
( s g 1
),
<
'
(
( s g là đơn thức trong
<
) <
≤
)1 Tóm lại luôn có
.
/
.
'
'
'/ )
)
)
)
{ } g lại là cơ sở Gröbner tối tiểu. Hơn 1 ( 1g rút gọn trong 1G s g thì hoặc )1 ( s g là đơn thức của g hoặc chia hết cho từ khởi đầu *g G∈ nào đó, thì từ đó không thể là ( s g vì từ này đã bị ) ( . s g ( = m s g
( triệt tiêu. Cho nên s g 1 ( ) ( s g m in g
Thật vậy, giả sử
( s g 1
( s g 1
) mg in g thì cũng có ( ) ( s g Chú ý rằng s g sẽ không xác định nếu không tồn tại m như trên. Tiếp tục làm như vậy, theo các bổ đề
=
∪
Nếu )
{ } g
) { } G g \
(
G s
s
mà không 1.1.13 và 1.1.14, đến một lúc nào đó phải nhận được
), ( s g tức
sg rút gọn trong
.sG
,G thì cuối cùng sẽ 'G tối tiểu mà mọi phần tử của nó đều rút gọn (vì trong quá 'G chính là cơ sở
còn
(
=
'
)' . h
g
g
'
Nếu lặp lại quá trình trên với tất cả các phần tử không rút gọn của nhận được cơ sở Gröbner trình đó, mọi phần tử đã rút gọn được giữ nguyên).Theo định nghĩa Gröbner rút gọn.
) = in G in G )' .
=
≠
'G là hai cơ sở Gröbner rút gọn. Theo Cho g G∈ tùy ý. Khi ( = − ∈ Ta có ( I . in g ,g hoặc là một từ của
đó chọn được Đặt
in h hoặc là một từ của
( ) in g ( )
( in g
)
in g Theo định nghĩa của cơ sở Gröbner,
)' . ).
( )
.
Nếu
( ) in h ',g nhưng khác ( in g
)*
in h chia hết cho một từ g G∈ Nhưng điều này mâu thuẫn với điều kiện (ii) của định = ∈ ' g G
g
'.
đầu Bây giờ ta chứng tỏ tính duy nhất. Giả sử G và hệ quả 2.2.3 G và 'G có cùng số phần tử và g G∈ sao cho ' ( h ≠ thì 0 in g ( nào đó, với *
G G⊆
'.
h = và 0
G
'
G⊆ nên ,
nghĩa cơ sở Gröbner rút gọn. Suy ra Tương tự Tức là
G G=
'.
■ cũng có
34
§4: VAI TRÒ CỦA CƠ SỞ GRöBNER TRONG VIỆC XÁC ĐỊNH PHẦN TỬ CỦA IDEAL
} f hay không, s
+ + ...
r
.
f 1,..., + Trong đó r được hiểu như là dư
q f 1 1
q f s
s
f
}
f 1,...,
s
⊂ =
=
,...,
,...,
.
x
f
f
. Điều này có thể thực hiện được nhờ kết quả sau: Để xác định một đa thức f có thuộc một ideal I sinh bởi một hệ { = ta phải biểu diễn f dưới dạng f khi chia f cho {
R∈ có thể viết dưới dạng
}
{
]
[ R K x 1
1
n
s
=
+
+ + ...
, 2.3
f
r
(
)
q f 1 1
q f s
s
Định lí 2.4.1: (Định lí chia đa thức) Cố định một thứ tự từ ≤ trên M và cho Khi đó mọi đa thức f F
,iq r R∈ thỏa các điều kiện sau đây:
0,
≤
.
Trong đó
r = ( in f
( ) in r
( in f
).
s
≤
=
i
s 1,..., .
Hơn nữa hoặc không có từ nào của r chia hết cho một trong các từ khởi đầu ) (i) Hoặc ( ) in f 1 ,...,
( in q f
)
( in f
),
i
i
iq ≠ thì 0
f và đa thức r gọi là s
f 1,...,
=
(ii) Nếu
Re m
r
f
.
)2.3 gọi là biểu diễn chính tắc của f theo )
(
F
Vế phải của ( đa thức dư của f khi chia cho F và kí hiệu
=
Chứng minh:
f= và
I
.
,I đặt r
( in f
)
s
) 1 ,...,
=
=
...
0
q
( in f = ta có biểu diễn chính tắc của
.f
q 1
s
Đặt Nếu không có từ nào của f thuộc vào
u ≠ của f thuộc
0
,I và gọi
.
Giả sử có một từ
.I Lấy
i
= w u 0
0 /
0u chia cho
0u là từ lớn nhất với thứ tự từ đã cho ( ( in f in f
)0
)0i
=
+
f
0
h 1,
− 1 ' c c w f 0 i 0
i 0
Ta viết lại: và trong những từ u thuộc
'
35
.if
( in f
)0i
0
=
=
<
u
.
0ic là hệ số của ( in f
)
0
0
0c là hệ số của ( in w f 0
0u trong f và )
( w in f
)
i 0
i 0
=
0
f
trong đó trong Ta có:
+ là h 1
h = hoặc 0 1
h ≠ mà không có từ nào của 1
− 1 ' c c w f 0 i 0 0
i 0
Nếu
1h thuộc I thì .f
f 1,...,
f và 1h là đa thức dư của s
biểu diễn chính tắc của f theo
=
>
u
Nếu một từ của 1h thuộc I và nếu
u
u
.I Ta có
1h thuộc
u> 1.
0
1h mà
0
( in w f 0 i
(
0u ). Hơn nữa,
1u là từ lớn nhất với thứ tự từ đã cho trong những từ )0 ) 0u không thể là một
của Thật vậy, nếu một từ u của
=
.
thì u là một từ của f (mâu thuẫn với cách chọn từ của 1.h
1
i
1u
( 1 / w u in f
)1
=
+
f
)1i + h 2,
( in f − 1 ' c c w f i 1 1 1
i 1
− 1 ' c c w f i 0 0 0
i 0
'
Lấy và Ta có: chia cho
1h và
.if
( in f
)1i
1
1ic là hệ số của
≤
<
.
( in f
)
1c là hệ số của ( in w f 1
)
1u trong ) ( in w f 0
i 0
i 1
trong Ta có: trong đó
>
>
u
u
> ...
0
u 1
2
Tiếp tục quá trình như trên, ta được dãy giảm:
n
− 1
=
+
f
,
t
h n
− 1 ' c c w f t i t
i t
∑
=
t
0
0
Vì R là vành Noether nên dãy trên sẽ dừng sau hữu hạn bước, giả sử là n bước, ta có một biểu diễn:
,I và
nh = hoặc 0
nh ≠ mà không có từ nào của
nh thuộc
≤
< < ...
.
( in f
)
t
( in w f
)
( in w f 0
)
i t
i 0
trong đó
− 1
s
s
n
=
f
r
r
h=
36
i
t
i
,n
− 1 ' c c w f t i t
i t
+∑ q f i
=∑ q f i
∑
i
= 1
i
= 1
0
= t thỏa điều kiện (i) và (ii) như mong muốn. ■
2
=
=
−
=
,
,
Vì vậy, đặt và ta đạt được một biểu diễn
x
> > Xét z .
y
x
z f ,
xy
− 1
f 1
2
3
=
−
−
Ví dụ: Xét vành với thứ tự từ điển
f
x
2 x y
x
] [ R K x y x 2 1. − Ta có:
3
2
2
=
−
−
+
−
−
−
f
x
2 x y
x
− = 1
z
x
1
2
2
−
−
+
) −
+
+
−
=
2 x y
x
xz
( x f 1 − = 1
z
x
1
xf 1
xf 1
2
2 x y ( y f 1 −
+
−
+
−
+
−
−
=
−
x
xz
yz
− = 1
z
xz
yz
1
) − ( −
xz )
xf 1
yf 1
f 1
=
−
+
−
yz
− − z
1
=
+
−
yf 1 yf 1 − − y
xz
yz
− − z
xf 1 xf 1 ( x
− ) 1
xz (
) 1
f 1 f 1
và
3
2
2
=
−
−
+
−
−
−
f
x
2 x y
x
− = 1
z
1
2
2
−
−
+
) −
=
−
2 x y
x
xz
( x f 1 − = 1
x
xz
1
xf 1
xf 1
2
2
=
−
−
+
− − =
−
+
+
x
1
x
z
xf
xz
− − x
1
+ )
x ) + − 1 (
2
xf 1
f 1
2
=
−
−
− − −
+
x
xf
xz
x
z
xf ) 1
xz (
xf 1 (
2 x y ( x f − ) 1
f 1
2
−
Và:
− − và 1
xz
yz
z
xz
− − − là đa 1
x
z
,f 1
f và 2
.f
là một biểu diễn chính tắc của f theo
f
thức dư của
}
s
2
2
2
f 1,..., +
=
+
=
+
=
với một cách chia nào đó thì đa thức dư có thể
2 x y
xf
x
f
2 x y
xy
x
,
2
f 1
2
2
2
+
=
−
∈
x
f
y
ta có hay
f
f
,
yf 1
f là 2
f 1
2
2
2
=
−
≠ Như vậy hệ sinh
,f 1 I∈ thì đa thức
y
x
0.
f cần thỏa điều kiện nào để f s
, y f ) f 1,...,
r dư r chỉ duy nhất bằng 0?. Mệnh đề sau trả lời câu hỏi đó:
tức đa thức dư của f khi chia cho nhưng Ví dụ trên cho ta thấy đa thức dư trong thuật toán chia nói chung là không duy nhất. Vậy với các cách chia khác nhau thì đa thức dư khác nhau. Hơn nữa, một đa thức thuộc một ideal sinh bởi hệ { không bằng 0. Cho = (
=
f
f
F
37
{
1,..., f
} s ,
Mệnh đề 2.4.2: Giả sử
là một cơ sở Gröbner đối với một thứ tự từ cho R∈ đa thức dư r của phép chia f cho hệ F (trong trước. Khi đó với mỗi đa thức định lí chia đa thức) được xác định duy nhất. Nói riêng, kết quả thực hiện thuật toán chia đa thức trong trường hợp này không phụ thuộc vào thứ tự các đa thức chia trong .F
q
,...,
'
Chứng minh:
R∈ để
q q , s
' ,..., 1
q 1
s
=
+
f
+ + ...
+ = r
+ + ...
r
'.
q f s
s
q f ' s
s
q f 1 1
q f ' 1
1
Sự tồn tại của r được đảm bảo bởi định lí chia đa thức. Giả sử có hai đa thức dư r và ',r tức là tồn tại
−
=
−
−
r
r
'
q
+ + ...
q
'
q
f
∈ = I :
,...,
f
.
(
)
(
s
s
s
s
' 1
) q f 1 1
f 1
f
Khi đó:
s≤ để
r−
)'
( in r
1,...,
chia hết cho Vì
). i ',r
r−
f là cơ sở Gröbner của I nên tồn tại i s )'
( in r
Nhưng điều đó không thể xảy ra nếu
( in f phải là một đơn thức của r hoặc ).
( in f
'r chia hết cho
i
Vậy mà theo định lí chia đa thức, không có từ nào của r và
r
r=
'.
=
F
f
f
phải có ■
{
}
s
1,...,
Như vậy, khi là cơ sở Gröbner thì đa thức dư sẽ duy nhất, khi đó cho ta
=
F
f
f
ngay một điều kiện cần và đủ để một đa thức thuộc một ideal:
{
}
1,..., f
s .
R∈ Khi đó f
Hệ quả 2.4.3: Giả sử
là một cơ sở Gröbner của ideal I đối với một thứ I∈ khi và chỉ khi đa thức r của phép
f
.
=
+ + ...
0.
f
+ Do tính duy nhất của phần dư, suy ra
R∈ để
I∈ Khi đó tồn tại r = ■ 0.
tự từ cho trước và đa thức chia f cho hệ F bằng 0.
q f 1 1
q s
s
Chứng minh: Chỉ cần chứng minh điều kiện cần. Giả sử q f q 1,..., s
=
F
f
38
{
}
s
=
Ta có khi là một cơ sở Gröbner thì đa thức dư r xác định duy nhất.
F
'
,...,
f
' f 1
' s
}
f 1,..., { Ta có mệnh đề sau:
=
∈
Re m
f
f
,
'G là hai cơ sở Gröbner của I đối với cùng một thứ tự từ. tức là đa thức dư của f không phụ Re m
)
)
(
G
G
'
Vậy nếu thay là một cơ sở Gröbner khác thì đa thức dư r có thay đổi.
Mệnh đề 2.4.4: Cho G và [ ] ( Cho tùy ý. Khi đó f K x thuộc vào việc chọn cơ sở Gröbner.
=
G
g
Chứng minh:
{
}
1,..., g
s
=
G
'
}
n
=
r
f
{ Re m
g (
' ,..., g' 1 )
G
=
f
+ ⇒ − = f
r
r
+ + ...
+ + ...
Giả sử
q g s
s
q g s
s
q g 1 1
q g 1 1
⇒ − ∈ = r
I
f
g
⇒ − = f
r
+ + ...
'
q g ' n
n
q g ' 1
' 1
+
⇒ = f
r
' ,..., g' 1 + + ...
.
'
n q g ' n
n
q g ' 1
' 1
(
) in g nên s
=
=
,...,
'
Tacó:
( in g
)
)
n
s
( in g 1
' 1
,...,
các từ của r không thuộc Vì các từ của r không chia hết cho một trong các từ khởi đầu ) ( ) in I
) ( 1 ,..., in g ( ) in g ( in g
,..., )
( in g ( in g
1'
=
.Như vậy từ của r cũng không chia hết một trong các từ khởi đầu
r
f
(
)
Re mG
'
Vậy các . ) 'n hay đa thức dư của f không phụ thuộc vào cơ sở Gröbner.■
39
§5: THUẬT TOÁN BUCHBERGER
f
}
1,..., f
n
là cơ sở Gröbner, ta sẽ dùng
Ta đã thấy được vai trò của cơ sở Gröbner trong việc xác định phần tử của một ideal. Vậy thì tiêu chuẩn nào để biết một hệ sinh { thuật toán Buchberger để tìm cơ sở Gröbner từ một hệ sinh cho trước. Trước hết, ta đưa ra khái niệm S − đa thức:
[ ] ,f g K x∈
=
=
m
m
Định nghĩa 2.5.1: Cho là hai đa thức khác 0. Kí hiệu
fg
gf
,
,
) )
( lm g
)
) )
( lm g
)
( in f ( ( UCLN lm f
)
( in g ( ( UCLN lm f
) .
=
− m f m g
,
.
.
.
S − đa thức của f và g là đa thức
( S f g
)
gf
fg
và
3
2
4
5
5
=
−
+
=
−
+
Chú ý rằng S − đa thức phụ thuộc vào việc chọn thứ tự từ.
g
2 x y
x
xy
f
5 x y
3 x y
2 x y
3
2
3
4
2
K x y , .
[
]
3
=
=
m
3 x m ,
3
y
và trong vành Ví dụ: Cho
y> ta có
gf
fg
3
2
3
4
5
5
3
=
−
+
−
−
+
y
5 x y
3 x y
2 x y
x
2 x y
x
xy
,
3
4
2
3
2
3
)
( S f g
)
5
6
8
5
−
−
+
+
3 x y
x
2 x y
( 4 x y
= 3
12
2
) 6
( .
và Với thứ tự từ điển phân bậc mà x
y> ta có
m
y m= ,
= − và 2
gf
fg
3
5
4
5
2
= −
−
+
−
+
+
−
5 x y
3 x y
2 x y
y
x
2 x y
xy
,
4
2
2
3
3
2
( S f g
)
)
3
5
2
6
=
−
−
8
3
2 x y
4
2 x y
( 3 x y
) − 3
xy
( .
Với thứ tự từ điển mà x
Từ định nghĩa thấy ngay S − đa thức thỏa mãn các tính chất sau:
= −
Mệnh đề 2.5.2:
,
,
.
( S f g
)
( S g f
)
<
,
,
.
(i)
( in S f g
)
)
( in g
)
(
)
( ( BCNN in f
)
(ii)
40
( in f
( ) in g
Mệnh đề 2.5.3: Cho và
,
,f g là những đa thức khác không và nếu (
S f g cho hệ { )
) },f g bằng 0.
nguyên tố cùng nhau thì dư trong phép chia
in g nguyên tố cùng nhau thì
)
( in f
)
(
=
−
= −
−
+
,
f
g
.
)
( S f g
)
)
( in f
)
=
=
) −
=
( sm
và Chứng minh: Nếu
sm lm g
f )
( ( in f
)
(
),
( ) in f g ) ) ( − lm g in g
( ) in g f (
gsm
f
f
( g in g ( lm f do tính nguyên tố cùng nhau sẽ suy ra
lm g Điều này vô lí, vì
( sm lm f g ). (
− ). gsm chia hết cho
<
Đặt và Nếu thì
( lm g
).
gsm
−
=
max
g
f
,
,
,
Do đó ở đẳng thức trên phải có
( lm S f g
)
( in f
)
)
(
)
( lm f
(
} ) ) S f g cho G mà phần dư của nó bằng 0. ■
{ ( − lm g in g ,
(
)
tức là có một phép chia
n
Bổ đề kĩ thuật sau đây đóng vai trò then chốt trong việc chứng minh định lí tiêu chuẩn Buchberger tiếp theo
,...,
∈ và K
[ ] ∈ g K x
1,..., a
a ∈ thỏa mãn các tính chất t
g 1
1
t
a a ; ,..., t
Bổ đề 2.5.4: Cho
d
n
x=
.
sau:
t≤ mà
( ia x lm g
)
i
ia ≠ thì 0
t
d
<
in
a x g i
x
.
(i) Tồn tại
i
∑
i
a i = 1
d ∈ để với mọi i )
(ii)
(
jk Ka ∈ sao cho
t
d c
jk
=
,
,
a x g i
a − x
a i
i
jk
k
( S g g j
)
∑
∑
= 1
i
, j k
jkc
=
x
,
.
Khi đó tồn tại
( lm g
)
j
k
)
( ( BCNN lm g
)
− d c
d
jk
<
,
.
x
,j k đều có
Trong đó
k
( S g g j
)
( in x
)
Hơn nữa với mọi
jkc ta có
Chứng minh: Theo mệnh đề 2.5.2 và định nghĩa của
− d c
− d c
d
jk
jk
<
=
,
x
,
x
.
( lm g
)
k
j
k
)
( S g g j
)
( ( BCNN lm g
)
( in x
)
t
41
.
i
=∑
a x ga i i 1
i
=
Vì vậy chỉ còn phải chứng minh sự tồn tại của biểu diễn trên cho tổng
.
( lc g
)
β = i
i
p i
ia x g β / i i
và Đặt
ip có hệ số đầu là 1. Viết tổng cần xét dưới dạng :
t
t
=
a x g i
i
p i
i
=
−
+
−
+
∑ a i = 1
...
1 1
p 2
+
2 −
p 1 + + ...
)
)(
− 1
aβ t t
p t
−
=
+
...
) + + ... )
p 2
1 1
p 3 ( aβ 1 1 − p 2
p 3
2 −
p 1 + + ...
+
)(
∑ aβ i i = 1 i ( aβ 1 1 ( aβ 1 1 ( aβ 1 1 ( aβ 1 1
)( ( ) aβ aβ + p 2 2 ) + a β p p − − 1 1 t t t t )( ) ( + + aβ aβ 2 ) a β− p . t
p t
− 1
− 1
1
t
t
Đương nhiên các đa thức
t
0.
i
=∑ aβ i
i
= 1
ib
+
=
.ib
x=
Trong đẳng thức cuối cùng ta đã sử dụng đồng nhất thức sau đây được suy ra ngay từ điều kiện (ii):
i
t≤ Do đó
.
( in g
)
)
( lm g
i
i
xβ= i
b i
−
jkc
jk
=
,
x
Giả sử với mọi
d cx
.dx
.dx
( lm g
)
j
k
a Theo điều kiện (i): i )
( ( BCNN lm g
d )
Suy ra chia hết Vì vậy là đơn chia hết
thức. Ta có:
j
− d c
− d c
k
jk
jk
=
−
,
x
x
g
g
k
j
k
( S g g j
)
( lm g
)
( lm g
)
j
k
j
k
) ) ,
) ) ,
( in g ( ( UCLN lm g
)
( in g ( ( UCLN lm g
)
− d c
jk
=
−
x
g
g
,
( lm g
)
j
k
j
k
)
( ( BCNN lm g
)
β j ( lm g
)
k
j
β k ( lm g
)
d
d
=
−
g
g
β k
j
β j
k
j
x b x k
x b x
j
j
k
−
=
β k
β j
a x g β j
a x g k β k
=
−
p
p
.
ββ j k
j
k
(
)
42
p −−
p i
i
1
t
)
− d c
− d c
1 1
2
23
12
=
+
+
,
,
...
a x g i
x
x
)
)
a i
i
( S g g 1
2
( S g g 2
3
∑
i
= 1
( aβ aβ + 2 ββ 2 3
+
)
t
t
− d c (
) − 1
aβ 1 1 ββ 1 2 ( aβ 1 1
a β − − t t 1 1
+
,
.
x
g
( S g
)
t
t
− 1
+ .... β β − t t 1
=
−
≤
Thay vào biểu diễn ở trên ta được:
j k ,
i
1,
i
,
i
t
).
)
(
)
■ Đó là dạng biểu diễn cần tìm (thực ra chỉ cần tới các cặp (
t
Một cách phát biểu khác của bổ đề trên là: nếu hai điều kiện (i) và (ii) thỏa mãn thì
,
.
a x ga i i
i
k
( S g g j
)
∑
= 1
i
tổng thuộc ideal sinh bởi
.I
=
G
g
Sử dụng khái niệm S − đa thức, ta nhận được tiêu chuẩn sau đây để một hệ sinh là cơ sở Gröbner của
.I G
}
{
s
1,..., g ≤ ≠ ≤ một (hoặc mọi) đa thức
j
s
,i
j
Định lí 2.5.5 (tiêu chuẩn Buchberger): Cho là hệ sinh của ideal
( S g g trong phép chia cho G bằng 0.
là cơ sở Gröbner của I khi và chỉ khi với mọi cặp 1 i ) dư của S − đa thức
Chứng minh:
43
I∈ nên ,
,
.
I∈ Vì G là cơ sở Gröbner theo hệ quả
g g , i
j
j
Điều kiện cần: Do
,i
j
( S g g i ( S g g trong phép chia cho G xác định duy nhất
) )
2.4.3, đa thức dư của S − đa thức
≤ ≠ ≤ một đa thức dư của
và bằng 0.
s
i
j
,
,i
j
( S g g trong phép
)
Điều kiện đủ: Giả sử mọi cặp 1
f
∈ = I
g
.
chia cho G bằng 0 (đa thức dư này được chọn duy nhất theo một quy luật nào đó). Ta chỉ cần chứng minh rằng trong trường hợp này G là cơ sở Gröbner.
(
)
[ ] K x∈
s
g 1,...,
h 1,...,
h s
=
+ + ...
. 2.3
f
(
)
h g 1 1
h g s
s
Cho Khi đó tồn tại sao cho
,f
chọn biểu diễn sao cho
max
,...,
( lm h g
)
s
s
{ ( lm h g 1 1
nhỏ nhất. Đơn thức này hoàn toàn xác định vì thứ tự từ là
.d
Để không làm rắc rối thêm kí hiệu, ta giả sử biểu diễn Trong tất cả những biểu diễn như trên của } ) m x=
max
,...,
m= .
( lm h g
)
} )
{ ( lm h g 1 1
s
s
=
m lm h g
thứ tự tốt. Kí hiệu nó là (2.3) thỏa mãn
m< .
(
).
( lm f
)
i
i
i
ih g triệt tiêu nhau. Đặt i
Giả sử Khi đó các từ lớn nhất của
=
+
f
h g i
i
h g i
i
∑
∑
< m m i
= m m i
=
+
−
+
g
. 2.4
)
(
)
(
)
( ) in h g i
i
h i
( in h i
i
h g i
i
∑
∑
∑
= m m i
= m m i
< m m i
Tách các từ cao nhất ra để vận dụng bổ đề trên như sau:
m<
,
( in f
)
<
Vì mỗi hạng tử trong tổng riêng thứ hai và thứ ba ở (2.4) có các từ khởi đầu nhỏ hơn m và nên phải có
in
m
( ) in h g i
i
∑
= m m i
( xem mệnh đề 2.2.2)
Từ bổ đề 2.5.4 suy ra
=
,
, 2.5
(
)
( ) in h g i
i
jk
j
k
( T S g g
)
∑
∑
j k ,
= m m i
44
jkT là các từ sao cho
,
. 2.6
m<
(
)
jk
j
k
)
( ( in T S g g
)
Trong đó
,j
k
( S g g trong phép chia cho G là không, nên có thể
)
Theo giả thiết đa thức dư của
s
,
, 2.7
)
(
k
p g ijk
i
)
( S g g j
= ∑
i
= 1
≤
,
. 2.8
viết
(
)
[ ] K x∈
ijk
i
j
k
ijkp
( in p g
)
)
( ( in S g g
)
sao cho Trong đó
s
s
=
=
g
.
( ) in h g i
i
jk
p g ijk
i
T p jk
ijk
i
∑
∑ ∑ T
= 1
= 1
, j k
i
, j k
i
= m m i
∑ ∑
Thay (2.7) vào (2.5) ta được
s
s
=
+
−
+
f
g
= :
)
( 2.9
)
(
)
h g i
i
h i
( in h i
i
h g i
i
h g ' i
i
∑
∑
∑
∑
i
i
= 1
= 1
< m m i
= m m i
Do đó, từ (2.4) suy ra
.
h i
T p jk
ijk
= ∑
j k ,
Trong đó
≤
=
<
,
,
m .
i
i
jk
j
k
jk
j
k
)
)
( in h g
)
{ ( ( T in S g g
} )
{ ( ( in T S g g
} )
max j k ,
max j k ,
Chú ý rằng mệnh đề 2.2.2, (2.6) và (2.8) dẫn đến
max
,...,
'
m< .
( lm h g
)
} )
{ ( lm h g 1
' 1
s
s
Cùng với điều đó và mệnh đề 2.2.2, (2.9) cho ta một biểu diễn mới của f mà
.m Vậy phải có
45
m= .
( lm f
)
=
=
∈
Do đó tồn tại i để
.
),
( lm f
)
( in g
)
( in f
)
( in g
i
i
i
) 1 ,...,
s
( ( lm h g G là cơ sở Gröbner của
) ( lm h lm g i .I ■
hay Theo định nghĩa, Điều này mâu thuẫn với cách chọn )
=
= −
g
Sau đây là một số chú ý để giảm bớt số phép thử khi áp dụng tiêu chuẩn Buchberger:
,
,
{
}
)
( S g f
( S f g
s
j<
i
.
) G nên để thử xem Gröbner hay không, chỉ cần thử cho các cặp (
,f g là hai từ thì
g 1,..., ) g g với ,i j S f g = Do đó không cần thử tiêu chuẩn Buchberger
0.
,
có phải là cơ sở • Vì
(
)
• Nếu
cho các cặp từ.
4
−
−
• Không cần thử tiêu chuẩn Buchberger cho các cặp có từ khởi đầu nguyên tố
= và
I
x
z
3 y z y ,
y
x
)
( in x
)3
4
−
−
−
Ví dụ: Cho Đối với thứ tự từ điển ta có cùng nhau. ( =
3 y z y ,
x
z
z
y
. = nguyên tố cùng nhau. Theo chú ý trên, tập {
− }
( in y
)4
đã là cơ sở
.I
Gröbner của
4
3
3
4
3
4
−
+
= −
−
+
+
−
+
= −
+
S
3 y z
+ − , x
z
z
3 y z
x
y
z
xz
y
y
y
(
)
(
)
(
)
4
+
Tuy nhiên đối với thứ tự từ điển phân bậc thì
G
3 y z
+ − x ,
z
y
{ = −
}
.I
Không thể chia hết cho được, tức có đa thức dư khác không.
Vậy G không là cơ sở Gröbner của
Tiêu chuẩn Buchberger cho ta một thuật toán để tính cơ sở Gröbner từ một hệ sinh của một ideal.
f
Thuật toán Buchberger
.R Tính những S − đa thức
,
f
.
}
f 1,...,
n
i
j
( S f
)
f
f
là một hệ sinh của ideal I của Lấy {
}
f 1,...,
n
,i
j
( S f
)
f
cho hệ {
f
}
n
f 1,...,
,i
j
)
là một cơ sở Gröbner. Nếu một trong những Nếu tất cả dư trong phép chia Buchberger, {
n
1nf + khác 0. Khi đó, không một đơn thức nào trong các đơn thức
có dư ) ( in f bằng 0 thì theo tiêu chuẩn ( S f ) ( in f 1 ,...,
46
⊂
,...,
,
( in f
)
)
chia hết
)
n
n
f
,...,
f
I
Do đó: ) ( in f
}
f 1,...,
n
f 1
,n
f + 1 n
( )1 . in f + n ( ) ( ( in f + in f in f ,..., 1 1 1 n + ∈ nên bây giờ ta thay hệ sinh { 1nf
là ngặt. } bằng hệ sinh {
,...,
f
Chú ý rằng và tính tất cả các S − đa thức cho hệ sinh mới này.
f
}
f 1
,n
f + 1 n
,i
j
)
f
,...,
( S f }
,n
f + n 1
f 1
2nf + khác không
f
,
,
bằng 0 thì theo tiêu cho hệ {
+
n
n
+ 1
n
2
⊂
là một cơ sở Gröbner. Nếu có dư }
,...,
,
,...,
,
,
)
( in f
( in f
)
( in f
)
f ( in f
f )
,..., f 1 ) ( in f
)
)
+
n
n
n
n
n
+ 1
+ 1
2
là ngặt. Nếu tất cả dư trong phép chia chuẩn Buchberger, { ta có hệ sinh mới { ( in f 1 và: ( in f 1
⊂
,...,
,...,
( in f
)
( in f
)
)
)
)
( in f 1
( in f 1
+ 1
n
n
n
⊂
⊂ ⊂ ...
,...,
,
...
( in f
)
( in f
)
)
( in f 1
+ 1
n
n
+ n j
( , in f ( in f
)
Nhờ bổ đề Dickson, quá trình này sẽ dừng lại sau hữu hạn bước, và cơ sở Gröbner có thể tính được. Thật vậy, giả sử có dãy tăng ngặt vô hạn các ideal đơn thức:
( in f
)
) 1 ,...,
n
,..., { ( in f
} ,...
=
,...,
,
< < < ...
( ) G I
, i 1
i 2
i q
và nếu tập sinh tối tiểu
)
i 2
i 1
i q
( in f
} )
j
q
=
,...,
,
,...,
,
,...,
,
Tuy nhiên, nếu tập tất cả các đơn thức là ( in f
)
( in f
)
j
( in f 1
2
+ 1
( in f
)
{ ) ( in f i> ta có: ) ( ) n f
i q
i q
i q
i 2
i 1
( in f
)
( in f
)
( in f
)
là mâu
Với ( in f thuẫn.
=
−
,...,
.
f
Thuật toán để tìm cơ sở Gröbner từ một hệ sinh của I được trình bày ở trên là thuật toán Buchberger.
[ = R K x 1
x 7
x x 1 4
x x 2 3
x 1
x 7
=
=
] với các ideal khởi đầu
Ví dụ: Cho và thứ thự từ điển với Lấy và
f g ,
I
.
.
( in f
> ... (
> )
)
x x 5 6
x x in g , 1 4
x x 4 7
=
=
.
x x x 1 5 6
x f 7
=
=
−
Lấy
h
,
.
,
,
( S f g
= x x g 4 7 đã có { ta tính (
− = Ta },f g không là cơ sở Gröbner với thứ tự từ điển. Theo thuật toán Buchberger, ) ( − − Ta có thể chọn một dư trong phép chia x g , S f g 1 ) },f g chính là S f g cho hệ { ) ) S f g Đặt
x x x 2 3 7 (
x x x 2 3 7
x x x 1 5 6
của thì
in h nguyên tố cùng nhau. Mặt khác dư của phép
(
( )
( ) in h
=
−
,
,
f g h bằng 0. Vậy theo tiêu chuẩn Buchberger ,
1 5 6. x x x )
47
}
x x 5 6
) in g và ) f g h là cơ sở Gröbner của I với thứ tự từ điển. ,
,
= ( S f h }
cho { Ta có ( x x x x 2 3 4 7
chia hệ {
48
Kết luận
Luận văn đã trình bày các kiến thức một cách có hệ thống để giải quyết bài toán
=
=
I
f
R
đặt ra: Trong vành đa thức
cho f
R∈ và
[ R K x
1 xác ,
] x ,n
1,...,
1,..., f
s
I∈ thì f phải biểu diễn được dưới
định xem f có thuộc I hay không?. Để f
=
f
+ + ...
.
Để có biểu diễn này, luận văn đã trình bày thuật toán
dạng
q f s
s
q f 1 1
f
chia của f cho hệ
Tuy nhiên, khi R là vành đa thức nhiều biến thì đa
f 1,...,
.s
∈
f
f
thức dư khi chia f cho
f không duy nhất. Thậm chí, có thể s
f 1,...,
s
f 1,...,
nhưng khi chia f cho
1,..., f
f thì đa thức dư có thể khác không. Như vậy, liệu có s
hệ sinh
g theo bất cứ thuật toán
g 1,...,
g nào của I mà khi chia f cho t
g 1,...,
t
chia nào thì đa thức dư là duy nhất và do đó nếu f
I∈ thì đa thức dư luôn bằng
0. Đó chính là cơ sở Gröbner. Để có khái niệm cơ sở Gröbner, luận văn đã
nghiên cứu khái niệm và tính chất của ideal đơn thức, ideal khởi đầu. Luận văn
cũng đưa ra thuật toán Buchberger để tìm một cơ sở Gröbner của I từ hệ sinh
f ban đầu. s
f 1,...,
49
Tài liệu tham khảo
Tiếng Việt
1. Nguyễn Viết Đông – Trần Huyên (2006), Đại số đồng điều, Nhà xuất bản Đại học quốc gia Hà Nội.
2. Lê Tuấn Hoa (2003), Đại số máy tính Cơ sở Gröbner, Nhà xuất bản Đại học Quốc gia Hà Nội.
3. Hoàng Xuân Sính (1999), Đại số đại cương, Nhà xuất bản giáo dục.
Tiếng Anh
4. M.F. Atiyah and I.G Macdonald (1996), Introduction to Commutative Algebra, Addison-Wesley, Reading, Masachusetts.
5. D. Bayer and M. Stillman (1987), “A criterion for detecting m-regularity”, Invent. Math. 87 pp. 1-11.
6. Th. Becker and V. Weispfenning (1993), Gröbner Bases – A Computational Approach to Commutative Algebra, Springer Verlag.
7. W. Bruns and J. Herzog (1993), Cohen-Macaulay Rings, Cambridge Univ. Press.
8. B. Buchberger (1985), Gröbner base: An algorithmic method in polynomial ideal theory, in “Multidimensional system theory” (edited by N. K. Bose), Approach to Commutative Algebra, Springer Verlag.
9. W. Gröbner (1970), Algebraische Geometrie, Vol. II, Bibliographaishes Institul.
10. S. Mac Lane (1986), Homology, Springer-Verlag, New York.
