19
$\begingroup$

Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My questions are:

Question 1: has this function been studied before? Any reference? It looks related to Sidon sets, but not quite the same.

Question 2: It is easy to see that $m(n)\geq 2\sqrt{n}-1$. Can we show that $m(n)\approx 2\sqrt{n}$ asymptotically? (see the comments on how to get to $2\sqrt{2n}$).

I found one similar question (for $\mathbb F_2^n$ instead of integers) here but could not find further useful references.

$\endgroup$
22
  • 3
    $\begingroup$ @GerryMyerson: I don't think so, if I understood your comment right. It would be hard to get things in the range $[2n-d...2n]$. $\endgroup$ Oct 19, 2019 at 21:47
  • 3
    $\begingroup$ Never mind, I miscalculated again. How about everything from zero to $d$, multiples of $d$ up to $n-d$, and everything from $n-d$ to $n$? That's $3\sqrt n$, asymptotically. $\endgroup$ Oct 20, 2019 at 3:12
  • 6
    $\begingroup$ Here are the values of $m(n)$ for $n \in\{1,\dots,50\}$: 2 ,3 ,4 ,4 ,5 ,5 ,6 ,6 ,7 ,7 ,8 ,8 ,8 ,9 ,9 ,9 ,10 ,10 ,10 ,10 ,11 ,11 ,12 ,12 ,12 ,12 ,12 ,13 ,13 ,13 ,14 ,13 ,14 ,14 ,14 ,14 ,15 ,15 ,15 ,15 ,16 ,16 ,16 ,16 ,16 ,16 ,17 ,17 ,17 ,17. It doesn't seem to be in the OEIS. $\endgroup$
    – RobPratt
    Oct 20, 2019 at 5:19
  • 5
    $\begingroup$ The term to google is additive basis, or maybe try additive basis for interval. $\endgroup$
    – Seva
    Oct 20, 2019 at 13:58
  • 3
    $\begingroup$ @Seva: I looked at some literature on additive bases, and my question can be translated to basis for $2n$ but lies inside $[n]$. Unfortunately no paper that I came across seemed to address this particular problem, and all the current records use elements in the interval $[n+1, 2n]$, which does not help immediately. Perhaps one needs to really study the techniques there. $\endgroup$ Oct 21, 2019 at 0:47

4 Answers 4

11
$\begingroup$

Let $S\subset [1,N]$ with $S+S=2N$. I will show that $S$ must have at least $(2.033 +o(1))\sqrt{N}$ elements for large $N$. The argument can certainly be improved, but I don't know what the right answer should be.

Assume that $N$ is large and that $|S| =O(\sqrt{N})$ (else we are done of course). Let $r(n)$ denote the number of ways of writing $n$ as $a+b$ with $a$ and $b$ in $S$. Apart from the cases $a=b$ which occur for at $O(\sqrt{N})$ values, we have $r(n)\ge 2$ for $n\le 2N$ (since $a+b$ and $b+a$ will be counted as two different solutions). As noted in the problem, we then have $$ 4N +O(\sqrt{N}) \le \sum_{n\le 2N} r(n) = |S|^2, $$ which gave the asymptotic bound $|S| \ge 2\sqrt{N}+O(1)$ that we now wish to improve.

Decompose $S$ into three sets $A$, $B$, $C$, where $A=S\cap[1,N/3)$, $B=S\cap[N/3,2N/3)$, and $C= S\cap[2N/3,N]$. Say $|A|=\alpha\sqrt{N}$, $|B|=\beta\sqrt{N}$ and $|C| =\gamma\sqrt{N}$, so that we know already that $\alpha+\beta+\gamma\ge 2+o(1)$.

Consider $A+A$. This must cover all numbers in $[1,N/3]$ and therefore we must have $$ |A|^2 \ge \sum_{n\le N/3} r(n) \ge 2N/3+ O(\sqrt{N}). $$ Therefore we must have $$ \alpha \ge \sqrt{2/3} +o(1). \tag{1} $$

Similarly $C+C$ must cover all elements in $[5N/3,2N]$ which leads to $$ \gamma \ge \sqrt{2/3}+ o(1). \tag{2} $$

