Cơ sở Gröbner

 

(Updated 28/Nov/2010)

Hôm qua (26/Nov/2010) đi dự seminar về “hệ động lực gián đoạn”, được nghe trình bầy một đoạn về cơ sở Gröbner. Chợt nhận ra rằng, đây là một trong những khái niệm rất cơ bản và quan trọng của toán học hiện đại, và từ trước đến nay tôi đã nghe người ta nhắc đến nó nhiều lần từ hơn chục năm nay nhưng mà tôi “lảng tránh” nó, vì nó thuộc về lĩnh vực đại số giao hoán mà tôi khá dốt. Nhưng bây giờ thấy không nên lảng tránh nữa. Chủ đề chính của seminar tôi tham dự tất nhiên cũng không phải là về cơ sở Gröbner, mà là về sự tồn tại các nghiệm tuần hoàn ổn định chu kỳ nhỏ trong các hệ động lực có gián đoạn (chẳng hạn cái điện thoại di động là một hệ như vậy: gián đoạn giữa lúc nghỉ và lúc bật, và phải làm thế nào để điều tiết việc thu phát sóng sao cho nó ổn định). Các bài toán động lực ứng dụng đó cũng cần dùng đến cơ sở Gröbner.

Những cái rất khó, rất phức tạp, chưa chắc đã phải là quan trọng. Còn những cái quan trọng, cơ bản, thật là cần thiết, thì chưa chắc đã phải là những cái rất khó, rất phức tạp. Hình như nhà vật lý Lev Landau cũng đã từng nói, cần phải có “judgment” tốt, đánh giá được cái gì là quan trọng trong những cái mình thấy. Giải thưởng Nobel của ông Nash về “ổn định Nash”, là một khái niệm cơ bản nhưng tương đối dễ, cho thấy các nhà kinh tế hiểu được quan trọng không nhất thiết phải phức tạp. Đối với người làm khoa học, việc phân biết “cái gì là quan trọng” là một điều cần thiết. Tuy nhiên, trong khoa học, đặc biệt là trong toán học, vẫn có sự nhầm lẫn giữa “quan trọng” và “khó khăn, phức tạp”: người ta có xu hướng thổi phồng sự quan trọng của những kết quả rắm rối (mà cuối cùng phạm vi ứng dụng khá là hạn chế, chẳng mấy ai cần biết đến), trong khi những khái niệm quan trọng hơn, cần dùng nhiều hơn, nhưng không rắm rối lắm, khi được phát minh ra thì lại không được đánh giá cao. Nhưng sau đó thực tế cho thấy nó lại là những khái niệm cơ bản mà rất nhiều người trong nhiều chuyên ngành khác nhau cần dùng đến. Cơ sở Gröbner là một ví dụ như vậy về khái niệm cơ bản mà “không quá phức tạp” nên từng bị “coi rẻ”, và không được giải thưởng gì trong toán, trong thời gian dài.

Người đầu tiên viết về cơ sở Gröbner không phải là nhà toán học Wolfgang Gröbner, mà là một học trò của ông ta tên là Bruno Buchberger vào năm 1965 trong luận án tiến sĩ của mình. Đến năm 2007, Buchberger mới nhận được một giải thưởng, là giải Paris Kanellakis Theory and Practice Award. Giải này không phải là một giải về toán học, mà là một giải về tin học (computing) ! Nó mang tên một chuyên gia tin học (computer scientist) Paris Kanellakis (bị chết vì tai nạn máy bay năm 1995), và tặng thưởng cho các công trình có giá trị rất lớn trong lĩnh vực tin học (ví dụ như các công trình đầu tiên về public key cryptography, data compression, vector support machine, …). Giải này kèm theo một số tiền mặt tượng trưng là 5000 USD, nhưng giá trị của các công trình được giải này có thể tính theo đơn vị trăm triệu hay tỷ USD.

Cơ sở Gröbner  là gì mà quan trọng như vậy ?

Giả sử ta có một ideal I trong một vành đa thức A =   K[X_1,\hdots, X_n], sinh bởi một tập hữu hạn các phần tử   P_1,\hdots, P_k (trong đó K là một trường, ví dụ như   \mathbb{Q} hay \mathbb{C}). Khi đó bộ G = (P_1,\hdots,   P_k) được gọi là một cơ sở (basis) Gröbner của ideal I nếu như, ứng với một sự xếp thứ tự của các đơn thức nào đó (chẳng hạn coi là X_1^\alpha X_2^\beta đứng trước X_1^\gamma X_2^\delta nếu như \alpha <   \gamma hoặc là \alpha = \gamma\beta < \delta — kiểu xếp thứ tự như vậy gọi là kiểu lexicographic), ta có thể xác định được là một phần tử Q \in A có thuộc I hay không bằng thuật toán sau:

Chia Q lần lượt cho các phần tử P_1, \hdots, P_k (theo thứ tự bất kỳ) cho đến khi không chia được nữa, chỉ còn phần lẻ R thì thôi. Phần lẻ R ở đây có nghĩa là 1 đa thức sao cho đơn thức (có thứ tự) cao nhất của nó có thứ tự nhỏ hơn là thứ tự của (đơn thức có thứ tự lớn nhất) các đa thức P_1, \hdots P_k (bởi vậy không thể chia được tiếp). Điều quan trọng ở đây là R không phụ thuộc vào cách chia: tức là đầu tiên có thể chia cho P_1, rồi lấy phần lẻ chia cho P_2, hay là có thể chia cho P_2 trước, rồi lấy phần lẻ chia cho P_1, v.v. Cái phần lẻ R cuối cùng nhận được là xác định duy nhất theo Q. Nếu R= 0 thì Q \in I, còn ngược lại nếu R \neq  0 thì Q \notin I.

