Difference Sets without Squares (Rusza, Pintz, Steiger, and Szemeredi)

What is largest size of set such that there is no square in the difference set?
That is we don’t want solutions to a=b= s^2, \quad a, b \in S .

Lower bounds:

(Rusza) There exists a set of size x^{0.73} contained in [1, x] .

Proof: Rusza uses the following property: If there is a set such that its difference set modulo some number doesn’t have squares, then the difference set itself doesn’t have squares.

Lemma: Let m be a squarefree integer. If R is a square difference free set mod m of [1, m] then A =\{ \sum_{r_i}m^{i}| r_2j \in R, r_i \in [1, m]\} is a square difference free set.

If a=\sum r_{j} m^{j}, a^{\prime}=\sum r_{j}^{\prime} m^{j} and a-a{\prime}= t^2 , then we get t^2=a-a^{\prime}=(r_s -r^{\prime}_s)m^s + zm^{s+1} , where s is smallest index where a and a^{\prime} differ.
If s is odd, m^s dividing t^2 and the fact that m is squarefree implies that m^{s+1} |t^2 . This cannot happen because the we get a-a^{\prime} = \mod m.
If s is even then divding by m^{s} on both sides, we get

\left(\frac{t}{m^{s/2}}\right)^{2} = (r_s -r^{\prime}_s) + zm . If we go modulo m , we get that r_s -r^{\prime}_{s} =\square \mod m , but r_s, r^{\prime}_{s} are elements of the square difference set mod m R which is not possible.

The size of the set A restricted to [1, m^n] is A\left(m^{n}\right)=|R|^{1+[n-1 / 2]} m^{n-1-[n-1 / 2]}

Therefore using R =\{0,2,5,22,24,43,46\} which is difference free mod 65 and x= m^n , we get a set of size x^{0.5 (1+ \log_{65}{ 7})} \approx x^{0.73}.

(If we can find better examples of R and m, then we can improve these numerical results)

Upper Bounds:
The largest square difference free set has size at most
(Sarkozy) : O\left(\frac{n(\log \log n)^{2 / 3}}{(\log n)^{1 / 3}}\right)
(Pintz, Steiger, and Szemeredi): \frac{n}{\left.(\log n)^{O(\log \log \log \log n}\right)}

The proof of these results depends on Roth’s theorem type arguments using Fourier coefficients, density and energy increment arguments.
(See Wolf: Sets whose differences set is square-free, 2008)

Posted in $.

Leave a comment