Erdős

生平

保罗・埃尔德什（Paul Erdős, 1913-1996）出生于奥地利布达佩斯（Budapest）一个犹太家庭（原始姓氏为 Engländer），但是他的父母都不信奉犹太教。

Lajos 和母亲 Anna（1880-1971）有在 Erdős 前有两个女儿，分别在三岁和五岁因猩红热去世，而这就发生在 Erdős 出生前几天。

这自然使得 Lajos 和 Anna 对 Erdős 极为溺爱，由于母亲担心他也会染上致命的儿童疾病，所以一直把他留在家里，直到他 10 岁才送他上学。Erdős 的父母均为数学教师，然而他的父亲被关进了俄国的战俘营长达六年，而母亲又需要长时间工作，还雇了一位德国籍女家庭教师照看他。

Erdős 当时通过翻阅父母的数学书籍来消磨时间。正如他后来回忆的那样：“我在很小的时候就爱上了数字，它们是我的朋友，我可以依赖它们，它们总在那里，总是一成不变。三岁时，我就在脑中乘出三位数逗得母亲的朋友们开心；四岁时，我就发现了负数。我告诉我母亲，如果你用 100 减去 250，就会得到 '150 below zero'。”

Erdős 刚满一岁不久，第一次世界大战爆发。Erdős 的父亲 Lajos 在俄军进攻奥匈军队时被俘，随后在西伯利亚度过了六年的囚禁生活。Lajos 一被俘，为了照顾 Erdős，同时由于母亲 Anna 白天在教学，一位德国籍的女家庭教师被雇来照看 Erdős。因失去了两个女儿，Anna 对 Erdős 的保护过度，在他早年大部分时间里不让他上学，而是聘请了家庭教师在家中辅导他。

第一次世界大战结束后，匈牙利局势陷入混乱，国家先是短暂成为民主共和国，随后由贝拉・昆（Béla Kun, 1886-1938）接管。Anna 当时被任命为学校校长，但在针对 Kun 政权的罢工行动中，她继续工作，纯粹出于对孩子们教育的关切，而非政治立场。

1919 年 7 月，随着罗马尼亚军队逼近布达佩斯，Kun 逃往维也纳，米克洛斯・霍尔蒂（Miklós Horthy de Nagybánya, 1868-1957）随即掌权，Anna 因未响应罢工号召而被归入打击对象，遭到解雇，并在 Horthy 部队街头屠杀犹太人和共产主义者的行动中险些失去生命。

1920 年对 Erdős 来说并非完全不幸，因为他的父亲 Lajos 从西伯利亚归来。他在囚禁期间学会了英语，但由于没有英语教师，他的发音带有浓重的口音。Lajos 开始教 Erdős 讲英语，这种奇特的英语口音伴随 Erdős 一生，成为他的一大特色。

在高中时期，Erdős 定期解答杂志《高中数学和物理》（Középiskolai Matematikai és Fizikai Lapok (KöMaL)）中提出的问题。

这是一份面向中学生的数学和物理月刊，目标读者的平均年龄仅为 17 至 18 岁。该刊物被认为在 19 世纪末和 20 世纪初匈牙利学生的数学成功中占有重要作用。

多年后，Erdős 还在该期刊上发表了关于初等平面几何问题的多篇文章。1962 年，匈牙利裔美国数学家拉斯洛・洛瓦斯（László Lovász, 1948-；1999 年 Wolf 奖，2021 年 Abel 奖）据说偶然读到 Erdős 的一篇文章，“着迷得几乎读了 20 遍”。

通过 KöMaL，Erdős 首次结识了图兰（Pál Turán, 1910-1976）和加莱（Tibor Gallai, 1912-1992）。

尽管匈牙利对犹太人进入大学有所限制，Erdős、Turan 和 Gallai 仍凭借在全国数学竞赛中的优异表现，成功进入了大学。当时年仅 17 岁的 Erdős 进入布达佩斯的彼得・帕兹马尼大学（Pázmány Péter University），仅用了四年就完成了本科学业并获得了数学博士学位。

