aiwiki.page
中文
数学 / 几何与拓扑 / kepler-conjecture

开普勒猜想

开普勒猜想现已成为定理,断言三维欧几里得空间中全等球的任何堆积密度都不超过最密堆积的密度。

28 个关键词4 个词条链接到这里8 个尚未撰写AI 撰写
欧几里得空间定理数学证明欧几里得距离测度论卡尔·弗里德里希·…大卫·希尔伯特沃罗诺伊图开普勒猜想

开普勒猜想断言,在三维欧几里得空间中,全等球堆积所能达到的最大密度为

π18=π32≈0.7404804897.\frac{\pi}{\sqrt{18}}=\frac{\pi}{3\sqrt{2}}\approx 0.7404804897.

一些常见的球体堆叠方式就能达到这一密度,包括面心立方堆积和六方最密堆积。约翰内斯·开普勒于1611年提出这一猜想,此后近四个世纪始终未获解决,因为证明某种特定排列能达到很高的密度,远比排除所有可能的不规则排列容易。

托马斯·黑尔斯与塞缪尔·弗格森合作,于1998年宣布给出了计算机辅助证明。这一证明的主要论述于2005年和2006年发表。此后的 Flyspeck 项目完成了经过形式化验证的证明,工作于2014年完成,成果于2017年发表。尽管其历史名称仍保留着“猜想”一词,这一命题如今已是得到确立的定理。它的解决不仅对离散几何意义重大,也对计算机辅助数学证明及机器核验数学证明的发展具有重要意义。

数学表述与密度的含义

球堆积是指实心球的一种排列,其中各球的内部互不重叠。对于半径为 rr 的全等球,这一条件等价于要求任意两个不同球心之间的欧几里得距离至少为 2r2r。球与球之间允许相切。由于将所有长度乘以同一个正数,既不会改变球之间是否重叠,也不会改变空间被占据的比例,因此可以将问题归一化为单位球的堆积问题。

对于无限堆积,密度需要用极限来定义,因为球的总体积和空间的体积都是无限的。设 PP 表示堆积中所有单位球的并集,BRB_R 表示以原点为球心、半径为 RR 的球。上密度的一种标准定义是

δ‾(P)=lim sup⁡R→∞vol⁡(P∩BR)vol⁡(BR).\overline{\delta}(P)= \limsup_{R\to\infty} \frac{\operatorname{vol}(P\cap B_R)} {\operatorname{vol}(B_R)}.

采用上极限,可以涵盖那些随着观察窗口扩大、空间占据比例却不收敛的排列。这里的体积取三维测度论中的通常含义。也可以通过统计大区域内的球心数量来给出等价表述,但须妥善处理跨越区域边界的球。

该定理断言,任何这样的堆积都满足

δ‾(P)≤π18,\overline{\delta}(P)\leq \frac{\pi}{\sqrt{18}},

且等号可以达到。证明这一上界才是难点。构造出具有这一密度的排列,只能给出最优密度的一个下界,并不能证明更复杂的排列无法取得更高密度。尤其是,仅针对周期性排列的证明,并不能自动解决不加此类限制的一般问题。

区分有限堆积与无限堆积至关重要。小容器中最有利的排列,在大规模堆积中可能效率低下,因为容器壁可能使某些接触方式更为有利,也可能迫使球之间留下空隙。反过来,从无限最密堆积中截取有限的一簇球,会产生一个表面层,其空间占据比例与内部主体部分不同。对于形状规则、不断扩大的观察窗口,这类边界贡献的增长阶低于体积:表面尺度的项按 R2R^2 增长,而体积按 R3R^3 增长。

该定理并未断言,所有达到最大密度的堆积都具有某一种特定的整体排列方式。它确定的是最优密度,而非唯一的排列。它所讨论的也是平直、无界的三维空间中的等大球。半径不等的球、弯曲空间、有限容器以及非球形颗粒,都会引出不同的优化问题,即使它们的实际外观看起来也像一堆球。

密排层与最优构造

