An extremal combinatorics problem

Taking Fedor Petrov's observation a little further, I believe the right question to ask is as follows: $$ \text{What is the largest size of a $b$-separated Sidon set in the interval $[0,L]$?} $$ Here "$b$-separated" means that the difference between any two consecutive elements of the set is at least $b+1$.

Clearly, one cannot find in $[0,L]$ a $b$-separated set of size larger than $L/b+1$; on the other hand, taking a large Sidon set in $[0,L/(b+1)]$ and dilating it by the factor $b+1$, you can get a $b$-separated Sidon set in $[0,L]$ of size $(1+o(1))\sqrt{L/(b+1)}$.

In general, the answer will depend heavily on the relation between $L$ and $b$. If $b$ is small as compared to $L$ (say, $b<\sqrt{L/2}$), then you can find a $b$-separated Sidon set $S\subset[0,L]$ of size about $\sqrt{L/2}$, as follows.

Let $q$ be a prime satisfying $2q^2\le L$ (this is the size of our set $S$, so we want to choose $q$ as large as possible subject to this condition). Fix a primitive root $g$ modulo $q$, and set $$ S := \{2qn+\nu(n)\colon 1\le n\le q-1 \}, $$ where $\nu(n)$ is the integer in the range $[0,q-2]$ such that $g^{\nu(n)}\equiv n\pmod q$.

Since $2q(n+1)>(2qn+q-2)+b$ (as it follows from $q\approx\sqrt{L/2}>b$), the set $S$ is $b$-separated.

To see that $S$ is Sidon, notice that $$ (2qn_1+\nu(n_1))+(2qn_2+\nu(n_2)) = (2qn_3+\nu(n_3)) + (2qn_4+\nu(n_4)) $$ yields $n_1+n_2=n_3+n_4$, leading to $\nu(n_1)+\nu(n_2)=\nu(n_3)+\nu(n_4)$ and, consequently, to $n_1n_2\equiv n_3n_4\pmod q$. Thus, $$ n_1+n_2 =n_3+n_4 $$ and $$ n_1n_2 \equiv n_3n_4\pmod q, $$ as a result of which $\{n_1,n_2\}=\{n_3,n_4\}$.


(This answer is totally different from the one I posted several days ago, so I prefer to post it separately and not as a sort of an edit / appendix.)


It is well known that the largest Sidon subset of the interval $[0,L]$ has size $(1+o(1))\sqrt L$; see, for instance this survey by O'Bryant. Remarkably, if $b=o(\sqrt L)$, then you can find $b$-separated Sidon sets in $[0,L]$ of the same size $(1+o(1))\sqrt L$; indeed, for any $b$, there is a $b$-separated Sidon set in $[0,L]$ of size at least $(1+o(1))\sqrt L-b$.

To see this, start with your favorite Sidon set $S\subset[0,L]$ (which, I expect, has size $|S|=(1+o(1))\sqrt L$). There is at most one pair of elements in $S$ at the distance $1$; remove one of them from $S$ and repeat the procedure with the distances $2,3,\dotsc,b$. You will have to remove $b$ elements at most, ending up with a $b$-separated subset of $S$ of size at least $|S|-b$.

Since any $b$-separated set in $[0,L]$ has size at most $L/(b+1)+1$, one cannot expect to have a lower bound of the order of magnitude $\sqrt L$ if $b$ is large as compared to $\sqrt L$. For a weaker bound, you can take a Sidon set $[0,L/(b+1)]$ and dilate it by the factor $b+1$; this way you get a $b$-separated Sidon set in $[0,L]$ of size $(1+o(1))\sqrt{L/(b+1)}$