四色猜想证明中的几次重大创新

zhangyd2007@soh

                                                                 四色猜想证明中的几次重大创新

                                                                                四色之巅      

        四色猜想作为世界数学界第二大著名难题，从1852年英国的格思里提出至今，已经经历了166年的漫长岁月。期间，不知耗费了多少数学家、数学爱好者的心血，也不知提供了多少种证明思路、方法。这里，我把期间具有重大创新的研究成果，分述如下。

                                                                   第一次创新----肯普证明

         1878年，英国数学家凯利向伦敦数学会提交关于四色猜想的报告，从此四色猜想成为世界数学难题。
         1879年，英国A.B.Kempe(肯普)给出第一个证明，其中重大创新是：
        （1）、运用欧拉公式V-E+F=2证明了“在正规地图中，不可避免地存在一个国家与二个、三个、四个、五个国家相邻的情形”,用数学符号表述为“d(v)=2、3、4、5”。这样一来，就把一个国家与无限多个国家相邻的复杂问题简化为最多与五个国家相邻的简单问题了。并且给出这些“构形”的模型，然后，证明了：要证明四色猜想，只要证明不可能存在最小五色地图即可。方法是证明：最小五色地图上不能有他的不可避免集中的任何构形，每一幅地图都至少包含这些构形中的一个。他成功地证明了前三种构形是可约的（即可以4-染色的）。                 
        （2）、他在证明一国与四国相邻即d(v)=4可约时，发明了“肯普链法” ，并且在证明一国与五国相邻即d （v）=5可约时，应用2次肯普链法分别证明了两种简单构形[即在五个相邻国四染色呈现“ABCDB”型（简记为“BAB”型）时 ，构形外围存在B-C链或者B-D链的情形与构形外围存在A-C链、A-D链但彼此不相交情形]的可约性。

                                                                第二次创新 ---赫伍德反例

         在肯普证明论文发表11年以后的1890年 ，英国Heawood（赫伍德）给出一个反例（简称H反例），考虑到A-C链、A-D链彼此相交的情形，即肯普证明中疏忽掉的情形，指出经过2次肯普链法不能给H反例成功4-染色。Heawood研究四色猜想的证明不下60年，始终没有成功，不过他应用肯普链法成功证明了五色定理。
