Logo
All Random Solved Random Open
OPEN
Let $A\subset \mathbb{R}_{>0}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$.
For comparison, note that if $B$ were a Sidon set then $\lvert B-B\rvert=13$, so this condition is saying that at most one difference is 'missing' from $B-B$. Equivalently, one can view $A$ as a set such that every four points determine at least five distinct distances, and ask for a subset with all distances distinct.

Erdős and Sós proved that $c\geq 1/2$. Gyárfás and Lehel [GyLe95] proved \[\frac{1}{2}<c<\frac{3}{5}.\] (The example proving the upper bound is the set of the first $n$ Fibonacci numbers.)