Adjacent comparison bounds and extremal sets for Ruzsa numbers

技术摘要：相邻比较界限与 Ruzsa 数的极值集

问题定义
设 $m$ 为正整数，$\mathbb{Z}_m$ 为模 $m$ 的剩余类环。对于子集 $A \subset \mathbb{Z}_m$，令 $\sigma_A(n)$ 表示满足 $a + a' \equiv n \pmod m$ 的有序对 $(a, a') \in A^2$ 的数量。Ruzsa 数 $R_m$ 定义为最小整数 $r$，使得存在子集 $A \subset \mathbb{Z}_m$ 满足对于所有 $n \in \mathbb{Z}_m$，都有 $1 \le \sigma_A(n) \le r$。这一概念受 Erdős-Turán 关于加性基底猜想的启发。前人的工作已经确定 $R_m$ 被一个绝对常数控制，其上界随时间不断改进，从 $C$ (Ruzsa) 到 $768$ (Tang 和 Chen)，再到 $5120$ (Tang 和 Chen)，最后到 $288$ (Chen)。最近，Ding 和 Zhao (2024) 将上界改进为 $R_m \le 192$，并猜想对于所有 $m$，有 $|R_{m+1} - R_m| \le 1$。

方法论
作者结合了组合比较引理、涉及表示函数的解析不等式以及广泛的计算验证。

1. 比较引理： 本文引入了一个新的比较引理（引理 3.2），建立了 $R_m \le 4R_{m+1}$ 且 $R_{m+1} \le 4R_m$ 的关系。这是通过利用集合平移和并集，从 $\mathbb{Z}_m$ 中的加性基底构造 $\mathbb{Z}_{m+1}$ 中的加性基底（反之亦然），并对新集合的表示计数进行界定来实现的。
2. 解析界限： 为了估计极值集 $A$（即满足 $1 \le \sigma_A(n) \le R_m$ 的集合）的大小，作者利用了 Lev-Sárközy 不等式（引理 2.1）。通过分析 $\sigma_A(n)$ 与常数 $c$ 的均方偏差，他们推导出了关于集合势 $|A|$ 与 $m$ 及 $R_m$ 之间的二次不等式关系。
3. 计算验证： 作者执行了基于证书的搜索，以确定 $m$ 直至 100 时 $R_m$ 的精确值。
   • 对于 $m \le 45$，通过证明不存在表示界限低于所声称的 $R_m$ 的集合来验证其精确性。
   • 对于 $m > 45$，他们依赖于一个下界证明（$R_m \ge 6$），并搜索满足 $\max \sigma_A(n) \le 6$ 的集合。
   • 该搜索利用了一种启发式优化程序，涉及集合平移、元素替换以及旨在最小化表示缺陷的有预算尝试。

主要贡献与结果

• 相邻比较界限 (定理 1.1)： 作者证明了对于任何正整数 $m$，有 $|R_{m+1} - R_m| \le 144$。利用新的比较引理和已知的上界 $R_m \le 192$，这改进了由 $192 - 6$得出的平凡界限$186$。
• 精确值与反例： 本文提供了所有 $2 \le m \le 100$ 的 $R_m$ 精确值的表格。
  • 计算显示 $R_{37} = 4$ 且 $R_{39} = 5$。
  • 特别地，$R_{36} = 6$ 且 $R_{37} = 4$，这为 $m=36$ 时原 Ding-Zhao 猜想（$|R_{m+1} - R_m| \le 1$）提供了反例。
  • 作者提出了一个修正后的猜想：对于所有充分大的 $m$，$|R_{m+1} - R_m| \le 1$ 成立。
  • 他们进一步猜想对于所有 $m \ge 40$，$R_m = 6$ (猜想 2.3)。
• 极值集大小的界限 (定理 1.2)： 对于足够大的 $m$ 以及实现 Ruzsa 数的集合 $A$，作者推导出了 $|A|^2$ 的非平凡界限。令 $s = \lfloor R_m/2 \rfloor$，其大小满足：
  $$\left( s + \frac{1}{2} - \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s - \epsilon} \right)m \le |A|^2 \le \left( s + \frac{1}{2} + \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s + \epsilon} \right)m$$
  作为推论，如果 $R_m = 6$，则 $|A| \le \sqrt{191m}$。
• 结构性质： 本文研究了集合 $A_m$（实现 $R_m$ 的子集）的性质。
  • 奇偶性： 命题 5.5 提供了当 $m$ 为偶数时，$A$ 中偶元素的比例的界限。如果 $R_m = 6$，则偶元素比例在 $1/2$ 的 $\approx 0.14$ 范围内。
  • 算术级数： 本文定义 $L_m$ 为任何属于 $A \in A_m$ 的集合中所包含的算术级数的最大长度。注意到 $L_m \le R_m$。
  • $A_m$ 的基数： 命题 5.6 建立了 $|A_m|$ 的渐近界限，显示 $\frac{1}{2}\log m - C \le \log |A_m| \le \sqrt{191m} \log(\dots)$。

意义
本文完善了对 Ruzsa 数行为的理解，特别是解决了 $R_m$ 在相邻模数变化下的稳定性问题。通过在较小的 $m$ 处证伪了严格的 $|R_{m+1} - R_m| \le 1$ 猜想，同时为该猜想在渐近意义上的有效性提供了强有力的证据，作者阐明了代数结构（模性质）与组合随机性之间的相互作用。提供直至 $m=100$ 的精确值显著扩展了之前的表格，而推导出的极值集大小界限为未来研究循环群中的加性基底提供了新的约束。这项工作还针对表示值的分布、极值集的结构以及此类集合数量的增长提出了若干开放性问题。