【數論】等差數列，你在嗎

等差數列，顧名思義就是一串數字排好站成一列，使得兩兩相鄰的數字都有一樣的差距間隔。

舉例來說 1, 3, 5, 7, 9 是一個等差數列；101, 202, 303, 404, 505, 606, 707, 808 也是一個等差數列。如果再進一步區分等差數列，我們可以用長度來區分它們，例如 1, 3, 5, 7, 9 共有五個數字，故稱之為一個長度五的等差數列，依此類推 101, 202, 303, 404, 505, 606, 707, 808 是長度八的等差數列。那麼我們這邊說的『等差數列存在性』是什麼意思？

上述兩個數列，透過檢驗可以立刻知道它們都是等差數列，是因為它們被具體的寫出來．那如果有一串數字沒有被具體描述出來，我們是否還有辦法判斷到底會不會在這一串數字中存在部分數字形成等差數列呢？接下來我們就來談談這問題的發展，從中也可以看見數學家如何思考以及展現創意（怎麼往自己臉上貼金呢）。

舉例來說，現在有5個自然數每個數字都不大於10，請問這樣子的5個自然數是否保證有一部分形成等差數列呢？如果我們能夠找到5個數字使得其中任意三個恰好都不足以形成長度3(等差數列的最小長度)的等差數列，答案就是NO；否則的話，如果任意挑選5個數字都找得到長度3的等差數列，答案就是YES。

顯然，這組數字 1, 2, 4, 5, 10 很容易驗證不存在等差數列，因此從1到10之中挑選5個數字並不保證會有等差數列。另一方面，這也是能挑出不形成等差數列的數字裡面最多的了，也就是說你若從中選6個數字，就必定會存在長度3的等差數列，不管這6個數字怎麼挑都無法避免。

換句話說，小於等於10的自然數中，若挑選大於5個數就保證了等差數列的存在性。

此時我們知道若要避免形成等差數列，從10以下(含)的數字中最多只能挑選 5/10=50% 的數字。如果從40以下(含)的數字中挑選，則最多只能拿  15/40=37.5% 的數字才不會形成等差數列。此處 5/10 或 15/40 就是數字的密度，也是數學家用來衡量此問題的重要指標之一。

由於等差數列平移之後仍是等差數列，上述例子也告訴我們，若不要形成等差數列，不管從哪裡開始數連續10個正整數，最多只能挑選其中 10×50%=5 個數字；連續40個正整數，則最多只能挑選其中 40×37.5%=15 個數字。你或許已經感覺到，隨著可選範圍越來越大，為了避免等差數列形成，能夠挑選出來的數字密度也越來越小。

如何建構一個數列避免包含等差數列?

是一個具有挑戰且有趣的數學問題。1946 年 F. Behrend 提出了一個建構法，然而他的方法隨著範圍變大，找到的數字密度卻下降得相當快，比方說在連續10萬個數字中，Behrend找的不含等差數列的數字集合中只有171個數字；連續100萬個數字中，他的集合中也只有586個數字，密度小於0.06%。

一個很自然的想法是利用貪婪演算法去建構，比方說先選 1 和 2，接下來每次都選不會形成等差數列的最小的數字，所以接下來的數字是 4 (如果選 3 就會形成等差，4 是最小不形成等差的數)，後面依序就是 1, 2, 4, 5, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40,…，按照這套邏輯可建構出要多長就有多長的不包含等差數列的數列。這個方法是 1978 年 A. Odlyzko 和 R. Stanley 在一篇未發表的論文裡提出，後來人們也給這樣建構出來的數列冠上 Stanley sequence 的名稱。

有沒有更好的方法找到更大密度的數列去避免包含等差呢？這是數學家數十年來關心的重要問題。

挑選多少數字就一定會包含等差數列呢？

這是另一個方向的有趣問題。我們立馬就來介紹第一個重量級結果出場，英國數學家羅斯 K. Roth (菲爾茲獎得主)於1953年證明：

[Roth 定理]:
如果集合A在自然數中的密度是正的，則A必定包含長度3的等差數列。而且這樣的等差數列有無窮多組。

羅斯美妙的結果開創了後續許多衍伸，也間接讓加性組合學在近代蓬勃發展。例如，大數學家 Szemeredi (2012 Abel 獎得主) 用組合學的方法證明了更強(事實上可說是強到不可思議)的結果：在相同的假設之下 ，集合Ａ不僅包含長度3的等差數列，Szemeredi 指出 A 包含了【任意長度的等差數列】。也就是你心裡面任選一個正整數，例如 100萬，那麼集合A 裡面必定有100萬個數字形成等差數列。之後H. Furstenberg（2020 Abel獎得主）用動態系統方法證明了相同的結果，T. Gowers（1998 菲爾茲獎得主）用傅立葉分析也證明了相同的結果。

假設 A 是 {1, 2, 3,….., N} 的一個子集合，如果 A 不包含長度3的等差數列，那麼 A 的密度最大可以到多大？我們令 |A|/N =r(N)（我們用 |A| 來代表 A 集合中的元素個數，因此 r(N) 就是 A 的密度）。事實上，我們可以從羅斯的證明裡面得到，r(N) < 1/(loglog N)。

