P21 · 最优性证明

九个点,八块区域

HwaterB 的分割证明补上了九点猜想的上界,不需要对称性假设或数值搜索。

区域定义

取由五个单位正方形组成的闭十字形,边界也属于区域:

C = ([1,2] × [0,3]) ∪ ([0,3] × [1,2]).

对 C 内任意九个互不相同的点组成的集合 S,记 δ(S) 为最小两点欧氏距离。下面先证明适用于所有 S 的上界,再给出达到它的构型。

1. 用八块直径受限的区域覆盖十字形

沿平行于外侧边的方向,把四条单位正方形臂各切成两半,外侧的四个半臂保留为矩形。再沿中央正方形的两条对角线切出四个三角形,把每个三角形与相邻的内侧半臂合并。于是得到四个矩形和四个凸五边形。

12345678
四个 1 × 1/2 矩形(绿色)与四个凸五边形(紫色),包含公共边界。

只需检查上方的两块区域,其余六块是它们绕 (3/2,3/2) 旋转得到的全等图形:

R = [1,2] × [5/2,3],
P = conv{(1,2), (1,5/2), (2,5/2), (2,2), (3/2,3/2)}.

矩形的直径为 √(1²+(1/2)²)=√5/2。五边形五个顶点之间的十个距离平方均属于 {1/4, 1/2, 1, 5/4},最大值为 5/4。

为什么只检查顶点就够了?若凸多边形的任意两顶点距离都不超过 D,把其中任意两点写成 x=Σαᵢvᵢ、y=Σβⱼvⱼ,其中系数非负且分别求和为 1。由三角不等式,

‖x−y‖ = ‖Σᵢⱼ αᵢβⱼ(vᵢ−vⱼ)‖ ≤ Σᵢⱼ αᵢβⱼ‖vᵢ−vⱼ‖ ≤ D.

所以整个五边形的直径也是 √5/2,而不只是顶点对满足这个界。八块闭区域的直径都不超过 √5/2。

2. 九个点必有两个落在同一块

把每个点分配给包含它的一块区域;若落在公共边界上,任选其中一块即可。九个点分配到八块区域,由抽屉原理,至少两个点被分到同一块。它们的距离不超过该块的直径,所以 δ(S)≤√5/2。这个论证同样包含所有切割线和 C 的边界上的点。

3. 达到上界的精确构型

取四个顶点 (1,0)、(3,1)、(2,3)、(0,2),再加入它们相邻边的四个中点和中心 (3/2,3/2):

(1,0), (3,1), (2,3), (0,2),
(2,1/2), (5/2,2), (1,5/2), (1/2,1), (3/2,3/2).

顶点、边中点与中心组成一个旋转后的 3 × 3 正方形网格。

所有点都属于 C。更具体地,它们可写为 (1,0)+iu+jv,其中 i,j∈{0,1,2},u=(1,1/2)、v=(−1/2,1)。由于 u·v=0,且 ‖u‖²=‖v‖²=5/4,任意两点的距离平方为 (5/4)((Δi)²+(Δj)²)≥5/4;相邻网格点达到等号。

max δ(S) = √5/2 ≈ 1.118033988749895. ∎

贡献与核验

HwaterB #40 在原帖中提出了八块区域的上界论证,并已在回复中更正“小长方形”的笔误:其中四块是五边形。极值竞技场核验了几何细节,补全公共边界与凸性论证,并完成这份中英文正式表述和配图。八块分割这一数学思路归于 HwaterB。

达到上界的构型已出现在 HwaterB #40 于 8 月 29 日提交的纪录中。NUE_13 #31 随后也在投稿中描述了同一九点构型与最优值猜想,见此前的证明页面;这份讨论贡献同样保留。本次发布补上缺失的上界,并保留 HwaterB 的原有纪录。 此前构型与讨论

配套精确算术测试检查八块多边形的直径与覆盖、构型的全部 36 个点对,以及正式验证器得到的精确距离平方 5/4。测试用于防止实现出错;上界来自上述解析证明,而不是采样实验。