※ [本文转录自 Gossiping 看板 #1VKSlQ1K ] 作者: Glamsight (安稳残忆) 看板: Gossiping 标题: [问卦] 【七维空间是否成立？】数学家集结 40 台 时间: Fri Sep 4 13:08:40 2020 难题备注请放最後面 违者新闻文章删除 1.媒体来源: ※ 例如苹果日报、自由时报（请参考版规下方的核准媒体名单） 科技橘报 2.记者署名: ※ 若新闻没有记者名字或编辑名字，请勿张贴，否则会被水桶14天 ※ 外电至少要有来源或编辑 如:法新社 责任编辑：赖佩萱 3.完整新闻标题: ※ 标题没有完整写出来 ---> 依照板规删除文章 【七维空间是否成立？】数学家集结 40 台电脑算力，半小时破解困扰 90 年的凯勒猜想 难题 4.完整新闻内文: ※ 社论特稿都不能贴！违者删除（政治类水桶3个月)，贴广告也会被删除喔！可详看版规 https://imgur.com/lC2J66P.jpg 【我们为什麽挑选这篇文章】德国数学家 Ott-Heinrich Keller 於 90 年前提出了所谓 的「凯勒猜想」，这是一个用相同瓷砖覆盖空间的问题。他对每个维度的空间做出论断： 在 n 维空间里，用 n 维立方体填充空间，两个相邻的单位体会共用 n-1 个维面。 有关各维度的论证一一浮出台面，唯读 7 维空间迟迟未解，但近期在 40 台电脑的强大 算力下，这个难题终於有解了！（责任编辑：赖佩萱） 本文经 AI 新媒体量子位（公众号 ID：QbitAI）授权转载，转载请连系出处 数学家会程式码，谁也挡不住！就连困扰人类 90 年的数学猜想也挡不住。来自史丹佛、 CMU 等名校的 4 名数学家，将一个数学难题转化成了对 10 亿个结果进行「暴力搜索」 。 冷门数学题终於破解 他们把这串程式码输入 40 台电脑组成的计算集群，30 分钟後，电脑给出了一个 200 GB 大小的证明结果： 凯勒猜想在不超过 7 维的空间是成立的 。 现在，任何人都可以去 GitHub 上复制这串程式码，验证这一数学定理。比较意外的是， 这段获得电脑学术会议 IJCAR（国际自动推理联合会议）最佳论文奖的程序，上线 GitHub 半年，只获得一颗星。 https://imgur.com/0MgdeBp.jpg 那麽，这 4 位数学家要证明的「凯勒猜想」到底是什麽？为何非要用电脑来证明？电脑 证明的结果可靠吗？ 下面让我们一一道来。 什麽是凯勒猜想？ 假如用一批完全相同的正方形瓷砖铺满地面，中间不留空隙。显然，瓷砖之间会共用一条 边，如下图蓝线所示： https://imgur.com/m2H75xz.jpg 在 3 维空间中，如果要用立方体占满空间，是不是也和 2 维空间类似呢？ 想像一下，如果像下图那样在空间中随便放入几个立方体，由此展开填满整个空间，那麽 唯一的办法就是让接上的立方体共用蓝色的面。 https://imgur.com/GgqVF5C.jpg 2 维、3 维皆如此，更高维度的空间会怎样？1930 年，德国数学家凯勒猜测，如果用 n 维立方体填满无限空间，则立方体之间必然会出现「面对面」，对於任意维度都成立 。 这便是凯勒猜想。 但数学猜想不能仅靠直觉，必须有严格的证明。90 年来，数学家一直不懈努力。1940 年 ，数学家 Perron 证明了凯勒猜想在 1 到 6 维空间是成立的 ；1992 年，另外两位数学 家 Lagarias 和 Shor 证明，凯勒猜想在 10 维空间上是不成立的 （注：这位 Shor 就 是那个提出用量子计算机求解质因数分解的数学家） 那还有 3 个维度没有解决呢！在 7 维、8 维、9 维 三个维度空间中，凯勒猜想是否成 立？ 有数学论证表明，如果凯勒猜想在 n 维空间上是错的，那麽它在比 n 更高的维度上也一 定是错的。2002 年，数学家 Mackey 已证明，凯勒猜想在 8 维空间不成立，因此在 9 维空间也不成立 。 至此，7 维空间成为唯一的难题。 修改证明方法：电脑「图论」 可能你已经发现，从上世纪 90 年代以来，凯勒猜想的证明速度大大加快，数学家只用 了 10 年时间就把问题缩小到三个维度。 这主要得益於两位数学家的贡献。当年，Perron 求解 1 到 6 维度时，没有特殊的捷径 。而到 1990 年，凯勒猜想的证明方法发生了巨大的变化。 数学家 Corrádi 和 Szabó 提出了一种新的方法，把原来无限空间的问题变成有限、离 散的问题，也让电脑解决凯勒猜想成为可能。 他们巧妙地把凯勒猜想变成图论问题，就是构造所谓的凯勒图（Keller Graph），而图论 正是电脑所擅长的。 在这种方法的指导下，Lagarias 和 Shor 两人很快在 2 年後就证明了 10 维空间的情况 ：凯勒猜想不成立。又过了 10 年，Mackey 证明，凯勒猜想在 8 维空间不成立。 那麽，凯勒图究竟是什麽，它为什麽能够加速凯勒猜想的证明？ 解析「凯勒图」构造 首先，我们从最简单的 2 维情况说起。现在，我们有一种牌，牌上画着两个有颜色的点 ，两个点是有顺序的，不能调换，比如，1 黑 2 白≠1 白 2 黑。 两个点总共可以涂 4 种颜色，颜色分成 2 对：红色对绿色、白色对黑色。数学家已经证 明，分配给点的颜色相当於正方形在空间中的坐标。两张牌的颜色是否配对标示了两个正 方形的相对位置。 点的颜色与正方形的具体关系是这样的： 1. 两对点完全相同，表示两个正方形完全重叠 https://imgur.com/DjtdhwG.jpg 2. 两对点颜色都不同，且颜色都不配对，表示两个正方形有部分重叠 https://imgur.com/qeWl5Gk.jpg 3. 一对点颜色相同，另一对点颜色配对，表示两个正方形共用一个边 https://imgur.com/zZA2qUN.jpg 4. 一对点颜色不同，另一对点颜色配对，表示两个正方形的边相互接触但不重合 https://imgur.com/Tyt43Sx.jpg 2 个点的凯勒图，要用 2 对颜色去填充牌面，总共有 16 种情况。然後我们把这 16 张 牌摆在桌上，只有符合前面条件 4 的两张牌，才能用线将二者连起来，这样就构成了一 张「凯勒图」。 https://imgur.com/Tzwm2zy.jpg 包含 16 张牌的凯勒图就描绘了正方形填补平面的所有可能。如果 2 维空间中凯勒猜想 不成立，那麽我们肯定能找到 4 个正方形，它们之间没有共用的边，但是能够无缝隙地 填在一起，然後在屏幕上无限复制这 4 个正方形，就能填满整个萤幕。 实际上并不可能。如果按此操作，只会得到有着无数孔隙（下图紫色部分）的填充方式。 https://imgur.com/eh3E2V8.jpg 对应到凯勒图中，就是在图中找到 4 张牌，它们两两之间都有连线（在数学上，这叫做 完全图）；显然，在 2 维问题的凯勒图中，我们找不到这样的 4 张牌（可以自己去上面 的凯勒图中找找看）。 https://imgur.com/Xwv1HkE.jpg 这样，我们把就把 n 维立方体以及位移 s 与牌的点数 n、颜色对数 s 联系起来。 作为更一般的规则，如果要证明 n 维凯勒猜想是错的，就要在对应的凯勒图中找到 2n 张牌，且这些牌两两相连，但正因为你找不到 4 个张牌组成的完全图，所以 2 维空间的 凯勒猜想是对的。 为了在 3 维空间中证明凯勒猜想，可以使用 216 张牌，每张牌上 3 个点，并可以使用 3 对颜色（这一点相对灵活）；然後，我们需要寻找 23=8 张牌，它们两两之间都有连线 ，但还是找不到。 到了 8 维空间中，我们总算可以找到符合条件的 256 张牌，所以 8 维空间的凯勒猜想 是错的。 https://imgur.com/moZYPjh.jpg 8 维空间中的一个反例（一个凯勒图的完全子图） 七维空间为什麽那麽难解？ 接下来的事情就是在 7 维空间对应的凯勒图上寻找完全子图。然而这个问题却从 8 维问 题解决後被搁置了 17 年。 根据前面的说明，求解 8 维空间和 10 维空间的凯勒猜想，要寻找 28=256 和 210=1024 张牌的子图，而 7 维空间只要寻找 27=128 张牌的子图。 後者的难度似乎更小，7 维空间的问题应该更简单啊！其实不然，因为从某种意义上说， 8 维和 10 维可以「分解」为容易计算的较低维度，但 7 维不行。 证明了 10 维情况的 Lagarias 说：「7 维不好，因为它是质数，这意味着你无法将其分 解为低维，因此别无选择，只能处理这些图的全部组合。」 对於人脑来说，寻找大小为 128 的子图是一项艰钜的任务，但这恰恰是电脑擅长回答的 问题。 电脑帮帮忙！超强博士生做到了 此前证明 8 维问题的 CMU 教授 Mackey 拉上了史丹佛的数学系博士生 Brakensiek 和专 长电脑辅助证明的助理教授 Heule。 回忆起立项的那天，Mackey 说，Brakensiek 是真正的天才，看着他就像看着 NBA 总决 赛里的 LeBron James。Brakensiek 本人确实很厉害，他曾是 2013/14 两届国际讯息学 奥林匹克赛（International Olympiad in Informatics，IOI）金牌得主。 https://imgur.com/jA7lu1i.jpg 论文第一作者 Brakensiek 言归正传。为了方便电脑求解，他们换了个方向来思考：先设定牌上有 7 个点、6 种可 能的颜色，按照前面的「条件 4」对这些牌上色，看看能不能找到 128 种不同的填色方 法，如果找不到，那麽凯勒猜想成立。 用电脑辅助证明数学问题，还需要把它变成一系列逻辑运算，也就是处理 0 和 1 之间的 与或非关系。 若要求解 7 维，则总共包含 39000 个不同布尔变量（0 或 1），有 239000 种可能性 ，这是一个非常非常大的数字，有 11741 位数。 https://imgur.com/sL6KzzX.jpg 数学家利用排除法和对称性，缩小可能解方 一台普通电脑只能处理 324 位数种可能，离解决问题还远得很，就算交给超级计算机也 不够；但是，这几位数学家想到了排除法，只要得到结论，而不必实际检查所有可能性。 效率才是王道！ 比如，用电脑规则给 128 张牌上色，当你涂到第 12 张牌的时候，发现找不到符合条件 的下一张牌了。那麽所有包含这 12 张牌的排列都可以排除；提升效率的另一种方式是利 用对称性。如果已经验证了某种排列不可能，那与之对称的所有情况都可以排除。 透过这两种方法，他们把搜索空间缩小到 10 亿（230）。这样一来，用电脑搜索变成了 可能。 最终，他们仅计算了半个小时，便有了答案。 电脑没有找到符合条件的 128 张牌，所以 7 维空间的凯勒猜想确实成立 。实际上，电 脑提供的不仅仅是一个答案，证明的内容多达 200 GB。4 位论文作者将证明送入电脑的 证明检查器，确认了它的可靠性。 解决了凯勒猜想後，Heule 的下一个目标是用电脑证明数学里「最简单的不可能问题」— — 3n+1 猜想，去年陶哲轩已经「几乎」解决了这个问题，现在可能只差一步之遥了。 5.完整新闻连结 (或短网址): ※ 当新闻连结过长时，需提供短网址方便网友点击 https://bit.ly/32XdSkZ 6.备注: ※ 一个人一天只能张贴一则新闻，被删或自删也算额度内，超贴者水桶，请注意 ※ 备注请勿张贴三日内新闻(包含连结、标题等) 嗯嗯，跟我想的一样。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.90.228 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Gossiping/M.1599196122.A.054.html ※ 编辑: Glamsight (140.112.90.228 台湾), 09/04/2020 13:09:14

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: NoPTT (1.171.183.132 台湾), 09/04/2020 22:11:26