ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
NGUYỄN THỊ ÁNH LY
THUẬT TOÁN SLICE CHO PHÂN TÍCH BẤT KHẢ QUY CỦA IĐÊAN ĐƠN THỨC
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
NGUYỄN THỊ ÁNH LY
THUẬT TOÁN SLICE CHO PHÂN TÍCH BẤT KHẢ QUY CỦA IĐÊAN ĐƠN 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: PGS.TS. NGUYỄN THỊ DUNG
THÁI NGUYÊN - 2016
Lời cam đoan
Tôi xin cam đoan rằng luận văn này là hoàn toàn trung thực và không trùng
lặp với các luận văn trước đây. Các thông tin, tài liệu trong luận văn đã được ghi
rõ nguồn gốc.
Thái Nguyên, ngày .... tháng .... năm 2016
Học viên
i
NGUYỄN THỊ ÁNH LY
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn khoa học của PGS.TS
Nguyễn Thị Dung, giảng viên Trường Đại học Nông Lâm- Đại học Thái Nguyên.
Đầu tiên, tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới cô. Trong suốt quá
trình làm luận văn, cô đã dành nhiều thời gian và công sức để chỉ bảo hướng dẫn
tôi từ những điều nhỏ nhặt nhất tới những vấn đề khó khăn cô vẫn luôn kiên nhẫn,
tận tình quan tâm giúp đỡ tôi để hoàn thành luận văn này.
Tôi cũng xin bày tỏ lòng biết ơn sâu sắc tới các thầy cô giáo của Viện Toán học
và Đại học Thái Nguyên, những người đã tận tình giảng dạy và khích lệ, động
viên tôi vượt qua những khó khăn trong học tập. Tôi xin cảm ơn ban lãnh đạo
Trường Đại học Sư phạm - Đại học Thái Nguyên, Khoa Sau đại học đã tạo mọi
điều kiện thuận lợi, giúp đỡ tôi trong suốt thời gian học tập. Cuối cùng tôi xin
cảm ơn bạn bè, người thân đã giúp đỡ, động viên, ủng hộ tôi để tôi có thể hoàn
thành tốt khóa học của mình.
Thái Nguyên, ngày .... tháng .... năm 2016
Học viên
ii
NGUYỄN THỊ ÁNH LY
Mục lục
Lời cam đoan i
Lời cảm ơn ii
Mục lục iii
Mở đầu 1
1 Iđêan đơn thức 3
1.1 Iđêan đơn thức và đồ thị của iđêan đơn thức . . . . . . . . . . . 3
1.2 Các phép toán trên iđêan đơn thức . . . . . . . . . . . . . . . . 7
1.2.1 Giao của các iđêan đơn thức . . . . . . . . . . . . . . . 7
1.2.2 Căn của iđêan đơn thức . . . . . . . . . . . . . . . . . . 9
1.2.3 Phép chia trên iđêan đơn thức . . . . . . . . . . . . . . 10
1.3 Iđêan đơn thức bất khả quy và sự phân tích . . . . . . . . . . . . 12
1.4 Phân tích tham số của các iđêan đơn thức . . . . . . . . . . . . 15
1.4.1 Iđêan tham số . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2 Phần tử góc . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Thuật toán Slice 18
2.1 Đơn thức chuẩn cực đại, đế và sự phân tích . . . . . . . . . . . . 18
2.2 Nhãn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Thuật toán Slice . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Slice cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Sự kết thúc và sự lựa chọn then chốt . . . . . . . . . . . . . . . 30
iii
2.6 Giả mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.7 Cải tiến thuật toán cơ sở . . . . . . . . . . . . . . . . . . . . . . 33
2.7.1 Đơn thức chặn dưới của cái chứa slice . . . . . . . . . . 33
2.7.2 Tách độc lập . . . . . . . . . . . . . . . . . . . . . . . 38
iv
Tài liệu tham khảo 41
Mở đầu
Một trong những kết quả cơ bản trong Đại số giao hoán là định lý phân tích
bất khả quy được chứng minh bởi Emmy Noether năm 1921. Trong bài báo đó
Emmy Noether đã chứng minh rằng iđêan bất kì trong vành Noether có thể viết
thành giao hữu hạn của các iđêan bất khả quy. Cho A là một vành giao hoán có
đơn vị và đặt R = A[X1, . . . , Xd] là vành đa thức d biến trên A. Một iđêan đơn thức m-bất khả quy theo một nghĩa nào đó là iđêan đơn thức nhỏ nhất, tức là nó không
iđêan đơn thức của R, một phân tích m-bất khả quy của J là biểu diễn J =
với mọi i 6
thể viết được thành giao không tầm thường của các iđêan đơn thức. Cho J là một n i=1Ji ∩ thành giao của các iđêan m-bất khả quy, phân tích này được gọi là rút gọn nếu Ji * Ji′ = i′ và phân tích m-bất khả quy rút gọn là duy nhất nếu không kể đến thứ tự các iđêan đơn thức trong phân tích. Chú ý rằng nếu J ( R là iđêan đơn thức bất khả quy thì là nó luôn là iđêan m-bất khả quy và điều ngược lại cũng
đúng nếu A là miền nguyên.
Gần đây phân tích bất khả quy của iđêan đơn thức trở thành vấn đề tính toán
cơ bản và được áp dụng trong nhiều lĩnh vực từ thuần túy toán học đến toán học
ứng dụng và các lĩnh vực như sinh học, ... Một vài ví dụ của áp dụng phân tích
bất khả quy của iđêan đơn thức là cát tuyến của các iđêan đơn thức và lũy thừa
hình thức của iđêan đơn thức đưa ra bởi B. Sturmfels and S. Sullivant [8], vấn đề
Frobenius đưa ra bởi B.H. Roune [7], kỹ thuật nghịch đảo của các mạng sinh học
đưa ra bởi A.S Jarrah [3].
Mục đích của luận văn là giới thiệu về thuật toán Slice, một thuật toán dùng
để tính phân tích bất khả quy của iđêan đơn thức, nghĩa là viết iđêan đơn thức
đó thành giao rút gọn của các iđêan đơn thức bất khả quy. Các kết quả này được
trình bày lại và chứng minh chi tiết một phần của bài báo "The slice Algorithm
1
for Irreducible Decomposition of Monomial ideals" của tác giả B. Roune [6].
Cho k là một trường và đặt R = k[x1, . . . , xn], với n > 2 là vành đa thức n biến R được gọi là đơn lấy hệ số trên k, I là iđêan đơn thức của R. Một đơn thức m ∈ I, với mọi i = 1, . . . , n. Tập tất cả thức chuẩn cực đại của I nếu m / ∈ ∈ I và mxi các đơn thức chuẩn cực đại của I được ký hiệu là msm(I). Nếu biểu diễn I bằng
đồ thị thì mỗi đơn thức chuẩn cực đại của I ứng với một điểm nằm ngoài I nhưng
nằm ở góc "gần nhất" so với phần đồ thị thuộc I.
Tập đơn thức chuẩn cực đại msm(I) đóng một vai trò quan trọng trong thuật
toán Slice bởi ý tưởng cơ bản của thuật toán bắt nguồn từ một kết quả sau của
Miller và Sturmfels [4]:
i
Chọn số nguyên t sao cho t lớn hơn bậc của mỗi đơn thức trong tập các đơn
mi + 1 < t). Khi đó, ánh n)) vào tập các iđêan | 1, . . . , xt
thức sinh rút gọn min(I) và định nghĩa f (xm) = (xmi+1 xạ f là một song ánh từ tập chuẩn cực đại msm(I + (xt đơn thức bất khả quy irr(I) của I.
Vì thế, bài toán tìm phân tích bất khả quy được quy về bài toán tìm tập đơn
thức chuẩn cực đại. Thuật toán Slice cung cấp một công cụ để tính msm(I) bằng
cách tách nó thành hai tập con gọi là slice trong và slice ngoài. Cả hai slice này
đều phụ thuộc vào cách chọn một đơn thức gọi là then chốt. Các đơn thức của
mỗi slice này lại được coi như tập chuẩn cực đại của các iđêan mới. Tiếp theo
mỗi slice này lại được tách thành các slice đơn giản hơn và quá trình này tiếp tục
cho đến khi tách thành những slice đủ đơn giản để có thể tính được tập các đơn
thức chuẩn cực đại của chúng.
Cấu trúc của luận văn gồm hai chương. Chương 1 của luận văn dành để nhắc
lại một số kiến thức về iđêan đơn thức: đồ thị, các phép toán giao, căn, chia và
phân tích bất khả quy, phân tích tham số của iđêan đơn thức.
Chương 2 giới thiệu về thuật toán slice: mô tả thuật toán thông qua tập đơn
thức chuẩn cực đại; chứng minh thuật toán dừng và đoạn giả mã để thực hiện
thuật toán; mục 2 của chương 2 giới thiệu một số cải tiến cho phiên bản cơ sở của
thuật toán.
2
Phần kết luận của luận văn tổng kết một số công việc đã thực hiện.
Chương 1
Iđêan đơn thức
Ký hiệu A là một vành giao hoán có đơn vị và đặt R = A[X1, . . . , Xd]. Chương này dành để nhắc lại một số kiến thức về iđêan đơn thức: đồ thị, các phép toán,
phân tích tham số của iđêan đơn thức. Các kết quả ở chương này được viết dựa
theo [5].
1.1 Iđêan đơn thức và đồ thị của iđêan đơn thức
Định nghĩa 1.1.1. Một iđêan đơn thức trong R là một iđêan của R được sinh bởi
các đơn thức theo các biến X1, . . . , Xd.
Ví dụ 1.1.2. Đặt R = A[X,Y ].
(i) Iđêan I = (X 2, X 3Y,Y 3)R là một iđêan đơn thức.
Y 3, X 5) là một iđêan đơn thức vì J = (X 5,Y 3). −
1 · · ·
(ii) Iđêan J = (X 5 (iii) Iđêan 0 và R là các iđêan đơn thức vì 0 = ( /0)R và R = 1RR = X 0 X 0 d R.
Với mỗi iđêan đơn thức khác không I R, ta ký hiệu [[I]] là tập hợp tất cả các
R là một tập vô hạn nhưng không ⊆ đơn thức chứa trong I. Khi đó tập hợp [[I]] ⊂ là iđêan. Theo định nghĩa, ta có [[I]] = I [[R]]. Hơn nữa, với mỗi iđêan đơn thức ∩ I R, ta có I = ([[I]])R. ⊆
Mệnh đề 1.1.3. Cho I và J là hai iđêan đơn thức của R.
(i) I J nếu và chỉ nếu [[I]] [[J]]. ⊆ ⊆
(ii) I = J nếu và chỉ nếu [[I]] = [[J]].
Định nghĩa 1.1.4. (i) Cho f và g là các đơn thức của R. Khi đó f được gọi là bội
3
đơn thức của g nếu tồn tại một đơn thức h R sao cho f = gh. ∈
1 . . . X nd
d ∈
R, khi đó ta có bộ d-số tự nhiên
Nd được gọi là véc tơ lũy thừa của f . (ii) Với mỗi đơn thức f = X n = X n1 n = (n1, . . . , nd) ∈
Vì thế, có một sự tương ứng 1 −
1 giữa các đơn thức trong R với các véc tơ trong Nd và vì các đơn thức trong R = A[X1, . . . , Xd] là độc lập tuyến tính trong A nên véctơ lũy thừa của mỗi đơn thức f R là hoàn toàn xác định. ∈
≥ Cho d là một số nguyên dương. Giả sử trên Nd ta định nghĩa một quan hệ < như sau: m = (m1, . . . , md) < (n1, . . . , nd) nếu và chỉ nếu với mọi i = 1, . . . , d ta có mi ni theo thứ tự thông thường trên N. Khi đó nhờ vào tính độc lập tuyến tính của các đơn thức trong R, kết quả sau đây nói rằng tích của một đơn thức và
một đa thức thì không là đơn thức (xem [5, Bổ đề 2.1.9]).
Bổ đề 1.1.5. Cho f = X m và g = X n là các đơn thức trong R. Nếu h là một đa thức trong R sao cho f = gh thì m < n và h = X p là đơn thức, trong đó pi = mi ni. −
Ví dụ 1.1.6. Đặt R = A[X,Y ]. Cho f = X 2Y và g = X 3Y, vì m1 = 2 < n1 = 3 nên theo Bổ đề 1.1.5 thì f không là bội của g nhưng ngược lại g là một bội của f .
Cho d là số nguyên dương, với mỗi n Nd, đặt
[n] = = n + Nd. Nd ∈ m < n } | m { ∈
Kết quả tiếp theo cho ta một tiêu chuẩn để kiểm tra xem khi nào thì một đơn
thức f thuộc iđêan sinh bởi đơn thức g. Đặc biệt là các điều kiện tương đương (i)
và (iv) cho phép ta có thể kiểm tra bằng cách làm việc trên các véc tơ lũy thừa.
Bổ đề 1.1.7. Cho f = X m và g = X n là các đơn thức trong R. Khi đó các điều kiện sau là tương đương:
(i) f gR. ∈
(ii) f là một bội của g.
(iii) f là một bội đơn thức của g.
(iv) m < n.
(v) m [n]. ∈
4
Vì ta có một song ánh giữa các đơn thức của [[R]] và các bộ số thuộc Nd, nên (iv), ta có thể xây dựng một quan hệ trên tập hợp các theo Bổ đề 1.1.7 (iii) ⇔
đơn thức [[R]] của R như sau: X m < X n khi X m là một bội của X n và rõ ràng rằng < là một quan hệ thứ tự gọi là thứ tự chia hết trên [[R]].
Kết quả sau đây cho ta một tiêu chuẩn để kiểm tra xem một đơn thức bất kỳ có
thuộc vào một iđêan sinh bởi các đơn thức hay không (xem [5, Định lý 2.1.14]).
( f1, . . . , fm)R ∈ Định lý 1.1.8. Cho f , f1, . . . , fm là các đơn thức trong R. Khi đó f nếu và chỉ nếu tồn tại i sao cho f fiR. ∈
Để có một hình dung trực quan hơn về iđêan đơn thức, đặc biệt là đối với vành
đa thức hai biến, người ta đưa ra khái niệm sau: Đồ thị của một iđêan đơn thức I
là tập hợp
X n I G (I) = Nd n { ∈ | . } ∈
Khái niệm đồ thị của iđêan đơn thức cho ta một sự kết nối giữa các đơn thức
sinh của I với các tập con của tập Nd (xem [5, Định lý 2.1.17]): Định lý 1.1.9. Nếu I = (X n1, . . . , X nm)R thì G (I) = [n1] [nm]. ∪ · · · ∪
[n1] [nm]. Khi đó tồn tại i sao cho m [ni] và do đó ∪ · · · ∪ ∈ ∈ Chứng minh. Cho m m < ni. Theo Bổ đề 1.1.7 ta có
X m X niR (X n1, . . . , X nm)R = I. ⊆
Từ định nghĩa suy ra m ∈ G (I). ∈ Ngược lại, giả sử rằng p G (I). Khi đó X p I = (X n1, . . . , X nm)R. Theo Định ∈ ∈ X n jR với mỗi j. Từ Bổ đề 1.1.7 ta kết luận lí 1.1.8 suy ra X p ∈
p [n j] [n1] [nm]. ⊆ ∪ · · · ∪ ∈
[(2, 2)] [(0, 3)] ⊆ ∪ ∪ Ví dụ 1.1.10. (i) Đặt R = A[X,Y ]. Đồ thị của iđêan I = (X 3, X 2Y 2,Y 3)R là tập hợp G (I) = [(3, 0)] N2, được biểu diễn bởi đồ thị trong Hình 1.1.
(ii) Đặt R = A[X,Y ]. Cho I = (X)R và J = (Y 3)R. Khi đó I + J = (X,Y 3)R. Theo Định lí 1.1.9, G (I) = [(1, 0)], G (J) = [(0, 3)] và
G (I + J) = [(1, 0)] [(0, 3)] = G (I) G (J). ∪
5
∪ Ta có đồ thị của chúng được biểu diễn trong Hình 1.2.
...
...
...
...
...
4
. . .
3
. . .
. . .
2
1
. . .
0
. . .
3
1
2
4
0
Hình 1.1: G (X 3, X 2Y 2,Y 3)
...
...
...
...
...
...
...
...
. . .
. . .
4
4
. . .
. . .
3
3
. . .
2
2
. . .
1
1
. . .
0
0
3
3
1
2
4
1
2
4
G (I)
G (J)
...
...
...
...
...
. . .
4
. . .
3
. . .
2
. . .
1
. . .
0
3
1
2
4
G (J)
∪
G (I + J) = G (I) Hình 1.2:
Tiếp theo, ta cần nhắc lại một số kiến thức về tập các phần tử sinh của iđêan
∈
6 đơn thức. Cho I là một iđêan đơn thức của R. Cho z1, . . . , zm [[I]] sao cho ta có I = (z1, . . . , zm)R. Dãy z1, . . . , zm là một dãy sinh đơn thức rút gọn của I nếu zi = j. Ngược lại, dãy trên được gọi là dãy không là một bội đơn thức của z j, với i sinh đơn thức không rút gọn. Khi đó Định lý cơ sở Hilbert khẳng định rằng mọi
iđêan đơn thức I trong R đều hữu hạn sinh và được sinh bởi một tập hữu hạn các
đơn thức. Hơn nữa, mọi tập sinh đơn thức của I đều chứa một dãy sinh đơn thức
6
rút gọn và dãy này là duy nhất nếu không kể đến thứ tự. Nếu ký hiệu tập các đơn
thức trong dãy sinh đơn thức rút gọn của I là min(I) thì ta có
I không tồn tại X m sao cho n < m min(I) = X n { ∈ | . }
X 2Y nên X 3, XY, X 2Y,Y 3 là một dãy sinh Ví dụ 1.1.11. Đặt R = A[X,Y ]. Vì XY | đơn thức không rút gọn của iđêan (X 3, XY, X 2Y,Y 3)R. Dãy X 3, X 2Y 2, XY 3,Y 5 là một dãy sinh đơn thức rút gọn đối với (X 3, X 2Y 2, XY 3,Y 5)R vì không có một đơn thức nào trong X 3, X 2Y 2, XY 3,Y 5 là bội của đơn thức còn lại.
Sau đây là một thuật toán để tìm dãy sinh đơn thức rút gọn.
[[R]] và đặt J = (z1, . . . , zm)R. ∈ Thuật toán 1.1.12. Cho các đơn thức z1, . . . , zm Ta giả sử rằng m > 1.
Bước 1. Kiểm tra xem dãy sinh z1, . . . , zm là rút gọn bằng cách sử dụng định
nghĩa.
Bước 1a. Nếu mọi chỉ số i và j sao cho i = j, ta có z j (zi)R, thì dãy sinh đó 6∈ 6 là rút gọn. Trong trường hợp này, thuật toán dừng lại.
Bước 1b. Nếu tồn tại chỉ số i và j sao cho i = j và z j (zi)R, thì dãy sinh ∈ 6 không rút gọn; ta thực hiện tiếp bước 2.
−
1.
−
Bước 2. Rút gọn dãy sinh bằng cách loại bỏ các phần tử z j sao cho z j ∈ với i 6 (zi)R = j. Không mất tính tổng quát, ta có thể giả thiết j = m và sắp xếp lại các 1)R. (zi)R với i < m. Suy ra J = (z1, . . . , zm)R = (z1, . . . , zm ∈ chỉ số sao cho zm Bây giờ ta áp dụng bước 1 cho một dãy các đơn thức mới z1, . . . , zm
Thuật toán sẽ dừng lại sau m 1 bước vì ta có thể loại bỏ nhiều nhất m 1 đơn − − thức trong dãy sinh và cuối cùng là thu được một iđêan khác 0.
1.2 Các phép toán trên iđêan đơn thức
1.2.1 Giao của các iđêan đơn thức
Ta đã biết rằng các iđêan của một vành giao hoán luôn đóng đối với phép toán
giao. Đối với các iđêan đơn thức, điều này cũng được chứng minh là đúng nhờ
vào các kết quả sau.
∩ · · · ∩ In]] = [[I1]] In là [[In]]. Hơn nữa, ta có
7
Định lý 1.2.1. Nếu I1, . . . , In là các iđêan đơn thức của R thì giao I1 một iđêan đơn thức của R và [[I1 đồ thị của iđêan giao G (I1 ∩ · · · ∩ In) = G (I1) ∩ · · · ∩ G (In). ∩ · · · ∩ ∩ · · · ∩
...
...
...
...
...
...
. . .
. . .
⊛
⊛
⊛
⊛
⊛
⊛
4
4
. . .
. . .
⊛
⊛
⊛
⊛
⊛
⊛
3
3
. . .
.....
. . .
⊛
⊛
⊛
⊛
⊛
2
2
... ... ... ... ◦ ... ... ◦ ... ◦
.....
.....
.....
. . .
1
1
⊛ ... ... ∗
∗
∗
0
0
0
3
1
2
4
2
3
4
0
1
KEY
................
G ((XY 2)R)
◦
................
G ((X 2Y )R)
........
∗ ⊛
G ((XY 2)R
(X 2Y )R)
∩
Hình 1.3: G (I + J)
Ví dụ 1.2.2. Đặt R = A[X,Y ]. Cho I = (XY 2)R và J = (X 2Y )R. Khi đó nhờ vào Định lý 1.2.1, quan sát đồ thị Hình 1.3 ta có thể tìm được I J = (X 2Y 2)R. ∩
Đối với vành hai biến ta có thể sử dụng đồ thị để tìm giao của hai iđêan đơn
thức, tuy nhiên việc sử dụng đồ thị là khó khăn với vành nhiều hơn hai biến. Kết
quả sau đây cho ta một phương pháp chung để tìm giao của hai iđêan đơn thức.
Trước hết ta cần định nghĩa sau.
∈
Nd. Khi đó, bội chung nhỏ , và với mọi } Định nghĩa 1.2.3. Cho f = X m và g = X n với m, n nhất của f và g là đơn thức lcm( f , g) = X p, với pi = max mi, ni { i = 1, . . . , d.
Ví dụ 1.2.4. Đặt R = A[X,Y, Z] và cho f = X 2Y Z, g = XZ5. Khi đó m = (2, 1, 1) và n = (1, 0, 5), do đó p = (2, 1, 5). Vậy bội chung nhỏ nhất của f và g là
lcm(X 2Y Z, XZ5) = X 2Y Z5.
và J Mệnh đề 1.2.5. Giả sử I được sinh bởi tập hợp các đơn thức } { được sinh bởi tập hợp các đơn thức f1, . . . , fm J được sinh bởi tập g1, . . . , gn { . Khi đó I } ∩ hợp các đơn thức
8
lcm( fi, g j) { | 1 6 i 6 m, 1 6 j 6 n . }
Mệnh đề trên và Thuật toán 1.1.12 sẽ được áp dụng trong ví dụ sau để tìm dãy
sinh đơn thức rút gọn.
(X 4,Y 3, Z4)R. Ta ∩ Ví dụ 1.2.6. Đặt R = A[X,Y, Z]. Cho I = (X 3Y Z, XY 2Z2)R có
lcm(X 3Y Z, X 4) = X 4Y Z lcm(X 3Y Z,Y 3) = X 3Y 3Z lcm(X 3Y Z, Z4) = X 3Y Z4 lcm(XY 2Z2, X 4) = X 4Y 2Z2. lcm(XY 2Z2,Y 3) = XY 3Z2. lcm(XY 2Z2, Z4) = XY 2Z4.
Khi đó theo Mệnh đề 1.2.5 suy ra X 4Y Z, X 4Y 2Z2, X 3Y 3Z, XY 3Z2, X 3Y Z4, XY 2Z4 là dãy sinh của I. Tiếp theo, ta dùng Thuật toán 1.1.12 để tìm dãy sinh đơn thức rút gọn của I. Chỉ có đơn thức X 4Y 2Z2 là bội của đơn thức X 4Y Z vì vậy ta loại X 4Y 2Z2 ra khỏi dãy và vì không có đơn thức nào trong dãy là một bội của các đơn thức còn lại nên dãy X 4Y Z, X 3Y 3Z, XY 3Z2, X 3Y Z4, XY 2Z4 là một dãy sinh đơn thức rút gọn của I.
1.2.2 Căn của iđêan đơn thức
Cho A là vành giao hoán có đơn vị và I là iđêan của A. Nhắc lại rằng căn của
I là tập hợp
A n I rad(I) = N, xn x { ∈ | ∃ ∈ . } ∈
Ta cũng thường kí hiệu căn của I là √I hoặc r(I).
Chú ý rằng căn của một iđêan đơn thức nhìn chung không là iđêan đơn thức.
Ví dụ trong vành đa thức một biến R = Z4[X], iđêan J = (X)R là một iđêan đơn thức. Tuy nhiên, iđêan rad(J) = (2, X)R không phải là một iđêan đơn thức. Vì
thế, trong mục này ta sẽ giới thiệu một khái niệm căn sao cho căn của một iđêan
đơn thức vẫn là iđêan đơn thức.
Định nghĩa 1.2.7. Cho J là một iđêan đơn thức trong R. Căn đơn thức của J, ký
hiệu là m-rad(J) là một iđêan đơn thức m-rad(J) = (S)R, trong đó
J n > 1sao cho zn S = [[R]] = rad(J) [[R]]. z { ∈ | ∃ ∈ } ∩
Ví dụ 1.2.8. Đặt R = A[X,Y ] và cho I = (X 5,Y 7)R. Khi đó theo định nghĩa ta có m-rad(I) = (S)R, trong đó
9
I S = [[R]] n1 = 5 sao cho X 5 Ivà n2 = 7 sao cho Y 7 X,Y { ∈ | ∃ . } ∈ ∈
Vì thế m-rad(I) = (X,Y )R. Tương tự m-rad((X 4Y 6)R) = (XY )R.
Kết quả sau đây cho ta mối quan hệ giữa rad(J) và m-rad(J).
Mệnh đề 1.2.9. Cho J là một iđêan đơn thức trong R.
(i) m-rad(J) rad(J). ⊆
(ii) m-rad(J) = rad(J) nếu và chỉ nếu rad(J) là một iđêan đơn thức.
(iii) Nếu A là một trường thì m-rad(J) = rad(J).
1.2.3 Phép chia trên iđêan đơn thức
Trước hết, ta nhắc lại khái niệm iđêan chia trên một vành giao hoán có đơn vị
A. Cho S là một tập con của A và cho I là một iđêan của A. Với mỗi phần tử r A, ∈ s S đặt rS = rs { | ∈
rs A A S s I rS = I, . Khi đó iđêan chia của I cho S được định nghĩa là } (I :A S) = r { ∈ | ∈ ∀ ∈ . } ∈ | ⊆
Với mỗi s r { S, ta đặt (I :A s) = (I :A ∈ } s ). } {
Cho J và I là các iđêan của vành đa thức R = A[X1, . . . , Xd]. Khi đó iđêan chia
của J cho I được định nghĩa là
f R f g g I J, J :R I = ∈ ∈ ∈ ∀ { . }
| Ví dụ 1.2.10. Đặt R = A[X], cho I = (X 7)R và J = (X 2)R. Khi đó (J :R I) = R.
Kết quả sau nói rằng phép toán chia là đóng trên tập các iđêan đơn thức.
Định lý 1.2.11. Nếu I và J là các iđêan đơn thức của R thì iđêan chia (J :R I) là một iđêan đơn thức của R.
Đối với những ví dụ đơn giản ta có thể sử dụng định nghĩa để tính iđêan chia,
tuy nhiên đối với những ví dụ phức tạp hơn việc tính iđêan chia sẽ trở nên khó
khăn hơn. Kết quả sau đây cho phép ta xác định một đơn thức có thuộc iđêan chia
hay không.
10
Chú ý 1.2.12. (i) Cho I và J là hai iđêan đơn thức trong R. Ta luôn có J ⊆ bởi vì theo định nghĩa f g J với mọi f R và g ∈ ∈ ∈ vì ta phải kiểm tra tất cả các đơn thức f của R sao cho f I (J :R I) I. Vì thế để tính (J :R I) thay J thì nay ta chỉ cần ∈ kiểm tra f [[R]] [[J]]. ∈ \
fY
f
f X
...
. . .
Hình 1.4:
(ii) Đặt R = A[X,Y ]. Cho I là một iđêan đơn thức của R và đặt X = (X,Y )R. Một I. Mối quan hệ đơn thức f R là nằm trong (I :R X) nếu và chỉ nếu f X, fY ∈ ∈ giữa các phần tử f , f X, fY được thể hiện qua đồ thị Hình 1.4 dưới đây
N biểu diễn một điểm trong (I :R X) nếu và chỉ nếu các cặp ∈ Do đó, điểm (a, b) có thứ tự (a + 1, b) và (a, b + 1) đều nằm trong đồ thị G (I).
Một cách tổng quát, điều này cũng đúng trong vành đa thức R = A[X1, . . . , Xd]
(Xem thêm ở mục phần tử góc).
[[J]] = \ } Ví dụ 1.2.13. (i) Cho I = (X 2, XY,Y 2) và J = (X 2,Y 3). Để tính (J :R I) theo chú ý 1, X,Y,Y 2, XY, XY 2 trên ta chỉ cần kiểm tra xem các đơn thức thuộc [[R]] { có thuộc J :R I hay không. Ta có
J, X.XY = X 2Y J.
J, X.Y 2 = XY 2 / ∈ J. J,Y.Y 2 = Y 3 ∈ J,Y.XY = XY 2 / ∈ ∈
1 / ∈ X / ∈ Y / ∈ Y 2 J,Y 2.Y 2 = Y 4 J,Y 2.XY = XY 3 J. ∈ ∈ ∈
XY ∈ J, XY.XY = X 2Y 2 J, XY.Y 2 = XY 3 J. ∈ ∈
∈ XY 2 J, XY 2.XY = X 2Y 3 J, XY 2.Y 2 = XY 4 J. (J :R I). (J :R I) vì X.X 2 = X 3 ∈ (J :R I) vì Y.X 2 = X 2Y ∈ (J :R I) vì Y 2.X 2 = X 2Y 2 (J :R I) vì XY.X 2 = X 3Y ∈ (J :R I) vì XY 2.X 2 = X 3Y 2 ∈ ∈ ∈ ∈
Vậy (J :R I) = (Y 2, XY, XY 2, X 2,Y 3)R = (Y 2, XY, X 2)R. (ii) Cho I = (X 3, X 2Y 2,Y 3) và đặt X = (X,Y )R. Theo Chú ý 1.2.12(ii) và quan sát đồ thị Hình 1.5 ta có
11
(I :R X) = (X 2Y, XY 2)R.
...
...
...
...
...
. . .
4
. . .
3
. . .
2
q
. . .
1
q
. . .
0
4
0
3
1
2 Hình 1.5:
1.3 Iđêan đơn thức bất khả quy và sự phân tích
Trước hết, ta nhắc lại các khái niệm về iđêan bất khả quy trên vành giao hoán
A khác không có đơn vị.
∩
=i′
= Một iđêan J ( A được gọi là iđêan bất khả quy nếu tồn tại hai iđêan J1 và J2 J2 thì J = J1 hoặc J = J2. Nếu A là một vành Noether thì luôn n i=1Ji và được gọi là sự phân ∩ Ji với mọi 6 ∩i 6 sao cho J = J1 tồn tại các iđêan bất khả quy J1, . . . , Jn sao cho J = tích bất khả quy của J, phân tích này được gọi là rút gọn nếu J chỉ số i′.
Bây giờ, ta sẽ quan tâm tới phân tích bất khả quy của iđêan đơn thức trên vành
đa thức R = A[X1, . . . , Xd].
Định nghĩa 1.3.1. Một iđêan đơn thức J ( R là m-bất khả quy nếu có hai iđêan đơn thức J1, J2 sao cho J = J1 J2 thì J = J1 hoặc J = J2.
(X,Y )R nên ta có ⊆ (X,Y )R. Theo định nghĩa, ta có I là iđêan đơn thức m-bất khả ∩ ∩ Ví dụ 1.3.2. Đặt R = A[X,Y ], cho I = (X,Y 2)R. Vì (X,Y 2)R viết I = (X,Y 2)R quy.
Định lý sau đây cho phép ta dễ dàng kiểm tra một iđêan đơn thức có là m-bất
khả quy hay không.
t1 , . . . , X ek
tk )R.
12
Định lý 1.3.3. Cho J là một iđêan đơn thức khác không của R. Iđêan J là m-bất khả quy nếu và chỉ nếu tồn tại các số nguyên dương k,t1, . . . ,tk, e1, . . . , ek sao cho 1 d và J = (X e1 t1, . . . ,tk ≤ ≤
Ví dụ 1.3.4. Đặt R = A[X,Y, Z,W ]. Khi đó theo định lý trên các iđêan đơn thức I = (X,Y 2)R, J = (Y 3, Z,W 2) là các iđêan đơn thức m-bất khả quy.
Iđêan m-bất khả quy theo nghĩa nào đó là iđêan đơn thức đơn giản nhất, trong
đó chúng không viết được thành giao của các iđêan đơn thức không tầm thường.
Tuy nhiên trong vành đa thức bất kỳ, một iđêan đơn thức là bất khả quy thì cũng
là m-bất khả quy, nhưng điều ngược lại nhìn chung không đúng. Ví dụ trong vành
Z6[X] iđêan 0 là m-bất khả quy nhưng lại là khả quy trong Z6[X]. Định lý sau cho ta điều kiện của vành A để điều ngược lại cũng đúng.
Định lý 1.3.5. Cho A là một miền nguyên, và đặt R = A[X1, . . . , Xd]. Một iđêan đơn thức khác không J ( R là bất khả quy nếu và chỉ nếu nó là m-bất khả quy.
Tương tự phân tích bất khả quy, một kết quả quan trọng sau được chứng minh
bởi Emmy Noether cũng cho phép đưa ra khái niệm phân tích bất khả quy rút
gọn.
Định lý 1.3.6. Nếu J ( R là một iđêan đơn thức thì có các iđêan đơn thức m-bất n khả quy J1, . . . , Jn của R sao cho J = i=1Ji. ∩
6 Định nghĩa 1.3.7. Cho J ( R là một iđêan đơn thức. Một phân tích m-bất khả n quy của J là biểu diễn J = i=1Ji trong đó mỗi Ji là m-bất khả quy, sự phân tích ∩ này là rút gọn nếu Ji * Ji′ = i′. Hơn nữa, phân tích m-bất khả với mọi chỉ số i quy rút gọn là duy nhất nếu không kể đến thứ tự các nhân tử và ta ký hiệu tập
các iđêan đơn thức m-bất khả quy trong phân tích m-bất khả quy rút gọn của J là
irr(J).
Ví dụ 1.3.8. Đặt R = A[X,Y ]. Cho J = (X 4, XY 2,Y 3)R. Khi đó, các phân tích m-bất khả quy của J
∩ ∩ J = (X,Y 3)R = (X,Y 3)R (X 4,Y 2)R (X 4,Y 2)R (X,Y )R (X 2,Y 2)R ∩
13
∩ (X,Y )R, (X 4,Y 2)R (X 2,Y 2)R. Rõ ràng rằng ⊆ ⊆ là không rút gọn vì (X 4,Y 2)R sự phân tích m-bất khả quy không rút gọn của J là không duy nhất.
Mặt khác, vì ta có X (X 4,Y 2)R và Y 2 (X 4,Y 2)R (X,Y 3)R ∈ ∈ \ \ (X,Y 3)R nên (X,Y 3)R * (X 4,Y 2)R và (X 4,Y 2)R * (X,Y 3)R. Do đó phân tích m-bất khả quy
J = (X,Y 3)R (X 4,Y 2)R ∩
là rút gọn và duy nhất.
Sau đây là một thuật toán để tìm phân tích m-bất khả quy rút gọn.
n i=1Ji đã rút gọn chưa. ∩
Thuật toán 1.3.9. Đặt R = A[X1, . . . , Xd]. Cho J là một iđêan đơn thức có phân n i=1Ji. Chú ý rằng n > 1. tích m-bất khả quy là J = ∩
n i=1Ji ∩
thì J = = j′, ta có J j * J j′ 6 Bước 1: Kiểm tra xem phân tích J = Bước 1a: Nếu với mọi chỉ số j và j′ sao cho j là rút gọn; trong trường hợp này, thuật toán dừng lại.
n i=1Ji ∩
thì J = Bước 1b: Nếu tồn tại chỉ số j và j′ sao cho j = j′ ta có J j J j′ ⊆ 6 là không rút gọn; trong trường hợp này, ta tiếp tục bước 2.
thì ta loại bỏ iđêan = j′ và J j J j′ ⊆ 6
với j < n. Suy ra J = J j′ sao cho J j J j′ ⊆ Bước 2: Nếu tồn tại chỉ số j, j′ sao cho j . Không mất tính tổng quát, ta có thể giả thiết j′ = n và sắp xếp lại các chỉ số n i=1Ji = ∩
n 1 i=1 Ji. − ∩ n 1 Bước 3: Áp dụng bước 1 cho phân tích mới J = i=1 Ji. − ∩ 1 bước vì ta có thể loại bỏ nhiều nhất là n
1 Thuật toán sẽ dừng lại sau n − − iđêan đơn thức trong giao và cuối cùng thu được một iđêan là giao khác rỗng của
các iđêan m-bất khả quy.
Tiếp theo cho các phân tích m-bất khả quy của các iđêan đơn thức I =
n j=1I j ∩ m i=1Ji. Ta quan tâm tới phân tích m-bất khả quy của I + J. Ta đã biết tổng
và J = ∩ của các iđêan đơn thức là một iđêan đơn thức. Hơn nữa ta có
Mệnh đề 1.3.10. Nếu J1, . . . , Jn là các iđêan đơn thức m-bất khả quy của R thì tổng J1 + . . . + Jn là m-bất khả quy.
Kết quả sau cho ta luật phân phối của giao đối với tổng của các iđêan đơn thức.
m i=1Ji) =
m n i=1 (I j + Ji). j=1 ∩ ∩
Bổ đề 1.3.11. Cho các iđêan đơn thức I1, . . . , In và J1, . . . , Jm của R. Khi đó ta có
n j=1I j) + ( ( ∩
14
∩
Kết quả tiếp theo là làm thế nào để xây dựng phân tích m-bất khả quy cho tổng
của các iđêan đơn thức.
Định lý 1.3.12. Cho I, J là các iđêan đơn thức của R với phân tích m-bất khả quy
m i=1Ji. Khi đó phân tích m-bất khả quy của I + J là
n j=1I j và J = ∩
I = ∩
m n i=1 (I j + Ji). j=1 ∩ ∩
I + J =
Ví dụ 1.3.13. Đặt R = A[X,Y, Z]. Cho
I = (X 3, X 2Y, X 3Z4,Y Z)R = (X 2, Z)R (X 3,Y )R; J = (Y 3, Z4)R. ∩
Khi đó ta có phân tích m-bất khả quy rút gọn của I + J là
((X 3,Y )R + (Y 3, Z4)R) ∩ I + J = (X 3, X 2Y, X 3Z4,Y Z,Y 3, Z4)R = ((X 2, Z)R + (Y 3, Z4)R) = (X 2,Y 3, Z)R (X 3,Y, Z4)R. ∩
1.4 Phân tích tham số của các iđêan đơn thức
1.4.1 Iđêan tham số
d )R,
1 , . . . , X ad Nd thì iđêan tham số ứng với
1. Nếu cho đơn thức f = X n với n ≥ ∈ Định nghĩa 1.4.1. Một iđêan tham số trong R là một iđêan có dạng (X a1 với a1, . . . , ad f là
1
)R. PR( f ) = (X n1+1 , . . . , X nd+1 d
Ví dụ 1.4.2. Cho R = A[X,Y ].
(i) Cho đơn thức f = XY, khi đó ta có iđêan tham số của f là PR(XY ) = (X 2,Y 2)R. Quan sát đồ thị Hình 1.6, ta thấy rằng ký hiệu q trong đồ thị của PR(XY ) tương
ứng với đơn thức XY.
15
(ii) Đặc biệt PR(1) = (X,Y )R, PR(X) = (X 2,Y ) và PR(Y ) = (X,Y 2).
...
...
...
...
...
. . .
4
. . .
3
. . .
2
. . .
1
q
0
4
3
0
1
2 Hình 1.6: G (PR(XY ))
Bổ đề sau cho ta một công cụ hữu ích để làm việc với các iđêan tham số.
Bổ đề 1.4.3. Cho f , g là các đơn thức trong R. Khi đó:
PR( f ). (i) f / ∈
(ii) g (g)R. PR( f ) nếu và chỉ nếu f / ∈ ∈
của J là phân tích có dạng J =
tham số rút gọn nếu với mọi j Định nghĩa 1.4.4. Cho J là một iđêan đơn thức của R. Một phân tích tham số n i=1 PR(zi). Hơn nữa, phân tích này là phân tích ∩ = j′ ta có PR(z j) * PR(z j′ ). 6
Chú ý 1.4.5. (i) Một iđêan đơn thức J của R có thể có hoặc không có phân tích
tham số và mục tiếp theo chỉ ra rằng điều kiện cần và đủ để J có phân tích tham số là m-rad(J) = X.
(ii) Định lý 1.3.3 chỉ ra rằng mọi iđêan tham số trong R là m-bất khả quy. Vì thế,
mỗi phân tích tham số của J là một phân tích m-bất khả quy. Cũng vậy, mỗi một
phân tích tham số là rút gọn nếu và chỉ nếu nó là một phân tích m-bất khả quy rút
gọn. Hơn nữa, mỗi phân tích tham số rút gọn là duy nhất nếu không kể đến thứ
tự các nhân tử.
1.4.2 Phần tử góc
Mục này đưa ra một công thức để tính phân tích tham số rút gọn. Trước hết ta
có định nghĩa sau.
16
Định nghĩa 1.4.6. Cho J là một iđêan đơn thức trong R. Một đơn thức z [[R]] ∈
J. Tập hợp các phần tử J-góc của J J và X1z, . . . , Xdz ∈ là phần tử J-góc nếu z / ∈ trong [[R]] được ký hiệu là CR(J).
Ví dụ 1.4.7. Cho R = A[X,Y ], J = (X 3, X 2Y, XY 2,Y 3). Khi đó ta có tập phần tử J-góc của J là
CR(J) = X 2, XY,Y 2 { . }
Kết quả dưới đây cho ta mối quan hệ chặt chẽ giữa các phần tử góc và phân
tích tham số rút gọn của một iđêan đơn thức.
m
j=1 PR(z j), theo [5, Hệ quả 6.3.3] suy ra giao này là rút gọn và J′ ⊆
∩ Định lý 1.4.8. Đặt X = (X1, . . . , Xd)R và J là iđêan đơn thức của R sao cho m- rad(J) = X. Nếu các phần tử J-góc phân biệt là z1, . . . , zm thì J = m j=1 PR(z j) là phân tích tham số rút gọn của J.
J′. Do đó zi ∈ ∈ Chứng minh. Chú ý rằng [5, Mệnh đề 6.3.4] đã chỉ ra rằng J có một phần tử góc. Đặt J′ = J. ∩ J. Vì PR(z j) là một iđêan đơn thức, Định lý 1.2.1 chỉ ra Do đó ta sẽ chỉ ra J′ ⊇ rằng J′ là một iđêan đơn thức. Giả sử ngược lại J′ ( J. Theo [5, Mệnh đề 6.3.4] PR(zi), điều này mâu suy ra J′ chứa một phần tử J-góc, hay zi thuẫn với Bổ đề 1.4.3 (i).
Định lý 1.4.8 chỉ ra rằng các phần tử J-góc hoàn toàn xác định một phân tích
tham số rút gọn của J và kết quả dưới đây cũng chỉ ra rằng một phân tích tham
số rút gọn của J cũng xác định các phần tử J-góc.
[[R]] và giả sử J = ∈ ∩
m Mệnh đề 1.4.9. Cho các đơn thức z1, . . . , zm j=1 PR(z j) là một phân tích tham số rút gọn của J. Khi đó các phần tử J-góc phân biệt là z1, . . . , zm.
17
Chương 2
Thuật toán Slice
Trong chương này, ta sẽ giới thiệu về thuật toán Slice, một thuật toán dùng để
tính phân tích bất khả quy của iđêan đơn thức, nghĩa là viết iđêan đơn thức đó
thành giao rút gọn của các iđêan bất khả quy thông qua việc tính tập các đơn thức chuẩn cực đại. Cho k là một trường và đặt R = k[x1, . . . , xn] với n > 2 là vành đa thức n biến lấy hệ số trên k, I là iđêan đơn thức của R. Thuật toán Slice cung cấp
một công cụ để tính tập các đơn thức chuẩn cực đại msm(I) bằng cách tách nó
thành hai tập con gọi là slice trong và slice ngoài. Cả hai slice này đều phụ thuộc
vào cách chọn một đơn thức gọi là then chốt. Các đơn thức của mỗi slice này lại
được coi như tập chuẩn cực đại của các iđêan mới. Tiếp theo mỗi slice này lại
được tách thành các slice đơn giản hơn và quá trình này tiếp tục cho đến khi tách
thành những slice đủ đơn giản để có thể tính được tập các đơn thức chuẩn cực đại
của chúng.
Các kết quả của chương này được viết dựa theo [6]. Chú ý rằng vì R là vành
đa thức lấy hệ số trên trường k nên theo các kết quả của chương 1 ta không phân
biệt các khái niệm rad, m-rad, bất khả quy và m-bất khả quy.
2.1 Đơn thức chuẩn cực đại, đế và sự phân tích
Trong phần này ta sẽ tìm hiểu về đơn thức chuẩn cực đại, đế và mối quan hệ
giữa chúng. Cho I là iđêan đơn thức và min(I) là tập các phần tử sinh rút gọn của
I.
18
I, m Định nghĩa 2.1.1. Đơn thức m được gọi là đơn thức chuẩn của I nếu m / ∈ I với i = 1, . . . , n. I và mxi được gọi là đơn thức chuẩn cực đại của I nếu m / ∈ ∈
Tập các đơn thức chuẩn cực đại ký hiệu là msm(I).
Nhận xét 2.1.2. Tập các đơn thức chuẩn cực đại msm(I) chính là tập các phần tử
góc trong Định nghĩa 1.4.6.
Ví dụ 2.1.3. (i) Cho iđêan đơn thức I = (x6, x5y2, x2y4, y6). Khi đó tập chuẩn cực x5y, x4y3, xy5 I đại msm(I) = { và x5y.y = x5y2 vì theo định nghĩa các đơn thức x5y, x4y3, xy5 / ∈ I. Tương tự đối với các đơn thức x4y3, xy5. } I, x5y.x = x6y ∈ ∈
(ii) Cho iđêan đơn thức J = (x5y2, x2y4). Tương tự (i), ta có msm(J) = x4y3 { . }
y6
x2y4
x2y4
q xy5
x5y2
x5y2
q x4y3
q x4y3
q
x5y
x6
Hình 2.1:
x, x2, x3, x4, y, xy, x2y, x3y, x4y { S. K, với mọi đơn thức mi (iii) Cho iđêan đơn thức K = (x5y2). Khi đó ta có msm(K) = /0. Thật vậy, nếu gọi tập các đơn thức không thuộc K là S thì ta có S = . } Tuy nhiên, ta thấy mix / ∈ ∈ K và miy / ∈ Ta có thể kiểm tra bằng cách quan sát đồ thị Hình 2.1 .
Cho R là vành giao hoán, Noether, M là R-môđun. Nhắc lại rằng, đế của một
môđun M, ký hiệu là Soc(M) là môđun con của M
N là môđun con đơn của M Soc(M) = | . }
(cid:229) N { Nếu (R, m, k) là vành giao hoán, Noether, địa phương thì
Soc(M) = 0 :M m ∼= HomR(k, M).
Trên vành đa thức R = k[x1, . . . , xn], cho tập các phần tử sinh rút gọn min(I),
theo định nghĩa đế và tập đơn thức chuẩn cực đại, ta có
Soc(R/I) = 0 :R/I (x1, . . . , xn)
19
= mxi | I, i = 1, . . . , n } ∈ m = m + I { m + I { msm(I) . } ∈ |
Do đó đế của R/I là một không gian véc tơ hữu hạn chiều và khi đó ta có tập
m lập thành một cơ sở của đế. Vì thuật toán Slice cho phép msm(I) } ∈ | m + I { tính tập các đơn thức chuẩn cực đại msm(I) nên để tìm phân tích bất khả quy
6
irr(I) ta có thể quy về việc tính tập msm(I). Ta đã biết rằng, nếu J là iđêan đơn thức của R sao cho m-rad(J) = X thì theo Định lý 1.4.8 có thể tính phân tích bất khả quy irr(J) bằng cách dùng các phần tử góc (hay chuẩn cực đại). Tuy nhiên, = X thì ta có thể cộng vào J một iđêan đơn thức m-bất khả quy K sao nếu m-rad cho m-rad(J + K) = X và có thể áp dụng các kết quả ở Mệnh đề 1.3.10 và Định lý 1.3.12 để tìm irr(J + K) rồi sau đó sẽ tìm được irr(J).
Bây giờ ta sẽ mô tả ngắn gọn kỹ thuật của Bayes và cộng sự [1], Miller và
0 là số nguyên đủ lớn Sturmfels [4] để tính irr(I) thông qua msm(I). Chọn t ≫ và định nghĩa
i
f (xm) = (xmi+1 mi + 1 < t). |
n)) vào
1, . . . , xt
là một song ánh từ tập msm(I + (xt
Mệnh đề 2.1.4. ([4]). Ánh xạ f tập irr(I).
i
1
)R. Nếu ta ký hiệu ∈ , . . . , xmn+1 n | PRt ( f ) = (xmi+1 c Cho f = X m với m f là PR( f ) = (xm1+1 thì ⊆ và
Nn. Khi đó theo Định nghĩa 1.4.1, iđêan tham số ứng với mi + 1 < t) PR( f ). Ví dụ, cho R = k[x, y, z, w], ta có PR(x5y2z3w) = (x6, y3, z4, w2) PRt ( f ) c PR6(x5y2z3w) = (y3, z4, w2) khi chọn t = 6. Để chứng minh mệnh đề trên, ta c cần bổ đề sau:
n), với t
1, . . . , xt
0 sao ≫
m j=1
thì z1, . . . , zm { }
m j=1PR(z j). Vì thế I
∩ Bổ đề 2.1.5. Cho I là iđêan đơn thức của R và X t = (xt cho các đơn thức sinh của I đều chứa lũy thừa thực sự nhỏ hơn t. Khi đó nếu tập các đơn thức chuẩn cực đại của I + X t là msm(I + X t) = PRt (z j) là một phân tích tham số rút gọn của I. I = c
⊆ ∩ Chứng minh. Chú ý rằng vì m-rad(I + X t) = X nên theo Định lý 1.4.8, ta có phân tích tham số rút gọn của I + X t là I + X t = PR(z j), với mọi j. Nhưng vì các đơn thức sinh của I chứa các lũy thừa thực sự nhỏ hơn t nên
m j=1
I ⊆ ∩ PRt (z j), với mọi j. Do đó I PRt (z j). ⊆ c c Ngược lại, lấy một đơn thức sinh bất kỳ
j=1PR(z j) = I + X t. m
m j=1
20
f ⊆ ∩ ∈ ∩ PRt (z j) c
m j=1
Khi đó theo Mệnh đề 1.2.5, f là tích của các lũy thừa của xi, mỗi lũy thừa đều X t, thực sự nhỏ hơn t. Vì f là một đơn thức và I + X t là iđêan đơn thức nên f / ∈ do đó f I. Vậy I = ∈ ∩ PRt (z j). c Bây giờ, ta tiếp tục chứng minh mệnh đề. Theo Chú ý 1.4.5, vì mỗi phân tích
tham số rút gọn của I đều là phân tích bất khả quy rút gọn của I nên khi đó ta có
là ánh xạ cho bởi mỗi đơn n)) ứng với một thành phần bất khả
là song ánh. . Vì thế, ta định nghĩa f irr(I) = PRt (z j), j = 1, . . . , m { } c 1, . . . , xt thức chuẩn cực đại z j của msm(I + (xt quy của irr(I). Khi đó theo Bổ đề trên rõ ràng f
Để minh họa cho kết quả trên ta hãy xét một số ví dụ sau.
Ví dụ 2.1.6. (i) Cho I = (x2, xy) và chọn t = 3. Đặt I′ = I + (xt, yt) = (x2, xy, y3). Khi đó theo định nghĩa msm(I′) =
f . Ta xác định song ánh f như sau x, y2 } { : msm(I′) →
irr(I) (x2, y) 7→ (x) (x) (y2) 7→
Vì thế theo Mệnh đề 2.1.4, phân tích bất khả quy rút gọn của I là I = (x) (x2, y). ∩
(ii) Cho I = (xy3, x2y2) và chọn t = 4. Đặt I” = (I + (xt, yt)) = (x4, x2y2, xy3, y4). . Theo Mệnh đề 2.1.4, ta xác định song ánh f Khi đó msm(I”) = } x3y, xy2, y3 { như sau:
irr(I) →
7→
7→
f : msm(I”) (y3) (x3y) (xy2) (x) (y2) (x2, y3) 7→
Do đó ta có phân tích bất khả quy rút gọn của I là I = (x) (y2) (x2, y3). ∩ ∩
(iii) Cho J = (x6, x5y2, x2y4, y6), chọn t = 7. Đặt
J′ = (J + (xt, yt)) = (x6, x5y2, x2y4, y6).
21
xy5, x4y3, x5y { Ta có thể tính được msm(J′) = song ánh f , ta có phân tích bất khả quy của J là J = (x2, y6) . Tương tự các ý trên, áp dụng } (x6, y2). (x5, y4) ∩ ∩
2.2 Nhãn
N của đơn thức m ∈ được định nghĩa là m = xu = x Cho m là một đơn thức. Nhắc lại rằng véc tơ lũy thừa u u 1 n và degxi(xu ) := u i. 1 . . . xu n
min(I). Khi đó m ∈ Định nghĩa 2.2.1. Cho d là một đơn thức chuẩn của I và m là xi-nhãn cuả d nếu m dxi. |
i=1 mi.
Chú ý 2.2.2. (i) Nếu m là xi-nhãn của d thì degxi(m) = degxi(d) + 1. (ii) Một đơn thức d là chuẩn cực đại khi và chỉ khi nó có xi-nhãn mi, với mọi i = 1, . . . , n. Do đó trong trường hợp này dx1 . . . xn = lcmn
Ví dụ 2.2.3. Cho I = (x2, xz, y2, yz, z2).
(i) Ta có tập các đơn thức chuẩn cực đại của I là msm(I) = . } Xét đơn thức z z, xy { zx, yz là y-nhãn của z msm(I). Ta có xz là x-nhãn của z vì xz ∈ | vì yz zy và z2 là z-nhãn của z vì z2 zz. | | Đối với đơn thức xy ∈ | xyx, y2 là xyz msm(I). Ta có x2 là x-nhãn của xy vì x2 xyy và cả hai đơn thức xz, yz đều là z-nhãn của xy vì xz | | y-nhãn của xy vì y2 xyz. và yz |
(ii) Cho J := I + (xy). Khi đó msm(J) =
. Chú ý rằng mặc dù xy là x-nhãn x, y, z } { của y, là y-nhãn của x nhưng xy không là x-nhãn, y-nhãn và z-nhãn của z vì xy
không là ước của zx, zy và zz.
2.3 Thuật toán Slice
Trong mục này ta sẽ mô tả phiên bản cơ sở của thuật toán Slice. Thuật toán
Slice dùng để tính tập msm(I), trong đó I là iđêan đơn thức với tập sinh rút gọn
min(I) đã cho trước. Ý tưởng cơ bản của thuật toán Slice là quan tâm đến các tập
con của tập msm(I) được biểu diễn thành các slice. Thuật toán bắt đầu bằng cách
xem xét một slice đại diện cho tất cả các đơn thức chuẩn cực đại của msm(I).
Sau đó tách slice đó thành hai slice đơn giản hơn. Quá trình này tiếp tục cho đến
khi tách thành những slice đủ đơn giản để có thể dễ dàng tính được các đơn thức
22
chuẩn cực đại của chúng. Trước hết ta cần các kết quả sau.
C thì ta Bổ đề 2.3.1. Cho A, B,C là các iđêan đơn thức. Khi đó nếu A B = B ∩ ∩ có msm(A) C = msm(B) C. ∩
∩ Chứng minh. Lấy bất kỳ d msm(A) C. Ta cần chứng minh d msm(B) tức ∈ ∩ ∈ B. B và dxi
B là chứng minh d / ∈ ∈ Thật vậy, giả sử ngược lại d B. Khi đó d msm(A) ∈ ∩ ∈ A, suy ra ∈ B. Mặt khác vì d A, mâu thuẫn. Vậy d / ∈ ∈ ∈ C = B B. Khi đó ta có d C = A C, mà d ∩ msm(A) nên dxi msm(B), suy ra nên d / ∈ A dxi C, hay dxi ∈ ∩ ∩ ∈ ∈
C msm(A) msm(B) C. ∩ ⊆ ∩
C Tương tự msm(B) msm(A) C. Vậy msm(A) C = msm(B) C. ∩ ∩ ∩ ∩
⊆ Cho m là một đơn thức. Ta định nghĩa p (m) := . Ví dụ m √m
3x3
2x2
4 = x(0,0,1,2).
3x2
4) =
1x1
2x1
1x0
3x3 2x2 1x1 x0 4 qx0 3x3 2x2 1x1 4
p (x(0,1,2,3)) = p (x0 = x0
Mệnh đề 2.3.2. Cho I là một iđêan đơn thức và p là một đơn thức. Khi đó
(i) gcd(min(I)) gcd(msm(I)); |
(ii) msm(I) (p) = msm(I (p)); ∩
(iii) Nếu p ∩ gcd(min(I)) thì msm(I) = msm(I : p)p;
| (iv) msm(I) (p) = msm(I : p)p;
(v) msm(I) S). ∩ S = msm(I′) S, trong đó I′ = (m
\ Chứng minh. (i) Lấy d \ msm(I). Cho li, l j ∈ của d, trong đó i ∈ = j vì ta đã giả thiết n > 2. Theo Định nghĩa 2.2.1 ta có li p (m) / min(I) ∈ | ∈ min(I) lần lượt là các xi, x j-nhãn dxi | 6 và l j dx j.Từ đó ta có |
gcd(min(I)) gcd(li, l j) d gcd(xi, x j) d (do xi = x j). | | | 6
Vì d là một đơn thức bất kỳ của msm(I) nên suy ra gcd(min(I)) gcd(msm(I)). |
(ii) Đặt A = msm(I),C = (p), B = msm(I (p)). Khi đó theo Bổ đề 2.3.1, nếu
23
như ta có A C = B ∩ C thì suy ra msm(A) C = msm(B) C. Khi đó ta có ∩ ∩ ∩ ∩ (p) = msm(I msm(I) (p)) (p). Vật ta cần chứng minh msm(I (p)) (p). ∩ ∩ ∩ ∩ ⊆
Thật vậy, lấy d min(I ∈ | ∈ dxi suy ra p dxi (p)) sao cho li ∩ gcd(dx1, . . . , dxn) = d msm(I ∩ sao cho li = pli′ | (p)). Khi đó tồn tại li pli′ | . Ta có p | và tồn tại li′ nên d (p).Vậy msm(I (p)) (p). ∩ ⊆ ∈
(iii) Nếu p gcd(min(I)) thì theo (i) ta có p gcd(msm(I)). Lấy d msm(I). Ta | ∈ | có
p I d = msm(I) I, pxi d p d p ∈ p / ∈ ⇔ ∈
I : p I : p, xi d p d p d p / ∈ ⇔ ∈
Từ đó suy ra msm(I : p), suy ra d msm(I : p)p. Vậy msm(I) msm(I : p)p. d p ∈ ∈ ⊆
Ngược lại, bằng cách chứng minh tương tự ta cũng có msm(I : p)p msm(I). ⊆
(iv) Hiển nhiên ta có (I (p)) : p = I : p suy ra msm(I (p)) : p = msm(I : p). ∩ Mặt khác, vì p ∩ gcd(min(I (p)) nên msm(I (p)) = msm((I (p)) : p)p (theo | ∩ ∩ ∩ (iii)). Vì vậy
msm(I) (p) = msm(I (p)) = msm((I (p)) : p)p = msm(I : p)p, ∩ ∩ ∩
trong đó đẳng thức thứ nhất là theo (ii).
(v) Lấy d S ta cần chứng minh d S hay d msm(I) msm(I′) \ ∈ vậy, vì d ∈ \ msm(I) nên d / ∈ đó l S. Suy ra dxi I suy ra d / ∈ min(I′) do p (l) I′ do l ∈ | ∈ I′ do I′ ⊆ | msm(I′). Thật ∈ I. Lấy l là xi-nhãn của d. Khi dxi. d / ∈ ∈ | ∈ Vậy d dxi. Ta có l S. min(I) và l msm(I′) ∈ \ Ngược lại, lấy d S ta cần chứng minh d S hay chứng msm(I) msm(I′) ∈ \ ∈ \ minh d I. Mặt khác, giả sử d I, msm(I). Thật vậy vì dxi I nên dxi ∈ ∈ ∈ S điều này min(I′) sao cho m I′ ⊆ | m ∈ I. Vậy ta có min(I′) nên p (m) d vì m / ∈ S. Vậy điều giả sử là sai suy ra d / ∈ d / ∈ | | ∈ tồn tại m min(I) \ ∈ mâu thuẫn vì p (m) d S. msm(I) ∈ \
Tiếp theo ta sẽ đưa ra các định nghĩa slice, cái chứa của nó và làm thế nào để
tách chúng.
Định nghĩa 2.3.3. Một slice là bộ ba (I, S, q), trong đó I, S là các iđêan đơn thức
24
và q là một đơn thức.
Cái chứa của slice (I, S, q), ký hiệu con(I, S, q), được định nghĩa là
con(I, S, q) = (msm(I) S)q. \
Ví dụ 2.3.4. Cho I là một iđêan đơn thức bất kỳ. Lấy S = 0, q = 1. Khi đó cái
chứa của slice (I, 0, 1) là
con(I, 0, 1) = (msm(I) 0)1 = msm(I). \
Định nghĩa 2.3.5. Một slice (I, S, q) được gọi là chuẩn tắc nếu
p (min(I)) S = /0. ∩
Ví dụ 2.3.6. Cho I1 = (x6, x5y2, x2y4, y6), I2 = (x6, x5y2, y6), p = xy3.
Xét slice (I1, (p), 1). Ta có p (min(I1)) = p (x6, x5y2, x2y4, y6) = (x5, x4y, xy3, y5)
(p) = xy3 suy ra p (min(I1)) = /0. Vậy (I1, (p), 1) không là slice chuẩn tắc. ∩ 6
Xét slice (I2, (p), 1). Khi đó ta có p (min(I2)) = p (x6, x5y2, y6) = (x5, x4y, y5), (p) = /0. Vậy (I2, (p), 1) là slice chuẩn tắc. suy ra p (min(I2)) ∩
Ví dụ sau sẽ cho thấy các khái niệm trên được dùng như thế nào trong việc mô
tả các bước của thuật toán.
Ví dụ 2.3.7. Cho iđêan đơn thức I = (x6, x5y2, x2y4, y6), và đơn thức p = xy3. Qua đồ thị ở Hình 2.2 ta có thể tính được tập msm(I) = . Bây giờ ta sẽ } x5y, x4y3, xy5 { mô tả từng bước tính msm(I) để hình thành nên các bước của thuật toán. Hiển
nhiên ta có
(2.3.1) msm(I) = (msm(I) (p)) (msm(I) (p)). \ ∪ ∩
trong đó hợp là rời nhau.
Đặt I1 = I : p = (y3, xy, x4), suy ra msm(I1) = x3, y2 {
⊆ . Ta có thể thấy qua so } sánh Hình 2.2(a) và Hình 2.2(b) rằng I1 tương ứng là một phần của I nằm ở phía bên trong của (p). Điều này khiến ta dự đoán rằng msm(I1) msm(I) cũng tương ứng nằm ở phía bên trong của (p). Ta sẽ chứng tỏ rằng điều dự đoán này là
đúng. Trước hết ta có
25
(2.3.2) = msm(I) (p). msm(I1)p = x4y3, xy5 { } ∩
y6
y6
q
x2y4
... ... ... ... ... ...... ... . . . . . . . . . . . . . . . . . . . . . . . . . . . p
... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p
y3 q
x5y2
x5y2 q
xy
x4
x6
x6
q
(b)
(a)
(c)
Hình 2.2:
Bây giờ ta chỉ cần tính msm(I) \
x6, x5y2, y6 { (p). Chọn iđêan I2 gồm các đơn thức thuộc (được vẽ trong Hình } (được minh họa bởi ký hiệu q như trong hình). x5y, x4y5 { }
min(I) nhưng không thuộc (p). Vì thế I2 = 2.2(c)) và msm(I2) = Quan sát hình vẽ ta thấy đường nét đứt cho phép ta có thể bỏ qua những phần tử của min(I) nằm trong (p), đó là đơn thức x2y4. Sở dĩ ta chọn I2 vì
(2.3.3) (p) = = msm(I) (p). msm(I2) \ x5y { } \
Từ các đẳng thức 2.3.2 và 2.3.3 ta có thể tính được msm(I) thông qua msm(I1), msm(I2) và (p) như sau:
(p)) = msm(I) = (msm(I1)p) (msm(I2) ∪ \ xy5, x4y3, x5y { . }
Bây giờ chuyển sang ngôn ngữ của slice. Tách slice A = (I, (0), 1) thành hai slice "nhỏ" hơn là A1 = (I1, (0), p) và A2 = (I2, (p), 1). Theo Định nghĩa 2.3.3 và các Đẳng thức 2.3.2, 2.3.3 ta có
con(A) = con(I, (0), 1) = msm(I);
(p); con(A1) = con(I1, (0), p) = (msm(I1) (0))p = msm(I1)p = msm(I)
∩ (p) = msm(I) (p). con(A2) = con(I2, (p), 1) = (msm(I2) \ (p))1 = msm(I2) \ \
\ Vì thế, từ các đẳng thức trên và Đẳng thức 2.3.1, ta có thể chuyển việc tính tập
msm(I) sang việc tính cái chứa của nó như sau
26
con(A) = con(A1) con(A2), ∪
trong đó hợp là rời nhau.
Bây giờ cho một slice bất kỳ (I, S, q). Mục đích của ta là làm thế nào để tách
(I, S, q) thành hai slice đơn giản hơn sao cho cái chứa của (I, S, q) là hợp rời nhau
của hai cái chứa của hai slice sau khi tách. Để làm được điều này vấn đề đặt ra là
cần chọn được một đơn thức p gọi là đơn thức then chốt thỏa mãn kết quả sau:
Bổ đề 2.3.8. Cho một slice (I, S, q) và p là đơn thức then chốt. Khi đó
(2.3.4) con(I, S, q) = con(I : p, S : p, qp) con(I, S + (p), q). ∪
Chứng minh. Từ Đẳng thức 2.3.1 ta có
con(I, S, q) = con(I, S, q) (qp) con(I, S, q) (qp). \ ∪ ∩
Ta sẽ chứng minh
(2.3.5) con(I, S, q) (qp) = con(I, S + (p), q). \
(2.3.6) con(I, S, q) (qp) = con(I : p, S : p, qp). ∩
Từ Định nghĩa 2.3.3 để chứng minh Đẳng thức 2.3.5, ta chỉ cần chứng minh
(msm(I) S)q (qp) = (msm(I) S + (p))q. \ \ \
Thật vậy, lấy một đơn thức bất kỳ mq thuộc vế phải. Khi đó m msm(I) S + (p),
suy ra m \ qp hay vế (p). Do đó mq ∈ (msm(I) S)q msm(I) và m / ∈ S và m / ∈ ∈ ∈ \ \ phải nằm trong vế trái.
Ngược lại, lấy đơn thức bất kỳ lq thuộc vế trái. Khi đó lq (msm(I) S)q ∈ (qp). Suy ra l msm(I) (p). Vì thế l msm(I) \ S + (p) hay ∈ \ S và l / ∈ \ lq và lq / ∈ (msm(I) ∈ S + (p))q. Suy ra vế trái nằm trong vế phải. \ ∈ Tương tự, để chứng minh Đẳng thức 2.3.6, ta cũng chỉ cần chứng minh
(msm(I) S)q (qp) = (msm(I : p) S : p)qp. \ ∩ \
Thật vậy, lấy một đơn thức bất kỳ M thuộc vế trái. Khi đó ta có M = pqN
trong đó N = msm(I) S. Suy ra pN msm(I) S.Mà theo Mệnh \ (p) và pN / ∈ ∩ ∈ đề 2.3.2,(iv) ta có msm(I) (p) = msm(I : p)p. Suy ra pN msm(I : p)p và
27
S, hay ta có N ∩ msm(I : p) S : p. Vậy M ∈ (msm(I : p) S : p)qp. Suy ra pN / ∈ \ ∈ \ ∈ vế trái nằm trong vế phải.
Ngược lại, lấy đơn thức bất kỳ M′ thuộc vế phải. Ta có M′ = qpN′ suy ra S : p, suy ra \ p msm(I) msm(I : p) (S : p). Khi đó N′ ∈ msm(I : p)p và pN′ / ∈ ∩ (qp). Suy ra vế phải nằm trong vế trái. (msm(I) S)q ta có N′ ∈ pN′ ∈ và pN′ / ∈ msm(I : p) và N′ / ∈ S. Mà từ Mệnh đề 2.3.2, ta suy ra pN′ ∈ \ S, hay M′ ∈ ∩
Đẳng thức 2.3.4 là công cụ cơ bản của thuật toán slice và quá trình áp dụng nó
được gọi là quá trình tách then chốt. Đẳng thức 2.3.4 đề cập đến ba slice: slice
(I, S, q) gọi là slice hiện tại vì nó là slice đang cần tách; slice (I : p, S : p, qp) được
gọi là slice trong vì cái chứa của nó nằm bên trong (qp); slice (I, S + (p), q) được
gọi là slice ngoài vì cái chứa của nó nằm ngoài (qp).
Không phải hiển nhiên mà thấy được tại sao việc tính cái chứa của slice ngoài
lại dễ hơn việc tính cái chứa của slice hiện tại. Vấn đề mấu chốt của điều này là
đẳng thức đã được chứng minh trong Bổ đề 2.3.1 như sau:
(2.3.7) msm(I) S). S = msm(I′) S, trong đó I′ = (m \ \ ∈ p (m) / min(I) | ∈
Đẳng thức 2.3.7 kéo theo con(I, S, q) = con(I′, S, q). Nói cách khác ta có thể loại S (những đơn thức nằm trong phần bỏ những đơn thức m min(I) mà p (m) / ∈ ∈
S màu trắng trên Hình 2.2). Đẳng thức 2.3.7 sẽ tiếp tục được áp dụng cho đến khi p (min(I)) = /0. ∩ 6
Áp dụng các kết quả trên trong việc mô tả các bước của thuật toán, ta có thể
tính ví dụ sau.
Ví dụ 2.3.9. Cho I = (x4, x3y2, y5). Chọn đơn thức then chốt p = x. Khi đó theo Đẳng thức 2.3.4, ta có:
msm(I) = con(I, (0), 1) = con(I : x, 0 : x, x) con(I, (0) + (x), 1). ∪
Trước hết ta tính con(I : x, 0 : x, x). Vì ta có I : x = (x3, x2y2, y5), nên suy ra msm(I : x) = x2y, xy4 {
. Vậy } con(I : x, 0 : x, x) = (msm(I : x) 0)x = msm(I : x)x = \
. } (x)). Khi Tiếp theo ta tính con(I, (0) + (x), 1). Đặt I′ = (m ∈ x3y, x2y4 { p (m) / min(I) | ∈ (x) = /0. Suy (x) = msm(I′) \ \ đó I′ = (y5). Theo Đẳng thức 2.3.7 ta có msm(I) ra con(I, (x), 1) = (msm(I) (x))1 = msm(I) (x) = /0. Vậy \
28
msm(I) = \ x3y, x2y4 { . }
2.4 Slice cơ sở
Trước hết, ta nhắc lại một số khái niệm sau.
Định nghĩa 2.4.1. Đặt R = A[X1, . . . , Xn], trong đó A là một vành giao hoán bất kỳ.
[[R]] được gọi là không chứa bình phương nếu với i = 1, . . . , d
R được gọi là không chứa bình phương nếu ∈ { ⊆ (i) Đơn thức X n ∈ ta có ni . Iđêan đơn thức J 0, 1 } nó sinh bởi các đơn thức không chứa bình phương.
(ii) Sự rút gọn của đơn thức f = X n [[R]] là một đơn thức
i
Supp( f )
∈
∈ red( f ) = (cid:213) Xi.
Rõ ràng rằng red( f ) là tích của các biến chia hết f :
f
|
Xi. red( f ) = (cid:213) Xi
Ví dụ 2.4.2. (i) Đặt R = A[X,Y, Z]. Các đơn thức không chứa bình phương trong
R là 1, X,Y, Z, XY, XZ,Y Z, XY Z { . } (ii) Cho R = A[X,Y, Z] và f = (X 3Z4). Khi đó red( f ) = XZ.
i , tức là khi và chỉ khi f = red( f ).
(i) Đơn thức f [[R]] là không chứa bình phương nếu và chỉ nếu ∈ Chú ý 2.4.3. nó không chứa X 2
(ii) Iđêan đơn thức trong R là không chứa bình phương nếu và chỉ nếu các đơn
thức trong một dãy sinh đơn thức rút gọn là không chứa bình phương.
Định nghĩa 2.4.4. Một slice (I, S, q) là slice cơ sở nếu I là iđêan đơn thức không chứa bình phương hoặc nếu x1 . . . xn ∤ lcm(min(I)).
Mệnh đề 2.4.5. Nếu x1 . . . xn ∤ lcm(min(I)) thì msm(I) = /0.
Chứng minh. Giả sử msm(I) = /0 suy ra tồn tại d msm(I). Khi đó với mọi i tồn 6 tại m lcm(min(I)). ∈ min(I) sao cho m là xi-nhãn của d suy ra m ∈ | | m lcm(min(I)). dxi m. Từ đây ta có xi Mặt khác degxi(m) = degxi(d)+1 suy ra xi | | | Vậy điều giả sử là sai.
29
Mệnh đề 2.4.6. Nếu I là iđêan không chứa bình phương và I = (x1, . . . , xn) thì 6 ta có msm(I) = /0.
= /0 suy ra tồn tại d ∈ 6 min(I) sao cho mi là xi-nhãn của d, suy ra m ∈ | msm(I). Khi đó với mọi i tồn dxi. Mặt khác, ta lại có m. Mà I là iđêan không chứa bình phương nên |
Chứng minh. Giả sử msm(I) tại mi degxi(m) = degxi(d) + 1, suy ra xi degxi(m) = 1 suy ra mi = xi. Vậy I = (x1, . . . , xn) mâu thuẫn với giả thiết.
2.5 Sự kết thúc và sự lựa chọn then chốt
Trong mục này ta sẽ chỉ ra rằng một số ràng buộc trong việc lựa chọn đơn thức
then chốt sẽ tác động một cách hiệu quả đến việc đảm bảo cho thuật toán dừng.
Có bốn điều kiện để lựa chọn đơn thức then chốt p, trong đó hai điều kiện đầu
là đảm bảo cho thuật toán dừng, còn hai điều kiện cuối dùng để mở rộng thuật
toán cơ sở.
S: Nếu p S thì slice ngoài bằng slice hiện tại. ∈ • p p / ∈ = 1: Nếu p = 1 thì slice trong bằng slice hiện tại. • 6
• p I p / ∈ p (lcm(min(I))). |
• Một đơn thức then chốt thỏa mãn bốn điều kiện trên được gọi là đơn thức then
chốt hiệu lực. Mệnh đề sau cho thấy rằng một slice không phải là slice cơ sở thì
luôn có đơn thức then chốt hiệu lực.
Mệnh đề 2.5.1. Cho (I, S, q) là một slice chuẩn tắc và không tồn tại đơn thức
then chốt hiệu lực. Khi đó I là iđêan không chứa bình phương.
∈
∩ |
Chứng minh. Giả sử I là iđêan đơn thức chứa bình phương. Khi đó tồn tại xi và min(I) sao cho x2 m I. Mặt khác, do (I, S, q) là slice m. Điều này suy ra xi / i | ∈ chuẩn tắc nên theo định nghĩa ta có p (min(I)) p (m) nên suy ra S = /0, vì xi S. Vì thế xi thỏa mãn bốn điều kiện của đơn thức then chốt hiệu lực, mâu xi / ∈ thuẫn với giả thiết của mệnh đề. Vì thế, I là iđêan không chứa bình phương.
Mệnh đề 2.5.2. Việc lựa chọn đơn thức then chốt hiệu lực đảm bảo cho thuật
toán dừng.
Chứng minh. Ta sẽ chứng minh thuật toán dừng bằng cách sử dụng tính chất mọi
30
dãy tăng chặt các iđêan đều dừng trong vành Noether R = k[x1, . . . , xn]. Thật vậy,
cho A = (I, S, q) không là slice cơ sở và p là đơn thức then chốt hiệu lực. Ta tách A thành hai slice A1 = (I : p, S : p, qp) là slice trong và A2 = (I, S + (p), q) là slice ngoài. Cho f và g là các ánh xạ từ tập các slice vào tập các iđêan được định nghĩa
như sau:
f (I, S, q) = S và g(I, S, q) = (lcm(min(I))).
Ta sẽ chứng minh các khẳng định sau:
(i) f (A) f (A1); f (A) ( f (A2) ⊆
(ii) g(A) ( g(A1); g(A) = g(A2) Thật vậy, ta có f (A) = S S : p = f (A1). Mặt khác vì p là đơn thức then chốt ⊆
hiệu lực nên p / ∈ Tương tự, ta có I S. Do đó f (A) = S ( S + (p) = f (A2). I : p, suy ra lcm(min(I)) lcm(min(I : p)). Mặt khác vì ⊆ ⊆ A = (I, S, q) không là slice cơ sở nên theo Mệnh đề 2.4.5 ta có msm(I) = /0. Do 6 I với mọi đó tồn tại d msm(I) suy ra dxi ∈ lực nên p = 1, do đó pd ∈ I. Vậy d I : p mà d / ∈ ∈ ∈ 6
i. Vì p là đơn thức then chốt hiệu I nên suy ra I ( I : p. Vì vậy lcm(min(I)) ( lcm(min(I : p) suy ra g(A) ( g(A1). Tiếp theo, từ định nghĩa ánh xạ g ta có ngay g(A) = lcm(min(I)) = g(A2).
tương ứng thì f (A) f (A′), g(A) ⊆ ⊆ Từ các khẳng định trên, nếu cho A là một slice tùy ý và A′ là slice chuẩn tắc g(A′). Do đó f và g không bao giờ giảm, trong khi f là một dãy tăng chặt trên các slice ngoài thì g là một dãy tăng chặt
trên các slice trong. Do đó theo tính chất của vành Noether thì các dãy trên phải
dừng. Điều này có nghĩa là nếu cho một slice không phải là slice cơ sở thì sau
một số hữu hạn bước áp dụng các Đẳng thức 2.3.4 và 2.3.4 thì ta thu được một
slice cơ sở, hay thuật toán dừng.
2.6 Giả mã
Mục này cung cấp các câu lệnh trong lập trình máy tính để thực hiên thuật toán
Slice. Nội dung của mục này là thực hiện bộ giả mã của thuật toán của thuật toán
31
slice. Ý tưởng ở đây là theo Mệnh đề 2.5.1 và kiểm tra xem mỗi biến x1, . . . , xn có là đơn thức then chốt hiệu lực hay không. Nếu không có biến nào là đơn thức
then chốt hiệu lực thì I′ thu được trong đoạn câu lệnh dưới đây là không chứa bình phương.
S) function con(I, S, q) let I′ := (m ∈
p (m) / min(I) ∈ | if x1 . . . xn ∤ lcm(min(I′)) then return /0 if I′ is square free and I′ 6 if I′ is square free and I′ = (x1, . . . , xn) then return = (x1, . . . , xn) then return /0 q } { let p := selectPivot(I′, S)
return con(I′ : p, S : p, qp) con(I′, S + (p), q).
∪ Bây giờ ta sẽ giải thích các câu lệnh của thuật toán:
Bước 1: Đặt I′ := (m ∈
S p (m) / min(I) S). Vì theo Đẳng thức 2.3.4 và 2.3.7 | ∈ thay vì tính con(I, S, q) ta tính con(I′, S, q). Nói cách khác là loại bỏ những đơn S, cho đến khi p (min(I)) = /0. Khi đó xảy ra ba thức m min(I) mà p (m) / ∈ ∩ 6 ∈ trường hợp.
Trường hợp 1: nếu x1 . . . xn ∤ lcm(min(I′)) thì theo Mệnh đề 2.4.5 ta có
msm(I′) = /0.
= (x1, . . . , xn), thì theo Trường hợp 2: nếu I′ là không chứa bình phương và I′ 6 Mệnh đề 2.4.6 ta có msm(I′) = /0.
Trường hợp 3: nếu I′ là không chứa bình phương và I′ = (x1, . . . , xn), thì quay
trở lại q . } { Bước 2: Nếu không xảy ra các trường hợp đặc biệt trên thì ta sẽ chọn đơn thức
then chốt hiệu lực p = selectPivot(I′, S) và dùng công thức 2.3.4 để tách slice con(I′, S + (p), q). hiện tại thành hai slice đơn giản hơn là con(I′ : p, S : p, qp) ∪
Để thuật toán có thể dừng nhanh hơn thì chiến thuật chọn đơn thức then chốt
hiệu lực p là rất quan trọng. Dựa vào Đẳng thức 2.3.7 ta nên lựa chọn p sao cho
p (m) / min(I) ∈ | ∈
S) loại bỏ được càng nhiều các đơn thức trong iđêan I′ = (m min(I) càng tốt. Ta làm lại Ví dụ 2.3.7 nhưng thay vì chọn p = xy3 ta sẽ chọn p = x.
32
Ví dụ 2.6.1. Cho iđêan đơn thức I = (x6, x5y2, x2y4, y6), và đơn thức then chốt
p = x. Khi đó theo Đẳng thức 2.3.4 ta có:
msm(I) = con(I, (0), 1) = con(I : x, 0 : x, x) con(I, (0) + (x), 1). ∪
Trước hết ta tính con(I : x, 0 : x, x). Vì ta có I : x = (x5, xy4, x4y2, y6), nên suy ra msm(I : x) = x4y, x3y3, y5 { . Vậy }
con(I : x, 0 : x, x) = (msm(I : x) 0)x = msm(I : x)x = \ . }
(x)). Khi đó ∈ x5y, x4y3, xy5 { p (m) / min(I) | ∈ (x) = /0. Suy ra (x) = msm(I′) \ \ Tiếp theo ta tính con(I, (0) + (x), 1). Đặt I′ = (m I′ = (y6). Theo Đẳng thức 2.3.7 ta có msm(I) con(I, (x), 1) = (msm(I) (x))1 = msm(I) (x) = /0. Vậy \ \
msm(I) = x5y, x4y3, xy5 { . }
2.7 Cải tiến thuật toán cơ sở
Mục này dành để trình bày một số cải tiến cho phiên bản cơ sở của thuật toán
Slice đã được trình bày ở đầu chương.
2.7.1 Đơn thức chặn dưới của cái chứa slice
d, với Đơn thức ql được gọi là là đơn thức chặn dưới của slice (I, S, q) nếu ql | mọi d con(I, S, q), nghĩa là l d, với mọi d msm(I). Theo định nghĩa ta có ∈ ∈ |
con(I, S + (l), q) = (msm(I) S + (l))q = /0 \
vì mọi phần tử thuộc msm(I) đều thuộc S + (l). Vì thế nếu như ta thực hiện tách
trên l sao cho l d, với mọi d msm(I) thì slice ngoài bằng rỗng và theo đẳng ∈ | thức 2.3.4 ta có
con(I, S, q) = con(I : l, S : l, ql) con(I, S + (l), q) = con(I : l, S : l, ql). ∪ (2.7.8)
Đẳng thức 2.7.8 cho phép ta có thể chuyển từ việc tách trên con(I, S, q) về việc
tách trên con(I : l, S : l, ql). Điều này rõ ràng là hiệu quả hơn vì để tính con(I, S, q),
thay vì ta phải làm việc trên con(I : l, S : l, ql) và con(I, S + (l), q) thì nay ta chỉ
33
cần làm việc trên con(I : l, S : l, ql).
Trong khi Mệnh đề 2.3.2 cho ta một đơn thức chặn dưới đơn giản là gcd(min(I))
thì mệnh đề sau đây cung cấp cho ta một chặn dưới tổng quát hơn.
i=1 li, trong đó
Mệnh đề 2.7.1. Cho (I, S, q) là một slice và đặt l(I) = lcmn
gcd(min(I) (xi)). li = ∩ 1 xi
Khi đó ql(I) là đơn thức chặn dưới của (I, S, q).
d, với mọi d Chứng minh. Theo định nghĩa ta chỉ cần chứng minh l(I) msm(I). | ∈ Thật vậy, lấy bất kỳ d m, vì msm(I) và cho m là xi-nhãn của d. Khi đó ta có xi | m d và ta có điều phải chứng minh. thế lixi ∈ dxi. Suy ra li | | |
Ví dụ 2.7.2. Cho I := (x2y, xy2, yz, z2). Chứng minh rằng tập các đơn thức chuẩn cực đại msm(I) = xy {
. } Chứng minh. Áp dụng Mệnh đề 2.7.1 ta có
gcd(min(I) (x)) = y; l1 = ∩
gcd(min(I) (y)) = 1; l2 = ∩
gcd(min(I) (z)) = 1. l3 = 1 x 1 y 1 z ∩
Suy ra l(I) = lcm3 i=1 li = y. Vì msm(I) = con(I, (0), 1) nên áp dụng Đẳng thức 2.7.8 với S = (0) và q = 1, ta có thể thực hiện tách trên đơn thức chặn dưới
ql(I) = y, ta có
msm(I) = con(I, (0), 1) = con(I : y, (0), y),
trong đó I : y = (x2, xy, z). Tiếp tục, vì
gcd(min(I : y) (x)) = 1; l1 = ∩
gcd(min(I : y) (y)) = x; l2 = ∩
gcd(min(I : y) (z)) = 1 l3 = 1 x 1 y 1 z ∩
i=1 li = x. Vì thế, áp dụng Đẳng thức 2.7.8 một lần nữa với
34
nên ta có l(I : y) = lcm3
q = y, S = (0) và thực hiện tách trên đơn thức chặn dưới ql(I : y) = xy, ta có
con(I : y, (0), y) = con((I : y) : x, (0) : x, xy)
= con((x2, xy, z) : x, (0) : x, xy) = con((x, y, z), (0), xy)
= (msm(x, y, z) (0))xy = (1 (0))xy = \ \ xy { . }
Chúng ta có thể cải tiến chặn dưới bằng khái niệm xi-cực đại và sử dụng kết
quả sau đây.
Định nghĩa 2.7.3. Một đơn thức m msm(I) được gọi là xi-cực đại nếu ∈
0 < degxi(m) = degxi(lcm(min(I))). Ví dụ 2.7.4. Cho I := (x2y, xy2, yz). Khi đó lcm(min(I)) = x2y2z. Theo định nghĩa, ta có x2y là x-cực đại vì 0 < degx(x2y) = degx(x2y2z), xy2 là y-cực đại vì có cực đại vì 0 < degz(yz) = degy(x2y2z). 0 < degy(xy2) = degy(x2y2z) và yz là z −
msm(I) và m là xi-nhãn của d. Nếu m là x j-cực đại với biến
Bổ đề 2.7.5. Cho d ∈ x j nào đó thì xi = x j.
= x j và cho l là x j-nhãn của d. Khi đó dẫn đến 6 Chứng minh. Giả sử ngược lại xi điều vô lý
degx j(m) 6 degx j(d) < degx j(l) 6 degx j(lcm(min(I))) = degx j(m),
trong đó các bất đẳng thức được giải thích như sau:
Bất đẳng thức thứ nhất là do giả thiết m là xi-nhãn của d nên m |
6
∈ dxi, suy = x j nên lũy thừa lớn nhất của ra tồn tại h sao cho dxi = mh. Do ta giả sử xi x j trong m phải nhỏ hơn hoặc bằng lũy thừa lớn nhất của x j trong d, hay ta có degx j(m) 6 degx j(d). Bất đẳng thức thứ hai có được do l là x j-nhãn của d nên theo định nghĩa, degx j(l) = degx j(d) + 1. Mặt khác, vì l min(I) nên bất đẳng thức thứ ba thỏa mãn. Đẳng thức cuối cùng là do định nghĩa x j-cực đại.
Bổ đề 2.7.5 cho phép ta chuyển từ việc tính tập chuẩn cực đại của iđêan đơn
thức I về việc tính tập chuẩn cực đại của iđêan đơn thức I sau khi đã loại bỏ bớt
35
các đơn thức xi-cực đại theo hai biến phân biệt trong tập các phần tử sinh rút gọn min(I).
min(I) là xi-cực đại theo hai biến phân biệt thì ta có ∈ m Hệ quả 2.7.6. Nếu m msm(I) = msm(I′), trong đó I′ = (min(I) ). } \ {
msm(I). Ta chứng minh msm(I) msm(I′). ⊆ ⊆ Chứng minh. Dễ thấy msm(I′) Thật vậy, lấy bất kỳ d ∈ = m msm(I). Ta xét hai trường hợp: - Trường hợp 1. Nếu tồn tại hi sao cho dxi = mihi, với mọi i thỏa mãn mi 6 m thì vì I′ = (min(I) msm(I′) hay msm(I) msm(I′). ) nên d } \ { ∈ ⊆
giả thiết tồn tại j - Trường hợp 2. Nếu tồn tại h sao cho dxi = mh thì m là xi-nhãn của d. Theo = i sao cho m là x j-cực đại. Suy ra xi = x j theo Bổ đề 2.7.5, 6 điều này mâu thuẫn. Vậy trường hợp này không thể xảy ra.
Hệ quả sau đây cho ta một cải tiến hơn nữa trong việc giảm bớt các bước của
thuật toán tìm đơn thức chặn dưới ql.
Hệ quả 2.7.7. Cho (I, S, q) là một slice và đặt li := gcd(Mi), trong đó 1 xi
min(I) Mi := xi là ước của m và m không là x j cực đại với xi = x j | . } 6
m { ∈ Khi đó q(lcmn − i=1 li) là một đơn thức chặn dưới của (I, S, q).
| Chứng minh. Theo định nghĩa, ta cần chứng minh li vì d ∈ min(I). Vì d, với mọi i. Thật vậy, I, với mọi i. Do đó tồn tại các đơn thức hi sao cho )hi, với mọi mi msm(I) nên dxi dxi = mihi, suy ra d = ( ∈ ∈ mi xi
dx j = m jh j = ( hi)x j mi xi
nên nếu mi có lũy thừa lớn nhất theo biến x j thì degx j(m j) = degx j(mi) + 1, điều = xi hay ta có này dẫn đến mâu thuẫn. Vậy mi không là x j-cực đại với mọi x j 6 d, hay ta có điều cần chứng ) gcd(Mi), nên ( Mi. Do cách đặt li := mi | 1 xi mi xi d. ∈ minh li |
Ví dụ 2.7.8. (i) Cho I := (xy, x2, y2). Khi đó
36
Mx = xy, x2; My = xy, y2.
(ii) Áp dụng Hệ quả 2.7.7 cho Ví dụ 2.7.2 với I := (x2y, xy2, yz, z2), ta có
Mx = x2y lx = 1 x
gcd(xy2, yz) = 1 → My = xy2, yz ly = gcd(x2y) = xy 1 y →
gcd(yz) = y Mz = yz, lx = 1 z →
Khi đó đơn thức chặn dưới của Slice (I, (0), 1) là:
q(lcm(lx, ly, lz)) = 1(lcm(xy, 1, y)) = xy { . }
Rõ ràng rằng trong Ví dụ 2.7.2, ta phải qua hai bước mới tìm được đơn thức chặn
dưới xy { , trong khi đó nếu áp dụng Hệ quả 2.7.7, ta chỉ cần một bước. }
Ta có thể tính toán đơn thức chặn dưới một cách chính xác hơn bằng cách định nghĩa M(i, j) và tính ước chung lớn nhất của một cặp các đơn thức sinh rút gọn sao cho chúng đồng thời tương ứng là các xi-nhãn và x j-nhãn. Tuy nhiên, việc mở rộng như vậy làm tăng độ chính xác nhưng cũng đồng thời làm tăng độ phức
tạp của thuật toán. Hơn nữa, nếu ta mở rộng từ hai biến thành n biến thì ta sẽ tìm
được chặn dưới chính xác, nhưng độ phức tạp của việc tính toán lại ngang bằng
với việc ta phải tính chính tập msm(I).
Hệ quả 2.7.6 và Hệ quả 2.7.7 cho phép ta làm cho slice đơn giản hơn mà không
cần phải thay đổi cái chứa của nó, và quá trình này được lặp lại cho đến khi đạt
được đến một điểm cố định. Ta gọi quá trình này là đơn giản hóa (simplification)
và slice được gọi là đơn giản hết mức (fully simplified) nếu nó đạt được đến điểm
cố định của quá trình. Mệnh đề sau đây là một ví dụ về quá trình đơn giản hóa
mở rộng như thế nào để đạt được slice cơ sở.
Mệnh đề 2.7.9. Cho A := (I, S, q) là một slice đơn giản hết mức. Nếu min(I) | 6 n | thì A là một slice cơ sở.
Chứng minh. Theo Hệ quả 2.7.6, nếu đơn thức m là xi-cực đại của hai biến thì ta có thể xóa bỏ nó khỏi min(I). Điều này có nghĩa là mỗi đơn thức thuộc min(I) chỉ có thể là xi-cực đại của nhiều nhất là một biến xi nào đó. Vì mỗi biến đều xuất hiện một lũy thừa cực đại trong một đơn thức sinh nào đó nên với mỗi chỉ số i, tồn
37
tại một đơn thức mi min(I) sao cho mi là xi-cực đại. Do đó tất cả các đơn thức ∈
min(I) m1, . . . , mn { | mi, . . . , mn là phân biệt. Vì theo giả thiết Do đó Mi = 6 n nên min(I) = . } | , trong đó Mi được định nghĩa như trong Hệ quả 2.7.7. Hơn nữa, } mi { vì theo giả thiết A là slice đơn giản hết mức nên gcd(Mi) = 1, vì thế mi = xi, 1 xi do đó ta có điều phải chứng minh.
Với lập luận giống như lập luận trong chứng minh của Mệnh đề 2.7.9, ta có
thể chỉ ra rằng (I, S, q) là slice cơ sở nếu như tất cả các phần tử của min(I) đều là
cực đại. Nếu có đúng một phần tử m min(I) là không cực đại thì ta có thể xây ∈ dựng một slice cơ sở mới cho thuật toán bằng cách tìm ra khả năng của phần tử
m. Ta cũng có thể làm tương tự như vậy cho trường | N. Tuy nhiên độ phức sinh đó là xi-nhãn với mỗi xi hợp có k phần tử thuộc min(I) không là cực đại, với k ∈ tạp của việc tính toán sẽ tăng theo hàm mũ theo k, do đó thời gian tính toán sẽ rất
chậm nếu như k đủ lớn.
2.7.2 Tách độc lập
Trong mục này ta định nghĩa khái niệm I-độc lập và chỉ ra rằng khái niệm
này sẽ cho phép ta thực hiện việc tách hiệu quả hơn như thế nào. Nội dung của
mục này đã được xây dựng dựa trên một kỹ thuật tương tự trong việc tính chuỗi
Hilbert-Poincaré được giới thiệu bởi Bayer và Stillman (1992) và được mô tả chi
tiết hơn bởi Bigatti (1993).
Định nghĩa 2.7.10. Cho A, B là các tập khác rỗng rời nhau sao cho khi đó ta có
A B = (B) = /0. (A) x1, . . . , xn { . Vậy A và B được gọi là I-độc lập nếu min(I) } ∩ ∩
∪ Nói cách khác, A và B là I-độc lập nếu không có phần tử nào thuộc min(I) là
ước của cả biến trong A lẫn biến trong B.
Mệnh đề sau đây cho ta cách tính tập msm(I). Quá trình áp dụng Mệnh đề
2.7.11 được gọi là tách độc lập.
Mệnh đề 2.7.11. Nếu A, B là I-độc lập thì
msm(I) = msm(I k[A]). msm(I k[B]). ∩ ∩
38
k[A]) và B′ = msm(I ∩ k[B]). Khi đó nếu A′ = (0) = /0. Chứng minh. Đặt A′ = msm(I ∩ thì msm(I) = /0 theo Mệnh đề 2.4.5. Vì thế ta có thể giả sử rằng A′ 6 = /0 và B′ 6
Ta có đẳng thức
min(I) = min(A′) min(B′)
nên với các đơn thức a k[A] và b ∪ k[B] ta có ∈ ∈
ab I nếu và chỉ nếu a A′ hoặc b B′ ∈ ∈ ∈
và vì thế
B′. ab / ∈ I nếu và chỉ nếu a / ∈ A′ và b / ∈
Điều này suy ra
ab A B msm(I) I và abxi I với xi ∈ ⇔ ∪ ∈ B ab / ∈ A′ và axi ∈ A′ với xi B′ và bxi B′ với xi ∈ ⇔ a / ∈ A và b / ∈ ∈ ∈ a msm(A′) và b ∈ msm(B′). ∈ ⇔ ∈
và là I-độc lập. x, y { } và Ví dụ 2.7.12. Cho I = (x4, x2y2, y3, z2, zt,t2). Khi đó z,t { Điều này có nghĩa là ta có thể tính msm(I) một cách độc lập với } x, y { } z,t { . } Áp dụng Mệnh đề 2.7.11, ta có
msm(I) = msm(I k[x, y]). msm(I k[z,t]) = ∩ ∩ x3y, xy2 { z,t . { } } = x3yz, x3yt, xy2z, xy2t { . }
Cho slice (I, S, q), một vấn đề đặt ra là ta sẽ làm gì với S trong khi A, B là I-độc
lập nhưng không là S-độc lập. Có hai cách để vượt qua vấn đề trên. Cách thứ nhất
là chỉ dùng các đơn thức then chốt là các lũy thừa thuần túy, trong đó S sẽ được
sinh bởi các lũy thừa thuần túy, vì thế cứ mỗi hai tập các biến đều là S-độc lập.
Cách thứ hai là chỉ thực hiện tách độc lập khi cả hai tập vừa là I-độc lập, vừa là
S-độc lập.
Mệnh đề 2.7.11 cho ta cách tách slice (I, S, q) trong trường hợp S = (0) và
q = 1. Bây giờ ta quan tâm đến việc tính con(I, S, q) trong trường hợp tổng quát.
Ta cũng có thể thực hiện với tập không là S-độc lập theo cách trực tiếp hơn. Đầu
tiên ta bỏ đi các phần tử của tập min(S) (A) (B) từ min(S) khi thực hiện tách ∩ ∩ độc lập. Tiếp đó ta lại bỏ đi những đơn thức chuẩn cực đại đã được tính toán đó
39
mà nằm trong tập (min(S) (A) (B)). ∩ ∩
và B =
z,t { (z,t) = y2z } (x, y) (A) ∩ ∩ ∩ ∩ 6
Ví dụ 2.7.13. Cho iđêan I = (x4, x2y2, y3, z2, zt,t2) như trong Ví dụ 2.7.12 và cho S = (x3y, y2z). Ta sẽ tính con(I, S, 1). Đặt A = x, y . Theo định { } = /0 nên (B) = /0 và min(S) nghĩa, vì ta có min(I) A, B là I-độc lập nhưng không là S-độc lập. Tuy nhiên nếu ta bỏ đơn thức y2z ra khỏi S và đặt S′ = (x3y) thì A, B lại là S′-độc lập. Vì thế ta có thể tách độc lập trên slice (I, (x3y), 1) và tính được
(x3y))1 = = con(I, S′, q) = con(I, (x3y), 1) = (msm(I) \ z,t . { } } xy2z, xy2t { . }
xy2 { Sau đó bằng cách bỏ (y2z) ra khỏi tập trên ta tính được
40
con(I, S, q) = con(I, (x3y, y2z), 1) = xy2t { . }
KẾT LUẬN
Tóm lại, luận văn đã trình bày và chứng minh chi tiết một phần kết quả trong
bài báo "The Slice Algorithm for irreducible decomposition of monomial ideals"
cuả B. H. Roune đăng trên tạp chí Journal of Symbolic Computation năm 2009.
Kết quả chính của luận văn là trình bày các nội dung sau:
- Nhắc lại một số kiến thức về iđêan đơn thức: đồ thị của iđêan đơn thức; các
phép toán trong iđêan đơn thức như là phép toán giao, chia, căn, ...; iđêan đơn
thức bất khả quy và sự phân tích bất khả quy; phân tích tham số của iđêan đơn
thức, ...
- Trình bày các khái niệm: tập đơn thức chuẩn cực đại , nhãn, slice và cái chứa
của nó, đơn thức then chốt, ...
- Phân tích các bước để xây dựng thuật toán Slice dùng để tính tập đơn thức
chuẩn cực đại.
41
- Một số mở rộng của thuật toán cơ sở như: đơn thức chặn dưới, tách độc lập.
Tài liệu tham khảo
[1] Bayes D., Peeva I., Sturmfels B, (1998), "Monomial resolution", Mathematical
research Letters, 5 (1-2), 31-46.
[2] Gao,
S.,
Zhu, M.,
(2005),
"Irreducible
decomposition
of
SIGSAM Bulletin
monomial
ideals",
39
(3),
99-99.
URL:
http://portal.acm.org/citation.cfm?id=1113458.
[3] Jarrah, A.S., Laubenbacher, R., Stigler, B.,Stillman, M., (2006), "Reverse-
engineering of polynomial dynamial systems" , Advances in Applied Mathematics.
[4] Miller, E., Sturmfels, B., (2005), "Combinatorial Commutative Algebra", Gradu-
ate Texts in Mathematic , vol. 227, Springer.
[5] Rogers M.,
(2013), "Monomial
ideals and their decompositions", URL:
http://math.misouristate.edu/43628.htm.
[6] Roune B. H., (2009), "The Slice Algorithm for irreducible decomposition of
monomial ideals", Journal of Symbolic Computation, 44, 358-381.
[7] Roune B. H., (2008), "Solving thousand digrit Frobenius problems using
Grobner bases", Journal of Symbolic Computation, 43,(1), 1-7. URL:http:
www.broune.com.
[8] Sturmfels B., Sullivant S., (2006), "Combinatorial secant varieties", Pure and Ap-
plied Mathematics Quarterly, 2(3).
42
