ĐẠ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 đây là công trình nghiên cứu khoa
học độc lập của riêng tôi dưới sự định hướng của
PGS.TS Phan Văn Thiện. Các số liệu sử dụng phân
tích trong luận án có nguồn gốc rõ ràng, đã công bố
theo đúng quy định. Các kết quả nghiên cứu trong
luận án do tôi tự tìm hiểu, phân tích một cách trung
thực, khách quan. Các kết quả này chưa từng được
công bố trong bất kỳ nghiên cứu nào khác.
Tôn Nữ Quỳnh Mai

ii


LỜI CẢM ƠN
Luận văn này được hoàn thành dưới sự hướng dẫn của 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 và sự kính trọng đối với
Thầy. Thầy đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện
khóa luận tốt nghiệp, đồng thời giúp tôi lĩnh hội được những kiến thức chuyên
môn và rèn luyện cho tôi 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 cô Khoa Toán, các Thầy ở
Đại học Huế và Viện Toán học đã dạy dỗ và truyền đạt kiến thức cho tôi trong

suốt quá 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 Toán trường ĐHSP Huế đã tạo điều kiện cho tôi trong suốt
khóa học.
Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, các anh chị Cao học Toán khóa
XXIV trường ĐHSP Huế chuyên ngành Đại số và Lý thuyết số vì sự động viên,
giúp đỡ trong quá trình học tập vừa qua.
Ngày 15 tháng 09 năm 2017.
Học viên thực hiện

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


1

Lời nói đầu

3

1 Thuật toán tìm cơ sở Groebner của iđêan các đa thức triệt tiêu
trong vành Zm [x1 , . . . , xn ]

5

1.1

Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.1

Vành đa thức Zm [x1 , . . . , xn ]. Định lý Hilbert về cơ sở. .

5

1.1.2

Thứ tự từ trong vành Zm [x1 , . . . , xn ] . . . . . . . . . . .

7

1.1.3


Iđêan đơn thức. Iđêan dẫn đầu. . . . . . . . . . . . . . .

11

1.2

Cơ sở Groebner của iđêan các đa thức triệt tiêu trong vành
Zm [x1 , . . . , xn ] . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.2.1

Iđêan các đa thức triệt tiêu. . . . . . . . . . . . . . . . .

16

1.2.2

Cơ sở Groebner mạnh tối tiểu của I0 . . . . . . . . . . .

17

1.2.3

Thuật toán tìm cơ sở Groebner mạnh tối tiểu trong vành
Zm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21


2 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 ] bằng ngôn ngữ C.

24

2.1

Tổ chức cấu trúc dữ liệu . . . . . . . . . . . . . . . . . . . . . .

24

2.1.1

Đơn thức trong Zm [x1 , . . . , xn ] . . . . . . . . . . . . . . .

24

2.1.2

Đa thức trong Zm [x1 , . . . , xn ]

. . . . . . . . . . . . . . .

25

2.1.3

Hàm biểu diễn đa thức triệt tiêu p. . . . . . . . . . . . .


30

1


2.2

Xây dựng chương trình . . . . . . . . . . . . . . . . . . . . . . .

31

2.3

Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

Kết luận

44

2


LỜI NÓI ĐẦU
Năm 1970, Buchberger đã công bố nền tảng lý thuyết về cơ sở Groebner của
iđêan trong vành đa thức nhiều biến trên một trường. Tám năm sau, năm 1978,
W.Trinks đưa ra một cách tổng quát lý thuyết vành đa thức trên một vành
noetherian, giao hoán. Ông ấy đã trình bày khái niệm của cơ sở Groebner trong
vành đa thức nhiều biến từ trường hợp trên một trường sang trường hợp trên

một vành. Có thể thấy tính chất cơ bản của cơ sở Groebner trong các vành đa
thức nhiều biến trên một vành C rất được chú ý, song nó vẫn chưa được nghiên
cứu nhiều. Tuy nhiên, do ứng dụng tiềm năng và các tính chất thú vị nên nó
đã thu hút sự quan tâm của nhiều nhà toán học trên thế giới, chẳng hạn như
Greuel G., Seelish F., Wienand O., Adam W., ... (xem [5], [6]).
Khi vành Zm chỉ có hữu hạn phần tử thì tồn tại các đa thức khác không trong
Zm [x1 , . . . , xn ] triệt tiêu với mọi (a1 , a2 , . . . , an ) ∈ Zn , ta gọi là các đa thức triệt
tiêu. Tất cả các đa thức triệt tiêu tạo thành một iđêan I0 . Trên phương diện
toán học và tin học, I0 ⊂ Zm [x1 , . . . , xn ] có một số tính chất thú vị (xem [5]).
Luận văn sẽ đưa ra một cơ sở Groebner mạnh tối tiểu Gm của I0 . Việc xây
dựng chi tiết cơ sở Groebner mạnh tối tiểu của iđêan các đa thức triệt tiêu trong
vành Zm [x1 , . . . , xn ] với m ≥ 2 đã được chứng minh một cách hoàn toàn tổng
quát ([5]). Điều đáng chú ý là việc xây dựng cơ sở Groebner không phụ thuộc
vào thứ tự đơn thức và tập các từ dẫn đầu của cơ sở Groebner là duy nhất.
Luận văn cũng trình bày lại một thuật toán đệ quy trong [5] để xây dựng một
cơ sở Groebner mạnh tối tiểu của iđêan các đa thức triệt tiêu trong Zm [x1 , . . . , xn ].
Phần cuối của luận văn là xây dựng một chương trình tính cơ sở Groebner mạnh
tối tiểu của iđêan các đa thức triệt tiêu trong vành Zm [x1 , . . . , xn ] bằng ngôn
ngữ C dựa trên thuật toán trong [5].
Luận văn bao gồm hai chương:
Chương 1 : Thuật toán tìm cơ sở Groebner của iđêan các đa thức triệt tiêu
trong vành Zm [x1 , . . . , xn ]
Đầu tiên chương này trình bày một số khái niệm, tính chất cơ bản nhất của
vành đa thức Zm [x1 , . . . , xn ].
Tiếp theo chương này trình bày những khái niệm, nội dung những định lý
cần thiết, liên quan đến việc xây dựng định nghĩa cơ sở Groebner của iđêan các
đa thức triệt tiêu và thuật toán để tìm nó trong vành Zm [x1 , . . . , xn ], chương
3



này là tiền đề nghiên cứu cho chương sau.
Chương 2 : 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 ] bằng ngôn ngữ C
Đây là phần chính của luận văn. Nội dung trình bày cách biểu diễn dữ liệu,
một vài ý kiến trong việc sử dụng thuật toán tính cơ sở Groebner mạnh tối tiểu
trong [5]. Cuối chương là chương trình tính cơ sở Groebner, các ví dụ chạy mẫu
và nhận xét.

4


