最大根方法——一段往事

05-24

最大根方法——一段往事

來自專欄愛哞客棧

這是一個歷史悠久的故事，從頭講起至少應該追溯到六十年前，但我們先從冪級數的定義開始說。

壹

冪級數是多項式的推廣形式，指的是形如 $sum_{n=0}^infty a_n t^n$ 的式子，我們可以認為這裡的 $t$ 和求和號都只是符號，那麼冪級數的意義就只在於一個數列 ${a_n}$ 。不過我們不會滿足於此。當冪級數作為一個級數在某些意義下收斂時，它又可以代表一個函數。我們可以對函數作各種運算，而泰勒公式提示我們，在一些時候運算得到的函數又可以寫成冪級數的形式。如此一來，我們有時可以直接定義冪級數上的運算。比如加法，我們有 $sum_{n=0}^infty a_n t^n+sum_{n=0}^infty b_n t^n=sum_{n=0}^infty (a_n+b_n) t^n，$

看上去天經地義。

那麼，乘法呢？

美國人發明了一個詞 "freshmans dream"，指代的是 $(x+y)^n=x^n+y^n$ 這個式子。在實踐中，大一學生做得更多的事情是將矩陣中對應項相乘得到的矩陣當作矩陣的乘法。類似地，我們也可以定義冪級數的「乘法」為 $sum_{n=0}^infty a_n t^ncirc sum_{n=0}^infty b_n t^n=sum_{n=0}^infty a_nb_n t^n，$

簡潔明了。然而這樣的乘法卻和冪級數對應的函數之間的乘法是不相容的。如果要相容，我們只能定義 $sum_{n=0}^infty a_n t^ncdot sum_{n=0}^infty b_n t^n=sum_{n=0}^inftyleft( sum_{k=0}^n a_kb_{n-k} ight) t^n。$

為了區分這兩種乘法，我們把第一種稱為冪級數的哈達瑪乘法，第二種稱為冪級數的乘法。

那麼冪級數的哈達瑪乘法與冪級數對應的函數之間就沒有多大聯繫了嗎？也不完全是。至少，我們還可以有這樣的命題：

命題甲：如果兩個冪級數對應的函數是有理函數，那麼它們的哈達瑪乘積對應的函數也是有理函數。

有理函數指的是多項式的商，這與這些多項式的係數是不是有理數無關，請注意不要混淆。

設有理函數 $frac{P(t)}{Q(t)}$ 對應的冪級數為 $sum_{n=0}^infty a_n t^n$ ，由於滿足 $Q(t)cdot sum_{n=0}^infty a_n t^n=P(t)$ ，由冪級數的乘法可知，數列 ${a_n}$ 自某項起形成一個常係數線性遞推數列。反之亦然。由特徵方程法或者考慮部分分式，我們可以推得，有理函數對應的冪級數係數自某項起有通項公式 $a_n=sum_{i=1}^s p_i(n)alpha_i^n$ ，這裡 $alpha_i$ 是一些兩兩不同的複數，而 $p_i$ 是一些非零復係數多項式。注意：即使 $a_n$ 全是實數，甚至全是正整數，我們也無法保證 $p_i$ 的係數是實數或者 $alpha_i$ 是實數，事實上， $alpha_i$ 是 $Q(t)$ 的某些根。

因為兩個有理函數對應的哈達瑪乘積的冪級數係數的通項公式也有這樣的形式，故我們可以反其道而行之，推得其冪級數係數某項起也形成一個常係數線性遞推數列，因而哈達瑪乘積對應的函數也是有理函數，即命題甲成立。

那麼，除法呢？

我們定義哈達瑪除法為哈達瑪乘法的逆運算，即當 $b_n$ 全不為零時，定義 $sum_{n=0}^infty a_n t^n$ 和 $sum_{n=0}^infty b_n t^n$ 的哈達瑪商為 $sum_{n=0}^infty frac{a_n}{b_n} t^n$ 。那麼兩個有理函數對應的冪級數的哈達瑪商對應的函數也是有理函數嗎？答案是否定的。

