2026/08/02 by Dmitry Krachun
Mathematics · #math.CO #math.NT
7 pages
arxiv created 2026/08/02 · arxiv updated 2026/08/04
Let D(N) denote the largest cardinality of a subset of \1,…,N\ containing no nonzero square difference. While a construction certifying D(N)≥ (1-o(1))N1/2 is almost trivial, Erdős conjectured that this bound is sharp up to polylogarithmic factors. This was disproved by Sárközy and later again by Ruzsa, who found an elegant construction showing that D(N)≥ c⋅ N0.733077…, with an absolute constant c>0. His approach was subsequently refined, leading to the previously best known lower bound with exponent 0.7334117… due to Beigel-Gasarch and, independently, Lewko. However, in the original paper Ruzsa observed that 3/4 seems to be the natural barrier of his approach. In this paper we develop a new construction leading to the lower bound \liminfN→∞(log D(N))/(log N) ≥ α_*:= 0.7527964558…; thus crossing the natural exponent-3/4 barrier of Ruzsa's method. The value 0.7527964558… arises from a simple optimisation problem and appears to be the limit of the new approach.