Chương 1
Thuật toán tìm cơ sở Groebner của
iđêan các đa thức triệt tiêu trong
vành Zm[x1, . . . , xn]
Trong suốt luận văn này ta sẽ xét vành đa thức Zm [x1 , . . . , xn ] với m ≥ 2.
Tài liệu tham khảo chính của chương là [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 về cơ sở.
Xét vành đa thức Zm [x1 , . . . , xn ] với các biến x1 , x2 , . . . , xn (n ≥ 1). Ta gọi
đơn thức là biểu thức có dạng:
xα1 1 xα2 2 · · · xαnn
trong đó (α1 , . . . , αn ) ∈ Nn được gọi là bộ số mũ của đơn thức. Nếu α1 = · · · =
αn = 0 thì đơn thức là 1. Phép nhân trên tập các đơn thức được định nghĩa như
sau:
(xα1 1 · · · xαnn )(xβ1 1 · · · xβnn ) = xα1 1 +β1 · · · xαnn +βn
Tổng các số mũ của các biến trong đơn thức được gọi là bậc của đơn thức.
Từ là biểu thức có dạng axα1 1 · · · xαnn , trong đó a ∈ Zm được gọi là hệ số của
từ. Thông thường phần tử của vành cơ sở Zm được gọi là phần tử vô hướng. Hai

từ khác không bxα1 1 · · · xαnn và bxα1 1 · · · xαnn được gọi là đồng dạng với nhau. Như
vậy có thể xem đơn thức là từ với hệ số là 1, và phần tử vô hướng a là từ a · 1.
Kí hiệu x = (x1 , . . . , xn ), a = (a1 , . . . , an ) ∈ Nn và xa = xa11 · · · xann . Đa thức
n biến x1 , . . . , xn trên vành Zm là một tổng hình thức của các từ:
aα xα

f (x) =
α∈Nn

5


trong đó aα ∈ Zm và chỉ có một số hữu hạn hệ số aα = 0. Từ aα xα với aα = 0
được gọi là từ của đa thức f (x) và xα là đơn thức của f (x).
aα xα và g(x) =

Hai đa thức f (x) =
α∈Nn
n

bα xα được xem là bằng nhau,
α∈Nn

nếu aα = bα với mọi α ∈ N .
Phép cộng đa thức định nghĩa như sau:
aα xα ) + (

(
α∈Nn


(aα + bα )xα .

bα x α ) =
α∈Nn

α∈Nn

Phép nhân đa thức được định nghĩa như sau:
(

aα xα )(

α∈Nn

bα xα ) =

α∈Nn

cα x α ,
α∈Nn

trong đó
cα =

aβ bγ .
β,γ∈Nn ,β+γ=α

aα xα là:

Định nghĩa 1.1.1. [1, tr.32] Bậc tổng thể của đa thức f (x) =

α∈Nn

degf (x) = max{α1 + · · · + αn |aα = 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.
Định nghĩa 1.1.2. [6, tr.6] Cho I là iđêan của vành Zm [x1 , . . . , xn ]. Nếu tồn
tại các đa thức f1 , f2 , . . . , fs ∈ Zm [x1 , . . . , xn ] sao cho I = f1 , f2 , . . . , fs thì I
được gọi là 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 ] , các mệnh đề sau tương đương:
(i) Với mọi iđêan I ⊆ Zm [x1 , . . . , xn ] tồn tại f1 , f2 , . . . , fs ∈ I sao cho
I = f1 , f2 , . . . , fs .
(ii) Mọi dãy tăng các iđêan của Zm [x1 , . . . , xn ] như sau:
I1 ⊆ I2 ⊆ · · · ⊆ In ⊆ · · ·
tồn tại N sao cho IN = IN +1 = IN +2 = · · · .
Tức là, vành Zm [x1 , . . . , xn ] là Noetherian nếu và chỉ nếu mọi iđêan của
Zm [x1 , . . . , xn ] đều có tập sinh hữu hạn
6


Chứng minh. (i) =⇒ (ii) Đặt:
I1 ⊆ I2 ⊆ · · · ⊆ In ⊆ . . .
∞

In .

là dãy tăng các iđêan của Zm [x1 , . . . , xn ]. Xét tập I =
n+1

Khi đó, I cũng là một iđêan của Zm [x1 , . . . , xn ]. Theo (i) ta có I = f1 , f2 , . . . , fs ,

với f1 , f2 , . . . , fs ∈ Zm [x1 , . . . , xn ]. Với mỗi i = 1, . . . , s, vì fi ∈ I nên tồn tại Ni
sao cho fi ∈ INi . Đặt N = max1≤i≤s Ni , ta có fi ∈ IN với mọi i = 1, . . . , s, do
đó I ⊆ IN . Suy ra I = IN .
(ii) =⇒ (i) Giả sử có iđêan I của Zm [x1 , . . . , xn ] mà không có tập sinh hữu
hạn gồm các phần tử của Zm [x1 , . . . , xn ]. Giả sử f1 ∈ I, khi đó tồn tại f2 ∈ I
mà f2 ∈
/ f1 . Vì vậy f1

f1 , f2 . Tiếp tục quá trình này ta thu được dãy

tăng ngặt các iđêan của Zm [x1 , . . . , xn ], mâu thuẫn với (ii).

1.1.2 Thứ tự từ trong vành Zm [x1 , . . . , xn ]
Định nghĩa 1.1.4. [1, tr.76] Thứ tự từ là một thứ tự toàn phần ≤ trên tập M
tất cả các đơn thức của Zm [x1 , . . . , xn ] thỏa mãn các tính chất sau:
(a) Với mọi m ∈ M, 1 ≤ m.
(b) Nếu m1 , m2 , m ∈ M mà m1 ≤ m2 thì mm1 ≤ mm2 .
Định nghĩa 1.1.5. Quan hệ thứ tự tốt trên một tập M là một quan hệ thứ
tự toàn phần trên M với thuộc tính là mọi tập con không rỗng của M có một
phần tử bé nhất trong quan hệ thứ tự này. Tập M cùng với quan hệ thứ tự tốt
được gọi là tập được sắp thứ tự tốt.
Ví dụ 1.1.6. Tập N với quan hệ thứ tự thông thường ≤ trên các số là tập được
sắp thứ tự tốt. Tập Z với quan hệ thứ tự thông thường ≤ không phải là tập
được sắp thứ tự tốt bởi vì nó không có phần tử bé nhất.
Thứ tự từ trong vành đa thức một biến là thứ tự được xác định bởi bậc của
đơn thức. Vậy với đa thức số biến từ hai trở lên thứ tự từ được xác định như thế
nào? Dưới đây ta sẽ thiết lập một số tính chất chung của thứ tự từ và các cách
xác định thứ tự từ.
Mệnh đề 1.1.7. [1, tr.76] Mọi thứ tự toàn phần ≤ trên M là thứ tự tốt khi và
chỉ khi mọi dãy đơn thức thực sự giảm:

m1 > m2 > m3 > · · ·
7


sẽ dừng (sau hữu hạn phần tử).
Chứng minh. Nếu ≤ 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à một 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ật sau khi tìm được n
đơn thức m1 > m2 > m3 · · · > 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.
Mệnh đề 1.1.8. [1, tr.76] 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 (b) của Định nghĩa 1.1.4 là thứ tự từ.
Chứng minh. Xem [1, tr.76]
Sau đây là một số thứ tự từ quan trọng.
Định nghĩa 1.1.9. [1, tr.77] Thứ tự từ điển (lexicographic order) trên tập các
đơn thức trong vành Zm [x1 , . . . , xn ], kí hiệu là ≤lex , là thứ tự từ được xác định
như sau:
x1α1 · · · xαnn ≤lex xβ1 1 · · · xβnn
nếu 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 (tức là, nếu tồn tại 0 ≤ i < n sao cho α1 = β1 , . . . , αi = βi ,
nhưng αi+1 < βi+1 .)
Ví dụ 1.1.10. Với các đơn thức 3 biến bậc tổng thể không quá 2, ta có:
1 < x3 < x23 < x2 < x2 x3 < x22 < x1 < x1 x3 < x1 x2 < x21
Định nghĩa 1.1.11. [1, tr.77] Thứ tự từ điển phân bậc (graded lex order) trên
tập các đơn thức trong vành Zm [x1 , . . . , xn ], kí hiệu là ≤glex , là thứ tự từ được
xác định như sau:
x1α1 · · · xαnn ≤glex xβ1 1 · · · xβnn

nếu deg(xα1 1 · · · xαnn ) < deg(xβ1 1 · · · xβnn ) hoặc deg(xα1 1 · · · xαnn ) = deg(xβ1 1 · · · xβnn )
và thành phần đầu tiên khác không kể từ bên trái của vector (α1 −β1 , . . . , αn −βn )
là một số âm. Nói cách khác, xα1 1 · · · xαnn ≤glex xβ1 1 · · · xβnn nếu α1 + · · · + αn <
β1 + · · · + βn hoặc α1 + · · · + αn = β1 + · · · + βn và xα1 1 · · · xαnn ≤lex xβ1 1 · · · xβnn
8


Ví dụ 1.1.12. Với các đơn thức 3 biến bậc tổng thể không quá 2, ta có:
1 < x3 < x2 < x1 < x23 < x2 x3 < x22 < x1 x3 < x1 x2 < x21
Định nghĩa 1.1.13. [1, tr.78] Thứ tự từ điển ngược (reverse lex) trên tập các
đơn thức trong vành Zm [x1 , . . . , xn ], kí hiệu là ≤rlex , là thứ tự từ được xác định
như sau:
x1α1 · · · xαnn ≤rlex xβ1 1 · · · xβnn
nếu deg(xα1 1 · · · xαnn ) < deg(xβ1 1 · · · xβnn ) hoặc deg(xα1 1 · · · xαnn ) = deg(xβ1 1 · · · xβnn )
và thành phần đầu tiên khác không kể từ bên phải của vector (α1 − β1 , . . . , αn −
βn ) là một số dương. Nói cách khác, xα1 1 · · · xαnn ≤rlex xβ1 1 · · · xβnn nếu α1 + · · · +
αn < β1 + · · · + βn hoặc α1 + · · · + αn = β1 + · · · + βn và tồn tại 1 ≤ i ≤ n sao
cho α1 = β1 , . . . , αi+1 = βi+1 , nhưng αi > βi .
Ví dụ 1.1.14. Với các đơn thức 3 biến bậc tổng thể không quá 2, ta có:
1 < x3 < x2 < x1 < x23 < x2 x3 < x1 x3 < x22 < x1 x2 < x21
Định nghĩa 1.1.15. [5, tr.563] Cho f = a0 xα(0) + · · · + ak xα(k) là một đa thức
trong Zm [x1 , x2 , . . . , xn ] với ai = 0, 0 ≤ i ≤ k và xα(0) > xα(1) > · · · > xα(k) . Ta
dùng kí hiệu sau:
deg(f ) = max{|α(i) ||0 ≤ i ≤ k} Bậc tổng thể của f .
LT≤ (f ) = a0 xα(0)

Từ dẫn đầu của f .

LM≤ (f ) = xα(0)


Đơn thức dẫn đầu của f .

LC≤ (f ) = a0
Hệ số dẫn đầu của f .
Nếu thứ tự từ ≤ đã được ngầm hiểu, ta sẽ viết LT (f )(t.ư. LC(f ), LM (f ))
thay cho LT≤ (f ) (t.ư. LC≤ (f ), LM≤ (f ))
Từ dẫn đầu của đa thức 0 được xem là không xác định (có thể nhận giá trị
tùy ý).
Từ dẫn đầu còn gọi là từ đầu hay từ đầu tiên. Như vậy nếu trong biểu diễn
của đa thức f ta viết các từ theo thứ tự giảm dần, thì LT (f ) sẽ xuất hiện đầu
tiên. Đương nhiên cách viết này cũng như từ khởi đầu của f phụ thuộc vào thứ
tự từ đã chọn.
Ví dụ 1.1.16. Cho f = x3 + 3x2 yz − 2xy 2 + 4z 2 + 6xy 3 . 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 = x3 + 3x2 yz + 6xy 3 − 2xy 2 + 4z 2 và LT≤lex (f ) = x3
9


b) Đối với thứ tự từ điển phân bậc mà x > y > z:
f = 3x2 yz + 6xy 3 + x3 − 2xy 2 + 4z 2 và LT≤glex (f ) = 3x2 yz
c) Đối với thứ tự từ điển ngược mà x > y > z:
f = 6xy 3 + 3x2 yz + x3 − 2xy 2 + 4z 2 và LT≤rlex (f ) = 6xy 3
Một số tính chất cơ bản của các từ dẫn đầu đối với một thứ tự từ ≤ nào đó
trong quan hệ với các phép toán trên vành Zm [x1 , . . . , xn ].
Bổ đề 1.1.17. Cho f, g ∈ Zm [x1 , . . . , xn ] và m ∈ M, với M là tập các đơn thức
của nó. Khi đó:
(a) LT (f g) < LT (f )LT (g).
(b) LT (mf ) = mLT (f ).
(c) LM (f + g) ≤ max{LM (f ), LM (g)}. Dấu < xảy ra khi và chỉ khi LT (f ) =

