Hitting Arithmetic Progressions at the Square-Root Scale

技术摘要：在平方根尺度下击中算术级数

问题陈述
本文研究了函数 $f(N, k)$，其定义为集合 $A \subseteq \{0, 1, \dots, N-1\}$ 的最小基数，使得该集合与包含在区间内的每一个 $k$ 项算术级数（AP）都有交集。该问题是经典无级数集极值问题的补集。当 $k$ 固定时（由 Szemerédi 定理可知 $f(N, k) = N - o(N)$），以及当 $k$ 随 $N$ 的幂次增长时（其中 $f(N, k) \ll N^{1-\epsilon}$），$f(N, k)$ 的行为已得到充分理解；而本文则聚焦于“平方根尺度”机制，即 $k \approx \sqrt{N}$。在此情形下，$N = n^2$ 且 $k \approx n$，这是一个转换点，简单的构造方法（如质数倍数法）不再能自动匹配平凡的块下界。

方法论
本文结合了初等组合论证、数论引理和概率构造方法。

• 下界： 证明依赖于将区间 $[0, n^2-1]$ 划分为长度为 $k$ 的连续块。作者分析了“单元素运行”（singleton runs）——即仅包含一个选中点的连续块序列。通过定义基于这些点相对位置的“下降序列”，作者推导出了强整除约束。其核心组成部分是“下降同余引理”（Descent Congruence Lemma，引理 2.2），该引理确立了非恒定下降序列必须具有二次总质量。该引理结合有限同余论证，迫使击中集的规模超过平凡界限，并多出一个特定的二阶项。
• 上界： 上界构造采用了一种“随机前沿”（randomized front）方法，随后进行修正步骤。区间 $[0, p^2-1]$ 被视为行与列组成的网格。构造过程通过一个“前沿”行确定性地覆盖大公差和特定剩余类。对于剩余的级数（即那些被限制在顶层行的、具有小公差的级数），则使用随机分配点的方法。作者计算了漏掉的级数的期望值，并证明该期望值足够小，可以通过添加极少量点来进行修复。

主要贡献与结果

1. 改进的关键下界（定理 1.1）：
   作者改进了 $f(n^2, n)$ 下界中二阶项的领先常数。此前 Truss 证明了 $f(n^2, n) > n + \frac{1}{2}n^{1/2} - 2$，而本文建立如下结论：
   $$f(n^2, n) \ge n + \left(\frac{1}{\sqrt{2}} + o(1)\right)n^{1/2}$$
   该结果是通过分析长运行单元素块中下降序列的约束得出的。

2. 广义临界以下下界（定理 1.2）：
   该结果被扩展到 $k = n - \theta n^{1/2} + O(1)$（其中 $\theta \ge 0$ 为固定值）的机制。本文证明：
   $$f(n^2, k) \ge \left\lfloor \frac{n^2}{k} \right\rfloor + \left( \frac{\sqrt{\theta^2 + 2} - \theta}{2} + o(1) \right) n^{1/2}$$
   该公式在临界尺度与 $k$ 略小于 $n$ 的机制之间进行了插值。

3. 更强的渐近上界（定理 1.3）：
   对于素数平方情况 $N=p^2, k=p$，作者改进了 Brown 和 Freedman 的 $2p-2$ 界的结论以及随后的对数级节省。他们证明：
   $$f(p^2, p) \le 2p - \left(\sqrt{\frac{2}{3}} - o(1)\right)\sqrt{\frac{p}{\log p}}$$
   这是通过带有修正步骤的随机前沿构造实现的，从而节省了一个数量级为 $\sqrt{p/\log p}$ 的项。

4. 转换点分析（命题 1.4）：
   本文确认了 $k = N^{1/2}$ 是一个转换点。对于 $k = N^c$ 且 $c > 1/2$ 的情况，函数表现为 $f(N, k) = (1+o(1))N/k$，与平凡的块下界相匹配。平方根尺度被识别为简单质数模数构造不再能自动匹配该界限的阈值。

意义与主张
本文声称提供了自 Truss 结果发表以来，对下界常数的首次改进，精细化了对平方根尺度下击中集大小的理解。在上界方面，本文提出了一个更强的关于素数平方情况的渐近结果，展示了通过涉及 $\sqrt{p/\log p}$ 的项可以缩小下界与上界之间的差距。作者强调，下界的证明是初等的，依赖于下降序列的整除性质，而上界则依赖于带有确定性修复步骤的概率方法。这项工作置于加法组合学（特别是无级数集与击中集的定量估计）的宏大背景之下。