BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC SƯ PHẠM

NGUYỄN VĂN TÂN

¨
TÌM HIỂU VỀ CƠ SỞ GROBNER
VÀ
ỨNG DỤNG

Chuyên ngành: ĐẠI SỐ VÀ LÝ THUYẾT SỐ
Mã số: 60.46.01.04

LUẬN VĂN THẠC SĨ TOÁN HỌC

Cán bộ hướng dẫn khoa học

PGS-TS. PHAN VĂN THIỆN

Huế, Năm 2016
i


LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên
cứu của riêng tôi, các số liệu và kết quả nghiên
cứu nêu trong luận văn là trung thực, được các
đồng tác giả cho phép sử dụng và chưa từng
được công bố trong bất kỳ một công trình nào
khác.

Nguyễn Văn Tân

ii


LỜI CẢM ƠN

Luận văn này được hoàn thành dưới sự hướng dẫn khoa học tận tình của
PGS.TS. Phan Văn Thiện. Tác giả xin được bày tỏ lòng biết ơn sâu sắc vì sự
quan tâm, giúp đỡ và tạo điều kiện tối đa của thầy trong quá trình thực hiện
luận văn. Tác giả cũng xin gửi lời cảm ơn sâu sắc đến quý thầy cô giáo trong
Khoa Toán, Trường Đại học Sư phạm Huế đã tận tâm truyền đạt kiến thức cho
tác giả trong suốt quá trình học Cao học. Cuối cùng tác giả xin gửi lời cảm ơn
sâu đến phòng đào tạo sau đại học, các bạn học viên cao học khóa 23 đã luôn
quan tâm giúp đỡ tác giả trong suốt thời gian học tập.
Nguyễn Văn Tân

iii


MỤC LỤC

Trang phụ bìa

ii

Lời cam đoan

ii


Lời cảm ơn

iii

Mục lục

2

Lời mở đầu

3

¨
1 CƠ SỞ GROBNER

4

1.1

Các thứ tự đơn thức . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Thuật chia đa thức trong vành nhiều biến . . . . . . . . . . . .

7

1.3


Cơ sở Gr¨obner

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

13

1.4

Thuật toán Buchberger . . . . . . . . . . . . . . . . . . . . . . .

21

1.5

Cơ sở Gr¨obner rút gọn . . . . . . . . . . . . . . . . . . . . . . .

31

1.6

Tính cơ sở Gr¨obner bằng Maple 13 . . . . . . . . . . . . . . . .

34

¨
2 ỨNG DỤNG CỦA CƠ SỞ GROBNER

39


2.1

Bài toán thử thành viên ideal . . . . . . . . . . . . . . . . . . .

39

2.2

Bài toán thử hai ideal bằng nhau . . . . . . . . . . . . . . . . .

41

2.3

Bài toán tìm cơ sở của K-không gian vectơ K[x]/I . . . . . . .

42

2.4

Bài toán khử biến để tìm giao của hai ideal

45

1

. . . . . . . . . . .


2.5


Bài toán khử biến để tìm ước chung lớn nhất và bội chung nhỏ
nhất của hai đa thức . . . . . . . . . . . . . . . . . . . . . . . .

50

2.6

Bài toán khử biến để tìm thương của hai ideal . . . . . . . . . .

51

2.7

Bài toán tìm nghiệm nguyên không âm của hệ phương trình có
hệ số nguyên không âm

2.8

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

54

Bài toán tìm nghiệm không âm của hệ phương trình hệ số nguyên
bất kỳ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

Kết luận


63

Tài liệu tham khảo

65

2


LỜI MỞ ĐẦU

Cho K là một trường, trong tài liệu này ta sẽ đề cập đến vành đa thức nhiều
biến K[x1 , x2 , ..., xn ]. Cho I là một ideal trong K[x1 , x2 , ..., xn ] sinh bởi các đa
thức f1 , f2 , ..., ft ∈ K[x1 , ...., xn ], ta kí hiệu I = f1 , f2 , ..., ft . Ta sẽ tiến nghiên
cứu một loại tập sinh đặc biệt của ideal I đó chính là cơ sở Gr¨obner.
Lý thuyết về cơ sở Gr¨obner được nhà toán học Bruno Buchberger (học trò
của nhà toán học Gr¨obner) đề xuất năm 1965. Lý thuyết cơ sở Gr¨obner ra đời
tạo một bước ngoặc lớn trong nghiên cứu, giúp chứng minh nhiều bài toán đại
số, hình học cũng như việc kiểm chứng một giả thuyết hay một bài toán đại
số hoặc hình học. Hiện nay nhờ có các phần mềm, chẳng hạn như Maple mà
việc tính cơ sở Gr¨obner, các thuật toán chia và một vài thuật toán khác nhanh
hơn và dễ dàng thực hiện hơn. Việc nghiên cứu cơ sở Gr¨obner đã tỏ ra rất hữu
ích khi hàng loạt các ứng dụng của nó trong đại số và hình học đại số. Có thể
kể đến là giúp giải bài toán thành viên ideal, các bài toán về tìm giao của hai
ideal, tìm thương của hai ideal,. . . , giúp ta tìm nghiệm của các hệ phương trình
nghiệm nguyên (xem ở [2], [3], [4], [5],...).
Với mong muốn được tìm hiểu thêm về cơ sở Gr¨obner và những ứng dụng
của nó và được sự định hướng của thầy hướng dẫn PGS.TS Phan Văn Thiện,
tôi đã chọn đề tài "Tìm hiểu về cơ sở Gr¨obner và ứng dụng" làm đề tài nghiên
cứu cho luận văn. Mặc dù đã có nhiều cố gắng, song trong việc nghiên cứu và

trình bày khó tránh khỏi các sai sót, mong quý độc giả góp ý thêm để luận văn
được hoàn thiện hơn.
3


