Largest Sidon subsets in weak Sidon sets

本文改进了关于$(4,5)$-集（弱 Sidon 集）中最大 Sidon 子集比例常数$c_*$的界限，将其下界从$\frac{1}{2} + \frac{1}{141 \cdot 76}$提升至$\frac{9}{17}$，上界从$\frac{3}{5}$降低至$\frac{4}{7}$。

要点

这篇论文就像是在解决两个关于“数字聚会”的谜题。想象一下，你有一群数字朋友聚在一起，他们之间有一些特殊的规则。数学家们想知道，在这些遵守特定规则的数字群体中，我们最多能挑出多少个“最守规矩”的朋友？

让我们把这篇论文拆解成两个有趣的故事：

故事一：弱 Sidon 集合（“不重复的和”派对）

背景知识：
想象有一群数字 $A$。如果这群人里，任意两个不同的数字加起来，得到的和都是独一无二的（没有两个不同的组合算出同一个和），那这群人就叫Sidon 集合（也就是“完美守规矩”的群体）。

但是，有时候这群人只遵守一个稍微宽松一点的规则：只要两个不同的数字加起来，和是唯一的就行（允许一个数字自己加自己，比如 $2+2=4$，只要没有其他两个不同的数加起来也是 4 就行）。这种稍微宽松一点的群体，论文里叫弱 Sidon 集合。

问题：
Sárközy 和 Sós 这两位数学家问了一个问题：如果我们有一个“弱 Sidon 集合”（稍微有点乱，但大体守规矩），里面一定藏着一个“完美守规矩”的 Sidon 子集。这个子集最大能有多大？

比如，如果弱 Sidon 集合有 100 个人，我们能不能保证里面至少有 50 个人是完美守规矩的？还是说可能只有 10 个？

论文的答案：
作者 Jie Ma 和 Quanyu Tang 给出了一个完美的答案：
不管这个弱 Sidon 集合有多大，我们总能从中挑出一半多一点点的人，让他们组成一个完美的 Sidon 集合。

• 具体公式： 如果集合有 $n$ 个人，我们至少能挑出 $\lceil \frac{n+1}{2} \rceil$ 个人（也就是 $(n+1)/2$ 向上取整）。
• 比喻： 想象你有一堆乱糟糟的积木（弱 Sidon 集合）。虽然它们堆得有点歪，但作者证明了，你总能从中拆出一半多一点的积木，把它们重新搭成一个完美的、严丝合缝的塔（Sidon 集合）。
• 结论： 这个比例极限是 1/2。也就是说，在极限情况下，弱 Sidon 集合里大约有一半的人是“完美守规矩”的。

---

故事二：(4, 5)-集合（“距离不重复”的侦探游戏）

背景知识：
第二个故事稍微复杂一点，涉及“距离”。
想象有 4 个数字站成一排。它们两两之间会有 6 个距离（比如 A 到 B，A 到 C...）。
如果一个集合里的任意 4 个数字，它们产生的 6 个距离里，至少有 5 个 是互不相同的（也就是说，最多只能有一对距离是重复的），那这个集合就叫 (4, 5)-集合。

这比“弱 Sidon 集合”要求更严格，但比“完美 Sidon 集合”稍微宽松一点点。

问题：
Erdős（著名的数学家）问：如果我们有一个 (4, 5)-集合，里面一定藏着一个“完美守规矩”的 Sidon 子集。这个子集的大小至少占整体的多少？
比如，如果有 100 个这样的数字，能不能保证至少有 30 个是完美守规矩的？还是 40 个？

以前的进展：
以前的数学家（Gyárfás 和 Lehel）猜这个比例大概在 0.5 到 0.6 之间。他们用了类似“超图”（一种复杂的数学网络结构）的方法来分析。

论文的答案：
作者改进了这个范围，把答案锁得更紧了：
这个比例 $c^*$ 一定在 $9/17$到$4/7$ 之间。

• 比喻：

  • 上限（4/7）： 作者像侦探一样，通过计算机搜索，构造出了一个具体的、只有 14 个人的“坏例子”。在这个例子里，无论你怎么挑，都只能挑出 8 个完美守规矩的人。$8/14$约等于$4/7$。这证明了比例不可能超过$4/7$。
  • 下限（9/17）： 作者改进了之前的数学工具（把之前的“超图”分析工具升级了），证明了无论这个集合怎么变，你至少能挑出 $9/17$（约 53%）的人组成完美团队。

