Solution of Erd\H{o}s problem $\# 443$

技術的要約：Erdős問題 #443 の解法

問題提起
本論文は、ErdősとGrahamによる1980年の著作 [1] における問題 #443 を扱うものである。この問題は、二次形式 $k(m-k)$ および $\ell(n-\ell)$ によって生成される2つの整数の集合に関するものである。ここで、$1 \le k \le m/2$ および $1 \le \ell \le n/2$ とする。具体的には、$S(m) = \{k(m-k) : 1 \le k \le m/2\}$ および $S(n) = \{\ell(n-\ell) : 1 \le \ell \le n/2\}$ とする。中心となる問いは以下の通りである：

1. 共通の整数の数、すなわち $f(n, m) = \#(S(m) \cap S(n))$ を推定できるか？
2. $m$ と $n$ が変化するとき、この数は非有界（unbounded）か？
3. $mn$が十分に大きいとき、この数は任意の$\epsilon > 0$に対して$(mn)^\epsilon$ 未満となるか？

手法および導出
著者であるStijn Cambieは、$f(n, m)$ という表記を採用し、断りなく $m > n$ と仮定する。手法の核心は、共通部分の条件を平方の差へと変換することにある。

$k(2m-k) = m^2 - (m-k)^2$ であることに着目し、$c = m-k$ と置く。整数が両方の集合に含まれるための条件 $k(2m-k) = \ell(2n-\ell)$ は、次のように書き換えられる：
$$m^2 - c^2 = n^2 - d^2$$
ここで $d = n-\ell$ である。項を整理すると、以下が得られる：
$$m^2 - n^2 = c^2 - d^2 = (c-d)(c+d)$$
この変換は、解の数が整数 $m^2 - n^2$ の約数の個数の半分、すなわち $\tau(m^2 - n^2)$ によって抑えられることを示している。$c-d$ が $\sqrt{m^2 - n^2}$ 以下である約数であるという制約を利用して、この上界を確立している。

主要な結果

1. 上界： 本論文は、$f(n, m) \le \lfloor \tau(m^2 - n^2) / 2 \rfloor$ であることを立証している。約数関数 $\tau(x)$ に関する周知の性質、すなわち $\tau(x) \le 2^{(1+o(1))\frac{\log x}{\log \log x}} = x^{o(1)}$ を用いることで、著者は $f(n, m) = (mn)^{o(1)}$ であることを確認している。これにより、共通の整数の数は $mn$が十分に大きいとき、任意の$\epsilon > 0$に対して$(mn)^\epsilon$ 未満であるという予想が裏付けられた。
2. 非有界性： 共通の整数の数が非有界であるかという問いに対し、著者は $m = n+1$ という特定のケースを検討する。このシナリオでは、$m^2 - n^2 = 2n+1$ となる。解の数は $\lfloor \tau(2n+1)/2 \rfloor - 1$ に関連することが示される。$\tau(x)$ は（高度合成数において大きな値を取るため）非有界であることから、$f(2n+2, 2n)$ は非有界である。この構成は、$2n+1 = pq$（ただし$p \ge q \ge 2$）という因数分解を、有効な整数の解$c$および$d$ へと明示的に写像するものである。

意義および主張
本論文は、Erdős問題 #443 に対する完全な解を提供し、共通部分のサイズの劣多項式的な成長率と、その非有界性の両方を確認したと主張している。

著者は、解の歴史に関する特定の注記を含めている。Norbert Hegyvári [2] が、本ノートの出版の40年前に独立してこの問題を解決していた。しかし、Hegyváriの証明は最近出版されたものであり、本ノートの投稿後であった。本論文は、先行する遅延された研究（Hegyváriの研究）を認めつつ、独立した検証および解法として位置づけられている。

引用文献

• [1] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980.
• [2] N. Hegyvári, (最近出版された問題の解法).
• [3] 約数関数 $\tau(x)$ に関する標準的な結果.