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$).


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.

  • $\begingroup$ Thanks! I forgot to say that I was looking for an explicit construction. $\endgroup$
    – jege
    Jun 14 '13 at 10:13
  • $\begingroup$ 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. $\endgroup$ Jun 14 '13 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 14 '13 at 18:14

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.