The $\ell$-th element of a Sidon set in $\mathbb Z_m$

Before we begin, a Sidon set is a set $\mathcal S\subset \mathbb N$ with no non-trivial solutions to the equation $a+b=c+d$ (trivial solutions being those satisfying $\{a,b\}=\{c,d\}$). A Sidon subset $A\subset [n]:=\{1,2,\dots , n\}$ is called dense if $\left\lvert A\right\rvert = \max \left\lvert S\right\rvert$ where the maximum is taken over all Sidon subsets of $[n]$. For a brief introduction to some of the work done in the field, see the first two sections of our paper. That being said, for all practical purposes of this particular post, it is enough to think of Sidon sets as sets with a certain property.

Recently I co-authored Prof. R. Balasubramanian in a work on Sidon sets (which has now been accepted in Journal of Number Theory) where we proved that if $A = \{a_1< a_2< \dots <a_{\left\lvert A\right\rvert}\}\subset [n]$ be a dense Sidon set with $|A|=n^{1/2}-L^\prime$, then

$$a_m = m\cdot n^{1/2} + \mathcal O\left( n^{7/8}\right) + \mathcal O\left(L^{1/2}\cdot n^{3/4}\right)$$

where $L=\max\{0,L^\prime\}$. This helped us to provide easier derivations of results previously also achieved by Ding (see this and this).

The main ingredient in our proof is a theorem due to Cilleruelo. Very informally, the theorem says that if we have a dense Sidon set $\mathcal S \subset [n]$ and if we choose an interval $I\subset [n]$ of length $m$, then $I$ will contain about these many elements of $\mathcal S$. In our proof, we specifically put $I=[1,a_m]$ and this gave us an asymptotic estimate for $a_m$.

It was only much after the paper was uploaded that it came to my notice that an analogue of Cilleruelo's theorem also exists for Sidon sets in $\mathbb Z_m$, due to Tomasz Schoen. This means that our proof technique can also achieve an analogous result for Sidon sets in $\mathbb Z_m$. And (due to technical reasons), this time the calculations will be easier than before. This is what I will show here.

Theorem : Let $A\subset \mathbb Z_m$ be a dense Sidon set with $|A|=m^{1/2}+O(1)$. Then

$$a_\ell = \ell\cdot m^{1/2} + \mathcal O\left( m^{3/4} \ln m\right)$$

where $a_\ell$ is the $\ell$-th element of $A$ (in increasing order).

Proof : Take Theorem 1 from Schoen's paper and put

$$\mathscr I = \{1,2,\dots , a_\ell\}$$

so that (by definition) $\left\lvert \mathscr I\right\rvert = a_\ell$ and $\left\lvert A\cap \mathscr I\right\rvert = \ell$. So, by Schoen's theorem,

$$\left\lvert \ell - \left\lvert A\right\rvert \cdot \frac{a_\ell}{m}\right\rvert = \mathcal O \left(\left\lvert A\right\rvert^{1/2} \ln m\right)$$

and hence

$$\frac{a_\ell}{\sqrt{m}} = \ell + \mathcal O\left(m^{1/4}\ln m\right)$$

thus giving

$$a_\ell = \ell \sqrt m + \mathcal O\left(m^{3/4}\ln m\right)$$

hence completing the proof.

Finding asymptotic form for $\sum_{a\in \left\lvert A\right\rvert} a^k$ (as done in our original paper) is now only a matter of computaion and is left as an exercise for the reader. It should be noted (as was also done in the original paper) that this theorem is technically a valid formula for all $\ell$, but it's only useful as an asymptotic formula when $\ell$ is close to $\sqrt m$, more precisely when $\ell > m^{1/4}\ln m$.