业余数学家为一道填色难题带来突破!

  2020-06-15  阅读 412 views 次 点赞数432
业余数学家为一道填色难题带来突破!

1950 年秋天,当时仍在芝加哥大学就读的数学家尼尔逊对于「四色问题」感到兴趣。这个问题是︰

对于任何地图,假如希望把所有区域填上颜色,而且分享边界的区域不能使用同一颜色,那幺最少要用多少种颜色?这个问题当时尚未解决,数学家知道三种颜色并不足够,而五种颜色则够用,因此问题是,只用四种颜色是否足够?

答案是︰足够。这个问题要到 1976 年才获得解决,而且需要依靠电脑计算证明,1950 年时仅得 18 岁的尼尔逊自然未有找到答案。不过他在研究四色问题期间,想到一个相关问题︰

在平面上任意选取无限多点,而且把距离为 1cm的点连起来。如果要为这些点填上颜色,而且相连的点不可使用相同颜色,那幺最少要用多少种颜色?这个数字称为「平面色数」。

四到七之间

数学家加林发现的以下这图显示,答案最少要四种颜色︰

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

Image Credit: MathsPoetry

尼尔逊把这个问题称为「第二个四色问题」,问题涉及的图称为「等距图」,图中每条直线——在图论中称为边——的长度相等,故图中由同一条边连接的相邻节点距离相等,而且边数可以无限多。

这个问题现在被称为夏维格—尼尔逊问题,因为数学家夏维格在 1945 年解决另一个问题时,提出了有助证明「CNP=7」的想法,以及有段时间不少人误以为他率先提出这个问题。

比夏维格早提出证明的是数学家伊斯堡,后者是尼尔逊最早一批提及其问题的人。当时尼尔逊已经知道答案下限是四,伊斯堡问他︰「那幺上限是多少?」尼尔逊说他不知道,伊斯堡便找出答案。他跟夏维格一样,使用以下填上七种颜色的密铺平面图案︰

 
业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

Image Credit: David Eppstein, Public Domain

假设六角形的边长为 1cm,那幺在一个六角形内两点最远距离为 2cm,连接另一个同色六角形的话,最短距离——图中 a、b 两点之距离——则为√7cm,即约 2.65cm。因此我们只需把这些六角形缩小 2.1 倍,便能确保任何相隔 1cm 的两点,都不会在同一颜色的六角形上——在任何一个六角形中放一条 1cm 的直线,线的另一端必然在另一种颜色的六角形内。

因此在 1950 年的时候,尼尔逊和伊斯堡已经知道平面色数介乎四到七之间。

在数学专栏作家葛登能、多产数学家艾狄胥等人的介绍下,数学界得悉这个问题,然而多年来没有取得太大进展,数学家仍然只知道「4≤CNP≤7」这条不等式。

研究如何令人长寿的业余数学家

直到今个月初,网络论文预印本存库 arXiv 出现了一篇文章,题目是 〈平面色数最少是五〉。这篇由迪桂所写的论文,描述了如何构造一个多达 1581 个顶点的等距图,并解释如何以电脑检查无法用四种颜色填上所有顶点,从而证明平面色数最少是五,也就是说,现在只余下三个可能答案︰五、六或七。

一个久无进展的难题取得突破,在数学界并不罕见,今次较为难得的是,迪桂是个业余数学家。他在剑桥大学电脑科学系毕业,并因其妻子、专研果蝇的遗传学家卡本特而对生物学和程式产生兴趣,透过妻子教授和阅读自学生物学。在 2000 年他更因为一本关于线粒体 DNA 和老化的着作,获剑桥大学颁发博士学位。

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

迪桂现于他有份创办的 SENS 研究基金会担任首席科学家,致力研究以技术逆传老化带来的负面影响。他曾于接受《BBC》访问时表示,医学技术发展可以令人寿命大幅延长,人类甚至可能活至 1000 岁。

许多年前,迪桂曾迷上玩黑白棋,并因此认识了一些同样喜爱这个游戏的数学家。他们向迪桂介绍了图论,此后他不时会研究这门学科。他说︰「当我需要从工作中休息时,我偶尔会想数学。」去年圣诞,他刚好有时间想这个数学问题。

证明概要

整个证明的起点,是一个由正六边形及中心共七点构成的等距图,迪桂称为图 H。他指出,要把下图 H 填上最多四种颜色,如果不考虑旋转、镜射或交换颜色的话,其实只有以下四种方式︰

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

图 H 的四种填色方式。Image Credit: Aubrey de Grey 2018

留意上面两种方式中,均有三点相同颜色,下面两种则没有。

接下来迪桂构造了一个包含 52 份图 H 的等距图,称为图 L,他证明如果要把图 L 填上四种颜色的话,最少有一个图 H 包含相同颜色的三点。

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

由 52 个图 H 所构成的图 L Image Credit: Aubrey de Grey 2018

图 2 中黑线画出来的图,由数学家李奥·摩沙和威廉·摩沙两兄弟于 1961 年发现,这个在正五边形内画上四个等边三角形的图,同样需要最少四种颜色,换言之其色数为四。

迪桂以摩沙兄弟的发现为基础,构造出一个有 301 个顶点的图 W,再把图 W 複製七份,每份的中心点分别放在图 H 的各点上,构造出一个含 1345 个顶点的图 M。利用 MacBook Air 及 Mathematica 11,他只需要几分钟便检查完各种为图 M 填上四种颜色的方法,发现其中心的图 H 都不会有三点相同颜色。

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

有 301 个顶点的图 W和有 1345 个顶点的图 MImage Credit: Aubrey de Grey 2018

于是他把图 M 複製 52 份,各份中间的图 H 均对应图 L 中的图 H,得出一个非常庞大的图 N——总共有 20,425 个顶点!

由于超过 2 万个顶点实在太多,迪桂其后把 N 简化,最终构造出「只」有 1581 个顶点的等距图 G,同样需要最少五种颜色才可填满所有顶点。

接力挑战难题

虽然迪桂的论文仅是放到网上的预印本,尚未通过期刊的同行审查,但他已把数据公开,其他数学家可以验证。数学家米臣在网誌上表示,他跟另一数学家已独立验证其结果,并把顶点数目减至 1577 点。

现时夏维格—尼尔逊问题已成为「博学者计划」的第 16 号计划。这项计划始于 2009 年 1 月,由剑桥大学数学家高华斯提出,希望透过数学家在网络讨论,令尚未解决的难题取得进展。博学者计划的网页表示,第 16 号计划有三项明确目标︰

德州大学奥斯汀分校的电脑科学家浩劳已找到顶点数目为 826 个、必须用五种颜色才能填满的等距图。更小的等距图除了更容易验证外,也可能给其他研究这个问题的人启发,进一步解决夏维格—尼尔逊问题。

业余数学家为一道填色难题带来突破!
业余数学家为一道填色难题带来突破!

Image Credit: Marijn Heule

数学家格拉咸曾提出,会给最先找到平面色数的人 1000 美元奖金,而他似乎相信平面色数在五到六之间,因为他亦表示给最先证明平面色数大于五的人 100 美元奖金——这笔奖金相信属于迪桂;最先证明平面色数小于六者更可获得 250 美元。

虽然把平面色数的上限降低,看来要比提升其下限困难,不过迪桂的突破相信会令夏维格—尼尔逊问题更受关注,也许问题在不久将来会被解决。

相关文章︰资料来源︰
上一篇: 下一篇:
相关文章