4
$\begingroup$

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

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

  2. $\min_{1\leq i<j\leq m}|a_i-a_j|>b$ holds?

$\endgroup$
  • 1
    $\begingroup$ Instead of the interval $(p^\alpha,p-p^{\alpha})$ you may consider any interval containing the same number of integers (by shifting). Sets satisfying 1) are called Sidon sets and a lot if known about them. Is there asymptotic relation between $b$ and $p-2p^\alpha$ which you are mostly interested in? $\endgroup$ – Fedor Petrov Jan 11 at 5:26
  • $\begingroup$ @FedorPetrov $b\asymp p^\beta$ holds and I am interested in $0<\beta<\alpha$, $\beta=\alpha$ and $\alpha<\beta<1$ regime. $\endgroup$ – Freeman. Jan 11 at 6:03
4
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ I start this routine verification and have troubles: if $dn+\nu(n)+dm+\nu(m)=dn_1+\nu(n_1)+dm_1+\nu(m_1)$, we get $\nu(n)+\nu(m)\equiv \nu(n_1)+\nu(m_1) \pmod{d}$, while I would prefer to have it modulo $q-1$... $\endgroup$ – Fedor Petrov Jan 11 at 9:13
  • $\begingroup$ @FedorPetrov: well, the only thing we really need is that the largest possible value of $\nu$ does not exceed $d/2$. Maybe, some parameters in my answer need to be adjusted; I will take care of it later today. $\endgroup$ – Seva Jan 11 at 9:17
  • $\begingroup$ but for this $b$ should be greater than $q$ (or like that) $\endgroup$ – Fedor Petrov Jan 11 at 9:19
  • $\begingroup$ @FedorPetrov: I do not think so; we just have to define $d:=q-1+\max\{b,q-1\}$ instead of $d:=b+q-1$. Anyway, I have to leave now, will look closer later. $\endgroup$ – Seva Jan 11 at 9:23
  • $\begingroup$ with such value of $d$ of course, but it yields sometimes the worse estimate for the diameter of $S$ $\endgroup$ – Fedor Petrov Jan 11 at 9:41
2
$\begingroup$

(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)}$

$\endgroup$
  • $\begingroup$ Do you think there is reason to believe $b=o(L^{2/3})$ and $|S|=\Omega(\sqrt{L})$ is possible? $\endgroup$ – Freeman. yesterday
  • $\begingroup$ @Freeman: As you state it, this is certainly possible, just take $b=1$. I guess this is not what you really had in mind. $\endgroup$ – Seva yesterday
  • $\begingroup$ $b=\omega(L^{2/3-\epsilon})$ at any fixed $\epsilon$? $\endgroup$ – Freeman. yesterday
  • $\begingroup$ @Freeman: What is that $\omega$ notation? $\endgroup$ – Seva yesterday
  • $\begingroup$ Please take notation $\Omega$. $\endgroup$ – Freeman. yesterday

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.