1934 年，他完成了题为《关于某些算术级数的素数》（Über die Primzahlen gewisser arithmetischer Reihen）的博士论文。

他的导师是费耶尔（Lipót Fejér, 1880-1959），他还指导过众多其他匈牙利数学家，如冯・诺伊曼（John von Neumann, 1903-1957）、波利亚（George Pólya, 1887-1985）以及 Erdős 的朋友 Turán。

当时 Erdős 对于数学的优雅已有明确的看法。他认为，上帝拥有一本超限之书（The Book），其中记载着每个可能数学问题最短、最美的证明。对他来说，给予同事工作的最高赞誉便是说：“那正是摘自 The Book。” 至于 Erdős 对 Bertrand（Joseph Louis François Bertrand, 1822-1900）Postulate 的证明，没人怀疑 Erdős 确实在 The Book 中找到了。

在大学期间，他还与其他年轻的犹太数学家组成了一个自称 “匿名小组” 的团体，他们倡导一门新兴的数学分支 —— 拉姆齐理论（Ramsey Theory），其哲学基础在于认为完全的混乱是不可能存在的。一个具体的例子是在平面（即一个平坦的表面）上随机散布的点，Ramsey 理论的学者便猜想：无论这些点看起来多么杂乱无章，总会出现某种模式和结构。

他在 1934 年获得博士学位。随后，他获得了 Manchester 的博士后奖学金，此时他也因为犹太人身份而不得不离开匈牙利。在博士后期间，Erdős 在英国各地广泛旅行。1934 年他在 Cambridge 遇见了哈代（Godfrey Harold Hardy, 1877-1947）。

1935 年又在 Cambridge 遇见了乌拉姆（Stanislaw Marcin Ulam, 1909-1984），他与 Ulam 的友谊也促进他在后来做出往美国的决定。此时，他的流浪精神早已显露。“…… 自 1934 年以来，他几乎从未连续七晚睡在同一张床上。”

在 Manchester 博士后期间，Erdős 每年仍会三次访问 Budapest。1938 年 3 月，希特勒控制了 Austria，Erdős 只好取消原定于春季前往 Budapest 的访问，但在暑假期间还是访问了 Budapest。1938 年 9 月 3 日爆发的捷克危机（Czech crisis）迫使他匆忙返回英国。几周之内，Erdős 就踏上了前往美国的旅程，并在那里获得了 Princeton 的一个奖学金职位。

他本希望奖学金能够延长，但由于 Erdős 不符合普林斯顿（Princeton）的标准，他只获得了六个月的延长而非预期的一年。Princeton 方面认为他 “粗鲁且不合常规（uncouth and unconventional）”。

最终他接受了 Ulam 的邀请，到 University of Wisconsin-Madison 访问，从此开启了他终生在世界各大学之间辗转流浪的旅程。

1941 年 8 月发生的一件颇为离奇的小插曲。Erdős 与另外两位数学家在长岛一座军事无线电发射器附近被警察拦下。由于这三位数学家太过沉浸于数学讨论，竟然没有注意到 “NO TRESPASSING” 的标志。经过与警察友好交谈后，大家意识到并无恶意。但这件事为 Erdős 留下了一份 FBI 档案记录，后来被拿来对付他。

1943 年，Ulam 离开 Madison 前往新墨西哥州 Los Alamos，与其他数学家和物理学家一起从事原子弹项目。他曾邀请 Erdős 加入该项目，但尽管 Erdős 对面试表现出一定兴趣，他给出的回答显然不是面试官所期望的。Erdős 直言不讳地表示他希望战后回到 Budapest，这种诚实令面试官失望。

1943 年，Erdős 也离开 Madison 开始在 Purdue 大学担任兼职教职，之后还辗转于 Stanford 大学、Notre Dame 大学、Johns Hopkins 大学。在此期间，匈牙利的犹太人遭受了极其惨重的苦难，许多人被杀害，另有许多人被发配到奥斯维辛（Auschwitz）。当时在美国的 Erdős 几乎没有机会知道家乡的消息。

