Let $S$ be a finite set of integers. We define $d_2(S)$ and $d_3(S)$ as: $\bullet$ $d_2(S)$ is the number of elements $a \in S$ such that there exist $x, y \in \mathbb{Z}$ such that $x^2-y^2 = a$ $\bullet$ $d_3(S)$ is the number of elements $a \in S$ such that there exist $x, y \in \mathbb{Z}$ such that $x^3-y^3 = a$ (a) Let $m$ be an integer and $S = \{m, m+1, \ldots, m+2019\}$. Prove: $$d_2(S) > \frac{13}{7} d_3(S)$$ (b) Let $S_n = \{1, 2, \ldots, n\}$ with $n$ a positive integer. Prove that there exists a $N$ so that for all $n > N$: $$ d_2(S_n) > 4 \cdot d_3(S_n) $$
Problem
Source: Spain Mathematical Olympiad 2020 P6
Tags: difference of squares, number theory, Spain, Analytic Number Theory
Tintarn
15.07.2020 21:45
In general, it is easy to see that $a=x^2-y^2$ must be either odd or divisible by $4$.
On the other hand, $(y+1)^2-y^2=2y+1$ and $(y+1)^2-(y-1)^2=4y$, so $d_2(S)$ counts exactly the odd numbers and the multiples of $4$ in $S$.
For $d_3(S)$, we can see that $x^3 \equiv \{0,1,-1\} \mod 7$ and similarly mod $9$. So $x^3-y^3$ can take at most $5$ residue classes mod $7$ and $5$ residue classes mod $9$, so only $25$ residue classes mod $63$. This is already good enough to solve (a).
(a) Among $2020$ successive numbers, there are exactly $\frac{3}{4} \cdot 2020=1515$ odd numbers or multiples of $4$. Hence $d_2(S)=1515$.
Moreover, $2020=32 \cdot 63+4$ so there are at most $32 \cdot 25+4=804$ differences of two cubes. Hence
\[\frac{13}{7} \cdot d_3(S) \le \frac{13}{7} \cdot 804 <1494<1515.\](b) As before, we have $d_2(S_n)>\frac{3n-2}{4}$ and hence it suffices to show that $d_3(S_n)<\frac{3n-2}{16}$ for all sufficiently large $n$.
Since $\frac{25}{63}>\frac{3}{16}$ our argument from above is not quite good enough.
But in fact, for large $n$, there are much fewer than $cn$ sums of cubes for any $c>0$. This is because cubes are very sparse.
Indeed, to represent $n=x^3-y^3$ we have two possibilities:
Either $x$ is positive and $y$ is negative. Then certainly $x,y \le \sqrt[3]{n}$ and this gives at most $n^{2/3}$ possibilities.
The harder case is when $x,y$ are both positive. Then they can be larger, but not all that much: Let $d=x-y$. Then $x=y+d$ and
\[n=(y+d)^3-y^3=3dy^2+3d^2y+d^3.\]So certainly $d \le n^{1/3}$ and also $y^2 \le n$ so that $y \le n^{1/2}$. This gives at most $n^{5/6}$ possible choices for $(y,d)$ and hence for $(x,y)$. So all in all, we get
\[d_3(S_n)\le n^{2/3}+n^{5/6}\]which is certainly much smaller than $\frac{3n-2}{16}$ for $n$ sufficiently large.
Remarks:
1) In fact, by counting $d$ and $y$ slightly more carefully one can improve $n^{5/6}$ to $n^{2/3}$.
2) Note that it would not be enough to only show that $x$ and $y$ are both less than $n^{1/2}$, this would combine to $n$ possible choices which would be too much. While it is true that both can be as large as $n^{1/2}$, it is crucial that the difference $d$ has to be much smaller.