一个绘图员的伟大数学猜想,用计算机证明的重大问题——四色定理

很多时候我们都会发现很多世界闻名的数学难题,困扰了人类几百年,但是看起来却如此之简单。比如中国人民最熟悉的哥德巴赫猜想,其实就是一个乡村教师,哥德巴赫在闲暇里注意到的数学规律,写给欧拉之后,经过欧拉之手推向整个数学界;再比如一个表述极为容易,但是证明却毫无头绪的“3X+1”猜想,也是一位数学家简单概括就得出来的一个世界级巨难的问题。可见,数学问题的难度绝对不能以表面意思的难以来定论,今天的四色定理也完全是这样的套路,看似简单,看似迷人,实际上折磨死人!

3x+1 猜想极其繁杂的迭代运算

1852年,伦敦大学毕业的一位制图员格斯里,按部就班地在一家科研单位工作,他的主要工作就是绘制地图。时间长了,格斯里逐渐注意到一个现象:任何一部地图,只要用4种颜色就可以把所有的区域分隔开来,相邻国家之间不会混淆。可以想象作为绘图员的他,肯定保留着一贯的细心谨慎风格,在常年以往的绘图工作中,他确信这个现象是真实存在的。于是他想着能否从理论上进行证明呢?他当然想做到这点,于是他找了正在读大学的弟弟一起来讨论,开始了理论证明的道路。然而,一开始,这两兄弟并不知道这个问题的难度,做出了自己第一步尝试。

他们做了大量的绘制工作,所用稿纸不计其数,但是收效甚微。只做验算,永远是得不到真正的证明的。还好,弟弟的老师德摩尔根是当时一位著名的数学家,请教他应该会有更好的结果。但是摩尔根在深刻思考之后,双手摊开,也表示无能为力。于是老师也去请教了更厉害的人,德国著名数学家哈密尔顿,然而哈密尔顿在经过深思熟虑之后,也没有从理论上给出证明,这份遗憾直到1865年哈密尔顿去世都没有弥补完全。

地图绘制员的伟大猜想——四色猜想

1872年,英国数学家凯利正式向伦敦数学会推荐了这个问题,从此四色问题登上世界数学舞台。这个问题看起来如此浅显易懂,而且很容易尝试,吸引了一大批优秀的数学家前赴后继地研究。很快,数学界传来了第一个研究成果,1879年,一位叫肯普的律师兼业余数学家(很熟悉吧,费马的职业跟他一模一样)发表了第一个理论证明。这个证明在很长时间内都获得了数学家们的认可,人们以为四色猜想从此就成为定理,事实上从这之后,人们习惯了就叫四色定理,即使这个问题没有被解决。也许有已经称呼习惯了不想费事再去改正的原因,也从另一方面说明了,人们对此四色问题的深信不疑。然而,10年之后,1890年,数学家希伍德用精确计算的方式发现了肯普的证明存在严重的错误,对此肯普本人也承认,其实他更加愿意承认的是他没有能力去弥补这个巨大的缺陷。

世界由4种色彩构造

此时人们才意识到,这个看似浅显的问题可能是堪比费马大定理的历史级猜想,绝对不是什么轻而易举就可以解决的问题了。因此,四色猜想也和费马大定理,哥德巴赫猜想一起并称世界数学三大难题。顺便说一下,到目前为止,这个三个问题中,只有两个已经完全解决了。

虽然如此,肯普的方法仍然具有很大开拓性作用,他采用了一种叫做归谬法的证明方式,这个方法的思路是:

先假设四色猜想不真,那么就会有五色地图,而五色地图中也必定会有最小的一个,但这最小的五色地图中一定存在不可避免域,如果不可避免中有可约域,那么把可约域去掉后就会得到更小的五色地图,这与假设相矛盾,说明五色地图不存在。

