Dense ascending waves: A resolution of the Alon-Spencer conjecture

技术摘要：稠密上升波与 Alon–Spencer 猜想的解决

问题陈述
本文研究了关于整数稠密子集中“上升波”（ascending waves）的一个极值组合数学问题。对于正整数 $n$，令 $[n] = \{1, \dots, n\}$。一个严格递增的整数序列 $x_1 < \dots < x_k$ 被定义为“上升波”，如果其相邻差值是非递减的（即 $x_{t+1} - x_t \ge x_t - x_{t-1}$）。

令 $g(n)$ 表示满足以下条件的最大的整数 $k$：每一个密度至少为 $1/2$ 的子集 $A \subseteq [n]$（即 $|A| \ge n/2$）都包含一个长度为 $k$ 的上升波。Alon 和 Spencer 此前已经确定，对于足够大的 $n$：
$$c_1 \frac{(\log n)^2}{\log \log n} \le g(n) \le c_2 (\log n)^2$$
他们猜想，下界中的 $\log \log n$ 因子并非本质性的，并猜测 $g(n) = \Theta((\log n)^2)$。本文的主要目标是通过建立匹配的下界来证明这一猜想。

方法论
本证明采用了一种结合相位空间动力学（phase-space dynamics）与确定性填充论证（deterministic packing arguments）的新颖综合方法，以克服直接贪婪分析（greedy analysis）的局限性。作者指出，在以往的尝试中，在序列早期产生的“投影误差”（projection errors）会导致多个暂时的轨迹聚焦于同一个间隙（gap），使得对命中事件（hitting events）进行独立的概率处理变得无效。

为了解决这一问题，本文引入了以下框架：

1. 相位空间动力学与影子映射（Shadow Map）：
   作者定义了一个“相位点” $p = (u, d) \in \mathbb{R}^2$，其中 $u$ 是位置，$d$ 是差值。他们引入了一个由 $T: D \to X$ 定义的“影子映射” $T(u, d) = (u+d, d + 2\rho(u+d))$，其中 $\rho(z)$ 是 $z$ 在集合 $A$ 上的超量（overshoot）。

   • 关键性质： 映射 $T$ 是一个保测度的 Borel 双射，且是面积保持（保 Lebesgue 测度）且可逆的。
   • 意义： 通过将投影误差 $\rho$ 作为第二个状态变量保留下来，动力学过程变得可逆。这使得“聚焦”现象（即许多轨迹命中同一个间隙）转化为相位空间中的一个确定性填充问题，其中对固定间隙的重复活跃命中对应于不相交的图像切片（image slices）。

2. 局部平方能量定理（第 3 节）：
   作者定义了尺度 $D$ 下的一个区间 $I$ 的“短间隙平方能量” $E_D^<(I)$。他们证明了一个局部定理（定理 3.2），即如果一个局部窗口 $J$ 具有足够低的平方能量（具体为 $E_D^<(J) \le \epsilon D$），那么存在一个起始点，能够生成一个具有受控差值的长度为 $L$ 的局部上升波。

   • 该证明利用了一个“填充估计”（引理 3.1），表明任何间隙 $G$ 上的活跃命中总相位空间面积被 $5D|G|$ 所限制。这使得将能量界限转化为存在一个避免跨越“超量阈值” $D$ 的有效轨迹成为可能。

3. 全局尺度选择与多尺度拼接（第 4 节）：
   为了构造一个全局上升波，作者选择了一系列尺度 $D_i = 2^i$，并识别出一个在多个尺度下都是“容许的”（admissible）“共同起始点” $x^*$。

   • 容许性： 一个点在尺度 $i$ 下是容许的，如果它满足安全条件（保持在边界内）、避开了大间隙，并且具有较低的局部平方能量。
   • 选择： 通过对间隙集合和点集的平均论证，作者证明了存在一个在规模集合 $I$ 上均是容许的点 $x^*$，且满足 $|I| \ge \frac{1}{32} \log n$。
   • 拼接： 通过选择一组几何间隔（由因子 $Q=128$ 分隔）良好的尺度子集 $I'$，作者迭代地应用局部定理。这种大幅度的间隔确保了新局部波的“桥接”差值大于前一个局部波的最终差值，从而在拼接时保持了上升波的性质。

主要贡献与结果

• 解决猜想： 本文证明了定理 1.2：存在一个绝对常数 $c > 0$，使得每个满足 $|A| \ge n/2$ 的集合 $A \subseteq [n]$ 都包含一个长度至少为 $c(\log n)^2$ 的上升波。
• 渐近紧致性： 结合 Alon 和 Spencer 提供的上界，这确立了 $g(n) = \Theta((\log n)^2)$，证实了猜想 1.1。
• 方法论创新： 本文引入了一种相位空间提升（phase-space lift），将涉及相关命中事件的问题转化为一个确定性的面积保持问题。这避免了以往分析中由于独立性假设而导致的“对数损失”。
• 显式构造： 证明具有构造性特征，依赖于满足特定能量和间隙条件的点的存在，而非纯粹的概率存在性论证。

意义
本文声称消除了稠密上升波下界中的“对数损失”，这是一个自 Alon 和 Spencer 的工作以来一直悬而未决的问题。其意义不仅在于对界限的定量改进，更在于方法论的定性转变：用确定性的、面积保持的动力系统方法取代了独立性假设。这种技术通过相位空间中的几何填充来控制轨迹的聚焦，为分析波形配置及相关的极值组合问题提供了新的工具。该结果解决了稠密集合上升波函数的渐近行为，将其稳固地置于 $(\log n)^2$ 的范畴内。