Now consider $B+B$ and $A+C$. These sums are all in $[2N/3,4N/3]$ and therefore we obtain $$ \sum_{2N/3 \le n \le 4N/3} r(n) \ge |B|^2 + 2|A| |C| +O(\sqrt{N}) = (\beta^2+2\alpha\gamma+o(1)) N. $$ Therefore $$ |S|^2 =\sum_{n\le 2N} r(n) \ge \Big(\sum_{n< 2N/3} +\sum_{2N/3\le n\le 4N/3} +\sum_{4N/3<n \le 2N} \Big) r(n) $$ must be at least $$ \Big(\frac{8}{3} + \beta^2 + 2\alpha \gamma +o(1)\Big) N. \tag{3} $$

Put $\alpha+\gamma =2\sqrt{2/3}+\delta$, with $\delta>0$. Since both $\alpha$ and $\gamma$ must be $\ge \sqrt{2/3}+o(1)$ we must have $$ \alpha\gamma \ge \sqrt{2/3}(\sqrt{2/3}+\delta)+o(1) = \frac 23 +\sqrt{\frac 23}\delta +o(1). $$ If $\delta\ge 2-2\sqrt{2/3}$, then using this in (3) we would get $$ |S|^2 \ge \Big( 4 +2 \sqrt{2/3} \delta+o(1)\Big) N \ge 4.599N, $$ which is more than we claimed.

Suppose then that $\delta \le 2-2\sqrt{2/3}$, so that $\beta \ge 2-(\alpha+\gamma)=2-2\sqrt{2/3}-\delta (>0)$. Using this in (3) we find $$ |S|^2 \ge \Big( 4+ 2\sqrt{2/3} \delta + (2-2\sqrt{2/3}-\delta)^2 +o(1) \Big) N. $$ The right side is smallest for $\delta=0$, yielding $$ |S|^2 \ge (4+(2-2\sqrt{2/3})^2+o(1))N, $$ which gives $|S| \ge (2.0333\ldots +o(1))\sqrt{N}$.

