Problem 587

What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that, for all $\emptyset\neq S\subseteq A$ , $\sum_{n\in S}n$ is not a square?

Source: erdosproblems.com/587

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. Nguyen and Vu (2010) prove that a square-sum-free subset of $\{1,\ldots,N\}$ has at most $N^{1/3}(\log N)^C$ elements for an absolute constant $C$ , matching Erdős's construction of order $N^{1/3}$ (the first $k$ multiples of a prime $p\approx N^{2/3}$ with $1+\cdots+k<p$ ) up to the logarithmic factor, so the largest such set has size $N^{1/3+o(1)}$ ; the site's curator, Thomas Bloom, labels the problem SOLVED and credits them, describing the problem as solved in essence; the Formulation above records the reading under which the label attaches to the order of magnitude. A public Lean development reports a gap in the proof of the paper's Lemma 4.2 and proves the bound by a corrected route; see the claim page. The claim page of Nguyen and Vu records the acceptance, and the frontmatter standing derives from it. The site points to Problem 438 as related.

NgVu10: Nguyen, Hoi H. and Vu, Van H., Squares in sumsets. An irregular mind (Szemerédi is 70), Bolyai Society Mathematical Studies 21, Springer (2010), 491--524; DOI 10.1007/978-3-642-14444-8_14; arXiv:0811.1311 (v1 of 9 November 2008, v2 of 29 October 2009). Theorems 1.4 and 1.5 and Example 1.2 are cited from the arXiv version. Library home: Nguyen 2010.
Er89: Erdős, P., Some problems and results on combinatorial number theory. Graph theory and its applications: East and West (Jinan, 1986), Ann. New York Acad. Sci. 576 (1989), 132--145. Not held. The site's header key is identified with this paper by inference, not by a site record: Nguyen and Vu write that Erdős raised the question in 1986 and cite, as their reference [4], his Some problems and results on combinatorial number theory in the proceedings of the first China conference on combinatorics (1986), which is the Jinan conference whose proceedings appeared in 1989.

Problem 587

Status

Proof claims

Discussion