Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 7 / 6 / ii / Solution

Write $m=|A|$, choose $u=\lfloor N^{3/4}\rfloor$, and let $A_i$ count the points of $A$ in the length-$u$ window ending at $i$, for $1\le i\le N+u$. Each element occurs in precisely $u$ such windows, so ${\sum }_i{A}_i=um$. The Cauchy-Schwarz inequality consequently givesOn the other hand, a pair $a<b$ of difference $d=b-a<u$ belongs to exactly $u-d$ windows; larger differences contribute none. The Sidon set condition permits at most one pair for each positive difference $d$. ThereforeCombining these two estimates proves the sliding-window upper bound for Sidon sets:If $D=(N+u)/u$, the final inequality for this quadratic polynomial implies $m\le \sqrt{N+u}+D$; otherwise $m(m-D)>N+u$. With the chosen $u$, $D=O(N^{1/4})$ and $\sqrt{N+u}=\sqrt{N}+O(N^{1/4})$. ThusTogether with part (i)'s construction, this proves that the maximum cardinality is $\sqrt{N}+o(\sqrt{N})$. The lower and upper error terms need not have the same size to establish that asymptotic conclusion.