類似地，我們還可以定義 $sum_{n=0}^infty a_n t^n$ 的哈達瑪 $k$ 次方根為滿足按哈達瑪乘法自乘 $k$ 次等於 $sum_{n=0}^infty a_n t^n$ 的所有冪級數。然而，有理函數對應的冪級數也未必有一個哈達瑪 $k$ 次方根，使得其對應的函數是有理函數。

一切就到此為止了嗎？不，讓我們回到六十年前。

貳

1959年，法國數學家皮索在前人的特例 [1] 的啟發下提出了如下的猜想 [2]：

命題乙：如果兩個整係數冪級數對應的函數是有理函數，且它們的哈達瑪商也是整係數冪級數，則它們的哈達瑪商對應的函數也是有理函數。

命題丙：如果一個冪級數對應的函數是有理函數，且它的係數都是整數的 $k$ 次方，則它有一個哈達瑪 $k$ 次方根，使得其對應的函數也是有理函數。

命題乙解決於八十年代 [3,4,5]，命題丙解決於2000年 [6]，對於這些證明，我們先放一放。我們且來看看皮索是怎麼處理這兩個命題的。

皮索用了一種現在我們稱為「最大根方法」的技巧。他首先作了一些額外的假設：在命題乙中，設除數 $sum_{n=0}^infty b_n t^n$ 的係數自某項起的通項公式 $b_n=sum_{i=1}^{s} q_i(n)eta_i^n$ 中， $eta_1$ 的模長大於任何 $eta_i (2le ile s)$ 的模長。在命題丙中，設冪級數 $sum_{n=0}^infty a_n t^n$ 的係數自某項起的通項公式 $a_n=sum_{i=1}^{s} p_i(n)alpha_i^n$ 中， $alpha_1$ 的模長大於任何 $alpha_i (2le ile s)$ 的模長。這種條件被稱為最大根條件。

我們首先來看命題乙。

設被除數 $sum_{n=0}^infty a_n t^n$ 的係數自某項起的通項公式為 $a_n=sum_{i=1}^s p_i(n)alpha_i^n$ ，除數 $sum_{n=0}^infty b_n t^n$ 的係數自某項起的通項公式為 $b_n=sum_{i=1}^{s} q_i(n)eta_i^n$ ，那麼哈達瑪商的係數自某項起的通項公式則為

$egin{align}frac{a_n}{b_n}&=frac{sum_{i=1}^{s} p_i(n)alpha_i^n}{sum_{i=1}^{s} q_i(n)eta_i^n}\&=frac{sum_{i=1}^{s} frac{p_i(n)}{q_1(n)}left(frac{alpha_i}{eta_1} ight)^n}{1+sum_{i=2}^{s} frac{q_i(n)}{q_1(n)}left(frac{eta_i}{eta_1} ight)^n}\&=left(sum_{i=1}^{s} frac{p_i(n)}{q_1(n)}left(frac{alpha_i}{eta_1} ight)^n ight)sum_{j=0}^inftyleft(-sum_{i=2}^{s} frac{q_i(n)}{q_1(n)}left(frac{eta_i}{eta_1} ight)^n ight)^j，end{align}$

展開後可以寫作 $frac{a_n}{b_n}=sum_{i=1}^infty r_i(n)gamma_i^n$ ，這裡 ${r_i(n)}$ 是一列非零有理函數，而 ${gamma_i}$ 是模長不增的複數列，估計每一項的大小，我們得到，存在正整數 $l$ 和實數 $0<gamma<1$ ，使得 $|r_i(n)gamma_i^n|ll n^{li}gamma^{ni}$ 。