Nói cách khác, cơ sở Gröbner là một cơ sở có tính thuật toán, cho phép xác định là một đa thức cho trước có nằm trong ideal sinh bởi một số đa thức khác không. (Có thể cho vào máy tính tính toán kiểm tra). Định lý quan trọng là cơ sở Gröbner luôn luôn tồn tại, và có thể tìm được nó một cách thuật toán. (Tức là cứ có ideal thì đút vào máy tính, máy tính sẽ cho một cơ sở Gröbner). Cơ sở Gröbner không duy nhất, và nó cũng phụ thuộc vào thứ tự trên các đơn thức (chẳng hạn nếu lấy thứ tự theo tổng các bậc của đơn thức đơn thì sẽ được cơ sở Gröbner khác là nếu lấy thứ tự lexicographic). Tuy là nó có tính thuật toán, nhưng độ phức tạp về tính toán của nó khác lớn: double exponential theo  số các biến số và theo bậc của các đa thức ban đầu sinh ra ideal.

Thuật toán tìm cơ sở Gröbner là mở rộng đồng thời của 3 thuật toán kinh điển: thuật toán diện biến số của Gauss để giải hệ phương trình tuyến tính, thuật toán chia của Euclide, và thuật toán đơn hình trong qui hoạch tuyến tính. Ví dụ, xuất phát từ một bộ hai hàm bậc 1

\mathcal{F} = \{ 2x + 3y + 4z - 5, 3x + 4 y + 5z -2 \},

(chúng sinh ra một ideal trong R[x,y,z], và nếu đặt chúng bằng 0 thì ta được một hệ phương trình tuyến tính), dùng thuật toán Gauss ta chuyển chúng về được thàngh một bộ khác đơn giản hơn:

\mathcal{G} = \{ x-z+14, y + 2z - 11 \}. Bộ này chính là một cơ sở  Gröbner. (Ví dụ này lấy từ bài báo của Bernd Sturmfelds, “What is a Gröbner basis”, Notices AMS, Vol. 52, No. 10, 2005)

Một điều kiện cần và đủ để một họ hữu hạn \mathcal{G} các phần tử của một ideal I là một cơ sở Gröbner là: ideal sinh bởi các phần đầu (tức là đơn thức có thứ tự cao nhất trong một đa thức) của các phần tử của I cũng chính là ideal sinh bởi các phần đầu của các phần tử của họ \mathcal{G}. Điều này cho thấy, nếu  \mathcal{G} là một cơ sở Gröbner, thì khi thêm một số phần tử tùy ý vào họ này, ta vẫn được một cơ sở Gröbner. Từ đó nảy sinh khái niệm cơ sở Gröbner suy giản (reduced Gröbner basis): Một cơ sở Gröbner được gọi là suy giản nếu nó thỏa mãn 3 điều kiện:

1) Hệ số của phần đầu (đơn thức có thứ tự lớn nhất, gọi là “initial term”) của mỗi phần tử của \mathcal{G} đều bằng 1;

2) Nếu bỏ bớt 1 phần tử ra khỏi \mathcal{G} thì nó không còn là cơ sở Gröbner;

3) Ngoài phần đầu của các phần tử của \mathcal{G} ra, thì tất cả các đơn thức khác có trong các phần tử của \mathcal{G} (gọi là các “trailing terms”) đều nằm ngoài ideal sinh bởi các phần đầu của các phần tử của \mathcal{G}.

Khi đó ta có

Định lý (Buchberger): Với mọi ideal I của   K[X_1,\hdots,X_n] và mọi sự xếp thứ tự đơn thức (monomial order), tồn tại duy nhất một cơ sở Gröbner suy giản của I ứng với sự xếp thứ tự đơn thức đó, và có thuật toán để tính cơ sở này.

Các ideal trong K[X_1,\hdots,X_n] cho ta các đa tạp đại số trong K^n (là tập các không điểm của các ideal, hay nói cách khác, là tập các nghiệm của một hệ phương trình đại số). Cơ sở Gröbner cho ta các thông tin về các đa tạp đại số này. Ví dụ như, trong trường hợp mà tập các nghiệm của một hệ các phương trình đại số là rời rạc, thì có thể tính được số nghiệm từ một cơ sở Gröbner suy giản. Khi mà tập các nghiệm có số chiều dương, thì cũng tính được số chiều, v.v.

Các cơ sở tương tự như cơ sở Gröbner, nhưng cho các ideal trong các vành địa phương, được Hironaka nghiên cứu vào năm 1964, và gọi chúng là các “cơ sở chuẩn tắc” (standard bases). Chúng đã góp phần giúp Hironaka giải quyểt được vấn đề giải kỳ dị (cho các đa tạp giải tích trên trường đặc số 0) vào năm đó (?).

(còn tiếp)

Print Friendly
 

1 comment to Cơ sở Gröbner

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Spam Protection by WP-SpamFree