H反例的出现，使得四色猜想在证明d(v）=5时，沿袭肯普成果与赫伍德所创立的成功思路，开启了长达150多年新的探索历程。  
                  
                                                               第三次创新---Appel-Haken机器证明

         1976年，美国Appel---Haken（阿佩尔—哈肯）运用“放电”理论，首先确立了一个1482种构形组成的庞大集合，然后利用电脑编程，交给计算机逐一检验这些构形的可约性，开创了机器证明四色猜想的先河。
          1997年，罗伯逊等人沿着阿佩尔—哈肯的思路，改进了“放电”算法，把1千多种构形简化为633种构形，但是仍然需要计算机逐一检验其可约性。
          两种机器证明，由于人工无法检验整个证明过程的正确性，所以数学界一直怀疑机器证明的可靠性。
Kempe的证明，Appel和Haken的证明，以及Robertson等人的证明，都有一个共同之处：所提及的这些证明，都依赖于证明任何平面图都包含给定构形集之中的一个构形，进而证明对于构形集之中的每一个构形，由一个比所给构形较小的图（即G-V） 的四染色可以扩展到原先所给的图G四染色。

                                                               第四次创新----具有周期性的H染色程序的确立

        1935年，美国Irving（欧文）等人在《对部分四染色地图的一组操作》中给出一个“Errera（埃雷拉）”构形(简称“E”构形)，这个构形在一组特定的α操作下发生144度（4次颠倒染色）的周期性转化，β操作（20次颠倒染色）下发生720度的周期性转化。
        1980年，Hamish Carr and William Kocay（哈米什.卡尔和威廉.考凯）在《一种试探式的平面图四染色》中把肯普链法发展了，此方法是基于Kempe染色的迭代。这一试探式的方法，称为算法2.1，引出一族非常有趣的平面图，能使算法2.1循环。他们描述了这些平面图的结构，并提出了一种改进的染色算法，这一改进的算法似乎总是能为平面图成功四染色。这些方法有可能会 演绎成四色定理的证明，且不需要用计算机来构造不可约的构形并为其染色。
         1992年，英国Holrovd – Miller（霍罗伊德-米勒）在《赫伍德应该知道的范例》中，进一步把欧文、卡尔等人的研究具体化。详细解析了两个著名范例。一个是用发展了的肯普链法----“4次逆时针赫伍德颠倒染色”（她们简称“H染色程序”）给出H反例的4-染色证明，指出H染色程序对H反例的有效性；另一个是给出“E”构形的对偶图表示，同时用3个图详细论述了这个构形在施行4次H染色程序后发生周期性转化，无法正确4染色。这个反例又指出H染色程序的局限性。
         同在1992年，我国山西省盂县党校的张彧典先生在他发表于山西省教育学院学报《教学与管理》1994年第二期《四色定理的数学归纳法证明》58-62页的论文中也发现：                          
          任何H反例构形的五边形4染色基本模型“BAB-C-D”（简记为“BAB”）在连续的4次H染色程序下一定沿着BAB—DCD—ABA—CDC--BAB发生周期性转化。基于这种发现，他认为，一定存在一个构形集，其中所有构形都可以用具有周期性的H染色程序证明它们可约。
         以上介绍的几个人对“ E”构形发生周期性转化的认识以及H染色程序的确立起了重要的推动作用。我国北京的敢峰先生的研究更加详尽 ，作为第五次创新在下面单独介绍。
                     
                                                                    第五次创新----敢峰对“ E”构形生成的详细演绎

        2009年，敢峰在《四色定理简证》（收录于2011年出版的《4CC和1+1的证明》61-71页）中，对“ E”构形的生成原因给出一个连续的16步演绎分析， 前15步揭示了“ E”构形如何从基本模型（8点式BAB型）生成 点、边由少到多、 几何结构由简到繁的非十折对称的15个无解构形的规律性，第16步完成了由非十折对称的无解构形的演变（量变）向十折对称无解构形的演变（质变），从第17步到第20步，给出了“ E”构形的4个不同的连续转化形式，即第四次创新中的四个周期循环构形。

                                                                  第六次创新------张彧典有解构形集的雏形


        1994-1999年，他首先根据H反例的结构特征建立了一个数学模型，然后根据四色地图中固有的6种色链的不同组合（包含数量、位置两种组合）构造了由模型派生的类似H反例的构形8个，同时用已经确立的H染色程序（逆时针颠倒染色法）逐一证明其可约，颠倒染色次数从2连续递增到9。
        结果在1999年拜读了《赫伍德应该知道的范例》以后，“ E” 构形的解析否定了他的判断。2000年，他仔细分析了H-M构形的染色特征后发现，虽然，“ E”构形在施行逆时针H染色程序时生成4个连续转化的无解构形，无法正确4染色。但是，在仔细分析这4个构形时发现，它们具有一个统一的染色特征，就是都包含一个已知A-B环，从而给出一个创新的肯普链法---张彧典链法（简记为Z染色程序），完成了4个构形的可约证明。到此确立了包含9个构形的集合，论文《肯普证明的完善》发表于山西忻州师范学院学报2004年第二期。

                                                                 第七次创新---雷明反例

         2017年底，我国西安的雷明先生给出一个反例（简称L反例），打破张彧典不可避免构形集中的最多颠倒染色9次这个上限值---需要10次颠倒染色才可约。这个反例将与赫伍德反例一样著名。因为它促成了张彧典不可避免构形集的产生。

                                                              
                                                        第八次创新------完成了《四色猜想染色困局构形的可约证明》



       第一：2017年12月，张彧典发现并且证明了一个重要定理：在任何一幅用四色染色的极大平面图中，不可避免地存在至少 “一个四边形之四个顶点用四种不同颜色染色”，简称为“四色顶点四边形”存在定理（即定理1），同时证明了四色顶点四边形的性质定理（即定理2）：

        在四色顶点四边形中，已知对角链被它的相反对角链替换时，只会改变构形的几何结构，而不会改变构形的色图。

        第二：找到了E-族（4个）构形。

        1935年，《美国数学学会会刊》发表了《对已部分染色地图的一组操作》【1】给出赫伍德反例构形的基本模型，同时提出了一个Errera图（即构形），称之为“染色困局”构形。

       《一种试探式的平面图四染色》【2】一文又把Errera图称之为CK图。

        1992年，《已知的赫伍德范例》【3】把Errera图用它的对偶图简化表示出来，我们称之为“E构形”，就是论文中图3之E1。

为了名称的统一，我们把以上3种叫法统一为“染色困局”构形 。

        2018年，他通过解析上述3个同类文献，找到了与E构形同胎的另外3个构形，这4个构形统称为“E-族构形”，分别记为E1,E2,E3,E4 。

     《一种试探式的平面图四染色》中已经通过E1构形证明了一个引理，这就是：

     “引理3.1 ：当初始染色为CK0时，算法2.1循环，并以20种不同染色序列为一个周期” 。

       这个引理中所说的“初始染色为CK0”，就是初始的色图，“算法2.1”就是H染色程序。通过E族中的4个构形周期循环性分析，证明了它们周期循环的根本原因，主要不仅是因为构形初始染色，而且是因为它们都具有的十折对称性几何结构。为什么认识有差别呢？理由是：文献1、3、4只是考虑到E族中的一个构形即图4中E1的共性---色图CK0循环，他则与文献2一样，不仅考虑到色图循环，而且考虑到E族中的四个构形的共性---几何结构也循环。所以引理3.1 应该完善为：

       引理3.1：“当具有十折对称几何结构且初始染色为CK0时，算法2.1循环，并以20种不同染色序列为一个周期”。

       在《已知的赫伍德范例》中，米勒她们两人给出范例2即“E构形”，并且证明了：在“四次逆时针赫伍德颠倒之后，构形发生周期性循环”，这里我们不妨称为引理3.2。
       显然，以上两个引理互为逆定理，如果把引理3.1作为原定理，那么引理3.2 就是它的逆定理，根据高中数学学习过的四种命题真假性的四种不同组合可以判定，引理3.1的四种命题都是真命题，所以它的否定理一定成立，即：

         定理3：         

       “当初始染色的CK0不具有十折对称几何结构时，算法2.1不循环。”

         把定理3推而广之，得到推论：

    “如果任意放大的染色困局构形不具有十折对称几何结构时，那么H染色程序一定不循环，即经过有限次的颠倒染色后使得构形可约。
这个推论对于点与边无限、非十折对称几何结构复杂的染色困局构形的可约提供了理论证明。     

        对于E族4个构形，如果运用H染色程序求解，都会发生周期性循环，无法证明其可约。但是，张彧典发现，四个E构形都存在A-B或者C-D两种特征环，当在这两种特征环外颠倒与之相反的色链的染色时，都是可约的，于是产生了“张氏染色程序”（简记为Z染色程序），也可以称为定理4。

        然后，运用完全数学归纳法证明了：

        对于任意具有十折对称几何结构的构形，Z染色程序可行。

        包括任意放大的，只要没有破坏十折对称几何结构的基本框架，Z染色程序仍然可约。

        张彧典等人通过4个定理理的确立，完成了四色猜想中染色困局构形理论性的可约证明，也就是弥补了肯普（Kempe）证明d(v)=5时的漏洞，从“实践+理论”上给出四色猜想一个完整而简短的证明。论文《四色猜想“染色困局构形”的可约证明》在2020年12月发表于《内蒙古科技》杂志39期（总462期）。2021年，他认真修改了上述论文，并且翻译成英文稿《四色猜想中染色困局构形的4-染色》，在2022年发表于《应用数学与应用物理杂志第3期（总10期），中英文对照版发表于数学中国哥猜难题栏目。


        至此，张彧典等人经过40年的不懈探索，实现了清华大学林翠琴教授1996年给他们指出的方向:
如果能够证明，对于任意极大平面图，通过有限次的赫伍德颠倒染色，都可以正确四染色，那将是威震海内外的成果。


        

                                                            
                                                                             结束语


         阿佩尔在给出机器证明以后曾经预见：四色问题的一个简短证明有朝一日会被发现，甚至被一位因此而一举成名的天才高中生所发现。
         张彧典坚信：
       “四色猜想”在英国“下种”（提出并成为世界数学难题），“生长并开花”（ 肯普证明），在美国“结果”（Appel-Haken的机器证明），并且确立“梦想”即 Appel预见 ：四色猜想的简短证明有朝一日会被发现 。
         由美国人确立的“梦想”将在中国“成真” ！这个圆梦的人也许不是张彧典，但是，他的《四色猜想染色困局构形的可约证明》或许成为实现“四色猜想人工证明”的一座新的里程碑。
         张彧典希望：能够得到中外四色问题专家们的关注、评价！
                        
                                                                              （ 2022年12月3日）