CHƯƠNG 1
¨
CƠ SỞ GROBNER

Trong chương này sẽ đề cập đến các thứ tự từ, thuật chia đa thức trong vành
nhiều biến, cơ sở Gr¨obner, thuật toán Buchberger, cơ sở Gr¨obner rút gọn và
cách dùng Maple để tính cơ sở Gr¨obner. Ta kí hiệu x := (x1 , x2 , ..., xn ) và kí
hiệu K[x1 , x2 , ..., xn ] := K[x]. Tài liệu tham khảo chính của chương này là [1],
[5].

1.1

Các thứ tự đơn thức

Định nghĩa 1.1.1. Một quan hệ < trên tập X được gọi là quan hệ thứ tự nếu
nó thỏa mãn các tính chất phản xạ, đối xứng, bắt cầu. Nếu trong tập X có quan
hệ thứ tự thì ta nói X được sắp thứ tự. Đồng thời nếu hai phần tử bất kỳ trong
X đều so sánh được với nhau thì X được gọi là tập sắp thứ tự toàn phần. Nếu
X là tập sắp thứ tự toàn phần sao cho bất kỳ tập con nào khác rỗng của X đều
có phần tử nhỏ nhất thì X được gọi là tập sắp thứ tự tốt.
Tiếp theo cho vành đa thức n biến K[x1 , x2 , ..., xn ]
Một phần tử trong K[x1 , x2 , ..., xn ] có dạng a.xα1 1 .xα2 2 .....xαnn với a ∈ K và αi ∈
N, ∀i = 1, ..., n được gọi là một đơn thức trong K[x].
Một phần tử trong K[x1 , x2 , ..., xn ] có dạng xα1 1 .xα2 2 .....xαnn với αi ∈ N, ∀i =
1, ..., n được gọi là một từ trong K[x].

Đặt T n = {xβ : = x1 β1 ....xn βn |βi ∈ N, i = 1, ... , n } được gọi là tập các từ trong
K[x1 , x2 , ..., xn ].
4


Định nghĩa 1.1.2. Một thứ tự từ trong T n là một thứ tự toàn phần < trong
T n nếu thỏa mãn hai điều kiện sau:
1) 1 < xβ với mọi xβ ∈ T n , xβ = 1.
2) Nếu xα < xβ thì xα xγ < xβ xγ với mọi xγ ∈ T n .
Ta nói thêm, đơn thức nào có từ lớn hơn thì đơn thức đó lớn hơn, như vậy tập
các đơn thức có quan hệ thứ tự toàn phần và ta gọi là thứ tự đơn thức, ta có
thể hiểu thứ tự từ và thứ tự đơn thức là khá giống nhau.
Sau đây là một vài thứ tự từ (hay thứ tự đơn thức):
Định nghĩa 1.1.3 (Thứ tự từ điển “lex”). Giả sử x1 > x2 > .... > xn ,
α = (α1 , ... ,αn ) và β = (β1 , ... , βn ) ∈ N n . Khi đó:

 thành phần thứ nhất αi và βi trong α và β từ trái sang
α
β
x 
 mà khác nhau thì αi < βi
Ví dụ 1. Cho x, y ∈ Q[x, y], nếu x < y, theo thứ tự "lex", thì 1 < x < x2 <
x3 < .... < y < xy < x2 y < ... < y 2 < ...
Định nghĩa 1.1.4 (Thứ tự từ điển phân bậc “deglex”). Giả sử x1 > x2 >
.... > xn , α = (α1 , ..., αn ) và β = (β1 , ... , βn ) ∈ N n
n

n

αi <
βi


i=1
i=1
Khi đó: xα < xβ ⇔ 
n
n

 nếu
βi thì dùng ”lex”.
αi =
i=1

i=1

Ví dụ 2. Cho x, y ∈ Q[x, y], nếu x < y, theo thứ tự deglex, thì 1 < x < y <
x2 < xy < y 2 < x3 < x2 y < xy 2 < y 3 < ....
5


Định nghĩa 1.1.5 (Thứ tự từ điển ngược phân bậc “degrevlex”). Giả sử
x1 > x2 > .... > xn , α = (α1 , ... , αn ) và β = (β1 , ... , βn ) ∈ N n .
n






α
β
Khi đó: x < x ⇔ 




n

αi <
i=1



 nếu

βi
i=1
n

n

αi =
i=1

βi thì thành phần đầu tiên αi và βi
i=1




 trong α và β từ phải sang mà khác nhau thì α > β .
i
i

Ví dụ 3. Cho x1 , x2 , x3 ∈ Q[x1 , x2 , x3 ], nếu x1 > x2 > x3 , theo thứ tự degrevlex
thì x1 2 x2 x3 > x1 x2 3 , nhưng theo deglex thì x1 2 x2 x3 < x1 x2 3 .
Mệnh đề 1.1.6. Cho xα , xβ ∈ T n . Nếu xα chia hết xβ thì xα ≤ xβ .
Chứng minh: Giả sử có xγ ∈ T n sao cho xβ = xα xγ . Theo Định nghĩa 1.1.2
thì xγ ≥ 1 và ta có xβ = xα xγ ≥ xα .1 = xα hay xα ≤ xβ .
Định nghĩa 1.1.7. Cho f ∈ K[x1 , x2 , ..., xn ], f = 0, ta có thể viết f dưới dạng
f = a1 xα1 + a2 xα2 + ... + ar xαr
với ai ∈ K, xαi ∈ T n , ∀i = 1, ..., r và xα1 > xα2 > ... > xαr . Khi đó, ta định
nghĩa:
• lp(f ) = xα1 , gọi là lũy thừa dẫn đầu (hoặc từ dẫn đầu) của f .
• lc(f ) = a1 , gọi là hệ số dẫn đầu của f .
• lt(f ) = a1 xα1 , gọi là hạng tử dẫn đầu của f .
• T (f ) = {X ∈ T n X là hạng tử của f }.
Định lý 1.1.8. Mỗi thứ tự từ trong T n đều là thứ tự tốt, tức là mọi tập con A
của T n đều tồn tại xα ∈ A sao cho xβ ≤ xα , ∀xβ ∈ A.
6


