数学家完成构建“球形立方体”的任务

公元四世纪，亚历山大港的希腊数学家帕普斯称赞蜜蜂具有“几何预见性”。 它们蜂窝的六边形结构似乎是将二维空间划分为面积相等且周长最小的细胞的最佳方式——允许昆虫减少它们需要产生的蜡量，并花费更少的时间和精力来构建它们蜂巢。

或者 Pappus 和其他人是这么假设的。 几千年来，没有人能够证明六边形是最佳的——直到最后，在 1999 年，数学家托马斯·黑尔斯 (Thomas Hales) 证明没有其他形状可以做得更好。 今天，数学家仍然不知道哪些形状可以以尽可能小的表面积平铺三个或更多维度。

这个“泡沫”问题已经证明具有广泛的应用——物理学家研究肥皂泡（或泡沫）的行为，化学家分析晶体的结构，数学家探索球体堆积排列，统计学家开发有效的数据处理技术.

在 2000 年代中期，泡沫问题的一个特殊表述也引起了理论计算机科学家的注意，他们惊讶地发现它与他们领域中一个重要的开放问题有着深刻的联系。 他们能够利用这种联系找到一种新的具有最小表面积的高维形状。

“我喜欢来来回回，”说 阿萨夫瑙尔 普林斯顿大学。 “一些古老的数学与计算机科学相关； 计算机科学回报并解决了数学中的问题。 当这种情况发生时，感觉非常好。”

但是这种形状虽然是最佳的，但缺少一些重要的东西：几何基础。 因为它的存在已经用计算机科学技术证明了，所以它的实际几何形状很难掌握。 这就是 Naor 和 奥德·雷格夫，纽约大学 Courant 研究所的计算机科学家，着手纠正 上个月在网上发布的证明.

“这是一个非常好的故事结局，”Regev 说。

立方泡沫

数学家已经考虑了泡沫问题的其他版本——包括如果只允许根据所谓的整数格来划分空间会发生什么。 在该版本的问题中，您采用均匀分布的点（每个间隔 1 个单位）的方形阵列，并使每个点成为形状的中心。 “立方体”泡沫问题问的是，当您需要以这种方式平铺空间时，最小表面积是多少。

研究人员最初对施加此限制感兴趣，以了解称为流形的拓扑空间的属性。 但是这个问题有了自己的生命，与数据分析和其他应用程序相关。

它在几何学上也很有趣，因为它改变了“最佳”的含义。 例如，在二维中，如果正六边形只能在水平和垂直方向上移动整数，则它们不能再平铺平面。 （你必须在两个方向之一上以不合理的数量移动它们。）

正方形可以。 但这是可以做到的最好的吗？ 作为数学家 崔再庆 1989年发现，答案是否定的。 最佳形状是一个六边形，它在一个方向上被压扁，在另一个方向上被拉长。 （当面积为 3.86 时，这种六边形的周长约为 1——超过了正方形的周长 4。）

这些差异可能看起来微不足道，但在更高的维度上它们会变得更大。

在给定体积的所有形状中，使表面积最小的是球体。 作为 n, 维数, 增长, 球体的表面积增加与平方根成正比 n.

但是球体不能在不留空隙的情况下平铺空间。 另一方面，一个 n体积为 1 罐的维立方体。 问题是它的表面积是 2n，与其维度成正比地增长。 体积 10,000 的 1 维立方体的表面积为 20,000 — 比 400 大得多，大约是 10,000 维球体的表面积。

因此，研究人员想知道他们是否可以找到一个“球形立方体”——一种平铺的形状 n次元空间，如立方体，但表面积增长缓慢，如球体。

这似乎不太可能。 “如果你想让你的泡泡完全填满空间并以这个立方体网格为中心，很难想象除了立方体泡泡你会用什么，”说 瑞恩奥唐奈，卡内基梅隆大学理论计算机科学家。 “看来，魔方应该是最好的了。”

我们现在知道事实并非如此。

难题的难度

几十年来，立方体泡沫问题在更高维度上的探索相对较少。 第一批在这方面取得进展的研究人员不是来自几何领域，而是来自理论计算机科学。 他们偶然发现了它，同时寻找一种方法来证明他们领域中被称为 独特的博弈猜想. “独特的博弈猜想，”Regev 说，“是我认为目前理论计算机科学中最大的悬而未决的问题。”

