Take the 2-minute tour ×

Let $A$ be a set of $n$ positive integers with distinct $k$-sums. In other words, if $a_1\le\cdots\le a_k$ and $b_1\le\cdots\le b_k$ are elements of $A$ such that $a_1+\cdots+a_k=b_1+\cdots+b_k$, then $a_i=b_i$, $i=1,\ldots,k$. How small can $\max A$ be?

Let $S(n,k)$ be the smallest possible value of $\max A$.

Some trivial attempts: The construction $A=\lbrace 1,k,k^2,\ldots,k^{n-1}\rbrace$ gives $S(n,k)\le k^{n-1}$. On the other hand, there are ${k+n-1\choose n-1}$ sequences $a_1\le\cdots\le a_k$, which correspond to distinct $k$-sums whose values are at most $k\cdot\max(A)$. Thus $S(n,k)\ge\frac1k{k+n-1\choose n-1}$.

Additional question: How to explicitly construct the set $A$ so that $\max A$ is small? Thomas Bloom asserted below that $S(n,k)\asymp n^k$, but I will be satisfied with a construction where $\max A$ is a polynomial of $n$ (of order possibly larger than $k$).

share|improve this question

1 Answer 1

These are commonly known as $B_k$ sets. It is known that the order of magnitude of a $B_k$ set in $[1,N]$ is around $N^{1/k}$ so that, in your notation

$$ S(n,k) \asymp n^k $$

where the implicit constants can depend on $k$.

A paper of Bose and Chowla (Theorems in the additive theory of numbers. Comment. Math. Helv. 37 1962/1963 141–147) shows that $$ S(n,k) \leq (1+o(1))n^k $$

as $n\to\infty$. This generalises a result of Singer in the $k=2$ case.

When $k=2$ this is sharp, as shown in a paper of Erdos and Turan (On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. 16, (1941). 212–215)

For recent progress on lower bounds for $k\geq 3$ see "New upper bounds for finite Bh sequences" by J. Cilleruelo (Adv. Math. 159 (2001), no. 1, 1–17). For large $k$ these are roughly of the shape $k^{-2k^2}$.

Edit: here's a simple explicit construction that almost gives $n^k$. Equivalently, we want to find a $B_k$ set in $[1,N]$ of size almost $N^{1/k}$. Suppose that $N+1$ is a prime. Let $P$ be the set of all primes at most $N^{1/k}$. Let

$$ A = \{ 1\leq n\leq N : \theta^n\in P\} $$

for some primitive root $\theta$ of $N+1$. Then

$$ x_1+\cdots+x_k=y_1+\cdots+y_k $$

if and only if, letting $p_i=\theta^{x_i}$ and $q_i=\theta^{y_i}$,

$$ p_1\cdots p_k =q_1\cdots q_k \pmod{N+1} $$

But since these terms are less than $N+1$ this congruence is a genuine equality, and we're done by the fundamental theorem of arithmetic. This gives a construction of a $B_k$ set in $[1,N]$ of size about $kN^{1/k}/\log N$, and we're done.

share|improve this answer
Thanks! I forgot to say that I was looking for an explicit construction. –  jege Jun 14 '13 at 10:13
The Bose-Chowla paper gives an upper bound using an explicit construction generalised from that of Singer, which uses finite affine geometry. A simpler construction was also given by Bose. Kevin O'Bryant has a nice survey paper detailing these in the k=2 case which can be found by Googling. The paper of Bose and Chowla has a very readable description of the general construction. –  Thomas Bloom Jun 14 '13 at 16:11
See the edit for a simple construction. I learnt about this from Javier Cilleruelo only a few weeks ago! Simple as it sounds, I'm not sure whether it appears in print anywhere. –  Thomas Bloom Jun 14 '13 at 18:14

Your Answer


