What is the smallest cardinality of a set A whose difference A-A contains $n$ consequtive integer numbers?

Question

Problem. What is the smallest cardinality $d(n)$ of a set $A$ of integer numbers such that the difference set $A-A=\{a-b:a,b\in A\}$ contains $n$ consequtive integer numbers?

It can be shown that $(1+\sqrt{4n-3})/2\le d(n)\le \frac32p(\sqrt{n})=\frac32\sqrt{n}+O(n^{21/80})$ where $p(x)$ is the smallest prime number greater or equal to $x$.

These bounds suggest the following more precise questions:

Question 1. Is $d(n)\le (\sqrt{2}+o(1))\sqrt{n}$?

Question 2. Is $d(n)=(1+o(1))\sqrt{n}$?

Comment. Looking at the literature, I discovered that this question has been studied by classics: Erdos, Gal (1948), Redey, Renyi (1949), Leech (1956), Whichmann (1963), Golay (1972). More information (in the context of perfect rulers) can be found here. Wichmann proved that for every $r,s\ge 0$ there exists a set $A\subset \mathbb N\cup\{0\}$ of cardinality $n=4r+s+3$ such that $A-A=[-L,L]$ where $L=4r(r+s+2)+3(s+1)$. This gives an affirmative answer $d(n)\le \sqrt{2n}$ to Question 1. On the other hand, much earlier Redei and Renyi (1949) proved the lower and upper bounds $1+\frac2{3\pi}< \lim_{n\to\infty}\frac{d(2n+1)^2}{2n}=\inf_{n\in\mathbb N}\frac{d(2n+1)^2}{2n}<\frac{4}3$. These lower and upper bound were improved a bit by Leech (1956) and Golay (1972). This negatively answers my Question 2 (and completes the answer given by Lucia).

Answer 1

Since you say that only Question 2 is open, I'll only address that. The answer is no, and $d(n)$ must be at least $(1+\delta)\sqrt{n}$ for some positive $\delta$. I won't compute this, but it shouldn't be too hard to find some bound.

Suppose for contradiction that $|A|\le (1+\delta) \sqrt{n}$. Since the difference set is symmetric about $0$, we might as well assume that the consecutive numbers hit in the difference set are from $[-n/2,n/2]$. For any number $k$ let $r(k)$ denote the number of ways of writing $k$ as $a-b$ with $a$, $b$ in $A$. Now $$ \sum_{k} r(k) = |A|^2, $$ and by hypothesis $r(k) \ge 1$ for $k \in [-n/2,n/2]$. Therefore $$ \sum_{k\notin [-n/2,n/2]} r(n) + \sum_{k \in [-n/2,n/2]} (r(n)-1) \ll \delta n. $$

Note also that there must be some interval of length $n/2$ such that almost the full density (say $1-10\sqrt{\delta}$) of $A$ is contained in that interval. Else there would be many differences of size larger than $n/2$, contradicting the estimate above.

Set $$ {\hat A}(\ell) = \sum_{a\in A} e(a\ell/n). $$ Then for $\ell \neq 0 \mod n$, using that $\sum_{k \in [-n/2,n/2]} e(k\ell/n) = O(1)$, $$ |{\hat A}(\ell)|^2 = \sum_{k} r(k) e(k\ell/n) \le \sum_{k \notin [-n/2,n/2]} r(k) + \sum_{k \in [-n/2,n/2]} (r(k)-1) +O(1) \ll \delta n. $$

If $\delta$ is small enough, then what we have essentially shown is that the elements of $a$ are essentially uniformly distributed $\mod n$ (the smaller $\delta$ is, the better the equidistribution). But that is not possible, because we observed earlier that most of $A$ must fit into an interval of size $n/2$.