Problem 1551

First, we observe that a number can be written as a difference of squares if and only if it is not of the form $4k + 2$. To see this, we write $x^2 - y^2 = \alpha \cdot \beta$, where $\alpha$ and $\beta$ have the same parity, and we simply set $x = \frac{\alpha+\beta}{2}$, $y = \frac{\beta-\alpha}{2}$. For example, if $n = 4k$ we may take $\alpha = 2$, $\beta = 2k$; if $n = 4k + 1$ or $n = 4k + 3$, we may take $\alpha = 1$, $\beta = n$. Conversely, a difference of squares can never leave remainder 2 upon division by 4 (simply noting that a square is 0 or 1 modulo 4).

Let us now analyze what the differences of two cubes can look like. We observe that the residue modulo 7 of the cube of an integer can only be 0, 1, or 6; consequently, the difference of two cubes, modulo 7, can only be 0, 1, 2, 5, or 6. Doing the same modulo 9, we see that the residue of a cube modulo 9 can only be 0, 1, or 8; consequently, the difference of two cubes modulo 9 can only be 0, 1, 2, 7, or 8. Therefore, there are at most 5 options modulo 7 and 5 options modulo 9, and, by the Chinese Remainder Theorem, we have only 25 options modulo 63.

In an interval of length 2020 (a multiple of 4), exactly 3/4 of the numbers will be non-congruent to 2 modulo 4 (that is, $d_2(S) = 1515$). On the other hand, we have that $2020 = 32 \cdot 63 + 4$, so that
$$d_3(S) \leq 32 \cdot 25 + 4 = 804.$$
Therefore, we have that $d_2(S)/d_3(S) \geq 1515/804 > 13/7$, as we wanted to show.

We now move on to solving the second part. The same reasoning used above shows that
$$\frac{3n}{4} - \frac{1}{2} \leq d_2(S_n) \leq \frac{3n}{4} + \frac{1}{4}.$$
It will then suffice to show that asymptotically $d_3(n) < \frac{3n}{16}$, that is, that for sufficiently large values of $n$ this last inequality holds.

Suppose that $x > y > 0$. A first observation is that if $x^3 - y^3 \le n$, then
$$n \ge x^3 - y^3 = (x - y)(x^2 + xy + y^2) \ge x^2 + xy + y^2 > 3y^2,$$
so that $y < \sqrt{n/3}$. On the other hand,
$$x^3 \le n + y^3 \le n + (n/3)^{3/2}.$$
That is, $x \le \sqrt[3]{n + (n/3)^{3/2}}$. Since the ratio $n/(n/3)^{3/2}$ tends to 0 as $n$ tends to infinity, we have that for any $\delta > 0$ there will exist a sufficiently large number $N$ such that when $n > N$,
$$x \le \sqrt[3]{n + (n/3)^{3/2}} < (1 + \delta)\sqrt{n/3}.$$
Since we also know that $y < x$, the number of pairs is necessarily bounded by $(1+\delta)^{2n/3}/2$. Therefore, we can obtain at most $(1+\delta)^2n/6$ numbers. We note that it is not necessary to consider the case where $x, y < 0$, since the numbers obtained will be the same.

In the case where $y < 0 < x$, we have that $x^3 + (-y)^3 \le n$, and it must be that $x, -y < n^{1/3}$, so that we can obtain at most $n^{2/3}$ numbers. Selecting a sufficiently small $\delta$ (for example $\delta = 0.01$), we conclude that
$$d_3(S_n) \le (1 + 0.01)^2 n/6 + n^{2/3} < \frac{3n}{16}$$
if $n$ is sufficiently large.