ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC SƯ PHẠM TÔN NỮ QUỲNH MAI LẬP TRÌNH TÍNH CƠ SỞ GROEBNER CỦA IĐÊAN CÁC ĐA THỨC TRIỆT TIÊU TRONG VÀNH Zm[x1, , xn] LUẬN VĂN THẠC SĨ TOÁN HỌC THEO ĐỊNH HƯỚNG: Nghiên cứu NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS PHAN VĂN THIỆN Thừa Thiên Huế, năm 2017 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC SƯ PHẠM TÔN NỮ QUỲNH MAI LẬP TRÌNH TÍNH CƠ SỞ GROEBNER CỦA IĐÊAN CÁC ĐA THỨC TRIỆT TIÊU TRONG VÀNH Zm[x1, , xn] Chuyên ngành: ĐẠI SỐ VÀ LÝ THUYẾT SỐ Mã số: 60460104 LUẬN VĂN THẠC SĨ TOÁN HỌC THEO ĐỊNH HƯỚNG: Nghiên cứu NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS PHAN VĂN THIỆN Thừa Thiên Huế, năm 2017 i LỜI CAM ĐOAN Tơi xin cam đoan cơng trình nghiên cứu khoa học độc lập riêng định hướng PGS.TS Phan Văn Thiện Các số liệu sử dụng phân tích luận án có nguồn gốc rõ ràng, công bố theo quy định Các kết nghiên cứu luận án tự tìm hiểu, phân tích cách trung thực, khách quan Các kết chưa công bố nghiên cứu khác Tôn Nữ Quỳnh Mai ii LỜI CẢM ƠN Luận văn hoàn thành hướng dẫn Thầy giáo, PGS.TS Phan Văn Thiện Tơi xin bày tỏ lịng biết ơn sâu sắc kính trọng Thầy Thầy tận tình hướng dẫn, giúp đỡ tơi suốt q trình thực khóa luận tốt nghiệp, đồng thời giúp tơi lĩnh hội kiến thức chuyên môn rèn luyện cho tác phong nghiên cứu khoa học Tôi xin gửi lời cảm ơn chân thành đến quý Thầy Khoa Tốn, Thầy Đại học Huế Viện Toán học dạy dỗ truyền đạt kiến thức cho tơi suốt q trình học tập Tơi xin chân thành cảm ơn Ban giám hiệu trường ĐHSP Huế, phịng Đào tạo sau Đại học, khoa Tốn trường ĐHSP Huế tạo điều kiện cho suốt khóa học Cuối cùng, tơi xin cảm ơn gia đình, bạn bè, anh chị Cao học Tốn khóa XXIV trường ĐHSP Huế chuyên ngành Đại số Lý thuyết số động viên, giúp đỡ trình học tập vừa qua Ngày 15 tháng 09 năm 2017 Học viên thực Tôn Nữ Quỳnh Mai iii Mục lục Trang phụ bìa i Lời cam đoan ii Lời cảm ơn iii Mục lục Lời nói đầu Thuật tốn tìm sở Groebner iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] 1.1 Kiến thức chuẩn bị 1.1.1 Vành đa thức Zm [x1 , , xn ] Định lý Hilbert sở 1.1.2 Thứ tự từ vành Zm [x1 , , xn ] 1.1.3 Iđêan đơn thức Iđêan dẫn đầu 11 1.2 Cơ sở Groebner iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] 14 1.2.1 Iđêan đa thức triệt tiêu 16 1.2.2 Cơ sở Groebner mạnh tối tiểu I0 17 1.2.3 Thuật tốn tìm sở Groebner mạnh tối tiểu vành Zm 21 Lập trình tính sở Groebner iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] ngôn ngữ C 24 2.1 Tổ chức cấu trúc liệu 24 2.1.1 Đơn thức Zm [x1 , , xn ] 24 2.1.2 Đa thức Zm [x1 , , xn ] 25 2.1.3 Hàm biểu diễn đa thức triệt tiêu p 30 2.2 Xây dựng chương trình 31 2.3 Một số ví dụ 42 Kết luận 44 LỜI NÓI ĐẦU Năm 1970, Buchberger công bố tảng lý thuyết sở Groebner iđêan vành đa thức nhiều biến trường Tám năm sau, năm 1978, W.Trinks đưa cách tổng quát lý thuyết vành đa thức vành noetherian, giao hốn Ơng trình bày khái niệm sở Groebner vành đa thức nhiều biến từ trường hợp trường sang trường hợp vành Có thể thấy tính chất sở Groebner vành đa thức nhiều biến vành C ý, song chưa nghiên cứu nhiều Tuy nhiên, ứng dụng tiềm tính chất thú vị nên thu hút quan tâm nhiều nhà toán học giới, chẳng hạn Greuel G., Seelish F., Wienand O., Adam W., (xem [5], [6]) Khi vành Zm có hữu hạn phần tử tồn đa thức khác không Zm [x1 , , xn ] triệt tiêu với (a1 , a2 , , an ) ∈ Zn , ta gọi đa thức triệt tiêu Tất đa thức triệt tiêu tạo thành iđêan I0 Trên phương diện toán học tin học, I0 ⊂ Zm [x1 , , xn ] có số tính chất thú vị (xem [5]) Luận văn đưa sở Groebner mạnh tối tiểu Gm I0 Việc xây dựng chi tiết sở Groebner mạnh tối tiểu iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] với m ≥ chứng minh cách hoàn toàn tổng quát ([5]) Điều đáng ý việc xây dựng sở Groebner không phụ thuộc vào thứ tự đơn thức tập từ dẫn đầu sở Groebner Luận văn trình bày lại thuật tốn đệ quy [5] để xây dựng sở Groebner mạnh tối tiểu iđêan đa thức triệt tiêu Zm [x1 , , xn ] Phần cuối luận văn xây dựng chương trình tính sở Groebner mạnh tối tiểu iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] ngôn ngữ C dựa thuật toán [5] Luận văn bao gồm hai chương: Chương : Thuật tốn tìm sở Groebner iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] Đầu tiên chương trình bày số khái niệm, tính chất vành đa thức Zm [x1 , , xn ] Tiếp theo chương trình bày khái niệm, nội dung định lý cần thiết, liên quan đến việc xây dựng định nghĩa sở Groebner iđêan đa thức triệt tiêu thuật tốn để tìm vành Zm [x1 , , xn ], chương tiền đề nghiên cứu cho chương sau Chương : Lập trình tính sở Groebner iđêan đa thức triệt tiêu vành Zm [x1 , , xn ] ngôn ngữ C Đây phần luận văn Nội dung trình bày cách biểu diễn liệu, vài ý kiến việc sử dụng thuật tốn tính sở Groebner mạnh tối tiểu [5] Cuối chương chương trình tính sở Groebner, ví dụ chạy mẫu nhận xét Chương Thuật tốn tìm sở Groebner iđêan đa thức triệt tiêu vành Zm[x1, , xn] Trong suốt luận văn ta xét vành đa thức Zm [x1 , , xn ] với m ≥ Tài liệu tham khảo chương [1], [5], [6] 1.1 Kiến thức chuẩn bị 1.1.1 Vành đa thức Zm [x1 , , xn ] Định lý Hilbert sở Xét vành đa thức Zm [x1 , , xn ] với biến x1 , x2 , , xn (n ≥ 1) Ta gọi đơn thức biểu thức có dạng: xα1 xα2 · · · xαnn (α1 , , αn ) ∈ Nn gọi số mũ đơn thức Nếu α1 = · · · = αn = đơn thức Phép nhân tập đơn thức định nghĩa sau: (xα1 · · · xαnn )(xβ1 · · · xβnn ) = xα1 +β1 · · · xαnn +βn Tổng số mũ biến đơn thức gọi bậc đơn thức Từ biểu thức có dạng axα1 · · · xαnn , a ∈ Zm gọi hệ số từ Thông thường phần tử vành sở Zm gọi phần tử vô hướng Hai từ khác không bxα1 · · · xαnn bxα1 · · · xαnn gọi đồng dạng với Như xem đơn thức từ với hệ số 1, phần tử vô hướng a từ a · Kí hiệu x = (x1 , , xn ), a = (a1 , , an ) ∈ Nn xa = xa11 · · · xann Đa thức n biến x1 , , xn vành Zm tổng hình thức từ: aα xα f (x) = α∈Nn aα ∈ Zm có số hữu hạn hệ số aα = Từ aα xα với aα = gọi từ đa thức f (x) xα đơn thức f (x) aα xα g(x) = Hai đa thức f (x) = α∈Nn n bα xα xem nhau, α∈Nn aα = bα với α ∈ N Phép cộng đa thức định nghĩa sau: aα xα ) + ( ( α∈Nn (aα + bα )xα bα x α ) = α∈Nn α∈Nn Phép nhân đa thức định nghĩa sau: ( aα xα )( α∈Nn bα xα ) = α∈Nn cα x α , α∈Nn cα = aβ bγ β,γ∈Nn ,β+γ=α aα xα là: Định nghĩa 1.1.1 [1, tr.32] Bậc tổng thể đa thức f (x) = α∈Nn degf (x) = max{α1 + · · · + αn |aα = 0} Đối với đa thức biến, bậc tổng thể bậc thơng thường Đơi bậc tổng thể đa thức nhiều biến gọi tắt bậc, khơng có hiểu nhầm xảy Định nghĩa 1.1.2 [6, tr.6] Cho I iđêan vành Zm [x1 , , xn ] Nếu tồn đa thức f1 , f2 , , fs ∈ Zm [x1 , , xn ] cho I = f1 , f2 , , fs I gọi có tập sinh hữu hạn hay hữu hạn sinh Định lý 1.1.3 [6, tr.6] Cho vành Zm [x1 , , xn ] , mệnh đề sau tương đương: (i) Với iđêan I ⊆ Zm [x1 , , xn ] tồn f1 , f2 , , fs ∈ I cho I = f1 , f2 , , fs (ii) Mọi dãy tăng iđêan Zm [x1 , , xn ] sau: I1 ⊆ I2 ⊆ · · · ⊆ In ⊆ · · · tồn N cho IN = IN +1 = IN +2 = · · · Tức là, vành Zm [x1 , , xn ] Noetherian iđêan Zm [x1 , , xn ] có tập sinh hữu hạn 2.2 Xây dựng chương trình Chương trình C bắt đầu thực dòng lệnh đặt hàm main() Hàm main trình biên dịch gọi thực ko phân biệt vị trí đặt hàm Việc thực thi hàm khai báo theo trình tự từ xuống dưới, chương trình C, cần số thư viện , để thực việc nhập vào từ bàn phím xuất giá trị hình Từ ta xây dựng chương trình sau: #include #include #include #include #include #include #include //Số lượng đa thức #define countOfP(f) ((f)->count) //Lấy đa thức triệt tiêu thứ i #define VanishingPoly(f,i) (((f)->term)[i]) typedef struct v_poly { int count; int term[50][4]; } V_Poly; //Thực tính tốn void execute(int M, int N, V_Poly *G ); //Tìm số nguyên tố lớn int isPrimeNumber(int num); //Khai báo biểu thức p void p(int alpha, int a, int l); //Gán phần tử p vào pInput void setV_Poly(int alpha1, int alpha2, int alpha3, int a, 31 V_Poly *pInput); //Tìm a ước m void divide (int m, int ret[]); //Tìm S void S(int a[], int m, V_Poly *S); //So sánh Sm SM trả Sm SM int compareP(int Sm[], int SM[]); //Gán giá trị p vào pInput void setV_PolytoV_Poly(int p[], V_Poly *pInput); //Tìm x void findBeta(int alpha[], int * beta[]); //Tính (alpha+beta)! int factorialVector(int alpha[], int beta[]); //Tính ước chung lớn a,b int gcd(int a,int b); //In biểu thức p void printP(V_Poly *G); //Hàm tính giai thừa int factorial(int num); //Tìm x cho a m int findX(int a, int m); //Tìm số nguyên tố bé int isSmallesPrime(int num); int M; int n; //FOR DEBUG int isDebug = 0; /* */ /* Thực tính tốn */ void execute(int M, V_Poly *G ){ countOfP(G) = 0; 32 //Tìm số nguyên tố lớn M int q = isPrimeNumber(M); int smallesPrime = isSmallesPrime(M); int m = 0; //Gm V_Poly Gm[50]; //Kiểm tra M = q if(q == -1){ setV_Poly(M,0,0,1, G); setV_Poly(0,M,0,1, G); setV_Poly(0,0,M,1, G); }else{ m = M/q; if(m > && isPrimeNumber(m) == -1 && m != q ){ // H= Gm setV_Poly(q,0,0,1, G); setV_Poly(0,q,0,1, G); setV_Poly(0,0,q,1, G); // H= Gm setV_Poly(m,0,0,q, G); setV_Poly(0,m,0,q, G); setV_Poly(0,0,m,q, G); //Tìm Sm V_Poly Sm[50]; int a[50]; //Tìm ước a m divide(m,a); //Tìm Sm S(a,m,Sm); 33 if(isDebug == 1){ printf("\n Sm :\n"); printP(Sm); } a[50] = {}; //Tìm SM V_Poly SM[50]; //Tìm ước a M divide(M,a); //Tính SM S(a,M,SM); if(isDebug == 1){ printf("\n SM :\n"); printP(SM); } //Kiểm tra Sm SM int isExist = 0; for(int i=0; i < countOfP(Sm); i++){ isExist = 0; for(int j = 0; j < countOfP(SM); j++){ //Kiem tra neu Sm(i) == SM(j) if(compareP(VanishingPoly(Sm, i), VanishingPoly(SM,j)) == 1){ isExist = 1; } } if(isExist == 1){ //Thêm Sm vào G setV_PolytoV_Poly(VanishingPoly(Sm, i), G); }else{ //Thêm Sm vào G 34 int temp[4] = {0,0,0,0}; temp[0] = VanishingPoly(Sm, i)[0]; temp[1] = VanishingPoly(Sm, i)[1]; temp[2] = VanishingPoly(Sm, i)[2]; temp[3] = VanishingPoly(Sm, i)[3]*q; //VanishingPoly(Sm, i)[3] = VanishingPoly(Sm, i)[3]*q; setV_PolytoV_Poly(temp, G ); //Xét Beta < Alpha int beta[3] ={0,0,0}; beta[0] = VanishingPoly(Sm, i)[0]; beta[1] = VanishingPoly(Sm, i)[1]; beta[2] = VanishingPoly(Sm, i)[2]; //findBeta(VanishingPoly(Sm, i), beta); for(int k = 0; ; k++){ if(beta[0] b) a=a-b; else b=b-a; return a; } /* */ /* Tìm a ước m */ void divide (int m, int ret[]){ int tt = 0; for(int a = 1; a < m; a++){ if(m%a == 0){ ret[tt++] = a; } } } /* */ 38 /* Tìm x */ int findX(int a, int m){ return m/a; } /* */ /* Tìm beta thỏa điều kiện */ void findBeta(int alpha[], int beta[]){ //beta = alpha; if(alpha[0] - > 0){ beta[0] = alpha[0] - 1; }else if(alpha[1] - > 0){ beta[1] = alpha[1] - 1; }else{ beta[2] = alpha[2] - 1; } } /* */ /* Tính(alpha+beta)! */ int factorialVector(int alpha[], int beta[]){ return factorial(alpha[0]+beta[0])*factorial(alpha[1] +beta[1])*factorial(alpha[2]+beta[2]); } /* */ /* Gán phần tử p vào pInput */ void setV_Poly(int alpha1, int alpha2, int alpha3, int a, V_Poly *pInput){ VanishingPoly(pInput,countOfP(pInput))[0] = alpha1; VanishingPoly(pInput,countOfP(pInput))[1] = alpha2; 39 VanishingPoly(pInput,countOfP(pInput))[2] = alpha3; VanishingPoly(pInput,countOfP(pInput))[3] = a; countOfP(pInput)++; } /* */ /* Gán giá trị p vào pInput */ void setV_PolytoV_Poly(int p[], V_Poly *pInput){ VanishingPoly(pInput,countOfP(pInput))[0] = p[0]; VanishingPoly(pInput,countOfP(pInput))[1] = p[1]; VanishingPoly(pInput,countOfP(pInput))[2] = p[2]; VanishingPoly(pInput,countOfP(pInput))[3] = p[3]; countOfP(pInput)++; } /* */ /* So sánh Sm SM trả Sm SM.*/ int compareP(int Sm[], int SM[]){ int ret = 1; if(Sm[0] != SM[0]){ ret = 0; } if(Sm[1] != SM[1]){ ret = 0; } if(Sm[2] != SM[2]){ ret = 0; } if(Sm[3] != SM[3]){ ret = 0; } return ret; 40 } /* */ /* RUN */ int main(){ char c; printf("Minimal Strong Grobner Basis"); printf("\n"); V_Poly G[50]; c = ’y’; printf("\nInput M = " ); scanf("%d" , &M); //printf("Input n = " ); //scanf("%d" , &n); execute(M, G); getchar(); return 0; } /* */ /* Tính giai thừa số truyền vào num */ int factorial(int num){ int ret = 1; for(int i=1;i