Luận văn Về Iđêan cạnh nhị thức

} là hệ sinh của iđêan I. Khi đó, G là cơ sở Gro¨bner của I khi và chỉ khi với mọi 1 ≤ i 6= j ≤ s, phần dư của S-đa thức S(gi, gj) đối với g1, . . . , gs bằng 0, kí hiệu S(gi, gj) G−→ 0. Chứng minh của Định lý trên cho ta một thuật toán tìm cơ sở Gro¨bner như sau: Input: I là iđêan tròn R, F tập các phần tử sinh của I. Output: Cơ sở Gro¨bner G của I. 12 Algorithm 1 Thuật toán Buchberger 1: procedure Buchberger(F ) 2: G := F 3: repeat 4: G ′ := G 5: for {p, q} ⊆ G′, p 6= q do 6: s := RemG(S(p, q)) 7: if s 6= 0 then 8: G := G ∪ {s} 9: end if 10: end for 11: until G = G′ 12: end procedure Thuật toán sẽ dừng sau một số hữu hạn bước và kết quả G là cơ sơ Gro¨bner của I (xem [7, Định ý 11.9]). Mệnh đề 1.1.18. Cho f và g là các đa thức khác không của R. Nếu in(f) và in(g) nguyên tố cùng nhau thì S(f, g) G−→ 0. Trở lại Ví dụ 1.1.14, áp dụng thuật toán Buchberger để tìm cơ sở Gro¨bner của iđêan trong ví dụ đó. Ví dụ 1.1.19. Xét với thứ tự từ điển phân bậc ≤glex, ta đặt G = {f, g} với f = x1x4 − x2x3 và g = x4x7 − x5x6. Ta có in(f) = x1x4 và in(g) = x4x7. Khi đó, S(f, g) = x7f − x1g = x1x5x6 − x2x3x7 =: h. Phần dư của S(f, g) đối với f, g là chính nó. Do đó, bổ sung h vào tập G để được G = {f, g, h}. Chú ý rằng in(h) = x1x5x6 mà in(g) = x4x7 nên 13 in(g) và in(h) nguyên tố cùng nhau. Bởi Mệnh đề 1.1.18, S(g, h) G−→ 0. Mặt khác, S(f, h) = x5x6f − x4h = x2x3(x4x7 − x5x6) = x2x3g. Do đó, phần dư của S(f, h) đối với f, g, h bằng 0. Theo tiêu chuẩn Buchberger suy ra rằng {f, g, h} là cơ sở Gro¨bner của I đối với thứ tự từ điển phân bậc ≤glex . 1.2 Phân tích nguyên sơ Trong mục này, ta luôn xét R là vành Noether giao hoán có đơn vị. Định nghĩa 1.2.1. Một iđêan thực sự I của vành R được gọi là (1) iđêan nguyên tố nếu với mọi x, y ∈ R mà xy ∈ I thì x ∈ I hoặc y ∈ I. (2) iđêan cực đại nếu tồn tại iđêan J của R và I ( J thì J = R. Ví dụ 1.2.2. Các iđêan cực đại trong vành các số nguyên Z đều có dạng pZ, trong đó p là số nguyên tố. Định nghĩa 1.2.3. Một iđêan thực sự I của vành R được gọi là iđêan nguyên sơ nếu xy ∈ I và x /∈ I thì yn ∈ I với n nào đó. Nói cách khác, iđêan thực sự I của vành R được gọi là iđêan nguyên sơ khi và chỉ khi mọi ước của 0 trong vành thương R/I đều là lũy linh. Ví dụ 1.2.4. Iđêan mZ trong vành giao hoán Z là nguyên sơ nếu và chỉ nếu m = 0 hoặc m = pk, trong đó p là số nguyên tố và k ∈ N. 14 Mệnh đề 1.2.5. Nếu I là một iđêan nguyên sơ của vành R thì √ I là iđêan nguyên tố. Chứng minh. Nếu xy ∈ √I và x /∈ √I, thì tồn tại n ∈ N sao cho xn /∈ I và (xy)n ∈ I. Suy ra xnyn ∈ I. Do I là iđêan nguyên sơ nên tồn tại m ∈ N sao cho (yn)m = ynm ∈ I. Do đó y ∈ √I. Vậy √I là iđêan nguyên tố. Ví dụ 1.2.6. Ngược lại của mệnh đề trên nói chung là không đúng. Thật vậy, xét vành R = k[x, y, z]/(xy−z2), gọi x, y và z là lớp thương của x, y và z trong R. Iđêan p = (x, z) là iđêan nguyên tố. Ta có x.y = z2 ∈ p2 nhưng x /∈ p2 và y /∈ p. Do đó, p2 không nguyên sơ. Mệnh đề 1.2.7. Nếu √ I là iđêan cực đại thì I là iđêan nguyên sơ. Chứng minh. Giả sử xy ∈ I và y /∈ √I. Do √I là iđêan cực đại nên √ I +Ry = R. Khi đó, tồn tại m ∈ √I và r ∈ R sao cho m+ ry = 1. Ta lại có, m ∈ √I nên mn ∈ I với n ≥ 1 nào đó. Từ đó, ta thấy rằng 1 = 1n = (m+ ry)n = mn + sy, trong đó s ∈ R. Nhân hai vế đẳng thức trên với x ta được x = xmn + sxy ∈ I. Từ đó ta suy ra I la iđêan nguyên sơ. Một iđêan nguyên sơ I của vành R mà √ I = P , ta nói I là iđêan P -nguyên sơ. Định lý 1.2.8. Cho Q là iđêan P -nguyên sơ và a ∈ R. Khi đó, các khẳng định sau luôn đúng: (a) Nếu a ∈ Q thì (Q : a) = R, 15 (b) Nếu a /∈ Q thì (Q : a) là iđêan P -nguyên sơ, (c) Nếu a /∈ P thì (Q : a) = Q. Chứng minh. (a) Với mọi r ∈ R, ta luôn có ar ∈ Q. Do đó, suy ra r ∈ (Q : a). Vì vậy R = (Q : a). (b) Ta có Q ⊆ (Q : a) nên P = √Q ⊆ √(Q : a). Bây giờ ta chứng minh √ (Q : a) ⊆ P . Thật vậy, với mọi x ∈√(Q : a) thì tồn tại n ∈ N∗ sao cho xna ∈ Q. Suy ra (xn)m ∈ Q với m nào đó, và vì vậy x ∈ √Q = P. Do đó, √ (Q : a) = P . Mặt khác, (Q : a) là iđêan nguyên sơ. Thật vậy, nếu xy ∈ (Q : a) và x /∈ (Q : a), thì xa /∈ Q và xya ∈ Q. Vì Q là iđêan nguyên sơ, nên yn ∈ Q với n nào đó. Do đó, y ∈ √Q = P . (c) Ta luôn có Q ⊆ (Q : a). Ngược lại, nếu x ∈ (Q : a) thì xa ∈ Q. Vì a /∈ P = √Q nên x ∈ Q. Vì vậy (Q : a) = Q. Mệnh đề 1.2.9. Nếu Q1, . . . , Qm là P -nguyên sơ thì ⋂m i=1Qi là P - nguyên sơ. Chứng minh. Theo quy nạp, ta chỉ cần chứng minh: giao của hai iđêan P -nguyên sơ là một iđêan P -nguyên sơ. Thật vậy, giả sử I và J là hai iđêan P -nguyên sơ. Ta luôn có √ I ∩ J = √ I ∩ √ J = P. Bây giờ, lấy xy ∈ I ∩J và x /∈ √I ∩ J = P . Khi đó, vì I là iđêan nguyên sơ, nên y ∈ I. Theo tính đối xứng ta cũng chỉ ra được y ∈ J . Do đó, y ∈ I ∩ J . 16 Định nghĩa 1.2.10. Cho I là iđêan thực sự của R. Một phân tích nguyên sơ của iđêan I là một biểu diễn I dưới dạng giao hữu hạn các iđêan nguyên sơ của R, tức là I = m⋂ i=1 Qi, trong đó các Qi là Pi-nguyên sơ. Nếu I có phân tích nguyên sơ thì ta gọi I là iđêan phân tích được. Ngoài ra, nếu tất cả các √ Qi = Pi đều phân biệt và không Qi nào chứa giao của những iđêan còn lại thì phân tích nguyên sơ của I = m⋂ i=1 Qi được gọi là tối tiểu. Ví dụ 1.2.11. Trong vành Z, iđêan mZ có phân tích nguyên sơ là mZ = pα11 Z ∩ . . . ∩ pαnn Z, nếu m = pα11 . . . pαnn với pi là số nguyên tố. Mệnh đề 1.2.12. Cho I = ⋂m i=1Qi là một phân tích nguyên sơ tối tiểu của I trong R và P là iđêan nguyên tố của R. Đặt Pi = √ Qi, với i = 1, . . . , n. Khi đó, các khẳng định sau là tương đương: (i) Tồn tại i ∈ {1, . . . ,m} sao cho P = Pi. (ii) Tồn tại a ∈ R sao cho (I : a) là P -nguyên sơ. (iii) Tồn tại a ∈ R sao cho √(I : a) = P . Hay nói cách khác, Pi là những iđêan nguyên tố xuất hiện trong những iđêan √ I : a và không phụ thuộc vào sự phân tích nguyên sơ của I. 17 Định nghĩa 1.2.13. Iđêan nguyên tố P của R được gọi là iđêan nguyên tố liên kết của I nếu tồn tại 0 6= x ∈ R sao cho P = (0 :R x) = {a ∈ R | ax = 0, với mọi x ∈ I}. Tập các iđêan nguyên tố của I kí hiệu là Ass(I). Tập iđêan nguyên tố liên kết của I không phụ thuộc vào việc chọn phân tích nguyên sơ tối tiểu của I. Định lý 1.2.14 (Định lý duy nhất thứ nhất của phân tích nguyên sơ). Giả sử I là iđêan phân tích được và I = n⋂ i=1 Qi = m⋂ j=1 Q′j, là hai phân tích nguyên sơ tối tiểu của I, trong đó Pi = √ Qi và P ′ j =√ Q′j. Khi đó, n = m và {P1, . . . , Pn} = {P ′1, . . . , P ′m}. Chứng minh. Lấy x ∈ R, áp dụng Định lý 1.2.8 ta có √ (I : x) = √√√√ n⋂ i=1 (Qi : x) = n⋂ i=1 √ (Qi : x) = ⋂ x/∈Qi Pi. Nếu √ (I : x) là nguyên tố thì √ (I : x) ∈ {Pi | x /∈ Qi}. Hay nói cách khác, √ (I : x) = Pj với j nào đó sao cho x /∈ Qj. Theo Mệnh đề 1.2.12, Pj không phụ thuộc vào việc chọn phân tích nguyên sơ của I. Ngược lại, lấy i ∈ {1, . . . , n}, bởi vì phân tích nguyên sơ tối tiểu nên tồn tại xi ∈ ( ⋂ j∈[n]\{i}Qj) \Qi. Ta có thể thấy nếu y ∈ (Qi : xi) thì yxi ∈ Qi. Suy ra yxi ∈ Qi∩( ⋂ i6=j Qj) = I nên y ∈ (I : xi). Vì vậy, (Qi : xi) ⊆ (I : xi). Hơn 18 nữa, ta luôn có (I : xi) ⊆ (Qi : xi). Điều này suy ra (I : xi) = (Qi : xi). Vì vậy √ (I : xi) = √ (Qi : xi) = Pi nên ta có điều phải chứng minh. Định lý 1.2.15 (Định lý duy nhất thứ hai của phân tích nguyên sơ). Giả sử I là iđêan phân tích được và I = n⋂ i=1 Qi = n⋂ i=1 Q′i, là hai phân tích nguyên sơ tối tiểu của I, trong đó Pi = √ Qi = √ Q′i. Khi đó, nếu Pi là iđêan nguyên tố tối tiểu thuộc I với 1 ≤ i ≤ n, thì Qi = Q ′ i. Chứng minh. Với n = 1 định lý luôn đúng. Với n > 1, cố định i, ta luôn tìm được a ∈  ⋂ j∈[n]\{i} Pj  \ Pi. Thật vậy, nếu ngược lại ta có ⋂ j∈[n]\{i} Pj ⊆ Pi. Điều này suy ra Pj ⊆ Pi và mâu thuẩn với giả thiết Pi là iđêan nguyên tố tối tiểu của I. Với mỗi j ∈ [n]\{i}, tồn tại hj ∈ N sao cho ahj ∈ Qj. Gọi t số nguyên sao cho t ≥ max{hj | j ∈ [n] \ {i}}. Khi đó, at /∈ Pi, và I : at = n⋂ j=1 Qj : a t = n⋂ j=1 ( Qj : a t ) = Qi. Một cách tương tự, ta cũng có (I : at) = Q′i với mỗi số nguyên t đủ lớn. Vậy Qi = Q ′ i. Định nghĩa 1.2.16. Một iđêan thực sự I của vành R được gọi là bất khả quy nếu nó không phải là giao của hai iđêan chứa nó thật sự. Nói 19 cách khác, iđêan thực sự I của vành R là bất khả quy nếu với mọi iđêan I1 và I2 sao cho I = I1 ∩ I2 thì I = I1 hoặc I = I2 . Ví dụ 1.2.17. Cho vành Z, I = pZ là iđêan bất khả quy. Thật vậy, giả sử I = I1 ∩ I2 = aZ ∩ bZ, với a, b ∈ Z. Không mất tính tổng quát ta giả sử a, b > 0 và a 6= b. Khi đó, pZ ⊆ aZ và pZ ⊆ bZ suy ra a | p và b | p. Vì vậy, (a, b) = (1, p) hoặc (a, b) = (p, 1). Suy ra I1 = pZ hoặc I2 = pZ. Vậy pZ là iđêan bất khả quy của Z. Mệnh đề 1.2.18. Mọi iđêan bất khả quy là iđêan nguyên sơ. Chứng minh. Giả sử a, b ∈ R sao cho ab ∈ I và b /∈ I. Ta cần chứng minh a ∈ √I. Thật vậy, ta có (I : a) ⊆ (I : a2) ⊆ . . . ⊆ (I : ai) ⊆ . . . là dãy tăng các iđêan của R. Do R là vành Noether nên tồn tại n ∈ N sao cho (I : an) = (I : an+i) với mọi i ∈ N. Ta chứng minh I = (I + Ran) ∩ (I + Rb). Thật vậy, ta luôn có I ⊆ (I +Ran)∩ (I +Rb). Ngược lại, lấy bất kì r ∈ (I +Ran)∩ (I +Rb), suy ra tồn tại g, h ∈ I và c, d ∈ R sao cho r = g + can = h + db. Do đó ra = ga + can+1 = ha + dba. Suy ra can+1 = ha + dba − ga ∈ I vì ab, g, h ∈ I. Điều này suy ra c ∈ (I : an+1) = (I : an). Suy ra r = g + can ∈ I. Vì vậy (I +Ran) ∩ (I +Rb) ⊆ I. Do I bất khả quy và I ( (I + Rb) nên I = I + Ran. Suy ra an ∈ I. Do đó, I là iđêan nguyên sơ của R. Theo mệnh đề trên, việc tồn tại phân tích nguyên sơ của một iđêan 20 thực sự trong vành Noether có quy về việc tồn tại một phân tích bất khả quy của iđêan đó hay không? Định lý 1.2.19. Mọi iđêan thực sự I trong vành Noether R đều có phân tích bất khả quy. Chứng minh. Đặt Ω là tập các iđêan thực sự sao cho nó không có phân tích thành giao hữu hạn của các iđêan bất khả quy của R. Ta chứng minh Ω = ∅. Giả sử phản chứng Ω 6= ∅. Do R là vành Noether nên tồn tại I là phần tử cực đại trong Ω theo quan hệ bao hàm. Khi đó, nếu I là iđêan bất khả quy thì I = I ∩ I. Điều này dẫn đến vô lí vì I ∈ Ω. Do vậy, I khả quy, tức là I = I1 ∩ I2, trong đó I1, I2 ⊆ R và I ( I1, I ( I2. Vì I cực đại trong Ω nên I1, I2 /∈ Ω. Suy ra I1, I2 được biểu diễn dưới dạng giao hữu hạn các iđêan bất khả quy trong R. Cụ thể: I1 = Q1 ∩ . . . ∩Qr I2 = Q ′ 1 ∩ . . . ∩Q′s, trong đó các Qi và Q ′ i là các iđêan bất khả quy. Do đó I = Q1 ∩ . . . ∩Qr ∩Q′1 ∩ . . . ∩Q′r. Điều này mâu thuẫn với điều kiện I ∈ Ω. Vì vậy, ta kết luận rằng Ω = ∅. Hay nói cách khác, mọi iđêan thực sự trong vành Noether đều có phân tích bất khả quy. Để tìm phân tích nguyên sơ của một iđêan sinh bởi đơn thức, ta có 21 thể vận dụng liên tiếp bổ đề sau: Bổ đề 1.2.20. Giả sử m,n là hai đơn thức không chứa biến chung và m1, . . . ,mr là các đơn thức. Khi đó (m1, . . . ,mr,mn) = (m1, . . . ,mr,m) ∩ (m1, . . . ,mr, n) . Ví dụ 1.2.21. Áp dụng bổ đề trên, ta có thể tìm được phân tích nguyên sơ của iđêan I = (xy2, x2y, y4) như sau: I = (x, x2y, y4) ∩ (y2, x2y, y4) = (x, y4) ∩ (y2, x2y) = (x, y4) ∩ (y2, x2) ∩ (y2, y) = (x, y4) ∩ (x2, y2) ∩ (y) = Q1 ∩Q2 ∩Q3, trong đó Q1 = (x, y 4), Q2 = (x 2, y2) và Q3 = (y) là các iđêan nguyên sơ của I. Do đó, các iđêan nguyên tố liên kết của I là P1 = (x, y) = √ Q1 = √ Q2 và P2 = (y) = √ Q3. Vì vậy Ass(I) = {(x, y), (y)}. Chương 2 Cơ sở Gro¨bner của iđêan cạnh nhị thức Mục đích của chương này là nghiên cứu bài toán khi nào các phần tử sinh bậc hai của iđêan cạnh nhị thức lập thành một cơ sở Gro¨bner. Cơ sở Gro¨bner rút gọn của iđêan cạnh nhị thức cũng được tìm hiểu trong chương này. Nội dung của chương này được tham khảo từ các tài liệu [9] và [10]. 2.1 Iđêan cạnh nhị thức Cho G là đồ thị với tập đỉnh V := V (G) và tập cạnh E(G). Một cạnh e ∈ E(G) nối hai đỉnh x và y được kí hiệu là {x, y}. Trong trường hợp này, ta nói x và y kề nhau. Trong toàn bộ luận văn này đồ thị được xét là đồ thị đơn (tức là, đồ thị vô hướng, không có khuyên, và giữa hai đỉnh có nhiều nhất một cạnh). Ví dụ 2.1.1. Đồ thị G dưới đây là đơn với tập đỉnh V (G) = {1, . . . , 5} và tập cạnh E(G) = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 5}}. 22 23 3 1 2 4 5 Định nghĩa 2.1.2. Đồ thị đầy đủ kí hiệu Kn là đồ thị đơn mà mỗi đỉnh của đồ thị được nối với nhau bằng đúng một cạnh. Ví dụ 2.1.3. Các đồ thị dưới đây lần lượt là các đồ thị đầy đủ K3, K4 và K5. 2 1 3 2 1 3 4 2 1 3 45 Cho đồ thị đơn G với tập đỉnh V (G) và tập cạnh E(G), đường đi độ dài r từ đỉnh i đến đỉnh j là dãy: i = i0, i1, . . . , ir = j trong đó {is, is+1} ∈ E(G), với s = 0, 1, . . . , r − 1. Đỉnh i được gọi là đỉnh đầu của đường đi, đỉnh j là đỉnh cuối của đường đi. Đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là chu trình. Định nghĩa 2.1.4. Một đồ thị gọi là liên thông nếu luôn tìm được một đường đi giữa hai đỉnh bất kỳ của nó. 24 Ví dụ 2.1.5. Đồ thị trong các Ví dụ 2.1.1 và 2.1.3 là các đồ thị liên thông. Đồ thị dưới đây không là đồ thị liên thông vì giữa hai đỉnh 1 và 4 không tồn tại một đường đi nào. 2 1 3 45 Định nghĩa 2.1.6. Đồ thị H = (V ′, E ′) được gọi là đồ thị con của G = (V,E) nếu V ′ ⊆ V và E ′ ⊆ E. Trong trường hợp đồ thị đơn G không liên thông, nó sẽ được phân tích thành các đồ thị con liên thông độc lập nhau. Mỗi đồ thị con như vậy được gọi là thành phần liên thông của G. Ví dụ 2.1.7. Đồ thị không liên thông trong Ví dụ 2.1.5 gồm 2 thành phần liên thông. Thành phần liên thông thứ nhất là một tam giác với ba đỉnh 1,2,3. Thành phần liên thông thứ hai là cạnh {4, 5}. Cho S = K[x1, . . . , xn, y1, . . . , yn] là một vành đa thức trên trường K với các biến x1, . . . , xn, y1, . . . , yn. Đặt fij := xiyj−xjyi với 1 ≤ i < j ≤ n. Khi đó, nhị thức fij là định thức con của ma trậnx1 x2 . . . xn y1 y2 . . . yn  . 25 Định nghĩa 2.1.8. Cho G là đồ thị đơn với tập đỉnh [n] := {1, . . . , n}. Iđêan cạnh nhị thức JG của S là iđêan sinh bởi các nhị thức fij sao cho i < j và {i, j} là cạnh của đồ thị G. Ví dụ 2.1.9. Với đồ thị G trong Ví dụ 2.1.1, iđêan cạnh nhị thức của đồ thị G là iđêan sinh bởi các nhị thức x1y2−x2y1, x1y3−x3y1, x2y3−x3y2, x2y4−x4y2, x3y4−x4y3, và x4y5−x5y4 trong vànhK[x1, . . . , x5, y1, . . . , y5]. Định nghĩa 2.1.10. Cho đồ thị đơn G = (V,E) và T ⊆ V . Khi đó, đồ thị con cảm sinh của G trên T kí hiệu GT là đồ thị có tập đỉnh T và tập cạnh {{i, j} ∈ E(G) | i, j ∈ T}. Ví dụ 2.1.11. Cho đồ thị G với tập đỉnh {1, 2, 3, 4} và tập cạnh {{1, 2}, {2, 3}, {2, 4}, {3, 4}}; và đồ thị cảm sinh GT của đồ thị G trên tập đỉnh T = {1, 2, 3} được cho bởi các hình vẽ sau: 2 4 3 1 2 3 1 G GT 26 2.2 Cơ sở Gro¨bner và đồ thị đóng Trong mục này, chúng tôi sẽ trình bày cơ sở Gro¨bner của iđêan cạnh nhị thức trong vành đa thức S = K[x1, . . . , xn, y1, . . . , yn] đối với thứ tự từ điển ≤lex sao cho x1 > . . . > xn > y1 > . . . > yn. Định lý 2.2.1. Cho đồ thị G với tập đỉnh [n] và tập cạnh E. Khi đó, các phát biểu sau là tương đương: (a) Hệ sinh fij của JG là một cơ sở của Gro¨bner. (b) Với mỗi i < j < k, (i) Nếu {i, k} và {j, k} là các cạnh của G, thì {i, j} là cạnh của G, (ii) Nếu {i, j} và {i, k} là các cạnh của G, thì {j, k} là cạnh của G. Chứng minh. (a) ⇒ (b) Ta sẽ chứng minh khẳng định (ii), còn khẳng định (i) được chứng minh tương tự. Với i < j < k, giả sử ta có các cạnh {i, j} và {i, k} ∈ E nhưng {j, k} /∈ E. Khi đó, S(fik, fij) = xiyj xi (xiyk − xkyi)− xiyk xi (xiyj − xjyi) = yj (xiyk − xkyi)− yk (xiyj − xjyi) = yi (xjyk − xkyj) = yifjk. Theo giả thiết, ta suy ra yifjk = S(fik, fij) ∈ JG. Chú ý rằng in(yifjk) = yixjyk. Theo Định lý chia đa thức (Định lý 1.1.9) dẫn đến mâu thuẫn. 27 Thật vậy, vì {j, k} /∈ E, do đó không có đơn thức dẫn đầu của hệ sinh nhị thức của JG là ước của in(yjfjk). (b) ⇒ (a): Đặt G là tập gồm các phần tử fij với i < j và {i, j} ∈ E. Ta chứng minh khẳng định này bằng tiêu chuẩn Buchberger (Định lý 1.1.17) rằng S (fij, fkl) G−→ 0 với mọi i < j, và k < l. Thật vậy, ta chia chứng minh của khẳng định này thành các trường hợp sau: • Trường hợp i 6= k và j 6= l: Lúc đó, in(fij) = xiyj và in(fkl) = xkyl nguyên tố cùng nhau. Theo Mệnh đề 1.1.18, S(fij, fkl) G−→ 0. • Trường hợp i = k và l < j: Theo giả thiết, ta có {j, l} ∈ E(G) nên flj ∈ JG. Do vậy S(fij, fil) = yiflj là biểu diễn chuẩn tắc của S(fij, fil) đối với G. Vì vậy, S(fij, fil) G−→ 0. • Trường hợp j = l và i < k: Tương tự, S(fij, fkj) = xjfik G−→ 0. Định nghĩa 2.2.2. Đồ thị G với tập đỉnh [n] thỏa mãn điều kiện (ii) của Định lí 2.2.1 được gọi là đồ thị đóng đối với thứ tự ≤. Đặc trưng cơ sở Gro¨bner gồm các phần tử bậc hai ở Định lý 2.2.1 không chỉ đúng với thứ tự từ điển ≤lex mà còn đúng với thứ tự bất kì. Định nghĩa 2.2.3. Cho JG là iđêan cạnh nhị thức của G và một thứ tự từ ≺ bất kì trên vành đa thức S = K[x1, . . . , xn, y1, . . . , yn]. Ta định nghĩa một đồ thị có hướng G≺ với tập đỉnh V (G≺) = V (G) và tập cạnh E(G≺) = {(i, j) : xiyj ∈ in≺(JG)}. 28 Mệnh đề 2.2.4. G≺ là đồ thị có hướng không chứa chu trình. Chứng minh. Ta chứng minh mọi chu trình trong G không là chu trình có hướng trong G≺. Đặt {i1, i2, . . . , ir} ⊆ V (G) là tập đỉnh của một chu trình của G và giả sử (ij, ij+1) ∈ E(G≺) với j = 1, . . . , r − 1. Ta sẽ chứng minh (ir, i1) /∈ E(G≺). Thật vậy, với mỗi j = 1, . . . , r − 1, theo giả thiết ta có xijyij+1 ∈ in≺(JG). Do đó, xijyij+1  xij+1yij . Vì ≺ là thứ tự từ nên yi3(xi1yi2)  yi3(xi2yi1) và yi1(xi2yi3)  yi1(xi3yi2). Từ đó suy ra yi3(xi1yi2)  yi1(xi3yi2) và vì vậy xi1yi3  xi3yi1. Với lí luận tương tự, ta có yi4(xi1yi3)  yi4(xi3yi1) và xi1yi4  xi4yi1. Tiếp tục quá trình này với hữu hạn bước, ta nhận được xi1yir  xiryi1. Do đó xiryi1 /∈ in≺(JG). Vì vậy (ir, i1) /∈ E(G≺). Định lý 2.2.5. Các điều kiện sau là tương đương: (1) G là đồ thị đóng trên tập đỉnh [n]; (2) JG có cơ sở Gro¨bner gồm các phần tử bậc hai với thứ tự từ ≺ nào đó trên S. Chứng minh. (1) =⇒ (2): Theo Định lí 2.2.1, ta biết rằng với thứ tự từ điển, cơ sở Gro¨bner của JG bao gồm phần tử fij với {i, j} ∈ E(G). (2) =⇒ (1): Theo Mệnh đề 2.2.4, G≺ là đồ thị có hướng không chứa chu trình. Do vậy tồn tại ω : V (G≺) −→ [n] 29 sao cho với mọi cặp (i, j) ∈ E(G≺) thì ω(i) < ω(j). Điều đó có nghĩa ω tương thích với định hướng của G≺ ([11, Mệnh đề 1.4.3]). Bây giờ chúng ta chứng minh G là đồ thị đóng đối với ω. Lấy i1, i2, i3 ∈ V (G≺) sao cho ω(i1) = i, ω(i2) = j, ω(i3) = k và đặt {i1, i2}, {i1, i3} ∈ E(G). Điều này suy ra, {i, j}, {i, k} là các cạnh của G đối với ω. Bởi Định lý 2.2.1 (2), ta có hai trường hợp sau (a) Trường hợp i < j và i < k: Vì ω tương thích với đồ thị có hướng G≺, nên ta có bất đẳng thức sau xi1yi2  xi2yi1 và xi1yi3  xi3yi1. (2.1) Theo giả thiết, S-đa thức S(fi1i2, fi1i3) = yi1(xi2yi3 − xi3yi2) tiến về 0. Do đó, tồn tại đơn thức xisyit − xityis ∈ JG mà đơn thức khởi đầu của nó là ước của đơn thức khởi đầu của yi1fi2i3. Giả sử in(fi1i2) = xi2yi1. Điều này mâu thuẫn với bất đẳng thức đầu tiên của (2.1). Lí luận tương tự và bất đẳng thức thứ hai của (2.1), in(fi1i3) không là ước của in(yi1fi2i3). Do đó fi2i3 ∈ JG và {j, k} là cạnh của G đối với ω. (b) Trường hợp i > j và i > k: được chứng minh tương tự như trường hợp (a). Từ đó, ta có thể kết luận rằng G là đồ thị đóng. 30 2.3 Cơ sở Gro¨bner rút gọn Định nghĩa 2.3.1. Cho G là đồ thị đơn trên tập đỉnh [n] và lấy i và j là hai đỉnh của G sao cho i < j. Một đường đi i = i0, i1, . . . , ir = j từ i đến j được gọi là chấp nhận được nếu (i) ik 6= il, với k 6= l; (ii) Với mỗi k = 1, . . . , r − 1, ik j; (iii) Với bất kì tập con thực sự {j1, . . . , js} của {i1, . . . , ir−1}, dãy i, j1, . . . , js, j không là một đường đi. Cho một đường đi chấp nhận được pi : i = i0, i1, . . . , ir = j từ i tới j, trong đó i < j. Một đơn thức liên kết với đường đi này kí hiệu là: upi := (∏ ik>j xik )(∏ il<i yil ) . Định lý 2.3.2. Cho G là đồ thị đơn trên tập đỉnh [n] và < là thứ tự từ sao cho x1 > . . . > xn > y1 > . . . > yn. Khi đó, tập các nhị thức G = ⋃ i<j {upifij | pi là đường đi chấp nhận được từ i đến j} là cơ cở Gro¨bner rút gọn của JG. Chứng minh. Ta sẽ chứng minh định lí theo các bước sau: Bước 1: G ⊆ JG. 31 Thật vậy, chứng minh bằng quy nạp theo r rằng với mỗi đường đi chấp nhận được pi từ i đến j, với i < j, thì nhị thức upifij ∈ JG. Gọi pi : i = i0, i1, . . . , ir−1, ir = j là đường đi chấp nhận được trongG. Rõ ràng với r = 1 ta luôn có khẳng định đúng. Xét r > 1. Đặt A = {ik : ik < i} và B = {i` : il > j}. Khi đó, A 6= ∅ hoặc B 6= ∅. Nếu A 6= ∅ thì ta đặt ik0 := maxA. Nếu B 6= ∅ thì đặt i`0 := minB. Giả sử A 6= ∅. Điều này suy ra mỗi đường đi pi1 : ik0, ik0−1, . . . , i1, i0 = i pi2 : ik0, ik0+1, . . . , ir−1, ir = j trong G là chấp nhận được. Theo giả thuyết quy nạp, upi1fik0 ,i, và upi2fik0 ,j thuộc vào JG. Mặt khác, ta có S(upi1fik0 ,i, upi2fik0 ,j) = upifij. Do vậy upifij ∈ JG. Khi B 6= ∅, với lí luận tương tự như trường hợp A 6= ∅. Bước 2: G là cơ sở Gro¨bner của JG. Theo tiêu chuẩn Buchberger, ta cần ra rằng S(upifij, uσfk`) tiến đến 0, trong đó i < j và k < `. Ta xét các trường hợp sau: • Trường hợp i = k, j = `: Ta luôn có S(upifij, uσfk`) = 0. • Trường hợp {i, j} ∩ {k, `} = ∅ hoặc i = ` hoặc k = j: Khi đó, các đơn thức khởi đầu in(fij), in(fk`) nguyên tố cùng nhau. Theo Mệnh đề 1.1.18, ta suy ra S(upifij, uσfk`) tiến về 0. • Trường hợp i = k, j 6= ` hoặc i 6= k, j = `: hai trường hợp này chứng minh tương tự nhau, nên ta xét trường hợp đầu tiên i = k, j 6= `. Ta 32 chứng minh S(upifij, uσfk`) tiến đến 0. Giả sử rằng j < ` và ta tìm một biểu diễn chuẩn tắc của S(upifij, uσfk`) mà phần dư bằng 0. Lấy pi : i = i0, i1,. . ., ir = j and σ : i = i ′ 0, i ′ 1, . . ., i ′ s = `. Khi đó tồn tại các chỉ số a và b sao cho ia = i ′ b và {ia+1, . . . , ir} ∩ {i′b+1, . . . , i′s} = ∅. Xét đường đi sau τ : j = ir, ir−1, . . . , ia+1, ia = i′b, i ′ b+1, . . . , i ′ s−1, i ′ s = ` từ j đến `. Để đơn giản kí hiệu, ta viết lại đường đi như sau: τ : j = j0, j1, . . . , jt = ` Đặt jt(1) = min{jc : fc > j, c = 1, . . . , t} và jt(2) = min{jc : jc > j, c = t(1) + 1, . . . , t}, trong đó 0 = t(0) < t(1) < · · · < t(q − 1) < t(q) = t. Từ đó suy ra j = jt(0) < jt(1) < · · · < jt(q)−1 < jt(q) = ` và với mỗi 1 ≤ c ≤ t, đường đi τc : jt(c−1), jt(c−1)+1, . . . , jt(c)−1, jt(c) 33 là chấp nhận được. Tiếp theo của chứng minh này là chỉ ra rằng S (upifij, uσfi`) = q∑ c=1 vτcuτcfjt(c−1)jt(c) là biểu diễn chuẩn tắc của S (upifij, uσfj`) với phần dư bằng 0, trong đó mỗi vτc là đơn thức được định nghĩa như sau: Cho w = yi BCNN(upi, uσ). Do đó suy ra S (upifij, uσfj`) = −wfj`. Khi đó, (i) Nếu c = 1 thì vτ1 = x`w uτ1xjt(1) , (ii) Nếu 1 < c < q thì vτc = xjx`w uτcxjt(c−1)xjt(c) , (iii) Nếu c = q thì vτq = xjw uτqxjt(q−1) . Bây giờ ta chứng minh wfj` = wx` xjt(1) fjjt(1) + q−1∑ c=2 wxjx` xjt(c−1)xjt(c) fjt(c−1)jt(c) + wxj xjt(q−1) fjt(q−1)` là biểu diễn chuẩn tắc của wfj` với phần dư bằng 0. Mặt khác, ta chứng minh rằng: (∗) w (xjy` − x`yj) = wx` xjt(1) ( xjyjt(1) − xjt(1)yj ) + q−1∑ c=2 wxjx` xjt(c−1)xjt(c) ( xjt(c−1)yjt(c) − xjt(c)yjt(c−1) ) + wxj xjt(q−1) ( xjt(q−1)y` − x`yjt(q−1) ) 34 là biểu diễn chuẩn tắc của w(xjy` − x`yj) với phần bằng 0. Vì wxjy` = wxj xjt(q−1) xjt(q−1)y` > wxjx` xjt(q−2)xjt(q−1) xjt(q−2)xjt(q−1) > · · · > wxjx` xjt(1)xjt(2) xjt(1)yjt(2) > wx` xjt(1) xjyjt(1), Điều này suy ra rằng, nếu đẳng thức (∗) đúng, thì nó là biểu diễn chuẩn tắc của w(xjy` − x`yj) với phần dư là 0. Do đó, ta có thể viết lại như sau: w (xjy` − x`yj) = w ( xjx` yjt(1) xjt(1) − x`yj ) + wxjx` q−1∑ c=2 ( yjt(c) xjt(c) − yjt(c−1) xjt(c−1) ) +w ( xjy` − xjx` yjt(q−1) xjt(q−1) ) . Bước 3: Ta chứng minh cơ sở Gro¨bner của G là rút gọn. Lấy upifij, uσfkl ∈ G mà upifij 6= uσfkl trong đó i < j và k < l. Lấy pi : i = i0, i1, . . . , ir = j và σ : k = k0, k1, . . . , ks = l. Giả sử upixiyj chia hết cho uσxkyl hoặc uσxlyk. Khi đó, {i0, i1, . . . , ir} là tập con thực sự của {k0, k1, . . . , ks}. Với i = k và j = l, khi đó {i1, . . . , ir−1} là tập con của {k0, k1, . . . , ks} và k, i1, . . . , ir−1, l là một đường đi chấp nhận được. Điều này mâu thuẫn với σ là đường chấp nhận được. Với i = k và j 6= l thì uσ chia hết cho yj do đó j < k mâu thuẫn với i < j. Với {i, j} ∩ {k, l} = ∅, uσ chia hết cho xiyj. Do đó i > l và j < k, mâu thuẫn với i < j. 35 Hệ quả 2.3.3. JG là iđêan căn. Chứng minh. Theo Định lí 2.3.2, chúng ta thấy rằng đối với một thứ tự đơn thức phù hợp thì in(JG) là iđêan đơn thức không chứa mũ. Điều này suy ra in(JG) là iđêan căn. Giả sử f k ∈ JG, với số tự nhiên k nào đó. Khi đó, in(fk) = in(f)k ∈ in(JG) và do đó in(f) ∈ in(JG). Theo định nghĩa của iđêan khởi đầu, tồn tại g ∈ JG với in(g) = in(f). Khi đó, chọn a ∈ K sao cho in(f − ag) < in(f). Vì (f − ag)k = fk