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

技术摘要：Erdős 问题 #443 的解

问题陈述
本文探讨了由 Erdős 和 Graham 在其 1980 年的著作 [1] 中提出的问题 #443。该问题涉及由二次型 $k(m-k)$ 和 $\ell(n-\ell)$ 生成的两组整数，其中 $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$ 变化时，该数量是否无界？
3. 当 $mn$足够大时，该公共元素数量是否严格小于$(mn)^\epsilon$（对于每一个$\epsilon > 0$）？

方法论与推导
作者 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$足够大时，公共整数的数量小于$(mn)^\epsilon$（对于任何$\epsilon > 0$）。
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 和 R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980.
• [2] N. Hegyvári, (问题的解，近期发表).
• [3] 关于约数函数 $\tau(x)$ 的标准结论。