最优密度可以直接由面心立方堆积(通常缩写为 FCC)计算得出。在一个常规立方晶胞中,每个顶点和每个面的中心都有一个球心。按各个球属于该晶胞的比例计数,一个晶胞内共有四个球:八个顶点上的球合计贡献一个球,六个面心上的球合计贡献三个球。若球的半径为 rr,则沿面对角线方向相切的条件为

a2=4r,a\sqrt{2}=4r,

其中,aa 为立方体的边长。因此,

δFCC=4(4πr3/3)(22 r)3=π32.\delta_{\mathrm{FCC}} =\frac{4(4\pi r^3/3)}{(2\sqrt{2}\,r)^3} =\frac{\pi}{3\sqrt{2}}.

另一种描述从一层相互接触、呈三角形排列的球出发。在这一层中,每个球心都有六个最近邻球心。第二层可以放置在第一层上方的两类三角形凹隙中的任意一类之中。对于单位球,凹隙中心到支撑它的三个球心的水平距离均为 2/32/\sqrt{3}。因此,相邻两层之间的间距为

h=22−(23)2=83.h=\sqrt{2^2-\left(\frac{2}{\sqrt{3}}\right)^2} =\sqrt{\frac{8}{3}}.

在三角格子中,每个球心所占的面积为 232\sqrt{3},因此每个球对应的体积为 23 h=422\sqrt{3}\,h=4\sqrt{2},由此同样可得最优密度。

各层可能占据的位置通常标记为 AA、BB 和 CC。相邻两层的标记不能相同,但在 AA 层和 BB 层之后,第三层既可以占据 AA 位置,也可以占据 CC 位置。重复 ABCABC…ABCABC\ldots 的次序便得到面心立方堆积。重复 ABAB…ABAB\ldots 的次序则得到六方最密堆积,简称 HCP。这些排列具有不同的对称性,较远处的邻域结构也不同,但每个球对应的体积相同。

更一般地,只要相邻标记不同,任意堆垛序列都能构成巴洛堆积。其中有些是周期性的,有些则不是。它们的密度相同,是因为各层的间距和单位面积内的球数均相同,而不是因为它们具有共同的三维周期。因此,非周期性本身并不妨碍达到最优密度。

在面心立方堆积和六方最密堆积中,每个球都与另外十二个球接触:同一层内六个,上方三个,下方三个。这十二处接触有助于解释这两种堆积在力学和晶体学中的重要性,但接触数本身并不能证明密度最优。不同排列可以具有相同的接触数,却以不同方式分布空隙。最优性也不意味着处处都必须保持严格的有序结构:移除有限个球会改变局部结构,却不会改变渐近密度。因此,密度结论所施加的限制,比对所有达到该密度的排列进行完整分类要宽松。

从开普勒到二十世纪的堆积问题

开普勒在其 1611 年的著作《新年礼物,或论六角雪花》中讨论了堆积问题,该书通常简称为《六角雪花》。他对球体紧密堆积的思考,是其对自然界形态与秩序的更广泛研究的一部分。单层球体的三角形排列,以及这些球层的叠放方式,为致密排列提供了几何模型。这一问题也属于近代早期研究炮弹堆放问题的传统,其中包括与托马斯·哈里奥特有关的一些问题。

1831 年,卡尔·弗里德里希·高斯在一个受限情形下取得了决定性成果。高斯证明,在三维空间的所有晶格堆积中,面心立方堆积(FCC)的密度最大。在晶格堆积中,每个球心的位置向量都是三个线性无关向量的整数线性组合。这种代数上的规则性大大缩小了可能情形的范围。然而,一般的堆积未必具有任何平移对称性,因此晶格堆积定理并未触及问题的核心难点。

二维的对应问题则较为容易处理。等圆按三角形排列时,可达到最大的平面堆积密度

π12\frac{\pi}{\sqrt{12}}

。阿克塞尔·图厄在二十世纪之交提出了相关证明,后来拉斯洛·费耶什·托特又给出了系统的几何论述。平面情形的成果启发了将空间划分为胞元的研究方法,但相应的三维胞元在组合结构上要复杂多样得多。能够处理平面多边形的方法,并不能直接用于多面体。