−LT (g)
Chứng minh. Vì LT (m) = m nên (b) được suy ra từ (a). Để chứng minh (a) và
(c), giả sử
f = LT (f ) + Σmi ; mi < LT (f ) và g = LT (g) + Σnj ; nj < LT (g),
trong đó mi và nj là các từ có thể bằng 0. Khi đó:
(a) Với mọi i, j: LT (f )LT (g) = 0, LT (f )nj < LT (f )LT (g) và mi LT (g) <
LT (f )LT (g). Do đó LT (f )LT (g) không giản ước được với các từ nào sau khi
bỏ ngoặc của tích f g và là từ lớn nhất. Vì vậy LT (f g) = LT (f )LT (g).
(c) Không mất tính tổng quát có thể giả thiết LT (f ) ≥ LT (g). Nếu LT (f ) >
LT (g) thì
f + g = LT (f ) + LT (g) + Σmi + Σnj .
Ta có LT (f ) > LT (g) > nj nên LT (f ) > nj . Theo định nghĩa từ khởi đầu ta lại
có LT (f ) > mi . Vậy từ LT (f ) lớn nhất trong tổng trên và không giản ước được
với các từ khác, nên
LM (f + g) = LM (f ) = max{LM (f ), LM (g)}.
Nếu LM (f ) = LM (g) và LC(f ) = −LC(g) thì
f + g = (LC(f ) + LC(g))LM (f ) + Σmi + Σnj .
Do LC(f ) + LC(g) = 0 và LM (f ) > mi , LM (f ) = LM (g) > nj nên ta có
LM (f + g) = LM (f ) = max{LM (f ), LM (g)}.
10


