Erdős-Sidon 攻擊報告

Sidon set / $B_2$ set。$S \subseteq \mathbb{Z}$ 是 Sidon set，若對所有 $a, b, c, d \in S$，等式 $a + b = c + d$ 蘊涵 $\{a,b\} = \{c,d\}$。等價地，差集 multiset $r_{S-S}(d) := |\{(x,y) \in S \times S : x - y = d\}|$ 對 $d \ne 0$ 全部為 1。

研究函數：$F_2(N) := \max\{ |S| : S \subseteq [1, N], S \text{ Sidon}\}$。

Erdős–Turán 1941 上界：$F_2(N) \le \sqrt{N} + \sqrt[4]{N} + 1$.

Lindström 1969 改進常數：$F_2(N) \le \sqrt{N} + \sqrt[4]{N} + 1$（同樣 main term，常數略改）.

Singer 1938 / Bose–Chowla 1962 下界：$F_2(N) \ge \sqrt{N} - O(N^{1/2 - c})$ 對某 $c > 0$.

Erdős–Turán 猜想：$F_2(N) = \sqrt{N} + O(N^\varepsilon)$ 對所有 $\varepsilon > 0$.

若 $|S| = k$，則 $S$ 內共有 $\binom{k}{2} = \frac{k(k-1)}{2}$ 組 ordered pair 之差，且因 Sidon 性，這些差兩兩不同（pairs 反過來算也是兩兩不同）。所有差落在 $[1, N-1]$ 之間，可能值至多 $N - 1$ 個。鴿籠：$\frac{k(k-1)}{2} \le N - 1$，所以 $k \lesssim \sqrt{2N}$。

Erdős–Turán 1941 把這個簡單界用 Fourier 方法精細化，把上界從 $\sqrt{2N}$ 進化到 $\sqrt{N} + N^{1/4}$。Lindström 1969 進一步把常數壓到 1。85 年後沒有人能把 $N^{1/4}$ 換成更小的指數。

所有 16 個 framework（Fourier / Weil / algebraic geometry / Hilbert scheme / Behrend / regularity lemma / 概率方法 / 同態類比 / 高範疇 / holographic / tropical / Berkovich / ...）在 round 16 之前都遞迴到同一個 Sidon $L^4$ identity：

$$\sum_{\xi \in \widehat{\mathbb{Z}/N}} |\widehat{\mathbf{1}_S}(\xi)|^4 = N \cdot (2|S|^2 - |S|).$$

從這個 identity 出發的最強論證恰好就是 Lindström $\sqrt{N} + N^{1/4}$。要打破它你需要 $L^6$ moment control，但 Sidon 公理（pairwise differences distinct）不強制這個 control。我們 94 輪所有 attack 在某層都被這個 $L^6$ 障礙頂住。

有些條件性的「sub-Lindström」結果在 94 輪內被建構（W51 等）：例如假設 Generalized Lindelöf Hypothesis + 一個 Sidon–Kloosterman bridge，可得 $F_2(N) \le \sqrt{N} + O(N^{1/8 + \varepsilon})$。但這些都不算無條件——所以本報告嚴格地說「0 unconditional improvements」。

我們把 94 輪中反覆撞到的結構障礙抽象成 12 個 vertex，包括：(1) Sidon $L^4$ identity 障礙；(2) Lindström-Cilleruelo = Weil bound 等價（W48 Theorem 26.1）；(3) AG additive-vs-multiplicative mismatch；(4) holographic area-law；(5) Hilbert scheme 不適用；(6) ZFC independence 幾乎排除（Sidon 在 $\mathrm{ACA}_0$）；(7-12) 詳見 Paper G §4。

Vertex #12（order-sensitive distal-NIP）是 W342 在 R93 加入的——這也是 W348 反例最後落在的位置：order-sensitive 確實是 $r_{S-S}$ 之外的 escape，但這個 escape 無法 match Lindström。

R20 之後就已經 declared 過「research space exhausted」一次，但用戶的 plan B（負面結果可被當主結果）多次重開。R85–R94 的目標已轉為「documenting LLM-driven attack 的方法論特徵」而非「期待真的破 Lindström」——這也是 Paper G 的核心轉折。

Theorem 1.1（顯式 cube count）。令 $S \subseteq \mathbb{Z}$ 為 Sidon 集，$|S| = n$。對任意整數 $k \ge 3$，

$$T_k(S) := \#\{(x_0, v_1, \dots, v_k) \in S \times \mathbb{Z}^k : x_0 + \textstyle\sum_{i \in I} v_i \in S \text{ for all } I \subseteq [k]\} = n + k \cdot n(n-1).$$

證明用 parallelogram exclusion：除了 $v_i \in \{0, s_j - x_0 : s_j \in S\}$ 的情況外，所有 $v_i$ 都被 Sidon 公理排除。

