uniolympiads Ελληνικά

IMC 2025, Day 2, Problem 10

For any positive integer NN, let SNS_N be the number of pairs of integers 1≤a,b≤N1 \le a, b \le N such that the number (a2+a)(b2+b)(a^2 + a)(b^2 + b) is a perfect square. Prove that the limit

lim⁡N→∞SNN\lim_{N \to \infty} \frac{S_N}{N}

exists and find its value.

Original from the official PDFFor any positive integer N , let S N be the number of pairs of integers 1 ≤ a, b ≤ N such that the number (a 2 + a)(b 2 + b) is a perfect square. Prove that the limit S N N →∞ N lim exists and find its value.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Besfort Shala, University of Bristol)

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

We will show that the limit equals 11, corresponding to the trivial solutions a=ba = b. Note that (a2+a)(b2+b)(a^2 + a)(b^2 + b) is a perfect square if and only if a2+a=dz12a^2 + a = dz_1^2 and b2+b=dz22b^2 + b = dz_2^2 for some square-free dd and z1,z2∈Z>0z_1, z_2 \in \mathbb{Z}_{>0}. From this point on, all sums over dd will be over square-free positive integers. Multiplying the equations by 44 and setting yi=2ziy_i = 2z_i, we get

SN=∑d≪N2cd(N)2+O(1),S_N = \sum_{d \ll N^2} c_d(N)^2 + O(1),
where cd(N)c_d(N) is the number of solutions to (2k+1)2−dy2=1(2k+1)^2 - dy^2 = 1 with 1≤k≤N1 \le k \le N and 1≤y≤N/21 \le y \le N/2 with yy even. Other than for the purpose of identifying the trivial solutions, we will work with Pell’s equation x2−dy2=1x^2 - dy^2 = 1 with 1≤x,y≪N1 \le x, y \ll N. Split the sum as
∑d≪N2cd(N)≤1cd(N)+∑d≪N2cd(N)>1cd(N)2.\sum_{\substack{d \ll N^2 \\ c_d(N) \le 1}} c_d(N) + \sum_{\substack{d \ll N^2 \\ c_d(N) > 1}} c_d(N)^2.

Note that if d≫Nd \gg N, then the size of the second solution x2=x12+dy12x_2 = x_1^2 + dy_1^2 (coming from x2+y2d=(x1+y1d)2x_2 + y_2\sqrt{d} = (x_1 + y_1\sqrt{d})^2, where x1+y1dx_1 + y_1\sqrt{d} is the fundamental solution) is ≫d≫N\gg d \gg N. Hence we may assume that d≪Nd \ll N if cd(N)>1c_d(N) > 1 (with a suitable choice of hidden constants). Denote the second sum by EE (for error, which we will bound momentarily). The first sum is easily manipulated into being asymptotic to NN (up to the error EE), using the fact that fixing x=2a+1≤2N+1x = 2a + 1 \le 2N + 1 fixes the square-free dd and the square y2y^2, namely

∑d≪N2cd(N)≤1cd(N)=∑d≪N2 ∑1≤a≤N1≤y≤N2χ(2a+1)2−dy2=1+O(E)=∑a=1N∑d,yχ(2a+1)2−1=dy2+O(E)=N+O(E).\sum_{\substack{d \ll N^2 \\ c_d(N) \le 1}} c_d(N) = \sum_{d \ll N^2}\ \sum_{\substack{1 \le a \le N \\ 1 \le y \le \frac{N}{2}}} \chi_{(2a+1)^2 - dy^2 = 1} + O(E) = \sum_{a=1}^{N}\sum_{d,y} \chi_{(2a+1)^2 - 1 = dy^2} + O(E) = N + O(E).
Here χ⋅\chi_{\cdot} denotes the characteristic function (taking the value 00 if ⋅\cdot is not satisfied, and 11 otherwise).

Now we bound the error sum EE. Note that solutions to Pell’s equation x2−dy2=1x^2 - dy^2 = 1 grow exponentially, hence we have cd(N)≪log⁡Nc_d(N) \ll \log N. This means we may assume that N≫d≫N1−δN \gg d \gg N^{1-\delta} for some small enough fixed δ>0\delta > 0, since the contribution of d≪N1−δd \ll N^{1-\delta} is bounded by N1−δlog⁡NN^{1-\delta}\log N. By x2−dy2=1x^2 - dy^2 = 1, we have that d≫N1−δd \gg N^{1-\delta} implies y≪N1/2+δy \ll N^{1/2+\delta}.

Fixing each y≪Nδ/2y \ll N^{\delta/2} gives ≪N1−δ\ll N^{1-\delta} choices for xx (hence also for dd). So we may assume N1/2+δ≫y≫Nδ/2N^{1/2+\delta} \gg y \gg N^{\delta/2}, since the contribution of y≪Nδ/2y \ll N^{\delta/2} is bounded by N1−δ/2N^{1-\delta/2}.

By placing xx in residue classes modulo y2y^2 and splitting the interval [1,2N+1][1, 2N+1] into intervals of length y2y^2, we get that each choice of Nδ/2≪y≪N1/2+δN^{\delta/2} \ll y \ll N^{1/2+\delta} gives ≪Ng(y)/y2\ll Ng(y)/y^2 choices for xx (hence also for dd) by y2∣x2+1y^2 \mid x^2 + 1, where g(y)=∣{1≤x≤y2:x2+1≡0(mody2)}∣g(y) = |\{1 \le x \le y^2 : x^2 + 1 \equiv 0 \pmod{y^2}\}|. By elementary number theory, gg is multiplicative and g(pk)≤2g(p^k) \le 2 for all prime powers pkp^k. In particular we obtain g(n)≤τ(n)≪nεg(n) \le \tau(n) \ll n^{\varepsilon} for any ε>0\varepsilon > 0 (this is not hard to prove directly for gg, but may be used as a well-known fact for the divisor function τ\tau). Therefore the contribution of such yy is

≪∑Nδ/2≪y≪N1/2+δNg(y)y2≪N1−δ/2+ε,\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 ε>0\varepsilon > 0 small enough. We conclude that SN=N(1+o(1))S_N = N(1 + o(1)), as desired.

Remark. There is a secondary infinite family of solutions of “size” N\sqrt{N}, namely given by a=4b(b+1)a = 4b(b+1). This shows that

lim sup⁡N→∞SN−NN>0.\limsup_{N\to\infty} \frac{S_N - N}{\sqrt{N}} > 0.

Transcribed from the official solutions, pages 6–7. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?