← All problems

Erdős Problem #864 — Almost unique pair-sum sets

35 years old · traced to

For a positive integer NN, let A⊆{1,…,N}A\subseteq\{1,\ldots,N\} and, for each integer nn, let

rA(n)=#{(a,b)∈A2:a≤b, a+b=n}.r_A(n)=\#\{(a,b)\in A^2:a\le b,\ a+b=n\}.

Thus each unordered pair is counted once, including a diagonal pair a=ba=b. Define

M(N)=max⁡{∣A∣:A⊆{1,…,N}, #{n∈Z:rA(n)>1}≤1}.M(N)=\max\left\{|A|:A\subseteq\{1,\ldots,N\},\ \#\{n\in\mathbb Z:r_A(n)>1\}\le1\right\}.

Estimate M(N)M(N) as N→∞N\to\infty. In particular, is

M(N)≤(1+o(1))23N1/2M(N)\le (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}

true? Erdős Problem #864

Background

The problem is attributed to Erdős and Freud and is associated with their 1991 paper, “On sums of a Sidon-sequence.” A Sidon set is a set in which every integer has at most one representation as an unordered pair sum. The construction relevant here uses such a set together with its reflection in the midpoint of the interval; the many repeated sums are concentrated at the single central value. Erdős Problem #864 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.