11
$\begingroup$

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

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

1 Answer 1

8
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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}$. $\endgroup$ Feb 13, 2017 at 9:20
  • $\begingroup$ @Lucia Thank you for the solution. But then the problem of evaluation of the smallest constant arizes. Is it $\sqrt{2}$? $\endgroup$ Feb 13, 2017 at 22:42
  • 2
    $\begingroup$ Indeed! But, not my problem (for the moment at least). :) $\endgroup$
    – Lucia
    Feb 13, 2017 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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