Theorem 1.2.令 $A = \{0,1,5,7,15,18\}$, $B = \{0,1,3,8,14,18\}$（Bloom 1977 / Bloom–Golomb 1977 的 $(R(3,-2), \mathrm{refl}_{18} S(3,-2))$ 對）。在 $\mathbb{Z}/41$（和 $\mathbb{Z}/43$）上，

$$\|\mathbf{1}_A\|_{U^3(\mathbb{Z}/N)} \neq \|\mathbf{1}_B\|_{U^3(\mathbb{Z}/N)},$$

儘管它們的 $r_{S-S}$ multiset 完全相同。差異來自 cyclic-only doubling-relation count $M_5^{(N)}$（Lemma 4.1）；整數版本所有相關 count 都退化為 $r_{S-S}$ 的函數（Lemma 5.2，見 §4.M 也使用）。

$M_5^{(\infty)}(A) = M_5^{(\infty)}(B) = 158$，但 $M_5^{(41)}(A) \neq M_5^{(41)}(B)$——wraparound 才是兩者分歧的根源。

F1'' meta-overcategorization：當一個 LLM agent 在自評階段，把自己的工作歸入一個歷史 lineage（如「barrier theorems」、「impossibility framework」），但實際的歷史定理在 (a) 模型類別不對，(b) 證明工具不重疊，或 (c) 該 lineage 從未把這類問題收入。

F1''' frame-replication trap：當一個 LLM swarm 內 $k \ge 3$ 個 sub-agent 獨立回報「我用 framework $F$ 得到結論 $C$」，但其實 $F$ 隱含一個共享的偽引理 $L$，且沒有任何 sub-agent 在自己的回報裡實際核對 $L$。表面上 $k$ 重獨立證據，本質上只是一個錯誤被複製 $k$ 次。

Paper G 另一個 contribution 是 audit-to-quiescence failure 的 conjecture：在開放猜想 (open conjecture) 的 LLM-driven 攻擊上，audit cycle 不會收斂到 quiescent state。本研究中 24 個 audit cycle 後 still 在抓到新的 F1''/F1''' 案例（R94 triple-audit W347/W348/W349 仍 reopen 一個 vertex），驗證了 conjecture 的方向，但 $n=1$ 不能 confirm 一般性。

2025 年底 Tao 與 AlphaEvolve 的「AI 解了 100+ Erdős problems」narrative 認為 LLM-assisted attack 對開放問題逐步收斂。Paper G 提出對立立場：

• 不同 Sidon 子問題：AlphaEvolve 報告的成功多半是 (a) 有 explicit verifier 的構造性下界問題，(b) 已知 framework 的小量改進。Erdős–Sidon upper bound 兩者都不滿足——沒有 verifier，沒有 framework 可以小量改進。
• Verifier 不對稱：Sidon 下界有 verifier（檢查一個明確的集合）；上界沒有。LLM swarm 在無 verifier 的情境下高度依賴自我評估，這正是 F1''/F1''' 出現的溫床。

Theorem 4.7.令 $S \subseteq [1, N]$ 為 Sidon 集，$|S| = k$，gap sequence $g_1 < g_2 < \dots < g_{k-1}$（gap distinctness 是 Sidon 蘊涵）。若只用 (C1) $g_i$ 兩兩不同、(C2) $\sum g_i = s_k - s_1 \le N$、(C3) $M_2 = \sum g_i^2 \le N^2$ 與 Cauchy–Schwarz，最強上界是 $k = O(N^{2/3})$。

證明用 Mian–Chowla + outlier 構造，達到 $k = (1-o(1)) N^{2/3}$，因此上界 sharp。

結論：gap-sequence polynomial invariant 自成一族時，無法 match Erdős–Turán 的 $\sqrt{2N}$。Paper M 提出 Conjecture 7.1（W353-A）猜想：任何 gap-sequence 的 polynomial invariant 都不能 match Lindström。

下表為 Bose–Chowla 構造在 $\mathbb{F}_p$（$p = 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$）上的 $M_2 / N^{3/2}$ 比值（$N = p^2 - p$，$k = p$）。注意比值沒有收斂到單一常數，而是 fluctuating 在 $[0.74, 1.78]$ 之間——這是 order-sensitive escape 不是「飽和」的訊號。

$p$	$k = |S|$	$N$	$M_2$	$M_2 / N^{3/2}$
3	3	6	14	0.953
5	5	20	120	1.342
7	7	42	438	1.610
11	11	110	1832	1.589
13	13	156	2890	1.483
17	17	272	6624	1.476
19	19	342	9078	1.435
23	23	506	17170	1.508
29	29	812	35640	1.541
31	31	930	43578	1.534

數值由 paper-m/verify_numerics.py 重現（exact rational arithmetic）。

363 sub-agent 的完整 transcript 計畫以 CC-BY-4.0 釋出，放在 github.com/weiqi-kids/optimal-golomb-ruler 的 exploration/ 與 decisions.md。Paper G 的 §5 reproducibility section 引用這份 transcript。