Nếu LT (f ) = −LT (g) thì f + g = Σmi + Σnj . Như vậy hoặc f + g = 0, hoặc
LM (f + g) = LM (mi ) < LM (f ), hoặc LM (f + g) = LM (nj ) < LM (g) (i, j nào
đó). Vì vậy
LM (f + g) ≤ max{LM (f ), LM (g)}

Chú ý 1.1.18. Bất đẳng thức ở khẳng định (c) ở trên cũng thường được viết
dưới dạng:
LT (f + g) ≤ max{LT (f ), LT (g)},

trong đó khi LM (f ) = LM (g) thì max{LT (f ), LT (g)} được hiểu như αLM (f )
với 0 = α ∈ Zm .

1.1.3 Iđêan đơn thức. Iđêan dẫn đầu.
Định nghĩa 1.1.19. [1, tr.42] Iđêan I ⊂ Zm [x1 , . . . , xn ] được gọi là iđêan đơn
thức nếu nó sinh bởi các đơn thức.
Như vậy một iđêan đơn thức có dạng I = (xα ; α ∈ A), trong đó x =
(x1 , . . . , xn ), α = (α1 , . . . , αn ) ∈ Nn , A ∈ Nn .
Ví dụ 1.1.20. I = (xy; x2 y; y 3 )
Bổ đề 1.1.21. [1, tr.42] Cho I = (xα ; α ∈ A) là iđêan đơn thức. Đơn thức
xβ ∈ I khi và chỉ khi xβ chia hết cho một đơn thức xα với α ∈ A nào đó.
Chứng minh. Nếu xβ chia hết cho một đơn thức xα với aα ∈ A thì xβ ∈ I
s

β

hi .xα(i) , trong đó

β

theo định nghĩa của iđêan. Ngược lại nếu x ∈ I thì x =
i=1

hi ∈ Zm [x1 , . . . , xn ] và α(i) ∈ A. Xem hi như là 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 xα(i)
nào đó. Sau khi giản ước, sẽ còn lại một từ trong số đó và từ đó phải bằng xβ .
Vậy xβ phải chia hết cho xα(i) nào đó.
Bổ đề 1.1.22. [1, tr.42] Cho I là iđêan đơn thức và f ∈ Zm [x1 , . . . , xn ]. Các
điều kiện sau 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 Zm [x1 , . . . , xn ] của các đơn thức thuộc I.
11


Chứng minh. Rõ ràng ta có (iii) ⇒ (ii) ⇒ (i). Để chứng minh (a) ⇒ (c) 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 xα với α ∈ 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ử từ Zm [x1 , . . . , xn ], tức là f là tổ hợp
tuyến tính trên Zm [x1 , . . . , xn ] của các đơn thức thuộc I.
Hệ quả 1.1.23. [1, tr.43] Hai iđêan đơn thức trong một vành đa thức bằng nhau
nếu chúng chứa cùng một tập đơn thức.
Bổ đề 1.1.24. [1, tr.43] Iđêan I là iđêan đơn thức khi và chỉ khi với mọi f ∈ I,
các từ của f đều thuộc I.
Chứng minh. Điều kiện cần suy ra Bổ đề 1.1.22. Từ giả thiết suy ra tập tất cả
các đơn thức của các đa thức trong I sẽ sinh ra I. Do đó điều kiện đủ được
chứng minh.
Bổ đề 1.1.25. [1, tr.43] (Bổ đề Dickson). Mọi iđêan đơn thức I = (xα ; α ∈ A)
bao giờ cũng viết được dưới dạng I = (xα(1) , . . . , xα(s) ), trong đó α(1), . . . , α(s) ∈
A. Nói riêng I là hữu hạn sinh.
Chứng minh. Xem [1, tr.43]
Định nghĩa 1.1.26. [1, tr.43] Cho I là iđêan của Zm [x1 , . . . , xn ] và ≤ là một
thứ tự từ. Iđêan dẫn đầu của I, kí hiệu là LT≤ (I), là iđêan của Zm [x1 , . . . , xn ]
sinh bởi các từ dẫn đầu của các phần tử của I, nghĩa là:
LT≤ (I) = LT≤ (f )|f ∈ I
Cũng như trên ta sẽ viết LT (I) thay vì LT≤ (I) nếu ≤ đã rõ.
Chú ý 1.1.27. Thấy rằng LT (f ) và LM (f ) chỉ khác nhau bởi một hằng số
khác 0 nên LT (I) = LM (f )|f ∈ I , và do đó LT (I) là iđêan đơn thức.
Bổ đề 1.1.28. [1, tr.85] Cho ≤ là một thứ tự từ và I, J là hai iđêan của
Zm [x1 , . . . , xn ]. Khi đó:

(a) Tập tất cả các đơn thức trong LT (I) là tập {LM (f )|f ∈ I}.
(b) Nếu I là iđêan đơn thức thì LT (I) = I
(c) Nếu I ⊆ J thì LT (I) ⊆ LT (J). Hơn nữa nếu I ⊆ J và LT (I) = LT (J) thì
I = J.
12


