← All problems

Erdős Problem #840 — Quasi-Sidon sets in intervals

45 years old · traced to

For a finite set A⊂{1,…,N}A\subset\{1,\ldots,N\}, write A+A={a+a′:a,a′∈A}A+A=\{a+a':a,a'\in A\}, and let k=∣A∣k=|A|. The question calls AA quasi-Sidon when, along sets with k→∞k\to\infty, the number of distinct sums satisfies

∣A+A∣=(1+o(1))(k2).|A+A|=(1+o(1))\binom{k}{2}.

It asks for the asymptotic growth of the largest possible size f(N)f(N) of such a subset of {1,…,N}\{1,\ldots,N\}. Thus the o(1)o(1) is an asymptotic condition on the sets under consideration, rather than a finite-NN test with a specified error tolerance. Bloom, Erdős Problem #840 Pikhurko, Dense Edge-Magic Graphs and Thin Additive Bases

Background

The condition asks for a set whose pairwise sums are nearly as numerous as the pairs of elements: additive coincidences must be sparse on the scale of k2k^2. It is weaker than the Sidon property, which requires distinct unordered pairs to have distinct sums. Erdős and Freud considered the quasi-Sidon extremal question; the problem record also traces the bounds to earlier work of Erdős. Bloom, Erdős Problem #840 Erdős and Freud, On sums of a Sidon-sequence (1991)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.