= 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\leq i\leq N+u$. Each element occurs in precisely $u$ such windows, so $\sum_i A_i=um$. The <Cauchy-Schwarz inequality> consequently gives
$$
\sum_i\binom{A_i}2=\frac12\left(\sum_iA_i^2-um\right)\geq\frac12\left(\frac{u^2m^2}{N+u}-um\right).
$$
On 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$. Therefore
$$
\sum_i\binom{A_i}2\leq\sum_{d=1}^{u-1}(u-d)=\frac{u(u-1)}2.
$$
Combining these two estimates proves the <sliding-window upper bound for Sidon sets>:
$$
m^2\leq(N+u)\left(1-\frac1u+\frac mu\right)\leq N+u+\frac{N+u}{u}m.
$$
If $D=(N+u)/u$, the final inequality for this <quadratic polynomial> implies $m\leq\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})$. Thus
$$
\boxed{|A|\leq\sqrt N+O(N^{1/4})=\sqrt N+o(\sqrt N).}
$$
Together with part (i)'s construction, this proves that the maximum <cardinality> is \b[$\sqrt N+o(\sqrt N)$]. The lower and upper error terms need not have the same size to establish that asymptotic conclusion.
Back to article page