(d) LT (I)LT (J) ⊆ LT (IJ)
(e) LT (I) + LT (J) ⊆ LT (I + J)
Chứng minh. (a) Do LT (I) = {LM (f )|f ∈ I} là một iđêan đơn thức nên theo
Bổ đề 1.1.21 thì với mọi đơn thức m ∈ LT (I) ta đều có m = LM (f )·m , trong
đó f ∈ I và m ∈ M. Lại theo Bổ đề 1.1.17(b), m = LM (f ) · m = LM (m f )
và m ∈ I. Vậy m ∈ {LM (f )|f ∈ I}. Điều ngược lại đương nhiên đúng.
(b) Vì I là iđêan đơn thức, nên I sinh bởi một tập đơn thức A nào đó. Với mỗi
m ∈ A, m = LT (m) ∈ LT (I), nên A ⊆ LT (I), do đó I ⊆ LT (I).
Ngược lại, nếu f ∈ I là phần tử tùy ý thì theo các Bổ đề 1.1.21 và 1.1.22,
LT (f ) chia hết cho đơn thức m ∈ A nào đó. Lại theo Bổ đề 1.1.21, LT (f ) ∈
I. Suy ra LT (I) ⊆ I, tức là LT (I) = I.
(c) Với mọi f ∈ I thì LT (f ) ∈ LT (I). Do I ⊆ J nên f ∈ J. Suy ra LT (f ) ∈
LT (J). Do đó LT (I) ⊆ LT (J).
Giả sử LT (I) = LT (J) Nếu I = J, theo Mệnh đề 1.1.8, có thể chọn được
f ∈ J \ I để
LM (f ) = min{LM (g)|g ∈ J \ I}.
Vì LM (f ) ∈ LT (J) = LT (I), nên tồn tại g ∈ I sao cho LM (f ) = LM (g).
Thay f, g bằng f /LC(f ), g/LC(g) ta có thể giả thiết LC(f ) = LC(g) = 1.
Đặt h = f − g. Vì f, g ∈ J nên h ∈ J. Nhưng f ∈
/ I và g ∈ I nên h ∈
/ I. Vậy
h ∈ J \ I. Mặt khác, theo Bổ đề 1.1.17(c) ta lại có LM (h) < LM (f ). Điều
này mâu thuẫn với việc chọn f . Vậy I = J.

(d) Vì LT (I)LT (J) sinh bởi các từ LT (f )LT (g), trong đó f ∈ I và g ∈ J, và theo
Bổ đề 1.1.17(a) LT (f g) = LT (f )LT (g), nên ta có LT (f )LT (g) ⊆ LT (IJ)
(e) Với mọi f ∈ LT (I) + LT (J) thì tồn tại g ∈ I, h ∈ J sao cho
f = LT (g) + LT (h)
Mặt khác, g ∈ I ⊆ I + J và h ∈ J ⊆ I + J nên LT (g), LT (h) ∈ LT (I + J).
Do đó f ∈ (I + J). Suy ra LT (I) + LT (J) ⊆ LT (I + J)

13


1.2 Cơ sở Groebner của iđêan các đa thức triệt tiêu
trong vành Zm[x1, . . . , xn]
Cho α = (α1 , . . . , αn ), β = (β1 , . . . , βn ) ∈ Nn , ta định nghĩa
α ± β = (α1 ± β1 , . . . , αn ± βn ).
Ta có thể so sánh α và β theo tính chất α
và tương tự α ≺ β ⇔ α

β ⇔ ∀i ∈ {1, . . . , n} : αi ≤ βi

β ∧ α = β.

Với α = (α1 , . . . , αn ) ∈ {0, 1, 2, . . .}n , ta kí hiệu: α! = α1 ! · · · αn ! và |α| =
α1 + · · · + αn .
Bởi vì ta sẽ nghiên cứu về tính chia hết trong Zm [x1 , . . . , xn ] nên ta cần phân
biệt tính chia hết trong Zm và trong Z. Ta gọi a là ước của b trên Z, kí hiệu
a|Z b ⇔ ∃k ∈ Z : b = a · k và a là ước của b trên Zm kí hiệu a|m b ⇔ ∃k ∈ Z :
m|Z (b − a · k), vì b và a · k đại diện cho cùng một lớp trong Zm .
Với hai đơn thức axα , bxβ ta nói axα là ước của bxβ nếu a|m b ∧ α

β. Ta


thường kí hiệu axα |bxβ .
Định nghĩa 1.2.1. [5, tr.563] Cho một iđêan I ⊂ Zm [x1 , . . . , xn ]. Một tập hữu
hạn G ⊂ I được gọi là một cơ sở Groebner của I nếu:
L(I) = L(G)
Nhìn chung, tất cả những điều được định nghĩa trên phụ thuộc vào thứ tự từ
được chọn. Đặc biệt, một tập G có thể là cơ sở Groebner chỉ với một thứ tự từ
nhất định nào đó. Chú ý rằng, với định nghĩa đã cho I sinh bởi G.
Định nghĩa 1.2.2. [5, tr.563] Cơ sở Groebner G được gọi là một cơ sở Groebner
mạnh nếu với mọi f ∈ I \ {0}, tồn tại đa thức g ∈ G sao cho LT (g)|LT (f ).
Định nghĩa 1.2.3. [5, tr.563] G là một cơ sở Groebner mạnh được gọi là cơ sở
Groebner mạnh tối tiểu nếu LT (g1 ) LT (g2 ) với mọi g1 , g2 ∈ G phân biệt.
Lưu ý rằng nếu Zm là một trường ( với m là số nguyên tố), bất kỳ hệ số
khác không của một từ đều có phần tử khả nghịch trong Zm , khi đó LT (f ) =
a · LM (f ) với a ∈ Zm do đó ∃a−1 ∈ Zm : a−1 · LT (f ) = LM (f ) ∈ L(I), vì vậy
L(I) = LM (f )|f ∈ I . Dễ dàng kiểm chứng được trong trường hợp này tất cả
cơ sở Groebner là một cơ sở Groebner mạnh. Điều này nhìn chung không đúng
khi Zm là một vành. Ta xét ví dụ sau:
14


Ví dụ 1.2.4. Xét Z6 [x] là vành đa thức một biến. Khi đó G = {2x, 3x} là một
cơ sở Groebner của iđêan I = x .
Nhưng vì 2x và 3x đều không là ước của x. Do đó G không là một cơ sở
Groebner mạnh.
Bổ đề 1.2.5. [1, tr.88] Cho I là một iđêan tùy ý của Zm [x1 , . . . , xn ]. Nếu
g1 , . . . , gs là cơ sở Groebner của I đối với một thứ tự từ nào đó, thì g1 , . . . , gs là
cơ sở của I.
Chứng minh. Đặt J = (g1 , . . . , gs ) ⊆ I. Vì LT (I) = (LT (g1 ), . . . , LT (gs )) ⊆
LT (J) ⊆ LT (I), nên LT (J) = LT (I). Theo Bổ đề 1.1.28 (c), ta có I = J

Như vậy, việc xác định iđêan dẫn đầu tương đương với việc tìm một cơ sở
Groebner của I (đối với một thứ tự từ nào đó). Tuy nhiên việc này không đơn
giản vì không phải mọi cơ sở của I là cơ sở Groebner của I. Hơn nữa, một cơ
sở đã cho của I có thể là cơ sở Groebner đối với thứ tự này, nhưng không là cơ
sở Groebner đối với thứ tự khác.
Ví dụ 1.2.6.

