← All problems

Erdős Problem #156 — Small maximal Sidon sets

32 years old · traced to

For a positive integer NN, write [N]={1,…,N}[N]=\{1,\ldots,N\}. A set A⊆[N]A\subseteq[N] is Sidon if sums of unordered pairs of its elements, with repetition allowed, are all distinct; equivalently, whenever a≤ba\le b and c≤dc\le d are in AA and a+b=c+da+b=c+d, one has a=ca=c and b=db=d. It is maximal in [N][N] if no element of [N]∖A[N]\setminus A can be adjoined while preserving the Sidon property; maximal here means inclusion-maximal, not maximum cardinality. The question is whether there are constants C>0C>0 and N0N_0 such that for every integer N≥N0N\ge N_0 there exists an inclusion-maximal Sidon set A⊆[N]A\subseteq[N] with Erdős Problems #156 O’Bryant (2004)

∣A∣≤CN1/3.|A|\le C N^{1/3}.

Erdős Problems #156

Background

The question is attributed to Erdős, Sárközy, and Sós, whose 1994 paper is titled “On Sum Sets of Sidon Sets, I.” Maximality is a local obstruction condition: every omitted integer must create a repeated pair-sum if added. This differs from asking for a Sidon set of largest possible size, which is a maximum-cardinality problem. Erdős Problems #156 Erdős, Sárközy, and Sós (1994)

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.