九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

爱多士单位距离问题

《图论中的 50 个公开问题》 · 问题 32 专题综述

题面n 个平面点最多产生多少对单位距离?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

爱多士 1946:平面上 n 个点的集合最多能决定多少对距离恰为 1 的点对?记 u(n)。已知下界 n1+c/log log n(整数格构造),上界 n4/3(Spencer–Szemerédi–Trotter 1984)。八十余年两个界之间纹丝不动。

主要概念

整数格构造

在 √n×√n 方格中取点,选距离 d(使 d² 有很多 «素因子分解» 表法),则 «半径 d 的圆» 过格点的期望数 ≈ r(d²)(除数函数)——取 d 使 r(d²) ≈ elog 2·log n/log log n,得 u(n) ≥ n·r/2 ≈ n1+c/log log n。

SST 上界的两条路

①交叉引理:把 «单位圆» 视为 «圆»、点视为 «顶点»,得 «圆–点关联» 图,其交叉数 ≤ 圆对相交数;Szemeredi–Trotter 型 «关联计数» 上界 O(m2/3n2/3+m+n) 翻译过来即 u(n) ≤ n4/3。②多项式方法(Guth–Katz 的 «距离问题» 用的同一机器): «多项式切分» 把空间 «分而治之»——Guth–Katz 用它把 «distinct distances»(对偶问题)压到 n/log n,但 «单位距离» 的同类突破未成—— «重根结构»(很多圆过同两点)卡住机器。

主要命题与证明

命题 1(SST 上界完整骨架) u(n) = O(n4/3)。

梗概 把 «点–单位圆» 关联图 G(顶点 = 点, «边» = 圈, «关联» = 点在圆上)做 Szemerédi–Trotter 分割:以 K2,2(两圆过同两点 = 至多 C(n,2) 次)控制 «重根»,经 «交叉不等式»(关联图的画法交叉数 ≤ 圆对相交数 ≤ 圆数²)得 «关联 ≤ m2/3n2/3 + m + n»;代 m = n 个单位圆、每圆平均 n1/3 点,即 u(n) ≤ n4/3。□

命题 2(下界的除数函数核心,完整推导) 存在 d 使 r(d²) ≥ e(log 2−o(1))·log n/log log n—— «超完全数» 型除数爆炸:取 d² 为 «前 k 个素数之积» 型(d² = ∏pi2,则 r(d²) = ∏(2ei+1) 型), «格点圆» 的平均点数由 «平方和表示数 r₂» 的素因子公式给出。

进展与文献

爱多士 1946 原文;Spencer–Szemerédi–Trotter 1984;Matoušek《Lectures on Discrete Geometry》专章;Guth–Katz 2015(Annals)的 «distinct distances» 解决—— «机器在隔壁问题成功、本问题受阻» 的当代格局;Sheffer 的单位距离综述。开放核心:n1+ε 构造是否存在( «格之外的构造» 完全缺席);上界压到 n1+o(1) 需 «重根» 的新处理——多项式方法、代数几何(切簇)、加法组合三线交汇处。

← 返回问题 32