動機
兩個代數表達式即使寫法看上去相差很大,也可能表示同一個多項式。展開一個很大的表達式,代價可能很高。隨機取值提供了另一種檢驗方法:在隨機選取的點上計算兩者之差的值。若值非零,即證明兩個多項式不同;若值為零,則可能只是巧合。
Schwartz–Zippel 界限制了總次數有界的非零多項式出現這種巧合的概率。該檢驗具有單邊錯誤:在域運算精確的前提下,它絕不會把非零的取值判為零,但可能剛好取在某個根上,因而未能檢測出非零多項式。
定義
定義 6.3.1
(總次數與隨機取值點)
設 為域, 為多項式。它的總次數是所有非零單項式中指數之和的最大值;零多項式另行處理。設 為有限非空集合。從 中獨立而均勻地選取 。
定義 6.3.2
(單邊恆等檢驗)
對於表示 的某個表達式,恆等檢驗就是在所選的點上計算它的值。若結果非零,則報告 不恆為零;若結果為零,則報告今次試驗沒有找到見證。重複試驗可以降低漏掉非零多項式的概率,但並不能把一次零取值變成恆等的證明。
定理
定理 6.3.3
(Schwartz–Zippel 界)
若 非零且總次數至多為 ,則
當右端大於 時,此界仍然成立,只是這時不提供任何資訊。當 時,非零常數的取值永遠不為零。
定理 6.3.4
(透過行列式判定二分圖匹配)
對於兩側各有 個頂點的二分圖,構造一個 矩陣:對每條邊 ,其對應位置的元素取為互不相同的未定元 ,其餘位置取零。該矩陣的行列式多項式非零,當且僅當此圖有完美匹配。
證明:對變量個數歸納
證明
(對變量個數歸納)
域上次數至多為 的非零一元多項式至多有 個根。這就證明了一元情形。非零常數沒有根,包括 的情形。
對於歸納步驟,把非零多項式寫成關於最後一個變量的多項式:
首項係數 的總次數至多為 。由歸納假設, 在前 個取值處為零的概率至多為 。若它不為零,則所得關於 的一元多項式的次數恰為 ,在 中至多有 個根。在前面各次選取已確定的條件下,獨立選取的最後一個值落在這些根之一的概率至多為 。
取值為零的概率至多等於首項係數為零的概率,加上首項係數不為零時取到根的概率。這至多是 。此論證同樣適用於 的情形:這時多項式不依賴最後一個變量,第二項為零。
證明透視
歸納如何收束
證明用到三個要素,各用一次。域的假設只通過最後一個變量的根的個數界起作用。最後一個座標獨立於前面的座標,所以證明可以先固定 ,再套用該根界。不顯然的一步,是按首項係數 在所選的點上是否為零來分類。若為零, 的次數可能下降,根界便不能使用,於是整個事件就歸給歸納假設處理,代價至多為 。
次數的核算使論證收束。由於 是 的一部分, 的總次數至多為 。無論 取何值,兩項代價 與 的和都是 ;兩個事件以聯集界合併,所以不需要它們之間的獨立性。若各座標互相依賴,或在 上並非均勻,條件步驟就會失效。
證明:行列式與匹配
證明
(行列式與完美匹配)
把行列式形式地展開為對右側指標的置換 求和:
採用標準邊界約定: 行列式為一,空圖的空匹配是完美匹配。某一項非零,當且僅當所選取的每個矩陣元素都對應一條邊。這樣的置換在每個左側頂點和每個右側頂點處各選出一條關聯邊,即得到一個完美匹配。若圖沒有完美匹配,則所有項均為零。
若存在完美匹配,則它對應的乘積對所選的每條邊使用一個互不相同的變量。兩個不同的置換選出不同的邊集,而各條邊的變量互不相同,因此它們對應不同的單項式。該項的係數為 或 ,在任何域中都非零,包括特徵為二、兩種符號相同的情形。因此該匹配項不會與另一個不同匹配的項相消,行列式多項式非零。當 時,其總次數為 。
選取一個有限域,其抽樣集合 的大小大於 。獨立地為每個邊變量從 中均勻地賦值,然後精確地計算行列式。若行列式非零,則證明存在完美匹配。若存在完美匹配,則行列式為零的概率至多為 。若不存在完美匹配,則每次取值的結果都為零,因此該檢驗絕不會錯誤地報告存在匹配。
例題詳解
例題 6.3.5
(一元情形的根的巧合)
在有理數域上,取 ,。這個非零多項式在四種選擇中的其中一種取值為零。此界給出 ,恰好等於失敗概率。
例題 6.3.6
(帶有壞點的非零多項式)
對於 與 ,該多項式非零,但它在 與 處取值為零。實際概率為 ,一次的界也是 。一次零取值並不能證明恆等。
例題 6.3.7
(兩個完美匹配)
對於兩側各有兩個頂點的完全二分圖,
這兩個不同的單項式分別對應兩個完美匹配。儘管形式多項式非零,在某個具體的數值代入下,它們的值仍可能互相抵消。
例題 6.3.8
(沒有完美匹配)
若兩個左側頂點都只與第一個右側頂點相鄰,則 矩陣的第二列為零。其行列式恆為零,這與不存在完美匹配相符。每一次數值取值得到的行列式也都為零。
重複與實現
使用 個獨立的隨機取值點。若其中任何一個行列式非零,則報告存在完美匹配;否則報告各次試驗沒有找到見證。當存在完美匹配時,所有試驗都漏掉它的概率至多為 ,前提是 。當不存在完美匹配時,每個行列式都為零,不會出現假陽性。
高斯(Gauss)消去法可以用多項式個域運算在域上計算行列式。若某個主元為零,實現中必須尋找非零的主元,或者正確地識別出矩陣奇異;除法只能除以非零的域元素。明確的有限域表示方式和精確的均勻抽樣方法決定了位元複雜度。僅僅說「選一個足夠大的域」,本身並沒有確定這些代價。
該檢驗以單邊錯誤判定匹配是否存在;數值行列式非零是形式行列式非零的代數證書。但它本身並不輸出匹配。可以另用自歸約,透過對子圖的存在性檢驗來構造匹配,並單獨核算其錯誤概率。
常見錯誤
反例模式
一次零取值可能只是落在根上
多項式 並不恆為零,但在 時取值為零。僅憑一次零取值就報告「恆等」可能是錯誤的。相反,一次非零取值則是形式多項式非零的確鑿見證。
常見錯誤
(對每條邊重用同一個變量)
行列式的證明對每條邊使用不同的變量。如果在展開行列式之前把所有邊都賦予同一個形式變量,不同匹配的項就可能相消。對於完全的二乘二二分圖,把每個元素都換成 ,得到行列式 ,儘管圖中有兩個完美匹配。
常見錯誤
(對錯誤的對象估計次數)
總次數的界必須針對實際被檢驗的多項式來建立。書面表達式的次數可以作為一個上界,即使相消使多項式的真實次數變低。更大的有效上界依然安全,只是給出的概率保證可能較弱。
為甚麼域的假設很重要
一元多項式的根的個數界是域的性質。在含零因子的環上,次數為 的非零多項式可能有多於 個根,所以如果沒有額外條件,歸納法無法照搬。精確運算也是單邊保證的一部分:數值捨入可能把一個很小的非零值變成表觀上的零,或者反過來。
抽樣的各個座標是互相獨立的。證明先對前 個座標取條件,再使用獨立而均勻的最後一個座標。若讓所有座標相關聯,概率可能集中在根集上:例如,取 時 總是為零。帶有依賴關係的抽樣方案需要單獨分析。
概念視角組合
數網格上的零點
這個上界可以看成對網格 上的點計數:總次數至多為 的非零多項式,在網格上至多有 個零點。這個界是精確的:當 ,取 中相異的 ,多項式 恰好在網格的 個超平面切片上為零,即 個點。例子 在 上,四個點中有兩個零點。
透過自歸約構造匹配
存在性檢驗可以用來構造匹配,前提是要核算每一次隨機查詢。從完整的圖開始。選取一個剩餘的左側頂點,考察與它關聯的各條邊。對於候選邊 ,刪去 和 ,用全新的獨立取值檢驗較小圖的行列式。若有任何一次取值非零,就保留 ,並繼續處理這個較小的圖。若所有候選邊的檢驗結果都為零,則報告失敗。到達空圖時,輸出所保留的邊。
非零取值不會產生假陽性,所以被保留的邊總是可以擴充為當前圖的完美匹配。若當前圖有完美匹配,則所選左側頂點的關聯邊中至少有一條屬於某個完美匹配。它對應的縮小圖也有完美匹配,但隨機檢驗可能漏掉它。當域的抽樣集合大於原圖規模 時,在縮小圖上的每次試驗的失敗概率至多為 ;即使圖在縮小,也使用這個共同的上界。
對每條候選邊做 次獨立取值。對於含有匹配的候選邊,所有取值均為零的概率至多為 。這個自適應過程至多檢查原圖的 條候選邊。全新的隨機性使得同樣的條件界在任何先前歷史之後都成立,所以由聯集界得出失敗概率至多為 。若初始圖沒有完美匹配,則任何候選檢驗都不會產生假的非零行列式,該過程會報告失敗,而不會輸出無效的匹配。所返回的邊也可以直接檢查端點是否互不相同,以及是否屬於該圖。
這個構造至多使用 次行列式計算,以及多項式量級的額外圖運算。它說明了單邊錯誤與全新隨機選擇如何簡化自適應的誤差核算。它是有別於單次存在性檢驗的另一個算法,有單獨的界和明確的失敗結果。
歸納所依據的根的個數界
對於域上的非零一元多項式 ,若 是根,則由多項式除法得 。任何不同的根 都滿足 ,因此 。重複這一論證可知,次數為 的多項式至多有 個不同的根。非零常數沒有根。
多項式與它在有限域上誘導的函數之間的區別很重要。例如,在有 個元素的域上, 是非零的形式多項式,卻在每個域元素處取值為零。它的次數為 ,所以在從整個域中抽樣時,定理給出的是沒有資訊的界 。這並不矛盾:要得到有用的界,需要抽樣集合大於相應的次數。
總結
總次數為 的非零多項式,在 中獨立均勻選取的點上為零的概率至多為 。使用互不相同的邊變量時,二分圖匹配的行列式非零當且僅當存在完美匹配,由此得到一個單邊錯誤的隨機存在性檢驗。
練習
快速檢查
(對於次數至多為三、 的情形,定理對非零多項式取值為零的概率給出怎樣的上界?)
套用 ,取 。
解答 · 答案
至多為 。實際概率可能更小。
快速檢查
(為甚麼兩個不同的完美匹配會產生不同的行列式單項式?)
比較兩個置換所用到的邊變量。
解答 · 答案
它們使用不同的邊集,而每條邊都有各自的變量。因此它們的乘積至少在一個變量因子上不同。
快速檢查
(若一次試驗漏掉某個非零多項式的概率至多為 ,試給出三次獨立試驗全部漏掉它的概率的上界。)
各次試驗獨立,把三次漏掉的概率相乘。
解答 · 答案
由獨立性,至多為 。
快速檢查
(為甚麼行列式的一次非零取值就能證明形式行列式多項式非零?)
回想零多項式在每個點上的取值。
解答 · 答案
零多項式在每個點上的取值都為零。非零取值與「形式多項式為零」這一假設矛盾。