未解決問題、算術と数論, 組合せ論と離散数学、1941年に提起

加法的基底に関するエルデシュ・トゥーラン予想

未解決エルデシュ

$A \subseteq \mathbb{N}$ を位数が $2$ の漸近的加法的基底、すなわち十分大きいすべての整数 $n \ge n_0$ が $a, b \in A$ を用いて $n = a + b$ と表される集合とする。このとき表現関数 $r_A(n) = \#\{(a, b) \in A^2 : a + b = n\}$ は上に有界ではあり得ず、 $\limsup_{n \to \infty} r_A(n) = \infty$ が成り立つ。

提起者, 1941ポール・エルデシュ

研究の最前線 2026年時点

2026年現在、加法的基底に関するエルデシュ・トゥーラン予想は位数 $2$ の場合でさえ未解決である。すべての $n \ge n_0$ に対して $r_A(n) \ge 1$ を仮定すると（順序対で） $\limsup_{n \to \infty} r_A(n) \ge 8$ や表現関数が最終的に定数にならないことは従うが、 $\limsup_{n \to \infty} r_A(n) \le 10$ を排除することすら未解決である。研究は2次モーメント $N^{-1} \sum_{n \le N} r_A(n)^2$ の評価や $B_2[g]$ 集合の増大度の解析に集中している。

既知の最良の結果

位数 $2$ のすべての漸近的加法的基底は、順序対の表現に関して $\limsup_{n \to \infty} r_A(n) \ge 8$ を満たす（グレコス、ハダッド、エルー、ピフコ、2003年）。
十分大きいすべての $n$ に対して対数的増大 $c_1 \log n \le r_A(n) \le c_2 \log n$ をもつ位数 $2$ の漸近的基底が存在する（エルデシュ、1956年）。

使われた手法と限界

手法	達成したこと	限界
母関数と円周法・パーセヴァル評価	単位円周上の母関数 $f(z) = \sum_{a \in A} z^a$ を $r_A(n)$ の平均と結びつけ、最終的に定数となる表現関数を排除した。	$L^2$ フーリエ平均だけでは振動の相殺を排除できず、 $f(z)^2$ の係数の $L^\infty$ ノルムの発散を直接強制することができない。
ランダムな薄い基底に対する確率的手法	各整数 $x$ を確率 $c \sqrt{\log x / x}$ で独立に選ぶことで、 $r_A(n) = \Theta(\log n)$ を満たす基底を構成した。	独立なランダム選択では被覆されない隙間をなくすためにボレル・カンテリの補題から $\sqrt{\log x}$ の因子が不可欠となり、ランダム構成では $r_A(n) = O(1)$ を実現できない。

未解決の問い

位数 $2$ のすべての漸近的加法的基底に対して $\limsup_{n \to \infty} r_A(n) = \infty$ が成り立つか。
位数 $2$ の漸近的加法的基底が $n \to \infty$ のとき $r_A(n) = o(\log n)$ を満たすことは可能か。

参考文献

Paul Erdős, Pál Turán (1941). On a problem of Sidon in additive number theory, and on some related problems · DOI:10.1112/jlms/s1-16.4.212
Georges Grekos, Labib Haddad, Charles Helou, Jukka Pihko (2003). On the Erdős–Turán conjecture · DOI:10.1016/S0022-314X(03)00099-4