Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

技术摘要：具有算术级数交集的整数族的精确值与精确上界

问题陈述
本文研究了 Erdős 问题 #272，该问题旨在确定函数 $t(N)$，其中 $t(N)$ 定义为满足以下条件的互不相同的子集 $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ 的最大数量：任意两个不同集合的交集 $A_i \cap A_j$ 是一个非空算术级数（AP）。

从历史上看，Simonovits 和 Sós 确定了 $t(N) = O(N^2)$，并推测最大值由所有包含一个固定元素的规模至多为 3 的子集族实现，其界限为 $\binom{N}{2} + 1$。随后，Szabó 通过构造一个实现 $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ 的集合族，推翻了这一精确性猜想。Szabó 进一步确立了渐近行为 $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$，并提出了两个关键问题：(i) 是否 $t(N) = \binom{N}{2} + O(N)$，以及 (ii) “核问题”（kernel question），即询问每一个极大集合族（达到最大规模的集合族）是否必须包含一个所有集合都共有的公共元素。

研究方法
作者采用了一种结合了穷举计算验证、结构组合学和解析定界技术的混合方法：

1. 精确计算： 对于较小的 $N$ ($N \le 12$)，将该问题建模为寻找图中的最大团问题，其中顶点是 $[N]$ 的非空子集，边连接具有非空 AP 交集的集合。
   • 对于 $N \le 10$，使用了一种带有贪心着色界的位并行分支定界求解器（bit-parallel branch-and-bound solver）。
   • 对于 $N=11$ 和 $12$，使用了一种利用根分解（root decomposition）、退化序（degeneracy ordering）、核心剥离（core peeling）以及严谨的“星形剪枝”（star pruning）步骤的决策搜索，以证明不存在更大的集合族。
2. 结构分解： 用于一般上界的证明依赖于将一个“星形”集合族（即有一个公共元素 $m$ 的集合族）分解为规模 $\le 2$、规模 $3$以及规模$\ge 4$ 的子集。
3. 缺陷一计数不等式（Defect-One Counting Inequality）： 一个核心技术工具是针对“阶梯区域”（包含 0 的整数区间集合）的计数不等式。作者证明了对于任何此类集合族，其成员数量被其覆盖的“坏对”（bad pairs，即 $\{u,v\}$ 使得 $\{0,u,v\}$ 不是 AP 的对）的数量加上一个小的缺陷项所限制。该结论通过对参数高达 500 的精确动态规划进行验证，并利用较大参数下的正定二次型进行渐近论证得到证实。
4. 私有对定理（Private-Pair Theorem）： 建立了一个结构化定理，表明在良交集集合族中，每个“弯曲”成员（即规模 $\ge 4$ 且不是 AP 的集合）都包含一个“私有坏对”——即一个不被该集合族中其他任何成员包含的元素对。这防止了非 AP 成员之间共享“杀手”（bad pairs），从而实现了紧凑的计数界限。

主要贡献与结果

• 小 $N$ 的精确值： 本文确定了 $N = 3, \dots, 12$ 时 $t(N)$ 的精确值。这些值为 $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$。在整个范围内，Szabó 的下界都是精确的。该序列目前尚未收录于 OEIS。
• 精炼猜想： 基于计算证据，作者猜想对于所有 $N \ge 1$：
  $$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$$
  这通过一个精确公式精炼了 Szabó 的渐近问题。
• 星形集合族的精确上界： 主要理论结果（定理 1.4）证明了对于任何星形集合族（即所有集合都共享一个公共元素的集合族），其规模都受限于 Szabó 的下界。这是此类问题中第一个已知的针对任何 $N \ge 5$ 的精确上界。
  • 该证明结合了“缺陷一”计数不等式与“私有对定理”来处理非 AP 成员。
• 向“核问题”的归约： 作者证明，如果 Szabó 的核猜想成立（即每一个极大集合族都是星形的），那么精炼后的猜想（即该公式对所有 $N$ 均成立）将直接成立。因此，确定 $t(N)$ 精确值的任务被归约为证明极大集合族必须具有一个公共元素。
• 反例的结构约束： 本文分析了非星形极大集合族（即核猜想的反例）的假设结构。作者证明，如果此类集合族存在，其三元组必须共享一个公共元素，且避开该元素的任何成员必须是公差较小的长算术级数。作者认为此类配置是“自我限制”的，不太可能达到猜想的界限，尽管完整的证明仍是一个开放问题。

意义
本文声称提供了第一个针对 $N \ge 5$ 的 $t(N)$ 的精确判定（具体为 $N \le 12$），并为受限的星形集合族类建立了第一个精确上界。通过证明对于所有星形集合族，下界都是精确的，这项工作将“核属性”孤立为解决 Erdős 问题 #272 的唯一剩余障碍。作者指出，其结果证实了 Szabó 的构造在共享公共元素的集合族类中是最优的，并提供了关于潜在非星形反例结构的第一个严谨结构约束。这项工作还引入了新的组合技术，特别是缺陷一计数不等式和私有对定理，这些技术可能适用于其他的交集问题。