人们在20世纪很长一段时间里都是用到肯普的方法慢慢推进。1933年,美国数学家富兰克林证明了22国(地图上的区域)内,四色定理成立。1950年到1960年,人们理论证明的国家数量从22国推进到50国。可以看出来这种推进是多么缓慢,就好像当年手工寻找黎曼非平凡零点一样,一点一点何时才是头啊。不过转而一想,我们虽然没有认真去研读肯普的证明方式,但是也可以感觉到,肯普的证明需要大量的构型和计算量为基础,区域比较少的时候,人们可以轻而易举地去实现枚举证明,但是数量一旦扩大到某个程度之后,构型和计算就变得极为困难,搞不好可能会演化成NP问题。可以想象,在没有计算机的环境下,人们将四色定理的成立条件推进到50国是多么艰辛的一个工作。

在中国地图上手动验算四色定理

20世纪下半叶,大型计算机的发展给了那些需要大量计算验证的问题一个明显的解决信号。在人工证明捉襟见肘的情况下,计算机决定正式迎战四色定理。

超强计算力计算当今各种复杂问题

1976年,人们完成了数学史上重大问题的第一个机械式证明。美国数学家哈肯和阿佩尔,应用前人的创造的“放电”法,编写了一个很好的程序,这个程序可以自行构造出一些特别的图,并且可以迅速验证这样的图是否可以只用四色。于是他们利用这个相当给力的程序构造了一个空前大的集合,这个集合的数量有1936种之多!对比之前人工取得的数量,这个数目实在太恐怖了。程序对每一张图都进行了多达20万次可能的着色方案试探,在美国的伊利诺伊大学里,在两台计算机上这个程序运行了1200小时,做了200亿次逻辑判断,证明了这1900多种图形中,没有一种需要四种颜色以上才可以涂完,也就是说只要用4种颜色就完全可以绘制出这么多种地图了。工作进行到此,我们貌似就可以宣布四色定理成立了!两位数学家宣布四色定理成立之后,当地的信封上盖“Four colorssutfice”(四色足够了)的邮戳,人们从各种渠道上开始传播这个地方的人们获得的巨大荣耀。

美国数学家 哈肯

前面说了貌似,事实上,从两位数学家证明四色定理的方法一公布,数学界的争论就从来没有停止过。发表一下我的看法,首先人们用计算机得出的结论肯定是正确的,因为验算过程中的1936种构型完全超过了当今任何地图的区域数,在这个数目以内的任何地图都满足要求。但是我的第一感觉就是,这样的证明方式不漂亮,有点暴力计算的意思,我不否认计算机的强大计算能力在解决数学问题中起到的巨大作用,但是那些仅仅是做验算给人类的核心证明打辅助而已。然而四色定理的证明方法却完全一反常态,人类创造的一种算法,让计算机的算力打头阵,颇有些喧宾夺主的意思。

美国伊利诺伊大学

所谓穷举法来证明问题,应该是计算机专家们相当信赖的法子,实在称不上什么高深的技巧。如果这种方式成为了解决重大问题的一般处理方法,人类就过于依赖计算力了,从而在某种程度上大大减轻了人类智力的巅峰考验。我不认为这是一件特别值得庆祝的事情。

恐怕当今世界仍然没有四色定理的理论证明成为了很多相关领域数学家的一块心病,人们不愿意承认,如此重大的一个问题是由计算机做出证明的。时至今日,研究四色定理理论证明的人仍然很多很多,只不过,我们悲观地发现,当今还没有任何一位数学家提出的理论证明获得了大家的认可。

这里,我们不是说哈肯,阿佩尔的工作意义不重要,相反地他们提出了一个全新的视角,开拓了人工智能和现代计算机分析技术。人们尝试着从各种不同角度来解决四色问题的过程中,毫无意外地收获了大量的数学方法,尤其是图论和拓扑学两大学科,都获得了空前发展

数学研究永无止境

然而人们的探索却永无止境,只要有些许可能,人类必将付出百般努力,在这里,向那些仍然努力寻找纯粹四色定理证明的数学家们致敬!

(0)

相关推荐