然而，1945 年 8 月，Erdős 收到一份电报，告知了他家中的情况：他的父亲于 1942 年因心脏病发作去世；他的母亲幸存下来，他的堂妹 Magda Fredro 被送往奥斯维辛，但也奇迹般地生还。此外 Erdős 的四位叔叔和姑姨均已被杀害。

1948 年底左右，Erdős 得以回访匈牙利，与仍然健在的家人和朋友重聚。接下来的三年里，他频繁往返于英国和美国之间，直至 1952 年接受了 Notre Dame 大学的一个临时职位。

1950 年代初期，美国掀起了对共产主义的强烈反感情绪。在此期间，Erdős 开始受到当局的怀疑。1954 年，在 Amsterdam 参会后返回美国时，美国移民官询问他对马克思的看法，Erdős 回答道：“我不能完全的判断，但是无疑他是一个伟大的人。” 随后又被问及是否会重返匈牙利，Erdős 回答道：“我不确定我是否会返回匈牙利因为我不确定我还能不能出来。我只计划去英国和荷兰。”

Erdős 最终未被允许返回美国，官方并未给出理由。档案显示，官方原因并非他上述回答中所表达的，而是由于他曾与一位后来从美国返回中国的中国数学家通信，以及他的 1941 年 FBI 档案记录。

事实上，2013 年，科迪・温彻斯特（Cody Winchester）根据《信息自由法》向 FBI 提交请求，要求在该局的中央记录系统中搜索所有与 “Paul Erdős” 相关的信息。该请求最终于 2014 年 3 月 27 日获得批准。在解密的 FBI 记录中，可以看出 FBI 从 1950 年代起便对 Erdős 及其行踪进行了数十年的跟踪。调查的结论似乎是 —— 正如利普顿（Beryl Lipton）后来所写：“FBI 花了几十年追踪数学家 Paul Erdős，最终得出的结论是，这家伙只是非常热爱数学。”

接下来的十年里，他大部分时间在以色列度过。1960 年代初，他曾多次请求允许返回美国，最终于 1963 年 11 月获得签证。但此时的 Erdős 已经养成在各大学之间辗转、并且暂居于各数学家中的习惯。他的流浪足迹遍及以色列、中国、澳大利亚以及其他 22 个国家。

期间，他有一个比较长久的落脚之处，那就是他的朋友格雷厄姆（Ronald Lewis Graham，1935-2020）家中。Erdős 与 Graham 在 1963 年的一次数论会议上相识，不久便开始了数学合作。Graham 为 Erdős 提供了一个可以居住的房间，也存放了他的论文，在许多方面充当了 Erdős 的秘书。

也是在这段时间开始，Erdős 靠着一种药物维持清醒，以一种传教士般的热情进行数学研究，经常一天工作 20 小时，最终发表了约 1500 篇论文，这一数字远远超过当时的同行。他的热情极具感染力，把数学变成了一种社交活动，鼓励那些最为内向的同事们共同合作。他曾说，他们共同的目标是揭示 The Book 中的秘密篇章。

数学界也产生了 Erdős number 的概念：Erdős 本人曾与 507 位合作者共同发表论文，在数学界，这 507 人因此获得了 “Erdős 数为 1” 的 “殊荣”，意味着他们曾与 Erdős 共同署名发表论文。与 Erdős 的合作者合作发表论文的人则被称为 Erdős 数为 2；而 Erdős 数为 3 则表示某人与某位与 Erdős 有过合作的人共同发表过论文。

1951 年，John von Neumann 因其在素数理论方面的贡献，将 Cole Prize 颁发给了 Erdős。1959 年，Erdős 参加了第一届 International Conference on Graph Theory，而图论正是他参与创立的领域之一。

在接下来的三十年中，他在组合数学、划分理论、集合论、数论以及几何等多个领域持续作出重要贡献 —— 他涉猎领域的多样性实属罕见。

1984 年，他赢得了数学界最丰厚的奖项 —— Wolf Prize，并将 5 万美元奖金中除 720 美元外的全部奖金捐出，用以在以色列设立以纪念其父母的奖学金。

