2
$\begingroup$

Let $n\in\mathbb N$.

Given a set $S\subset\mathbb N$, let $\Delta(S) = \{a-b\mid a,b\in S\}$ denote its set of differences.

I'm interested in finding a small set $S_n$ such that $\{1,\ldots,n\}\subseteq\Delta(S_n)$.

For example, if $n=8$ we can use

$$S_8 =\{1,2,4,8,9\}. $$

How can we construct a small $S_n$ efficiently? (Efficiently should ideally be $O(|S_n|)$ time, but any $o(n)$ time would be interesting.)

How does the smallest $|S_n|$ grow as a function of $n$? (As a guess, I'd like to say $|S_n|=O(\sqrt n)$ should be possible?)

$\endgroup$

1 Answer 1

4
$\begingroup$

One example of such a set is $S_n = \{0,1,2,\dots,k\} \cup \{k,2k,3k,\dots,k^2\}$ where $k=\lceil \sqrt{n} \rceil$. It follows that $|S_n|=O(\sqrt{n})$, and $S_n$ can be constructed in $O(\sqrt{n})$ time.

See also https://math.stackexchange.com/q/168079/14578.

$\endgroup$
4
  • $\begingroup$ This seems to give an easy 2-approx for $|S_n|$. Any thoughts on whether this can be improved? $\endgroup$
    – M A
    Sep 6 at 7:48
  • $\begingroup$ @MA, If you want to know how small $|S_n|$ can be, that sounds like a good question for Math.SE. I'm not sure that it is a matter of computer science. $\endgroup$
    – D.W.
    Sep 6 at 8:15
  • $\begingroup$ Isn't finding an optimal solution (or a $c$-approx. for $c<2$) a matter of computer science? I asked here because I am interested in something I can program, I'm not sure that Math.SE. is the right place for that. $\endgroup$
    – M A
    Sep 6 at 10:08
  • $\begingroup$ @MA, yes, you are right. If it were me, I would ask first on Math.SE, as many constructions are easily implementable and difference sets are well studied in mathematics, but it is up to you. In any case, this is a new question and should be asked separately. $\endgroup$
    – D.W.
    Sep 7 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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