Luận văn Thuật toán slice cho phân tích bất khả quy của iđêan đơn thức

. Một iđêan đơn thức J ( R là m-bất khả quy nếu có hai iđêan đơn thức J1,J2 sao cho J = J1∩ J2 thì J = J1 hoặc J = J2. Ví dụ 1.3.2. Đặt R = A[X ,Y ], cho I = (X ,Y 2)R. Vì (X ,Y 2)R⊆ (X ,Y )R nên ta có viết I = (X ,Y 2)R∩ (X ,Y )R. Theo định nghĩa, ta có I là iđêan đơn thức m-bất khả quy. Định lý sau đây cho phép ta dễ dàng kiểm tra một iđêan đơn thức có là m-bất khả quy hay không. Định lý 1.3.3. Cho J là một iđêan đơn thức khác không của R. Iđêan J là m-bất khả quy nếu và chỉ nếu tồn tại các số nguyên dương k, t1, . . . , tk,e1, . . . ,ek sao cho 1≤ t1, . . . , tk ≤ d và J = (Xe1t1 , . . . ,Xe k tk )R. 12 Ví dụ 1.3.4. Đặt R = A[X ,Y,Z,W ]. Khi đó theo định lý trên các iđêan đơn thức I = (X ,Y 2)R, J = (Y 3,Z,W 2) là các iđêan đơn thức m-bất khả quy. Iđêan m-bất khả quy theo nghĩa nào đó là iđêan đơn thức đơn giản nhất, trong đó chúng không viết được thành giao của các iđêan đơn thức không tầm thường. Tuy nhiên trong vành đa thức bất kỳ, một iđêan đơn thức là bất khả quy thì cũng là m-bất khả quy, nhưng điều ngược lại nhìn chung không đúng. Ví dụ trong vành Z6[X ] iđêan 0 là m-bất khả quy nhưng lại là khả quy trong Z6[X ]. Định lý sau cho ta điều kiện của vành A để điều ngược lại cũng đúng. Định lý 1.3.5. Cho A là một miền nguyên, và đặt R = A[X1, . . . ,Xd]. Một iđêan đơn thức khác không J ( R là bất khả quy nếu và chỉ nếu nó là m-bất khả quy. Tương tự phân tích bất khả quy, một kết quả quan trọng sau được chứng minh bởi Emmy Noether cũng cho phép đưa ra khái niệm phân tích bất khả quy rút gọn. Định lý 1.3.6. Nếu J ( R là một iđêan đơn thức thì có các iđêan đơn thức m-bất khả quy J1, . . . ,Jn của R sao cho J = ∩ni=1Ji. Định nghĩa 1.3.7. Cho J ( R là một iđêan đơn thức. Một phân tích m-bất khả quy của J là biểu diễn J = ∩ni=1Ji trong đó mỗi Ji là m-bất khả quy, sự phân tích này là rút gọn nếu Ji * Ji′ với mọi chỉ số i 6= i′. Hơn nữa, phân tích m-bất khả quy rút gọn là duy nhất nếu không kể đến thứ tự các nhân tử và ta ký hiệu tập các iđêan đơn thức m-bất khả quy trong phân tích m-bất khả quy rút gọn của J là irr(J). Ví dụ 1.3.8. Đặt R = A[X ,Y ]. Cho J = (X4,XY 2,Y 3)R. Khi đó, các phân tích m-bất khả quy của J J = (X ,Y 3)R∩ (X4,Y 2)R∩ (X ,Y )R = (X ,Y 3)R∩ (X4,Y 2)R∩ (X2,Y 2)R là không rút gọn vì (X4,Y 2)R ⊆ (X ,Y )R, (X4,Y 2)R ⊆ (X2,Y 2)R. Rõ ràng rằng sự phân tích m-bất khả quy không rút gọn của J là không duy nhất. 13 Mặt khác, vì ta có X ∈ (X ,Y 3)R\ (X4,Y 2)R và Y 2 ∈ (X4,Y 2)R\ (X ,Y 3)R nên (X ,Y 3)R * (X4,Y 2)R và (X4,Y 2)R * (X ,Y 3)R. Do đó phân tích m-bất khả quy J = (X ,Y 3)R∩ (X4,Y 2)R là rút gọn và duy nhất. Sau đây là một thuật toán để tìm phân tích m-bất khả quy rút gọn. Thuật toán 1.3.9. Đặt R = A[X1, . . . ,Xd]. Cho J là một iđêan đơn thức có phân tích m-bất khả quy là J = ∩ni=1Ji. Chú ý rằng n> 1. Bước 1: Kiểm tra xem phân tích J = ∩ni=1Ji đã rút gọn chưa. Bước 1a: Nếu với mọi chỉ số j và j′ sao cho j 6= j′, ta có J j * J j′ thì J = ∩ni=1Ji là rút gọn; trong trường hợp này, thuật toán dừng lại. Bước 1b: Nếu tồn tại chỉ số j và j′ sao cho j 6= j′ ta có J j ⊆ J j′ thì J = ∩ni=1Ji là không rút gọn; trong trường hợp này, ta tiếp tục bước 2. Bước 2: Nếu tồn tại chỉ số j, j′ sao cho j 6= j′ và J j ⊆ J j′ thì ta loại bỏ iđêan J j′. Không mất tính tổng quát, ta có thể giả thiết j′ = n và sắp xếp lại các chỉ số sao cho J j ⊆ J j′ với j < n. Suy ra J = ∩ni=1Ji = ∩n−1i=1 Ji. Bước 3: Áp dụng bước 1 cho phân tích mới J = ∩n−1i=1 Ji. Thuật toán sẽ dừng lại sau n− 1 bước vì ta có thể loại bỏ nhiều nhất là n− 1 iđêan đơn thức trong giao và cuối cùng thu được một iđêan là giao khác rỗng của các iđêan m-bất khả quy. Tiếp theo cho các phân tích m-bất khả quy của các iđêan đơn thức I = ∩nj=1I j và J = ∩mi=1Ji. Ta quan tâm tới phân tích m-bất khả quy của I+J. Ta đã biết tổng của các iđêan đơn thức là một iđêan đơn thức. Hơn nữa ta có Mệnh đề 1.3.10. Nếu J1, . . . ,Jn là các iđêan đơn thức m-bất khả quy của R thì tổng J1 + . . .+ Jn là m-bất khả quy. Kết quả sau cho ta luật phân phối của giao đối với tổng của các iđêan đơn thức. Bổ đề 1.3.11. Cho các iđêan đơn thức I1, . . . , In và J1, . . . ,Jm của R. Khi đó ta có (∩nj=1I j)+(∩mi=1Ji) = ∩nj=1∩mi=1 (I j + Ji). 14 Kết quả tiếp theo là làm thế nào để xây dựng phân tích m-bất khả quy cho tổng của các iđêan đơn thức. Định lý 1.3.12. Cho I,J là các iđêan đơn thức của R với phân tích m-bất khả quy I = ∩nj=1I j và J = ∩mi=1Ji. Khi đó phân tích m-bất khả quy của I + J là I+ J = ∩nj=1∩mi=1 (I j + Ji). Ví dụ 1.3.13. Đặt R = A[X ,Y,Z]. Cho I = (X3,X2Y,X3Z4,Y Z)R = (X2,Z)R∩ (X3,Y )R;J = (Y 3,Z4)R. Khi đó ta có phân tích m-bất khả quy rút gọn của I + J là I + J = (X3,X2Y,X3Z4,YZ,Y 3,Z4)R = ((X2,Z)R+(Y 3,Z4)R)∩ ((X3,Y )R+(Y 3,Z4)R) = (X2,Y 3,Z)R∩ (X3,Y,Z4)R. 1.4 Phân tích tham số của các iđêan đơn thức 1.4.1 Iđêan tham số Định nghĩa 1.4.1. Một iđêan tham số trong R là một iđêan có dạng (Xa11 , . . . ,X ad d )R, với a1, . . . ,ad ≥ 1. Nếu cho đơn thức f = Xn với n∈Nd thì iđêan tham số ứng với f là PR( f ) = (Xn1+11 , . . . ,Xnd+1d )R. Ví dụ 1.4.2. Cho R = A[X ,Y ]. (i) Cho đơn thức f =XY, khi đó ta có iđêan tham số của f là PR(XY )= (X2,Y 2)R. Quan sát đồ thị Hình 1.6, ta thấy rằng ký hiệu q trong đồ thị của PR(XY ) tương ứng với đơn thức XY. (ii) Đặc biệt PR(1) = (X ,Y )R,PR(X) = (X2,Y ) và PR(Y ) = (X ,Y 2). 15 1 2 3 4 1 2 3 4 q . . . . . . . . . . . . ... ... ... ... ... 0 0 Hình 1.6: Γ(PR(XY )) Bổ đề sau cho ta một công cụ hữu ích để làm việc với các iđêan tham số. Bổ đề 1.4.3. Cho f ,g là các đơn thức trong R. Khi đó: (i) f /∈ PR( f ). (ii) g ∈ PR( f ) nếu và chỉ nếu f /∈ (g)R. Định nghĩa 1.4.4. Cho J là một iđêan đơn thức của R. Một phân tích tham số của J là phân tích có dạng J = ∩ni=1 PR(zi). Hơn nữa, phân tích này là phân tích tham số rút gọn nếu với mọi j 6= j′ ta có PR(z j)* PR(z j′). Chú ý 1.4.5. (i) Một iđêan đơn thức J của R có thể có hoặc không có phân tích tham số và mục tiếp theo chỉ ra rằng điều kiện cần và đủ để J có phân tích tham số là m-rad(J) = X. (ii) Định lý 1.3.3 chỉ ra rằng mọi iđêan tham số trong R là m-bất khả quy. Vì thế, mỗi phân tích tham số của J là một phân tích m-bất khả quy. Cũng vậy, mỗi một phân tích tham số là rút gọn nếu và chỉ nếu nó là một phân tích m-bất khả quy rút gọn. Hơn nữa, mỗi phân tích tham số rút gọn là duy nhất nếu không kể đến thứ tự các nhân tử. 1.4.2 Phần tử góc Mục này đưa ra một công thức để tính phân tích tham số rút gọn. Trước hết ta có định nghĩa sau. Định nghĩa 1.4.6. Cho J là một iđêan đơn thức trong R. Một đơn thức z ∈ [[R]] 16 là phần tử J-góc nếu z /∈ J và X1z, . . . ,Xdz ∈ J. Tập hợp các phần tử J-góc của J trong [[R]] được ký hiệu là CR(J). Ví dụ 1.4.7. Cho R = A[X ,Y ],J = (X3,X2Y,XY 2,Y 3). Khi đó ta có tập phần tử J-góc của J là CR(J) = {X2,XY,Y 2}. Kết quả dưới đây cho ta mối quan hệ chặt chẽ giữa các phần tử góc và phân tích tham số rút gọn của một iđêan đơn thức. Định lý 1.4.8. Đặt X = (X1, . . . ,Xd)R và J là iđêan đơn thức của R sao cho m- rad(J) = X. Nếu các phần tử J-góc phân biệt là z1, . . . ,zm thì J = ∩mj=1 PR(z j) là phân tích tham số rút gọn của J. Chứng minh. Chú ý rằng [5, Mệnh đề 6.3.4] đã chỉ ra rằng J có một phần tử góc. Đặt J′ = ∩mj=1 PR(z j), theo [5, Hệ quả 6.3.3] suy ra giao này là rút gọn và J′ ⊆ J. Do đó ta sẽ chỉ ra J′ ⊇ J. Vì PR(z j) là một iđêan đơn thức, Định lý 1.2.1 chỉ ra rằng J′ là một iđêan đơn thức. Giả sử ngược lại J′ ( J. Theo [5, Mệnh đề 6.3.4] suy ra J′ chứa một phần tử J-góc, hay zi ∈ J′. Do đó zi ∈ PR(zi), điều này mâu thuẫn với Bổ đề 1.4.3 (i). Định lý 1.4.8 chỉ ra rằng các phần tử J-góc hoàn toàn xác định một phân tích tham số rút gọn của J và kết quả dưới đây cũng chỉ ra rằng một phân tích tham số rút gọn của J cũng xác định các phần tử J-góc. Mệnh đề 1.4.9. Cho các đơn thức z1, . . . ,zm ∈ [[R]] và giả sử J = ∩mj=1 PR(z j) là một phân tích tham số rút gọn của J. Khi đó các phần tử J-góc phân biệt là z1, . . . ,zm. 17 Chương 2 Thuật toán Slice Trong chương này, ta sẽ giới thiệu về thuật toán Slice, một thuật toán dùng để tính phân tích bất khả quy của iđêan đơn thức, nghĩa là viết iđêan đơn thức đó thành giao rút gọn của các iđêan bất khả quy thông qua việc tính tập các đơn thức chuẩn cực đại. Cho k là một trường và đặt R = k[x1, . . . ,xn] với n> 2 là vành đa thức n biến lấy hệ số trên k, I là iđêan đơn thức của R. Thuật toán Slice cung cấp một công cụ để tính tập các đơn thức chuẩn cực đại msm(I) bằng cách tách nó thành hai tập con gọi là slice trong và slice ngoài. Cả hai slice này đều phụ thuộc vào cách chọn một đơn thức gọi là then chốt. Các đơn thức của mỗi slice này lại được coi như tập chuẩn cực đại của các iđêan mới. Tiếp theo mỗi slice này lại được tách thành các slice đơn giản hơn và quá trình này tiếp tục cho đến khi tách thành những slice đủ đơn giản để có thể tính được tập các đơn thức chuẩn cực đại của chúng. Các kết quả của chương này được viết dựa theo [6]. Chú ý rằng vì R là vành đa thức lấy hệ số trên trường k nên theo các kết quả của chương 1 ta không phân biệt các khái niệm rad, m-rad, bất khả quy và m-bất khả quy. 2.1 Đơn thức chuẩn cực đại, đế và sự phân tích Trong phần này ta sẽ tìm hiểu về đơn thức chuẩn cực đại, đế và mối quan hệ giữa chúng. Cho I là iđêan đơn thức và min(I) là tập các phần tử sinh rút gọn của I. Định nghĩa 2.1.1. Đơn thức m được gọi là đơn thức chuẩn của I nếu m /∈ I, m được gọi là đơn thức chuẩn cực đại của I nếu m /∈ I và mxi ∈ I với i = 1, . . . ,n. 18 Tập các đơn thức chuẩn cực đại ký hiệu là msm(I). Nhận xét 2.1.2. Tập các đơn thức chuẩn cực đại msm(I) chính là tập các phần tử góc trong Định nghĩa 1.4.6. Ví dụ 2.1.3. (i) Cho iđêan đơn thức I = (x6,x5y2,x2y4,y6). Khi đó tập chuẩn cực đại msm(I) = {x5y,x4y3,xy5} vì theo định nghĩa các đơn thức x5y,x4y3,xy5 /∈ I và x5y.y = x5y2 ∈ I,x5y.x = x6y ∈ I. Tương tự đối với các đơn thức x4y3,xy5. (ii) Cho iđêan đơn thức J = (x5y2,x2y4). Tương tự (i), ta có msm(J) = {x4y3}. (iii) Cho iđêan đơn thức K = (x5y2). Khi đó ta có msm(K) = /0. Thật vậy, nếu gọi tập các đơn thức không thuộc K là S thì ta có S = {x,x2,x3,x4,y,xy,x2y,x3y,x4y}. Tuy nhiên, ta thấy mix /∈ K và miy /∈ K, với mọi đơn thức mi ∈ S. Ta có thể kiểm tra bằng cách quan sát đồ thị Hình 2.1 . y6 x2y4 x5y2 x6 xy5 x4y3 x5y x2y4 x4y3 x5y2 q q q q Hình 2.1: Cho R là vành giao hoán, Noether, M là R-môđun. Nhắc lại rằng, đế của một môđun M, ký hiệu là Soc(M) là môđun con của M Soc(M) = {∑N | N là môđun con đơn của M}. Nếu (R,m,k) là vành giao hoán, Noether, địa phương thì Soc(M) = 0 :M m∼= HomR(k,M). Trên vành đa thức R = k[x1, . . . ,xn], cho tập các phần tử sinh rút gọn min(I), theo định nghĩa đế và tập đơn thức chuẩn cực đại, ta có Soc(R/I) = 0 :R/I (x1, . . . ,xn) = {m+ I|mxi ∈ I, i = 1, . . . ,n} = {m+ I | m ∈msm(I)}. 19 Do đó đế của R/I là một không gian véc tơ hữu hạn chiều và khi đó ta có tập {m+ I | m ∈ msm(I)} lập thành một cơ sở của đế. Vì thuật toán Slice cho phép tính tập các đơn thức chuẩn cực đại msm(I) nên để tìm phân tích bất khả quy irr(I) ta có thể quy về việc tính tập msm(I). Ta đã biết rằng, nếu J là iđêan đơn thức của R sao cho m-rad(J) = X thì theo Định lý 1.4.8 có thể tính phân tích bất khả quy irr(J) bằng cách dùng các phần tử góc (hay chuẩn cực đại). Tuy nhiên, nếu m-rad 6= X thì ta có thể cộng vào J một iđêan đơn thức m-bất khả quy K sao cho m-rad(J +K) = X và có thể áp dụng các kết quả ở Mệnh đề 1.3.10 và Định lý 1.3.12 để tìm irr(J+K) rồi sau đó sẽ tìm được irr(J). Bây giờ ta sẽ mô tả ngắn gọn kỹ thuật của Bayes và cộng sự [1], Miller và Sturmfels [4] để tính irr(I) thông qua msm(I). Chọn t ≫ 0 là số nguyên đủ lớn và định nghĩa φ(xm) = (xmi+1i |mi +1 < t). Mệnh đề 2.1.4. ([4]). Ánh xạ φ là một song ánh từ tập msm(I+(xt1, . . . ,xtn)) vào tập irr(I). Cho f = Xm với m ∈ Nn. Khi đó theo Định nghĩa 1.4.1, iđêan tham số ứng với f là PR( f ) = (xm1+11 , . . . ,xmn+1n )R. Nếu ta ký hiệu P̂Rt ( f ) = (xmi+1i | mi + 1 < t) thì P̂Rt ( f )⊆ PR( f ). Ví dụ, cho R = k[x,y,z,w], ta có PR(x5y2z3w) = (x6,y3,z4,w2) và P̂R6(x 5y2z3w) = (y3,z4,w2) khi chọn t = 6. Để chứng minh mệnh đề trên, ta cần bổ đề sau: Bổ đề 2.1.5. Cho I là iđêan đơn thức của R và X t = (xt1, . . . ,xtn), với t ≫ 0 sao cho các đơn thức sinh của I đều chứa lũy thừa thực sự nhỏ hơn t. Khi đó nếu tập các đơn thức chuẩn cực đại của I +X t là msm(I + X t) = {z1, . . . ,zm} thì I = ∩mj=1P̂Rt (z j) là một phân tích tham số rút gọn của I. Chứng minh. Chú ý rằng vì m-rad(I+X t) =X nên theo Định lý 1.4.8, ta có phân tích tham số rút gọn của I +X t là I +X t = ∩mj=1PR(z j). Vì thế I ⊆ PR(z j), với mọi j. Nhưng vì các đơn thức sinh của I chứa các lũy thừa thực sự nhỏ hơn t nên I ⊆ P̂Rt(z j), với mọi j. Do đó I ⊆ ∩mj=1P̂Rt (z j). Ngược lại, lấy một đơn thức sinh bất kỳ f ∈ ∩mj=1P̂Rt (z j)⊆ ∩mj=1PR(z j) = I+X t . 20 Khi đó theo Mệnh đề 1.2.5, f là tích của các lũy thừa của xi, mỗi lũy thừa đều thực sự nhỏ hơn t. Vì f là một đơn thức và I +X t là iđêan đơn thức nên f /∈ X t , do đó f ∈ I. Vậy I = ∩mj=1P̂Rt (z j). Bây giờ, ta tiếp tục chứng minh mệnh đề. Theo Chú ý 1.4.5, vì mỗi phân tích tham số rút gọn của I đều là phân tích bất khả quy rút gọn của I nên khi đó ta có irr(I) = {P̂Rt(z j), j = 1, . . . ,m}. Vì thế, ta định nghĩa φ là ánh xạ cho bởi mỗi đơn thức chuẩn cực đại z j của msm(I +(xt1, . . . ,x t n)) ứng với một thành phần bất khả quy của irr(I). Khi đó theo Bổ đề trên rõ ràng φ là song ánh. Để minh họa cho kết quả trên ta hãy xét một số ví dụ sau. Ví dụ 2.1.6. (i) Cho I = (x2,xy) và chọn t = 3. Đặt I′ = I +(xt ,yt) = (x2,xy,y3). Khi đó theo định nghĩa msm(I′) = {x,y2}. Ta xác định song ánh φ như sau φ : msm(I′)→ irr(I) (x) 7→ (x2,y) (y2) 7→ (x) Vì thế theo Mệnh đề 2.1.4, phân tích bất khả quy rút gọn của I là I = (x)∩(x2,y). (ii) Cho I = (xy3,x2y2) và chọn t = 4. Đặt I” = (I +(xt ,yt)) = (x4,x2y2,xy3,y4). Khi đó msm(I”) = {x3y,xy2,y3}. Theo Mệnh đề 2.1.4, ta xác định song ánh φ như sau: f : msm(I”)→ irr(I) (y3) 7→ (x) (x3y) 7→ (y2) (xy2) 7→ (x2,y3) Do đó ta có phân tích bất khả quy rút gọn của I là I = (x)∩ (y2)∩ (x2,y3). (iii) Cho J = (x6,x5y2,x2y4,y6), chọn t = 7. Đặt J′ = (J+(xt ,yt)) = (x6,x5y2,x2y4,y6). Ta có thể tính được msm(J′) = {xy5,x4y3,x5y}. Tương tự các ý trên, áp dụng song ánh φ , ta có phân tích bất khả quy của J là J = (x2,y6)∩ (x5,y4)∩ (x6,y2). 21 2.2 Nhãn Cho m là một đơn thức. Nhắc lại rằng véc tơ lũy thừa υ ∈ N của đơn thức m được định nghĩa là m = xυ = xυ11 . . .x υn n và degxi(x υ) := υi. Định nghĩa 2.2.1. Cho d là một đơn thức chuẩn của I và m ∈ min(I). Khi đó m là xi-nhãn cuả d nếu m | dxi. Chú ý 2.2.2. (i) Nếu m là xi-nhãn của d thì degxi(m) = degxi(d)+1. (ii) Một đơn thức d là chuẩn cực đại khi và chỉ khi nó có xi-nhãn mi, với mọi i = 1, . . . ,n. Do đó trong trường hợp này dx1 . . .xn = lcmni=1 mi. Ví dụ 2.2.3. Cho I = (x2,xz,y2,yz,z2). (i) Ta có tập các đơn thức chuẩn cực đại của I là msm(I) = {z,xy}. Xét đơn thức z ∈msm(I). Ta có xz là x-nhãn của z vì xz | zx, yz là y-nhãn của z vì yz | zy và z2 là z-nhãn của z vì z2 | zz. Đối với đơn thức xy ∈ msm(I). Ta có x2 là x-nhãn của xy vì x2 | xyx, y2 là y-nhãn của xy vì y2 | xyy và cả hai đơn thức xz, yz đều là z-nhãn của xy vì xz | xyz và yz | xyz. (ii) Cho J := I+(xy). Khi đó msm(J) = {x,y,z}. Chú ý rằng mặc dù xy là x-nhãn của y, là y-nhãn của x nhưng xy không là x-nhãn, y-nhãn và z-nhãn của z vì xy không là ước của zx,zy và zz. 2.3 Thuật toán Slice Trong mục này ta sẽ mô tả phiên bản cơ sở của thuật toán Slice. Thuật toán Slice dùng để tính tập msm(I), trong đó I là iđêan đơn thức với tập sinh rút gọn min(I) đã cho trước. Ý tưởng cơ bản của thuật toán Slice là quan tâm đến các tập con của tập msm(I) được biểu diễn thành các slice. Thuật toán bắt đầu bằng cách xem xét một slice đại diện cho tất cả các đơn thức chuẩn cực đại của msm(I). Sau đó tách slice đó thành hai slice đơn giản hơn. Quá trình này tiếp tục cho đến khi tách thành những slice đủ đơn giản để có thể dễ dàng tính được các đơn thức chuẩn cực đại của chúng. Trước hết ta cần các kết quả sau. 22 Bổ đề 2.3.1. Cho A,B,C là các iđêan đơn thức. Khi đó nếu A∩B = B∩C thì ta có msm(A)∩C = msm(B)∩C. Chứng minh. Lấy bất kỳ d ∈ msm(A)∩C. Ta cần chứng minh d ∈ msm(B) tức là chứng minh d /∈ B và dxi ∈ B. Thật vậy, giả sử ngược lại d ∈ B. Khi đó d ∈ B∩C = A∩C, mà d ∈ msm(A) nên d /∈ A, mâu thuẫn. Vậy d /∈ B. Mặt khác vì d ∈ msm(A) nên dxi ∈ A, suy ra dxi ∈ A∩C = B∩C, hay dxi ∈ B. Khi đó ta có d ∈msm(B), suy ra msm(A)∩C ⊆msm(B)∩C. Tương tự msm(B)∩C ⊆msm(A)∩C. Vậy msm(A)∩C = msm(B)∩C. Cho m là một đơn thức. Ta định nghĩa pi(m) := m√ m . Ví dụ pi(x(0,1,2,3)) = pi(x01x 1 2x 2 3x 3 4) = x01x 1 2x 2 3x 3 4√ x01x 1 2x 2 3x 3 4 = x01x 0 2x 1 3x 2 4 = x (0,0,1,2). Mệnh đề 2.3.2. Cho I là một iđêan đơn thức và p là một đơn thức. Khi đó (i) gcd(min(I)) | gcd(msm(I)); (ii) msm(I)∩ (p) = msm(I∩ (p)); (iii) Nếu p | gcd(min(I)) thì msm(I) = msm(I : p)p; (iv) msm(I)∩ (p) = msm(I : p)p; (v) msm(I)\S = msm(I′)\S, trong đó I′ = (m ∈min(I)|pi(m) /∈ S). Chứng minh. (i) Lấy d ∈ msm(I). Cho li, l j ∈ min(I) lần lượt là các xi,x j-nhãn của d, trong đó i 6= j vì ta đã giả thiết n> 2. Theo Định nghĩa 2.2.1 ta có li | dxi và l j | dx j.Từ đó ta có gcd(min(I)) | gcd(li, l j) | d gcd(xi,x j) | d (do xi 6= x j). Vì d là một đơn thức bất kỳ của msm(I) nên suy ra gcd(min(I)) | gcd(msm(I)). (ii) Đặt A = msm(I),C = (p),B = msm(I ∩ (p)). Khi đó theo Bổ đề 2.3.1, nếu như ta có A∩C = B∩C thì suy ra msm(A)∩C = msm(B)∩C. Khi đó ta có msm(I)∩ (p) = msm(I∩ (p))∩ (p). Vật ta cần chứng minh msm(I∩ (p))⊆ (p). 23 Thật vậy, lấy d ∈msm(I∩ (p)). Khi đó tồn tại li ∈min(I∩ (p)) sao cho li | dxi và tồn tại li′ sao cho li = pli′ . Ta có p | pli′ | dxi suy ra p | gcd(dx1, . . . ,dxn) = d nên d ∈ (p).Vậy msm(I∩ (p))⊆ (p). (iii) Nếu p | gcd(min(I)) thì theo (i) ta có p | gcd(msm(I)). Lấy d ∈ msm(I). Ta có d = d p p ∈msm(I)⇔ d p p /∈ I, d p pxi ∈ I ⇔ d p /∈ I : p, d p xi ∈ I : p Từ đó suy ra d p ∈msm(I : p), suy ra d ∈msm(I : p)p. Vậy msm(I)⊆msm(I : p)p. Ngược lại, bằng cách chứng minh tương tự ta cũng có msm(I : p)p⊆msm(I). (iv) Hiển nhiên ta có (I ∩ (p)) : p = I : p suy ra msm(I ∩ (p)) : p = msm(I : p). Mặt khác, vì p | gcd(min(I∩ (p)) nên msm(I∩ (p)) = msm((I∩ (p)) : p)p (theo (iii)). Vì vậy msm(I)∩ (p) = msm(I∩ (p)) = msm((I∩ (p)) : p)p = msm(I : p)p, trong đó đẳng thức thứ nhất là theo (ii). (v) Lấy d ∈msm(I)\S ta cần chứng minh d ∈msm(I′)\S hay d ∈msm(I′). Thật vậy, vì d ∈ msm(I) nên d /∈ I suy ra d /∈ I′ do I′ ⊆ I. Lấy l là xi-nhãn của d. Khi đó l ∈min(I) và l | dxi. Ta có l ∈min(I′) do pi(l) | d /∈ S. Suy ra dxi ∈ I′ do l | dxi. Vậy d ∈msm(I′)\S. Ngược lại, lấy d ∈ msm(I′) \ S ta cần chứng minh d ∈ msm(I) \ S hay chứng minh d ∈ msm(I). Thật vậy vì dxi ∈ I′ ⊆ I nên dxi ∈ I. Mặt khác, giả sử d ∈ I, tồn tại m ∈ min(I)\min(I′) sao cho m | d vì m /∈ min(I′) nên pi(m) ∈ S điều này mâu thuẫn vì pi(m) | m | d /∈ S. Vậy điều giả sử là sai suy ra d /∈ I. Vậy ta có d ∈msm(I)\S. Tiếp theo ta sẽ đưa ra các định nghĩa slice, cái chứa của nó và làm thế nào để tách chúng. Định nghĩa 2.3.3. Một slice là bộ ba (I,S,q), trong đó I,S là các iđêan đơn thức và q là một đơn thức. 24 Cái chứa của slice (I,S,q), ký hiệu con(I,S,q), được định nghĩa là con(I,S,q) = (msm(I)\S)q. Ví dụ 2.3.4. Cho I là một iđêan đơn thức bất kỳ. Lấy S = 0,q = 1. Khi đó cái chứa của slice (I,0,1) là con(I,0,1) = (msm(I)\0)1 = msm(I). Định nghĩa 2.3.5. Một slice (I,S,q) được gọi là chuẩn tắc nếu pi(min(I))∩S = /0. Ví dụ 2.3.6. Cho I1 = (x6,x5y2,x2y4,y6), I2 = (x6,x5y2,y6), p = xy3. Xét slice (I1,(p),1). Ta có pi(min(I1))= pi(x6,x5y2,x2y4,y6)= (x5,x4y,xy3,y5) suy ra pi(min(I1))∩ (p) = xy3 6= /0. Vậy (I1,(p),1) không là slice chuẩn tắc. Xét slice (I2,(p),1). Khi đó ta có pi(min(I2)) = pi(x6,x5y2,y6) = (x5,x4y,y5), suy ra pi(min(I2))∩ (p) = /0. Vậy (I2,(p),1) là slice chuẩn tắc. Ví dụ sau sẽ cho thấy các khái niệm trên được dùng như thế nào trong việc mô tả các bước của thuật toán. Ví dụ 2.3.7. Cho iđêan đơn thức I = (x6,x5y2,x2y4,y6), và đơn thức p = xy3. Qua đồ thị ở Hình 2.2 ta có thể tính được tập msm(I) = {x5y,x4y3,xy5}. Bây giờ ta sẽ mô tả từng bước tính msm(I) để hình thành nên các bước của thuật toán. Hiển nhiên ta có msm(I) = (msm(I)\ (p))∪ (msm(I)∩ (p)). (2.3.1) trong đó hợp là rời nhau. Đặt I1 = I : p = (y3,xy,x4), suy ra msm(I1) = {x3,y2}. Ta có thể thấy qua so sánh Hình 2.2(a) và Hình 2.2(b) rằng I1 tương ứng là một phần của I nằm ở phía bên trong của (p). Điều này khiến ta dự đoán rằng msm(I1)⊆msm(I) cũng tương ứng nằm ở phía bên trong của (p). Ta sẽ chứng tỏ rằng điều dự đoán này là đúng. Trước hết ta có msm(I1)p = {x4y3,xy5}= msm(I)∩ (p). (2.3.2) 25 p y 3 xy x4 y6 x2y4 x5y2 x6 y6 x5y2 x6 p (a) (b) (c) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ... ... ... ... ... ... . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ...... ... ... ... ... q q q q Hình 2.2: Bây giờ ta chỉ cần tính msm(I) \ (p). Chọn iđêan I2 gồm các đơn thức thuộc min(I) nhưng không thuộc (p). Vì thế I2 = {x6,x5y2,y6} (được vẽ trong Hình 2.2(c)) và msm(I2) = {x5y,x4y5} (được minh họa bởi ký hiệu q như trong hình). Quan sát hình vẽ ta thấy đường nét đứt cho phép ta có thể bỏ qua những phần tử của min(I) nằm trong (p), đó là đơn thức x2y4. Sở dĩ ta chọn I2 vì msm(I2)\ (p) = {x5y}= msm(I)\ (p). (2.3.3) Từ các đẳng thức 2.3.2 và 2.3.3 ta có thể tính được msm(I) thông qua msm(I1), msm(I2) và (p) như sau: msm(I) = (msm(I1)p)∪ (msm(I2)\ (p)) = {xy5,x4y3,x5y}. Bây giờ chuyển sang ngôn ngữ của slice. Tách slice A = (I,(0),1) thành hai slice "nhỏ" hơn là A1 = (I1,(0), p) và A2 = (I2,(p),1). Theo Định nghĩa 2.3.3 và các Đẳng thức 2.3.2, 2.3.3 ta có con(A) = con(I,(0),1) = msm(I); con(A1) = con(I1,(0), p) = (msm(I1)\ (0))p = msm(I1)p = msm(I)∩ (p); con(A2) = con(I2,(p),1) = (msm(I2)\ (p))1 = msm(I2)\ (p) = msm(I)\ (p). Vì thế, từ các đẳng thức trên và Đẳng thức 2.3.1, ta có thể chuyển việc tính tập msm(I) sang việc tính cái chứa của nó như sau con(A) = con(A1)∪ con(A2), 26 trong đó hợp là rời nhau. Bây giờ cho một slice bất kỳ (I,S,q). Mục đích của ta là làm thế nào để tách (I,S,q) thành hai slice đơn giản hơn sao cho cái chứa của (I,S,q) là hợp rời nhau của hai cái chứa của hai slice sau khi tách. Để làm được điều này vấn đề đặt ra là cần chọn được một đơn thức p gọi là đơn thức then chốt thỏa mãn kết quả sau: Bổ đề 2.3.8. Cho một slice (I,S,q) và p là đơn thức then chốt. Khi đó con(I,S,q) = con(I : p,S : p,qp)∪ con(I,S+(p),q). (2.3.4) Chứng minh. Từ Đẳng thức 2.3.1 ta có con(I,S,q) = con(I,S,q)\ (qp)∪ con(I,S,q)∩ (qp). Ta sẽ chứng minh con(I,S,q)\ (qp) = con(I,S+(p),q). (2.3.5) con(I,S,q)∩ (qp) = con(I : p,S : p,qp). (2.3.6) Từ Định nghĩa 2.3.3 để chứng minh Đẳng thức 2.3.5, ta chỉ cần chứng minh (msm(I)\S)q\ (qp) = (msm(I)\S+(p))q. Thật vậy, lấy một đơn thức bất kỳ mq thuộc vế phải. Khi đó m∈msm(I)\S+(p), suy ra m ∈ msm(I) và m /∈ S và m /∈ (p). Do đó mq ∈ (msm(I)\S)q\qp hay vế phải nằm trong vế trái. Ngược lại, lấy đơn thức bất kỳ lq thuộc vế trái. Khi đó lq ∈ (msm(I) \ S)q và lq /∈ (qp). Suy ra l ∈ msm(I) \ S và l /∈ (p). Vì thế l ∈ msm(I) \ S+(p) hay lq ∈ (msm(I)\S+(p))q. Suy ra vế trái nằm trong vế phải. Tương tự, để chứng minh Đẳng thức 2.3.6, ta cũng chỉ cần chứng minh (msm(I)\S)q∩ (qp) = (msm(I : p)\S : p)qp. Thật vậy, lấy một đơn thức bất kỳ M thuộc vế trái. Khi đó ta có M = pqN trong đó N = msm(I) \ S. Suy ra pN ∈ msm(I)∩ (p) và pN /∈ S.Mà theo Mệnh đề 2.3.2,(iv) ta có msm(I)∩ (p) = msm(I : p)p. Suy ra pN ∈ msm(I : p)p và pN /∈ S, hay ta có N ∈msm(I : p)\S : p. Vậy M ∈ (msm(I : p)\S : p)qp. Suy ra vế trái nằm trong vế phải. 27 Ngược lại, lấy đơn thức bất kỳ M′ thuộc vế phải. Ta có M′ = qpN ′ suy ra ta có N ′ ∈ msm(I : p) \ (S : p). Khi đó N ′ ∈ msm(I : p) và N ′ /∈ S : p, suy ra pN ′ ∈msm(I : p)p và pN ′ /∈ S.Mà từ Mệnh đề 2.3.2, ta suy ra pN ′ ∈msm(I)∩ p và pN ′ /∈ S, hay M′ ∈ (msm(I)\S)q∩ (qp). Suy ra vế phải nằm trong vế trái. Đẳng thức 2.3.4 là công cụ cơ bản của thuật toán slice và quá trình áp dụng nó được gọi là quá trình tách then chốt. Đẳng thức 2.3.4 đề cập đến ba slice: slice (I,S,q) gọi là slice hiện tại vì nó là slice đang cần tách; slice (I : p,S : p,qp) được gọi là slice trong vì cái chứa của nó nằm bên trong (qp); slice (I,S+(p),q) được gọi là slice ngoài vì cái chứa của nó nằm ngoài (qp). Không phải hiển nhiên mà thấy được tại sao việc tính cái chứa của slice ngoài lại dễ hơn việc tính cái chứa của slice hiện tại. Vấn đề mấu chốt của điều này là đẳng thức đã được chứng minh trong Bổ đề 2.3.1 như sau: msm(I)\S = msm(I′)\S, trong đó I′ = (m ∈min(I)|pi(m) /∈ S). (2.3.7) Đẳng thức 2.3.7 kéo theo con(I,S,q) = con(I′,S,q). Nói cách khác ta có thể loại bỏ những đơn thức m ∈ min(I) mà pi(m) /∈ S (những đơn thức nằm trong phần màu trắng trên Hình 2.2). Đẳng thức 2