Erdős 通常将他从奖项和其他工作中获得的收入捐赠给有需要的人和各种有价值的事业。他依靠大学和会议的津贴以及微薄的报酬维持生活，剩余的钱则用于设立现金奖励，奖励那些为他认为有趣的问题给出证明的人。奖金从 25 美元到数千美元不等。

其中最著名的 “Erdős 问题” 可能是考拉兹猜想（Collatz conjecture）或叫 猜想：是指对于每一个正整数，如果它是奇数，则对它乘 3 再加 1，如果它是偶数，则对它除以 2，如此循环，最终都能够得到 1。Collatz 猜想由考拉兹（Lothar Collatz, 1910-1990）在 1937 年左右提出，当时他刚刚获得博士学位。

为此 Erdős 提供了 500 美元奖金。他在谈到 Collatz 猜想时说：“数学还没准备好应对这样的问题。”

目前最好的相关结果由陶哲轩在 2022 年发表，他证明对于几乎任何一个大于 0 的整数 ，Collatz 猜想对于 的序列的下界一定会低于，这里 可以取任何一个定义在大于 0 的整数上的实值函数且满足 ，比如 可以取 ， 等等。

5000 美元奖金的问题则是：Erdős conjecture on arithmetic progressions—— 如果一个整数序列的倒数之和发散，那么该序列中必包含任意长度的等差数列（If the sum of the reciprocals of a sequence of integers diverges, then the sequence contains arithmetic progressions of arbitrary length.）。

这个问题和目前最高悬赏（10000 美元）的未解决问题密切相关：

对于任何 ，令 表示从集合 中选出一个子集的最大可能的大小，使得该子集中不包含任何非平凡的 项等差数列。10000 美元的问题是找到 的渐进公式。这个问题只对 有意义，目前对于 人们不知道任何渐进公式。

而 Erdős conjecture on arithmetic progressions 则本质上是寻找 的上界的好的估计，例如若能证明：

对所有 成立，（这里 可以依赖于 的选取）则足够证明猜想。

对（Kelley-Meka, 2023）和（Green-Tao, 2017）有一些好的估计。对于一般的，James Leng、Ashwin Sah、Mehtaab Sawhney 在 2024 年有一个结果，但还不足以证明 Erdős 上述猜想。

Erdős conjecture on arithmetic progressions 的一个重要推论是 Green-Tao 定理：素数中包含任意长的等差数列。

在纪录片《N is a Number: A Portrait of Paul Erdős》中，讲述了一位年轻数学家的故事：该数学家被 Harvard 录取，但他的父母尽管有能力支付学费，却拒绝付款。Erdős 仅与这位学生偶遇一次，就给了他 1000 美元，并说道：“如果你能还给我就还给我；如果还不了，请帮别人还。”

他还当选为世界上众多最负盛名的科学学会的成员，包括 Hungarian Academy of Sciences（1956 年）、National Academy of Sciences（1979 年）和 Royal Society（1989 年）。

Erdős 一直证明和提出猜想直到 83 岁，最终于 1996 年在华沙参与一场几何学会议数小时后，因心脏病发作而逝世。

当被问及如何最好地描述他的朋友 Erdős 时，斯宾塞（Joel Spencer, 1946-）曾写道：“数学真理是永恒不变的；它存在于物理现实之外…… 这是我们的信仰，是我们最核心的动力源泉。然而，当我们试图向非数学界的朋友描述这种信念时，就如同向无神论者描述上帝的存在。Erdős 用他的一生践行了对数学真理的信仰。他将自己非凡的天赋与精力全部奉献给了数学的圣殿。对于这项探索的重要性与绝对性，他从未有过丝毫怀疑。”

Erdős 对数学的贡献既众多又广泛。但基本上，Erdős 是一个问题解决者，而非理论构建者。他最感兴趣的问题主要集中在组合数学、图论和数论等领域。然而，他不仅仅满足于解决问题，而是要求以一种优雅且初等的方式来解决。Erdős 不喜欢通过提供一系列复杂的步骤来构成形式证明。

他在 1984 年获得沃尔夫奖，颁奖词为：
“在数论、组合数学、概率论、集合论等领域做出开创性贡献，并通过个人魅力激励全球数学家。”

贡献

一、Bertrand's Postulate

