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?

Improve this question
$\endgroup$
2
  • 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, 2019 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$
    – Turbo
    Jan 11, 2019 at 6:03

2 Answers 2

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

Improve this answer
$\endgroup$
8
  • $\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, 2019 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, 2019 at 9:17
  • $\begingroup$ but for this $b$ should be greater than $q$ (or like that) $\endgroup$
    – Fedor Petrov
    Jan 11, 2019 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, 2019 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, 2019 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)}$

Improve this answer
$\endgroup$
8
  • $\begingroup$ Do you think there is reason to believe $b=o(L^{2/3})$ and $|S|=\Omega(\sqrt{L})$ is possible? $\endgroup$
    – Turbo
    Jan 17, 2019 at 6:18
  • $\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
    Jan 17, 2019 at 7:49
  • $\begingroup$ $b=\omega(L^{2/3-\epsilon})$ at any fixed $\epsilon$? $\endgroup$
    – Turbo
    Jan 17, 2019 at 7:51
  • $\begingroup$ @Freeman: What is that $\omega$ notation? $\endgroup$
    – Seva
    Jan 17, 2019 at 7:57
  • 1
    $\begingroup$ @Freeman: I found it very technical and difficult to understand. If you want people to look at it, you should find a way to restate it in a clear, non-technical way, avoiding heavy notation and keeping the number of parameters to a minimum. $\endgroup$
    – Seva
    Jan 17, 2019 at 9:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .