Problem 819

Let $f(N)$ be maximal such that there exists $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$ . Estimate $f(N)$ .

Source: erdosproblems.com/819

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem OPEN. Its commentary credits Erdős and Freud [ErFr91] (J. Number Theory 38 (1991) 196--205, refereed) with $(\tfrac38-o(1))N\le f(N)\le(\tfrac12+o(1))N$ and ties the problem to how large a quasi-Sidon set can be, Problem 840. The bounds are the paper's Proposition 1 (p. 203): "Given any $\varepsilon>0$ , then for $n$ large enough $3/8-\varepsilon\le T(n)/n\le1/2+\varepsilon$ ", the upper bound being the count of all sums and the lower bound the set $B\cup(3n/4-B)$ for a maximally dense Sidon set $B\subset[1,n/4]$ , whose sums are all distinct except those equal to $3n/4$ ; the connection to quasi-Sidon sets rests on the paper's statement (p. 204) that improving the upper bound of Proposition 1 and pushing the coefficient in the trivial quasi-Sidon bound $k\le(2+o(1))n^{1/2}$ below $\sqrt2$ are equivalent problems. The lower bound is the accepted partial claim Erdős and Freud's lower bound, on the refereed paper. A discussion-thread comment of 15 May 2026 announces a nine-page note on the commenter's personal site claiming $\liminf f(N)/N\ge(16\sqrt2-17)/12\approx0.4690$ , found with GPT-5.5 and Rethlas and verified by hand according to the comment; the note's statement is recorded and its argument is not checked in this corpus; no proof claim is on the tab and the site's commentary does not mention it. It has a partial claim page, Liu's lower bound 0.469, with status claimed. No refereed source improving the bounds was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness.

ErFr91: Erdős, P. and Freud, R., On sums of a Sidon-sequence. J. Number Theory 38 (1991), no. 2, 196--205, DOI 10.1016/0022-314X(91)90083-N (June 1991; the Crossref record lists the publisher's open-archive license). The definition of $T(n)$ , Proposition 1 with its proof, Remark 1 and the Definition of a quasi-Sidon sequence, printed p. 203; the quasi-Sidon construction, the trivial bound (37), the unproved $1.98$ , the equivalence sentence and Remark 2, p. 204; Lemma 1 on the uniform distribution of maximal Sidon sequences, p. 197. Claim page: Erdős and Freud's lower bound. Library home: Erdős and Freud 1991; result pages Proposition 1 and Definition (p. 203).
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397--406. Not held.
Pi06: Pikhurko, O., Dense edge-magic graphs and thin additive bases. Discrete Math. 306 (2006), 2097--2107, DOI 10.1016/j.disc.2006.05.003; library home: Pikhurko 2006. Its p. 2098 restates the quasi-Sidon question of [ErFr91] with their construction of quasi-Sidon sets of size $(2/\sqrt3+o(1))n^{1/2}$ and their promised bound $1.98n^{1/2}$ , its Lemma 10 (p. 2104) generalizes [ErFr91]'s Lemma 1 (p. 197) on the uniform distribution of maximum Sidon sets, and its Lemma 12 (p. 2105) borrows from [ErFr91] the reflected set $A\cup(n-A)$ of a Sidon set $A$ (the construction of [ErFr91]'s Proposition 1, p. 203, and its enlargement, p. 204). It does not restate the bounds on $f(N)$ and is context for the problem, not progress on it.
Liu26: Liu, Y. L., Erdős #819: Reflected Sidon lower bound. A note dated 15 May 2026, 9 pp., at https://leon2k2k2k.github.io/assets/pdf/erdos/erdos819.pdf (the thread links https://leon2k2k2k.github.io/erdos819.pdf, which redirects there; not held); its Theorem 3 (p. 1) claims $\liminf f(N)/N\ge(16\sqrt2-17)/12$ . Claim page: Liu's lower bound 0.469.

Problem 819

Status

Proof claims

Discussion