Solution of Erdős problem $\# 443$

In [1], p.88, Erdős and Graham posed the following problem;

Let $m$ and $n$ be positive integers and consider the two sets

Can one estimate the number of integers common to both? Is this number unbounded? It should certainly be less than $(mn)^{\varepsilon}$ for every $\varepsilon> 0$ if $mn$ is sufficiently large.

The problem is listed in the online database of Erdős problems as problem #443 (as of the time of publication), https://www.erdosproblems.com/443.

We will use the notation $S(m) = \left\{ k(m-k): 1 \le k \le\frac{m}{2} \right\}$ for such sets, and let $f(n,m) = \#(S(m) \cap S(n))$.

Observe that $f(n,m) \le f(2n,2m)$ by doubling each of $n,m,k,\ell$ in an equality $k(m-k) = \ell(n-\ell)$. Without loss of generality, we will assume $m > n$.

Writing $k(2m-k) = m^2 - (m-k)^2 = m^2-c^2$, for $c=m-k$, we deduce that the number of solutions is bounded by half of the number of divisors of $m^2-n^2$, since $m^2-c^2 = n^2-d^2 \Leftrightarrow m^2-n^2 = c^2-d^2 = (c-d)(c+d)$ and $c-d$ is thus a divisor bounded by $\sqrt{m^2-n^2}$.

A well-known result [3] states that the number of divisors of $x$, $\tau(x)$, is bounded by $2^{(1+o(1))\frac{\log x}{\log\log x}} = x^{o(1)}$ and this is sharp (for highly composite numbers), up to the $o(1)$ term which is a function tending to zero (as $x \to\infty$). Since $m^2-n^2 < (mn)^2$, we obtain that $f(m,n) \le f(2m,2n) \le\left\lfloor\frac{\tau(m^2-n^2)}{2} \right\rfloor= (mn)^{o(1)}$, as expected.

When $m=n+1$, $f(2m,2n) = \left\lfloor\frac{\tau(2n+1)}{2} \right\rfloor- 1$ is unbounded, concluding the other question. For this we note that for every factorization $2n+1=pq$ with $p \ge q \ge2$ (both odd), $c=\frac{p+q}{2}$ and $d=\frac{p-q}{2}$ are integers for which $c<m$ and $0 \le d<n$.

Remark.

Norbert Hegyvári [2] solved the problem independently, 40 years earlier. His proof appeared recently, after submission of this note.