# $B_k[1]$ sets with smallest possible $m = \max B_k[1]$ for given $k$ and $n = \lvert B_k[1]\rvert$ elements

Sidon sets are sets $$A \subset \mathbb{N}$$ such that for all $$a_j,b_j \in A$$ holds $$a_1+a_2=b_1+b_2 \iff \{a_1,a_2\}=\{b_1,b_2\}.$$ Thus if you know the sum of two elements, you know which elements were added in the first place.

The general case is known in literature as $$B_k[g]$$ sets. Every result of adding up at most $$k$$ elements will occur at most $$g$$ times in all possible combinations. Sidon sets are therefore called $$B_2[1]$$ sets.

An example of a $$B_3[1]$$ set is $$\{1,7,11\}$$ with $$k = 3$$, $$n = \lvert B_k[1]\rvert=3$$ elements, $$m = \max B_k[1] = 11$$ and $${n+k \choose k}={6 \choose 3}=20$$ distinct sums:

0=0, 1=1, 1+1=2, 1+1+1=3, 7=7, 7+1=8, 7+1+1=9, 11=11, 11+1=12, 11+1+1=13, 7+7=14, 7+7+1=15, 11+7=18, 11+7+1=19, 7+7+7=21, 11+11=22, 11+11+1=23, 7+7+11=25, 11+11+7=29, 11+11+11=33.

I didn't find a $$B_3[1]$$ set with $$n=3$$ and a smaller $$m$$ than 11. However $$\{1, 8, 11\}$$ has similar properties.

My Question

Considering $$B_k[1]$$ sets (only one solution for any sum of at most $$k$$ elements). What is the smallest $$m$$ for given $$k$$ and $$n$$ and how to construct a set with this property?

If the general case for any given $$k$$ isn't known, we may set $$k=3$$.

Note: In a former question ("Set of small numbers with distinct $$k$$-sums") a construction by Javier Cilleruelo was given. However it doesn't manage to find sets with the smallest $$m$$ possible.

• You might consider choosing a more informative title in order to make more people see this question. Oct 16, 2015 at 12:41

## 1 Answer

Since the question asks for exact smallest values, not bounds or asymptotics, it is likely to be a difficult problem.

First note that instead of taking sums of at most $$k$$ elements, we can take sums of exactly $$k$$ elements, if we include a zero element. So the three-element solution $$\{1,7,11\}$$ corresponds to a four-element solution $$\{0,1,7,11\}$$ with this interpretation. The result (minimum possible largest element) is not affected by this change, but the number of elements changes by 1.

For $$k=3$$ this is the OEIS sequence A227358, "Length of shortest Golomb-like (for sums of triples) ruler with n marks". Currently (last updated 2013) the values listed are:

$$\begin{array}{lllllllll} n& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ \hline m& 0& 1& 4& 11& 23& 45& 82& 129& 208& 309 \end{array}$$

using the "exactly $$k$$ elements" definition (so the $$n$$ are off by one with respect to the current question). The OIES entry links to a C program that computes the solutions, answering the "how to construct" part.

For $$k=3$$ and $$n=4=3+1$$ the results of the OP are confirmed: There are exactly four minimal solutions with $$m=11$$, namely:

 0     1     7    11
0     1     8    11
0     3    10    11
0     4    10    11


(The C program lists only the first two, because the other two are obtained by reversal symmetry, i.e. by the mapping $$x \mapsto 11-x$$.)

See also A227588 for a table where both $$k$$ and $$n$$ are varying.