2002 年由 苏巴什霍特当时是一名研究生，这个猜想假设如果一个特定的问题——一个涉及为网络节点分配颜色的问题——不能被精确地解决，那么即使找到一个近似的解决方案也是非常困难的。 如果属实，该猜想将使研究人员能够一次性理解大量其他计算任务的复杂性。

计算机科学家通常根据任务是否可以用有效的算法解决，或者它们是否是“NP-hard”（这意味着随着问题规模的增长，它们无法有效解决，只要人们普遍认为但关于计算复杂性的未经证实的猜想是正确的）。 例如，旅行推销员问题要求找到访问网络中每个城市一次所需的最短路径，这是 NP-hard 问题。 确定一个图——由边连接的顶点的集合——是否可以用最多三种颜色标记，以便任何两个连接的顶点具有不同的颜色也是如此。

事实证明，对于其中许多任务，即使找到近似解决方案也是 NP 难的。 假设您想以满足某些约束列表的方式用不同颜色标记图形的顶点。 如果满足所有这些约束是 NP 难的，那么尝试只满足其中的 90%、75% 或 50% 怎么样？ 低于某个阈值，可能会提出一个有效的算法，但高于该阈值，问题就会变成 NP-hard。

几十年来，计算机科学家一直致力于确定不同优化问题的阈值。 但是有些问题回避了这种描述。 虽然一种算法可能保证 80% 的最佳解决方案，但实现 95% 的最佳解决方案可能是 NP-hard，因此问题在 80% 到 95% 之间的确切位置进入 NP-hard 领域的问题悬而未决。

独特的游戏猜想或 UGC 提供了一种立即查明答案的方法。 它做出了一个乍一看似乎更有限的声明：它是 NP-hard 区分一个你可以满足几乎所有特定着色约束集（比如，超过 99%）的图形和一个图形之间的区别你几乎不能满足任何一个（比如，少于 1%）。

但在 2002 年 UGC 提出后不久，研究人员表明，如果该猜想成立，那么您可以轻松计算出任何约束满足问题的硬度阈值。 （这是因为 UGC 还暗示已知算法可以为所有这些问题实现最佳近似。）“这恰恰是所有这些优化问题的关键，”O'Donnell 说。

因此，理论计算机科学家着手证明 UGC——这项任务最终导致他们中的一些人发现了球形立方体。

让难题变得更难

2005 年，O'Donnell 在微软研究院工作。 他和两个同事—— 尤里尔费格，现在在魏茨曼科学研究所，和 盖·金德勒，现在在耶路撒冷希伯来大学 - 联手解决教资会问题。

他们对如何进行有一个模糊的想法。 他们会从一个关于图表的问题开始——一个与 UGC 非常相似的问题。 所谓的最大切割（“最大切割”）问题会问，当给定一个图时，如何将其顶点划分为两个集合（或颜色），以便连接这些集合的边数尽可能多。 （您可以将最大割看成是关于用两种颜色为图形着色的最佳方式的问题，以便尽可能少的边连接相同颜色的顶点。）

如果 UGC 为真，则意味着给定一些随机图，有效的近似算法只能得到该图真实最大割的 87% 以内。 做得更好将是 NP-hard。

Feige、Kindler 和 O'Donnell 反而想走相反的方向：他们希望证明 max cut 是难以近似的，然后用它来证明 UGC。 他们的计划依赖于一种叫做平行重复的技术的力量——一种让难题变得更难的聪明策略。

假设您知道区分一个您可以解决的问题和一个您基本上可以解决的问题是 NP 难的。 并行重复使您能够在此基础上显示出更强的硬度结果：区分您可以解决的问题和您几乎无法解决的问题也是 NP 难的。 “这种非直觉的、深刻的现象……是当今许多计算机科学的核心，”Naor 说。

但有一个陷阱。 并行重复并不总是像计算机科学家希望的那样放大问题的难度。 特别是，最大切割问题的某些方面“让并行重复很头疼”，Regev 说。

Feige、Kindler 和 O'Donnell 专注于证明平行重复在头痛的情况下仍然有效。 “分析起来真的很复杂，”他说 达娜·莫什科维茨，德克萨斯大学奥斯汀分校的理论计算机科学家。 “但这似乎非常接近。 平行重复似乎会 [帮助] 从最大切割到独特游戏之间建立联系。”

