小朋友的涂鴉（三）：地圖的魔術

昵稱535749 2016-11-13

展開全文

方弦發(fā)表于 2016-10-26 03:50

地圖的魔術

我們先回到一開始的問題：對于某個正整數 $k$ ,，假設有兩個互質的多項式 $P (x), Q (x)$ ，其中 $P (x)$ 的次數是 $3 k$ ,， $Q (x)$ 的次數是 $2 k$ ,。那么,，多項式 $R (x) = P (x)^{2} - Q (x)^{3}$ 的次數最小可以有多小,？

我們現在用別雷函數,、球面覆蓋和二部地圖的眼光來看這個問題。首先,，我們來考慮分式 $f (x) = \frac{- Q (x)^{3}}{R (x)}$ ,。可以證明,，如果 $f (x)$ 除了0,、1和∞以外還有別的分支點的話，我們就得不到最優(yōu)解,。所以,，我們可以假設 $f (x)$ 是別雷函數。

函數 $f (x)$ 在0處的分支點就是 $Q (x)^{3}$ 的根,，也就是 $Q (x)$ 的根（計算重數的話,，一共有 $2 k$ 個），但每個根的重數要乘以3,。同樣的道理,，它在∞處的分支點就是 $R (x)$ 的根，再加上無窮遠點 $x = \infty$ ,，因為 $R (x)$ 的次數比 $Q (x)^{3}$ 要小,，所以當 $x$ 趨向于無窮時， $f (x)$ 也會趨向于無窮,。那么,，它在1處的分支點又怎么樣呢？這就是我們選取 $f (x)$ 的目的： $f (x) - 1$ 就等于 $\frac{- P (x)^{2}}{R (x)}$ ,，所以,， $f (x)$ 在1處的分支點，就是 $P (x)$ 的根（計算重數的話,，一共有 $3 k$ 個）,，但每個根的重數要乘以2。我們可以假定 $f (x)$ 沒有別的分支點,。我們要問的問題實際上就是： $f (x)$ 在∞處的分支點至少有多少個,？

我們重溫一下球面覆蓋和二部地圖概念之間的翻譯表。

別雷函數	平面二部地圖
覆蓋的次數	邊的條數
0處的分支點	黑色頂點
1處的分支點	白色頂點
∞處的分支點	面
0處和1處分支點的重數	頂點的度數
∞處分支點的重數	面的度數的一半

如果將所有這些要求翻譯成二部地圖的概念,，我們實際上要解決的是這樣的一個問題：

如果一個二部地圖,，它的白色頂點度數都是偶數，并且加起來是 $6 k$ ，而黑色頂點的度數都是3的倍數,，加起來也是 $6 k$ ,，那么,，它至少有多少個面,？（在這里，我們不能說白色頂點的度數都是2,，因為 $P (x)$ 可能有重根,，黑色頂點同理）

如果 $k$ 很小的話，試著畫畫也就可以了,。但因為現在 $k$ 可以要多大有多大,，亂試一通大概不太管用。這就是借助別的數學工具的時候了,。18世紀的大數學家歐拉（順帶一提,，按博士導師的師承關系的話，他是筆者以及很多人的祖師爺）在開辟圖論這一領域時,，證明了下面的等式：如果一個平面地圖有 $v$ 個頂點,、 $e$ 條邊和 $f$ 個面（最外面的也算一個面）的話，那么必然有

v - e + f = 2.

我們把這個等式套到我們的問題上,，看看會得到什么,。容易知道，我們的二部地圖必定有 $3 k$ 條邊,，也就是說 $e = 3 k$ ,。把等式改寫一下，我們得到 $f = 2 - v + e$ ,。因為我們想知道至少有多少個面,，所以我們應該嘗試尋找最大可能的 $v$ ，也就是最大化頂點的個數,。因為白色頂點的度數都是偶數,，并且加起來是 $6 k$ ，要獲得最多的頂點,，最好的方法就是要求每個頂點的度數都是2,，這樣就能拿到最多的 $3 k$ 個頂點。同理,，對于黑色頂點,，最好的情況就是每個頂點的度數都是3，這樣能拿到最多的 $2 k$ 個頂點,。所以,，頂點的總數合起來最多是 $5 k$ 個，也就是 $v \leq 5 k$ 。代入歐拉的等式,，得到的就是 $f \geq k + 2$ ,，也就是說這樣的平面地圖至少有 $k + 2$ 個面?？紤]到其中一個面對應的是無窮遠點 $x = \infty$ ,，這就意味著 $R (x)$ 的度數至少是 $k + 1$ ，而且要達到這個度數,， $R (x)$ 必須不能有重根,，也就是說每個面（除了最外邊）的度數都是2。

我們得到了想要的下界,，但還要證明這個下界能夠達到,，而我們又不想計算無窮個滿足條件的多項式，怎么辦呢,？這就是別雷定理出場的時候了：它告訴我們,，只要對應的二部地圖能畫出來，那么滿足要求的分式必定存在,，而且系數都是代數數,。所以，我們根本不需要計算,，只需要畫出滿足條件的二部地圖就足夠了,。這樣的地圖畫法非常簡單：首先畫出一棵有 $2 k$ 個黑色頂點的三叉樹（也就是沒有圈的地圖，而分叉的頂點度數都是3）,，在每個葉頂點（也就是度數為1的頂點）上畫一條跟自身連接的邊,，然后在每條邊中間插入一個白色頂點，就得到了滿足條件的二部地圖,?？梢宰C明，滿足條件的二部地圖必定能用這樣的方法構造出來,。根據別雷定理,，既然二部地圖能畫出來，那么滿足要求的分式存在,，也就是說使 $R (x)$ 達到最小度數 $k + 1$ 的 $P (x), Q (x)$ 是存在的,。

三叉樹的構造，蒙A. Zvonkine惠允

實際上,，我們可以給 $P (x), Q (x)$ 施加更復雜的限制,，用同樣的辦法，也能得到 $R (x)$ 的最小度數,。這個推廣首先由U. Zannier在1995年給出,，后來A. Zvonkine等利用二部地圖的方法給出了簡單得多的證明,。

不僅如此，根據別雷定理,，二部地圖和分支點只有0,、1和∞的分式有著一一對應的關系，所以,，要知道有多少組 $P (x), Q (x)$ 能使 $R (x)$ 達到最小度數,，只需要知道有多少個由 $2 k$ 個頂點組成的三叉樹地圖。我們之前考慮 $k = 5$ 的情況,，截至2000年,，數學家找到了兩組解,。但要知道一共多少組,，只要在紙上隨便畫畫，很容易數出來一共有四組解：

k=5的四組解,，蒙A. Zvonkine惠允

通過這些地圖,，我們不僅能知道解的個數，還能部分推斷出解的性質,。樹a和d各自擁有鏡像對稱性,，所以它們對應的解的系數應該都是實數；樹b和c分別是各自的鏡像,，所以它們對應的解的系數可能不是有理數,，而是各自的復共軛。因為已知的兩組解的系數都是有理數,，它們對應的必定是樹a和d,，而未知的兩組解應該向復數領域尋找。果不其然,，剩下的兩組解在2005年被日本數學家鹽田徹治給出,，這些解的系數在 $Q (\sqrt{- 3})$ 中，一如預測,。