什麼是埃爾德什差異問題?

12-03

所以說有些人啊，總是喜歡搞個大新聞。
Tao+Erdos合起來，配上一個博客學術。簡直帥呆了。
結果那麼多人微博上跟風轉來轉去，連個arxiv號都不掛。
數學科普還任重道遠啊。

回到正題，先上arxiv http://arxiv.org/abs/1509.05363
然後搬運一下具體的問題：
考慮序列，取值為 $pm 1$ ，即 $f:mathbb{N} ightarrow {1,-1}$ .
Erdos是問這個量，即所謂的差異
$sup_{n,din mathbb{N} }|sum_{i=1}^nf(id)|$
對任意的f，是否無限。
Tao證明的版本要比這個強得多。
他證明了向量值序列的版本：即設H是一個Hilbert空間。若f是取值與H上單位球的序列，即
$f:mathbb{N} ightarrow H, ||f(n)||_H=1$
差異 $sup_{n,din mathbb{N} }||sum_{i=1}^nf(id)||_H$ 總是無限的。
作為推論，取 $H=mathbb{R}$ ，原命題就成立了。
證明中的技術和結果的意義我一概不懂，僅作一個勤勞的搬運工。

這是一個值得科普的好問題。

2015 年 9 月 17 日，陶哲軒 宣布破解 埃爾德什差異問題（the Erd?s Discrepancy Problem)（論文地址：http://arxiv.org/abs/1509.05363），實在是可喜可賀。

埃爾德什差異問題 當然是一個很難的問題。從提出者和破解者的履歷便可見一斑：

Terence Tao 有多厲害，相信大家都知道：12 歲獲得 IMO 金牌，31 歲獲得菲爾茲獎等，都是極其厲害的成就。當然，讓我印象深刻的，還有這麼一段描述：「陶哲軒的數學生涯 也並非一帆風順。9歲多時，他未能入選澳大利亞隊，去參加國際數學奧林匹克競賽。」
但我們更應該知道，Paul Erd?s 也是一個很厲害的人，至少，從成就上來說，他可能比現在的 Tao 更厲害：他發表論文高達 1475 篇，為現時發表論文數最多的數學家（第二位為歐拉）；曾和 511 人合寫論文。如果你看過《我的大腦敞開了》或《數字情種》，你一定會對這個神奇的數學家留下深刻的印象。

然而，與兩人的光輝履歷形成鮮明對比的是，「埃爾德什差異問題」從 問題描述 來說，卻是相當簡潔且便於理解的——通過適當的解釋，只要是小學畢業了的人，都可以理解這個問題在說什麼。

埃爾德什差異問題的描述是這樣的：

對於任意無窮數列 $f:mathbb{N} ightarrow {1,-1}$ ， $sup_{n,din mathbb{N} }|sum_{i=1}^nf(id)| ightarrow infty$

接下來，我嘗試用 小學生可以理解的方式 來解釋這個問題：

（1）首先，有一個無限長的數列，數列中的每個數，都是由 1 和 -1 組成的。

比如數列 A：1，-1，-1，-1，1，-1……就是一個滿足條件的數列。

（2）接下來，我們要取數列的某些項，這些項在數列中的位置都是某個自然數 N 的倍數，並且是從頭開始的連續幾個倍數（即第 N 、2N、3N……項）。

比如，我們可以取數列的第 1、2、3、4 項（在 A 中分別為 1，-1，-1，-1），因為它們都是 1 的倍數，且為前 4 項；或者取數列的第 2、4、6 項（在 A 中分別為 -1，-1，-1），因為『它們都是 2 的倍數，且為前 3 項。但我們不能取數列的第 1、2、4 項或者第 4、6、8 項，因為它們不是【從頭開始】的【連續幾個倍數】。

（3）對於（2）中的每種取法構成的新的數列，我們可以求該數列所有項的和。我們要證明的命題是：無論原來的無窮數列長什麼樣，我們都可以找到一種取法，使得新數列的和的絕對值大於任意給定的自然數 C。

——————————

遇到這樣的問題，一個很自然的思路是：試試 C 比較小的時候，我們是否可以給出證明。

當 C=0 時，結論是顯然的。

我們只要取數列的第 1 項就可以，它的絕對值肯定大於0。

當 C=1 時，結論就不那麼顯然了。

我們要證明的是，對任意滿足要求的數列， $sup_{n,din mathbb{N} }|sum_{i=1}^nf(id)|>1$

我思考了這個問題，給出了自己的解法，並認為這可以成為一道中學數學競賽題。為了便於理解，解答過程不使用超過初中的數學。

**********

證明：

用反證法。假設存在一個數列，滿足 $sup_{n,din mathbb{N} }|sum_{i=1}^nf(id)|leq 1$
於是我們有兩個簡單的推論：

對任意正整數 d，數列的第 d 項和第 2d 項的和為 0——反之，它們的和必為 2 或-2，矛盾；
對任意正整數 d，數列的第 2d-1 項和第 2d 項的和為 0——反之，設 k 為最小的不滿足該條件的數，即第 2k-1 項和第 2k 項的和為 2 或 -2，則數列的前 2k 項的和為 2 或 -2，矛盾；

不失一般性，設數列第 1 項為 1。

