檢視埃爾德什-圖蘭關於加法基的猜想的原始碼

艾狄胥-圖蘭猜想是加性數論中一個歷史悠久的未解問題（請勿與艾狄胥等差數列猜想混淆），由保羅·艾狄胥和帕爾·圖蘭於1941年提出。

該猜想涉及加性基，即自然數的子集，其性質為每個自然數都能表示為基中有限個元素的和。粗略地說，該猜想指出，這種表示法的數量也不可能是有界的。

==背景與陳述==
此問題涉及稱為加性基的自然數（通常記為 <math> \mathbb{N} </math>）子集。如果存在某個正整數 <math>h</math>，使得每個足夠大的自然數 <math>n</math> 都可以寫成 <math>B</math> 中至多 <math>h</math> 個元素的和，則稱子集 <math>B</math> 為有限階（漸近）加性基。例如，自然數本身就是一個1階加性基，因為每個自然數顯然都是至多一個自然數的和。拉格朗日四平方和定理指出，正平方數集合是一個4階加性基。在這方面，另一個非常不平凡且著名的結果是維諾格拉多夫定理。

人們自然會問這些結果是否最優。事實證明，拉格朗日四平方和定理無法改進，因為有無窮多個正整數不能表示為三個平方數的和。這是因為任何可表示為三個平方數之和的正整數，除以8的餘數都不會是7。然而，我們或許可以預期，一個與平方數一樣稀疏的集合 <math>B</math>（意指在給定區間 <math>[1,N]</math> 中，<math>[1,N]</math> 內大約有 <math>N^{1/2}</math> 個整數屬於 <math>B</math>），若沒有這種明顯的缺陷，應具有這樣的性質：每個足夠大的正整數都是 <math>B</math> 中三個元素的和。這可以從以下概率模型得出：假設 <math>N/2 < n \leq N</math> 是一個正整數，且 <math>x_1, x_2, x_3</math> 是從 <math>B \cap [1,N]</math> 中「隨機」選取的。那麼，從 <math>B</math> 中選取一個給定元素的概率大約是 <math>1/N^{1/2}</math>。接著可以估計期望值，而在這種情況下，期望值會相當大。因此，我們「預期」<math>n</math> 有許多種表示法可寫成 <math>B</math> 中三個元素的和，除非存在某種算術障礙（意指 <math> B </math> 在某種程度上與具有相同密度的「典型」集合非常不同），就像平方數的情況一樣。因此，我們應預期平方數在將正整數表示為四個元素之和方面相當低效，因為對於那些通過了算術障礙的正整數 <math>n</math>，應該已經有很多種表示法可寫成三個元素的和。審視維諾格拉多夫定理可以迅速發現，例如，質數在將正整數表示為四個質數之和方面也非常低效。

這引出了一個問題：假設 <math>B</math> 與平方數或質數不同，在將正整數表示為 <math>B</math> 中 <math>h</math> 個元素的和方面非常高效。它可以有多高效呢？最佳的可能性是，我們可以找到一個正整數 <math>h</math> 和一個集合 <math>B</math>，使得每個正整數 <math>n</math> 都能以唯一的方式表示為 <math>B</math> 中至多 <math> h </math> 個元素的和。如果做不到，或許我們可以找到一個 <math>B</math>，使得每個正整數 <math>n</math> 至少有一種、至多有 <math>S(h)</math> 種方式表示為 <math>B</math> 中至多 <math>h</math> 個元素的和，其中 <math>S</math> 是 <math>h</math> 的函數。

這基本上就是保羅·艾狄胥和帕爾·圖蘭在1941年提出的問題。事實上，他們對這個問題猜測了一個否定的答案，即如果 <math>B</math> 是自然數的一個 <math>h</math> 階加性基，那麼它將正整數表示為至多 <math>h</math> 個元素之和的效率就不可能太高；<math>n</math> 的表示法數量，作為 <math>n</math> 的函數，必定會趨於無窮大。