設正整數 $M$ 滿足 $|gamma_{M+1}|<1$ ，並將 $frac{a_n}{b_n}=sum_{i=1}^infty r_i(n)gamma_i^n$ 寫作 $sum_{i=1}^M r_i(n)gamma_i^n+sum_{i=M+1}^infty r_i(n)gamma_i^n，$

則後一半當 $n$ 趨於無窮時趨於零。由條件 $a_n, b_n$ 均為整數，故 $p_i,q_j$ 的所有係數以及 $alpha_i, eta_j$ 均為代數數，故 $r_i$ 的所有係數以及 $gamma_i$ 也均為代數數。因為 $r_i$ 的所有係數都是代數數，所以存在非零整係數多項式 $R$ ，使得所有 $R(n)r_i(n) (1le ile M)$ 均為多項式。因為 $gamma_i$ 都是代數數，所以 $sum_{i=1}^MR(n) r_i(n)gamma_i^n$ 形成一個整係數線性遞推數列，即，存在不全為零的整數 $c_1,ldots,c_h$ ，使得 $sum_{k=1}^hc_kleft(sum_{i=1}^M R(n+k) r_i(n+k)gamma_i^{n+k} ight)=0。$

於是，我們有 $sum_{k=1}^hfrac{a_{n+k}}{b_{n+k}}c_kR(n+k)=sum_{k=1}^hc_kleft(sum_{i=M+1}^infty R(n+k) r_i(n+k)gamma_i^{n+k} ight)。$

由於左邊是整數，右邊當 $n$ 趨於無窮時趨於零，我們知道當 $n$ 足夠大時，左右均等於零，即冪級數 $sum_{n=0}^infty frac{a_n}{b_n}R(n) t^n$ 的係數自某項起形成常係數線性遞推數列，換句話說，冪級數 $sum_{n=0}^infty frac{a_n}{b_n}R(n) t^n$ 對應的函數是有理函數。

如果我們額外假設了 $q_1(n)$ 是常數，那麼 $R(n)$ 也是常數，此時我們已經不需要再做什麼了。而在一般情況下，我們再回過頭來看看命題乙就會發現，我們已經把最大根條件下的命題乙，化歸成了在除數 $sum_{n=0}^infty b_n t^n$ 的係數是整值多項式的條件下的命題乙。換句話說，我們只需證明如下命題，這個命題的證明應該歸功於皮索的後繼者康托爾 [7]：

命題丁：如果整係數冪級數 $sum_{i=0}^infty a_n t^n$ 對應的函數是有理函數，且存在一個整值多項式 $R$ ，使得 $frac{a_n}{R(n)}$ 總是整數，則冪級數 $sum_{i=0}^infty frac{a_n}{R(n)} t^n$ 對應的函數也是有理函數。

與之前一樣，我們設 $sum_{n=0}^infty a_n t^n$ 的係數自某項起的通項公式為 $a_n=sum_{i=1}^s p_i(n)alpha_i^n$ 。這時 $frac{a_n}{R(n)}=sum_{i=1}^s frac{p_i(n)alpha_i^n}{R(n)}$ ，其分母總是整數，而其分子在一般情況下卻只是個代數數，看來我們在這裡無論如何也得用一些代數數論的知識才能處理下去了。世界就是如此，有的問題高等而膚淺，比如如何將一個初等數論的證明平行推廣到代數數論中去，而有的問題卻初等而深刻，比如生命的意義是什麼。為了讓本文更可讀，我決定只證明其初等的特例，而將完全版的證明留給了解一些代數數論或者對代數數論感興趣的讀者們。我們假設，這裡 $p_i$ 的係數和 $alpha_i$ 都是有理數。