i) Cho I = (xy, y 3 ) ⊆ Zm [x, y] và f1 = xy, f2 = xy − y 3 . Cho

x > y. Khi đó LT≤lex (f1 ) = LT≤lex (f2 ) = xy, nên {f1 , f2 } không là cơ sở
Groebner của iđêan I đối với ≤lex , vì LT≤lex (I) = I. Tuy nhiên LT≤glex (f1 ) =
LT≤rlex (f1 ) = xy, LT≤glex (f2 ) = LT≤rlex (f2 ) = y 3 và LT≤glex (I) = LT≤rlex (I) =
I nên f1 , f2 là cơ sở Groebner của iđêan I đối với thứ tự từ điển phân bậc
và thứ tự từ điển ngược.
ii) Cho I = (f1 , f2 ) ⊆ Zm [x, y], trong đó f1 = x3 − 2xy và f2 = x2 y − 2y 2 + x.
Xét thứ tự từ điển phân bậc hoặc thứ tự từ điển ngược. Khi đó LT (f1 ) = x3 ,
LT (f2 ) = x2 y. Tuy nhiên x2 = x.f2 − y.f1 ∈ I và LT (x2 ) = x2 ∈
/ (x3 , x2 y)
nên f1 , f2 không là cơ sở Groebner của iđêan I đối với thứ tự này.
iii) Cho I = (x + y, y + z) ⊆ Zm [x, y, z] và xét thứ tự từ điển với x > y > z.
Ta sẽ chứng tỏ x + y, y + z là cơ sở Groebner của I. Thật vậy mọi phần tử
0 = f ∈ I có dạng f = g.(x + y) + h.(y + z). Nếu LT (f ) không chứa x và
y thì f chỉ chứa biến z, tức f = f (z). Thay x = z và y = −z vào biểu thức
vừa nêu của f , ta có f = f (z) = g(z, −z, z).0 + h(z, −z, z).0 = 0, vô lý. Vậy
LT (f ) ∈ (x, y) = (LT (x + y), LT (y + z)), hay x + y, y + z là cơ sở Groebner
của I đối với thứ tự từ điển.

15



1.2.1 Iđêan các đa thức triệt tiêu.
Định nghĩa 1.2.7. [5, tr.564] Cho đa thức f ∈ Zm [x1 , . . . , xn ], hàm đa thức
của f là:
f : Znm → Zm
(c1 , . . . , cn ) −→ f (c1 , . . . , cn )
Khi đó, ta gọi f là một đa thức triệt tiêu nếu hàm f đồng nhất không.
Tập I0 = {f ∈ Zm [x1 , . . . , xn ]|f là một đa thức triệt tiêu} là một iđêan trong
Zm [x1 , . . . , xn ] và được gọi là iđêan các đa thức triệt tiêu.
Bổ đề 1.2.8. [5, tr.564] Xét a ∈ Z và α = (α1 , . . . , αn ) ∈ Nn sao cho m|Z aα!.
Khi đó

n

αi

(xi − l) ∈ Zm [x1 , . . . , xn ]

pα,a = a
i=1 l=1

là một đa thức triệt tiêu.
Chứng minh. Cố định (c1 , c2 , . . . , cn ) ∈ Znm .
Với mọi i, pα,a (c1 , c2 , . . . , cn ) có các thừa số liên tiếp là ci −1, ci −2, . . . , ci −αi .
Các thừa số này độc lập với giá trị của ci và chứa các thừa số từ 2 đến αi . Do
đó αi ! là ước pα,a (c1 , c2 , . . . , cn ), ∀i. Kết hợp kết quả trên ta có aα1 ! . . . αn ! là ước
của pα,a (c1 , c2 , . . . , cn ). Mà m|Z aα!.
Vì vậy pα,a (c1 , c2 , . . . , cn ) = 0 theo modulo m.
Bổ đề 1.2.9. [5, tr.564] Cho f ∈ I0 ⊂ Zm [x1 , x2 , . . . , xn ] là một đa thức triệt
tiêu tùy ý với LT (f ) = bxβ . Khi đó m|Z bβ!.
Chứng minh. Cho Zm [x1 , x2 , . . . , xn ] là vành đa thức n biến (n ≥ 1) và h ∈

Zm [x1 , x2 , . . . , xn ] là một đa thức. Khi đó ta định nghĩa sai phân riêng thứ i
∇i h = h(x1 , . . . , xi−1 , xi + 1, xi+1 , . . . , xn ) − h(x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ).
với 1 ≤ i ≤ n, ∇i là một toán tử tuyến tính. Và
∇0i h = h, và ∇k+1
h = ∇i ∇ki h, với k ≥ 0.
i
Rõ ràng, ∇i ∇j h = h(x1 , . . . , xi +1, . . . , xj +1, . . . , xn )−h(x1 , . . . , xi +1, . . . , xn )−
h(x1 , . . . , xj + 1, . . . , xn ) + h(x1 , . . . , xn ) = ∇j ∇i h, với mọi i, j ∈ {1, . . . , n}, ta
có thể mở rộng với bộ chỉ số α = (α1 , . . . , αn ) ∈ {0, 1, 2, . . .}n ,
∇α h = ∇α1 1 ∇α2 2 . . . ∇αnn h
16


không phụ thuộc vào thứ tự của các ∇i .
Xét sai phân (xi + 1)k − xki = k · xk−1
+ g(xi ), với deg(g) < k − 1.
i
Bằng quy nạp ta có: ∇ki xki = k! và ∇ji xki = 0, với mọi j > k.
Ta kí hiệu axα = LT (h) là từ dẫn đầu của h. Khi đó, nhờ vào sự tuyến tính
của toán tử ∇i ta có:
∇α h = aα! và ∇β h = 0, với mọi β

a.

Áp dụng đẳng thức thứ nhất cho đa thức triệt tiêu f trên vành Zm . Khi đó:
∇β f = bβ! là một đa thức triệt tiêu.
Vì vậy bβ! = 0 theo modulo m.

1.2.2 Cơ sở Groebner mạnh tối tiểu của I0
Định nghĩa 1.2.10. [5, tr.566] Xét vành đa thức Zm [x1 , x2 , . . . , xn ]. Ta định

nghĩa các tập như sau:
Sm = {(α, a)| 1 ≤ a < m, a|Z m, α ∈ Nn0 , m|Z aα!,
∀β ≺ α : m

Z

aβ!,

∀b < a, b|Z a : m
Gm = {pα,a |

Z

bα!},

(α, a) ∈ Sm }.

