ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐỖ NGỌC THỦY
CƠ SỞ GRÖBNER
VÀ GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC
LUẬN VĂN THẠC SỸ KHOA HỌC TOÁN HỌC
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐỖ NGỌC THỦY
CƠ SỞ GRÖBNER
VÀ GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC
LUẬN VĂN THẠC SỸ KHOA HỌC TOÁN HỌC
Chuyên ngành : Phương pháp toán sơ cấp
Mã số: 60.46.40
Người hướng dẫn khoa học:
PGS.TS. Tạ Duy Phượng
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Mục lục
Chương 1. Cơ sở Gröbner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1. Cấu trúc đại số cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1.1. Vành . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Ideal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3. Trường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
6
7
1.2. Vành đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.1. Đa thức và bậc đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2. Định lý Hilber về cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3. Đa thức một biến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.4. Iđêan đơn thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Cơ sở Gröbner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Thứ tự từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Một số thứ tự từ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3. Từ khởi đầu, đơn thức đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.4. Ideal khởi đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.5. Định nghĩa cơ sở Gröbner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.6. Thuật toán chia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.7. Tiêu chuẩn Buchberger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.8. Thuật toán Buchberger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
14
16
18
20
21
26
28
35
Chương 2. Hệ phương trình đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
2.1. Nghiệm của hệ phương trình đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
2.2. Cách giải hệ phương trình đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.3. Các hàm liên quan tới Gröbner của Maple . . . . . . . . . . . . . . . . . . . . . . . . .
49
Chương 3. Giải hệ phương trình đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
MỞ ĐẦU
Lý thuyết cơ sở Gröbner được nghiên cứu lần đầu tiên vào khoảng thập
kỉ 60 của thế kỉ 20, nó nhanh chóng trở thành hạt nhân của ngành Đại số
máy tính (Computer Algebra) và là một công cụ hữu hiệu trong rất nhiều
bài toán cơ bản của Đại số giao hoán, Hình học đại số. Dưới sự hướng dẫn
của Giáo sư Wolfgang Gröbner, năm 1965, Bruno Buchberger đã đưa ra
thuật toán Buchberger trong luận án tiến sĩ của mình. Điểm mấu chốt khởi
đầu cho sự hình thành lý thuyết của Buchberger chính là việc mở rộng
thuật toán chia hai đa thức một biến sang trường hợp các đa thức nhiều
biến. Cơ sở Gröbner về phương diện lý thuyết còn được khẳng định bằng
việc cung cấp chứng minh cho ba định lý của Hilbert: Định lý Hilbert về
cơ sở, Định lý Hilbert về xoắn và Định lý Hilbert về không điểm.
Trong các ứng dụng gần gũi nhất của lý thuyết cơ sở Gröbner, chúng tôi
quan tâm tới việc giải hệ phương trình đa thức. Thực chất việc tìm cơ sở
Gröbner của một hệ phương trình đa thức là đưa hệ phương trình ban đầu
về một hệ phương trình mới có dạng tam giác. Từ đó ta tìm được nghiệm
của hệ. Dưới góc độ của một giáo viên phổ thông, hy vọng đề tài này sẽ
đem đến cho chúng tôi cơ hội được học hỏi thêm nhiều hơn các công cụ
toán học hiện đại, góp phần soi sáng cho những nội dung liên quan trong
chương trình toán phổ thông.
• Luận văn Cơ sở Gröbner và giải hệ phương trình đa thức có mục đích
cung cấp cho giáo viên phổ thông, các em học sinh và những người
yêu toán một hướng tiếp cận mới, một công cụ giải hệ phương trình
đa thức, một phương pháp chung cho hầu hết các bài toán dạng này.
Luận văn cũng cung cấp cho người sử dụng một số hàm quan trọng
2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
trong Maple liên quan tới cơ sở Gröbner.
• Luận văn gồm ba Chương.
• Chương 1: Trình bày tổng quan lý thuyết cơ sở Gröbner.
• Chương 2: Trình bày điều kiện có nghiệm và cách giải tổng quát hệ
phương trình đa thức.
• Chương 3: Trình bày một số hệ phương trình đa thức được giải dựa
vào cơ sở Gröbner và các hàm liên quan tới cơ sở Gröbner trong
Maple.
Luận văn được hoàn thành dưới sự hướng dẫn của PGS TS Tạ Duy
Phượng. Tác giả xin bày tỏ lòng kính trọng và biết ơn thầy hướng dẫn đã
tận tình giúp đỡ tác giả trong suốt quá trình tập dượt nghiên cứu và viết
luận văn.
Tác giả xin trân trọng cảm ơn các thầy cô giáo trường Đại học khoa
học - Đại học Thái Nguyên và các thầy cô giáo Viện Toán học đã tận tâm
giảng dạy và giúp đỡ tác giả hoàn thành khóa học.
Đồng thời tác giả xin chân thành cảm ơn Trường THPT Bạch Đằng Hải Phòng, nơi tác giả đang công tác, các đồng nghiệp, gia đình và bạn
bè đã động viên, giúp đỡ và tạo điều kiện về mọi mặt trong quá trình học
tập.
Thái Nguyên, tháng 07 năm 2012
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Chương 1
Cơ sở Gröbner
1.1.
Cấu trúc đại số cơ bản
1.1.1.
Vành
Định nghĩa 1.1.1 Vành là một tập hợp R 6= 0/ được trang bị phép toán
cộng “+”: (a, b) 7→ a + b và phép toán nhân “.”: (a, b) 7→ a.b thỏa mãn các
tính chất sau:
(i) Đối với phép cộng, R là một nhóm giao hoán.
(ii) Phép nhân có tính kết hợp, tức là với mọi a, b, c ∈ R:
a. (b.c) = (a.b) .c
(iii) Phép nhân có tính chất phân phối đối với phép cộng, tức là a, b, c ∈ R:
a. (b + c) = a.b + a.c và (b + c) .a = b.a + c.a.
Phần tử "không" của vành được kí hiệu là 0. Để cho tiện, thông
thường ta viết ab thay cho tích a.b. R được gọi là vành có đơn vị nếu nó
chứa phần tử 1 thỏa mãn a1 = 1a = a với mọi a ∈ R. Khi cần nhấn mạnh
vành R ta dùng kí hiệu 0R , 1R để chỉ các phần tử không và đơn vị của R.
Vành R được gọi là vành giao hoán nếu với mọi a, b ∈ R, ab = ba. Trong
luận văn này ta chỉ xét đến vành giao hoán, có đơn vị. Do đó vành luôn
hiểu theo nghĩa này.
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Ví dụ :
1. Tập số nguyên Z, số thực R, số phức C, với các phép cộng và
phép nhân thông thường lập thành các vành. Tuy nhiên tập N không phải
là vành.
2. Tập R [x] các đa thức một biến x với hệ số thực lập thành một vành.
Định nghĩa 1.1.2 Cho R là một vành và a ∈ R. Phần tử a được gọi
là:
(i) ước của không nếu a 6= 0 và tồn tại 0 6= b ∈ R sao cho ab = 0.
(ii) khả nghịch (hoặc đơn vị) nếu tồn tại c ∈ R sao cho ac = 1.
Vành R không chứa ước của 0 được gọi là miền nguyên.
Ví dụ :
Vành Z là miền nguyên với hai phần tử đơn vị là 1 và −1.
Định nghĩa 1.1.3 Giả sử R là một vành, A là một bộ phận ổn định
của R đối với hai phép toán trong R nghĩa là x + y ∈ A và xy ∈ A với mọi
x, y ∈ A. A là một vành con của vành R nếu A cùng với hai phép toán cảm
sinh trên A là một vành.
Định lý 1.1.4 Giả sử A là một bộ phận khác rỗng của vành R. Các
điều kiện sau đây là tương đương:
(i) A là một vành con của vành R.
(ii) Với mọi x, y ∈ A, x + y ∈ A, xy ∈ A, −x ∈ A.
(iii) Với mọi x, y ∈ A, x − y ∈ A, xy ∈ A.
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1.1.2.
Ideal
Định nghĩa 1.1.5 Cho R là một vành. Tập con I 6= 0/ của R được gọi
là iđêan nếu hai điều kiện sau thỏa mãn:
(i) Với mọi a, b ∈ I, a + b ∈ I.
(ii) Với mọi a ∈ I và r ∈ R, ra ∈ I.
Ví dụ :
1. Mọi vành R đều chứa iđêan tầm thường I = 0 và chính nó I = R .
2. Tập nZ là các iđêan trong vành Z.
Định nghĩa 1.1.6 Ta gọi là đêan trái (iđêan phải) của một vành R, là
một vành con A của R thỏa mãn điều kiện xa ∈ A (ax ∈ A) với mọi a ∈ A
với mọi x ∈ R. Một vành con A của vành R gọi là một iđêan của R nếu và
chỉ nếu A vừa là iđêan trái, vừa là iđêan phải của R.
Định lý 1.1.7 Một tập A khác rỗng của một vành R là một iđêan của
R nếu và chỉ nếu các điều kiện sau thỏa mãn:
(i) a − b ∈ A với mọi a, b ∈ A.
(ii) xa ∈ A, ax ∈ A với mọi a ∈ A và mọi x ∈ X.
Ví dụ :
1. Tập {0} và X là hai iđêan của vành X.
2. Tập mZ gồm các số nguyên là bội của một số nguyên m cho trước.
Định lý 1.1.8 Giao của một họ bất kì những iđêan của một vành R là
một iđêan của R.
Định lý 1.1.9 Giả sử X vành giao hoán có đơn vị và a1 , a2 , ..., an ∈ X.
Bộ phận A của X gồm các phần tử có dạng x1 a1 + x2 a2 + ... + xn an với
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
x1 , x2 , ..., xn ∈ X là iđêan của X sinh bởi a1 , a2 , ..., an .
1.1.3.
Trường
Định nghĩa 1.1.10 Ta gọi trường là một miền nguyên R trong đó mọi
phần tử khác 0 đều có một nghịch đảo trong vị nhóm nhân R. Vậy một
vành R giao hoán, có đơn vị, có nhiều hơn một phần tử là một trường nếu
và chỉ nếu R\ {0} là một nhóm đối với phép nhân của R.
Ví dụ :
Tập hợp Q các số hữu tỉ cùng với phép cộng và phép nhân các số là
một trường. Ta cũng có trường số thực R và trường số phức C.
Định nghĩa 1.1.11 Giả sử X là một trường, A là một bộ phận của X
ổn định đối với hai phép toán trong X. A gọi là một trường con của trường
X nếu A cùng với hai phép toán cảm sinh trên A là một trường.
Định lý 1.1.12 Giả sử A là một bộ phận có nhiều hơn một phần tử
của một trường X. Các điều kiện sau đây là tương đương:
(i). A là một trường con của trường X.
(ii). Với mọi x, y ∈ A, x + y ∈ A, xy ∈ A, −x ∈ A, x−1 ∈ A nếu x 6= 0.
(iii). Với mọi x, y ∈ A, x − y ∈ A, xy−1 ∈ A nếu y 6= 0.
Ví dụ :
1 . X là một trường con của trường X. Bộ phận {0} không phải là
một trường con của X, vì theo định nghĩa một trường có ít nhất hai phần
tử.
2 . Trường số hữu tỉ Q là trường con của trường số thực R, bản thân
R lại là trường con của trường số phức C.
7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1.2.
Vành đa thức
1.2.1.
Đa thức và bậc đa thức
Cho R là một vành và x1 , x2 , ..., xn (n > 1) là các biến. Ta gọi đơn
thức là một biểu thức có dạng x1a1 ...xnan trong đó ai ∈ N, i = 1, .., n được gọi
là bộ số mũ của đơn thức. Nếu a1 = ... = an = 0 thì đơn thức được kí hiệu
là 1. Phép nhân trên tập các đơn thức được định nghĩa như sau
b1 b
a1
an
x1 ...xn
x1 ...xnn = x1a1 +b1 ...xnan +bn .
Từ là biểu thức có dạng αx1a1 ...xnan , trong đó α ∈ R gọi là hệ số của
từ. Hai từ khác không αx1a1 ...xnan và β x1a1 ...xnan là đồng dạng với nhau.
Để cho tiện ta kí hiệu x = (x1 , ...xn ) , a = (a1 , ..., an ) ∈ N n và
xa = x1a1 ...xnan . Đa thức n biến x1 , ..., xn trên vành R là một tổng hình thức
của các từ:
f (x) = ∑ αa xa ,
trong đó chỉ có hữu hạn hệ số αa 6= 0. Từ αa xa với αa 6= 0 được gọi là từ
của đa thức f (x) và xa là đơn thức của f (x).
Hai đa thức f (x) = ∑a∈N n αa xa và g (x) = ∑a∈N n βa xa được xem là
bằng nhau nếu αa = βa với mọi a ∈ N n .
Phép cộng đa thức được định nghĩa như sau:
!
!
∑n αaxa
a∈N
+
∑n βaxa
a∈N
=
∑n (αa + βa)xa.
a∈N
Vì αa + βa 6= 0 nếu một trong hai hệ số αa hoặc βa bằng 0, nên trong
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
biểu thức ở vế phải cũng chỉ có hữu hạn hệ số khác 0 và nó đúng là đa
thức.
Phép nhân đa thức được định nghĩa như sau:
!
!
∑ n αa x a
+
a∈N
trong đó γa =
∑
b,c∈N n ; b+c=a
∑ n βa x a
a∈N
=
∑ n γa x a ,
a∈N
αb βc .
Định nghĩa 1.2.1 Vành R [x1 , ..., xn ] xây dựng như trên được gọi là
vành đa thức n biến trên vành R.
Chú ý 1.2.2
1. Khi n = 1 ta có vành đa thức một biến thông thường. Đa thức một
biến x thường được viết dưới dạng
f (x) = an xn + ... + a1 x + a0 (n ∈ N, a0 , ..., an ∈ R) ,
2. Cho 0 6 m 6 n. Bằng cách xem mỗi từ αx1a1 ...xnan trên R như là
am+1
từ αx1a1 ...xnan xm+1
trên vành R [x1 , ..., xn ], có thể xem R [x1 , ..., xn ] như là
vành đa thức n − m biến xm+1 , ..., xn trên vành R [x1 , ..., xm ], tức là
R [x1 , ..., xn ] = R [x1 , ..., xm ] [xm+1 , ..., xn ] .
Với quan điểm trên có thể xây dựng vành nhiều biến (vô hạn biến
R [xi , i ∈ I]) từ vành một biến theo quy nạp. Tuy nhiên mỗi đa thức của
các vành đó vẫn là một đa thức hữu hạn biến.
3. Khi tập đa thức đã được xác định, ta chỉ kí hiệu đa thức đơn giản
là f , g... thay cho f (x) , g (x) ....
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Định nghĩa 1.2.3 Bậc tổng thể của đa thức f (x) = ∑ αa xa là số
a∈N n
deg f (x) = max {a1 + ... + an |αa 6= 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 gọi tắt là bậc, nếu như không
có sự hiểu nhầm nào xảy ra.
Chú ý 1.2.4
1. Bậc tổng thể của đa thức hằng là 0. Bậc tổng thể của đa thức 0
được quy ước là một số tùy ý.
2. Nhiều khi ta còn dùng bậc của đa thức đối với tập con các biến,
chẳng hạn {x1 , ..., xm }, được định nghĩa như sau:
degx1 ...xm f (x) = max {a1 + ... + am |αa 6= 0} ,
trong đó m < n cố định. Nói cách khác, đó là bậc tổng thể của đa thức f (x)
xét như đa thức của vành K [xm+1 , ..., xn ] [x1 , ..., xm ].
1.2.2.
Định lý Hilber về cơ sở
Định nghĩa 1.2.5 ChoR là một vành giao hoán, có đơn vị là 1. Các
điều kiện sau là tương đương:
(i) Mọi tập khác rỗng các iđêan của R đều có phần tử cực đại (đối với quan
hệ bao hàm).
(ii) Mọi dãy tăng các iđêan trong R
I1 ⊆ I2 ⊆ ... ⊆ In ⊆ In+1 ⊆ ...
là dừng, tức là tồn tại k để Ik = Ik+1 = ...
(iii) Mọi iđêan của R đều hữu hạn sinh, tức là với mọi iđêan I ⊆ R tồn tại
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
f1 , f2 , ..., fs ∈ I sao cho I = ( f1 , f2 , ..., fs ).
Một vành thỏa mãn một trong ba điều trên được gọi là vành Noether.
Định lý 1.2.6 (Định lý Hilbert về cơ sở). Cho R là vành Noether và x
là tập n biến. Khi đó vành R [x] cũng là vành Noether.
Hệ quả 1.2.7 Mọi iđêan của vành đa thức K [x] trên trường K là hữu
hạn sinh.
1.2.3.
Đa thức một biến
Định lý 1.2.8 (Định lý chia đa thức một biến) Cho K là một trường
và g (x) là đa thức khác 0 của K [x]. Khi đó mọi đa thức f ∈ K [x] có thể
viết dưới dạng
f (x) = q (x) .g (x) + r (x) ,
trong đó q (x) , r (x) ∈ K [x] và hoặc r (x) = 0 hoặc deg r (x) < deg f (x).
Hơn nữa q (x) và r (x) được xác định duy nhất.
Hệ quả 1.2.9 Vành đa thức K [x] trên một trường tùy ý là vành các
iđêan chính, nghĩa là mọi iđêan đều sinh bởi một đa thức.
Định nghĩa 1.2.10 Ước chung lớn nhất của các đa thức f1 , ..., fn ∈
K [x] là đa thức h sao cho:
(i) h chia hết f1 , ..., fn nghĩa là f1 = q1 g, ..., fn = qn g; q1 , ..., qn ∈ K [x].
(ii) Nếu h là đa thức khác chia hết f1 , ..., fn thì h chia hết g.
Trong trường hợp đó ta viết g = UCLN ( f1 , ..., fn ).
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Định nghĩa 1.2.11 Các đa thức f1 , ..., fn ∈ K [x] được gọi là nguyên
tố cùng nhau nếu UCLN ( f1 , ..., fn ) = 1.
Mệnh đề 1.2.12 Cho f1 , ..., fn ∈ K [x] , n ≥ 2. Khi đó:
(i) UCLN ( f1 , ..., fn ) tồn tại và duy nhất với sai khác một hằng số khác 0
của K.
(ii) ( f1 , ..., fn ) = (UCLN ( f1 , ..., fn )).
(iii) Nếu n ≥ 3 thì UCLN ( f1 , ..., fn ) = UCLN (UCLN ( f1 , ..., fn−1 ) , fn ).
Chứng minh. Xét Ideal I = ( f1 , ..., fn ). Theo hệ quả 1.2.8 tồn tại g ∈ K [x]
sao cho I = (g). Vì fi ∈ (g) , (i = 1, ..., n) nên fi chia hết cho g. Giả sử h
chia hết cho f1 , ..., fn , tức là f1 = q1 h, ..., fn = qn h, trong đó q1 , ..., qn ∈
K [x] . Vì g ∈ I nên tồn tại s1 , ..., sn ∈ K [x] sao cho:
g = s1 f1 + ... + sn fn .
Do đó
g = s1 f1 + ... + sn fn = s1 q1 h + ... + sn qn h = (s1 q1 + ... + sn qn ) h,
chia hết cho h. Như vậy g = UCLN ( f1 , ..., fn ). Nếu g0 là một ước chung
lớn nhất khác của f1 , ..., fn thì g và g0 chia hết lẫn nhau. Do đó chúng ta
phải có cùng bậc và g = λ g0 với 0 6= λ ∈ K. Đến đây các kết luận (i) và
(ii) được chứng minh.
Để chứng minh (iii), đặt g = UCLN ( f1 , ..., fn−1 )
Theo (ii) UCLN ( f1 , ..., fn−1 ) = ( f1 , ..., fn−1 ) ⇒ (g) = ( f1 , ..., fn−1 )
⇒ (g, fn ) = ( f1 , ..., fn−1 , fn ) .
Mặt khác, lại theo (ii) ta có:
( f1 , ..., fn−1 , fn ) = (UCLN ( f1 , ..., fn )) .
12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
(1)
Do đó (g, fn ) = (UCLN ( f1 , ..., fn )) .
(2)
Từ (1) và (2) ta suy ra
UCLN ( f1 , ..., fn ) = UCLN (g, fn ) = UCLN (UCLN ( f1 , ..., fn−1 ) , fn ) .
1.2.4.
Iđêan đơn thức
Định nghĩa 1.2.13 Iđêan I ∈ K [x] là iđêan đơn thức nếu có tập con
A ⊂ Nn (có thể vô hạn) mà ở đó I bao gồm tất cả các đa thức là tổng hữu
hạn của dạng hình thức ∑ ha xa trong đó ha ∈ K [x]. Trong trường hợp này,
a∈A
ta viết I
= (xa ; a
∈ A).
Một ví dụ của một iđêan đơn thức được cho bởi I = x2 y4 , x4 y3 , x5 y2 .
Bổ đề 1.2.14 Cho I = (xa ; a ∈ A) là iđêan đơn thức. Đơn thức xb ∈ I
khi và chỉ khi xb chia hết cho một đơn thức xa với a ∈ A nào đó.
Chứng minh. Nếu xb chia hết cho một đơn thức xa với a ∈ A thì xb ∈ I theo
định nghĩa của iđêan. Ngược lại nếu
xb
∈ I thì
xb
s
= ∑ hi .xa(i) , trong đó
i=1
hi ∈ K [x] và a (i) ∈ A.
Xem hi 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 mỗi từ của nó phải chia hết cho xa(i) nào đó. Sau khi giản ước,
một trong số từ đó còn lại và phải bằng xb . Vậy xb phải có tính chất của
những từ đó, tức là chia hết cho xa(i) nào đó.
Bổ đề 1.2.15 Cho I là iđêan đơn thức và f ∈ K [x]. Các điều kiện sau
là tương đương:
(i) f ∈ I.
(ii) Mọi từ của f thuộc I.
(iii) f là tổ hợp tuyến tính trên K của các đơn thức thuộc I.
13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Chứng minh. Rõ ràng ta có (iii) ⇒ (ii) ⇒ (i). Để chứng minh (i) ⇒ (iii)
ta cũng có nhận xét giống bổ đề trên, mỗi từ của f phải chia hết cho xa với
a ∈ A nào đó. Mà mọi đơn thức chia hết cho xa lại thuộc I. Do đó mỗi từ
của f là tích của một đơn thức thuộc I và một phần tử K, tức là có (c).
Như vậy mỗi iđêan đơn thức được xác định duy nhất bằng tập các đơn thức
của nó.
a
Bổ đề 1.2.16 (Bổ đề Dickson). Mọi
iđêan đơnthức I = (x ; a ∈ A)
bao giờ cũng viết được dưới dạng I = xa(1) , ..., xa(s) , trong đó
a (1) , ..., a (s) ∈ A. Nói riêng I là hữu hạn sinh.
1.3.
Cơ sở Gröbner
1.3.1.
Thứ tự từ
Định nghĩa 1.3.1 Giả sử X là một tập hợp, S là một bộ phận của
X × X, S được gọi là một quan hệ thứ tự (bộ phận) trong X nếu và chỉ nếu
các điều kiện sau đây thỏa mãn:
(i) (Phản xạ) Với mọi x ∈ X : xSx.
(ii) (Phản đối xứng) Với mọi x, y ∈ X : nếu xSy và ySx thì x = y.
(iii) (Bắc cầu) Với mọi x, y, z ∈ X : nếu xSy và ySz thì xSz.
Thông thường thứ tự bộ phận được kí hiệu bởi 6, >. Khi đó x 6 y
cũng được nói là “x nhỏ hơn hoặc bằng y”. Nếu S là một thứ tự bộ phận
thì quan hệ ngược
S−1 = {(x, y) |(y, x) ∈ S}
cũng là thứ tự bộ phận và gọi là thứ tự ngược của S. Nếu dùng 6 để kí hiệu
thứ tự từ thì > sẽ chỉ thứ tự ngược của nó.
Ta cũng sẽ dùng kí hiệu x < y để chỉ quan hệ x 6 y và x 6= y. Kí hiệu
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
x > y là thứ tự ngược của nó.
Khi trên tập X có một thứ tự bộ phận 6, ta nói X là tập được sắp (bộ
phận). Nếu x, y ∈ X mà x 6 y hoặc y 6 x thì ta nói x, y so sánh được với
nhau. Trong trường hợp ngược lại, x, y không so sánh được với nhau.
Quan hệ thứ tự 6 trên X được gọi là thứ tự toàn phần nếu mọi cặp
phần tử của X đều so sánh được với nhau. Khi đó ta nói tập X là tập được
sắp hoàn toàn.
Quan hệ chỉ thỏa mãn tính chất phản xạ và bắc cầu trong định nghĩa
trên được gọi là giả thứ tự (bộ phận, toàn phần).
Ví dụ
1. Quan hệ nhỏ hơn hoặc bằng thông thường trên R là một thứ tự
toàn phần.
2. Kí hiệu P (X) là tập tất cả các tập con của X. Quan hệ bao hàm ⊆
là thứ tự bộ phận trên P (X).
3. Quan hệ chia hết là thứ tự bộ phận trên N, nhưng chỉ là giả thứ tự
bộ phận trên Z.
Định nghĩa 1.3.2 Giả sử X là một tập hợp sắp thứ tự 6. Phần tử
a ∈ X gọi là phần tử tối tiểu (phần tử tối đại) nếu quan hệ x 6 a (x > a)
kéo theo x = a. Phần tử a ∈ X gọi là phần tử nhỏ nhất (phần tử lớn nhất)
của X nếu, với mọi x ∈ X, ta có a 6 x (x 6 a).
Phần tử b là chặn trên (chặn dưới) của X nếu với mọi a ∈ X ta có
a 6 b (b 6 a).
Tập X được gọi là tập sắp thứ tự tốt nếu nó được sắp hoàn toàn và
mọi tập con khác rỗng của nó có phần tử nhỏ nhất. Khi đó ta nói thứ tự
tương ứng là thứ tự tốt.
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Định nghĩa 1.3.3 Thứ tự từ 6 là một thứ tự toàn phần trên tập M tất
cả các đơn thức của K [x] thỏa mãn tính chất sau:
(i) Với mọi m ∈ M, 1 6 m.
(ii) Nếu m1 , m2 , m ∈ M mà m1 6 m2 thì mm1 6 mm2 .
Bổ đề 1.3.4 Mọi thứ tự toàn phần 6 trên M là thứ tự tốt khi và chỉ
khi mọi đơn thức thực sự giảm:
m1 > m2 > m3 > ...
sẽ dừng (sau hữu hạn phần tử).
Chứng minh. Nếu 6 không là thứ tự tốt thì tồn tại tập con A ∈ M không có
phần tử nhỏ nhất. Lấy m1 là phần tử tùy ý từ A. Vì A không có phần tử nhỏ
nhất nên tìm được m2 < m1 trong A. Tiếp tục như vậy sau khi tìm được n
đơn thức m1 > m2 > ... > mn trong A, ta lại tìm được mn+1 ∈ A sao cho
mn > mn+1 . Bằng quy nạp ta xây dựng được một dãy vô hạn các đơn thức
thực sự giảm.
Ngược lại, nếu có một dãy vô hạn các đơn thức thực sự giảm thì dãy đó
không có phần tử nhỏ nhất. Vì vậy thứ tự đã cho không phải là thứ tự tốt.
Bổ đề 1.3.5 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) trong Định nghĩa 1.3.3 là thứ tự từ.
1.3.2.
Một số thứ tự từ
Cho 6 là một thứ tự từ. Sau khi đổi chỉ số các biến luôn có thể giả thiết:
x1 > x2 > ... > xn .
Định nghĩa 1.3.6 Thứ tự từ điển là thứ tự 6lex , xác định như sau:
β
β
x1α1 ...xnαn 6lex x1 1 ...xn n nếu hoặc với mọi 0 6 i 6 n có αi = βi hoặc thành
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
phần đầu tiên khác không kể từ bên trái của vectơ (α1 − β1 , ..., αn − βn ) là
một số âm. Nói cách khác, nếu tồn tại 0 6 i 6 n sao cho α1 = β1 , ..., αi = βi ,
nhưng αi+1 < βi+1 .
Thứ tự từ điển tương tự như cách sắp xếp trong từ điển, và do đó có
tên gọi như vậy.
Định nghĩa 1.3.7 Thứ tự từ điển phân bậc là thứ tự 6glex xác định
như sau:
β
β
x1α1 ...xnαn 6glex x1 1 ...xn n nếu hoặc với mọi 0 6 i 6 n có αi = βi và thành
phần đầu tiên khác không kể từ bên trái của vectơ (α1 − β1 , ..., αn − βn )
β
β
là một số âm. Nói cách khác, x1α1 ...xnαn 6glex x1 1 ...xn n nếu α1 + ... + αn <
β
β
β1 + ... + βn hoặc α1 + ... + αn = β1 + ... + βn và x1α1 ...xnαn 6lex x1 1 ...xn n .
Định nghĩa 1.3.8 Thứ tự từ điển ngược là thứ tự 6rlex xác định như
sau:
β
β
x1α1 ...xnαn 6rlex x1 1 ...xn nnếu hoặcvới mọi 0 6 i 6 n có αi = β
i hoặc
β1
βn
β1
βn
α1
α1
α
α
n
n
deg x1 ...xn < deg x1 ...xn hoặc deg x1 ...xn = deg x1 ...xn và
thành phần đầu tiên khác không kể từ bên phải của vectơ (α1 − β1 , ..., αn − βn )
β
β
là một số dương. Nói cách khác, x1α1 ...xnαn 6rlex x1 1 ...xn n nếu α1 + ... + αn <
β1 + ... + βn hoặc α1 + ... + αn = β1 + ... + βn và tồn tại 1 6 i 6 n sao cho
αn = βn , ..., αi+1 = βi+1 , nhưng αi > βi .
Chú ý 1.3.9
1. Nếu có tập biến khác, chẳng hạn x, y, z thì ta có thể định nghĩa các
thứ tự từ điển, thứ tự từ điển phân bậc và thứ tự từ điển ngược một cách
duy nhất sau khi xác định một thứ tự giữa các biến. Chẳng hạn khi nói về
thứ tự từ điển trong vành K [x, y, z] với x > y > z có nghĩa xem x như x1 , y
17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
như x2 , z như x3 , rồi áp dụng định nghĩa 1.3.6. Tương tự, nếu ta muốn có
một thứ tự khác giữa các biến x1 , ..., xn (chứ không phải x1 > ... > xn ), thì
phải thay đổi các định nghĩa trên một cách tương ứng.
2. Có thể kiểm tra ngay là thứ tự từ điển ngược không thể nhận được
từ thứ tự từ điển phân bậc bằng cách đổi chỉ số các biến.
1.3.3.
Từ khởi đầu, đơn thức đầu
Kí hiệu R = K [x] = K [x1 , ..., xn ] và M là tập đơn thức của nó.
Định nghĩa 1.3.10 Cho 6 là một thứ tự từ và f ∈ K [x1 , ..., xn ]. Từ
khởi đầu của f , kí hiệu là in6 ( f ), là từ lớn nhất của đa thức f đối với thứ
tự từ 6.
Nếu in6 ( f ) = αxa , 0 6= α ∈ K, thì lc6 ( f ) = α được gọi là hệ số đầu
và lm6 ( f ) = xa là đơn thức đầu của f đối với thứ tự từ 6.
Nếu thứ tự từ 6 đã được ngầm hiểu, ta sẽ viết in ( f ) (tương ứng
lc ( f ) , lm ( f )) thay cho in6 ( f ) (tương ứng lc6 ( f ) , lm6 ( f )).
Từ khởi đầu của đa thứ 0 được xem là không xác định (có thể nhận
giá trị tùy ý).
Ví dụ:
Cho f = x3 y2 z + 5xyz − 3x4 + 7yz3 − 2y6 + z4 . Viết theo thứ tự các từ
giảm dần, ta có:
a. Đối với thứ tự từ điển mà x > y > z :
f = −3x4 + x3 y2 z + 5xyz − 2y6 + 7yz3 + z4 và in6lex ( f ) = −3x4 .
b. Đối với thứ tự từ điển phân bậc mà x > y > z :
f = x3 y2 z − 2y6 − 3x4 + 7yz3 + z4 + 5xyz và in6glex ( f ) = x3 y2 z.
c. Đối với thứ tự từ điển ngược mà x > y > z :
f = −2y6 + x3 y2 z − 3x4 + 7yz3 + z4 + 5xyz và in6rlex ( f ) = −2y6 .
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -