VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER

Mục lục
Lời

nói

đầu

3
1

Thứ

tự

trên

các

đơn

thức

của

vành

4
2

Thuật

toán

chia

trong

vành

6
3

Iđêan

khởi

đầu

và

cơ

sở

Groebner

9
4 Thuật toán Buchberger


15

5 Một số cải tiến Thuật toán Buchberger

20

Kết luận

40

Tài liệu tham khảo

41

1


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER

Lời nói đầu
Lý thuyết cơ sở Groebner là hạt nhân của việc thực hiện được tính toán hình
thức bằng máy tính trong Đại số giao hoán và Hình học đại số. Một tiêu chuẩn khá khả
dụng để tìm một cơ sở Groebner của một iđêan chính là thuật toán Buchberger. Lý
thuyết này đã được nhà toán học người Áo Bruno Buchberger đưa ra trong luận án tiến
sĩ của mình vào năm 1965.
Việc tìm cơ sở Groebner xuất hiện trong hầu hết các thuật toán liên quan đến
đa thức ( trên trường số). Vì vậy việc tìm ra một thuật toán hữu hiệu giải bài toán đó là
quan trọng. Cho đến nay thuật toán Buchberger vẫn là thuật toán duy nhất. Tuy nhiên
có rất nhiều cách cải tiến thuật toán này về phương diện lý thuyết cũng như về phương
diện lập trình nhằm giảm bớt đi khối lượng cũng như thời gian tính toán.

Luận văn này sẽ trình bày một số khái niệm cơ bản của cơ sở Groebner cũng
như thuật toán Buchberger. Từ đó sẽ trình bày một số cải tiến của thuật toán
Buchberger. Hy vọng rằng luận văn này sẽ hữu ích cho những ai quan tâm đến thuật
toán Buchberger. Mặc dù đã hết sức cố gắng nhưng không thể tránh khỏi những thiếu
sót kính mong quý thầy cô và bạn đọc thông cảm cũng như đóng góp ý kiến để hoàn
thiện hơn nội dung tài liệu.
Cuối cùng tôi xin gửi lời cảm ơn chân thành đến giảng viên - Tiến sĩ Ngô Lâm
Xuân Châu đã tận tình chỉ dạy, giúp đỡ, chỉnh sửa nội dung và hướng dẫn cách trình
bày để tôi có thể hoàn thành luận văn này. Đồng thời tôi xin chân thành cảm ơn quý
thầy cô khoa Toán trường Đại học Quy Nhơn đã tận tình dìu dắt, giảng dạy chúng tôi
trong suốt khoảng thời gian qua.
2


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Quy Nhơn, tháng 6 năm 2014
Sinh viên thực hiện

1 Thứ tự trên các đơn thức của vành
Định nghĩa 1.1. ( Thứ tự)
Cho là một tập hợp khác rỗng. Quan hệ (hai ngôi) là một quan hệ thứ tự ( bộ
phận) nếu nó thỏa mãn các điều kiện sau đây đối với mọi :
(i) ( tính chất phản xạ),
(ii) Nếu và thì ( tính chất bắc cầu),
(iii) Nếu và thì ( tính chất phản đối xứng).
Định nghĩa 1.2. ( Thứ tự từ)
Một thứ tự từ trên là một quan hệ trên ( hoặc tương đương với bất kỳ quan hệ
nào trên tập các đơn thức , ) thỏa mãn:
(i) là một thứ tự toàn phần trên ,
(ii) Nếu và thì ,

(iii) là một thứ tự tốt trên , nghĩa là mọi tập hợp con khác rỗng của đều có phần tử
nhỏ nhất.
Bổ đề 1.1. Một quan hệ thứ tự trên ( tương ứng trên tập các đơn thức) là một thứ tự
tốt khi và chỉ khi mọi dãy giảm chặt trong ( tương ứng dãy đơn thức giảm) sẽ dừng
( sau hữu hạn phần tử).
Định nghĩa 1.3. Thứ tự từ điển ( kí hiệu , nói gọn là lex)
Cho ,

. Ta nói

nếu trong véctơ hiệu ( , giá trị đầu tiên khác tính từ trái là

dương. Ta viết nếu .
Định nghĩa 1.4. Thứ tự từ điển phân bậc ( kí hiệu , nói gọn là thứ tự )
Cho . Ta nói nếu thỏa mãn một trong hai điều kiện:

3


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
hoặc .
Định nghĩa 1.5. Thứ tự từ điển ngược ( kí hiệu , nói gọn là thứ tự )
Cho . Ta nói nếu thỏa mãn một trong hai điều kiện:
hoặc
Định nghĩa 1.6. Cho là đa thức khác trên và là một thứ tự từ. Từ khởi đầu của , kí
hiệu , là từ lớn nhất theo quan hệ . Nếu , thì gọi là hệ số đầu của và gọi là đơn thức
đầu của đối với thứ tự từ
Khi đó .
Định nghĩa 1.7. Cho là hai đa thức khác và là một thứ tự từ. Đa bậc của đa thức ,
viết gọn là , được xác định là

.

2 Thuật toán chia trong vành

4


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Định lí 2.1. Cố định một thứ tự từ trên và cho là một tập hợp gồm đa thức trong .
Với mọi có thể viết được dưới dạng

trong đó , và hoặc hoặc là một tổ hợp tuyến tính của các đơn thức với hệ số trên và
không có đơn thức nào của chia hết cho bất kì . Khi đó được gọi là phần dư của khi
chia cho . Hơn nữa, nếu thì multideg() multideg(.
Thuật toán chia đa thức
INPUT:
OUTPUT:

WHILE DO

Chiahet false
WHILE AND Chiahet = false DO
IF THEN

Chiahet true
ELSE

IF Chiahet = false THEN

Chứng minh

Trước hết ta cần chỉ ra rằng
5


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
,

(2.1)

luôn đúng tại mỗi bước. Theo cách đặt ban đầu thì (2.1) hiển nhiên đúng. Giả sử rằng
(2.1) đúng tại một bước nào đó của thuật toán. Nếu bước tiếp theo là bước phép chia,
thì tồn tại chia hết , ta có đẳng thức

chứng tỏ không thay đổi, và vì các biến còn lại cũng không thay đổi nên ( 2.1) đúng;
nếu bước tiếp theo là bước phần dư ( tức không thực hiện được phép chia) thì và thay
đổi, nhưng tổng không thay đổi. Vậy ( 2.1) được bảo toàn.
Tiếp theo ta cần chứng tỏ thuật toán dừng. Chú ý là mỗi lần xác định lại biến ,
hoặc bị triệt tiêu, hoặc nó trở thành . Thật vậy, giả sử rằng qua một bước phép chia,
được xác định là . Khi đó
,

(2.2)

vậy và có cùng từ khởi đầu, khi đó hiệu của chúng sẽ triệt tiêu các từ khởi đầu này
khi , suy ra . Trường hợp qua một bước phần dư, được xác định lại là , rõ ràng khi .
Vậy theo thuật toán, phải giảm theo thứ tự đã chọn, nếu thuật toán không kết thúc, thì
ta sẽ có một dãy giảm vô hạn, điều này mâu thuẫn với tính sắp thứ tự tốt của thứ tự .
Do đó phải xảy ra cuối cùng, và thuật toán sẽ dừng sau hữu hạn bước.
Bây giờ ta đi kiểm tra kết quả của thuật toán. Vì thuật toán dừng khi , nên
( 2.1) trở thành . Vì hạng tử được cộng vào chỉ khi chúng không chia hết cho , nên kết

quả thu được có thuộc tính mong muốn khi thuật toán kết thúc. Hơn nữa, vì mỗi hạng
tử trong có dạng với mọi giá trị biến , thuật toán bắt đầu với , và theo chứng minh
trên, giảm, do vậy . Khi đó theo Đẳng thức (2.2) ta suy ra
.



6


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER

3 Iđêan khởi đầu và cơ sở Groebner
Định nghĩa 3.1. Cho là một iđêan khác , là một thứ tự từ.
Iđêan khởi đầu của kí hiệu , là iđêan sinh bởi tất cả các từ khởi đầu của các phần tử
thuộc , nghĩa là
.

7


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Định nghĩa 3.2. Iđêan được gọi là iđêan đơn thức nếu nó được sinh ra bởi các đơn
thức. Tức là, tồn tại tập hợp ( có thể vô hạn) sao cho bao gồm các đa thức có tổng
hữu hạn dạng , trong đó . Kí hiệu là .
Bổ đề 3.1. Cho là một iđêan đơn thức. Khi đó với nào đó.
Bổ đề 3.2. Cho là một iđêan đơn thức và . Các điều kiện sau là tương đương:
(i) .
(ii) Mọi từ của thuộc .
(iii) là tổ hợp tuyến tính trên của các đơn thức thuộc .

Mệnh đề 3.1. Cho là một tập hợp các đa thức khác , là một thứ tự từ. là iđêan sinh
bởi các từ khởi đầu của các đa thức trong . Khi đó là một iđêan đơn thức.
Định lí 3.1. ( Bổ đề Dickson)
Mọi iđêan đơn thức của vành đều có thể viết được dưới dạng , trong đó . Nói
riêng là hữu hạn sinh.
Hệ quả 3.1. Cho là iđêan khác . Khi đó tồn tại sao cho
.
Định lí 3.2. ( Định lí Hilbert về cơ sở)
Mọi iđêan của vành đều có tập sinh hữu hạn, tức là tồn tại sao cho .
Mệnh

đề

3.2.

Cho

hệ

cho

đa

thức

sao

. Khi đó, đa thức dư của phép chia

mọi đa thức cho hệ được xác định duy nhất thuộc và thỏa mãn:

• Không có từ nào của chia hết cho một trong các từ khởi đầu ).
•
Kết quả trên không phụ thuộc vào thứ tự các đa thức chia trong hệ đa thức .
Chứng minh
Ta có thể suy ra trực tiếp kết quả trên từ Thuật toán chia đa thức. Bây giờ ta chỉ
cần chứng minh tính duy nhất.
8


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Giả sử và là hai đa thức dư khác nhau, tức là tồn tại và sao cho
+
và không có từ nào của chia hết cho . Xét iđêan , ta có
.
Giả sử . Khi đó . Theo Bổ đề 3.1, có từ khởi đầu chia hết cho một trong các đơn thức .
Điều này mâu thuẫn với tính chất phần dư của và .
Vậy hay .



Định nghĩa 3.3. Cơ sở Groebner
Cố định một thứ tự từ. Tập hợp con hữu hạn của iđêan được gọi là một cơ sở
Groebner ( hay cơ sở chuẩn tắc) nếu
.
Một cách tương đương nhưng cung cấp nhiều thông tin hơn, tập hợp là cơ sở
Groebner của khi và chỉ khi từ khởi đầu của bất kì phần tử nào của cũng chia hết cho
nào đó, với .
Tuy nhiên trong định nghĩa trên chưa thấy rõ liệu bản thân có phải là cơ sở của
hay không? Từ định lí Hilbert về cơ sở cho ta kết quả
Hệ quả 3.2. Cố định một thứ tự từ. Khi đó mọi iđêan đều có cơ sở Groebner. Hơn

nữa, cơ sở Groebner của là cơ sở của .
Điều ngược lại nói chung là không đúng, tức một cơ sở của chưa chắc là một
cơ sở Groebner.
Chứng minh
Theo Bổ đề Dickson, tồn tại sao cho . Bây giờ ta cần chứng minh .
Ta luôn có vì . Do đó ta chỉ cần chứng minh . Thật vậy:
Lấy bất kì . Áp dụng thuật toán chia cho ta được
trong đó , và không có từ nào của chia hết cho bất kì các .
9


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Khi đó
.
Nếu thì . Khi đó sẽ chia hết cho ít nhất một trong các . Điều này mâu thuẫn, do đó .
Tức là,
Do vậy hay là .
Điều ngược lại nói chung không đúng. Ví dụ sau sẽ chứng tỏ điều đó.
Ví dụ 3.1. Cho , trong đó , . Sử dụng thứ tự trên các đơn thức của vành . Khi đó, là
một cơ sở của iđêan .
Hơn nữa, . Nhưng không chia hết cho cả và , vì thế .
Do vậy không phải là cơ sở Groebner của .



Hệ quả 3.3. Cho là một cơ sở Groebner của iđêan và cho . Khi đó khi và chỉ khi
phần dư của phép chia của cho bằng .
Chứng minh
Giả sử thực hiện phép chia của cho ta được
,

với và không có từ nào của chia hết cho một trong các .
Khi thì dễ thấy .
Ngược lại nếu , thì theo Mệnh đề 3.2 thì . Tức là chính là phần dư của phép chia của
cho .



Bổ đề 3.3. Cho là một cơ sở Groebner của iđêan đa thức . Cho đa thức sao cho . Khi
đó cũng là một cơ sở Groebner của .
Định nghĩa 3.4. Cơ sở Groebner tối tiểu
Cơ sở Groebner tối tiểu của iđêan là cơ sở Groebner của sao cho:
(i)
(ii) .
10


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Định nghĩa 3.5. Cơ sở Groebner rút gọn
Cơ sở Groebner rút gọn của iđêan là một cơ sở Groebner của sao cho:
(i)
(ii) , không có từ nào của nằm trong .
Mệnh đề 3.3. Cho là một iđêan. Khi đó có duy nhất một cơ sở Groebner rút gọn với
mọi thứ tự từ cho trước.
Chứng minh
Cho là một cơ sở Groebner cực tiểu của Ta nói là rút gọn trong nếu không có
từ nào của nằm trong . Mục đích của ta là đi thay đổi cho tới khi tất cả các phần tử
của nó đều là rút gọn.
Nhận xét rằng nếu là rút gọn trong , thì cũng rút gọn trong bất kì cơ sở
Groebner cực tiểu của chứa và có cùng tập các từ khởi đầu ( vì định nghĩa chỉ liên
quan đến các từ khởi đầu).

Giả sử lấy , đặt . Ta chứng minh là một cơ sở Groebner cực tiểu của . Thật
vậy, ta có , vì khi chia cho sẽ chuyển đến phần dư, điều này xảy ra do là cơ sở
Groebner cực tiểu nên không chia hết cho bất kì phần tử nào của , suy ra . Vì vậy là
một cơ sở Groebner cực tiểu của , và là rút gọn trong theo cấu trúc đã xây dựng.
Áp dụng quá trình trên cho tất cả các phần tử trong cho đến khi chúng đều là
rút gọn. Cơ sở Groebner có thể thay đổi qua mỗi lần thực hiện nhưng khi một phần tử
là rút gọn, thì nó vẫn rút gọn trong cơ sở mới nhận được vì chúng ta không hề thay đổi
từ khởi đầu. Do đó cuối cùng ta được một cơ sở Groebner rút gọn.
Để chứng minh tính duy nhất, ta giả sử và là hai cơ sở Groebner rút gọn của .
Khi đó và có cùng số phần tử và ( vì mỗi iđêan đơn thức có duy nhất một tập sinh
đơn thức tối tiểu). Do vậy lấy bất kì . Ta chứng minh , và từ đó suy ra .
Xét . Vì là cơ sở Groebner nên , mà , nên trong hiệu , các từ khởi đầu bị triệt
tiêu, còn lại những phần tử không chia hết cho ( vì là cơ sở Groebner rút gọn). Suy
ra . Vậy .



11


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER

4 Thuật toán Buchberger
Định nghĩa 4.1. Cho là hai đa thức khác và là một thứ tự từ.
(i) Đa bậc của đa thức , viết gọn là , được xác định là = .
(ii) Nếu = và = , xét , trong đó , , thì ta gọi là bội chung nhỏ nhất của và . Kí
hiệu là =
12



VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
(iii) Gọi S-đa thức của và là tổ hợp

Bổ đề 4.1. Giả sử có tổng , .
Nếu thì là một tổ hợp tuyến tính trên của các -đa thức Hơn nữa, , với mỗi .
Chứng minh
Đặt . Theo giả thiết, . Khi đó,

.
Đặt . Ta có
(4.1)
Mặt khác,
(4.2)

Ta có

+

chính là tổ hợp tuyến tính trên của - đa thức .
Hơn nữa, vì
nên .
Do đó theo (4.2) suy ra với mỗi .
Nhận xét 4.1. Dùng kí hiệu để chỉ phần dư của phép chia đa thức cho hệ gồm đa
thức . Khi đó nếu là một cơ sở Groebner của iđêan thì

Thật vậy, nếu thì rõ ràng . Ngược lại, nếu thì , trong đó hoặc không có từ nào
của chia hết cho với mọi . Vì nên nếu thì . Điều này không xảy ra, vậy .
13



VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Kết quả này cho ta giải quyết bài toán thành viên iđêan.
Định lí 4.1. Tiêu chuẩn Buchberger
Cho là một iđêan trong . Cố định một thứ tự từ, khi đó một cơ sở của là một
cơ sở Groebner khi và chỉ khi , phần dư của phép chia cho là .
Chứng minh
Nếu là cơ sở Groebner thì do , phần dư của phép chia bằng theo nhận xét
trên.
Ta chứng minh . Hiển nhiên . Ngược lại, lấy bất kì , suy ra , ta chứng minh .
Thật vậy thì tồn tại sao cho
(4.3)
Theo định nghĩa đa bậc, ta suy ra
.

(4.4)

Đặt , khi đó (4.4) trở thành .
Với mỗi sự biểu diễn với một thứ tự từ, ta có các khác nhau. Vì thứ tự từ là thứ
tự tốt nên ta chọn biểu diễn của trong phương trình (4.3) sao cho là cực tiểu. Ta chứng
tỏ với một giá trị cực tiểu của được chọn thì , khi đó đẳng thức (4.4) xảy ra nên ta suy
ra được .
Giả sử . Tách các từ có là , ta viết dạng

(4.5)
Mỗi hạng tử trong tổng thứ hai và thứ ba trên dòng thứ hai của (4.5) đều có . Do đó
theo giả thiết thì tổng đầu tiên phải có . Đặt . Khi đó
.
Theo Bổ đề 4.1, tổng này là tổ hợp tuyến tính trên của - đa thức ), mà ta có

,

14


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
với , nên cũng theo Bổ đề 4.1 ta suy ra
,

(4.6)

và tồn tại sao cho
(4.7)
Theo giả thiết nên ta có thể viết
(4.8)
sao cho
(4.9)
tức là khi , ta có thể tìm một sự biểu diễn của qua các phần tử của G sao cho các từ
khởi đầu không bị triệt tiêu.
Từ Phương trình (4.8) suy ra
,
với . Kết hợp với (4.9) và (4.6) ta có
.

(4.10)

Thay sự biểu diễn của vào Phương trình (4.7), ta được

với Theo (4.10) .
Lúc này thay vào Phương trình (4.5) thì
,
tức là tổ hợp tuyến tính của các mà tất cả các từ đều có đa bậc nhỏ hơn , điều này

mâu thuẫn với tính cực tiểu của .
Vậy và suy ra điều phải chứng minh.
Chú ý 4.1. Theo tiêu chuẩn Buchberger, trong trường hợp hệ cơ sở gồm nhiều đa
thức , ta chú ý một số đặc điểm sau để giảm bớt số phép thử không cần thiết:
• Vì nên chỉ cần thử cho các cặp đa thức với .
• Nếu là hai từ thì do vậy không cần thử cho các cặp từ.
• Nếu và nguyên tố cùng nhau thì
15


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
.