Nhận xét: Cho f1 , ..., fm ∈ T n , khi đó theo định lý trên sẽ tồn tại phần tử
lớn nhất fi ∈ {f1 , ..., fm }, sao cho fj

fi , ∀j = 1, .., m, lúc này ta kí hiệu

fi = max{f1 , ..., fm }.
Định lý 1.1.9 (Định lý cơ bản Hilbert). Cho vành K[x1 , ...., xn ]. Khi đó
1) Nếu I là ideal của K[x1 , ...., xn ] thì tồn tại các đa thức f1 , ...., fs ∈ K[x1 , ...., xn ]

sao cho I = f1 , ...., fs .
2) Nếu I1 ⊆ I2 ⊆ I3 ⊆ ..... ⊆ In ⊆ .... là dãy tăng các ideal trong K[x1 , ...., xn ],
thì tồn tại số tự nhiên N sao cho IN = IN +1 = IN +2 = ......
Chứng minh: xem [1].

1.2

Thuật chia đa thức trong vành nhiều biến

Ta nói rằng một đa thức f ∈ K[x] được gọi là thu gọn nếu trong biểu diễn tổng
của nó các từ giống nhau xuất hiện không quá một lần.
Định nghĩa 1.2.1. Cho f, g, h ∈ K[x1 , x2 , ..., xn ], với g = 0, ta nói f rút gọn
bước một về h theo g và kí hiệu
g

f →h
nếu và chỉ nếu lp(g) chia hết một hạng tử X khác 0 trong biểu diễn thu gọn của
f và
h=f−

X
g.
lt(g)

Ví dụ 4. Cho f = 6x2 y − x + 4y 3 − 1, g = 2xy + y 3 thuộc Q[x, y]. Dùng thứ
tự từ “lex” với x > y. Ta có lp(g) = xy chia hết X = 6x2 y = 0 (X là hạng tử

7

trong biểu diễn của f ). Khi đó
X
6x2 y
h=f−
g = (6x2 y − x + 4y 3 − 1) −
(2xy + y 3 ) = −3xy 3 − x + 4y 3 − 1.
lt(g)
2xy
g
Do đó f → h.
Ví dụ 5. Cho f = 6x2 y −x+4y 3 −1, g = 2xy +y 3 thuộc Q[x, y]. Dùng thứ tự từ
“deglex” với x > y. Ta có lp(g) = y 3 chia hết X = 4y 3 = 0 (X là hạng tử trong
X
4y 3
biểu diễn của f ), khi đó h = f −
g = (6x2 y − x + 4y 3 − 1) − 3 (2xy + y 3 ) =
lt(g)
y
g
2
6x y − 8xy − x − 1. Do đó f → h.
Nhận xét 1.2.2. Ta có các nhận xét sau:
• Ta nhắc lại, biểu diễn thu gọn của f là một biểu diễn của f mà trong
đó các từ giống nhau chỉ xuất hiện không quá một lần. Chẳng hạn: f =
4x2 y + 2x2 y − x + 4y 3 − 1 là chưa thu gọn.
• Ta có thể thấy h như phần dư của phép chia f cho g. Khi f rút gọn bước
một về h theo g, ta còn nói f chia được cho g.
• Ta có thể làm tiếp quá trình này, tức là sẽ trừ đi những hạng tử của f chia
hết cho lp(g).
Định nghĩa 1.2.3. Cho f, h, f1 , f2 , ..., fs ∈ K[x1 , x2 , ..., xn ], với fi = 0, ∀i =

F

1, ..., s. Đặt F = {f1 , f2 , ..., fs }. Ta nói f rút gọn về h theo F , và kí hiệu là f → h
nếu và chỉ nếu tồn tại dãy con i1 , i2 , ..., it ∈ {1, 2, ..., s} và dãy h1 , h2 , ...., ht−1 ∈
fi

fi

fit−1

fi

fi

1
2
3
t
K[x1 , x2 , ..., xn ] sao cho f → h1 → h2 → .... → ht−1 → h.

Khi f rút gọn về h theo F, ta còn nói f chia được cho F.
Nhận xét 1.2.4. Ta có các nhận xét sau:
8


s

F

• Nếu f → 0 thì f có dạng f =

fi1

fi2

X i fi .
i=1
fi3

fit−1

fi

t
Thật vậy, giả sử f → h1 → h2 → .... → ht−1 → h. Khi đó

t

f = X1 fi 1 + h1 = X1 fi 1 + X2 fi 2 + h2 = ..... =

Xj fi j .
j=1
s

• Điều ngược lại nói chung không đúng. Tức là f có dạng f =

Xi fi không
i=1

F

suy ra f → h. Ta sẽ xem phản ví dụ trong phần S-đa thức (Ví dụ 12, trang
24).
F

• Dựa vào nhận xét trên, nếu f → 0 thì luôn tồn tại g ∈ F sao cho f = g+h.
Ví dụ 6. Cho f1 = yx − y, f2 = y 2 − x ∈ Q[x, y], dùng thứ tự từ deglex với
y > x. Đặt F = {f1 , f2 }, f = y 2 x. Khi đó:
f1
y2x
X
f 1 = y2x −
(yx − y) = y 2
f → y 2 , do f −
lt(f 1 )
yx
2
f
y
X
2
2
2
2→
f 2 = y − 2 (y 2 − x) = x.
x, do y −
y
lt(f 2 )
y
f1