換句話說，如果一個集合 A 不存在任何長度3的等差數列，此集合的密度必定趨近於零。

因此在全部自然數中密度大於零（不管多小都可以，只要大於零）的集合就必定存在等差數列。當我們用 r(N) 來思考時，這些問題變得更加棘手，也因此估計 r(N) 的大小也就成了這幾年等差數列問題的重要研究方向，接下來我們就來談談一直到最近的重要發展。

1999年重要進展，布爾甘(J. Bourgain, 1994 費爾茲獎得主)登場，布爾甘在1999年的結果大幅度的改進羅斯了Roth的密度估計，布爾甘的結果證明了將上界下修到

也就是說，一個不存在長度三3的等差數列的集合密度是非常小的。

這裡說得非常小是跟羅斯的結果相比，例如，當 N=10^10 時，羅斯說若要不包含等差數列，那麼集合A的密度必定小於 100%，也就是不能全選。(咦?!這不是廢話嗎，對啦，在數論的研究中很多結果都是用 logloglog…來表示，必須在規模超級大的情況下才顯得出威力。) 布爾甘的結果則說集合 A 的密度必定小於 31.64% (看起來正常多了)。

這裡順便說一下有趣的小故事，筆者在美國唸書時候，曾經聽指導老師說格林 (Green) 和陶(Tao) 有一年做出其它長度的密度定理時，格林跟陶打賭一百美金說，他相信短期之內不大可能會有人可以做出比他們更好的密度估計，不曉得是不是布爾甘知道了，很快地就做出了更好的結果，當然我也不清楚格林到底有沒有給出這一百美金。

我們稍微談談布爾甘的證明思路，其實布爾甘證明的敘述是當 r(N) 足夠大時，那麼Ａ必定存在三個相異的數字 a, b, c 使得說 a+b=2c，當然這就說明Ａ存在長度三的等差數列。一直到2011年，一位年輕的英國數學家桑德斯(Sanders) 再次大幅度的改進估計，得到

簡單來說，布爾甘和桑德斯皆證明在這些密度估計之下，我們有這個不等式

其中 f 是集合Ａ的特徵函數，也就是 f(x)=1，當 x 在Ａ裡面；f(x)=0 ，當 x 不在Ａ裡。因此只要上述的和非零，也就意味著等差數列的存在。

數學家無所畏懼，總是勇於挑戰。桑德斯的結果在2020年被兩位數學家 Bloom 以及 Sisask 再度改進，而且這次的密度估計突破了大家普遍覺得不大可能可以攻克的境界。這兩位數學家證明了

其中 c 是一個大於零的常數。此密度估計不僅僅突破了分母次方是一的界線，更重要的是此密度結果對一道非常困難的【艾迪胥-圖蘭猜想 (Erdős–Turán conjecture)】給出了重大突破。

Bloom 以及 Sisask 密度估計直接證明了上述猜想在長度為3的等差數列為真。任何人如果可以證明上述的猜想，必定會轟動數學界，因為不僅解決了一個重要的數學問題，同時也把格林以及陶的結果當作特例，也就是令 A 是所有質數的情況。

時間來到 2023 年，當大家覺得數學家似乎已經相當相當難在有所突破時候，兩位資訊科學家，R. Meka 和 Z. Kelley 震撼了數學界。他們給出了遠比 Bloom 以及 Sisask 還要更小的估計

其中 b, c 是兩個大於零的固定常數。

這意味著一個集合如果沒有任何等差數列，此集合的密度是以指數函數的速度趨近到零。

R. Meka 和 Z. Kelley 的證明幾乎用了前述所有數學家的方法，加上許多全新的細膩操作才得到如此重要的突破，有些人甚至形容 Meka 和 Kelley 的結果是在乾毛巾再擰出水來。

說到指數遞減這樣的密度估計並不是第一次出現。以筆者在求學時有一陣子常玩的桌遊 SET來舉例，此桌遊由許多的牌組成，這些牌有不同的圖案及花色，如下圖。遊戲規則是先把所有牌在桌上排好，背面朝上，每人輪流翻一張之後蓋回去，接下來如果有人記得哪三張有相同花色或圖案的牌剛好排成一直線（橫，直，斜皆可）就可以拿走這三張牌，最後拿最多的人贏。

SET 遊戲其實跟這裡討論的數學問題息息相關。我們可以問說如果這副牌有N張，那最多可以在桌上放幾張，使得找不到任何三張相同花色或圖案剛好排成一直線。依此類推，在高維度空間，我們也可以問相同的問題使得集合裡沒有任何長度為三的等差數列。事實上，這些問題的密度估計在幾年前已經被幾位數學家用非常巧妙的線性代數方法，得到了指數函數型的遞減密度估計。

總結來說，比起等差數列的存在，要讓它不存在是一件更難辦到的事情，難到說不存在等差數列的集合中，數字的個數相對來說非常非常的稀少。

註：內文的所有密度估計精確來說分子都還有一堆 loglog... 項，但是這些項的大小跟分母比起來小的非常多，因此，為了讓內文更整潔以及凸顯分母的重要性，我們省略分子這些項。