International Mathematics Competition
for University Students
2025

IMC2025: Day 2, Problem 10

Problem 10. For any positive integer \(\displaystyle N\), let \(\displaystyle S_N\) be the number of pairs of integers \(\displaystyle 1\leq a, b\leq N\) such that the number \(\displaystyle (a^2+a)(b^2+b)\) is a perfect square. Prove that the limit

\(\displaystyle \lim_{N\to\infty} \frac{S_N}{N} \)

exists and find its value.

Besfort Shala, University of Bristol

Solution. Throughout the solution, we use the Vinogradov notation \(\displaystyle A\ll B\) to mean \(\displaystyle A=O(B)\), which in turn means that there exists a constant \(\displaystyle C>0\), independent of the quantities \(\displaystyle A\) and \(\displaystyle B\), such that \(\displaystyle \lvert A\rvert\leq C\lvert B\rvert\), on the entirety of the domain where \(\displaystyle A\) and \(\displaystyle B\) are defined (for us, this will always be the interval \(\displaystyle [1, \infty)\).)

We will show that the limit equals \(\displaystyle 1\), corresponding to the trivial solutions \(\displaystyle a=b\). Note that \(\displaystyle (a^2+a)(b^2+b)\) is a perfect square if and only if \(\displaystyle a^2+a=dz_1^2\) and \(\displaystyle b^2+b=dz_2^2\) for some square-free \(\displaystyle d\) and \(\displaystyle z_1, z_2\in\mathbb{Z}_{>0}\). From this point on, all sums over \(\displaystyle d\) will be over square-free positive integers. Multiplying the equations by \(\displaystyle 4\) and setting \(\displaystyle y_i = 2z_i\), we get

\(\displaystyle S_N = \sum_{d\ll N^2} c_d(N)^2 + O(1), \)

where \(\displaystyle c_d(N)\) is the number of solutions to \(\displaystyle (2k+1)^2-dy^2 =1\) with \(\displaystyle 1\leq k\leq N\) and \(\displaystyle 1\leq y\leq N/2\) with \(\displaystyle y\) even. Other than for the purpose of identifying the trivial solutions, we will work with Pell's equation \(\displaystyle x^2-dy^2 = 1\) with \(\displaystyle 1\leq x, y\ll N\). Split the sum as

\(\displaystyle \sum_{\substack{d\ll N^2 \\ c_d(N)\leq 1}}c_d(N) + \sum_{\substack{d\ll N^2 \\ c_d(N)>1}} c_d(N)^2. \)

Note that if \(\displaystyle d\gg N\), then the size of the second solution \(\displaystyle x_2 = x_1^2+dy_1^2\) (coming from \(\displaystyle x_2+y_2\sqrt d=(x_1+y_1\sqrt d)^2\), where \(\displaystyle x_1+y_1\sqrt d\) is the fundamental solution) is \(\displaystyle \gg d\gg N\). Hence we may assume that \(\displaystyle d\ll N\) if \(\displaystyle c_d(N)>1\) (with a suitable choice of hidden constants). Denote the second sum by \(\displaystyle E\) (for error, which we will bound momentarily). The first sum is easily manipulated into being asymptotic to \(\displaystyle N\) (up to the error \(\displaystyle E\)), using the fact that fixing \(\displaystyle x=2a+1\leq 2N+1\) fixes the square-free \(\displaystyle d\) and the square \(\displaystyle y^2\), namely

\(\displaystyle \sum_{\substack{d\ll N^2 \\ c_d(N)\leq 1}} c_d(N) = \sum_{\substack{d\ll N^2}} \sum_{\substack{1\leq a\leq N \\ 1\leq y\leq \frac{N}{2}}} \chi_{(2a+1)^2-dy^2=1} + O\left(E\right) = \sum_{a=1}^{N} \sum_{d, y} \chi_{(2a+1)^2 - 1 = dy^2} + O\left(E \right) = N + O(E). \)

Here \(\displaystyle \chi_{\cdot}\) denotes the characteristic function (taking the value \(\displaystyle 0\) if \(\displaystyle \cdot\) is not satisfied, and \(\displaystyle 1\) otherwise).

Now we bound the error sum \(\displaystyle E\). Note that solutions to Pell's equation \(\displaystyle x^2 - dy^2 = 1\) grow exponentially, hence we have \(\displaystyle c_d(N)\ll \log N\). This means we may assume that \(\displaystyle N\gg d\gg N^{1-\delta}\) for some small enough fixed \(\displaystyle \delta>0\), since the contribution of \(\displaystyle d\ll N^{1-\delta}\) is bounded by \(\displaystyle N^{1-\delta}\log N\). By \(\displaystyle x^2-dy^2=1\), we have that \(\displaystyle d\gg N^{1-\delta}\) implies \(\displaystyle y\ll N^{1/2+\delta}\).

Fixing each \(\displaystyle y\ll N^{\delta/2}\) gives \(\displaystyle \ll N^{1-\delta}\) choices for \(\displaystyle x\) (hence also for \(\displaystyle d\)). So we may assume \(\displaystyle N^{1/2+\delta}\gg y\gg N^{\delta/2}\), since the contribution of \(\displaystyle y\ll N^{\delta/2}\) is bounded by \(\displaystyle N^{1-\delta/2}\).

By placing \(\displaystyle x\) in residue classes modulo \(\displaystyle y^2\) and splitting the interval \(\displaystyle [1, 2N+1]\) into intervals of length \(\displaystyle y^2\), we get that each choice of \(\displaystyle N^{\delta/2}\ll y\ll N^{1/2+\delta}\) gives \(\displaystyle \ll Ng(y)/y^2\) choices for \(\displaystyle x\) (hence also for \(\displaystyle d\)) by \(\displaystyle y^2\mid x^2+1\), where \(\displaystyle g(y) = \lvert \{1\leq x\leq y^2 : x^2+1\equiv 0\pmod {y^2}\}\rvert\). By elementary number theory, \(\displaystyle g\) is multiplicative and \(\displaystyle g(p^k)\leq 2\) for all prime powers \(\displaystyle p^k\). In particular we obtain \(\displaystyle g(n)\leq\tau(n)\ll n^{\varepsilon}\) for any \(\displaystyle \varepsilon>0\) (this is not hard to prove directly for \(\displaystyle g\), but may be used as a well-known fact for the divisor function \(\displaystyle \tau\)). Therefore the contribution of such \(\displaystyle y\) is

\(\displaystyle \ll \sum_{N^{\delta/2}\ll y\ll N^{1/2+\delta}} \frac{Ng(y)}{y^2} \ll N^{1-\delta/2+\varepsilon}, \)

which is acceptable by choosing \(\displaystyle \varepsilon>0\) small enough. We conclude that \(\displaystyle S_N = N(1+o(1))\), as desired.

There is a secondary infinite family of solutions of ``size'' \(\displaystyle \sqrt N\), namely given by \(\displaystyle a=4b(b+1)\). This shows that

\(\displaystyle \limsup_{N\to\infty} \frac{S_N-N}{\sqrt N} >0. \)