结果族 183：Power savings for planar halving lines and k-sets · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
操场上站 n 个人，任意两人之间可以拉一条线。若某条线恰好把其余的人对半分到两侧，它就叫”平分线”。几十年来大家只知道平分线不超过 C·n^(4/3) 条；这篇论文证明实际上还要再少一个固定幂次——至多 C·n^(4/3−ε) 条，是 Dey 的 4/3 指数保持近三十年后首次被突破。
关键词卡片
看个具体例子
10 个点时，一条平分线长这样（线上 2 点，两侧各 4 点）：
数字版：n=10^6 时老界是 C·10^8 条，新界是 C·10^(8−6ε) 条，差距随 n 放大。同文的更强结论对每个”秩”一致成立，并推出 k-集个数至多 C·n·k^(1/3−ε)。已知构造只有约 n·e^(c√log n) 条平分线，上下界间的鸿沟仍然巨大。
为什么值得关心
平分线计数是 k-集问题与许多几何算法复杂度分析的核心瓶颈，指数上的任何突破都是领域事件——何况是悬置近三十年的 4/3。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”操场拉平分线”的画面，对象是平面上一群处于一般位置的点，操作是过其中两点作直线，”平分”指这条线把其余的点不多不少分到两侧各半。要问的是：这样的点对最多能有多少对？直觉上点可以排得刁钻让平分线层出不穷，但经典理论早就给出 n^(4/3) 的天花板。
第二级台阶
用本科语言精确化：设 P 为无三点共线的 n 点集（n 偶），若两点确定的直线使其余 n−2 个点两侧各留 (n−2)/2 个，称其为一个平分对，个数记 h(P)。k-集指能被某条直线从点集中严格切出的 k 个点，平分是它的中间秩情形。经典工具是交叉数引理——边画得太密必有大量交叉——Dey（1998）据此证得 h(P) = O(n^{4/3})。幂节省指把指数压到 4/3 − ε，ε > 0 为绝对常数。
第三级台阶
定理的语境是斜率扫描：让过点集的直线方向从竖直转起，标记最低的 k 个点，转动中标记集”一换一”地交换；中间秩的交换恰是平分对。定理 1.1 断言 h(P) ≤ C·n^(4/3−ε)，对一切构形一致。更强的定理 1.2 对每个秩 k 一致给出交换总数 S_k(P) ≤ C·N^(4/3−ε)——这个一致性不可省，因为把一段交换限制到其活动点集上，秩就变了；归纳法必须对所有秩同时成立。”无三点共线”挡住的是退化：它保证不同点对给出不同直线、平分计数无歧义。推论 1.3 把幂节省传导到 k-集计数与直线排列第 k 层的复杂度。证明是非定量的：ε 存在但无可用数值。
证明了存在绝对常数 @@M@@\varepsilon>0@@，使平面上无三点共线的偶数 @@M@@n@@ 点集至多有 @@M@@Cn^{4/3-\varepsilon}@@ 对平分点（halving pair）——这是 Dey 的 @@M@@O(n^{4/3})@@ 界保持近三十年后指数首次被突破；同样的幂次节约还推广到 @@M@@k@@-set 计数与直线排列的层复杂度。
设 @@M@@P@@ 为平面上 @@M@@n@@ 个点（@@M@@n@@ 为偶数，无三点共线）。若一对点确定的直线把其余 @@M@@n-2@@ 个点恰好平分到两侧，这对点就是平分对（halving pair），其直线为平分线（halving line），个数记作 @@M@@h(P)@@。该问题源自 1970 年代初 Lovász 与 Erdős–Lovász–Simmons–Straus 的工作，是 @@M@@k@@-set 问题（k-set problem：用直线能从点集中严格分离出多少个 @@M@@k@@ 点子集）的中间秩情形，也是计算几何诸多算法复杂度分析的瓶颈。上界方面：先驱工作给出 @@M@@O(n^{3/2})@@；Pach–Steiger–Szemerédi（1992）改进一个迭代对数因子；Dey（1998）用凸链分解与交叉数引理（crossing lemma）证得 @@M@@O(n^{4/3})@@，此后指数近三十年无人撼动。下界方面，最好的构造（Tóth、Nivasch）只达到 @@M@@n\exp(\Omega(\sqrt{\log n}))@@，远低于任何固定幂 @@M@@n^{1+\delta}@@，上下界之间的鸿沟一直悬而未决。本文首次在上界指数上打开缺口。
主定理（定理 1.1）：存在绝对常数 @@M@@\varepsilon>0@@、@@M@@C@@ 与 @@M@@n_0@@，使对一切偶数 @@M@@n\ge n_0@@ 与无三点共线的 @@M@@n@@ 点集 @@M@@P@@，有 @@M@@h(P)\le Cn^{4/3-\varepsilon}@@；改进体现在指数上，且对所有构形一致。
全秩一致界（定理 1.2）：以 @@M@@S_k(P)@@ 记斜率扫描（见下）中秩 @@M@@k@@ 处交换（switch）的总数，则对每个秩 @@M@@0\le k\le N@@ 一致地有 @@M@@S_k(P)\le CN^{4/3-\varepsilon}@@。中间秩的交换恰为平分对，主定理是其特例；@@M@@k@@-set 应用恰恰需要这种对秩的一致性。
@@M@@k@@-set 推论（推论 1.3）：对 @@M@@1\le k\le n/2@@，任一 @@M@@n@@ 点集的 @@M@@k@@-set 个数至多 @@M@@C_0\,n(k+1)^{1/3-\varepsilon_0}@@；同样的界适用于一般位置直线排列中第 @@M@@k@@ 层（@@M@@k@@-th level）的复杂度，改进了 Dey 的 @@M@@O(n(k+1)^{1/3})@@。论文不对伪直线（pseudoline）或线段排列作相应断言。
另需强调：证明是非定量的（nonquantitative），既不给 @@M@@\varepsilon@@ 的数值，也不给 @@M@@C@@、@@M@@n_0@@ 的有效值。
证明分三步：先证一致的装填小-@@M@@o@@ 改进，再用固定尺度递推兑换出幂次节约，最后经对偶导出 @@M@@k@@-set 推论。
第一步把问题改写为斜率扫描（slope sweep）：点按 @@M@@y-sx@@ 从小到大排序，标记最小的 @@M@@k@@ 个；让斜率 @@M@@s@@ 从 @@M@@-\infty@@ 增到 @@M@@+\infty@@，标记集不断”一换一”地交换，一段区间的活动度（activity）是其间隶属关系变过的点数。finite 一节复现 Dey 的机制：把扫描贪心切成批（batch），每批各失去、得到 @@M@@a@@ 个点，连成 @@M@@a^2@@ 条边的交换图；这些边既能分解为至多 @@M@@aS@@ 条凸链、也能分解为至多 @@M@@aS@@ 条凹链，再用交叉数引理得：步集互斥、活动度至少 @@M@@b@@ 的区间至多 @@M@@O((N/b)^{4/3})@@ 个——指数 @@M@@4/3@@ 正源于此；新的一致活动装填定理（定理 2.1）断言：对每个 @@M@@\xi>0@@，只要 @@M@@N/b@@ 充分大，常数可压到 @@M@@\xi@@ 以下。
第二步是核心，反证：设一列构形的批数 @@M@@R\asymp(N/a)^{4/3}@@ 达到临界。先给每点配紧致的秩坐标（rank coordinate）——某时间窗内 @@M@@M=aN@@ 条凸链图中位于其下方的比例（经平滑）；因扫描方向随时间单调旋转，两个分离窗口的坐标 @@M@@(r_A,r_B)@@ 是平面到 @@M@@(0,1)^2@@ 的同胚。对顶点、边、交叉赋权取弱极限测度后：交叉测度的投影受 Lebesgue 测度控制；带指定端点的交叉不等式使边质量对顶点质量绝对连续；正份额的边质量必被交叉”看见”。难点是秩坐标不控制欧氏距离——秩方块里的小块可能对应原平面极度扭曲的区域。differentiability 与 zoom 两节用其余窗口坐标的单调性与 Lipschitz 函数几乎处处可微性，迫使三族扫描线的极限方向彼此横截，再以局部刚性引理（先固定小秩尺度、再沿构形序列取极限）阻止几何塌缩，得逆映射的 Hölder 下界。spatial 一节删去顶点投影的奇异部分并截断密度，得空间测度：圆盘质量至多 @@M@@C_Gr^{32/17}@@、条带质量至多 @@M@@C_Gr^{15/17}@@（@@M@@32/17>7/4@@ 是关键数值）。boundary 一节的”三条带”引理收网：切割方向近乎平行时，有界区域内的参与顶点要么落入三条窄带，要么被穿越边界的令牌（token）计入，二者总量皆有预算；结合 Hölder 不等式求和，极限质量不超过 @@M@@CM^{-4/3}+C_GM(\delta^{1/12}+\delta^{3/68})@@，先令 @@M@@\delta\to0@@ 再令 @@M@@M\to\infty@@ 得零，与正质量矛盾。
第三步兑现幂次：取定尺度 @@M@@q@@（由装填定理保证，非定量），把扫描切成至多 @@M@@q^{4/3}/2@@ 个活动度约 @@M@@N/q@@ 的块；每块限制到其活动点集上仍是某固定秩的扫描，规模至多 @@M@@N/q@@，归纳得 @@M@@F(N)\le(C/\sqrt2)N^{4/3-\varepsilon}@@，@@M@@\varepsilon=\log 2/(2\log q)@@——收缩因子 @@M@@1/\sqrt2@@ 即幂次节约之源。@@M@@k@@-set 推论由点线对偶（排列顶点数即交换数）与浅切割（shallow cutting：@@M@@O(n/(k+1))@@ 个胞腔、每个仅被 @@M@@k+1@@ 条线穿过）导出。
依任务元数据，本文主结果暂无 Lean 形式化证明；OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。本结果族 183 目前仅收录本文一篇，无独立姊妹篇；但文内三层结论自洽相依：全秩一致界是枢纽，主定理与 @@M@@k@@-set 推论均由它导出。另需注意证明完全非定量：论文不排除 @@M@@\varepsilon@@ 极小，”幂次节约”是存在性结论。
问 1：证明中最脆弱的一环在哪里？
（答：从秩坐标到欧氏几何的控制。反证法假设装填界被渐近达到，取极限测度后，秩坐标并不控制真实距离——秩方块里的小块可能对应平面上极度扭曲的区域。论文靠三个扫描窗口坐标的单调性与 Lipschitz 函数几乎处处可微，迫使三族扫描线极限方向横截，再用”局部刚性引理”阻止塌缩。该引理的极限次序是先固定小秩尺度、再沿构形序列取极限——次序一旦交换，结论即可能失效，这是全文最精妙也最易受攻击的一步。）
问 2：辅助指数 32/17 与 15/17 是怎么回事？
（答：spatial 一节删奇异部分、截断密度后得空间测度：半径 r 圆盘质量 ≤ C·r^(32/17)，宽 r 条带质量 ≤ C·r^(15/17)；32/17 > 7/4 是让”三条带”引理收网的关键数值。但这两个指数不是最终的 ε——幂次节约来自其后固定尺度 q 的递推，ε = log2/(2 log q)。）
问 3：为什么必须证全秩一致界，而不能只盯中间秩？
（答：定理 1.2 的均匀性正是为归纳服务的：把一段交换限制到其活动点集上，秩会改变；若只控制中间秩，递推在块内就无法继续。秩 0 与 N 处 S_k = 0，边界无害。）
问 4：与 Dey 及 2024 年的改进相比，真正新意是什么？
（答：Dey 的 O(n^{4/3}) 悬置近三十年，Alonso–López–Rodrigo（2024）只改进低阶项、保住 4/3；本文不是精化 Dey 的组合论证，而是证明一致的 little-o 装填改进（定理 2.1）再兑换成幂次——方法论上引入了测度弱极限与刚性论证，是质的换轨。）
问 5：非定量证明意味着什么？
（答：论文明确声明不给 ε、C、n₀ 的任何数值：装填定理只说 N/b 充分大时常数可压到 ξ 以下，尺度 q 由存在性保证。与下界 n·exp(Ω(√log n)) 之间仍隔天堑，本文只打开指数缺口，不逼近真值。）
问 6：这类 AI 生成证明最可能出什么错？
（答：极限交换与测度正则性的配合。全文把有限组合计数（交叉数、令牌穿越预算）与测度论机器（弱紧性、Radon–Nikodym 分解、a.e. 可微）缝在一起，任何一处”取极限”次序不当或奇异部分没删干净，三条带引理的求和就会漏项。机器生成证明恰好在”先 δ→0 还是先 M→∞”这类顺序细节上最容易出错，而本文结论恰恰系于此。）
总评
（这是 k-集/平分线领域近三十年指数上的首次突破，且附带全秩一致界与 k-集推论，分量十足；最大风险是那条依赖极限次序的刚性论证链——优雅但脆，未经形式化核验前应视为待确认的突破。）