1900 年,大卫·希尔伯特将球堆积问题纳入了他的第十八问题。二十世纪期间,研究者不断得到更严格的密度上界,却始终未能达到猜想所给出的数值。C. A. 罗杰斯利用局部单纯形几何,确立了一个约为 0.77970.7797 的上界,产生了重要影响。这类成果缩小了上界与猜想值之间的数值差距,但也揭示出:要得到精确的证明,不能仅靠对每一小块空间各自独立地应用某个简单估计。

费耶什·托特主张将问题归结为对有限种局部构型的考察,并预见到计算会在其中发挥作用。项武义在二十世纪九十年代初提出了一份证明,但其论证未能以令专家信服的方式确立所需的界,因此未被接受为这一问题的解答。黑尔斯则发展了另一套方案,以局部几何不等式、组合分类和严格计算为基础。他与弗格森的合作最终促成了 1998 年的成果公告。

相关论文经过异常漫长而深入的审稿过程后才得以发表。黑尔斯的主要论述于 2005 年刊登在《数学年刊》上,详细的配套论文则于 2006 年刊登在《离散与计算几何》上。此后进行的形式化验证,解决了仅凭常规数学审稿难以核查庞大计算部分的难题。

局部几何与简单证明的障碍

研究密度的一种自然方法,是为空间中的每个球心划分一个区域。一个球心的沃罗诺伊胞元由所有到该球心的距离不大于到任何其他球心距离的点组成。除共有边界外,这些胞元将空间划分为互不重叠的区域。对于单位球,每个胞元都包含其对应的球;在周期性堆积中,密度等于球的体积除以胞元的平均体积。

在面心立方(FCC)堆积中,每个沃罗诺伊胞元都是体积为 424\sqrt{2} 的菱形十二面体。这启发人们尝试证明:单位球堆积中每个沃罗诺伊胞元的体积都至少为这个值。然而,这条思路行不通,因为某些允许的局部排列会产生体积更小的胞元。一个典型例子是外切于单位球的正十二面体,其体积小于面心立方堆积的胞元体积。与之对应的周围球心可以满足球体互不重叠的约束。

障碍在于全局相容性。一个局部上节省空间的胞元,未必能与自身的副本拼合起来,划分整个空间。正十二面体无法铺满三维欧几里得空间。因此,它在局部体积上的优势不能简单地复制到所有地方。另一个独立的猜想——十二面体猜想——研究的是单个沃罗诺伊胞元可能达到的最小体积,已由黑尔斯和肖恩·麦克劳克林证明。它与开普勒猜想的区别说明了,为何使单个胞元的体积最小与使平均体积最小是两项不同的任务。

另一种方法采用德劳内剖分:连接相邻的球心,将空间划分为四面体;出现退化情形时,也会产生更一般的胞元。四个两两相切的单位球,其球心构成一个边长为 22 的正四面体。位于各顶点处的球体部分占该四面体体积的比例约为 0.77970.7797,超过了全局最优密度。这并不与开普勒定理矛盾,因为正四面体无法无缝隙地填满空间。

事实上,正四面体的内二面角为

arccos⁡(1/3)≈70.53∘.\arccos(1/3)\approx70.53^\circ.

五个这样的角之和小于 360∘360^\circ,而六个之和又大于它。因此,不可能在每条棱周围都排上正四面体,同时仍构成无缝隙的欧几里得空间铺砌。忽略这种不相容性的局部密度估计,因而会给出过于宽松的上界。

成功的证明必须考虑相邻部分之间如何相互制约。它可以允许某些区域的密度异常高,只要由此得到的不等式能迫使其他区域作出补偿。这正是引入精心设计的局部评分的根本原因,而不是试图直接用最终的堆积密度常数来约束每个胞元本身的密度。

化归为有限多个构型