Chú ý rằng, theo Bổ đề 1.2.8, tất cả đa thức của Gm là phần tử của I0 . Và
theo Bổ đề 1.2.9, ta hy vọng có thể xây dựng một cơ sở Groebner mạnh.
Định lý 1.2.11. [5, tr.566] Cho m ≥ 2, n ≥ 1 là các số nguyên tùy ý. Với kí
hiệu ở trên Gm là một cơ sở Groebner mạnh tối tiểu của iđêan các đa thức triệt
tiêu I0 ⊂ Zm [x1 , x2 . . . , xn ] mà không phụ thuộc vào thứ tự từ nào.
Trước khi chứng minh định lý, ta xem ví dụ sau.
Ví dụ 1.2.12. Cho m = q1 · q2 · · · qk là tích của k số nguyên tố phân biệt, k ≥ 1
và n ≥ 1 tùy ý.
Giả sử q1 < q2 < . . . < qk . Khi đó tất cả phần tử Gm có dạng:
(xi − 1)(xi − 2) · · · (xi − qk ),
qk · (xi − 1)(xi − 2) · · · (xi − qk−1 ),
qk · qk−1 · (xi − 1)(xi − 2) · · · (xi − qk−2 ),
...

qk · qk−1 · · · q2 · (xi − 1)(xi − 2) · · · (xi − q1 ),
17


trong mỗi hàng i ∈ {1, 2, . . . , n}. Xét hàng đa thức thứ nhất trong Gm , vì qk !
chia hết cho mọi qj , ∀j, do đó m|Z qk !
Ta có với mọi r < qk , qk

r!, tức là m

Z

Z

r!. Lâp luận tương tự cho những

đa thức còn lại. Hơn nữa, mọi phần tử Gm điều chỉ chứa một biến và những đa
thức được nhắc đến điều là phần tử của Gm .
Trong trường hợp đặc biệt |Gm | = k · n và bậc cao nhất là qk . Điều đó có
nghĩa là độ lớn của cơ sở chỉ phụ thuộc vào số biến.
Trường hợp k = 1, Z/q1 là một trường, ta chỉ thu được n đa thức ở hàng đầu
tiên.
Chứng minh. Xét m ≥ 2, n biến với n ≥ 1 và một thứ tự từ tùy ý. Trước hết ta
cần chừng minh Gm là cơ sở Groebner của I0 . Tức là chứng minh:
i) Gm là tập hữu hạn.
ii) Gm ⊂ I0
iii) L(I0 ) ⊂ L(Gm )
Ta có Gm ⊂ I0 ⇒ L(Gm ) ⊂ L(I0 ).
i)Vì (α, a) ∈ Sm nên α


(m, m, . . . , m). Do đó, Gm là tập hữu hạn.

ii) Gm bao gồm đa thức pα,a với m|Z aα!. Khi đó, Gm ⊂ I0 theo Bổ đề 1.2.8.
iii) Xét f ∈ L(I0 ) bất kỳ, tồn tại số nguyên N ≥ 1, hi ∈ Zm [x1 , x2 , . . . , xn ] và
fi ∈ I0 , 1 ≤ i ≤ N , sao cho:
N

hi · LT (fi ).

f=
i=1

Đặt ai xα

(i)

= LT (fi ), ta có m|Z ai α(i) ! theo Bổ đề 1.2.9. Mà (α(i) , ai ) là một phần

tử của Sm . Hay ta có thể thay ai bởi bi |Z ai hoặc α(i) bởi β (i) với β (i)

α(i) sao

cho (β (i) , bi ) ∈ Sm . Ta có thể gộp hai trường hợp ở trên với mỗi i ∈ {1, 2, . . . , N }
(i)

có (β (i) , bi ) ∈ Sm sao cho bi xβ |LT (fi ). Với đa thức gi thích hợp, 1 ≤ i ≤ N ta
có:

N


hi · gi · LT (pβ (i) ,bi ),

f=
i=1

tức là f ∈ L(Gm ).
Tiếp theo, cho f ∈ I0 . Khi đó, với lập luận tương tự như fi ở trên, tồn tại
pγ,c ∈ Gm sao cho LT (pγ,c )|LT (f ). Điều này chứng tỏ rằng Gm là một cơ sở
Groebner mạnh.
18


Phần còn lại ta chứng minh Gm tối tiểu.
Lấy hai cặp (α, a), (β, b) ∈ Sm sao cho axα |bxβ . Khi đó a|m b, a|Z m, b|Z m, và
α

β. Ta cần chứng minh a = b và α = β.
Xét trên Z, cho một thừa số nguyên tố q của b và k ≥ 1 lớn nhất sao cho

q k |Z b. Giả sử q k

Z

a. Khi đó aα! hơn bα! ít nhất là một thừa số q trong phân

tích thành thừa số nguyên tố. Nhưng vì m|Z aα!, ta có m|Z b/q · α!|Z b/q · β!, và b
không phải phần tử nhỏ nhất trong (β, b) ∈ Sm . Tóm lại b|Z a.
Ta viết a = d · b với d|Z m. Ta có a|m b, tức là m|Z a · c − b với c bất kỳ. Ta
nhận được b · d = a|Z m do đó b · d|Z bcd − b = b(cd − 1). Vì vậy d|Z (cd − 1) suy
ra d = 1, dó đó a = b. Vì vậy ta cũng có α = β, bởi vì nói cách khác β không là

phần tử tối tiểu trong (β, b) ∈ Sm .
Định lý 1.2.13. [5, tr.567]
a) Cho G, F là hai cơ sở Groebner mạnh tối tiểu của iđêan I ⊂ C[x1 , x2 , . . . , xn ],
với C là vành giao hoán có đơn vị là 1. Khi đó |G| = |F | và:
∀g ∈ G, ∃f ∈ F, ∃c ∈ C : LT (g) = c · LT (f ).

(∗)

b) Nếu C = Zm và I = I0 thì c trong (∗) là phần tử đơn vị của Zm .
Chú ý rằng phát biểu b) đúng với mọi iđêan, nếu vành C là một miền xác định.
Chứng minh. a) Với mọi g ∈ G ⊂ I. Vì F là cơ sở Groebner mạnh nên với f ∈ F
thì LT (f )|LT (g). Hơn nữa, do G là cơ sở Groebner mạnh nên tồn tại g ∈ G sao
cho LT (g )|LT (f ). Do đó, LT (g )|LT (f )|LT (g), suy ra g = g ( vì G tối tiểu).
Nhưng đơn thức dẫn đầu LM (f ) và LM (g) như nhau, do đó ta cần tìm mối
liên hệ giữa LT (f ) và LT (g).
Tương tự lập luận trước, dễ dàng thấy được nếu tồn tại f, f ∈ F sao cho
LT (g) = c · LT (f ) và LT (g) = c · LT (f ) thì LT (f ) = LT (f ). Do đó ta có đẳng
thức |{LT (g)|g ∈ G}| = |{LT (f )|f ∈ F }|, rõ ràng |G| = |F | (vì G và F tối
tiểu).
b) Chọn G = Gm là cơ sở Groebner , và F là cơ sở Groebner mạnh tối tiểu
bất kỳ của I0 ⊂ Zm [x1 , x2 , . . . , xn ]. Xét một quan hệ tượng tự như (∗), tức là
b · xβ = c · a · xα , với (β, b) ∈ Sm và a · xα là từ dẫn đầu của f ∈ F . Khi đó
b = a · c mod m hay m|Z ac − b.
Xét a = gcd(a, m) là ước chung lớn nhất của a và m, ta có a = a · u, với
gcd(u, m) = 1 điều này có nghĩa u là phần tử đơn vị trong Zm . Vì a|Z m|Z ac − b,
ta có a|Z b.
19