f2

Suy ra: f → y 2 → x.
Định nghĩa 1.2.5. Đa thức r được gọi là rút gọn thích ứng với tập các đa thức
khác 0, F = {f1 , f2 , ..., fs } nếu r = 0 hoặc không có lũy thừa nào trong biểu
diễn của r chia hết cho mỗi lp(f i ), i = 1, ...., s. Nói cách khác r không thể rút
gọn theo F hay r không chia được cho F .
F

Định nghĩa 1.2.6. Nếu f → r và r là rút gọn thích ứng với F thì ta gọi r là
phần dư của f thích ứng với F . Khi đó f còn được gọi là rút gọn toàn phần về
r theo F .
Định nghĩa 1.2.7 (Bảng thuật toán chia đa thức). Cho các đa thức
9


f, f1 , f2 , ..., fs ∈ K[x1 , x2 , ..., xn ], fi = 0, ∀i = 1, ..., s, bằng cách sử dụng
thuật toán chia đa thức sau ta sẽ tìm thấy các thương u1 , u2 , ...., us ∈ K[x1 , x2 , ..., xn ]
và phần dư r ∈ K[x1 , x2 , ..., xn ] thỏa mãn
f = u1 f1 + u2 f2 + .... + us fs + r

INPUT: f, f1 , f2 , ..., fs ∈ K[x1 , x2 , ..., xn ], fi = 0, ∀i = 1, ..., s

OUTPUT u1 , u2 , ...., us , r sao cho f = u1 f1 + u2 f2 + .... + us fs + r và r là rút
gọn thích ứng với {f1 , f2 , ..., fs } và
max{lp(u1 )lp(f1 ),...., lp(us )lp(fs ), lp(r)} = lp(f ).
INITIALIZATION u1 := 0, u2 := 0, ...., us := 0, r := 0, h := f
WHILE h = 0 DO IF tồn tại i sao cho lp(fi ) chia hết lp(h)
THEN chọn i nhỏ nhất sao cho lp(fi ) chia hết lp(h)
lt(h)

u i := u i +
lt(fi )
lt(h)
h := h −
fi
lt(fi )
ELSE
r := r + lt(h)
h := h − lt(h)

Chú thích:
• INITIALIZATION nghĩa là khởi tạo.
• WHILE DO chế độ vòng lặp.

10


Ví dụ 7. Cho f1 = yx − y, f2 = y 2 − x ∈ Q[x, y], dùng thứ tự từ deglex với
y > x. Đặt F = {f1 , f2 }, f = y 2 x.
INITIALIZATION u1 := 0, u2 := 0, r := 0, h := y 2 x
• Phần thứ nhất của vòng lặp WHILE
yx = lp(f1 ) chia hết lp(h) = y 2 x
lt(h)
u 1 := u1 +
=y
lt(f1 )
lt(h)
y2x
2
h := h −

f1 = y x −
(yx − y) = y 2
lt(f1 )
yx
• Phần thứ hai của vòng lặp WHILE
yx = lp(f1 ) không chia hết lp(h) = y 2
y 2 = lp(f2 ) chia hết lp(h) = y 2
lt(h)
u 2 := u 2 +
=1
lt(f2 )
y2 2
lt(h)
2
f2 = y − 2 (y − x) = x
h := h −
lt(f2 )
y
• Phần thứ ba của vòng lặp WHILE
yx = lp(f1 ) không chia hết lp(h) = x
y 2 = lp(f2 ) không chia hết lp(h) = x
r := r + lt(h) = x
h := h − lt(h) = 0
F

• Vòng lặp dừng (vì h = 0). Khi đó ta có : f → x và f = yf1 + f2 + x.
Nhận xét 1.2.8. Cơ sở của thuật toán trên dựa trên định lý sau.
Định lý 1.2.9. Cho hệ các đa thức khác 0, F = {f1 , f2 , ..., fs } và f ∈ K[x1 , x2 , ..., xn ].
Bảng thuật toán 1.2.7 chỉ ra có các đa thức u1 , u2 , ...., us , r ∈ K[x1 , x2 , ..., xn ] sao
11

cho
f = u1 f1 + u2 f2 + .... + us fs + r
với r là rút gọn thích ứng với F và lp(f ) = max max {lp(ui )lp(fi )}, lp(r) .
1≤i≤s

Chứng minh: Đầu tiên ta chứng tỏ thuật toán trên là dừng. Ở mỗi giai đoạn
của thuật toán, hạng tử dẫn đầu của h bị trừ đi cho đến khi không trừ được
nữa. Vì

 hi+1 = hi − lt(hi ) + (các hạng tử bậc thấp hơn)

hi+1 = hi − lt(hi )
Suy ra lp(hi+1 ) < lp(hi ).
Do thứ tự từ là thứ tự tốt nên dãy h1 , h2 , ..., hi , ... phải dừng.
Trong các giai đoạn ta đều có lp(h) ≤ lp(f ).
lt(h)
lp(f )
Với mỗi i, ui = ui +
, dẫn đến lp(ui ) ≤
. Suy ra lp(ui )lp(f1 ) ≤ lp(f ).
lt(fi )
lp(f1 )
Hơn nữa r = r + lt(h). Do đó lp(r) ≤ lt(h) ≤ lt(f ).
Nhận xét 1.2.10. Ta có các nhận xét sau:
F

• Theo định lý trên, suy ra f →r.
+

• Theo định lý trên, ta có f − r ∈ I = f1 , ..., fs .
• Nếu r = 0 thì f ∈ I = f1 , ..., fs .
• Điều ngược lại không đúng, tức là, nếu f ∈ I = f1 , ..., fs thì r chưa chắc
bằng 0. Thông qua ví dụ sau:

12


