# Set of integers with a particular additive property

I have a set of integers $S = \{a_1,a_2,\ldots,a_n\}$. Let $K = a_1+a_2+\ldots+a_n$.

Consider the space of all $n$-tuples whose values are taken from the set $S$. For example $(a_1,a_2,\ldots,a_n)$ is one $n$-tuple and its sum is $K$, $(a_1,a_1,a_2,a_2,\ldots,a_k)$ is another. I need $S$ such that the only $n$-tuple that sums to $K$ among the space of all $n$-tuples is $(a_1,a_2,\ldots,a_n)$.

An example that wont work is, if $S = \{1,4,7\}$, $K = 12 (= 1+4+7)$. $\{1,4,7\}$ and $\{4,4,4\}$ both sum to $12$. Similarly if we take $S = \{1,2,3,4,5,6,7\}$, I can think of 2 $7$-tuples that add to $28$.

I tried the set $S = \{1, 2, 4, 8, \ldots, 2^n\}$ and it seems to work. Can anyone give me an example that is polynomial instead of exponential in $n$. Would the set $S = \{1, 4, 9, 16, \ldots, n^2\}$ or $\{1, 8, 27,\ldots,n^3\}$ work? Thanks for the comments and suggestions.

• I didn't understand the question – Amr Dec 29 '13 at 22:37
• @Amr More formally: Does there exist a polynomial $f\in\mathbb Z[X]$ such that for all finite sequences $(a_i)_{i=1}^n$ with $a_i\in\mathbb N_0$ and $\sum_{i=1}^n a_i=n$ and $\sum_{i=1}^n a_if(i)=\sum_{i=1}^n f(i)$, it follows that $a_1=\ldots=a_n=1$? – Hagen von Eitzen Dec 29 '13 at 22:48
• Instead of $n$-tuple you probably mean multiset. For $n>1$, reordering an $n$-tuple gives a different $n$-tuple with the same sum! – Hagen von Eitzen Dec 29 '13 at 22:49
• I don't understand why $S = \{1,2,4,\dots,2^n\}$ has the desired property. Why is $(1,...,1)$ of length $2^{n+1}-1$ not a counter-example as it has sum $K$? – benh Dec 29 '13 at 22:50
• @benh You are required to take exactly $n$ summands. – Hagen von Eitzen Dec 29 '13 at 23:14

The set of squares will not work in general. Any notrivial solution to $a^2+b^2=c^2+d^2$ allows us to drop $a^2$ and $b^2$ and instead have $c^2$ and $d^2$ twice. And such solutions are easy to find since the equation is equivalent to $(a-d)(a+d)=a^2-d^2=c^2-b^2=(c-b)(c+b)$. For example $1\cdot 15 = 3\cdot 5$, which leads to $a=8, b=1, c=4, d=7$. Indeed, $8^2+1^2=65=4^2+7^2$. There is also the smaller solution $5^2+5^2=1^2+7^2$. Thus already $S=\{1,4,9,16,25,36,49\}$ does not have the desired property. And this reminds us of Ramanujan and Hardy's taxi: $1729 = 10^3+9^3=12^3+1^3$. So the set $S=\{1,8,27,\ldots, 12^3\}$ of cubes won't work either.
Here's why exponential growth is necessary: Let $S=\{a_1,\ldots, a_n\}$. There are $2^n$ subsets of $\{1,\ldots, n\}$ be a "good" set. If $A,B\subseteq\{1,\ldots, n\}$ are distict subsets of the same size $k$ and with $\sum_{i\in A}a_i=\sum_{i\in B}a_i$, the set $S$ is "bad" as this allows us to replace summands coming from $A$ in $a_1+\ldots +a_n$ with summands coming from $B$. Since $\sum_{i\in A}a_i$ is between $0$ and $ka_n$ and there are $n\choose k$ subsets of size $k$, we conclude that $ka_n\ge {n\choose k}$. If we pick $k=\lfloor n/2\rfloor$, then using Stirling's approximation we see that ${n\choose k}\approx\frac{2^n\sqrt {2}}{\sqrt{\pi n}}$ and obtain $$a_n\gtrsim\frac{2^{n+1}\sqrt 2}{n\sqrt{\pi n}}.$$