由推論2 =&> 第 2 項為 -1；
由推論1 =&> 第 4 項為 1；
由推論2 =&> 第 3 項為 -1；
由推論1 =&> 第 6 項為 1；
由推論2 =&> 第 5 項為 -1；
由推論1 =&> 第 10 項為 1；
由推論2 =&> 第 9 項為 -1；

考慮數列的第 12 項：
由於數列的第 6 項為 1，由推論1 =&> 第 12 項為 -1；
但此時數列的第 3、6、9、12 項分別為 -1，1，-1，-1，其和為 -2，與題設矛盾！

故假設不成立，結論成立。

**********

好了，通過一陣折騰，我們證明了 C=1 的情況是成立的。
那麼，C=2 的時候，會是什麼情況呢？

2014 年 2 月，英國利物浦大學的 Alexei Lisitsa 和 Boris Konev，利用計算機，幾近於暴力驗證的辦法，驗證了 C=2 的特殊情況。但是，計算機驗證過程產生數據達到 13G，甚至超過整個Wikipedia 網站的總數據量。

C=3 呢？

相同的計算機演算法，沒有給出結果……

——————————

然後，陶哲軒登場了！

他證明了一個更強的命題：

對於任意無窮數列 $f:mathbb{N} ightarrow H, ||f(n)||_H=1$ ， $sup_{n,din mathbb{N} }||sum_{i=1}^nf(id)||_{H} ightarrow infty$

這段話是什麼意思呢？

首先，數列不再局限於由 1 和 -1 組成了，只要滿足 $||f(n)||_H=1$ 即可，
其中 H 代表希爾伯特空間。

當然，對於非數學系的同學來說，要理解希爾伯特空間可能有些困難。
為了讓高中生也能有一個概念，我們取一個該空間的子集：複數集。

即，對於數列的每一項，只要滿足模等於 1 即可。

比如，數列可以長成這樣： $1,frac{3}{5}+frac{4}{5}i, -frac{8}{17}+frac{15}{17}i,-1, frac{21}{29}-frac{20}{29}i, -frac{sqrt{3} }{2}-frac{i}{2} ,$ ……

在這種情況下，Tao 證明了：

我們總可以找到滿足要求的子數列，使得它們的和的模大於任意一個自然數。

現在，你是不是感覺到，這個結論好像真的很強？

然而我們可不能忘記，希爾伯特空間比複數集還要大得多得多。

對了，剛才忘了說，陶哲軒從接觸這個問題，到最終發表論文，只用了不到兩周：
他並沒有專門去攻克埃爾德什差異問題，只是在研究其他問題時，發現恰好和這個問題有關，於是「順手」證明了一下而已。
（註：這其實是一個略帶誇張的說法，評論區 @chen ke 指出，Tao自己在這篇paper里就說明了這個結果是基於polymath project的成果，而他本人就參加了這個項目）

所以，如果陶哲軒的證明最終被認為是正確的，
那麼對於我們而言，除了默默圍觀和讚歎，
還能做什麼呢？

【完】

********************
【如需轉載，請聯繫作者】

埃爾德什差異問題由數學家保羅·埃爾德什（Paul Erd?s）在1932年提出的猜想，指的是在任意只由1和-1組成的無限數列中，能找到項與項間等距的有限子列，使子列各項之和的絕對值大於一個任意大的常數C。

一個初等證明：（極有可能是錯誤的，請知友指正）
S 是一個有無限元素的集合，每個元素是一個無限序列，每個序列中的元素要麼是1，要麼是-1.
從S中任意取一個元素，命名該元素為 LIST.

１。複製LIST　[...1.........-1....] k次 (k是奇數），分別向右移動１s，２s... ks個單位。形成如下隊形：

[...1.........-1....] [...1.........-1....] 右移動1s個單位的結果 [...1.........-1....] 右移動2s個單位的結果 ... + -------------------------------- = FINAL= [.....a.....b.....]

２。把Ｋ＋１個ＬＩＳＴ相加，得到一個新列表ＦＩＮＡＬ：任意取一個元素a，它的值必然在[-K-1,K+1]之間，不難證明：|a| 不可能是奇數，而且｜a｜= 0 的概率最大，其次是｜a | = 2 ,... 其中｜a | = k+1的概率 [記為P(k+1) ] 最小，雖然很小，但大於０。P(k+1)只和變數K有關。

３。因為ＦＩＮＡＬ中元素的個數是無限的，所以必然存在一個元素b，| b | = k+1。（實際上存在無窮多個這樣的元素）

４。令Ｋ &> C，得到｜b | &> Ｃ。

５。這個等價與ＬＩＳＴ中必然存在Ｋ＋１個相隔 s （即等距）的１或者－１。

６。取這Ｋ＋１個數，即滿足猜想的要求。

證畢。

證明是錯誤的嗎？

推廣：
同理可證：若無限數列中任意元素a （a 為複數或者其它什麼未知的數，只要有絕對值的定義）, 都有｜a ｜ &>　０，那麼，必然存在一個等距的有限子列，其和的絕對值大於給定的常數Ｃ。

更強的是，如果ＬＩＳＴ中存在無限多的元素a, 滿足｜a ｜&> 0, 那麼即使存在無限多的元素b, |b| &<= 0 ( 絕對值小於0，也許是可能的，看如何定義一個未知數據的絕對值了），結論也成立！（這個結論太不可思議了！）