An improved lower bound related to the Furstenberg-Sárközy theorem

Abstract

Let $D(n)$ denote the cardinality of the largest subset of the set $\{1,2,\ldots,n\}$ such that the difference of no pair of distinct elements is a square. A well-known theorem of Furstenberg and Sárközy states that $D(n)=o(n)$. In the other direction, Ruzsa has proven that $D(n) \gtrsim n^{\gamma}$ for $\gamma = \frac{1}{2}\left( 1 + \frac{\log 7}{\log 65} \right) \approx 0.733077$. We improve this to $\gamma = \frac{1}{2}\left( 1 + \frac{\log 12}{\log 205} \right)  \approx 0.733412$.