多項式最大公因式與葛羅布納基底

從數字到多項式：歐幾里得最大公因式

你已經會求兩個整數的最大公因數了：不斷把較大的那個換成它對較小者取的餘數，直到其中一個變成零，最後一個非零的數就是最大公因數。這就是歐幾里得演算法，而它真正令人驚訝的地方在於：同一台機器也能套用在多項式上。把 x^3 - 1 和 x^2 - 1 不當成數字，而當成可以做帶餘除法的物件，你就能跑同一個迴圈。掉出來的多項式最大公因式，就是能同時整除這兩者的最大多項式。

誰會想要這個東西？因為最大公因式正是把多項式分式約成最簡形式的工具。比值 (x^3 - 1)/(x^2 - 1) 藏著一個公因式：分子分母都能被 x - 1 整除。電腦代數系統在找到 x - 1 之前，沒辦法誠實地化簡這個比值——而它找到 x - 1 的方式，就是跑多項式版的歐幾里得演算法。約去公因式、化簡有理表達式、偵測重根，全都歸結到這一個計算。

  gcd(a, b):                     # a, b are polynomials, deg(a) >= deg(b)
      while b != 0:
          r = remainder(a, b)    # polynomial long division, keep remainder
          a = b
          b = r
      return a / leading_coeff(a)   # normalize to make it canonical (monic)

  example:  a = x^3 - 1,  b = x^2 - 1
     x^3 - 1   = (x^2 - 1)*x  +  (x - 1)        # remainder x - 1
     x^2 - 1   = (x - 1)*(x + 1)  +  0          # remainder 0  -> stop
     gcd = x - 1

歐幾里得演算法，與整數版本一模一樣，只差在「餘數」現在指的是多項式長除法。最後一個非零餘數,化成首一形式,就是最大公因式。

精確運算,以及潛伏其中的係數爆炸

這裡的一切都活在前幾篇所建立的精確世界裡。多項式長除法會在係數裡產生分數,所以演算法跑在精確有理數運算上,絕不用浮點數。這很重要,因為「是否互質」這個問題很脆弱:x^2 - 2 沒有有理因式,但你一旦把 sqrt(2) 四捨五入成小數,就可能捏造出一個根本不存在的因式。問一個餘數是不是恰好等於零多項式,其實就是上一篇的零等價問題披上了多項式的外衣——而只有精確運算才能誠實地回答它。

但精確是有代價的,而且很早就現形。把樸素的歐幾里得演算法套在兩個係數不大的整數多項式上,看著中途的分數膨脹:即使最後的最大公因式係數很小,中途也可能冒出分子分母都有幾十位數的分數。這是你第一次親眼見到表達式膨脹——整個符號計算事業的核心限制,本階最後一篇就專門講它。實務上的系統會用更聰明的變體反擊:子結式演算法讓係數保持為整數且有界,模運算方法則在好幾個小質數上算出最大公因式再重組回來——但教訓已經很清楚:精確不代表便宜。

多個多項式、多個未知數:為什麼最大公因式還不夠

歐幾里得演算法是一大成就,但它被困在單一變數裡。一旦你有了好幾個未知數的多項式方程組——例如 x^2 + y^2 = 1 配上 x - y = 0——就沒有單一個「比較大的那個」可以拿來取餘數,那套整潔的最大公因式圖像就崩塌了。然而我們真正想問的,恰恰是這些多變數的問題:這個系統有沒有解?某一條方程式是不是其他幾條的邏輯後果?我能不能消掉 y,讀出 x 必須滿足什麼?

葛羅布納基底就是答案,而認識它最乾淨的方式,是把它看成兩樣你早已信任的東西的推廣。它推廣了最大公因式(單變數時,多個多項式塌縮成一個),也推廣了高斯消去法(線性方程式被三角化,於是你能回代)。一組葛羅布納基底是一組全新但等價的多項式——解相同、後果相同——只是被重新整理成一個標準形式,從中那些難題就變得一眼可讀。選對變數的排序,這組基底裡會真的出現一個只含 x 的單變數多項式,正是你想要的消元。

布赫貝格演算法:基底實際上怎麼建出來

那要怎麼算出一組?布赫貝格演算法是最原始的配方,它的核心想法是「取餘數」在多變數世界裡的一記漂亮回聲。變數多於一個時,用一個多項式去約化另一個,會有「消掉哪一項」的選擇,而這個選擇可能藏住一些抵消。所以對每一對多項式,你刻意造出一個組合——S-多項式——專門設計來消掉它們的領導項,把底下潛伏的東西逼出來。

固定一個單項式排序,讓每個多項式都有明確定義的「領導項」。令集合 G 一開始就等於你原本的那些多項式。
對 G 裡的每一對,造出消掉它們兩個領導項的 S-多項式,再用 G 裡所有成員去約化它(這是「取餘數」的多變數類比)。
如果某次約化留下非零的餘數,那個餘數就是真正的新資訊:把它加進 G,並開始也考慮它配出來的新對。
當每一對都約化成零時就停。此時集合 G 就是一組葛羅布納基底;把它整理乾淨(去掉多餘成員、把領導係數變成 1),就得到唯一的約化基底。

這個演算法總會停下,也總會回傳一組正確的基底——光是「它一定會停」這件事就是一條貨真價實的定理,而非顯而易見的事實。但代價要說老實話,因為它很慘烈。布赫貝格演算法的表達式膨脹可以遠比單變數最大公因式更嚴重:中途的多項式可以脹到龐大無比,最壞情況下執行時間是變數個數的雙重指數。一個看起來小而無害的系統,可能跑上好幾個鐘頭、吃掉好幾 GB 才結束,或者實務上根本跑不完。現代系統會用更鋒利的引擎(Faugere 的 F4 與 F5)和聰明的排序,但底下那份困難是真實的,而且躲不掉。

它換來什麼——以及該記住什麼

手上有了一組葛羅布納基底,一長串令人意外的問題就變得機械化。一個系統到底有沒有解?檢查約化基底是不是只剩常數 1——若是,方程式彼此矛盾,無解。想消去變數、像回代解三角線性系統那樣解一個系統?用消元排序,把答案直接讀出來。某個多項式是不是其他的後果?用基底去約化它,看會不會歸零。這些都是前幾階線性代數那些招式的「符號幾何」對應版,只不過現在方程式被允許彎曲了。

把這兩個世界分清楚很值得。如果你只需要多項式系統的數值解,一個數值解法器——牛頓法,或是某種伴隨矩陣的特徵值——通常更快,也擴展得好太多。葛羅布納基底真正派上用場,是當你需要精確、結構性的答案時:一個「無解」的證明、一份保證完整的所有解的描述、一條自動證出的幾何定理、一次精確的消元。是精確與符號,不是快速與近似——這正是你做的取捨,也正是開啟整個本階的那筆取捨。