Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 864

Statement. Let $A\subseteq \{1,\ldots N\}$ be a set such that there exists at most one $n$ with more than one solution to $n=a+b$ (with $a\leq b\in A$ ). Estimate the maximal possible size of $\lvert A\rvert$ - in particular, is it true that

\lvert A\rvert \leq (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}?

Status. Open.

Source. erdosproblems.com/864, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #864, https://www.erdosproblems.com/864.

References.

[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. The site gives this paper and [Er92c] as the problem's sources and calls it a problem of Erdős and Freud; this paper supplies the displayed constant. Its construction on p. 204, a maximally dense Sidon set $B\subset[1,n/3]$ together with $n-B$ , has $(2/\sqrt3+o(1))n^{1/2}$ elements and, by the argument printed for its $[1,n/4]$ version on p. 203, all sums distinct except those equal to $n$ ; it is the set behind the constant $2/\sqrt3$ , and the paper does not ask whether it is optimal. Library home: erdos_freud_1991_sums_sidon_sequence; result page Definition (p. 203).
[Er92c] Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. 15 (1992), 34--50, DOI 10.46298/hrj.1992.125. In §2 (pp. 39--40) Erdős reports the Erdős--Freud construction for sets in which only one sum is represented more than once and proposes $\max k=(1+o(1))\frac{2}{\sqrt3}n^{1/2}$ as the probable truth, which is this problem. Library home: erdos_1992_my_forgotten_problems_number_theory.

Formalization. None recorded.

Current assessment

No current assessment is recorded. The status above is imported from the dated site record. This page records no current literature search or independent assessment of proof coverage.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (28)

Additive Bases and Sidon Sets O'Bryant: A Complete Annotated Bibliography of Work Related to Sidon Sequences Erdös–Turán: On a Problem of Sidon in Additive Number Theory, and on some Related Problems Erdős et al.: On sum sets of Sidon sets, II O'Bryant: A Complete Annotated Bibliography of Work Related to Sidon Sequences Additive Bases and Sidon Sets additive_bases/erdos_1941_problem_sidon_additive_number_theory_related Theorem (p. 212): the largest Sidon set in [1,n] exceeds (1/sqrt(2) - e) sqrt(n)Theorem (p. 212): the largest Sidon set in [1,n] has fewer than (1 + e) sqrt(n) elements additive_bases/erdos_1981_problems_results_additive_multiplicative_number_theory Construction (p. 175): (1+o(1))2(n/3)^{1/2} integers up to n whose sums are distinct except those equal to n Theorem (p. 175): k = [(1+c)n^{1/2}] integers up to n have fewer than (1−ε_c) binom(k,2) distinct differences additive_bases/erdos_1994_sum_sets_sidon_sets_i Problem 5 (p. 346): extending Theorems 1 and 2 to nearly Sidon sets Theorem 1 (p. 330): the sumset of a finite Sidon set has more than c_1|A|^2 starts under every shift d Theorem 2 (p. 331): limsup of B(S_A,d,N)/A(N)^2 exceeds c_2 for every infinite Sidon set Erdős et al.: On sum sets of Sidon sets, II Theorem 1 (p. 223): a Sidon set in [1, N] has fewer than L/2 + 7L^(1/2)N^(1/4) sums in any length-L interval Theorem 3 (p. 229): a finite B_2[g] set has covering measure D_m(A) > |A|^2/(2^(m+1)g)additive_bases/erdos_freud_1991_sums_sidon_sequence Definition (p. 203): quasi-Sidon sequences, with the construction of size (2/sqrt 3) sqrt n and the bound (37)additive_bases/obryant_2004_complete_annotated_bibliography_work_related_sidon Definition 1 (p. 3): B_h^*[g] sequences, bounded ordered h-fold representation counts Theorem 5 (p. 10): the largest Sidon subset of [n] has ~ sqrt(n) elements additive_bases/pikhurko_2006_dense_edge_magic_graphs_thin_additive Theorem 2 (p. 2098): the upper bound on the largest sumset of a k-subset of [n]Theorem 3 (p. 2099): quasi-Sidon subsets of [n] have at most (1.863... + o(1)) n^(1/2) elements integer_sequences/erdos_1992_my_forgotten_problems_number_theory

Graph