一次家庭作業(yè)意外搞定40年前的數(shù)學(xué)猜想，牛津小哥：我只研究了幾禮拜

白交 2022-03-13 12:55:15 來源：量子位

曉查 蕭簫 發(fā)自 凹非寺

量子位 | 公眾號 QbitAI

只是完成一次普通家庭作業(yè)，就把困擾了數(shù)學(xué)家們幾十年的猜想搞出了新花樣？！

沒錯(cuò)，這是來自牛津大學(xué)的Thomas Bloom的親身經(jīng)歷。

在一次閱讀小組的論文分享上，他被要求解讀一篇2003年發(fā)表在《數(shù)學(xué)年刊》上的經(jīng)典論文。

這篇論文證明了一個(gè)與“最古老數(shù)學(xué)問題”埃及分?jǐn)?shù)有關(guān)的猜想。

簡單來說，猜想認(rèn)為：將大于1的整數(shù)任意分成有限個(gè)子集，必然有一個(gè)子集中的部分整數(shù)倒數(shù)加起來為1，例如只要有一個(gè)子集中有2、3、6，就有1 = 1/2 + 1/3 + 1/6。

這一猜想被命名為Erd?s-Graham猜想。

然而，這版2003年的證明還有很多待解決的疑惑：

Thomas Bloom在解讀論文的過程中，也發(fā)現(xiàn)這版證明對子集的要求有點(diǎn)高，很多特殊情況下沒辦法成立。

再仔細(xì)一看，他突然發(fā)現(xiàn)，這版證明還存在著可以繼續(xù)改善的地方！

于是借著這次交作業(yè)的機(jī)會，Thomas Bloom在這篇論文的基礎(chǔ)上提出了一種“強(qiáng)化版”證明思路，整個(gè)過程甚至只用了幾周時(shí)間。

就連數(shù)論領(lǐng)域著名學(xué)者、蒙特利爾大學(xué)教授Andrew Granvill都感嘆這種做法的不可思議：

此前我只是覺得，這是一個(gè)不可能被解決的問題，任何頭腦正常的人都沒法做到。

所以，這一猜想究竟是什么，Bloom的證明方法又究竟“不可思議”在哪里？

一個(gè)與“最古老數(shù)學(xué)問題”有關(guān)的猜想

在數(shù)學(xué)里，任意有理數(shù)都可以表示成分?jǐn)?shù)，且分子分母都是整數(shù)。

但是在3000多年前的古埃及，他們的分?jǐn)?shù)只有分子為1一種情況，我們現(xiàn)在叫它單位分?jǐn)?shù)。

也就是說，他們的字典里沒有“3/4”這類東西，因?yàn)?/4也需要被寫成1/4+1/2。

古埃及的文字里，一只眼睛下面放一個(gè)數(shù)字就代表了一個(gè)單位分?jǐn)?shù)。

從1到100萬都有相應(yīng)的圖形。

雖然它和我們現(xiàn)在的數(shù)學(xué)相去甚遠(yuǎn)，但其實(shí)所有分?jǐn)?shù)都可以寫成單位分?jǐn)?shù)之和的形式。

因此這種表示方法被稱作古埃及分?jǐn)?shù)。

顯然，1也可以寫成古埃及分?jǐn)?shù)：1 = 1/2 + 1/3 + 1/6。

這個(gè)看似簡單的問題經(jīng)久不衰，1970年代，著名數(shù)學(xué)家Paul Erd?s和Ronald Graham提出了一個(gè)關(guān)于古埃及分?jǐn)?shù)的猜想：

把正整數(shù)劃分成若干個(gè)子集，那么必然有一個(gè)子集中存在一組數(shù)，可以把1表示成古埃及分?jǐn)?shù)形式。

△從左至右依次為Paul Erd?s和Ronald Graham夫婦

（注：Ronald Graham中文名“葛立恒”，就是提出葛立恒數(shù)的那位數(shù)學(xué)家。）

比如上面的1 = 1/2 + 1/3 + 1/6，某個(gè)子集中包含這2、3、6這三個(gè)數(shù)，就可以做到。

那么如果很不巧，2、3、6被分配到不同的子集中，還可以把1拆成古埃及分?jǐn)?shù)形式嗎？

其實(shí)也是可以的，包含{2、3、12、18、36}一組整數(shù)也行：

表示1的方法千千萬，總有符合條件一組數(shù)滿足條件。

達(dá)特茅斯學(xué)院的數(shù)論學(xué)者Carl Pomerance對此評價(jià)道：“這可能是有史以來最古老的問題。”

沒想到的是，這個(gè)最古老的問題最近又發(fā)出新芽。

來自牛津大學(xué)的數(shù)學(xué)家Thomas Bloom最近不但提出了比Erd?s更厲害的“強(qiáng)化版”，還親自證明了它。

幾周就證明了一個(gè)“加強(qiáng)版”