1845 年，Bertrand 猜测，对于所有 ，总存在至少一个素数位于 和 之间。Bertrand 自己验证了在区间 内的所有数均满足这一命题。

该猜想在 1852 年由切比雪夫（Pafnuty Lvovich Chebyshev，1821-1894）证明；1919 年，拉马努金（Srinivasa Ramanujan，1887-1920）利用 函数的性质给出了一个更简单的证明。

1932 年，19 岁的 Erdős 发表了他的第一篇论文，利用二项式系数和 Chebyshev 函数 给出了一个令人惊讶的初等证明。论文题为《关于 Chebyshev 一个定理的证明》（Beweis eines Satzes von Tschebyschef），刊登于 Acta Scientifica Mathematica，这也是他博士论文的主要成果。

Erdős 的证明依赖于如下的一个初等结果：

Erdős 证明的第一部分表明，如果不存在满足 的素数 ，则我们可以对二项式系数设定一个上界，该上界小于 ，除非 属于 “较小” 的情况，从而证明了 Bertrand’s Postulate 对于所有充分大的 成立；第二部分则处理 较小时的情况，这部分内容通过人工验证完成。

二、素数定理（The Prime Number Theorem）

1948 年 7 月，Erdős 在 IAS 遇到了挪威数学家塞尔伯格（Atle Selberg，1917-2007）。经过简短的交流，一份初等证明版本的素数定理问世。

最初，该定理的猜想源自于勒让德（Adrien‑Marie Legendre，1752‑1833）、高斯（Johann Carl Friedrich Gauss，1777‑1855）和狄利克雷（Johann Peter Gustav Lejeune Dirichlet，1805‑1859）各自独立的工作。

其内容为：

当 趋向无穷大时，素数计数函数， 不超过 的素数的个数，将近似于 。

Prime Number Theorem

be the prime‑counting function
(number of primes less or equal to , for any real number )

该定理在 1896 年由阿达玛（Jacques Hadamard，1865-1963）和普桑（Charles Jean de la Vallée Poussin，1866-1962）独立证明，利用了 Riemann zeta 函数。1948 年 3 月，Selberg 建立了渐近公式

其中，Jacobi theta 函数 等于所有小于或等于 的素数的对数之和。

到 7 月时，Selberg 与 Erdős 均利用该公式证明了素数定理。两人究竟谁先证明这一结果曾引发一定的优先权争议，此后他们便再未合作。

1949 年 Selberg 发表了他的证明。次年，Selberg 因这一工作为主要原因获得了 Fields 奖。Erdős 也在《美国国家科学院院刊》（Proceedings of the National Academy of Sciences of the United States of America）上发表的论文《关于初等数论中的一种新方法，可得到素数定理的初等证明》（On a new method in elementary number theory which leads to an elementary proof of the prime number theorem）论文也发表于 1949 年。

三、Ramsey 理论

在 Erdős 最重要的成果中，他对 Ramsey 理论发展的贡献尤为突出。Ramsey 理论是数学的一个分支，专门研究 “在何种条件下必然出现秩序”。

拉姆齐（Frank Plumpton Ramsey，1903-1930）的原始问题是从一个完全图开始，总存在有限数（Ramsey number），其值取决于整数，满足若将足够大（定点个数大于等于）的完全图各边染红蓝两色，则不论如何染，必定有红色的 阶完全图或蓝色的 阶完全图。

如。

Ramsey 理论则引申这一现象：一个典型的问题是，从一个数学结构开始，将其分割成若干部分。典型的问题为：“原始结构必须有多大，才能保证至少有一部分具备某种特定而有趣的性质？”

其中一个例子是 Erdős - Szekeres 定理（1935）：该定理叙述为对于任给 和 ，任何长度至少为 的由互不相同的实数组成的序列，必包含一个长度为 的单调递增子序列或一个长度为 的单调递减子序列。该结果最早发表于 Erdős 和塞凯雷斯（George Szekeres, 1911-2005）1935 年那篇具有影响力的论文《几何里的组合问题》（A Combinatorial Problem in Geometry）中。