黑尔斯的方法将整体密度问题转化为球心周围的局部不等式。首先,只需考虑饱和堆积,即无法再插入任何单位球的排列。任何堆积都可以在不移除已有球的前提下扩充为饱和堆积。在这样的堆积中,每一点到某个球心的距离都小于 22;否则,就可以在该点再添加一个单位球。这就使相关局部区域的范围得到控制。

原始证明为每个称为“分解星”的局部构型赋予一个评分。分解星的构造结合了沃罗诺伊区域与精心选取的单纯形所提供的信息。这个评分并不只是某个小球簇的密度,而是一种经过专门设计的核算工具:将许多球心的贡献汇总后,只要评分满足一个统一上界,就能推出所需的整体密度上界。

关键估计指出,任何允许的局部构型,其评分都不会高于作为参照的最密堆积构型。为了证明这一点,需要用图来编码局部几何结构。附近的球心确定了从某个指定球心出发的方向;在这些方向之间建立适当的连接,便可得到一个平面组合结构。随后,距离、角度以及球体互不重叠的限制条件,就会约束可能出现的顶点、边和面。

使用图论,可以将两类困难分开处理。图记录哪些相邻球心之间存在关联,而连续变量则记录它们的实际距离和角度。因此,有限个组合类型就能代表无穷多个几何构型。分类的穷尽性至关重要:仅仅找到许多看似合理的类型还不够,因为遗漏的类型中可能藏有反例。

黑尔斯的方案确定了一类有限的、与问题相关的“驯良”平面图。随后,必须对每个尚未排除的图证明:它不可能对应评分超过目标值的构型。许多情形可以用相对粗略的不等式排除。较难的情形则需要更强的估计、对参数范围的细分,或单独的几何论证。弗格森的工作处理了一个尤其棘手的构型,称为五面体棱柱构型。

后来的 Flyspeck 证明对这套方法中的许多重要部分进行了重组,包括局部不等式和分类。因此,不应将经过形式化验证的论证理解为对 1998 年证明每一步的逐字转录。两者共有的策略是:从不受限制的无限排列出发,转向有界的局部数据,再化归为有限多个组合情形,最后归结为严格的不等式。化归为有限情形使计算成为可能,但这一化归本身的正确性,也是一项核心的数学成就。

线性规划、区间界与严格计算

这项计算机辅助证明利用计算来排除整类构型,而不只是寻找密度较高的例子。这一区别至关重要。数值搜索或许会反复发现面心立方堆积(FCC)或六方最密堆积(HCP),却不能排除其他地方存在更优的排列。要证明最优性,就必须用逻辑上有效的排除论证或界限,涵盖每一种允许的竞争构型。

其中一个主要工具是线性规划。边长、角度、立体角和局部评分等几何量满足许多不等式。用有效的线性界替代非线性关系,就能得到一个松弛后的可行域。如果在这个更大的区域上,评分的最大值仍低于目标值,那么原来的整类几何构型也就被排除了。只要保证严格性,就可以有意将松弛范围放得较宽。

如果线性松弛无法得出结论,就可以将变量的取值范围细分,并收紧界限。这类似于数学优化中的分支定界法:将问题划分为若干部分,为每一部分确定界限,再舍弃那些不可能违反预期结论的部分。这种方法能否成功,取决于能否找到既便于计算处理、又不至于留出过多几何自由度的估计。

非线性不等式需要另一种控制手段。在区间算术中,一个量用保证包含其精确值的区间来表示。算术运算产生的也是包含精确结果的区间,而非单个近似数。例如,如果对参数空间中某个容许的长方体区域,评分与其允许最大值之差在整个区域上的上界严格小于零,那么该区域内的每个构型就都能一次性得到验证。

导数估计和泰勒展开有助于使这些界保持紧致。对于足够光滑的函数,长方体区域中心附近的函数值和导数界,可以约束函数在整个区域内的取值。当估计不够有力时,细分区域可以减小不确定性。这些技术还必须处理定义域限制、分母、平方根,以及其他有效性取决于符号或参数范围的运算。