作为热身，研究人员试图理解一个简单的最大切割案例的并行重复，Moshkovitz 称之为“最愚蠢的最大切割”。 考虑由边连接形成一个圆或“奇数环”的奇数个顶点。 您想要用两种颜色中的一种标记每个顶点，以便没有一对相邻顶点具有相同的颜色。 在这种情况下，这是不可能的：一条边将始终连接相同颜色的顶点。 您必须删除该边，“打破”奇数循环，以使您的图形满足问题的约束。 最终，您希望最大限度地减少需要删除的边的总分数，以便为图形正确着色。

平行重复让你可以考虑这个问题的高维版本——你必须打破所有出现的奇数循环。 Feige、Kindler 和 O'Donnell 需要证明，随着维数变得非常大，您必须删除很大一部分边才能打破所有奇环。 如果那是真的，那就意味着平行重复可以有效地放大这个“愚蠢的最大切割”问题的难度。

就在那时，团队发现了一个奇怪的巧合：有一种几何方法可以解释平行重复是否会按照他们希望的方式进行。 秘密在于立方体泡沫的表面积。

从柠檬到柠檬水

他们的问题，用泡沫的语言重写，归结为表明球形立方体不存在——不可能沿着整数晶格将高维空间划分为表面积远小于立方体的单元。 （更大的表面积对应于需要删除奇数循环图中更多的“坏”边，正如计算机科学家希望展示的那样。）

“我们当时想，哦，多么奇怪的几何问题，但这可能是真的，对吧？” 奥唐奈说。 “我们真的需要它作为真正的答案。” 但他、飞哥和金德勒都无法证明。 所以在 2007 年，他们 发表了一篇论文 概述了他们计划如何利用这个问题来帮助攻击 UGC。

很快，他们的希望破灭了。

兰·拉兹（Ran Raz），普林斯顿大学的理论计算机科学家，已经证明了关于并行重复的几个主要结果，对他们的论文很感兴趣。 他决定分析奇数循环问题的并行重复，部分原因是与 Feige、Kindler 和 O'Donnell 发现的几何学有关。

Raz 并没有从泡沫问题入手，而是直面计算机科学版本的问题。 他表明，您可以通过删除更少的边来打破图中的所有奇数循环。 换句话说，并行重复不能充分放大这个最大切割问题的难度。 “从平行重复中获得的参数完全达不到这个要求，”Moshkovitz 说。

“我们使用平行重复来展示独特游戏的难度的计划甚至在最简单的情况下都行不通，”O'Donnell 说。 “这打破了整个计划。”

尽管令人失望，但 Raz 的结果也暗示了球形立方体的存在：能够平铺的形状 n-表面积与平方根成正比的维空间 n. “我们当时想，好吧，让我们用柠檬做柠檬水，把这个关于平行重复和离散图的令人失望的技术结果，把它变成一个整洁、有趣的几何结果，”奥唐奈说。

他和金德勒，与计算机科学家合作 阿努饶 和 阿维威德森, 仔细研究 Raz 的证明，直到他们很好地掌握了它的技术，可以将它们转化为泡沫问题。 2008 年，他们表明 球形立方体确实是可能的.

“这是推理问题的好方法，”说 马克·布雷弗曼 普林斯顿的。 “很美丽。”

它提出了故事的几何方面的问题。 因为他们使用了拉兹关于平行重复的工作来构建他们的瓷砖形状，金德勒、奥唐奈、拉奥和威格德森最终得到了一些丑陋的、类似弗兰肯斯坦的东西。 瓷砖很乱，到处都是凹痕。 用数学术语来说，它不是凸的。 虽然这对他们的目的有用，但球形立方体缺乏数学家喜欢的特性——使形状更具体、更容易定义和研究、更适合潜在应用的特性。

“他们的建筑有一些非常不令人满意的地方，”Regev 说。 “它看起来像变形虫。 它看起来不像你想象的那样，一个漂亮的瓷砖车身。”

这就是他和 Naor 着手寻找的东西。

挣脱牢笼

