Let S be a finite set of integers. We define d2(S) and d3(S) as: ∙ d2(S) is the number of elements a∈S such that there exist x,y∈Z such that x2−y2=a ∙ d3(S) is the number of elements a∈S such that there exist x,y∈Z such that x3−y3=a (a) Let m be an integer and S={m,m+1,…,m+2019}. Prove: d2(S)>137d3(S) (b) Let Sn={1,2,…,n} with n a positive integer. Prove that there exists a N so that for all n>N: d2(Sn)>4⋅d3(Sn)
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=x2−y2 must be either odd or divisible by 4.
On the other hand, (y+1)2−y2=2y+1 and (y+1)2−(y−1)2=4y, so d2(S) counts exactly the odd numbers and the multiples of 4 in S.
For d3(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.