==歷史==

此猜想由保羅·艾狄胥和帕爾·圖蘭於1941年共同提出。在原始論文中，他們寫道：

：「(2) 如果對於 <math>n > n_0</math>，<math>f(n) > 0</math>，那麼 <math>\varlimsup_{n \rightarrow \infty} f(n) = \infty</math>」，

其中 <math>\varlimsup_{n \rightarrow \infty}</math> 表示上極限。此處的 <math>f(n)</math> 是將自然數 <math>n</math> 寫成 <math>B</math> 中兩個（不必然相異）元素之和的方式數量。如果對於足夠大的 <math>n</math>，<math>f(n)</math> 恆為正，則稱 <math>B</math> 為（2階）加性基。這個問題已引起廣泛關注，但至今仍未解決。

1964年，艾狄胥發表了此猜想的一個乘法版本。

==進展==

儘管猜想仍未解決，但在這個問題上已取得一些進展。首先，我們用現代語言來表述這個問題。對於給定的子集 <math>B \subset \mathbb{N}</math>，我們定義其表示函數為 <math>r_B(n) = \#\{(a_1, a_2) \in B^2 \mid a_1 + a_2 = n \}</math>。則該猜想可表述為：如果對於所有足夠大的 <math>n</math>，<math> r_B(n) > 0 </math>，那麼 <math> \limsup_{n \rightarrow \infty} r_B(n) = \infty </math>。

更一般地，對於任意 <math>h \in \mathbb{N}</math> 和子集 <math>B \subset \mathbb{N}</math>，我們可以定義 <math>h</math> 表示函數為 <math>r_{B,h}(n) = \#\{(a_1, \cdots, a_h) \in B^h \mid a_1 + \cdots + a_h = n \}</math>。如果對於所有足夠大的 <math>n</math>，<math>r_{B,h}(n) > 0</math>，我們就說 <math>B</math> 是一個 <math>h</math> 階加性基。從一個基本的論證可以看出，如果 <math>B</math> 是一個 <math>h</h> 階加性基，則：

:<math>\displaystyle n \leq \sum_{m=1}^n r_{B,h}(m) \leq |B \cap [1,n]|^h</math>

因此我們得到下界 <math>n^{1/h} \leq |B \cap [1,n]|</math>。

最初的猜想源於艾狄胥和圖蘭為西頓問題（見：西頓數列）尋求部分解答。後來，艾狄胥著手回答西頓提出的以下問題：一個 <math> h </math> 階加性基 <math> B </math> 能多接近下界 <math> |B \cap [1,n]| \geq n^{1/h} </math>？1956年，艾狄胥在 <math>h=2</math> 的情況下回答了這個問題。艾狄胥證明了存在一個2階加性基 <math>B</math> 和常數 <math>c_1, c_2 > 0 </math>，使得對於所有足夠大的 <math>n </math>，<math>c_1 \log n \leq r_B(n) \leq c_2 \log n </math>。這尤其意味著，存在一個加性基 <math>B</math> 使得 <math>r_B(n) = n^{1/2 + o(1)} </math>，這基本上是最佳可能。這促使艾狄胥提出了以下猜想：

：如果 <math>B</math> 是一個 <math>h</math> 階加性基，那麼 <math> \limsup_{n \rightarrow \infty} r_B(n)/\log n > 0.</math>

1986年，愛德華·維爾辛證明了一大類加性基（包括質數）都包含一個子集，該子集本身也是一個加性基，但比原始集合稀疏得多。1990年，艾狄胥和普拉薩德·V·泰塔利將艾狄胥1956年的結果推廣到任意階的基。2000年，V. Vu 利用哈代-李特爾伍德圓法及其多項式集中結果，證明了在華林基中存在稀疏子基。2006年，博溫、崔和朱證明了對於所有加性基 <math>B</math>，<math>f(n)</math> 最終會超過7。
==參考文獻==

[[分類: 待校正]]