= Solution
We use the <Bose-Chowla Sidon construction>, deriving its difference property explicitly. Let $p$ be an odd prime and choose a generator $\theta$ of the <multiplicative group of a finite field> of the quadratic <finite field extension> $\mathbb F_{p^2}$. Such a generator cannot belong to $\mathbb F_p$, so $1,\theta$ are linearly independent over the prime field. For each $t\in\mathbb F_p$, the nonzero field element $\theta+t$ has a unique exponent $a_t$ modulo $p^2-1$, with $\theta^{a_t}=\theta+t$. The $p$ exponents are distinct.
Suppose $a_s-a_t=a_u-a_v$ in the <cyclic group>. Multiplying the corresponding field elements gives
$$
(\theta+s)(\theta+v)=(\theta+u)(\theta+t).
$$
Subtract the common $\theta^2$ term. Linear independence of $1,\theta$ gives $s+v=u+t$ and $sv=ut$. Thus the two unordered pairs are the roots of the same monic <quadratic polynomial>, so $\{s,v\}=\{u,t\}$. Either $s=u,v=t$, giving the same ordered difference, or $s=t,v=u$, giving two zero differences. This is exactly the <Sidon set> property.
Choose the integer representatives in $\{1,\ldots,p^2-1\}$. Equality of integer differences implies equality modulo $p^2-1$, so their Sidon property persists in the integers. Now apply the given prime-gap hypothesis at $x=\sqrt N$ to get $\sqrt N-N^{3/8}\leq p\leq\sqrt N$ for large $N$. The representatives fit inside $\{1,\ldots,N\}$, because $p^2-1\leq N$, and their <cardinality> is
$$
\boxed{|A|=p\geq\sqrt N-N^{3/8}=\sqrt N-o(\sqrt N).}
$$
Only the supplied short-interval prime existence and the elementary structure of a finite field are used.
Back to article page
