Minimum number of integers $a_1,....,a_m$ needed to express $2,...,n$ as $a_i + a_j$

Question

I am interested in the following problem. An arbitrary integer $n \geq 2$ is given. Find the minimum integer $m \geq 1$ such that there exist integers $0\lt a_1\lt a_2\lt \cdots \lt a_m$ satisfying the following property: for every integer $k \in \{2,\ldots,n\}$ there exist $i,j \in \{1,\ldots,m\}$ such that $k = a_i + a_j$.

To illustrate, let $n=5$. We are forced to take $a_1=1$, so that $2=a_1+a_1$. Then, we are forced to take $a_2=2$, so that $3 = a_1+a_2$. We get $4 = a_2+a_2$ ``for free''. Finally, we need to take $a_3=3$ to get $5=a_2+a_3$ or $a_3=4$ to get $5=a_1+a_3$. In any case, we see that $n=5$ corresponds to $m=3$.

My question: what is $m$ for arbitrary $n$? And if you do not know the answer: can you provide a non-trivial lower bound for $m$? Or do you know a problem which is equivalent or very similar to this one?

Answer 1

One strategy is to have your set $\{1,2,3,\ldots k,2k,3k,4k\ldots\}$ If you go up to $k^2$ you can get all sums up to $k^2+k$ with $2k$ numbers in the set. It means for numbers up to $n$ you choose $k$ so that $$k^2+k=n\\k=\frac 12(-1+\sqrt{1+4n})\approx \sqrt n\\m \approx 2\sqrt n$$ I don't know if this is optimal, but it is a target for others to shoot at.

Added: For a lower bound, note that there are at most $\frac 12m(m+1)$ sums possible. We then need $$\frac 12m(m+1) \ge n\\ (m+\frac 12)^2 \ge 2n+\frac 14\\ m \ge \sqrt{2n+\frac 14}-\frac 12$$ which shows the above is close. It is a factor $\sqrt 2$ higher because some of the sums match.

Answer 2

This is one variant of the postage stamp problem. OEIS sequence A001212 gives several values and references.

Answer 3

This is indeed a variant of the postage stamp problem, as Rob Pratt observed.

But let's see exactly how it is a variant. In fact, let us inspect three variants: Post($n,k$) the OEIS A001212 "postage stamp" variant, Add($n,k$) the one commonly found in the literature of "additive bases", and MSE($n,k$) the one asked here.

We write $A+B$ for the sumset $\{a+b \;:\; a\!\in\!A, \, b\!\in\!B\}$, and $A+c=A+\{c\}$. We write $[a,b]$ for the integer interval $\{a, a+1, \ldots, b\}$.

The variants.

• Post($n,m$): Given integer $n$, find a set of $m$ positive integers $A = \{a_1,\ldots,a_m\}$ such that $A \cup (A+A)$ covers $[1,n]$. This is called "postage stamp problem" because every postage fare from 1 to $n$ must be payable with one or two stamps (cannot fit more in an envelope).

• Add($n,m$): Given integer $n$, find a set of $m$ nonnegative integers $A$ such that $A+A$ covers $[0,n]$.

• MSE($n,m$): Given integer $n$, find a set of $m$ positive integers $A$ such that $A+A$ covers $[2,n]$.

The equivalence.

1. If $A$ is a solution for Post($n,m$), then $A' = \{0\} \cup A$ is a solution for Add($n,m+1$). You just augment a zero element (so $m$ increases by one) and now $A'+A' = \{0\} \cup (A+0) \cup (A+A) = \{0\} \cup A \cup (A+A) \supseteq \{0\} \cup [1,n] = [0,n]$.

2. If $A'$ is a solution for Add($n,m$), then $A'' = A'+1$ is a solution for MSE($n+2, m$). You just increase every element by 1, so the pairwise sums increase by two; if the original sums covered $[0,n]$, then the new sums cover $[2,n+2]$ as required.

3. It is not difficult to see that both transformations work in reverse also. So in fact minimal solutions to any one variant correspond to minimal solutions of the other variants.

A concrete example.

• Post(12,4) has a solution $A=\{1,3,5,6\}$, with all fares in $[1,12]$ payable; $1$ with one stamp, $2=1+1$ with two stamps, $3$ with one stamp, $4=1+3$ with two stamps and so on, up to $12=6+6$ with two stamps.

• Thus Add(12,5) has a solution $A'=\{0\} \cup A = \{0,1,3,5,6\}$, with $A'+A' \supseteq [0,12]$.

• Thus MSE(14,5) has a solution $A''=A'+1 = \{1,2,4,6,7\}$, with $A''+A'' \supseteq [2,14]$.

Note that Post solutions are forced to start with $1$ (no other way to pay the $1$ fare), equivalently Add solutions are forced to start with $0,1$, and MSE solutions are forced to start with $1,2$, as the original poster observed.

To the particular questions.

What is m for arbitrary n?

Not known in general, but from OEIS A001212 you get values up to $n=214$ and $m=25$ (observing the needed transformations of both parameters).

Can you provide a non-trivial lower bound for m?

Yes, the literature on additive bases contains several nontrivial, successively improved bounds. Usually they are stated as upper bounds on $n$ when $m$ is given, but that translates to a lower bound on $m$ when $n$ is given. See for example:

Yu, Gang, A new upper bound for finite additive (h)-bases, J. Number Theory 156, 95-104 (2015). ZBL1395.11028.