Tài liệu Cơ sở grobner và giải hệ phương trình đa thức

ĐẠ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