那篇近20年前的論文，由一位名叫Ernie Croot的數(shù)學(xué)家撰寫，2003年發(fā)表在數(shù)學(xué)領(lǐng)域頂級期刊《數(shù)學(xué)年刊》上。

他解決Erd?s-Graham問題的“基礎(chǔ)版本”。

把所有整數(shù)隨機(jī)分配到不同的桶里，至少有一個(gè)桶必須包含一組整數(shù)，其倒數(shù)和等于1。

Bloom仔細(xì)閱讀后發(fā)現(xiàn)，Croot的方法實(shí)際上比最初看起來更強(qiáng)大：“所以我研究了幾周，這個(gè)更強(qiáng)大的結(jié)果就出來了?！?/p>

Bloom給出的結(jié)論是，并不需要把整數(shù)分成若干個(gè)有限集合，只要集合滿足“正密度”的條件，那么這個(gè)集合就存在一組整數(shù)倒數(shù)和為1。

所謂“正密度”是指某一組整數(shù)在全體正整數(shù)里所占的比例，比如偶數(shù)的密度是0.5。

假如有一組整數(shù)集合記作A，在前n項(xiàng)中不大于n的項(xiàng)記作α，當(dāng)n趨于無窮大時(shí)，α/n極限就是叫做A的自然密度。

而Bloom提出而條件是密度大于零即可，無論這個(gè)密度多低（10%、1%、0.0001%甚至更低），這顯然比把整數(shù)分成有限份的條件更加苛刻。

嗯，充分說明哪怕是“讀論文”這種科研作業(yè)，也要認(rèn)真一點(diǎn)，說不定讀著讀著靈感就來了（手動狗頭）

作者介紹

Thomas Bloom，目前在牛津大學(xué)進(jìn)行數(shù)學(xué)方面的研究工作，獲得過英國皇家學(xué)會大學(xué)研究金，后者專門用于給各領(lǐng)域杰出年輕科學(xué)家提供科研資金。

Bloom曾于布里斯托大學(xué)獲得博士學(xué)位，并在劍橋大學(xué)進(jìn)行過博士后相關(guān)工作，本科畢業(yè)于牛津大學(xué)數(shù)學(xué)與哲學(xué)專業(yè)。

在進(jìn)行這項(xiàng)研究之前，他也曾經(jīng)和獲得過“數(shù)論界最高獎(jiǎng)”柯爾獎(jiǎng)的牛津大學(xué)教授James Maynard合作，完成過一篇關(guān)于無方差集的論文。

One More Thing

對于任意有理數(shù)，我們都可以用簡單的算法找到古埃及分?jǐn)?shù)表示。

最常用的便是貪心算法。

以7/15為例，我們先找到最接近它的單位分?jǐn)?shù)1/3，得到：

7/15 = 1/3 + 2/15

接著尋找最接近剩余項(xiàng)2/15的單位分?jǐn)?shù)，即1/8。依次類推，直到剩余項(xiàng)也是單位分?jǐn)?shù)為止。

7/15 = 1/3 + 1/8 + 1/120

怎么尋找最接近的單位分?jǐn)?shù)呢？將分母除以分子并向上取整即可。

以下是Python版的代碼：

# Python3 program to print a fraction
# in Egyptian Form using Greedy
# Algorithm

# import math package to use
# ceiling function
import math

# define a function egyptianFraction
# which receive parameter nr as
# numerator and dr as denominator
def egyptianFraction(nr, dr):

    print("The Egyptian Fraction " +
          "Representation of {0}/{1} is".
                format(nr, dr), end="\n")

    # empty list ef to store
    # denominator
    ef = []

    # while loop runs until
    # fraction becomes 0 i.e,
    # numerator becomes 0
    while nr != 0:

        # taking ceiling
        x = math.ceil(dr / nr)

        # storing value in ef list
        ef.append(x)

        # updating new nr and dr
        nr = x * nr - dr
        dr = dr * x

    # printing the values
    for i in range(len(ef)):
        if i != len(ef) - 1:
            print(" 1/{0} +" .
                    format(ef[i]), end = " ")
        else:
            print(" 1/{0}" .
                    format(ef[i]), end = " ")

# calling the function
egyptianFraction(6, 14)

# This code is contributed
# by Anubhav Raj Singh

你能寫出其他語言的版本，或是寫出其他古埃及分?jǐn)?shù)算法的代碼嗎？

參考鏈接：
[1]https://www.quantamagazine.org/maths-oldest-problem-ever-gets-a-new-answer-20220309/
[2]https://twitter.com/thomasfbloom
[3]https://www.youtube.com/watch?v=yBtluQoghXA
[4]https://www.geeksforgeeks.org/greedy-algorithm-egyptian-fraction/
[5]https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Graham_problem
[6]http://thomasbloom.org/aboutme.html
[7]https://annals.math.princeton.edu/2003/157-2/p04

— 完 —

量子位 QbitAI · 頭條號簽約

關(guān)注我們，第一時(shí)間獲知前沿科技動態(tài)