子序列是指从原序列中删除部分元素而不改变原有顺序所得的序列。

例如，给定序列 ，其子序列包括 、 、 、 、 、 、 、 。

例：对于 ， ，该公式告诉我们，任意三个数字的排列都必有一个长度为 的递增子序列或一个长度为 的递减子序列。

在数字 的六种排列中：

• 拥有一个由全部三个数字构成的递增子序列；
• 拥有一个递减子序列： ；
• 拥有一个递减子序列： ；
• 拥有两个递减子序列： 和 ；
• 拥有两个递减子序列： 和 ；
• 拥有三个递减子序列： 、 和 。

在论文中，Erdős 与 Szekeres 通过归纳法证明了

其中 表示使得任一由 个实数组成的序列必包含一个长度为 的单调子序列的最小整数。

四、The Happy Ending Theorem

同样是在 Ramsey 理论，1932 年，Erdős 与 Szekeres 的共同朋友艾丝特・克莱恩（Esther Klein, 1910-2005）观察到：（The Happy Ending Theorem）平面上任意一组处于一般位置的五个点，总存在其中的四个点构成一个凸四边形。

这一问题及其定理是推动 Ramsey 理论进一步发展的首批有影响力的成果之一。Erdős 称这一结果为 “Happy Ending Problem”，因为它最终促成了 Szekeres 与 Klein 的婚姻。

该定理是 Erdős 与 Szekeres 在 1935 年同篇论文中证明的更一般定理的一个特例，该定理表述为：对于任一正整数 ，平面上任意足够大的处于一般位置的有限点集，都包含一个由 个点构成的凸多边形的顶点子集。

同时，在该论文中，Erdős 与 Szekeres 还提出了猜想：

（The Erdős-Szekeres Conjecture, 1935）
在任一处于一般位置的点集内，包含 个点构成凸多边形所需的最小点数 为 。

目前这个问题在 小于 7 的时候被解决， 的情况是通过计算机证明。

五、Erdős–Rényi 随机图

在图论这一数学领域中，Erdős–Rényi model 是生成随机图或随机网络演化的两个密切相关的模型之一。这一模型以匈牙利数学家 Paul Erdős 和雷尼（Alfréd Rényi, 1921-1970）的名字命名，由他们在 1959 年提出。此后吉尔伯特（Edgar Gilbert, 1923-2013）与 Erdős 和 Rényi 同时且独立地提出了另一种模型。

在 Erdős–Rényi model 中，对于固定的顶点集和固定的边数，所有图的出现概率均相等。具体的来讲他们定义如下： 型（Erdős-Rényi model）：

在 模型中，先确定图中有 个不同的节点（带有表示，因此视为不同的），然后从所有可能的边中（在 个节点中，每两个节点之间都有可能连一条边，总共可能有 条边）随机均匀地挑选出 条边来构成图。

换句话说，每一张含有 条边的图都有同等的机会被生成。如当 ， 的图共有三种可能，每种发生的可能性为 。

Erdos 和 Rényi 在最初的文章中提出了四个问题，希望知道这些问题在 趋于无穷时的概率：

1、 模型中得到一个完全连通图的概率是多少？

2、 模型中得到的图的最大连通分量（子图）恰好具有 个顶点的概率是多少？其中 。

3、 模型中得到的图恰好有 个连通分量组成的概率是多少？其中 。

4、如果在一个有 个顶点的图中按以下方式依次随机增加边：每次随机添加一条边，每一步结束后，对于所有尚未被选中的边，它们都有相同的概率在下一步被选中。我们持续进行这个过程，直到图完全连通，那么图达到完全连通所需的步数 等于某个给定整数 的概率是多少？

Erdos 和 Rényi 对上述四个问题当 等于
的整数部分（ 是一个正实数）的情形给出了完整的解答，计算出了上述问题的概率。

答案大致的形式是一些 关于 的函数的指数

Erdős-Rényi model 不仅为数学家们研究图的性质提供了基本工具，而且在现实中也被广泛应用于网络科学、计算机网络、社交网络、生物系统和流行病传播等领域，帮助我们理解和预测各种复杂系统中随机连接和结构演变的规律。