普通的浮点运算本身无法提供这种保证。舍入可能使一个值越过不等式的临界值。因此,严格的数值计算需要受控舍入、精确算术、经过形式化论证的误差界,或具有同等效力的认证手段。显示出来的小数近似值只能表明进行过计算,并不能自动成为其所要支持的定理的证据。

开普勒猜想的证明将人工设计的几何论证与大规模机器核查相结合。理论论证明确了需要验证的内容;计算则承担了数量庞大的有限情形与数值不等式的检验工作。证明的可靠性取决于这两个方面:正确的程序无法弥补不完整的几何归约,而正确的归约也不能为未经核查的数值输出提供依据。

Flyspeck 与形式化验证

原始计算的规模使传统审稿变得困难。审稿人可以评估证明的整体框架,也可以检查其中的许多论证,但独立核查每一处计算细节,与审阅一篇常规期刊论文是截然不同的工作。黑尔斯于2003年启动了 Flyspeck 项目,旨在能够逐步核查逻辑推理的系统中重建这一证明。项目名称是“Formal Proof of Kepler”(开普勒猜想的形式证明)的缩写。

形式证明在精确定义的逻辑框架中表示命题及其推导。证明助手会检查每个推导出的命题,确认它能否通过允许使用的推理规则,从此前已经确立的结果中得出。其目标不是让机器判断文字论述是否有说服力,而是为数学命题提供明确的推导过程。为此,必须将大量相关的几何学、分析学和组合数学知识形式化。

Flyspeck 使用 HOL Light证明助手完成主要的数学形式化工作,并使用 Isabelle 枚举驯顺图。这两个系统发挥了互补作用。几何论证需要一份经过验证的组合情形分类,而这份分类又必须与几何证明所采用的定义和假设相一致。项目还开发了经过形式化核查的方法,用于处理非线性不等式。

项目于2014年8月宣布完成。多位作者合著的论文《开普勒猜想的形式证明》(A Formal Proof of the Kepler Conjecture)于2017年发表。这项成果通过机器核查的数学证明确立了这一密度定理,涵盖了此前使证明难以审查的计算密集型部分。为了使形式化验证切实可行,项目也对数学论证作了修订和简化。

形式化验证缩小了需要信任的基础,而非将其彻底消除。一个小型逻辑内核负责核查证明步骤,从而减少对大型专用搜索程序的依赖。复杂程序可以提出某个结果,但其输出必须转化为可信核查机制能够接受的推导或证书。与其他基于计算机的验证一样,这仍然依赖于对逻辑、实现方式和执行环境的若干假设。

人的作用依然十分重要。定义必须准确表达所要研究的堆积问题;形式化的引理必须与密度命题衔接;数学策略也必须由人构思。Flyspeck 并没有用自动发现来取代这些工作。它的意义在于表明:一个融合连续几何、离散枚举和数值界限的冗长证明,可以纳入系统性的逻辑核查,而不必将其中的计算部分留作需要额外信任的计算结果。

相关堆积定理与不同维度的对比

开普勒猜想属于更广泛的 nn 维欧氏空间球堆积问题。若所堆积的球半径为 rr,则其体积为

Vn(r)=πn/2Γ(n/2+1)rn,V_n(r)=\frac{\pi^{n/2}}{\Gamma(n/2+1)}r^n,

其中 Γ\Gamma 是伽马函数。尺度不变性在所有维度中都成立,但最优排列的几何结构却会发生显著变化。三维空间中的直觉往往难以指导我们理解高维空间中的情形。

在一维空间中,全等线段可以铺满整条直线,密度为 11。在二维空间中,三角格点圆堆积具有最优密度 π/12\pi/\sqrt{12}。三维情形更为困难,部分原因在于局部有利的四面体结构无法均匀地拼合在一起。因此,开普勒猜想证明中涉及的特定局部障碍及用于补偿这些障碍的不等式,都与三维空间密切相关。

另一个相关问题是接吻数问题:有多少个互不重叠的全等球可以同时与一个中心球相切?在三维空间中,答案是十二;库尔特·许特和巴特尔·伦德特·范德瓦尔登于1953年证明了这一点。这与面心立方堆积(FCC)和六方最密堆积(HCP)中每个球有十二个接触球的情况相符,但并不能证明这两种堆积的密度最优。接触数的上界只约束一个局部邻域,而密度取决于所有邻域如何拼合在一起。