从一开始，Naor 和 Regev 就意识到他们必须从头开始。 “部分原因是凸体的限制如此之大，以前的技术都没有任何工作的机会，”说 多明泽，麻省理工学院理论计算机科学家。

事实上，凸性过于严格是完全有道理的——凸球形立方体根本不存在。

但上个月，Naor 和 Regev 证明了你可以分区 n沿整数坐标的维空间，具有凸形，其表面积非常接近球体。 他们完全以几何方式做到了这一点——将问题回归到其数学根源。

他们首先必须绕过一个主要障碍。 立方泡沫问题要求每个瓷砖都以整数坐标为中心。 但在整数格中，某些点之间的距离非常短——而这些短距离会带来麻烦。

考虑二维网格中的一个点。 它在水平和垂直方向上距离最近的点 1 个单位。 但在对角线方向上，最近的点距离 $latex sqrt{2}$ 个单位——这种差异在更大的空间中变得更糟。 在里面 n维整数格，最近的点仍然是 1 个单位，但那些“对角线”点现在是 $latex sqrt{n}$ 个单位。 例如，在 10,000 个维度中，这意味着与任何点最近的“对角线”邻居距离为 100 个单位，即使有 10,000 个其他点（每个方向一个）距离只有 1 个单位。

在其他晶格中，这两种距离彼此成比例增长。 几十年来，数学家已经知道如何用最小表面积的凸形来平铺这种格子。

但在整数格中，最短距离始终固定为 1。这妨碍了构建具有最佳表面积的漂亮瓷砖。 “他们有点把你关在笼子里，”Regev 说。 “他们让你周围的一切都变得非常紧张。”

所以 Naor 和 Regev 反而考虑了完整的一部分 n维空间。 他们仔细选择了这个子空间，使其仍然富含整数点，但这些点之间的距离不会太近。

换句话说，他们最终得到的子空间恰恰是数学家已经知道如何最佳地平铺的类型。

但这只是工作的一半。 Naor 和 Regev 需要划分整个空间，而不仅仅是其中的一部分。 得到一个 n维球形立方体，他们必须将有效瓦片与剩余空间中的瓦片相乘（类似于如何将二维正方形与一维线段相乘以获得三维立方体）。 这样做会将他们的建筑抬回原来的空间，但也会增加其表面积。

两人必须证明，剩余空间的瓷砖虽然不是最优的，但并没有增加太多的表面积。 一旦他们这样做了，他们的建设就完成了。 （他们最终形状的表面积最终比非凸球形立方体的表面积大一点，但他们相信有可能找到一种与其非凸面对应物一样有效的凸面瓷砖。）

这位数学家说，“他们的证明与之前关于球形立方体的工作完全不同” 诺加阿隆. “现在回想起来，这可能是一个更自然的证据。 这就是某人也许应该尝试的开始。”

“当事情以不同的方式进行时，”拉兹补充道，“有时你会发现有趣的额外含义。”

希望重燃

目前尚不清楚这些含义可能是什么——尽管这项工作利用了整数格在密码学和其他应用程序中的潜在用途。 考虑到这个问题与其他领域的联系，“它可能会导致其他事情，”Alon 说。

目前，计算机科学家没有找到一种方法来用并行重复和 UGC 的语言来解释凸结果。 但他们并没有完全放弃原计划用泡沫问题来证明猜想。 “有多种方法可以尝试颠覆我们遇到的明显障碍，”金德勒说。

Braverman 和 Minzer 尝试了一种这样的方法，当他们 2020 年重温泡沫. 他们并没有要求平铺形状是凸的，而是要求它遵循一定的对称性，这样无论你如何翻转它的坐标，它看起来都是一样的。 （在 2D 中，正方形行得通，但矩形行不通；迄今为止所描述的高维球形立方体也行不通。）在这种新的限制下，两人能够展示 Kindler 和其他人在 15 年前所希望的：毕竟你不能比立方体的表面积做得更好。

这对应于一种不同类型的平行重复——一种可以使最简单的最大切割案例变得尽可能困难的重复。 虽然结果为这一研究方向带来了一些希望，但尚不清楚这种并行重复的版本是否适用于所有最大切割问题。 “这并不意味着你已经完成了，”布雷弗曼说。 “这只是意味着你回来了。”

“几何学有很大的潜力，”Minzer 说。 “只是我们还不够了解它。”