• 结论： 以前大家觉得这个比例可能在 50% 到 60% 之间晃荡，现在作者把它缩小到了 53% 到 57% 之间。虽然还没完全定死（比如是不是正好 55%），但已经非常接近真相了。

---

总结：这篇论文做了什么？

1. 彻底解决了第一个谜题： 证明了在“弱 Sidon 集合”里，完美子集的大小精确地是总数的一半多一点（$\lceil \frac{n+1}{2} \rceil$）。这是一个完美的数学解答。
2. 大幅推进了第二个谜题： 对于更复杂的"(4, 5)-集合”，他们把之前模糊的范围大大缩小了，证明了完美子集的比例至少是 $9/17$，至多是$4/7$。

核心思想：
这篇论文展示了数学中一种美妙的对称性：即使在一个看起来有点“乱”的集合里（只要它不是完全乱），也总是隐藏着大量的“秩序”（Sidon 子集）。作者通过巧妙的构造（造出反例）和严密的逻辑推导（证明下限），把这种“混乱中的秩序”量化得非常精确。

一句话总结：
作者证明了，在任何稍微有点乱的数字集合里，你总能找到至少一半（甚至更多）的数字，它们之间有着完美的数学秩序。

技术摘要

1. 研究背景与问题定义

论文主要研究两类“接近”Sidon 性质的有限实数集，并探讨其中包含的最大 Sidon 子集的大小。

• Sidon 集 (Sidon set)：集合 $S \subset \mathbb{R}$ 中所有满足 $x \le y$ 的和 $x+y$ 均互不相同。
• 弱 Sidon 集 (Weak Sidon set)：集合 $A \subset \mathbb{R}$ 中所有满足 $x < y$ 的和 $x+y$ 均互不相同（允许 $x+x$ 与其他和冲突，但不同元素对的和必须唯一）。
• (4, 5)-集 ((4, 5)-set)：集合 $A \subset \mathbb{R}$ 中任意 4 个不同元素构成的 6 个两两绝对差值中，至少有 5 个不同的值。

核心问题：

1. Sárközy 和 Sós 问题：对于大小为 $n$ 的弱 Sidon 集 $A$，令 $h(A)$ 为其最大 Sidon 子集的大小。定义 $g(n) = \min \{h(A) : |A|=n, A \text{ 是弱 Sidon 集}\}$。Sárközy 和 Sós 询问极限 $\lim_{n \to \infty} g(n)/n$ 是否存在及其值。
2. Erdős 问题：对于大小为 $n$ 的 (4, 5)-集 $A$，令 $f(n) = \min \{h(A) : |A|=n, A \text{ 是 (4, 5)-集}\}$。Erdős 询问是否存在最优常数 $c^*$ 使得 $f(n) \ge c^* n$，并确定该常数。

---

2. 主要贡献与结果

2.1 弱 Sidon 集中的最大 Sidon 子集

• 定理 1.2 & 1.3：作者完全解决了 Sárközy 和 Sós 的问题。
  • 证明了极限 $\gamma^* = \lim_{n \to \infty} g(n)/n$ 存在且等于 1/2。
  • 给出了精确公式：对于所有 $n \ge 1$，$g(n) = \lceil \frac{n+1}{2} \rceil$。
  • 这意味着在任何大小为 $n$ 的弱 Sidon 集中，必然存在一个大小至少为 $\lceil \frac{n+1}{2} \rceil$ 的 Sidon 子集，且该下界是紧的。

2.2 (4, 5)-集中的最大 Sidon 子集

• 定理 1.5：证明了极限 $\lim_{n \to \infty} f(n)/n$ 存在，且等于最优常数 $c^* = \inf_{n \ge 1} \frac{f(n)}{n}$。
• 定理 1.6：改进了 Gyárfás 和 Lehel 之前给出的界限 ($1/2 + \epsilon \le c^* \le 3/5$)，确立了新的界限：
  • $9/17 \le c^ \le 4/7$*。
  • 下界 $9/17 \approx 0.529$，上界$4/7 \approx 0.571$。

---

3. 方法论与证明策略

3.1 渐近常数的存在性 (Subadditivity Argument)

为了证明极限的存在性，作者使用了 Fekete 引理。

• 策略：证明序列 $g(n)$ 和 $f(n)$ 是次可加的（subadditive），即 $g(m+n) \le g(m) + g(n)$ 和 $f(m+n) \le f(m) + f(n)$。
• 构造：通过仿射变换（缩放和平移）将两个不相交的弱 Sidon 集（或 (4, 5)-集）拼接成一个新的集合。通过精心选择缩放因子 $q$ 和偏移量 $t$，确保新集合中“混合”产生的和（或差）不会与原有集合内部产生的和（或差）发生冲突，从而保持弱 Sidon 或 (4, 5) 性质，同时控制最大 Sidon 子集的大小不超过两部分之和。

