Sidon set

A Sidon set in an abelian group is a subset $A$ for which an equality $a+b=c+d$ with $a,b,c,d\in A$ forces the unordered pairs $\{a,b\}$ and $\{c,d\}$ to be equal. Equivalently, the ordered nonzero differences $a-b$ with $a\ne b$ are all distinct.

For a Sidon set $A\subseteq [1,N]$, put $m=|A|$ and let $A_i$ count points in a window of $u$ consecutive integers. Each point occurs in $u$ windows, so $\sum A_i=um$. Cauchy-Schwarz gives $\sum \left(\genfrac{}{}{0ex}{}{A_i}{2}\right)\ge [u^2{m}^2/(N+u)-um]/2$. Each positive difference occurs at most once and contributes $u-d$ windows, giving the upper bound $u(u-1)/2$. Thus $m^2\le (N+u)(1+(m-1)/u)$. Taking $u=\lfloor N^{3/4}\rfloor$ gives the displayed estimate, which combines with the Bose-Chowla Sidon construction to determine the asymptotic maximum.

Choose a generator $\theta$ of the multiplicative group of the quadratic finite field extension. Its $p$ shifts $\theta +t$ define $p$ distinct exponents modulo $p^2-1$. Equality of two sums of exponents gives $(\theta +s)(\theta +t)=(\theta +u)(\theta +v)$. Since $1,\theta$ are independent over the prime field, $s+t=u+v$ and $st=uv$, so the unordered pairs coincide. Thus the exponents form a Sidon set in the cyclic group. Taking integer representatives preserves the Sidon property. Primes within $o(\sqrt{N})$ below $\sqrt{N}$ give $\sqrt{N}-o(\sqrt{N})$ representatives in an interval of length $N$.