# An extremal combinatorics problem

Given two integers integers $$0 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 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 ib$$ holds?

• 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? Jan 11, 2019 at 5:26
• @FedorPetrov $b\asymp p^\beta$ holds and I am interested in $0<\beta<\alpha$, $\beta=\alpha$ and $\alpha<\beta<1$ regime. Jan 11, 2019 at 6:03

## 2 Answers

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

• 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$... Jan 11, 2019 at 9:13
• @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.
– Seva
Jan 11, 2019 at 9:17
• but for this $b$ should be greater than $q$ (or like that) Jan 11, 2019 at 9:19
• @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.
– Seva
Jan 11, 2019 at 9:23
• with such value of $d$ of course, but it yields sometimes the worse estimate for the diameter of $S$ Jan 11, 2019 at 9:41

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

• Do you think there is reason to believe $b=o(L^{2/3})$ and $|S|=\Omega(\sqrt{L})$ is possible? Jan 17, 2019 at 6:18
• @Freeman: As you state it, this is certainly possible, just take $b=1$. I guess this is not what you really had in mind.
– Seva
Jan 17, 2019 at 7:49
• $b=\omega(L^{2/3-\epsilon})$ at any fixed $\epsilon$? Jan 17, 2019 at 7:51
• @Freeman: What is that $\omega$ notation?
– Seva
Jan 17, 2019 at 7:57
• @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.
– Seva
Jan 17, 2019 at 9:45