15
$\begingroup$

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An alternative way to write this condition is to ask that $\{1, \ldots, N\} \subseteq A-A$.) For example, for $N=9$, we could take $A=\{-3, -2, -1, 0, 3, 6\}$, which achieves $|A|=6$.

It easy to see that $|A| \geq \sqrt{2N}$, as at most $\binom {|A|} 2 \leq |A|^2/2$ differences can be formed from the elements of $A$. I can also construct suitable sets $A$ with $|A| = 2 \sqrt N$.

Is the lower bound $\sqrt{2N}$ asymptotically correct? If not, what is the correct lower bound?

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ Try Golomb rulers. $\endgroup$
    – The Masked Avenger
    Commented Jan 8, 2015 at 8:15
  • $\begingroup$ What does the phrase naively prove mean? Does it mean prove? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jan 8, 2015 at 9:27
  • 2
    $\begingroup$ @TheMaskedAvenger No perfect Golomb ruler of length larger than $6$ exists, though. So, essentially $\{0,1\}$, $\{0,1,3\}$, and $\{0,1,4,6\}$ are the only ones that meet the bound $\binom{\vert A\vert}{2} \geq N$ with equality. Completeness is required for OP's purpose. $\endgroup$
    – Yuichiro Fujiwara
    Commented Jan 8, 2015 at 13:16
  • 3
    $\begingroup$ Suppose $N = k^2 - 1$. Consider $A = \{1 , \ldots , k\} \cup \{2k , 3k , \ldots , (k-1)k , k^2\}$. Then $A-A$ contains $\{1, \ldots , N\}$ and $|A| \sim 2 \sqrt{N}$. With sumset replacing difference set, see "a new upper bound for finite additive bases" by Gunturk and Nathanson. $\endgroup$
    – George Shakan
    Commented Jan 8, 2015 at 15:32
  • 1
    $\begingroup$ Allowing negative numbers is unimportant because you can translate $A$. $\endgroup$
    – Douglas Zare
    Commented Jan 8, 2015 at 16:02

1 Answer 1

Reset to default
10
$\begingroup$

These are not Golomb rulers, but difference bases. The contrast is that Golomb rulers are a packing problem (differences must be distinct, but can be as sparse as you like), and difference bases are a covering problem (differences must cover an interval, but can overlap as much as you like).

Difference bases have been studied at least from 1948, and it seems most of the research is in asymptotic bounds. In fact the list of known concrete values is conspicuously short: OEIS A239308 lists values up to $a(37)=10$, indicating a basis of $10$ elements whose differences cover $[1,37]$. For $N=9$ one can take $A=\{0, 1, 4, 7, 9\}$, achieving $|A|=5$.

The current question asks about lower bounds on $|A|$ with respect to $\sqrt{N}$.

Answer: The proposed bound $\sqrt{2N}$ is not tight. I think the first nontrivial lower bound was $(1.5570\ldots)\sqrt{N}$ by Rédei and Rényi in 1948 (cited by Erdős and Gál; I haven't seen the original). Leech (1956) improved it to $(1.5602\ldots)\sqrt{N}$. Recently Bernshteyn and Tait (2019) showed that Leech's bound could be improved further (at least "by $\epsilon$") but they did not explicitly show how much.

Further note: A similar MO question is here. In that question, it is required that the differences cover $N$ consecutive integers (not necessarily $[1,N]$). But note that if $[1,N]$ is covered by $A-A$, then in fact $2N+1$ consecutive integers $[-N,N]$ are covered, so the problems are very closely linked. (See also Fedor Petrov's comment there.)

Bibliography

Erdős, Pál; Gál, S. A., On the representation of $1,2,\ldots,N$ by differences, Proc. Akad. Wet. Amsterdam 51, 1155-1158 (1948). ZBL0032.01302.

Leech, John, On the representation of $1, 2,\ldots, n$ by differences, J. Lond. Math. Soc. 31, 160-169 (1956). ZBL0072.03401.

Bernshteyn, Anton; Tait, Michael, Improved lower bound for difference bases, J. Number Theory 205, 50-58 (2019). ZBL07101901.

Improve this answer
$\endgroup$

You must log in to answer this question.

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