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

非求平均集合的极值

《组合设计中的 50 个公开问题》 · 问题 44 专题综述

题面[1,n] 中最大的「无 3-项等差数列」子集的渐近公式是什么?

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

问题

[1,n] 中不含 3-项等差数列(x,y,z 互异且 x+z=2y)的子集最大多大?记 r₃(n)。已知:Behrend 下界(1946)r₃(n) ≥ n·exp(−C√(log n))——70 余年未被实质超越(Elkin 的指数常数改进是唯一微雕);上界侧:Roth(1953)n/log log n → Sanders → Bloom–Sisask(2020)n/(log n)1+c——上下界之间是 «exp vs log» 的天壤,这是加法组合最著名的 «上下界夹心»。与 30 号(𝔽₃ⁿ 的帽集)对照:有限域向量的 «多项式方法革命» 没有给整数情形带来实质突破——«序结构» 使机器失灵。

主要概念

Behrend 的球面构造

把 [1,n] 的数写成 d 维 «数字»(基 m):落在 «半径固定的高维球面» 上的点无 3-AP(球面上 «中点严格在球内»——严格凸性)。选 «最大层» 得 «大无 AP 集»:优化 d 给 exp(−C√log n) 型。构造的 «凸性» 是全部魔力的来源——而有限域无序无凸,故 30 号的机器在这里失效。

上界的 «密度增量» 机器

Roth 的机器:密度增量迭代——«正密度的集合有 «近» 密集子区间»(能量增量),迭代 log log n 次清零。每次增量的 «定量» 是四十年改进的战场(Heath-Brown、Szemerédi、Bourgain、Sanders、Bloom–Sisask);当前上界 n/(log n)1+o(1) 的 «下一个常数» 是现役攻坚点。

主要命题与证明

命题 1(Behrend 下界,1946,完整证明) 存在 A ⊆ [1,n],无 3-AP,|A| ≥ n·exp(−2√(2 log 2·log n)·(1+o(1)))。

证明 取基 m=2⌈√log₂ n⌉、维数 d 使 md ≈ n:把 [1,n] 的数对应 «坐标和 ≤ m» 的格点 {[x₁,…,xd]ₘ}(数字 xj ∈ [0,m/2))。格点落在 «球壳» 半径 r ∈ [0, d(m/2)²) 的球面族中,由鸽笼某球面含 ≥ 格点总数/球面个数 ≈ n/(d·m²)个点。球面上的点集无 3-AP:若 x+z=2y(坐标级),则 |x|²+|z|² = 2|y|²+2|y−x|² ≥ 2|y|²,等号 ⟺ x=y=z(严格凸性)——互异 3-AP 不可能同球面。|A| ≥ n/(2d·m²) = n·exp(−O(√log n))。□

命题 2(Roth 定理的定量形态;陈述) r₃(n) ≤ C n/(log n)1+c(Bloom–Sisask 2020,c>0 显式)。历史:Roth 1953(log log)、Heath-Brown/Szemerédi(logc)、Bourgain(log/log^{1−ε} 微调)、Sanders((log n)1/2−o(1) 的 «除数» 形态)、Bloom–Sisask 突破到 «>1 的幂»。机器:密度增量 + «能量 » 的 Fourier 控制。

说明 «下界 exp(−√log) vs 上界 (log)^{−1−c}»:两端在 «对数尺度» 上相距一个 «exp»——«Behrend 是否接近真相» 是整数 AP 理论的百年之问。□

命题 3(Kelley–Meka 的 2023 突破;陈述) Kelley–Meka(2023)把上界大幅改进到 «准 Behrend»:⟨准指数的 «随机化 Fourier» 论证⟩——整数情形的 «多项式方法革命» 初现端倪;«Behrend 型下界是否最优» 的判定因此进入射程。

说明 这是 «谱系最新一格»: Kelley–Meka 的机器(«分级 Fourier + 随机化» )首次让整数上界 «接近» Behrend 的指数——两端的会合是本十年的头号悬念。□

进展与文献

Behrend 1946;Roth 1953;Sanders 2011;Bloom–Sisask 2020;Kelley–Meka 2023;Elkin 的下界微雕;Tao–Vu 教材第 10 章。开放核心:r₃(n) 的真渐近;«整数 cap set» 的机器移植极限;高阶 AP(k≥4 项)的对应常数谱(Gowers 界与 green–Tao 的应用侧)。

← 返回问题 44