Problem 438

How large can $A\subseteq \{1,\ldots,N\}$ be if $A+A$ contains no square numbers?

Number theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved: the largest such $A$ has $(11/32+o(1))N$ elements. The upper bound is Theorem 3 of Khalfalah, Lodha and Szemerédi (DIMACS report of December 2000; Discrete Math. 256 (2002), a refereed journal), and the lower bound is Massias's construction of density $11/32$ , after Lagarias, Odlyzko and Shearer had proved $11/32$ sharp for unions of residue classes and the general bound $0.475N$ . The site labels the problem SOLVED and credits the paper (page last edited 7 April 2026). Claim page: Khalfalah, Lodha and Szemerédi 2000 (accepted).

KLS02: Khalfalah, A. and Lodha, S. and Szemerédi, E., Tight bound for the density of sequence of integers the sum of no two of which is a perfect square. Discrete Math. (2002), 243-255.
LOS83: Lagarias, J. C. and Odlyzko, A. M. and Shearer, J. B., On the density of sequences of integers the sum of no two of which is a square. II. General sequences. J. Combin. Theory Ser. A 34 (1983), no. 2, 123--139, doi:10.1016/0097-3165(83)90051-1.

Problem 438

Status

Proof claims

Discussion