Szemerédi定理

在算術組合學中，**塞邁雷迪定理**是個關於自然數集子集中的等差數列的結論。1936 年，艾狄胥和圖蘭・帕爾猜想：若整數集 _A_ 具有正的自然密度，則對任意的正整數 _k,_ 都可以在 _A_ 中找出一個 _k_ 項的等差數列。塞邁雷迪・安德烈於 1975 年證明了此結論。

## 定理敍述

若自然數集的子集 _A_ 滿足

　
: $\limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0,$

則稱 _A_ 具有正的_上密度_。塞邁雷迪定理斷言，若自然數集的一個子集具有正的上密度，則對任意的正整數 _k_, 該子集都包含無窮多個長為 _k_ 的（公差不為 0) 的等差數列。

定理另有一個等價的有限性敍述（即不牽涉「無窮」的）：對任意的正整數 _k_ 和實數 $\delta \in (0,1],$ 都存在正整數

　
: $N=N(k,\delta )$

使得 {1, 2, ..., _N_} 的每個至少 _δN_ 元的子集，都包含長為 _k_ 的等差數列。

定義 _r_k(_N_) 為 {1, 2, ..., _N_} 的子集當中，不包含長為 _k_ 的等差數列的最大子集的大小。塞邁雷迪定理給出漸近上界

　
: $r_{k}(N)=o(N).$

換言之，_r_k(_N_) 隨 _N_ 的增長慢於線性。

## 歷史

范德瓦爾登定理是塞邁雷迪定理的先驅，其於 1927 年獲證。

塞邁雷迪定理中， _k_= 1 和 _k_= 2 的情況顯然成立。 _k_ = 3 的結論關乎薩萊姆 - 斯賓塞集（不包含 3 項等差數列的整數子集）的大小。1953 年，克勞斯・羅特 利用類似哈代 - 李特爾伍德圓法的方法，證明了 _k_ = 3 的結論。1969 年，塞邁雷迪・安德烈利用組合學方法證明了 _k_ = 4 的情況。在 1972 年，羅特利用類似自己證明 _k_ = 3 的情況的方法，給出了 _k_ = 4 的情況的另證。

塞邁雷迪於 1975 年給出了適用於所有 _k_ 的證明。 他巧妙地擴展了自己先前對 _k_ = 4 的情況的組合論證，艾狄胥稱該證明為「組合學推理的傑作」("a masterpiece of combinatorial reasoning"). 定理亦有若干其他證明，較重要的有：1977 年希勒爾・菲爾斯滕貝格利用遍歷理論給出的證明，以及 2001 年高爾斯結合傅立葉分析和組合數學給出的證明。陶哲軒稱塞邁雷迪定理的眾多證明為「羅塞塔石碑」，因為它們連結了幾個乍看之下迥異的數學分支。

## _rk_(_N_) 的具體大小

_r_k(_N_) 的確切增長速度仍然未知。目前所知的上下界為

　
: $CN\exp \left(-n2^{(n-1)/2}{\sqrt[{n}]{\log N}}+{\frac {1}{2n}}\log \log N\right)\leq r_{k}(N)\leq {\frac {N}{(\log \log N)^{2^{-2^{k+9}}}}},$

其中 $n=\lceil \log k\rceil .$ 歐布萊恩（Kevin O'Bryant) 證出了上述的下界 ，其證明建基於貝哈連德（Felix Behrend)、羅伯特・藍欽，以及埃爾金（Michael Elkin) 先前的成果。上界由高爾斯證出。

對於較小的 _k,_ 可以找到比起一般情況更緊的上下界。當 _k_ = 3 時，布爾甘、希思 - 布朗 (Roger Heath-Brown)、塞邁雷迪，以及湯・桑德斯依次給出了愈來愈好的下界。目前所知的上下界為

　
: $N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq C{\frac {(\log \log N)^{4}}{\log N}}N.$

兩邊的界限分別由歐布萊恩 和布魯姆（Thomas Bloom) 給出。

當 _k_ = 4 時，本・格林和陶哲軒 證明了存在 _c_ > 0 使得

　
: $r_{4}(N)\leq C{\frac {N}{(\log N)^{c}}}.$

## 推廣

希勒爾・菲爾斯滕貝格和伊扎克・卡茨內勒松利用遍歷理論整明了塞邁雷迪定理的高維推廣。 高爾斯、沃伊傑赫・勒德爾和約澤夫・斯科肯 (Jozef Skokan) ，以及布蘭登・納格 (Brendan Nagle)、 勒德爾和馬蒂亞斯・沙赫特 ，和陶哲軒給出了各自的組合學證明。

亞歷山大・萊布門 (Alexander Leibman) 和維塔利・別爾格爾松 給出定理對多項式列的推廣：若 $A\subset \mathbb {N} $ 的上密度為正，且 $p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)$ 為滿足 $p_{i}(0)=0$ 的整值多項式，則存在無窮多組 $u,n\in \mathbb {Z} $ 使得對 $1\leq i\leq k$ 都有 $u+p_{i}(n)\in A.$ 萊布門和別爾格爾松的結果同樣適用於高維的情況。

塞邁雷迪定理的有限性版本可推廣至有限的加法群上，例如有限域上的向量空間。 定理在有限域上的類比，是有助理解原定理（在正整數集上）的模型。 所謂封頂集問題，就是要找出向量空間 $\mathbb {F} _{3}^{n}$ 所包含的無 3 項等差數列的最大子集的大小，即塞邁雷迪定理當 k = 3 時的界限。

格林 - 陶定理斷言，存在任意長的質數等差數列。此結論不能由塞邁雷迪定理推出，因為質數集的密度為 0. 本・格林和陶哲軒在其證明中引入了「相對性」（英語：relative) 的塞邁雷迪定理，該定理適用於任意具特定偽隨機性的整數子集（允許密度為 0)。大衛・康倫，雅各布・福克斯和趙宇飛 (Yufei Zhao) 其後亦給出了適用於更一般情況的相對性塞邁雷迪定理。

埃爾德什等差數列猜想（斷言倒數和發散的集合，必有任意長的等差數列）可以推出塞邁雷迪定理和格林 - 陶定理。

## 參見

* 與等差數列有關的問題
* 遍歷拉姆齊理論
* 算術組合學
* 塞邁雷迪正則性引理

## 參考資料

## 延申閱讀

* Tao, Terence. Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József , 編. Additive Combinatorics. CRM Proceedings & Lecture Notes **43**. Providence, RI: American Mathematical Society: 145–193. 2007. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005. arXiv:math/0604456 .

## 外部鏈結

* Announcement by Ben Green and Terence Tao （頁面存檔備份，存於網際網路檔案館） – the preprint is available at math.NT/0404188
* Discussion of Szemerédi's theorem (part 1 of 5) （頁面存檔備份，存於網際網路檔案館）
* Ben Green and Terence Tao: Szemerédi's theorem （頁面存檔備份，存於網際網路檔案館） on Scholarpedia
* 埃里克・韋斯坦因. SzemeredisTheorem. MathWorld.
* Grime, James; Hodge, David. 6,000,000: Endre Szemerédi wins the Abel Prize. Numberphile. 布雷迪・哈蘭. 2012 [2019-06-17]. （原始內容存檔於 2014-01-09）.