Erdős Problems
Wiki
Wiki

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

Updated

Problem 840

../

Statement. Let f(N)f(N) be the size of the largest quasi-Sidon subset A⊂{1,…,N}A\subset\{1,\ldots,N\}, where we say that AA is quasi-Sidon if

∣A+A∣=(1+o(1))(∣A∣2).\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.

How does f(N)f(N) grow?

Status. Open.

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

References.

  • [Er81h] Erdős, P., Some problems and results on additive and multiplicative number theory. Analytic number theory (Philadelphia, Pa., 1980) (1981), 171-182.
  • [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 Definition of a quasi-Sidon sequence, p. 203; the construction of (2/3+o(1))n1/2(2/\sqrt3+o(1))n^{1/2} elements, the trivial bound (37), k≤(2+o(1))n1/2k\le(2+o(1))n^{1/2}, and the unproved 1.981.98 in its place, p. 204. Library home: erdos_freud_1991_sums_sidon_sequence; result page Definition (p. 203).
  • [Pi06] Pikhurko, Oleg, Dense edge-magic graphs and thin additive bases. Discrete Math. (2006), 2097-2107.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

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 (14)
Additive Bases and Sidon SetsProblem 819Erdős and Freud's lower bound 3/8 for the sumset densityLiu's lower bound 0.469 for the sumset density f(N)/Nadditive_bases/erdos_1981_problems_results_additive_multiplicative_number_theoryConstruction (p. 175): (1+o(1))2(n/3)^{1/2} integers up to n whose sums are distinct except those equal to nQuestion (p. 175): the largest c with (1+o(1))cn^{1/2} integers up to n having (1+o(1))binom(k,2) distinct sumsadditive_bases/erdos_freud_1991_sums_sidon_sequenceDefinition (p. 203): quasi-Sidon sequences, with the construction of size (2/sqrt 3) sqrt n and the bound (37)additive_bases/pikhurko_2006_dense_edge_magic_graphs_thin_additiveTheorem 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) elementsTheorem 8 (p. 2101): the sumset bound for sets with elements outside [n]additive_bases/sarkozy_1997_additive_representation_functions
Graph