Ví dụ 8. Xét f = y 2 x − x, f1 = xy − y, f2 = y 2 − x thuộc Q[x, y].
f1

f2

Bằng cách chia như sau: f → y 2 −x → 0 . Ta có f = yf1 +f2 , dẫn đến f ∈ f1 , f2 .
f2

Nhưng ta có thể chia bằng cách khác: f → x2 − x, và x2 − x là rút gọn thích
ứng với {f1 , f2 }, suy ra x2 − x là phần dư của phép chia f cho {f1 , f2 }, nhưng
x2 − x = 0 .
Nhận xét 1.2.11. Ta có các nhận xét sau:
• Từ ví dụ này ta rút ra, có nhiều cách chia một đa thức f cho một hệ đa
thức {f1 , f2 , ..., fs }. (sỡ dĩ nhiều cách như vậy là do việc chọn thứ tự từ
hoặc việc chọn các đa thức {f1 , f2 , ..., fs } khi chia, vì có trường hợp các
lp (fi ) đều chia hết cho các hạng tử nào đó của f ).
• Như vậy mỗi cách chia f cho một hệ đa thức {f1 , f2 , ..., fs } có phần dư
chưa chắc giống nhau. Câu hỏi đặt ra là hệ {f1 , f2 , ..., fs } phải có tính chất
gì thì phần dư là giống nhau ? Câu trả lời là hệ {f1 , f2 , ..., fs } phải là cơ
sở Gr¨obner, vậy ngay bây giờ ta sẽ ngiên cứu cơ sở Gr¨obner.

1.3

Cơ sở Gr¨
obner

Định nghĩa 1.3.1. Cho tập các đa thức khác 0, G = {g1 , ...., gt } chứa trong
ideal I. G được gọi là cơ sở Gr¨obner của I nếu và chỉ nếu mọi f ∈ I mà f = 0
đều tồn tại gi ∈ G sao cho lp(gi ) chia hết lp(f ).
Nhận xét 1.3.2. Ta có các nhận xét sau:
• G là cơ sở Gr¨obner của I thì mọi đa thức khác 0 trong I đều rút gọn được
với G (ta có thể hiểu là chia được cho G).
13


• G là cơ sở Gr¨obner của I thì G phải chứa tất cả các đa thức nhỏ nhất của
I (theo một thứ tự từ nào đó).
• Chúng ta không chắc sự tồn tại của cơ sở Gr¨obner trong định nghĩa trên.
• Cho S ⊂ K[x1 , ...., xn ], ta định nghĩa ideal các hạng tử dẫn đầu của S là
ideal có dạng:
Lt(S) = lt(s) |s ∈ S
Định lý 1.3.3 (3 đặc trưng của cơ sở Gr¨obner). Cho I là một ideal khác 0 của
K[x1 , ...., xn ]. Tập các đa thức khác 0, G = {g1 , ...., gt } ⊂ I. Khi đó, bốn điều
sau tương đương nhau:
(i) G là cơ sở Gr¨obner của I.
G

(ii) f ∈ I nếu và chỉ nếu f −
→+ 0.
t

(iii) f ∈ I nếu và chỉ nếu f =

hi gi và lp(f ) = max {lp(hi )lp(gi )}.
1≤i≤t

i=1

(iv) Lt(G) = Lt(I).
Chứng minh:
(i) ⇒ (ii). Theo Định lý 1.2.9, tồn tại r ∈ K[x1 , ...., xn] là rút gọn thích ứng với
G

G sao cho f −
→+ r. Do đó f − r ∈ I. Nên f ∈ I khi và chỉ khi r ∈ I.
G

Nếu r = 0 thì f −
→+ 0.
Nếu r = 0, do f ∈ I nên r ∈ I. Từ (i), ta có tồn tại gi ∈ G sao cho lp(gi ) chia
hết lp(r), điều này mâu thuẫn với r là rút gọn thích ứng với G. Vậy r = 0 thì
G

f−
→+ 0.
14


G

(ii) ⇒ (iii). Cho f ∈ I. Từ (ii) suy ra f −

→+ 0. Từ Định lý 1.2.9 suy ra (iii).
(iii) ⇒ (iv). Ta có Lt(G) ⊂ Lt(I). Ngược lại, cần chứng minh mọi f ∈ I suy
ra lt(f ) ∈ Lt(G). Theo giả thiết (iii), lp(f ) = max {lp(hi )lp(gi )}, suy ra tồn tại
1≤i≤t

j ∈ {1, ..., t} sao cho lp(f ) = lp(hj )lp(gj ). Do đó lp(f ) = lp(hj )lp(gj ) ∈ Lt(G).
(iv) ⇒ (i). Cho f ∈ I, f = 0, thì lt(f ) ∈ Lt(G) và lt(f ) = 0. Suy ra
t

hi lt(gi ), với các hi ∈ K[x1 , ...., xn],

lt(f ) =
i=1

có vế trái (VT) là một đơn thức khác 0, nên muốn VT bằng vế phải (VP) thì
khi khai triễn VP, các hạng tử thu gọn khác bậc của VT đều bằng không, chỉ
còn lại tổng các đơn thức khác 0 có bậc bằng nhau. Khi đó lt(f ) có dạng (không
mất tổng quát hoặc có thể đánh số các gi lại)
s
i

ai .xα .lt(gi ), s ≤ t, ai ∈ K, ai = 0

lt(f ) =
i=1
α1

s

i

i

i

với x .lp(g1 ) = .... = xα .lp(gs ) và xα = x1 α 1 .....xn α n ∈ T n , i = 1, s.
1

s

