Tight bound for the density of sequence of integers the sum of no two of which is a perfect square Original Research Article

Erdős and Sárkőzy 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. Massias [(Sur les suites dont les sommes des terms 2 á 2 ne sont par des carr)] exhibited such a set consisting of all x≡1 (mod 4) with x≡14,26,30 (mod 32). Lagarias et al. [(J. Combin. Theory Ser. A 33 (1982) 167)] showed that for any positive integer n, one cannot find more than 1132n 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 [(J. Combin. Theory Ser. A 34 (1983) 123)] also proved that the density of such a set S is never >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 1132, the same as that for sequences made up of only arithmetic progressions.