An extremal combinatorics problem Given two integers integers $0<b<p$ and a real $\alpha\in(0,1)$ what is the largest $m$ we have such that in the interval $(p^\alpha,p-p^\alpha)$ there are $m$ integers $a_1<\dots<a_m$ such that


*

*$a_i-a_j\neq a_{i'}-a_{j'}$ holds if $i\neq i'$ or $j\neq j'$ or both.

*$\min_{1\leq i<j\leq m}|a_i-a_j|>b$
holds?
 A: 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\}$. 
A: (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)}$ 
