## 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