Tài liệu Sử dụng cơ sở groebner giải hệ phương trình đa thức bằng phương pháp khử biến

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ HOÀNG TÙNG SỬ DỤNG CƠ SỞ GROEBNER GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC BẰNG PHƯƠNG PHÁP KHỬ BIẾN LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ HOÀNG TÙNG SỬ DỤNG CƠ SỞ GROEBNER GIẢI HỆ PHƯƠNG TRÌNH ĐA THỨC BẰNG PHƯƠNG PHÁP KHỬ BIẾN LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số 60.46.01.13 Người hướng dẫn khoa học GS.TS. LÊ THỊ THANH NHÀN THÁI NGUYÊN - NĂM 2015 Mục lục Mở đầu 3 1 Vành đa thức, iđêan và tập đại số 1.1 Vành đa thức, iđêan trong vành đa 1.2 Định lý cơ sở Hilbert . . . . . . . 1.3 Tập đại số . . . . . . . . . . . . . 1.4 Iđêan đơn thức . . . . . . . . . . . thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 7 9 11 2 Ứng dụng cơ sở Groebner để giải hệ phương trình đa thức bằng phương pháp khử biến 2.1 Thứ tự đơn thức và thuật toán chia với dư . . . . . . . . . . 2.2 Cơ sở Groebner . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Thuật toán Buchberger . . . . . . . . . . . . . . . . . . . . . 2.4 Định lý khử biến và ứng dụng giải hệ phương trình đa thức . 2.5 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 17 23 27 32 34 Kết luận 40 Tài liệu tham khảo 41 1 Mở đầu Trong luận văn này chúng ta thường giả thiết K là trường, R là trường các số thực và C là trường các số phức. Thuật toán chia với dư là một trong những kết quả quan trọng trong vành đa thức một biến K[x], nó giúp giải quyết những bài toán quan trọng như bài toán thành viên, bài toán tìm ước chung lớn nhất của hai đa thức, bài toán tìm tổng, thương, giao của các iđêan. Mặc dù thuật toán chia với dư các đa thức một biến đã được biết từ xa xưa, nhưng một thuật toán chia với dư hữu hiệu như thế cho các đa thức nhiều biến mới được phát triển vào những năm 60 của thế kỉ trước. B. Buchberger đã giới thiệu lí thuyết cơ sở Groebner trong luận án tiến sĩ của mình vào năm 1965 dưới sự hướng dẫn của giáo sư W. Groebner. Điểm mấu chốt khởi đầu cho sự hình thành lí thuyết cơ sở Groebner là việc mở rộng thuật toán chia với dư và thuật toán Euclid tìm ước chung lớn nhất cho các đa thức một biến sang thuật toán chia với dư và thuật toán Buchberger tìm cơ sở Groebner cho các đa thức nhiều biến. Mục đích của luận văn "Sử dụng cơ sở Groebner để giải hệ phương trình đa thức bằng phương pháp khử biến" là trình bày lại một số kết quả trong bài báo [5] của Mencinger năm 2013, bài giảng [4] của Lall năm 2004 và bài báo [7] của Sturmfels năm 2005 về cơ sở Groebner, trong đó tập trung chủ yếu vào ứng dụng của cơ sở Groebner để giải hệ phương trình đa thức nhiều ẩn bằng phương pháp khử biến. Luận văn gồm hai chương, ngoài ra còn có phần kết luận và danh mục tài liệu tham khảo. Chương 1 trình bày về vành đa thức nhiều biến, iđêan trong vành đa thức nhiều biến và các tập đại số (đó là tập nghiệm của một họ đa thức trong vành đa thức K[x1 , ..., xn ]). Chương này cũng trình bày Định lý cơ sở Hilbert nhằm quy mỗi tập đại số về tập nghiệm của một họ hữu hạn đa thức. Chương 2 giới thiệu về cơ sở Groebner và tập trung trình bày việc 2 giải hệ phương trình đa thức nhiều biến bằng phương pháp khử biến. Trong suốt luận văn chúng ta luôn làm việc với đa thức có hệ số trên trường K . Riêng phần Định lí cơ sở Hilbert ở Chương 1, chúng ta phải làm việc với các đa thức có hệ số trên vành K[x1 , ..., xn−1 ], từ đó dùng quy nạp để chứng minh mọi iđêan của K[x1 , ..., xn ] đều hữu hạn sinh. Trong thời gian thực hiện luận văn này, tôi đã nhận được sự chỉ dẫn tận tình, chu đáo của Giáo sư - Tiến sĩ Lê Thị Thanh Nhàn. Tôi xin bày tỏ lòng biết ơn sâu sắc của mình tới cô đã giúp tôi hoàn thành luận văn. Tác giả 3 Chương 1 Vành đa thức, iđêan và tập đại số Trong suôt chương này, luôn giả thiết K là một trường. Kí hiệu N là tập các số nguyên dương và N0 là tập các số nguyên không âm. Trong chương này chúng ta tập trung trình bày về vành đa thức, iđêan trong vành đa thức nhiều biến và tập đại số, đồng thời trình bày Định lý cơ sở Hilbert nhằm quy mỗi tập đại số về tập nghiệm của họ hữu hạn đa thức. Ngoài ra còn trình bày về iđêan đơn thức, trong đó nghiên cứu đến bài toán thành viên, bài toán tìm giao và bài toán tìm iđêan thương của hai iđêan đơn thức. 1.1 Vành đa thức, iđêan trong vành đa thức Định nghĩa 1.1.1. Kí hiệu K[x1 , ..., xn ] là tập các đa thức n biến với hệ số trong K . Với i, j ∈ Nn0 , trong đó i = (i1 , ..., in ) và j = (j1 , ..., jn ), ta định nghĩa i + j = (i1 + j1 , ..., in + jn ).Kí hiệu xi là đơn thức xi11 ...xinn và ta gọi i1 + ... + in là bậc của xi . Khi đó K[x1 , ..., xn ] là một vành với phép cộng và phép nhân X X X ai xi + bi xi = (ai + bi )xi ; i∈Nn0 X ai x i∈Nn0 với mọi đa thức P i∈Nn0 i∈Nn0 i X bi x = i∈Nn0 ai x i , i P i∈Nn0 X k∈Nn0 k ck x , ck = X ai bj i+j=k bi xi ∈ K[x1 , ..., xn ]. Vành K[x1 , ..., xn ] được i∈Nn0 gọi là vành đa thức n biến x1 , ..., xn với hệ số trong K . Chú ý 1.1.2. Vành đa thức n biến x1 , ..., xn với hệ số trong K có thể được xây dựng bằng quy nạp theo n như sau. Khi n = 1, vành đa thức trở thành vành đa thức một biến K[x1 ]. Với n = 2, vành đa thức hai biến K[x1 , x2 ] 4 với hệ số trong K chính là vành đa thức một biến x2 với hệ số trong K[x1 ]. Bằng quy nạp, vành đa thức n biến K[x1 , ..., xn ] với hệ số trong K chính là vành đa thức một biến xn với hệ số trong vành K[x1 , ..., xn−1 ]. Với a là phần tử khác 0 trong K , ta gọi bậc của từ axi là bậc của đơn thức xi . Chú ý rằng mỗi đa thức được biểu diễn một cách duy nhất thành tổng của các từ không đồng dạng (nếu không kể đến thứ tự các hạng tử). Ta gọi bậc (hay bậc tổng thể) của một đa thức khác 0 là bậc cao nhất của các từ của đa thức đó. Từ định nghĩa, ta có các tính chất sau đây về bậc của đa thức. Bổ đề 1.1.3. Cho f1 (x1 , ..., xn ), f2 (x1 , ..., xn ) ∈ K[x1 , ..., xn ] là các đa thức khác 0 sao cho tổng của chúng khác 0. Khi đó (i) deg(f1 (x1 , ..., xn ) + f2 (x1 , ..., xn )) ≤ max deg fi (x1 , ..., xn ), i=1,2 (ii) deg f1 (x1 , ..., xn )f2 (x1 , ..., xn ) = deg f1 + deg f2 . Tiếp theo, chúng ta trình bày tính chất phổ dụng của vành đa thức nhiều biến. Mệnh đề 1.1.4. Gọi j : K → K[x1 , ..., xn ] cho bởi j(a) = a với mọi a ∈ K là phép nhúng tự nhiên. Với mọi vành giao hoán S , mọi hệ gồm n phần tử s1 , ..., sn của S và mọi đồng cấu ϕ : K → S , tồn tại duy nhất một đồng cấu ϕ∗ : K[x1 , ..., xn ] → S sao cho ϕ∗ (xi ) = si với mọi i ∈ {1, ..., n} và ϕ∗ j = ϕ. Chứng minh. Xét ánh xạ ϕ∗ : K[x1 , ..., xn ] → S xác định bởi X ϕ(ai )si11 ...sinn ϕ∗ (f (x1 , ..., xn )) = i=(i1 ,...,in )∈Nn0 với f (x1 , ..., xn ) = X ai xi11 ...xinn ∈ K[x1 , ..., xn ]. i=(i1 ,...,in )∈Nn0 Khi đó ϕ∗ là một đồng cấu vành, ϕ∗ (xi ) = si với mọi i ∈ {1, ..., n} và ϕ∗ j = ϕ. Do đó ϕ∗ là đồng cấu thỏa mãn các yêu cầu. Bây giờ ta chứng minh tính duy nhất. Giả sử ϕ∗1 là đồng cấu từ K[x1 , ..., xn ] đến S thỏa mãn ϕ∗1 (xi ) = si với mọi i ∈ {1, ..., n} và ϕ∗1 j = ϕ. Khi đó ϕ∗1 (a) = ϕ∗1 j(a) = ϕ(a) với mọi a ∈ K . Lại do ϕ∗1 là đồng cấu vành nên với mọi đa thức X f (x1 , ..., xn ) = ai xi11 ...xinn i=(i1 ,...,in )∈Nn0 5 trong vành K[x1 , ..., xn ] ta có X ϕ∗1 (f (x1 , ..., xn )) = ϕ(ai )si11 ...sinn . i=(i1 ,...,in )∈Nn0 Do đó ϕ∗ = ϕ∗1 . Cho A là vành con của K . Khi đó áp dụng Mệnh đề 1.1.4 đối với đồng cấu nhúng ϕ : A → K ta có kết quả sau. Hệ quả 1.1.5. Cho A là vành con của K . Với k1 , ..., kn ∈ K cho trước, tồn tại duy nhất một đồng cấu vành ϕ∗ : A[x1 , ..., xn ] → K sao cho ϕ∗ (xi ) = ki với i = 1, ..., n và ϕ∗ (a) = a với mọi a ∈ A. Hệ quả 1.1.6. Giả sử B là vành giao hoán, b1 , ..., bn ∈ B và j : K → B là đồng cấu vành sao cho với mỗi vành giao hoán S , mỗi đồng cấu ϕ : K → S và mỗi hệ gồm n phần tử s1 , ..., sn ∈ S , tồn tại duy nhất một đồng cấu ϕ∗ : B → S sao cho ϕ(bi ) = si với mọi i ∈ {1, ..., n} và ϕ∗ j = ϕ. Khi đó j là đơn cấu và B ∼ = K[x1 , ..., xn ]. Hệ quả 1.1.6 cho ta một cách xác định khác của vành đa thức như sau: Vành đa thức n biến với hệ số trong K là một bộ (B, j, b1 , ..., bn ), trong đó B là một vành giao hoán, b1 , ..., bn ∈ B và j : K → B là đồng cấu vành thỏa mãn điều kiện: với mỗi vành giao hoán S , với mọi bộ gồm n phần tử s1 , ..., sn ∈ S và với mỗi đồng cấu ϕ : K → S , tồn tại duy nhất một đồng cấu ϕ∗ : B → S sao cho ϕ∗ (bi ) = si với mọi i ∈ {1, ..., n} và ϕ∗ j = ϕ. Định nghĩa 1.1.7. Một tập I ⊆ K[x1 , ..., xn ] được gọi là một iđêan của K[x1 , ..., xn ] nếu 0 ∈ I, f − g ∈ I, hf ∈ I với mọi f, g ∈ I và h ∈ K[x1 , ..., xn ]. Định nghĩa 1.1.8. Iđêan I được gọi là iđêan hữu hạn sinh của K[x1 , ..., xn ] nếu tồn tại hữu hạn đa thức f1 , ..., ft ∈ I sao cho I = {h1 f1 + ... + ht ft | h1 , ..., ht ∈ K[x1 , ..., xn ]} Trong trường hợp này ta viết I = (f1 , ..., ft ) và ta nói {f1 , ..., ft } là hệ sinh của I . Nếu I = (f ) thì ta nói I là iđêan chính sinh bởi f . 6 1.2 Định lý cơ sở Hilbert Trong suốt tiết này, luôn giả thiết V là một vành giao hoán khác 0 và K là một trường. Ta nói rằng vành V là vành Noether nếu mỗi dãy tăng các iđêan của V đều dừng, tức là nếu I1 ⊆ I2 ⊆ . . . ⊆ In ⊆ là dãy tăng các iđêan của V thì tồn tại n0 ∈ N sao cho In = In0 với mọi n ≥ n0 . Mục tiêu chính của tiết này là chứng minh Định lí cơ sở Hilbert, phát biểu rằng nếu V là vành Noether thì vành đa thức V [x] cũng là vành Noether. Để chứng minh Định lí cơ sở Hilbert, chúng ta cần một số đặc trưng sau đây của vành Noether. Mệnh đề 1.2.1. Các phát biểu sau là tương đương. (i) V là vành Noether. (ii) Mỗi iđêan của V đều hữu hạn sinh. (iii) Mỗi họ khác rỗng những iđêan của V đều có phần tử cực đại (theo quan hệ bao hàm). Chứng minh. (i)⇒(ii). Cho I là iđêan của V . Giả sử I không hữu hạn sinh. Lấy a1 ∈ I . Do I không hữu hạn sinh nên (a1 ) 6= I , vì thế tồn tại a2 ∈ I\(a1 ). Do I không hữu hạn sinh nên (a1 , a2 ) 6= I , vì thế tồn tại a3 ∈ I\(a1 , a2 ). Cứ tiếp tục quá trình trên ta thu được một dãy tăng không dừng (a1 ) ⊂ (a1 , a2 ) ⊂ ... ⊂ (a1 , ..., an ) ⊂ ... các iđêan của V , điều này mâu thuẫn với giả thiết (i). (ii)⇒(iii). Cho Γ 6= ∅ là một họ những iđêan của V . Giả sử Γ không có phần tử cực đại. Lấy I1 ∈ Γ. Do I1 không cực đại nên tồn tại I2 ∈ Γ sao cho I1 ⊂ I2 và I1 6= I2 . Do I2 không cực đại nên tồn tại I3 ∈ Γ sao cho I2 ⊂ I3 và I2 6= I3 . Cứ tiếp tục quá trình trên ta được một dãy tăng không dừng S I1 ⊂ I2 ⊂ ... ⊂ In ⊂ ... các phần tử của Γ. Đặt I = In . Khi đó I là iđêan n≥1 của V . Theo giả thiết (ii), I hữu hạn sinh. Giả sử I = (a1 , ..., ak ). Với mỗi i = 1, ..., k , do ai ∈ I nên tồn tại ni sao cho ai ∈ Ini . Chọn n0 = max ni . i=1,...,k Khi đó ai ∈ In0 với mọi i = 1, ..., k . Suy ra I ⊆ In0 . Do đó In = In0 với mọi n ≥ n0 . Điều này là vô lí. (iii)⇒(i). Cho I1 ⊆ I2 ⊆ ... ⊆ In ⊆ ... là dãy tăng các iđêan của V . Đặt 7 Γ = {In }n≥1 . Theo giả thiết (iii), Γ có phần tử cực đại In0 . Suy ra In = In0 với mọi n ≥ n0 . Định lý 1.2.2. (Định lý cơ sở Hilbert). Cho V là vành Noether. Khi đó V [x] cũng là vành Noether. Chứng minh. Theo Mệnh đề 1.2.1, ta cần chứng minh mọi iđêan của V [x] đều hữu hạn sinh. Cho J là iđêan của V [x]. Nếu J = {0} thì rõ ràng J hữu hạn sinh. Cho J 6= {0}. Gọi m là số bé nhất trong các bậc của các đa thức khác 0 thuộc J . Với n ≥ m ta định nghĩa In = {a ∈ V | ∃f (x) = n X ai xi ∈ J, deg f (x) = n, an = a} ∪ {0}. i=0 Khi đó In là iđêan của V và In ⊆ In+1 . Vì V là vành Noether nên In hữu hạn sinh theo Mệnh đề 1.2.1, do đó ta có thể viết In = (an,1 , ..., an,in ) với mọi n ≥ m. Hơn nữa, do V Noether nên tồn tại số tự nhiên k ≥ m sao cho In = Ik với mọi n ≥ k . Với mỗi n = m, ..., k và mỗi j = 1, ..., in , gọi fn , j(x) ∈ J là đa thức có bậc n và hệ số cao nhất là an j . Đặt An = {fnj (x)|j = 1, ..., in } k S và A = An . Khi đó A là tập hữu hạn. Ta chứng minh J = (A). n=m Rõ ràng (A) ⊆ J . Cho 0 6= p(x) ∈ J với a là hệ số cao nhất của p(x). Khi đó deg p(x) ≥ m. Ta chứng minh p(x) ∈ (A) bằng quy nạp theo deg p(x). Cho deg p(x) = m. Khi đó a ∈ Im . Do đó tồn tại c1 , ..., cim ∈ K sao cho im im P P a = cj am,j . Đặt q(x) = p(x) − cj fm,j (x). Khi đó q(x) hoặc bằng 0 j=1 j=1 hoặc có bậc nhỏ hơn m. Chú ý rằng q(x) ∈ J . Do đó q(x) = 0 theo cách chọn m. Suy ra p(x) ∈ (A). Cho deg p(x) = n > m và giả thiết rằng mọi đa thức trong J với bậc nhỏ hơn n đều thuộc (A). Khi đó a ∈ In . Đặt t = min{n, k}. Suy ra In = It và vì thế a ∈ It . Do đó tồn tại c1 , ..., cit ∈ K it it P P sao cho a = cj at,j . Đặt q(x) = p(x)− cj xn−t ft,j (x). Khi đó q(x) ∈ J và j=1 j=1 q(x) hoặc bằng 0 hoặc có bậc nhỏ hơn n. Theo giả thiết quy nạp, q(x) ∈ (A). Suy ra p(x) ∈ (A). Do đó J = (A). Chú ý 1.2.3. Có một chứng minh khác ngắn gọn hơn cho Định lý cơ sở Hilbert. Cho V là vành Noether. Giả sử V [x] không Noether. Khi đó V [x] có một iđêan J không hữu hạn sinh. Rõ ràng J 6= 0. Chọn f1 là đa thức khác 0 8 có bậc bé nhất trong J . Vì J không hữu hạn sinh nên với mỗi n ∈ N, tồn tại đa thức khác 0 có bậc bé nhất thõa mãn fn ∈ J\(f1 , ..., fn−1 ). Gọi an là hệ số cao nhất của fn và dn là bậc của fn với mọi n ∈ N. Theo cách chọn fn ta có d1 ≤ d2 ≤ .... Do V Noether nên dãy các iđêan (a1 ) ⊆ (a1 , a2 ) ⊆ ... phải dừng. Do đó tồn tại m sao cho (a1 , ..., an ) = (a1 , ..., am ) với mọi n ≥ m. Vì thế am+1 ∈ (a1 , ..., am ). Do đó am+1 = b1 a1 + ... + bm am với b1 , ..., bm ∈ V . m P bi xdm+1 −di fi . Khi đó g ∈ J . Nếu g ∈ (f1 , ..., fm ) thì Đặt g = fm+1 − fm+1 = g + m P i=1 bi xdm+1 −di fi ∈ (f1 , ..., fm ), điều này mâu thuẫn với cách chọn i=1 fm+1 . Do đó g ∈ J\(f1 , ..., fm ). Suy ra g 6= 0 và deg g < deg fm+1 . Điều này mâu thuẫn với cách chọn fm+1 . Vì K là trường nên K chỉ có đúng hai iđêan là {0} và K . Do đó mọi dãy tăng các iđêan của K đều dừng. Vì vậy, K là vành Noether. Sy ra K[x1 ] là vành Noether. Vì K[x1 , . . . , xn ] = K[x1 , . . . , xn−1 ][xn ] nên bằng quy nạp ta có hệ quả sau. Hệ quả 1.2.4. Mọi iđêan của vành đa thức K[x1 , . . . , xn ] đều hữu hạn sinh. 1.3 Tập đại số Trong phần này chúng ta quan tâm đến các tập đại số, tức là tập nghiệm của một họ đa thức trong vành đa thức K[x1 , ..., xn ] trên một trường K . Định lý cơ sở Hilbert cho phép chúng ta quy mỗi tập đại số về tập nghiệm của hữu hạn đa thức, nhờ đó việc nghiên cứu các tập đại số bớt phức tạp hơn. Kí hiệu K n = {(a1 , ..., an ) | ai ∈ K, ∀i = 1, ..., n}. Ta gọi K n là không gian affin n chiều. Đặc biệt K = K 1 được gọi là đường thẳng affin, K 2 được gọi là mặt phẳng affin. Với mỗi tập con S của K[x1 , ..., xn ], kí hiệu Z(S) = {(a1 , ..., an ) ∈ K n | f (a1 , ..., an ) = 0, ∀f ∈ S} là tập nghiệm (hay tập các không điểm chung) của S . Định nghĩa 1.3.1. Một tập con X của K n được gọi là tập đại số (hay đa tạp affin) nếu tồn tại S ⊆ K[x1 , ..., xn ] sao cho X = Z(S). Khi đó ta cũng nói X là tập đại số định nghĩa bởi S . 9 Cho X = Z(S) là một tập đại số trong K n . Nếu S = {f } thì ta viết X = Z(f ). Nếu f khác hằng thì Z(f ) được gọi là một siêu mặt trong K n . Nếu S = {f1 , ..., fk } là tập hữu hạn thì ta viết X = Z(f1 , ..., fk ). Chú ý rằng mỗi tập đại số (khác ∅ và khác K n ) đều là giao của một họ siêu mặt, vì ta T có X = Z(S) = Z(f ). f ∈S Ví dụ 1.3.2. (i) Trong mặt phẳng affin R2 , tập đại số Z(x2 + y 2 − 1) là đường tròn bán kính bằng 1 và tâm là gốc tọa độ. Trong hình học giải tích, các đường tròn, đường elip, parabol, hypebol đều là các tập đại số. (ii) Trong không gian affin 3-chiều R3 , tập đại số Z(z − x2 − y 2 ) là mặt paraboloid tròn xoay, thu được bằng cách quay parabol z = x2 quanh trục z . Các mặt bậc hai ellipsoid, hypeboloid cũng là các tập đại số. Mệnh đề 1.3.3. Mỗi tập đại số trong K n là tập nghiệm của một iđêan trong vành đa thức K[x1 , ..., xn ]. Chứng minh. Cho X ⊆ K n là một tập đại số. Khi đó tồn tại họ đa thức S ⊆ K[x1 , . . . , xn ] sao cho X = Z(S). Đặt I = (S) là iđêan của K[x1 , . . . , xn ] sinh bởi S . Chú ý rằng S ⊆ (S) và mỗi phần tử của (S) có dạng f −1h1 +. . .+ft ht với f1 , . . . , ft ∈ S và h1 , . . . , ht ∈ K[x1 , . . . , xn ]. Suy ra mỗi phần tử của K n là nghiệm của họ S nếu và chỉ nếu nó là nghiệm của iđêan (S). Do đó X là tập nghiệm của iđêan (S). Mệnh đề 1.3.4. Mỗi tập đại số là tập nghiệm của hữu hạn đa thức. Chứng minh. Cho X ⊆ K n là một tập đại số. Khi đó tồn tại họ đa thức S ⊆ K[x1 , . . . , xn ] sao cho X = Z(S). Theo chứng minh Hệ quả 1.3.3 ta suy ra X là tập nghiệm của iđêan (S). Theo Định lí cơ sở Hilbert, (S) là i đêan hữu hạn sinh, tức là tồn tại f1 , . . . , ft ∈ (S) sao cho (S) = (f1 , . . . , ft ). khi đó X là tập nghiệm của họ hữu hạn đa thức f1 , . . . , ft . Chú ý 1.3.5. Việc quy mỗi tập đại số về tập nghiệm của hữu hạn đa thức là vô cùng quan trọng. Nó cho phép thực hiện được thuật toán Buchberger trong Chương 2 để tìm một cơ sở Groebner của một iđêan xuất phát từ một hệ sinh hữu hạn. 10 1.4 Iđêan đơn thức Trong vành đa thức K[x1 , ..., xn ], iđêan đơn thức theo nhiều khía cạnh là đơn giản và dễ nghiên cứu nhất. Vì thế, một trong những ý tưởng chủ đạo là tìm cách quy một iđêan về một iđêan đơn thức sao cho từ những thông tin của iđêan đơn thức, người ta có thể lấy lại được thông tin của iđêan ban đầu. Mục tiêu của tiết này là giới thiệu khái niệm, tính chất của iđêan đơn thức và giải quyết một số bài toán về iđêan đơn thức. Định nghĩa 1.4.1. Một iđêan I của vành đa thức K[x1 , ..., xn ] được gọi là iđêan đơn thức nếu nó có một hệ sinh gồm những đơn thức. Trong vành đa thức K[x, y, z], iđêan (xy 2 , x3 , yx2 , z) là iđêan đơn thức. Iđêan (xy 2 − x3 , x3 , yx2 ) cũng là iđêan đơn thức của K[x, y, z] vì ta có (xy 2 − x3 , x3 , yx2 , z) = (xy 2 , x3 , yx2 , z). Kết quả sau đây cho ta một số đặc trưng của iđêan đơn thức. Bổ đề 1.4.2. Cho I là iđêan của K[x1 , ..., xn ]. Các phát biểu sau là tương đương. (i) I là iđêan đơn thức. (ii) f ∈ I khi và chỉ khi mọi từ của f đều thuộc I với mọi f ∈ K[x1 , ..., xn ]. (iii) I là K -không gian véc tơ sinh bởi các đơn thức trong I . Chứng minh. (i) ⇒ (ii). Cho f ∈ K[x1 , ..., xn ]. Nếu mọi từ của f đều thuộc I thì rõ ràng f ∈ I . Giả sử f ∈ I . Do I là iđêan đơn thức nên tồn tại một họ S những đơn thức của K[x1 , ..., xn ] sao cho I = (S). Vì thế, tồn tại các đơn thức m1 , ..., ms ∈ S và các đa thức h1 , ..., hs ∈ K[x1 , ..., xn ] sao cho f = h1 m1 + ... + hs ms . Sau khi khai triển vế phải của đẳng thức trên và ước lược các từ đồng dạng ta nhân được biểu diễn chính tắc của f . Vì thế mỗi từ của f đều là bội của một đơn thức mi nào đó. Do đó f ∈ I . P (ii) ⇒ (iii). Rõ ràng I là K -không gian véc tơ. Cho f = ai ui ∈ I , trong đó ai ∈ K và ui là đơn thức, là biểu diễn chính tắc của f . Theo giả thiết (ii), mỗi từ ui của f đều thuộc I . Do đó f là tổ hợp tuyến tính với hệ số trong K của đơn thức trong I . Vì thế, hệ các đơn thức trong I là một hệ sinh của K -không gian véc tơ I . (iii) ⇒ (i). Gọi S là tập các đơn thức trong I . Kí hiệu L là K -không gian 11 véc tơ sinh bởi S và (S) là iđêan của K[x1 , ..., xn ] sinh bởi S . Theo giả thiết (iii) ta có I = L ⊆ (S) ⊆ I . Vì thế I = (S) là iđêan đơn thức. Hệ quả sau đây suy ra từ Bổ đề 1.4.2. Hệ quả 1.4.3. Trong vành đa thức K[x1 , ..., xn ], các phát biểu sau là đúng. (i) Hai iđêan đơn thức là bằng nhau nếu và chỉ nếu tập các đơn thức của chúng là như nhau. (ii) Nếu u là một đơn thức và I là iđêan sinh bởi một họ đơn thức S thì u ∈ I khi và chỉ khi u là bội của một đơn thức trong S . Mệnh đề 1.4.4. (Bổ đề Dickson) Mỗi iđêan đơn thức đều có một hệ sinh gồm hữu hạn đơn thức. Đặc biệt, từ mỗi hệ sinh gồm những đơn thức của I , ta có thể trích ra một hệ sinh hữu hạn. Chứng minh. Cho I là iđêan đơn thức. Theo Định lý cơ sở Hilbert (Định lý 1.2.2), I có hệ sinh hữu hạn. Giả sử I = (f1 , ..., fs ). Với mỗi i ∈ {1, 2, . . . , s}, ni P gọi fi = aij uij là biểu diễn chính tắc của fi , trong đó aij ∈ K và uij là j=1 đơn thức. Vì I là iđêan đơn thức nên theo Bổ đề 1.4.2, ta có uij ∈ I với mọi i, j . Đặt S = {uij |i = 1, ..., s; j = 1, ..., ni }. Khi đó fi ∈ (S) ⊆ I với mọi i. Suy ra I = (S), trong đó S là một hệ gồm hữu hạn đơn thức. Giả sử S 0 là một hệ sinh của I gồm những đơn thức, chúng ta chỉ ra rằng có thể trích ra từ S 0 một hệ con hữu hạn sinh ra I . Theo chứng minh trên, tồn tại hữu hạn đơn thức u1 , ..., us ∈ K[x1 , ..., xn ] sao cho I = (u1 , ..., us ). Với mỗi i ∈ 1, ..., s, vì ui ∈ I và I = (S 0 ) nên theo Hệ quả 1.1.3, tồn tại mi ∈ S 0 sao cho ui là bội của mi . Do đó ui ∈ (m1 , ..., ms ) với mọi i. Vì thế I = (u1 , ..., us ) ⊆ (m1 , ..., ms ) ⊆ (S 0 ) = I Vậy m1 , ..., ms là một hệ con hữu hạn của S 0 sinh ra I . Trong một vành giao hoán V , một hệ sinh S của một iđêan I được gọi là hệ sinh tối thiểu của I nếu I không sinh bởi bất cứ tập con thực sự nào của S . Trong vành đa thức, các iđêan có thể có nhiều hệ sinh tối thiểu. Chẳng hạn, {x − y 2 , x}, {y 2 , x − y 2 } và {x, y 2 } là 3 hệ sinh tối thiểu của iđêan I = (x − y 2 , x) trong vành đa thức K[x, y]. Tuy nhiên, mỗi iđêan đơn thức chỉ có duy nhất một hệ sinh tối thiểu gồm các đơn thức. 12 Mệnh đề 1.4.5. Cho I là ideal đơn thức trong K[x1 , ..., xn ]. Khi đó (i) Mỗi hệ đơn thức sinh ra I đều trích ra được một hệ con hữu hạn là hệ sinh tối thiểu của I . (ii) I có duy nhất một hệ sinh tối thiểu gồm hữu hạn đơn thức. Chứng minh. (i) Vì I ⊆ K[x1 , ..., xn ] là iđêan đơn thức nên I = (S), trong đó S là một hệ đơn thức. Theo Bổ đề Dickson (Mệnh đề 1.4.4), tồn tại một hệ con hữu hạn S 0 = {u1 , ..., us } của S sao cho I = (S 0 ). Với mỗi i ∈ {1, ..., s}, nếu ui là bội của uj với j 6= i thì ui ∈ (u1 , ..., ui−1 , ui+1 , ..., us ) và vì thế I = (u1 , ..., ui−1 , ui+1 , ..., us ). Do đó, bằng cách loại tất cả các đơn thức ui là bội của một đơn thức khác trong S 0 , ta được một tập con S 00 của S sao cho I = (S 00 ) và hai đơn thức bất kì trong S 00 không là bội của nhau. Vì thế, theo Hệ quả 1.4.3(ii), S 00 là hệ sinh tối thiểu của I . (ii) Từ chứng minh (i) ta suy ra I có hệ sinh tối thiểu gồm hữu hạn đơn thức. Giả sử S1 , S2 là hai hệ sinh tối thiểu của I gồm các đơn thức. Nếu u ∈ S1 thì u ∈ I = (S2 ). Theo Hệ quả 1.4.3(ii), tồn tại v ∈ S2 sao cho u là bội của v . Do v ∈ I = (S1 ) nên theo Hệ quả 1.4.3(ii), tồn tại u0 ∈ S1 sao cho v là bội của u0 . Suy ra u là bội của u0 . Do tính tối thiểu của S1 ta suy ra u = u0 . Vì thế u = v ∈ S2 . Do đó S1 ⊆ S2 . Tương tự S2 ⊆ S1 . Trong phần còn lại của tiết này ta giải quyết một số bài toán liên quan đến iđêan đơn thức. Trước hết ta có lời giải cho bài toán thành viên cho iđêan đơn thức. Hệ quả 1.4.6. (Bài toán thành viên).Cho I là iđêan đơn thức sinh bởi các đơn thức m1 , ..., ms và f là một đa thức. Khi đó f ∈ I khi và chỉ khi mỗi từ của f đều là bội của một đơn thức mi nào đó. Chứng minh. Nếu mỗi từ của f đều là bội của một đơn thức mi nào đó thì rõ ràng f ∈ I . Ngược lại, giả sử f ∈ I . Khi đó theo Bổ đề 1.4.2, mỗi từ của f đều thuộc I . Do I = (m1 , ..., ms ) nên theo Hệ quả 1.4.3. mỗi từ của f là bội của một đơn thức mi nào đó. Ví dụ 1.4.7. Cho I = (x4 y 2 , x3 yz 2 , yz 3 ) ⊆ Q[x, y, z]. Cho hai đa thức f = 3x5 y 4 z + 4x7 y 2 z 3 − 2xyz 3 và g = 3yz + 4x5 y 7 + 2xyz 7 . Nhận thấy rằng mọi từ của f đều là bội của một đơn thức trong hệ {x4 y 2 , x3 yz 2 , yz 3 }, do đó 13 f ∈ I . Chú ý rằng g có một từ 3yz không là bội của bất cứ đơn thức nào trong hệ {x4 y 2 , x3 yz 2 , yz 3 }. Do đó g ∈ / I theo Hệ quả 1.4.6. Vì vành đa thức K[x1 , ..., xn ] là miền phân tích duy nhất nên hai đa thức không đồng thời bằng 0 trong vành đa thức K[x1 , ..., xn ] luôn có ước chung lớn nhất. Trong trường hợp một biến, việc tìm ước chung lớn nhất được thực hiện dễ dàng thông qua thuật toán Euclid, nhưng bài toán tìm ước chung lớn nhất trong trường hợp nhiều biến lại không giải quyết được. Tuy nhiên, việc tìm ước chung lớn nhất của hai đơn thức lại rất đơn giản. Giả sử u = xi11 ...xinn và v = xj11 ...xjnn là hai đơn thức. Đặt rk = min(ik , jk ) và sk = max(ik , jk ) với k = 1, ..., n. Khi đó xr11 ...xrnn và xs11 ...xsnn lần lượt là ước chung lớn nhất của u, v (kí hiệu là gcd(u, v)) và bội chung nhỏ nhất của u, v (kí hiệu là lcm(u, v)). Hệ quả sau đây giải quyết bài toán tìm giao của các iđêan đơn thức. Hệ quả 1.4.8. (Bài toán tìm giao). Cho I và J là hai iđêan đơn thức lần lượt sinh bởi hai hệ đơn thức {m1 , ..., mp } và {u1 , ..., uq }. Khi đó I ∩ J là iđêan sinh bởi hệ hữu hạn đơn thức {lcm(mi , uj ) | i = 1, ..., p; j = 1, ..., q} Đặc biệt, giao của hai iđêan đơn thức là một iđêan đơn thức. Chứng minh. Đặt S = {lcm(mi , uj ) | i = 1, ..., p; j = 1, ..., q}. Rõ ràng I ∩ J ⊇ (S). Vì thế, theo Bổ đề 1.4.2, chúng ta cần chứng minh mỗi đơn thức của I ∩ J là bội của một đơn thức lcm(mi , uj ) nào đó. Giả sử u là một đơn thức của I ∩ J . Khi đó u ∈ I và u ∈ J . Vì I là iđêan đơn thức nên theo Hệ quả 1.4.3, u là bội của mi nào đó. Tương tự, vì J là ideal đơn thức nên u là bội của uj nào đó. Vì thế u là bội của lcm(mi , uj ). Ví dụ 1.4.9. Cho I = (xy, x2 z, yz 3 ) và J = (x2 z 2 , yz). Theo Hệ quả 2.1.8, I ∩ J = (x2 yz 2 , x2 z 2 , x2 yz 3 , xyz, x2 yz, yz 3 ) = (x2 z 2 , xyz, yz 3 ). Chú ý 1.4.10. Đối với bài toán tìm tổng của hai iđêan đơn thức, nếu I và J là hai iđêan đơn thức lần lượt sinh bởi hai hệ đơn thức {m1 , ..., mp } và {u1 , ..., uq }, thì I + J = (m1 , ..., mp , u1 , ..., uq ). Do đó tổng của hai iđean đơn thức là một iđean đơn thức. Tuy nhiên, nếu như iđean I ∩ J được tính qua các bội chung nhỏ nhất lcm(mi , uj ) thì tổng I + J trong trường hợp nhiều 14 biến lại không liên quan đến các ước chung lớn nhất gcd(mi , uj ). Chẳng hạn, trong vành đa thức hai biến K[x, y], cho I = (x) và J = (y) là hai iđêan đơn thức. Khi đó gcd(x, y) = 1 và I + J = (x, y) 6= (1) = K[x, y]. Đây là sự khác biệt khi so sánh với tổng của hai iđêan trong trường hợp một biến. Cụ thể, nếu I, J là hai iđêan trong K[x] thì I, J là các iđêan chính và I + J = (gcd(f, g)), trong đó I = (f ) và J = (g). Với I, J là hai iđêan trong một vành giao hoán V , ta đặt (I : J) = {a ∈ V | Ja ⊆ I}. Khi đó (I : J) là iđêan của V chứa I . Ta gọi (I : J) là iđêan thương của I và J . Nếu J = (b) thì (I : J) được viết là (I : b). Chú ý rằng nếu J = (b1 , ..., br ) thì ta có I : J = (I : b1 ) ∩ (I : b2 ) ∩ ... ∩ (I : br ). Vì thế, để tìm iđêan thương của một iđêan I cho một iđêan hữu hạn sinh, chúng ta chỉ cần tìm các iđêan thương dạng (I : b) với b ∈ V . Hệ quả tiếp theo giải quyết bài toán tìm iđêan thương của hai iđêan đơn thức. Hệ quả 1.4.11. (Bài toán tìm iđêan thương).Trong vành đa thức K[x1 , ..., xn ], cho I là iđêan sinh bởi hệ đơn thức {m1 , ..., ms } và u là một đơn thức. Với mỗi i = 1, ..., s, đặt di = gcd(mi , u). Giả sử mi = di vi . Khi đó (I : u) là iđêan sinh bởi hệ đơn thức {v1 , ..., vs }. Đặc biệt, thương của hai iđêan đơn thức cũng là iđêan đơn thức. Chứng minh. Rõ ràng (v1 , ..., vs ) ⊆ (I : u). Giả sử f ∈ (I : u). Khi đó f u ∈ I . Gọi m là một từ tùy ý của f . Chú ý rằng khi nhân các từ của f với đơn thức u ta được các từ không đồng dạng. Vì thế mu là một từ của f u. Do I là iđêan đơn thức và f u ∈ I nên mu ∈ I theo Bổ đề 1.4.2. Vì thế, theo Hệ quả 1.4.3, mu là bội của một đơn thức mi nào đó. Suy ra m là bội của vi . Do đó (v1 , ..., vs ) ⊆ (I : u). Vì thế (I : u) ⊆ (v1 , ..., vs ). Ví dụ 1.4.12. Cho I = (xyz, x3 yz, yz 3 ) và J = (x2 z 2 , yz). Đặt m1 = xyz, m2 = x3 yz, m3 = yz 3 và u1 = x2 z 2 , u2 = yz . Đặt d1 = gcd(m1 , u1 ) = xz, d2 = gcd(m2 , u1 )x = x2 y, d3 = gcd(m3 , u1 ) = z 2 . 15 Khi đó m1 = d1 y, m2 = d2 xy, m3 = d3 yz . Đặt v1 = y, v2 = xy, v3 = yz . Theo hệ quả 2.1.11 ta có (I : u1 ) = (v1 , v2 , v3 ) = (y, xy, yz). Tương tự (I : u2 ) = (x, yz, z 2 ). Theo Hệ quả 2.1.6, (I : J) = (I : u1 )∩(I : u2 ) = (x, xy, yz)∩(x, yz, z 2 ) = (xy, yz, yz 2 , xyz, xyz 2 ) = (xy, yz) . 16 Chương 2 Ứng dụng cơ sở Groebner để giải hệ phương trình đa thức bằng phương pháp khử biến 2.1 Thứ tự đơn thức và thuật toán chia với dư Ta kí hiệu U = K[x1 , ..., xn ] là vành đa thức n biến trên trường K và Mon(U ) là tập các đơn thức trong U . Kí hiệu N0 = {0, 1, ..., n, ...} là tập các số nguyên không âm. Định nghĩa 2.1.1. Một thứ tự đơn thức là một quan hệ thứ tự toàn phần ≤ trên Mon(U ) thõa mãn các tính chất (i) Nếu u < v thì uw < vw với mọi u, v, w ∈ Mon(U ). (ii) ≤ sắp thứ tự tốt, tức là mỗi bộ phận khác rỗng của Mon(U ) đều có phần tử nhỏ nhất. Với (i1 , ..., in ), (j1 , ..., jn ) ∈ Nn0 , ta định nghĩa (i1 , ..., in ) + (j1 , ..., jn ) = (i1 + j1 , ..., in + jn ). Chú ý 2.1.2. Nếu ta cho tương ứng mỗi đơn thức xi11 ...xinn ∈ Mon(U ) với bộ n số nguyên không âm (i1 , ..., in ) ∈ Nn0 thì ta có thể đồng nhất mỗi thứ tự đơn thức ≤ trên Mon(U ) với một quan hệ thứ tự toàn phần ≤ trên Nn0 thõa mãn hai tính chất: (i) Mọi tập con khác rỗng của Nn0 đều có phần tử nhỏ nhất; (ii) Nếu (i1 , ..., in ) < (j1 , ..., jn ) thì (i1 , ..., in ) + (t1 , ..., tn ) < (j1 , ..., jn ) + (t1 , ..., tn ) với mọi (i1 , ..., in ), (j1 , ..., jn ), (t1 , ..., tn ) ∈ Nn0 . Đồng nhất này xác định bởi (i1 , ..., in ) ≤ (j1 , ..., jn ) nếu và chỉ nếu xi11 ...xinn ≤ xj11 ...xjnn với mọi (i1 , ..., in ), (j1 , ..., jn ) ∈ Nn0 . 17 Kí hiệu 2.1.3. Cho ≤ là một thứ tự đơn thức trên Mon(U ). Với hai từ không đồng dạng au và bv , trong đó a, b ∈ K và u, v ∈ Mon(U ), ta định nghĩa au < bv nếu và chỉ nếu u < v . Khi đó mỗi đa thức f ∈ K[x1 , ..., xn ] có thể được viết một cách duy nhất thành tổng của các từ không đồng dạng với thứ tự từ cao xuống thấp, tức là f = a1 u1 + ... + at ut , trong đó a1 , ..., at ∈ K là các phần tử khác 0 và u1 , ..., ut ∈ Mon(U ) thõa mãn u1 > u2 > ... > ut . Ta gọi a1 , ..., at là các hệ số của f . Từ cao nhất a1 u1 của f được gọi là từ dấu của f và được kí hiệu bởi in(f ) (hay lt(f )). Đơn thức u1 của từ dấu của f được gọi là đơn thức cao nhất của f và được kí hiệu là lm(f ). Kết quả sau đây chỉ ra rằng điều kiện sắp thứ tự tốt trong Định nghĩa 2.1.1(ii) làm cho thứ tự đơn thức có những tính chất rất đặc biệt. Bổ đề 2.1.4. Cho ≤ là một thứ tự đơn thức trên tập Mon(U ). Khi đó (i) xi > 1 với mọi i = 1, ..., n. (ii) Mỗi dãy giảm các đơn thức đều dừng. Chứng minh. (i) Giả sử tồn tại i ∈ {1, ..., n} sao cho xi < 1. Nhân liên tiếp hai vế với xi ta có x2i < x1 , x3i < x2i , .... Do đó ta có tập con các đơn thức S = {xi , x2i , x3i , ...} và dãy này không có phần tử bé nhất. Điều này mâu thuẫn với giả thiết sắp thứ tự tốt. (ii) Cho dãy giảm các đơn thức u1 > u2 > u3 > .... Xét tập con S = {u1 ,u2 ,u3 ,...}. Khi đó S 6= ∅. Vì ≤ sắp thứ tự tốt nên S có phần tử bé nhất uk0 . Suy ra uk = uk0 với mọi k ≥ k0 . Sau đây chúng ta giới thiệu ba loại thứ tự từ hay được sử dụng. Cho thuận tiện, chúng ta đồng nhất mỗi thứ tự từ trên Mon(U ) với thứ tự tương ứng trên Nn0 (xem Chú ý 2.1.2). Định nghĩa 2.1.5. (Thứ tự từ điển) Cho i = (i1 , ..., in ), j = (j1 , ..., jn ) là hai bộ số trong Nn0 . Đặt i − j = (i1 − j1 , ..., in − jn ). Ta nói i ≤ j nếu i = j hoặc tọa độ khác 0 đầu tiên tính từ bên trái sang của i − j là số âm. Khi đó ≤ là một thứ tự đơn thức, đước gọi là thứ tự từ điển và được kí hiệu là ≤lex . Trong N30 ta có (0, 3, 5)lex x1 x32 x53 . Chú ý 2.1.6. Chúng ta đưa ra vài nhận xét về thứ tự từ điển. Trong Nn0 , (0, ..., 0, 1) - Xem thêm -