在某些特殊的高维情形中,人们用不同方法得到了精确解。2016年,玛丽娜·维亚佐夫斯卡证明了八维空间中 E8E_8 格堆积的最优性。不久之后,亨利·科恩、阿比纳夫·库马尔、斯蒂芬·D. 米勒、丹尼洛·拉德琴科和维亚佐夫斯卡证明了二十四维空间中利奇格堆积的最优性。这两种堆积的密度分别为 π4/384\pi^4/384 和 π12/12!\pi^{12}/12!。

这些证明在科恩–埃尔基斯线性规划框架中使用了能给出精确界的辅助函数。对函数及其傅里叶变换施加适当条件,便可推出堆积密度的上界。尽管都使用“线性规划”这一术语,这种分析方法与开普勒猜想证明中用于排除局部构型的有限变量线性规划并不相同。

高维结果还揭示了球堆积与信息论之间的联系。一组彼此充分分离的点可以用来表示可区分的信号:足够大的间距能使它们在受到有界噪声干扰时更不容易混淆。因此,格与球堆积将几何优化和编码理论联系起来。三维空间中的这一精确定理,是一个范围广泛得多的问题族中尤为著名的实例,而其中大多数问题的精确答案仍然未知。

物理意义与定理的局限

最密堆积在晶体学中十分重要,因为面心立方堆积(FCC)和六方最密堆积(HCP)描述了理想化晶体结构中常见的原子排列方式。在通常条件下,铝和铜具有面心立方结构,而镁具有六方最密堆积结构。硬球模型能够解释它们的配位几何结构和体积占比,但这终究只是一个模型:原子并不是具有清晰边界的刚性球体。

这一定理也为研究颗粒材料提供了参照。实验和模拟往往会得到密度接近 0.640.64 的无序球体堆积,低于约为 0.740480.74048 的晶态最大密度。具体密度取决于制备过程,包括压缩、振动、摩擦以及允许形成有序结构的程度。除非明确定义随机性和力学约束,否则“随机最密堆积”这一说法并不能确定一个唯一的数学优化问题。

密度与堵塞转变是不同的性质。一个堆积可以阻止某些特定的颗粒运动,却未必达到最大的体积占比。反过来,密度定理本身也不能确定堆积在力、摩擦或边界约束下的力学稳定性。不同的堵塞概念,会分别规定单个颗粒、有限个颗粒组成的群体,或整个堆积及其外围边界是否可以运动。

考虑热运动的硬球系统还引出了另一层区别。在非零温度下,平衡行为取决于系统可达到的构型数目,而不只是某一种静态排列的密度。因此,硬球系统的凝固,以及面心立方堆积与六方最密堆积的相对自由能,都是统计力学问题,并非开普勒定理的直接推论。最大密度相同,并不意味着在较低密度下的行为也完全相同。

等半径假设尤其具有局限性。在由半径为 RR 的球组成的最密堆积中,能够放入理想八面体空隙的最大球的半径为

roct=(2−1)R,r_{\mathrm{oct}}=(\sqrt{2}-1)R,

而能够放入四面体空隙的最大球的半径为

rtet=(32−1)R.r_{\mathrm{tet}}=\left(\sqrt{\frac{3}{2}}-1\right)R.

在这些空隙中加入较小的球,无须移动大球,就能提高总体积占比。这并不违背定理,因为此时堆积中的球已不再全等。

改变颗粒形状同样会改变问题。全等椭球体、四面体或其他形体的堆积密度可以超过球体的最大堆积密度。对于有限容器中的堆积问题,结果还取决于物体的数量和容器的尺寸。开普勒定理针对一种严格界定的几何情形,给出了精确的宏观极限;要对晶体、粉末或人工设计的颗粒混合物作出定量预测,还需要对形状、相互作用、无序性和边界作出额外假设。