Suy ra xα .lp(g1 ) = .... = xα .lp(gs ) = lp(f ).
Do đó chia hết cho các lp(g1 ), ...., lp(gs ) ⊂ { lp(g1 ), ....., lp(gt )}.
Suy ra G là cơ sở Gr¨obner của I.
Hệ quả 1.3.4. Nếu G = {g1 , ...., gt } là cơ sở Gr¨
obner của ideal I thì I =
g1 , ...., gt .
Chứng minh:
Ta có g1 , ...., gt ⊂ I, (do gi ∈ I, ∀ i).
t

Lấy f ∈ I. Do G = {g1 , ...., gt } là cơ sở Gr¨obner của ideal I, nên f =

hi gi .
i=1

Suy ra f ∈ g1 , ...., gt .
Bổ đề 1.3.5. Cho I là một ideal sinh bởi tập S gồm các hạng tử khác 0, và
15

f ∈ K[x1 , ...., xn ]. Khi đó, f ∈ I nếu và chỉ nếu mỗi hạng tử X trong biểu diễn
của f đều tồn tại Y ∈ S sao cho Y chia hết X. Hơn nữa tồn tại tập con hữu
hạn S0 của S sao cho I = S0 .
Chứng minh:
s

(⇒) Nếu f ∈ I, thì f =

hi Xi với hi ∈ K[x1 , ...., xn ], Xi ∈ S. Lấy Y là các
i=1

Xi ta được điều phải chứng minh.
s

Xi và Xi chia hết cho Yi , với Yi ∈ S, ∀i = 1, s, thì Xi ∈

(⇐) Nếu f =
i=1

S, ∀i = 1, s, và do đó f ∈ S.
Theo Định lý Hilbert, ta có I là hữu hạn sinh, tức là I = S0 , với S0 là hữu
hạn phần tử. Không mất tổng quát có thể giả sử các phần tử của S0 đều là các
đơn thức.
Vì mỗi phần tử của S0 đều thuộc I, nên các phần tử của S0 đều chia hết cho
Y tương ứng nào đó của S. Như vậy mỗi phần tử của S0 sẽ có ít nhất một Y
trong S thõa tính chất trên, và ta chỉ lấy một Y duy nhất ứng với một phần tử
của S0 , đặt S0 là tập các Y như vậy.
Vì S0 hữu hạn nên S0 cũng hữu hạn và dĩ nhiên S0 ⊂ S, hơn nữa S0 = S0 =
I.
Hệ quả 1.3.6. Mỗi ideal I khác 0 của K[x1 , ...., xn ] đều có cơ sở Gr¨

obner.
Chứng minh:
Xét ideal Lt(I) sinh bởi chính nó là Lt(I) gồm các hạng tử khác 0, theo Bổ đề
1.3.5 thì Lt(I) có hệ sinh hữu hạn gồm các hạng tử có dạng {lt(g1 ),...., lt(gt )},
với g1 , ...., gt ∈ I. Đặt G = {g1 , ...., gt }, ta có Lt(G) = Lt(I) và do đó G là cơ sở
16


Gr¨obner của I.
Nhận xét 1.3.7. Hệ quả trên đã khẳng định sử tồn tại của cơ sở Gr¨obner trong
mọi ideal khác 0.
Định nghĩa 1.3.8. Ta nói tập con G = {g1 , ...., gt } của K[x1 , ...., xn ] là cơ sở
Gr¨obner nếu và chỉ nếu G là cơ sở Gr¨obner của ideal G .
Sau đây là một đặc trưng thứ 4 của cơ sở Gr¨obner.
Định lý 1.3.9 (đặc trưng thứ 4 của cơ sở Gr¨obner). Cho G = {g1 , ...., gt } là
tập các đa thức khác 0 trong K[x1 , ...., xn ]. Khi đó G là một cơ sở Gr¨
obner nếu
và chỉ nếu mọi đa thức f ∈ K[x1 , ...., xn ] chia nhiều cách cho G đều có phần dư
là duy nhất.
Chứng minh:
G

G

(⇒) Giả sử G là một cơ sở Gr¨obner. Nếu f −
→+ r1 và f −
→+ r2 , với r1 , r2 là các
rút gọn thích ứng với G, ta có thể giả sử r1 , r2 = 0. Ta có f − r1 , f − r2 ∈ G
suy ra r1 − r2 ∈ G. Vì r1 , r2 là các rút gọn thích ứng với G nên không có hạng
tử nào trong r1 và r2 chia hết cho các lp(gi ), ∀i = 1, t, do vậy r1 − r2 = 0 hoặc

không có hạng tử nào trong r1 − r2 chia hết cho các lp(gi ), ∀i = 1, t. Nhưng do
r1 − r2 ∈ G, nên r1 − r2 = 0. Trong trường hợp có một phần dư bằng 0, giả
sử r1 = 0, làm tương tự quá trình trên ta cũng suy ra r2 = 0. Vậy r1 = r2 , hay
phần dư là duy nhất.
Ta có thể chứng minh cách khác như sau (dùng phản chứng): Giả sử G là một
G

G

cơ sở Gr¨obner. Nếu f −
→+ r1 và f −
→+ r2 , với r1 , r2 là các rút gọn thích ứng với G,
G

G

giả sử r1 = r2 . Do f −
→+ r1 và f −
→+ r2 nên tồn tại g1 , g2 ∈ G sao cho f = g1 + r1
17


và f = g2 + r2 . Suy ra r1 − r2 = g1 − g2 ∈ G . Mà G là cơ sở Gr¨obner suy
ra tồn tại g ∈ G sao cho lp(g) chia hết cho lp(r1 − r2 ). Do đó lp(g) chia hết
T (r1 ) ∪ T (r2 ). Điều này suy ra tồn tại một hạng tử trong biểu diễn của r1 hoặc
r2 chia hết cho lp(g). Điều này mâu thuẩn với r1 , r2 là các rút gọn thích ứng
với G.
(⇐) Giả sử phần dư trong định lý là duy nhất. Ta sẽ chứng minh đặc trưng thứ
hai của cơ sở Gr¨obner.
G