Ta cần chứng minh a = b, bằng phản chứng, giả sử a < b. f ∈ F ⊂ I0 suy ra

m|Z aα! theo Bổ đề 1.2.9, như vậy m|Z aα! = aβ! vì thừa số trong a/a không ảnh
hưởng đến phép chia cho m, vậy nên hiển nhiên α = β. Nhưng điều đó có nghĩa
là ta có thể thay b bằng một số a nhỏ hơn mà vẫn đảm bảo điều kiện m|Z aβ!.
Điều này mâu thuẫn với với tính tối tiểu của b trong (β, b) ∈ Sm . Vì vậy a = b.
Ta có khẳng định u · bxβ = axα , và c có thể được thay bởi phần tử đơn vị
u−1 ∈ (Zm )∗ .
Ta thấy có mối liên hệ giữa từ dẫn đầu của bất kỳ cơ sở Groebner mạnh tối
tiểu F của I0 ⊂ Zm [x1 , x2 , . . . , xn ] với từ dẫn đầu trong Gm bởi phần tử đơn
vị. Theo tính chất bắc cầu, ta có thể thấy rõ mối quan hệ giữa từ dẫn đầu của
hai cơ sở Groebner mạnh tối tiểu bởi phần tử đơn vị. Kết luận này là điều phải
chứng minh.
Chú ý 1.2.14. Với số c bất kỳ, mối quan hệ giữa hai từ dẫn đầu không nhất
thiết là một phần tử đơn vị.
Ví dụ 1.2.15. Xét đa thức f (x, y) = 3(x − 1)(x − 2) · (y − 1)(y − 2) ∈ G12 . Ta có
thể chuyển sang một cơ sở Groebner mạnh tối tiểu khác của I0 ⊂ Z12 [x, y], thay
f (x, y) bởi f (x, y) = 9(x − 1)(x − 2) · (y − 1)(y − 2). Lưu ý rằng trên Z12 iđêan
f và f

là đồng nhất. Do đó, Gm \ {f } ∪ {f } vẫn là một cơ sở Groebner

mạnh tối tiểu. Rõ ràng LT (f ) = 3 · LT (f ), nhưng 3 không phải phần tử đơn vị
trong Z12 .
Ta chỉ ra rằng cơ sở Groebner mạnh tối tiểu nhìn chung không duy nhất.
Điều này là do ta chỉ xét từ dẫn đầu mà không yêu cầu phần dư ở đây. Ví dụ,
trong trường hợp của iđêan I0 , ta có thể dễ dàng thay đổi cơ sở Gm và vẫn có
một cơ sở Groebner mạnh tối tiểu. Để chứng minh điều này, ta cho f, g ∈ Gm
với LM (g) < LM (f ) và thay f bởi f + g.
Nhắc lại sự phức tạp của Gm , ta có |Gm | là một hàm theo biến n. Theo Ví
dụ 1.2.12 thì |Gm | là một hàm tuyến tính theo n, đồng thời các thừa số nguyên
tố của m là phân biệt. Tổng quát, ta có m = q1e1 · q2e2 · · · qkek , trong đó các ej > 1.

Nếu xét trường hợp đặc biệt m = q k , với việc chọn m hợp lý, ta suy ra kích
thước của Gm là một đa thức theo n. Ta xét sự giới hạn của |Gm | khi n lớn. Giả
sử n > m = q k thì Gm được biểu diễn dưới dạng:

20


(j)

Gm =
(j)
Gm

Gm , với
0≤j≤k
j

= {q · (xi − 1) · · · (xi − (k − j)q|1 ≤ i ≤ n}

0≤j≤k

∪{q j · (xi1 − 1) · · · (xi1 − s1 q)(xi2 − 1) · · · (xi2 − s2 q)|
1 ≤ i1 , i2 ≤ n; i1 = i2 ; 1 ≤ s1 , s2 ; s1 + s2 = k − j}
...
∪{q j · (xi1 − 1){· · · (xi1 − q)(xi2 − 1) · · · (xi2 − q) · · ·
(xik−j − 1) · · · (xik−j − q)|1 ≤ iu ≤ n; iu = iv với u = v},
(j)

Tức là, trong Gm ta có hệ số không đổi q j , và các đa thức từ 1 đến k − j
(j)


biến. Với hj = |Gm |, ta có đánh giá sau:
k−j
n
n
hj ≤ n+
·k 1 +· · ·+
·k k−j−1 =
2
k−j
l=1

n
l

·k l−1 ≤

n
k

·k k ,

n

hj ≥

.
k−j
Cho h = |Gm | =
n


k−1

≤

0≤j≥k

n

hj ta có:
≤h≤k·

n

k
k−j
k
j=0
và h = |Gm | là đa thức bậc k theo biến n.

· kk =

n
k

· k k+1 ,

1.2.3 Thuật toán tìm cơ sở Groebner mạnh tối tiểu trong vành
Zm
Cấu trúc đơn giản của cơ sở Groebner mạnh tối tiểu giúp ta xây dựng Gm

từ cơ sở với số m nhỏ hơn. Ta tính GM từ những phần tử đã tính được của tập
Gm , m > 1 với M = q · m (q là số nguyên tố). Ta có biểu diễn của GM thành 3
tập rời nhau được xác định như sau:
GM = {pα,a ∈ Gm , (α, a) ∈ SM }
∪{pα,aq |pα,a ∈ Gm , (α, aq) ∈ SM }
∪{pα+β,b |pα,a ∈ Gm , ∃β ∈ B(α, a, q) ∃b|Z M : (α + β, b) ∈ SM },
Với B(α, a, q) bao gồm tập tất cả β

(0, 0, . . . , 0) sao cho (α + β)! chứa hơn

aα! một thừa số nguyên tố q.
Sự khai triển này cho thấy ta có thể tìm được ngay phần tử của GM trong
Gm . Hoặc là ta có thể xây dựng một phần tử của GM bởi tích q lần các phần tử
của Gm . Ngoài ra, nếu chỉ thay đổi hệ số, ta có thể thử phát triển số mũ vector
21