2000-39: Tight Bound for the Density of Sequences of Integers the Sum of No Two of which is a Perfect Square

DIMACS TR: 2000-39

Tight Bound for the Density of Sequences of Integers the Sum of No Two of which is a Perfect Square

Authors: Ayman Khalfalah, Sachin Lodha and Endre Szemeredi

ABSTRACT
P. Erd\H{o}s and D. Silverman~\cite{eg-80} proposed the problem of determining the maximal density attainable by a set $S$ of positive integers having the property that no two distinct elements of $S$ sum up to a perfect square. J. P. Massias exhibited such a set consisting of all $x \equiv 1$ (mod $4$) with $x \equiv 14, 26, 30$ (mod $32$) in~\cite{m}. In~\cite{los-82}, J. C. Lagarias, A. M. Odylzko and J. B. Shearer showed that for any positive integer $n$, one cannot find more than $\frac{11}{32} n$ residue classes (mod $n$) such that the sum of any two is never congruent to a square (mod $n$), thus essentially proving that the Massias' set has the best possible density. They~\cite{los-83} also proved that the density of such a set $S$ is never more than $0.475$ when we allow general sequences.

We improve on the lower bound for general sequences, essentially proving that it is not $0.475$, but arbitrarily close to $\frac{11}{32}$, the same as that for sequences made up of only arithmetic progressions.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-39.ps.gz

DIMACS Home Page