Giả sử f ∈ G . Giả sử có một cách chia bất kì nào đó mà kết quả là: f −
→+ r,
với r là các rút gọn thích ứng với G.
Ta cần bổ đề sau:
G

Bổ đề 1.3.10. Cho g ∈ K[x1 , ...., xn ] và g −
→+ r, với r là rút gọn thích ứng với
G. Khi đó với mọi c ∈ K, c = 0 và với mọi X ∈ T n là một tích các lũy thừa, ta
G

đều có: g − cXgi −
→+ r, với mỗi i ∈ {1, 2, ..., t}.
s

Nếu Bổ đề đúng, do f ∈ G , nên f =
Áp dụng Bổ đề với f = g, ta có f −

cv Xv giv , s ≤ t.

v=1
G
c1 X1 gi1 −
→+ r.
G

Lại áp dụng Bổ đề với f − c1 X1 gi1 = g, ta có f − c1 X1 gi1 − c2 X2 gi2 −
→+ r.
s

G

Áp dụng Bổ đề nhiều lần ta được f −

cv Xv giv −
→+ r.
v=1

G

Suy ra 0−
→+ r.
G

Suy ra r = 0. Suy ra f −
→+ 0. Suy ra G là cơ sở Gr¨obner.
Vậy ta cần chứng minh Bổ đề.
Gọi d ∈ K sao cho d.lc(gi ) là hệ số trước lũy thừa X.lp(gi ) trong g (hệ số này
có thể tồn tại hoặc không).
18


• Nếu d = 0, suy ra hệ số trước X.lp(gi ) trong g − cX.gi là −c.lc(gi ) = 0, nên
tồn tại hạng tử Y = −cX.lt(gi ) = 0 trong biểu diễn của g − cX.gi sao cho
Y
−cX.lt(gi )
(g − cX.gi ) −
gi = (g − cX.gi ) −
gi = g.
lt(gi )

lt(gi )
gi
G
Do đó (g − cX.gi ) −
→ g−
→+ r.
G

• Nếu d = c, giả sử (g−cX.gi )−
→+ r1 . Vì d = c, nên d = 0, nên tồn tại hạng tử Y =
Y
gi
G
dX.lt(gi ) = 0 trong biểu diễn của g sao cho g −
→g−
gi = g − cXgi −
→+ r1
lt(gi )
G
G
Mà g −
→+ r, theo tính duy nhất của r, suy ra r = r1 ⇒ (g − cX.gi )−
→+ r.
• Nếu d = 0 và d = c, đặt h = g − dXgi , khi đó hệ số của X.lp(gi ) trong h bằng
0. Do d = 0 nên tồn tại hạng tử Y = dX.lt(gi ) = 0 trong biểu diễn của g sao
Y
gi
gi = g − dXgi = h.
cho g −
→g−

lt(gi )
Do d − c = 0 nên nên tồn tại hạng tử Y = (d − c)X.lt(gi ) = 0 trong biểu
Y
gi
diễn của (g − cX.gi ) sao cho g − cXgi −
→ (g − cXgi ) −
gi = (g − cXgi ) −
lt(gi )
(d − c)Xlt(gi )
gi = g − dXgi = h.
lt(gi )
gi
G
G
Nếu h−
→+ r2 , với r2 là rút gọn thích ứng với G, ta có g −
→ h−
→+ r2 .
G

G

Mà g −
→+ r, theo tính duy nhất của r, suy ra r = r2 . Vậy nên (g − cX.gi )−
→+ r.
Ví dụ 9 (không phải hệ nào cũng là cơ sở Gr¨obner). Quay lại Ví dụ 8
Xét hệ F = {f1 , f2 }, với f1 = xy − y, f2 = y 2 − x. Lấy f = y 2 x − x.
f1

f2

F

Bằng cách chia như sau: f −
→ y2 − x −
→ 0. Suy ra f −
→+ 0.
f2

Bằng cách chia khác: f −
→ x2 − x, và x2 − x là rút gọn thích ứng với {f1 , f2 },
F

suy ra x2 − x là phần dư của phép chia f cho {f1 , f2 }. Suy ra f −
→+ x2 − x.
Nhưng vì x2 − x = 0, nên hai phần dư khác nhau, theo Định lý 1.3.9 thì hệ
F = {f1 , f2 } không phải là cơ sở Gr¨obner.

19


Ví dụ 10 (cơ sở Gr¨obner phụ thuộc vào thứ tự từ). Một hệ là cơ sở Gr¨obner
của thứ tự từ này nhưng chưa chắc là cơ sở Gr¨obner của một thứ tự từ khác.
Cho hệ G = {g1 , g2 }, với g1 = z + x, g2 = y − x ∈ Q[x, y, z]. Đặt I = g1 , g2 .
Xét thứ tự từ “lex”, với x < y < z. Ta chứng minh G là cơ sở Gr¨obner của I.
Giả sử ngược lại, khi đó tồn tại f ∈ I sao cho lt(f ) ∈
/ lt(g1 ), lt(g2 ) = z, y .
Suy ra z và y đều không chia hết lt(f ), do đó lt(f ) không chứa z và lt(f ) không
chứa y, do thứ tự từ đang dùng là “lex”, nên các hạng tử trong f thấp hơn lt(f )
cũng không chứa z và không chứa y. Suy ra f ∈ Q[x].