我們不妨設 $R(n)$ 模任何素數 $p$ 都不恆同餘於零，不然我們用 $frac{R(n)}{p}$ 代替 $R(n)$ ，而這樣的操作只能作有限次，否則某個不為零的整值就會變成絕對值小於一的數。取 $N$ 為一大於所有 $p_i$ 的係數的分母的絕對值、所有 $alpha_i$ 的分子和分母的絕對值、所有 $alpha_i-alpha_j (i eq j)$ 的分子和分母的絕對值、以及所有 $R(n)$ 的係數的分母的絕對值的正整數。由中國剩餘定理，存在無窮多個正整數 $d$ ，使得 $R(d)$ 的所有素因子都不小於 $N$ 。

取任意這樣的 $d$ 。對 $R(d)$ 的每個素因子 $p$ ，假設 $p^h$ 恰好整除 $R(d)$ ，那麼 $p^h$ 整除 $R(d+kp^h)$ ，這裡 $k=0,ldots,s-1$ 。由條件，

$0equiv a_{d+kp^h}=sum_{i=1}^s p_i(d+kp^h)alpha_i^{d+kp^h}equivsum_{i=1}^s p_i(d)alpha_i^{d+kp^h}pmod{p^h}，$

對每個 $k=0,ldots,s-1$ 。把這 $s$ 個式子想成關於 $p_1(d),ldots,p_s(d)$ 的 $s$ 元一次方程組。由范德蒙行列式及費馬小定理，係數行列式等於 $prod_{i=1}^salpha_i^dprod_{i>j}left(alpha_i^{p^h}-alpha_j^{p^h} ight)equivprod_{i=1}^salpha_i^dprod_{i>j}(alpha_i-alpha_j)pmod p，$

不是 $p$ 的倍數，由克萊姆法則，係數矩陣可逆，所以這個方程組在模 $p^h$ 意義下沒有非零解，故 $p^h$ 整除每個 $p_i(d)$ 。由 $p$ 的任意性，我們知道每個 $p_i(d)$ 的分子都是 $R(d)$ 的倍數。由於這樣的 $d$ 可以任意大，我們知道 $R$ 作為多項式整除每個 $p_i$ 。我們便得到了命題丁的結論。

皮索對於命題丙的處理是類似的，只是把冪級數展開式 $frac{1}{1-x}=sum_{i=0}^infty x^i$ 換作 $(1+x)^{frac{1}{k}}=sum_{i=0}^infty inom{frac{1}{k}}{i}x^i$ 。如此他得到的結論是，若最大根條件成立，且 $p_1(n)$ 是常數，則命題丁成立。如果想要擺脫 $p_1(n)$ 是常數這個條件，我們需要 [8,9,10] 通過分析素因子來區分多項式里的 $n$ 和指數上的 $n$ 帶來的影響。

也許我們應該在陷入更多對細枝末節的探討前停止，再回頭看看什麼是最大根方法，為什麼我們需要最大根來處理這些問題。

一言以蔽之，最大根方法就是以漸進的手段分析整數序列，由於絕對值小於一的整數只有零，或者，等價地，依據代數數論的劉維爾不等式，在不等式中得到等式。至於為什麼需要最大根，這是為了讓得到的級數收斂。

如果最大根不唯一的時候，這個方法就失效了嗎？也不是。

我們至少還有兩種普遍的方法在最大根不唯一的時候依然用最大根方法處理問題。

第一，是從最大根到最小根的轉變。如果 ${a_n} (nin mathbb{N})$ 是我們的常係數線性遞推數列，那麼我們可以依樣畫葫蘆把其定義拓展到 ${a_n} (nin mathbb{Z})$ ，把數列倒過來看，最大根就變成了最小根，最小根則變成了最大根，這時我們需要考慮兩個問題：第一， ${a_n} (nin mathbb{Z})$ 這時未必是整數數列了，我們需要對我們的命題作一點推廣；第二，我們需要證明對於 $nin mathbb{N}$ 時題目給的整除條件或者 $k$ 次方數條件可以推到對於所有 $nin mathbb{Z}$ 成立，這通常需要分別考慮每個素因子得到。

