埃尔德什与概率方法:用偶然性证明事物的存在

保罗·埃尔德什没有家,没有通常意义上的工作,几乎没有任何财产。他一生提着一只手提箱,在各所大学之间辗转,出现在同行的门前,说一句"我的大脑敞开着",然后留下一串定理和未解问题,数学家们至今仍在钻研。在他创造的一切之中,有一个思想因为彻底改变了证明的方式而格外突出。它叫做概率方法,而其核心是一个听起来几乎像作弊的招数:通过拒绝去构造,来证明某物存在。

问题:秩序何时不可避免?

先从一个听起来很简单的谜题说起。在一个六人聚会上,任意两人要么是朋友,要么是陌生人。事实证明,在任意六个人中,你总能找到三个彼此全是朋友的人,或者三个彼此全是陌生人的人。秩序逼迫自己出现。研究这种情形何时必然发生的数学分支叫做拉姆齐理论,它给这个问题赋予了一个数。

拉姆齐定理保证这些数存在,但它并没有说它们有多大。自然的追问是:一个群体能大到什么程度,同时仍然避免任何规模为k的单色集团?回答这个问题意味着要证明存在这样一种巧妙的染色。而恰恰在这里,靠手工去构造一种变得毫无希望,因为可能的染色数目大得惊人。

埃尔德什的招数:不去构造它,而是去计数它

埃尔德什在1947年的洞见,是不再试图设计一种好的染色,而是完全随机地去染色,然后让算术来完成这项工作。这个论证短到可以完整地跟下来。

把最后这一步再读一遍,因为这正是全部的魔法所在。我们从未给出一种好的染色。我们从未描述过一种。我们证明了平均的染色如此接近无瑕,以至于一种完美的染色被迫存在于那一堆里的某处。这个证明把关于某个特定对象的确定性交到你手里,却不指向任何特定的对象。

为什么这是革命性的

在埃尔德什之前,证明某物存在几乎总是意味着构造出它,或者至少描述一个能够构造出它的过程。概率方法打破了这种预期。它确立了随机性本身可以充当一种证明:如果一次随机尝试以任何大于零的概率成功,那么成功就是可能的,就这么简单。

这种非构造性的味道,使这个论证跻身于数学中某些最优雅的结果之列。康托尔的对角线论证同样证明了某物的存在,即一个从任何列表中缺失的数,靠的是纯粹的逻辑力量而非显式的构造。两者共享那种安静而几乎令人不安的力量:结论无懈可击,尽管它从不向你展示它所许诺的那个东西。这里的随机性建立在直观理解概率中所涵盖的同一基础之上,在那里,期望值这一思想,也就是第三步的引擎,从头开始被建立起来。

埃尔德什问题及其 AI 时刻

埃尔德什不只是证明定理。他提出问题,数以百计,常常附上小额现金奖励,从给一道棘手习题的几美元,到给一个他相信确实深刻的问题的数千美元不等。其中许多问题至今仍未解决,它们被仔细地编目并维护在erdosproblems.com上。

其中的禅意

概率方法之所以美,与一个好的魔术之所以美,理由是相同的:你看着每一步,你找不出自己被骗的地方,可结果仍然让人觉得不可能。这里没有任何手法上的花招。期望值确实小于一,而一个小于自身平均值的整数确实必然在某处跌到零。确定性是彻底的,构造是缺席的,而这两件事同时为真。

这就是埃尔德什留下的那个长久的教训。存在与构造不是一回事。有时,要知道某个完美的对象就在那里,最干净的办法是证明平均的对象几乎完美,然后让那道差距来完成其余的事。还有一个结果,其中单单一行就把看似毫不相干的思想系在了一起,欧拉恒等式提供了另一种美:埃尔德什从计数中变出存在,而欧拉则钉死了一个精确而不可避免的数。