Lại do f ∈ I = g1 , g2 , nên f có dạng: f = (z + x)h1 + (y − x)h2 , với h1 , h2 ∈
Q[x, y, z].
Vì y không có trong biểu diễn của f , nên khi khai triễn f thì các hạng tử
chứa y sẽ bị triệt tiêu, do đó sự có mặt của y trong công thức trên là không
quan trọng, vì vậy ta có thể cho y = x. Khi đó f = (z + x)h1 (x, x, z), suy ra
z + x chia hết f , và điều này mâu thuẩn với f là hàm một biến theo x. Suy
ra lt(f ) ∈ lt(g1 ), lt(g2 ) , đúng với mọi f ∈ I. Do vậy G = {g1 , g2 } là cơ sở
Gr¨obner của I.
Xét thứ tự từ “lex”, với x > y > z. Khi đó G còn là cơ sở Gr¨obner nữa không ?
x
x
g1
Ta lấy f = x. Khi đó f −
→f−
g1 = x − (z + x) = −z và −z không chia
lt(g1 )
x
hết cho lt(g1 ) = x hơn nữa −z cũng không chia hết cho lt(g2 ) = x. Vậy nên −z
G

là rút gọn thích ứng với G, hay −z là phần dư của phép chia f −
→+ − z. Mặt
x
x
g2
khác f −
→f−
g2 = x −
(y − x) = y và y không chia hết cho lt(g1 ) = x
lt(g2 )

−x
và y không chia hết cho lt(g2 ) = x, nên y là rút gọn thích ứng với G, hay y là
G

phần dư của phép chia f −
→+ y.
20


Và ta thấy có hai phần dư khác nhau là −z = y. Theo Định Lý 1.3.9, suy ra G
không là cơ sở Gr¨obner.

1.4

Thuật toán Buchberger

Thuật toán Buchberger là một thuật toán để tìm cơ sở Gr¨obner.
Lấy xα = xα1 1 xα2 2 ....xαnn , xβ = xβ1 1 xβ2 2 ....xβnn ∈ T n , với αi , βi ∈ N, i = 1, ..., n.
Đặt L = xγ1 1 xγ2 2 ....xnγn , với γi = max{αi , βi } , i = 1, ..., n.
Khi đó, L được gọi là bội chung nhỏ nhất của xα và xβ , kí hiệu là L =
lcm xα , xβ .
Định nghĩa 1.4.1 (S-đa thức). Cho 0 = f, g ∈ K[x1 , ...., xn ].
Đặt L = lcm{lp(f ), lp(g)}. Khi đó đa thức
S(f, g) =

L
L
f−
g
lt(f )

lt(g)

được gọi là S-đa thức của f và g.
Nhận xét 1.4.2. Các S-đa thức của hai đa thức có tính hủy đi hạng tử dẫn
đầu của hai thức đó.
Ví dụ 11. f = 2xy − y, g = 3y 2 − x ∈ Q[x, y]. Xét thứ tự từ deglex với y > x.
Khi đó: lp(f ) = yx, lp(g) = y 2 , suy
y2x
y2x
f − 2g =
Do đó S(f, g) =
2xy
3y

ra L = y 2 x.
1
1
1
1
yf − xg = − y 2 + x2 .
2
3
2
3

Bổ đề 1.4.3. Cho f1 , ..., fs ∈ K[x1 , ...., xn ] sao cho lp(f1 ) = .... = lp(fs ) =
s

ci fi , với ci ∈ K, i = 1, ..., s. Nếu lp(f ) < X, thì f là tổ

X = 0. Đặt f =
i=1

hợp tuyến tính với hệ số thuộc K của các S(fi , fj ), 1 ≤ i < j ≤ s.
21


Chứng minh:
Với mỗi i = 1, ..., s, ta viết fi = ai X + (các hạng tử bậc thấp hơn), ai ∈ K.
s

Theo giả thiết lp(f ) < X nên

ci ai = 0. Theo định nghĩa, ta có S(fi , fj ) =
i=1

1
1
fi − fj , do lp(fi ) = lp(fj ) = X. Khi đó
ai
aj
f = c1 f1 + ... + cs fs
1
1
= c1 a1
f1 + ... + cs as
fs
a1
as
1

1
1
1
f1 − f2 + (c1 a1 + c2 a2 )
f2 − f3 + .....
= c1 a1
a1
a2
a2
a3
1
1
1
+(c1 a1 + .... + cs−1 as−1 )
fs−1 − fs + (c1 a1 + .... + cs as ) fs
as−1
as
as
0

= c1 a1 S(f1 , f2 ) + (c1 a1 + c2 a2 )S(f2 , f3 ) + .... + (c1 a1 + ... + cs−1 as−1 )S(fs−1 , fs ).
Định lý 1.4.4 (đặc trưng thứ 5 của cơ sở Gr¨obner có tên đặc trưng Buchberger).
Cho G = {g1 ,..., gt } là tập các đa thức khác 0 trong K[x1 , ...., xn ]. G là cơ sở
Gr¨
obner của ideal I = g1 ,..., gt nếu và chỉ nếu với mọi i = j thì
G

S(gi , gj )−
→+ 0.
Chứng minh:

L
L
gi −
gj , nên S(gi , gj ) ∈ I, mà do
lt(gi )
lt(gj )
G là cơ sở Gr¨obner của ideal I = g1 ,..., gt , nên theo Định lý 1.3.3 (ii) (đặc

(⇒) Với mọi i = j. Do S(gi , gj ) =

G

trưng thứ nhất cơ sở Gr¨obner), suy ra S(gi , gj )−
→+ 0.
G

(⇐) Giả sử rằng S(gi , gj )−
→+ 0, với mọi i = j. Ta chứng minh đặc trưng
thứ hai của cơ sở Gr¨obner (Định lý 1.3.3 (iii)). Lấy f ∈ I = g1 ,..., gt , khi
đó f có nhiều cách viết thành tổ hợp tuyến tính của các gi , ta chọn một cách
t

hi gi sao cho X = max {lp(hi ).lp(gi )} thấp nhất trong tất cả các

viết f =
i=1

1≤i≤t

22