第二，是改變所在的度量空間。級數 $sum_{i=0}^infty 2^i$ 在通常意義下發散，卻在 $2$ 進度量中收斂於 $-1$ 。級數收斂條件的改變意味著最大根條件的改變。

叄

從方法到結論，我們都可以利用本文中講述的東西更深入地了解一些競賽題的背景。比如下面這道題是 2000 年全國高中數學聯賽加試題。證明一個常係數線性遞推式總是完全平方數，這種題目甚至已經成為了初中數學競賽的套路。

設數列 ${a_n}$ 和 ${b_n}$ 滿足 $a_0=1$ ， $b_0=0$ ，且 $egin{cases}a_{n+1}=7a_n+6b_n-3 \b_{n+1}=8a_n+7b_n-4end{cases}$ ，求證： $a_n$ 是完全平方數。

如果你遇到類似的考題，記住本文的命題丙，求通項——開方/冪級數展開——算結果的線性遞推式，必然能得到證明。

以下三道題直接按最大根方法作冪級數展開就可以得到：

設 $a,b$ 為整數，使得對所有 $nin mathbb{N}$ 都有 $2^n a+b$ 是完全平方數。證明 $a=0$ 。（2001年波蘭數學奧林匹克第三輪）
設 $a,b$ 為大於一的整數，使得對所有 $nin mathbb{N}$ 都有 $a^n-1$ 整除 $b^n-1$ 。證明存在正整數 $k$ 使得 $b=a^k$ 。（美國數學月刊問題 10674）
設 $a,b$ 為正整數，使得對所有 $nin mathbb{N}$ 都有 $b^n+n$ 是 $a^n+n$ 的倍數。證明 $a=b$ 。（2005年 IMO 預選題 N6 )

最後這個問題可以通過按最大根方法和係數比較得到，其中的多項式部分不是常數，這使得比較係數的過程大為簡化：

設 $a_1,a_2,a_3,b_1,b_2,b_3$ 是兩兩不同的正整數，使得對所有 $nin mathbb{N}$ 都有 $(n + 1)a_1^n + na_2^n + (n - 1)a_3^n|(n + 1)b_1^n + nb_2^n + (n - 1)b_3^n$ 。證明存在正整數 $k$ ，使得 $b_i=ka_i(i=1,2,3)$ 。（2010年中國數學奧林匹克）

感謝閱讀，希望大家能有所收穫。

參考文獻

[1] Pólya, G. Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. Journal für die reine und angewandte Mathematik 151 (1921): 1-31.

[2] Pisot, C. Conférences données à lInstitut Fourier de Grenoble. 1959.

[3] Pourchet, Yves. Solution du probleme arithmétique du quotient de Hadamard de deux fractions rationnelles. CR Acad. Sci. Paris288 (1979): 1055-1057.

[4] van der Poorten, Alfred J. Solution de la conjecture de Pisot sur le quotient de Hadamard de deux fractions rationnelles. CR Acad. Sci. Paris 306.97 (1988): 102.

[5] Rumely, Robert. Notes on Van der Poortens proof of the Hadamard quotient teorem. Séminaire de Th. de Nombres de Paris (1986).

[6] Zannier, Umberto. A proof of Pisots d-th root conjecture. Annals of Mathematics 151.1 (2000): 375-383.

[7] Cantor, David. On arithmetic properties of coefficients of rational functions. Pacific Journal of Mathematics 15.1 (1965): 55-58.

[8] Perelli, A., and Zannier, U. Arithmetic properties of certain recurrence sequences. Journal of the Australian Mathematical Society 37.1 (1984): 4-16.

[9] Bézivin, Jean-Paul. Factorisation de suites récurrentes linéaires. Groupe de travail danalyse ultramétrique 7.8 (1979): 1979-1981.

[10] Rumely, Roberts, and Van der Poorten, Alfred J. A note on the Hadamard kth root of a rational function. Journal of the Australian Mathematical Society 43.3 (1987): 314-327.