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

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).

• you mean $n$ consecutive numbers from 1 to $n$, or $n$ numbers from $-n/2$ to $n/2$ also count? – Fedor Petrov Feb 11 '17 at 11:53
• Any interval [a,a+n) is suitable. – Taras Banakh Feb 11 '17 at 17:12
• It seems that Question 1 has positive answer, so only Question 2 remains open. – Taras Banakh Feb 12 '17 at 23:32

## 1 Answer

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

• strictly speaking, if the difference set contains $a+1,\dots,a+n$ for $a>1$, this does not imply that it contains $[-n/2,n/2]$. But in this case $|A-A|\geqslant 2n+1$ and $|A|\geqslant \sqrt{(2+o(1))n}$. – Fedor Petrov Feb 13 '17 at 9:20
• @Lucia Thank you for the solution. But then the problem of evaluation of the smallest constant arizes. Is it $\sqrt{2}$? – Taras Banakh Feb 13 '17 at 22:42
• Indeed! But, not my problem (for the moment at least). :) – Lucia Feb 13 '17 at 23:46