= Sliding-window upper bound for Sidon sets
{title2=$|A|\leq\sqrt N+O(N^{1/4})$}
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\binom{A_i}2\geq[u^2m^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\leq(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.
Back to article page
