一次家庭作业意外搞定40年前的数学猜想，牛津小哥：我只研究了几个礼拜
发布时间：2022-03-13 14:39:13来源：量子位
只是完成一次普通家庭作业，就把困扰了数学家们几十年的猜想搞出了新花样？！
没错，这是来自牛津大学的ThomasBloom的亲身经历。
在一次阅读小组的论文分享上，他被要求解读一篇2003年发表在《数学年刊》上的经典论文。
这篇论文证明了一个与“最古老数学问题”埃及分数有关的猜想。
简单来说，猜想认为：将大于1的整数任意分成有限个子集，必然有一个子集中的部分整数倒数加起来为1，例如只要有一个子集中有2、3、6，就有1=1/2+1/3+1/6。
这一猜想被命名为Erdős-Graham猜想。
然而，这版2003年的证明还有很多待解决的疑惑：
ThomasBloom在解读论文的过程中，也发现这版证明对子集的要求有点高，很多特殊情况下没办法成立。
再仔细一看，他突然发现，这版证明还存在着可以继续改善的地方！
于是借着这次交作业的机会，ThomasBloom在这篇论文的基础上提出了一种“强化版”证明思路，整个过程甚至只用了几周时间。
就连数论领域著名学者、蒙特利尔大学教授AndrewGranvill都感叹这种做法的不可思议：
此前我只是觉得，这是一个不可能被解决的问题，任何头脑正常的人都没法做到。
所以，这一猜想究竟是什么，Bloom的证明方法又究竟“不可思议”在哪里？
在数学里，任意有理数都可以表示成分数，且分子分母都是整数。
但是在3000多年前的古埃及，他们的分数只有分子为1一种情况，我们现在叫它单位分数。
也就是说，他们的字典里没有“3/4”这类东西，因为3/4也需要被写成1/4+1/2。
古埃及的文字里，一只眼睛下面放一个数字就代表了一个单位分数。
从1到100万都有相应的图形。
虽然它和我们现在的数学相去甚远，但其实所有分数都可以写成单位分数之和的形式。
因此这种表示方法被称作古埃及分数。
显然，1也可以写成古埃及分数：1=1/2+1/3+1/6。
这个看似简单的问题经久不衰，1970年代，著名数学家PaulErdős和RonaldGraham提出了一个关于古埃及分数的猜想：
把正整数划分成若干个子集，那么必然有一个子集中存在一组数，可以把1表示成古埃及分数形式。
（注：RonaldGraham中文名“葛立恒”，就是。）
比如上面的1=1/2+1/3+1/6，某个子集中包含这2、3、6这三个数，就可以做到。
那么如果很不巧，2、3、6被分配到不同的子集中，还可以把1拆成古埃及分数形式吗？
其实也是可以的，包含{2、3、12、18、36}一组整数也行：
表示1的方法千千万，总有符合条件一组数满足条件。
达特茅斯学院的数论学者CarlPomerance对此评价道：“这可能是有史以来最古老的问题。”
没想到的是，这个最古老的问题最近又发出新芽。
来自牛津大学的数学家ThomasBloom最近不但提出了比Erdős更厉害的“强化版”，还亲自证明了它。
那篇近20年前的论文，由一位名叫ErnieCroot的数学家撰写，2003年发表在数学领域顶级期刊《数学年刊》上。
他解决Erdős-Graham问题的“基础版本”。
把所有整数随机分配到不同的桶里，至少有一个桶必须包含一组整数，其倒数和等于1。
Bloom仔细阅读后发现，Croot的方法实际上比最初看起来更强大：“所以我研究了几周，这个更强大的结果就出来了。”
Bloom给出的结论是，并不需要把整数分成若干个有限集合，只要集合满足“正密度”的条件，那么这个集合就存在一组整数倒数和为1。
所谓“正密度”是指某一组整数在全体正整数里所占的比例，比如偶数的密度是0.5。
假如有一组整数集合记作A，在前n项中不大于n的项记作α，当n趋于无穷大时，α/n极限就是叫做A的自然密度。
而Bloom提出而条件是密度大于零即可，无论这个密度多低（10%、1%、0.0001%甚至更低），这显然比把整数分成有限份的条件更加苛刻。
嗯，充分说明哪怕是“读论文”这种科研作业，也要认真一点，说不定读着读着灵感就来了（手动狗头）
ThomasBloom，目前在牛津大学进行数学方面的研究工作，获得过英国皇家学会大学研究金，后者专门用于给各领域杰出年轻科学家提供科研资金。
Bloom曾于布里斯托大学获得博士学位，并在剑桥大学进行过博士后相关工作，本科毕业于牛津大学数学与哲学专业。
在进行这项研究之前，他也曾经和获得过“数论界最高奖”柯尔奖的牛津大学教授JamesMaynard合作，完成过一篇关于无方差集的论文。
对于任意有理数，我们都可以用简单的算法找到古埃及分数表示。
最常用的便是贪心算法。
以7/15为例，我们先找到最接近它的单位分数1/3，得到：
7/15=1/3+2/15
接着寻找最接近剩余项2/15的单位分数，即1/8。依次类推，直到剩余项也是单位分数为止。
7/15=1/3+1/8+1/120
怎么寻找最接近的单位分数呢？将分母除以分子并向上取整即可。
以下是Python版的代码：
#Python3programtoprintafraction#inEgyptianFormusingGreedy#Algorithm#importmathpackagetouse#ceilingfunctionimportmath#defineafunctionegyptianFraction#whichreceiveparameternras#numeratoranddrasdenominatordefegyptianFraction(nr,dr):print("TheEgyptianFraction"+"Representationof{0}/{1}is".format(nr,dr),end="\n")#emptylisteftostore#denominatoref=[]#whilelooprunsuntil#fractionbecomes0i.e,#numeratorbecomes0whilenr!=0:#takingceilingx=math.ceil(dr/nr)#storingvalueineflistef.append(x)#updatingnewnranddrnr=x*nr-drdr=dr*x#printingthevaluesforiinrange(len(ef)):ifi!=len(ef)-1:print("1/{0}+".format(ef[i]),end="")else:print("1/{0}".format(ef[i]),end="")#callingthefunctionegyptianFraction(6,14)#Thiscodeiscontributed#byAnubhavRajSingh你能写出其他语言的版本，或是写出其他古埃及分数算法的代码吗？
参考链接：[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
—完—
本文系网易新闻•网易号特色内容激励计划签约账号【量子位】原创内容，未经账号授权，禁止随意转载。
直播报名|如何建立AI生态的“Android”
从感知到认知，AI还需要多久才能触及生产核心？从软件到数件，AI生态该如何建立自己“Android”？
3月16日19:30，「量子位·视点」CEO/CTO系列分享活动将邀请天云数据CEO雷涛直播分享个人见解。扫码预约直播围观吧~
量子位QbitAI·头条号签约作者
վ'ᴗ'ի追踪AI技术和产品新动态
一键三连「分享」「点赞」和「在看」
科技前沿进展日日相见~