(4.11)

Nếu thì do tính nguyên tố cùng nhau nên suy ra , vô lý vì . Vậy trong Phương trình
(4.11) không có sự triệt tiêu các đơn thức đầu, suy ra
,
tức là có một phép chia cho mà phần dư bằng . Do vậy không cần thử cho các cặp đa
thức có từ khởi đầu nguyên tố cùng nhau. ( Chẳng hạn, xét iđêan , sử dụng thứ tự
với , ta xét có và . Khi đó và nguyên tố cùng nhau, suy ra là cơ sở Groebner của.
Định lí 4.2. Thuật toán Buchberger
Cho là một iđêan đa thức. Khi đó cơ sở Groebner của có thể được xây dựng
bằng hữu hạn bước của thuật toán sau:
Input:
Output: cơ sở Groebner của và .

REPEAT

FOR mỗi cặp DO


IF THEN
UNTIL .

5 Một số cải tiến Thuật toán Buchberger
Trong việc thiết kế phần mềm hữu ích dành cho toán học, chúng ta không chỉ
chú ý đến độ chính xác của các thuật toán mà còn quan tâm đến kết quả của chúng.
Một số cách cải tiến thuật toán Buchberger đã được đưa ra chủ yếu làm tăng tốc độ
tính toán.

16


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Như đã biết, một cơ sở của một iđêan là cơ sở Groebner khi . Do đó một cách
tốt nhất để cải tiến hiệu quả thuật toán này là chỉ ra càng ít các -đa thức cần xem xét
càng tốt. Để xác định được các -đa thức có thể được lược bỏ chúng ta tìm hiểu các
khái niệm sau:
Định nghĩa 5.1. Cố định một thứ tự từ và cho . Cho , ta nói rằng rút gọn về theo
modulo , kí hiệu
,
nếu có thể viết được dưới dạng
,
với mỗi , ta có
.
Để hiểu được mối quan hệ giữa định nghĩa trên với thuật toán chia, ta xét bổ đề sau:
Bổ đề 5.1. Cho là một tập hợp có thứ tự của các phần tử của . Khi đó , điều ngược
lại nói chung là không đúng.
Chứng minh
Nếu ,theo thuật toán chia ta có

,
và theo Định lí 3.1, với mỗi , ta có
.
Do đó .
Điều ngươc lại nói chung không đúng. Xét ví dụ:
Cho , với thứ tự . Nếu chia cho , theo thuật toán chia ta có
,
Do đó .
Xong chúng ta cũng có thể viết

17


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Khi đó (thực chất chúng bằng nhau), suy ra .

Định lí 5.1. Một cơ sở của iđêan là cơ sở Groebner khi và chỉ khi với mọi .
Chứng minh
Trong chứng minh của Định lí 4.1 ta đã chứng minh kết quả này dưới dạng giả
thiết với mọi .
Tuy nhiên trong quá trình chứng minh ta chỉ sử dụng dạng biểu diễn

với
.
Đó chính là , và Định lí được chứng minh xong.



Mệnh đề 5.1. Cho một tập hợp hữu hạn , giả sử sao cho
,

tức là đơn thức đầu của và nguyên tố cùng nhau. Khi đó
.
Chứng minh
Để đơn giản, giả sử rằngvà đã được nhân với một hắng số thích hợp để . Viết
lại và dưới dạng

Khi đó, từ , ta có

.

(5.1)

Từ đó suy ra
.

(5.2)
18


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Thật vậy, từ (5.1) ta có đơn thức đầu của và là khác nhau và không thể triệt tiêu nhau.
Vì nếu các đơn thức đầu của chúng là như nhau thì
.
Điều này không thể xảy ra, vì nếu và là nguyên tố cùng nhau thì , vô lí vì . Từ
(5.1) và (5.2) suy ra với .

Mệnh đề 5.1 hiệu quả hơn Định lí 4.1 trong việc kiểm tra một cơ sở Groebner,
ta chỉ cần có với mọi và , không nguyên tố cùng nhau. Bây giờ, ta sẽ tìm hiểu rõ hơn
về vai trò của -đa thức. Trước hết chúng ta sẽ tìm hiểu khái niệm xoắn (syzygy) các từ
khởi đầu của tập hợp .

Định nghĩa 5.2. Cho . Một xoắn trên các từ khởi đầu của là một bộ gồm đa thức,
sao cho
.
Kí hiệu là tập con của bao gồm tất cả các xoắn trên các từ khởi đầu của . Đôi lúc
chúng ta cũng sử dụng ký hiệu thay cho .
Ví dụ 5.1 Xét . Khi đó sử dụng thứ tự từ điển,
xác định một xoắn trong vì
.
Cho , bằng tại vị trí thứ . Khi đó có thể viết dưới dạng . Với ví dụ xác định xoắn từ
-đa thức, tức là chỉ ra một cặp với , cho là của và . Khi đó
,
là một xoắn các từ khởi đầu của Trên thực tế, -đa thức là sự viết tắc của cụm từ
“syzygy polynomial”.
Định nghĩa 5.3. Phần tử được gọi là thuần nhất bậc , với , nếu
,
trong đó và , với mọi .
19


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Bổ đề 5.2. Mọi phần tử của có thể biểu diễn duy nhất thành tổng của các phần tử
thuần nhất trong
Chứng minh
Cho . Cố định số mũ , và cho là số hạng của ( nếu có) sao cho có bậc là . Khi
đó
.
Suy ra các số hạng , trong tổng , có bậc là .
Khi đó là phần tử thuần nhất bậc của và .
Tính duy nhất
Giả sử và

.
Khi đó
.
Suy ra . Vậy .



Mệnh đề 5.2. Cho . Mọi xoắn có thể viết dưới dạng

,
trong đó và .
Định lí 5.2. Một cơ sở của iđêan là một cơ sở Groebner khi và chỉ khi với mọi phần
tử trong một cơ sở thuần nhất của xoắn ta có
.
Chứng minh
Đặt , và là bậc nhỏ nhất trong tất cả biểu diễn của thông qua .
Giả sử . Khi đó

20


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
.

(5.3)

Suy ra có bậc nhỏ hơn suy ra , do đó

là một xoắn trong và là phần tử thuần nhất bậc .
Theo giả thiết, tồn tại một cơ sở thuần nhất


của sao cho . Khi đó S có thể

được biểu diễn dưới dạng
.

(5.4)

Bằng cách biểu diễn các thành tổng của các hạng tử và khai triển phương trình
(5.4) ta được biểu diễn thành tổng của các xoắn thuần nhất. Khi đó là đa thức thuần
nhất bậc .
Theo Bổ đề 5.2 chúng ta có thể loại bỏ tất cả các xoắn không có bậc là . Trong
(5.3), giả sử rằng với mỗi hoặc là hoặc là phần tử thuần nhất bậc .
Giả sử có bậc . Nếu thì nó có thể viết được dưới dạng , với . Do đó (5.3) đươc
viết lại
.
Nhân hai vế của biểu thức trên với ta được
.

(5.5)

Theo giả thiết, , nên có thể viết
,

(5.6)

trong đó sao cho
,.

(5.7)


Từ (5.5) và (5.6) suy ra
.

(5.8)

Vì là phần tử thuần nhất bậc nên có thể viết , là các từ, sao cho đồng dạng với và
,
suy ra
21


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
.
Do đó từ (5.6) dẫn đến trong (5.8) phải có
.
Kết hợp điều này với (5.3) và (5.8) ta có biểu diễn mới của là
,
mà
,
điều này mâu thuẫn với cách chọn . Vậy phải có .
Do đó
.
Theo định nghĩa là cơ sở Groebner của .



Bổ đề 5.3. Cho là các đơn thức trong và . Với xác định , và cho

trong đó là cơ sở chuẩn tắc của . Với mỗi đặt . Khi đó ta có

.
Hơn nữa, nếu chia hết thì có thể được biểu diễn thông qua và
Chứng minh
Để chứng minh Bổ đề ta đặt .
Khi đó ta có

Nếu chia hết thì và ta có

Do đó được sinh bởi .



22


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
Bây giờ ta tiến hành cải tiến thuật toán Buchberger bằng cách sử dụng xoắn. Ta sẽ sử
dụng các kí hiệu đã trình bày trong Bổ đề 5.3. Trước hết ta xem xét hệ quả sau:
Hệ quả 5.1. Cho là một tập sinh của . Giả sử chúng ta có đôi một khác nhau sao cho
vàchia hết . Khi đó cũng là hệ sinh của tập .
Bây giờ ta có là một tập sinh của iđêan trong và . Bằng cách sử dụng Hệ quả
5.1 ta tìm cách khử các càng nhiều càng tốt để có được tập sinh của càng ít phần tử.
Sau đó chúng ta tính các -đa thức tương ứng với các còn lại trong và tìm cách loại bỏ
chúng. Ta có được thêm vào tập nếu Khi đó ta sẽ mở rộng tập sinh của tập thành
do đó .
Một lần nữa, ta áp dụng các bước trong Hệ quả 5.1 để loại bỏ càng nhiều từ
tập mới càng tốt từ đó ta sẽ có một tập sinh mới của ít phần tử hơn. Ta tìm các -đa
thức tương ứng với các còn lại trong và tìm cách khử chúng. Tiếp tục quá trình cho
đến khi tất cả các -đa thức đều rút gọn về . Khi đó ta sẽ có một cơ sở của các môđun
xoắn.

Bây giờ ta sẽ tìm cách thiết lập các thuật toán tính các -đa thức và giảm bớt chúng.
Trước tiên ta chia nhỏ tập chỉ số

và

thành hai tập con là

.
Lưu ý rằng, bất cứ lúc nào trong thuật toán, khi đã được khởi tạo thì tập là tập

sinh của môđun xoắn của các từ khởi đầu. Thực hiện thuật toán cho đến khi . Với
những ý tưởng đó, chúng ta sẽ tìm hiểu cải tiến thuật toán Buchberger dựa trên hai
tiêu chí sau đây:
1. TIÊUCHÍ 1, kí hiệu Crit1.
Nó nhận giá trị “” khi và chỉ khi và là nguyên tố cùng nhau.
Nếu chúng ta sẽ không cần tính toán và nó sẽ rút gọn về theo Mệnh đề 5.1. Vì vậy sẽ
không có đa thức nào được thêm vào tập cơ sở và được thêm vào . Ta chọn cặp sao
cho và không nguyên tố cùng nhau.
23


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER
2. TIÊUCHÍ 2, kí hiệu Crit2.
Tiêu chí này được trình bày như một thuật toán ( Thuật toán 5.2 sẽ được trình
bày phía sau) và được sử dụng để loại bỏ các cặp từ tạo ra đồng thời sẽ loại bỏ luôn
các -đa thức tương ứng với chúng. Đây là ý tưởng dựa trên kết quả của Hệ quả 5.1. Ý
tưởng cơ bản là tìm ra ba chỉ số vàchia hết.
Thuật toán 5.1
INPUT:
OUTPUT: Cơ sở Groebner của

INITIALIZATION:

WHILE DO

WHILE DO
Chọn

IF THEN
, với là rút gọn đối với .
IF THEN

24


VỀ MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN BUCHBERGER

Thuật toán 5.2
INPUT: từ Thuật toán 5.1
OUTPUT: với các cặp bị xóa theo Hệ quả 5.1
INITIALIZATION:
WHILE DO
IF THEN

WHILE
IF THEN
IF chia hết THEN

WHILE DO
IF THEN


WHILE DO
IF AND THEN
IF chia hết THEN

25