# Number of Distinct Sums of Integers

Hello,

I'm new to MO. Please, bear with my inexperience. I try to be as precise as it is possible to me.

Given a multiset of integers $S$, I'm interested in the number of sub-multisets which sum up to distinct sums. I call this number $S_\sum$ and is defined as

$S_\sum = \left|\left\{ \sum_{i \in Q} i \quad \middle| \quad Q \subseteq S \right\}\right|$

EXAMPLE

$S = \{1,3,7,9\}$. Number of subsets is $2^4 = 16$, but the number of sub-multisets with distinct sums are $S_\sum = 15$, as the subsets $\{3,7\}$ and $\{1,9\}$ do add to the same number 10.

The upper bound is clearly the number of sub-multisets ($2^{|S|}$). The lower bound can be as small as $|S|+1$ (in the case of $S$ consisting of only equal numbers).

As I think, that it is difficult to come up with an exact solution, I'm looking for an estimation of the number in question if the set is chosen randomly.

The precise question:

For a randomly chosen multiset of integers $S$, how does $S_\sum$ relate in average to $|S|$ and $\sum_{i \in S} i$.

• What do you mean by a random choice of integers? – Barry Cipra Apr 29 '13 at 16:08
• this sounds like an arithmetic combinatorics problem.... – Suvrit Apr 29 '13 at 16:21
• @Sra: thanks for the hint. I'm not familiar with it, but looking into it right now and it looks promising. – Sebastian Schlecht Apr 29 '13 at 16:36
• @Barry: It's probably better to ask what the average of $S_\sum$ is for a given number and sum of the elements, $|S|$ and $\sum_{i\in S} i$ respectively. – Sebastian Schlecht Apr 29 '13 at 17:21
• This sounds related to the isolation lemma, see en.wikipedia.org/wiki/Isolation_lemma. Briefly, given a set {1,..,n} and a uniformly random assignment of integers $1 \leq w(i) \leq N$, the probability there is a unique subset with a minimal weight is $\geq 1 - n/N$. The proof is simple and available online, so perhaps you can adapt it to your needs. – Rob Myers Apr 29 '13 at 20:15

Here is a possible formulation of your question: A multiset is a list $S$ of positive integers $x_1 \le x_2 \le \cdots \le x_k.$ The size is $k=|S|$ and the total is $t=\Sigma_{x \in S}x.$ Call $S$ a $(k,t)-$multiset (which could also be called an unordered partition of $t$ into $k$ positive parts.) There are $2^k$ sums of some all or none of the $x_i$ and, as you say, the number of distinct sums could be as high as $2^k$ ( provided that $t \ge 2^{k}-1$) and as small as $k+1$ (provided that $t$ is a multiple of $k$).

Since the number of $(k,t)-$multisets is finite, what can be said, for fixed $k,t$, about the average number of distinct sums for a "randomly" chosen $(k,t)-$multiset.

There are still choices of what is meant by random. We could write each possible multiset on a card and pick one at random: then $13,13,13,13$ would be as likely as $3,10,13,26$ for $k,t=4,52.$ Or, you could roll a fair $4$-sided die $52$ times, see how often each face comes up and just use the multiset of those 4 counts ( you would either need to start over in the unlikely event that some count is zero or else roll $48$ times and start each count at $1$.). In this second model $5,8,13,26$ is twenty four times more likely than $13,13,13,13$

Later: You have now clarified that you are particularly interested in $(k,2^k+r)$ designs where $r$ is "small". I don't know if you are thinking about $r=3$ or $r=3k$ or $r=k^3.$ Even for $r=3$ I don't think that explicitly generating all multisets would be feasible for $k=10$ (or something like that) I can see a possible opening for impressive probability and statistics arguments by those expert in the field. It am thinking about fixing $k$ and increasing $t$ so perhaps that is not so much your interest, however maybe these thoughts would be of interest:

• For $A \subseteq \{1,2,\cdots,k\}$ let $\Sigma_A=\Sigma_{i \in A}x_i.$ Perhaps you want to consider what the set $\mathcal{E}_S=\{(A,B) \mid \Sigma_A=\Sigma_B\}$ could look like for a particular multiset $S$ of values. Certainly if $(A,B)$ is in $\mathcal{E}_S$ with $A,B$ disjoint so are $(A \cup C,B \cup C)$ for any of the $2^{k-|A|-|B|}$ sets disjoint from both. That is a special case of $(A \cup A',B \cup B') \in \mathcal{E}_S$ when the unions are disjoint and $(A,B)$,$(A',B')$ both are.

• For $t \lt \binom{k+1}{2}$ there are forced to be solutions of $x_i=x_j$ (with $i \ne j$ of course) each of which leads to $2^{k-2}$ other equal sums as just commented. For $t \lt 2^k-1$ we have $\mathcal{E}_S \ne \emptyset.$

• How big must $t$ be relative to $k$ in order to have the $x_i$ distinct with probability greater than $1-1/k$ ( or some other $1 - \varepsilon$? ) Is it a sharp transition at some critical point?

• The comment above about the isolation lemma seems very interesting. If I read it correctly, then if we take $t=mk$ then the least of the $x_i$ is unique of its value with probability exceeding $1-1/m.$ If we take that singleton set out of consideration then the next smallest is again unique of its weight with probability exceeding $1-1/m$ etc. So the expected number of distinct $x_i$ is at least $(1-1/m)k.$

• How much larger (I'd guess quite a bit larger) does $t$ have to be in order to make it unlikely that there would be any cases of $x_i+x_j=x_k+x_{\ell}$? The same question if we ask that instead (or in addition) we are unlikely to see $x_i+x_j=x_k?.$ Again the isolation lemma says that for any given partition of the index set $\{1,\cdots,k\}$ or merely family $F$ of subsets of the index set, the $A \in F$ which minimizes $\Sigma_A$ is the only one of its weight with probability exceeding $1-1/m.$ (So it makes sense to restrict $F$ to at least have no member contain any other.)

Well maybe that is far enough with questions I can't answer.

• @Aaron: thank you very much for your clarification. I very much agree with your formulation. My final application needs (for given $k,t$) all $(k,t)$-multisets to be equally likely. Further, I'm mainly interested in the case, where $2^k$ is close to $t$. It would be also fine to restrict the question to this case, if it simplifies the task. – Sebastian Schlecht Apr 29 '13 at 18:40
• @Aaron: thank you so much for your fruitful effort. it has been bank holiday in Germany, so please excuse my absence. I definitely agree on the promising of isolation lemma. Just a question for clarification in advance: 2nd Item: $x_i$ is a single element of $S$. For $t < 2^k -1$, I just see that there $\mathcal{E}_S \neq \emptyset$, but not necessary $(x_i,x_j) \in \mathcal{E}_S$. – Sebastian Schlecht May 3 '13 at 9:48
• For example: $S=\{1,2,4,6\}$. Hence, $k=4$, $t=13$. But $x_i\neq x_j$ for all $i \neq j$. – Sebastian Schlecht May 3 '13 at 9:54
• Of course you are right. I corrected it. – Aaron Meyerowitz May 4 '13 at 3:47