2.2 弱 Sidon 集的精确解 ($g(n)$)

• 下界证明 ($g(n) \ge \lceil \frac{n+1}{2} \rceil$)：
  • 利用 A.P.-超图 (A.P.-hypergraph) 框架。对于集合 $A$，定义超图 $H(A)$，其边为 $A$ 中的 3 项等差数列。
  • 引理表明：在弱 Sidon 集中，Sidon 子集等价于超图 $H(A)$ 的独立集（即不含 3 项等差数列的子集）。
  • 利用 Lemma 2.4 证明对于弱 Sidon 集，超图边数 $m_H \le n_H - 2$。
  • 结合 Chvátal 和 McDiarmid (以及 Tuza) 关于 3-一致超图覆盖数 $\tau(H)$ 的不等式 $4\tau(H) \le n_H + m_H$，推导出独立数$\alpha(H) \ge \frac{n+1}{2}$。
• 上界证明 ($g(n) \le \lceil \frac{n+1}{2} \rceil$)：
  • 构造了一族具体的弱 Sidon 集 $A_{2n+1}$，其元素基于 $2^{n-i}3^i$ 的形式构造。
  • 通过分析 3-adic 估值 ($v_3$) 的性质，证明这些集合确实是弱 Sidon 集。
  • 分析其 A.P.-超图结构，证明其最大独立集大小恰好为 $n+1$（对于 $2n+1$ 个元素），从而证明了上界的紧性。

2.3 (4, 5)-集的界限改进 ($c^*$)

• 上界改进 ($c^* \le 4/7$)：
  • 通过计算机辅助搜索，构造了一个具体的 14 点 (4, 5)-集 $A_{base}$。
  • 验证该集合满足 (4, 5) 性质，且其最大 Sidon 子集大小为 8。
  • 计算比率 $8/14 = 4/7$，结合$c^* = \inf f(n)/n$，直接得出上界。
• 下界改进 ($c^* \ge 9/17$)：
  • 利用 Gyárfás 和 Lehel 的框架，指出 (4, 5)-集对应的 A.P.-超图是 线性的 (linear) 且 不含 $F_7$ 子超图（$F_7$ 是特定的 7 顶点 3-一致超图）。
  • 引用 Henning 和 Yeo 关于线性且 $F_7$-free 的 3-一致超图的覆盖数界限：$17\tau(H) \le 5n_H + 3m_H$。
  • 结合 $m_H \le n_H - 2$ 的性质，推导出 $\tau(H) \le \frac{8}{17}n_H$，进而得到独立数 $\alpha(H) \ge \frac{9}{17}n_H$。

---

4. 关键数学工具与概念

1. A.P.-超图 (A.P.-hypergraph)：将集合中的 3 项等差数列建模为超图的边。Sidon 子集对应于超图的独立集。
2. 次可加性 (Subadditivity)：用于证明渐近极限的存在性。
3. Fekete 引理：处理次可加序列极限的标准工具。
4. 超图覆盖与独立数：利用 $\alpha(H) + \tau(H) = n$ 的关系，将寻找最大 Sidon 子集问题转化为寻找最小覆盖数问题。
5. 3-adic 估值：在构造具体的弱 Sidon 集时，利用 $v_3(x)$ 的性质来区分和的唯一性。
6. 计算机辅助构造：在 (4, 5)-集的上界证明中，使用了 AI 辅助和穷举搜索来寻找极值构造。

---

5. 研究意义

• 解决开放问题：完全解决了 Sárközy 和 Sós 提出的关于弱 Sidon 集渐近密度的问题，给出了精确的 $g(n)$ 公式。
• 推进 Erdős 问题：显著改进了 Erdős 关于 (4, 5)-集问题的常数界限，将上下界从较宽的区间压缩到了 $[0.529, 0.571]$ 之间。
• 方法论创新：展示了如何将组合数论中的集合性质问题转化为超图极值问题，并结合现代超图理论（如 Henning-Yeo 界限）和计算机搜索来解决经典问题。
• 结构洞察：揭示了弱 Sidon 集与 (4, 5)-集在结构上的细微差别（前者允许某些和重复，后者限制差值多样性），并证明了它们在 Sidon 子集密度上的不同表现。

综上所述，该论文通过严谨的理论推导和巧妙的构造，在加性组合数学的极值问题领域取得了重要突破。