$\endgroup$
2
  • $\begingroup$ Could you explain the fraction $8/3$ in (3)? (I can see $4/3$ $\endgroup$
    – Seva
    Oct 30, 2019 at 9:09
  • 1
    $\begingroup$ @Seva: Note that $r(n)$ is usually at least $2$. In the display preceding (3) the first and third sums have $2N/3$ elements each; giving a total of $4N/3$ terms, and now multiply this by $2$ (the usual size of $r(n)$). $\endgroup$
    – Lucia
    Oct 30, 2019 at 9:33
8
$\begingroup$

For a fixed $n$, you can solve the problem via integer linear programming. For $j \in [n]$, let binary decision variable $x_j$ indicate whether $j\in S$. For $0\le j_1\le j_2 \le n$, let binary decision variable $y_{j_1,j_2}$ indicate whether both $j_1$ and $j_2$ are in $S$. The problem is to minimize $\sum_j x_j$ subject to \begin{align} \sum_j y_{j,i-j} &\ge 1 &&\text{for $i \in [2n]$}\\ y_{j_1,j_2} &\le x_{j_1}\\ y_{j_1,j_2} &\le x_{j_2} \end{align}

I didn't try to find all optimal solutions, but here is one for each $n \le 50$:

 n  m optimal S
 1  2 {0,1}
 2  3 {0,1,2}
 3  4 {0,1,2,3}
 4  4 {0,1,3,4}
 5  5 {0,1,2,4,5}
 6  5 {0,1,3,5,6}
 7  6 {0,1,2,4,6,7}
 8  6 {0,1,3,5,7,8}
 9  7 {0,1,3,5,7,8,9}
10  7 {0,1,3,5,7,9,10}
11  8 {0,1,3,5,7,9,10,11}
12  8 {0,1,3,5,7,9,11,12}
13  8 {0,1,2,5,8,11,12,13}
14  9 {0,1,3,5,7,9,11,13,14}
15  9 {0,1,3,4,9,11,12,14,15}
16  9 {0,1,2,5,8,11,14,15,16}
17 10 {0,1,3,5,7,8,13,14,16,17}
18 10 {0,1,3,5,6,12,13,15,17,18}
19 10 {0,1,2,5,8,11,14,17,18,19}
20 10 {0,1,3,4,9,11,16,17,19,20}
21 11 {0,1,3,5,6,13,15,16,18,20,21}
22 11 {0,1,2,3,7,11,15,19,20,21,22}
23 12 {0,1,3,5,6,13,15,16,18,20,22,23}
24 12 {0,1,3,5,7,8,16,17,19,21,23,24}
25 12 {0,1,3,4,9,11,15,17,21,22,24,25}
26 12 {0,1,3,4,9,11,15,17,22,23,25,26}
27 12 {0,1,3,5,6,13,14,21,22,24,26,27}
28 13 {0,1,2,3,5,9,13,17,21,25,26,27,28}
29 13 {0,1,3,4,9,11,16,18,23,25,26,28,29}
30 13 {0,1,3,4,6,10,14,19,21,26,27,29,30}
31 14 {0,1,2,4,7,9,10,15,20,22,27,28,30,31}
32 13 {0,1,3,4,9,11,16,21,23,28,29,31,32}
33 14 {0,1,3,5,6,12,13,20,21,27,28,30,32,33}
34 14 {0,1,2,3,7,11,15,19,23,27,31,32,33,34}
35 14 {0,1,3,5,6,13,14,21,22,29,30,32,34,35}
36 14 {0,1,3,4,9,11,16,20,25,27,32,33,35,36}
37 15 {0,1,3,4,7,9,14,16,21,26,28,33,34,36,37}
38 15 {0,1,2,3,4,9,14,19,24,29,31,34,35,37,38}
39 15 {0,1,3,4,9,11,16,20,25,30,35,36,37,38,39}
40 15 {0,1,3,4,5,8,14,20,26,32,35,36,37,39,40}
41 16 {0,1,3,5,6,11,12,19,20,27,28,35,36,38,40,41}
42 16 {0,1,3,4,7,8,13,18,23,28,33,35,38,39,41,42}
43 16 {0,1,3,4,5,8,14,20,26,29,35,38,39,40,42,43}
44 16 {0,1,3,5,7,8,17,18,26,27,36,37,39,41,43,44}
45 16 {0,1,3,4,9,11,16,20,25,29,34,36,41,42,44,45}
46 16 {0,1,3,4,5,8,14,20,26,32,38,41,42,43,45,46}
47 17 {0,1,2,5,8,9,10,15,21,27,33,39,42,43,44,46,47}
48 17 {0,1,3,4,5,8,14,20,26,32,38,39,43,45,46,47,48}
49 17 {0,1,3,4,5,8,14,20,26,32,38,41,45,46,47,48,49}
50 17 {0,1,3,4,9,11,16,20,25,30,34,39,41,46,47,49,50}
$\endgroup$
3
  • 1
    $\begingroup$ Ah, that's clever. While you are at it, does the program tell you how many solutions for each $n$? $\endgroup$ Oct 20, 2019 at 6:06
  • 1
    $\begingroup$ After reading some literature I start to suspect that $\lim s(n)/\sqrt{n}$ might be larger than $2$. Is it possible to compute $s(100)$? Thanks. $\endgroup$ Oct 21, 2019 at 3:59
  • 1
    $\begingroup$ $m(100) \in [22,25]$. Best so far is $S= \{0,1,3,4,6,10,13,15,21,29,37,45,53,61,69,77,84,85,90,94,95,96,97,99,100\}$. $\endgroup$
    – RobPratt
    Oct 21, 2019 at 13:25
4
$\begingroup$

Short answer: Such a set $S$ is known as a restricted additive basis.


As observed in comments, the general term to search for is [finite] additive basis: a finite set $S \subset \mathbb{N}$ such that $S+S \supseteq [2n]$. Another term is postage stamp problem (not to be confused with the Frobenius postage stamp problem which is different).

The extra condition that $S \subseteq [n]$ makes this the restricted postage stamp problem and the solutions are restricted additive bases. ("Restricted" means that the elements are restricted to be in $[n]$.)

It is then (almost) equivalent to ask

  1. given $k$, what is the largest $n$ ...
  2. given $n$, what is the smallest $k$ ...

such that there exists a restricted additive basis of $k$ elements for the interval $[2n]$. More about that "almost" at the end of this answer. Let us write $n(k)$ for the largest $n$ when $k$ is given, and $k(n)$ for the smallest $k$ when $n$ is given.

Here the question asks for $k(n)$. For $n(k)$ this is OEIS A006638, where currently the largest entry is $a(47)=734$ by yours truly (2015). Some translation needed: That "47" counts only the nonzero elements, so in fact there are 48 elements; that "734" means the target interval is $[2n]=[734]$, so in our current notation it becomes $n(48)=367$, and $k(367)=48$.


To the specific questions:

Q1. The OEIS entry gives some pointers to literature. The oldest reference that I know is H. Rohrbach, "Ein Beitrag zur additiven Zahlentheorie", Math. Z., 42 (1937), 1-30, which studies both the unrestricted and the restricted versions. Symmetric bases have also been studied, see for example S. Mossige, "Algorithms for computing the h-range of the postage stamp problem", Math. Comp. 36 (1981), 575–582.

Q2. About asymptotics: No, one cannot achieve $k(n) \sim 2\sqrt{n}$ asymptotically. Gang Yu, "Upper bounds for finite additive 2-bases", Proc. AMS 137 (2009), 11-18, shows that

$$\limsup_{n \to \infty} \frac{n}{k_r(n)^2} \le 0.419822,$$

where $k_r(n)$ is the smallest size of a restricted basis for $[n]$. I believe this is currently the best lower bound for $k_r$. Translated to our notation (with target interval $[2n]$) this means the factor in front of $\sqrt n$ is asymptotically at least $2.18264$.


And about the "almost": Generally $k(n)$ increases as $n$ increases, but there are some known cases where $k(n)$ suddenly steps down. One of them was also noticed in the comments above: "What the heck is going on at n=31?". Indeed we have $k(31)=14$ but $k(32)=13$; $k(51)=18$ but $k(52)=17$; and $k(57)=19$ but $k(58)=18$. See Table 5 in this 2018 paper by me and coauthors, where the corresponding problem is studied in two dimensions.

$\endgroup$
3
$\begingroup$

Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.

In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.

Many values of $n$ (but not all) seem to have optimal solutions with this structure:

Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d-1\leq i \leq d+p.$

This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$ In some cases there are $3$ values of $d$ which work.


$m(23)=12$ and one solution is $S=\{0,1,3,5,6,13,15,16,18,20,22,23\}$

There are $22$ symmetric solutions. The lower halves are

$ \left\{ 0,1,2,3,4,9 \right\} , \left\{ 0,1,2,3,6,10 \right\} , \left\{ 0,1,2,3,7,10 \right\} , \left\{ 0,1,2,3,7,11 \right\} , \mathbf{\left\{ 0,1,2,4,5,11 \right\}} , \left\{ 0,1,2,4,6,9 \right\} , \left\{ 0,1,2,4,7,10 \right\} , \left\{ 0,1,2,5,6,8 \right\} , \left\{ 0,1,2,5,7,10 \right\} , \left\{ 0,1,2,5,8,10 \right\} , \left\{ 0,1,2,5,8,11 \right\} , \mathbf{\left\{ 0,1,3,4,5,11 \right\} , \left\{ 0,1,3,4,6,11 \right\} , \left\{ 0,1,3,4,7,9 \right\} , \left\{ 0,1,3,4,8,9 \right\} , \left\{ 0,1,3,4,8,10 \right\} , \left\{ 0,1,3,4,9,10 \right\} , \left\{ 0,1,3,4,9,11 \right\} , \left\{ 0,1,3,5,6,8 \right\} , \left\{ 0,1,3,5,6,10 \right\} , \left\{ 0,1,3,5,6,11 \right\} , \left\{ 0,1,3,5,7,8 \right\}} $

The values of $d$ represented are $3,4,5.$ The ones in bold merit further perusal. They do not fully fit the scheme described as there are jumps greater than the relevant $d$.


$m(20)=10$ and the given solution $S=\{0,1,3,4,9,11,16,17,19,20\}$ is symmetric.

There are no solutions which fit the scheme above as $$6+\lceil \frac{22}3 \rceil-3=8+\lceil \frac{22}4 \rceil-3=11.$$


$m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution with $d=4$

$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$

and also this one with $d=5$

$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$ In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$


For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$

  • $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
  • $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$

One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$

A symmetric solution is $$S =\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$

$\endgroup$
3
  • $\begingroup$ @LSpice You are right of course. $\endgroup$ Oct 20, 2019 at 18:34
  • $\begingroup$ I guess your last two bullets are instead $d=4$ and $d=5$. $\endgroup$
    – RobPratt
    Oct 20, 2019 at 19:27
  • 1
    $\begingroup$ For $n \le 50$, forcing symmetry yields the same optimal values, except $m(n)+1$ for $n\in \{5,9,15,21,29,37,39,47,49\}$, which are exactly the cases where both $n$ and $m(n)$ are odd. $\endgroup$
    – RobPratt
    Oct 22, 2019 at 3:13

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.