張貼日期：Mar 30, 2015 3:16:47 AM

作者：沈俊嚴 副教授（國立台灣大學數學系）

傅氏分析 (Fourier analysis) 又稱「傅立葉分析」是數學領域中一個非常重要的研究主題。基本上，它是用來學習函數的性質。如果我們想要很粗劣草率的把數學分成兩類的話，那麼有一種分法就是，分成【連續數學】和【離散數學】；又如果只能選一邊站的話，那麼傳統上「傅立葉分析」會跟「微積分、實變函數論...」一起站在【連續數學】那邊，而【離散數學】陣營的成員就會是「組合學、圖論、密碼學、...」。

不過，最近在一些頂尖數學家高爾斯、格林與陶哲軒的帶領之下，「傅氏分析」進一步開疆拓土，大軍已經正式入侵那個看似不相干的「組合學」領土。

加法組合學

加法組合學基本上是在研究集合的結構性。這領域已經有相當豐富且有趣的結果， 而今天要談的，是 1958 年榮獲素有＜數學界諾貝爾獎＞的菲爾茲獎的英國數學家 Roth 所證明的結果，一個關於等差數列的結果 － Roth 定理 [1952]。

什麼是等差數列?

簡單來說，就是一連串數字使得兩兩相鄰的數都有相同的差。

舉例來說，3, 7, 11 就是長度為 3 的等差數列；10, 20, 30, 40, 50 就是長度為 5 的等差數列。

我們現在考慮一個簡單的集合：正整數集合 (用 N 表示)。很明顯，正整數集合有長度為 3 的等差數列。

那麼比正整數集合小一點的集合應該也會有吧? 嗯嗯!

那麼比正整數集合小二點的集合應該也會有吧? 嗯嗯?

那麼比正整數集合小三點的集合應該也會有吧? 一點二點三點到底在說什麼阿!!

好吧! 那就用「密度」的概念來敘述多寡吧。

舉例來說，如果我們說有一個集合 A 在 {1, 2, 3, ..., 100} 裡面的密度是 1/10 的話， 那麼這就是說 A 這個集合裡有 10 個數字。不過重點是只知道集合 A 裡面有幾個數字 (用 |A| 來表示)，並不知道這幾個數字是 1, 2, 3, ..., 100 中的哪幾個。

給定一個正整數子集合 A，我們用 d 來代表 A 在正整數集合 N 裡的密度。回到前面的例子，如果 A 就是 N 自己，那麼 A 的密度當然就是 1，而且 A 也就存在許多長度為 3 的等差數列。再回到之前「比正整數小一點的集合應該也會有吧? 」的問題，用密度的語言，即是

如果 0 < d < 1，那麼 A 是否還存在長度為 3 的等差數列?

很明顯，密度 d 的大小當然在告訴我們集合 A 的元素多寡，密度越小代表個數越少，直觀上也就越不容易找到等差數列；反之，密度越大就越有機會找到等差數列。而 Roth 定理告訴我們:

不管 d 有多小，就算小到 10^-100 ，A 還是存在長度為 3 的等差數列 (事實上，還不只一個，是存在無窮多個等差數列)。

Roth 定理與傅式分析

Roth 定理在這幾年已經有好幾個不同的推廣。除此之外，也有許多不同的證明方法。舉例來說，當代非常知名的組合學大師 Szemerédi (目前在美國 Rutgers 大學電腦資訊科學系任教)，在 1975 年用組合學的方法證明了著名的 Szemerédi 定理:

對於任意 0 < d < 1，A 都存在任意長度的等差數列。

Furstenberg (1977) 則用動態系統的方法來證明 Roth 定理；2001 年劍橋大學數學系教授高爾斯 (Tim Gowers)，也是 1998 年菲爾茲獎得主，開創一條全新的道路，利用傅式分析這套強而有力的工具，重新證明了 Szemerédi 定理。這一天，正式宣告「傅式分析入侵組合學」！

最後，我們要簡單的來談談如何用傅式分析來證明 Roth 定理。

其中最核心的關鍵就是所謂的「密度增加定理」。 整個關鍵的想法如下:

假設 A 這個子集合是隨機的分佈，那麼自然地就應該存在等差數列。如果 A 沒有包含等差數列，那麼 A 就是被巧妙的安排避開了等差數列，一旦如此，也就洩漏出 A 具有某些結構。用數學的語言，即是：

假設 A 是 Z_n ={0,1,2,...,n-1} 中的一個子集合，使得 A 在其中的密度是 d，用傅式分析的方法可以證明下面兩個結果其中之一必定會成立:

(1) A 包含著長度為 3 的等差數列；

(2)在 Z_n 中存在一個比 A 小一點的【等差數列所成的集合 B】，使得 |A∩B| = (d + C_d )|B|，其中 C_d > 0。

一旦有了上面的結論，Roth 定理就宣告投降了。

因為如果 (1) 成立，那就結束。如果是 (2) 成立，我們令新的子集合 A' = A∩B，那麼 (2) 告訴我們 A' 這個集合在某個等差數列集合裡，有更大的密度。把 A' 帶進上面的密度增加定理，反覆繼續同樣的推論，如果一直都是 (2) 成立，最終則會得到存在某個子等差數列集合 B' 使得 A 在 B' 裡面的密度是 1 (因為密度一直增加)。既然 B' 是等差數列集合，同時 A 在 B' 的密度為 1，那麼 A 當然就包含某個等差數列。

自從高爾斯使用傅式分析來證明 Szemerédi 定理之後，此方法不僅已經大量被使用在其他許多相當困難的組合學問題，也被廣泛運用到數論領域，以及離散幾何領域。在這之中，有一個基本但是非常重要的概念就是 －

計數 (counting)

在組合學裡面常常需要去計數，這裡的計數指的是，比方說我們要搜尋某些東西，找到就用數字 "1" 來代表，沒有找到則用 "0" 來代表。那麼下面的公式就可以用來代表這個計算函數：令

我們有

所以當 r = 0 時候，我們可以把某樣東西計算一次。而這也是傅式分析方法引進的原因，因為上面的函數就是傅式分析領域中最重要的關鍵 e(θ)。

格林-陶哲軒定理

所有質數所形成的集合 P，還存在任意長度的等差數列嗎？

數論一個基本定理告訴我們 P 的密度是 0；換句話說，質數在正整數集合裡是相當的稀少。用機率的眼光來看就是，閉著眼睛選一個正整數出來，那麼選出來的數是質數的機率會趨近於 0。密度為 0 的情況下，前面提到的 Szemerédi 定理也就派不上用場了。格林（Ben Green）和陶哲軒（Terence Tao）在 2004 年發表了一篇論文，證明了著名的 Green-Tao 定理：

質數裡面存在任意長度的等差數列。

在這裡我們不會談到此定理的細節，不過，值得一提的是，格林和陶哲軒這段時間的工作獲得了極大的肯定，分別得到了許許多多數學界的重要獎項，他們的貢獻及後續引發的效應，也讓原本在數學上屬於非主流的組合學，日漸受到重視。