A finite set $ S \subset \mathbb{ R} $ is called a Sidon set if all sums $ x+y $ with $ x,y \in S $ and $ x \le y $ are distinct, and a weak Sidon set if all sums $ x+y $ with $ x,y \in S $ and $ x < y $ are distinct. For a finite set $ A \subset \mathbb{ R} $, let $ h(A) $ denote the maximum size of a Sidon subset of $ A $, and define $$ g(n) := \min\{ \, h(A) : A \subset \mathbb{ R},\ |A| = n,\ A \text{ is a weak Sidon set} \,\}. $$ S\'ark\"ozy and S\'os asked whether the limit $ \lim_{ n\to\infty} g(n)/n $ exists and, if so, to determine its value. We resolve this problem completely by determining $g(n)$ exactly: $$ g(n)=\left\lceil \frac{ n+1}{ 2}\right\rceil \qquad\text{ for all } n\ge 1. $$ In particular, $\lim_{ n\to\infty} g(n)/n=\frac12$. We also investigate a related problem of Erd\H{ o}s concerning a local difference condition. A finite set $ A \subset \mathbb{ R} $ is called a $(4,5)$-set if every $4$-element subset of $A$ determines at least five distinct values among its six pairwise absolute differences. Erd\H{ o}s asked for the optimal constant $ c_* > 0 $ such that every $(4,5)$-set of size $ n $ contains a Sidon subset of size at least $ c_* n $. Gy\'arf\'as and Lehel reduced this to an extremal problem of $3$-uniform hypergraphs and proved $\frac{ 1}{ 2} + \frac{ 1}{ 141 \cdot 76} \le c_* \le \frac{ 3}{ 5}$. We improve both bounds by establishing $$ \frac{ 9}{ 17} \le c_* \le \frac{ 4}{ 7}, $$ where the lower bound uses a reformulation of the extremal problem, and the upper bound follows from an explicit construction together with a convenient characterization of $c_*$.
Categories: math.CO