8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What do you mean by a random choice of integers? $\endgroup$ – Barry Cipra Apr 29 '13 at 16:08
  • $\begingroup$ this sounds like an arithmetic combinatorics problem.... $\endgroup$ – Suvrit Apr 29 '13 at 16:21
  • $\begingroup$ @Sra: thanks for the hint. I'm not familiar with it, but looking into it right now and it looks promising. $\endgroup$ – Sebastian Schlecht Apr 29 '13 at 16:36
  • $\begingroup$ @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. $\endgroup$ – Sebastian Schlecht Apr 29 '13 at 17:21
  • 3
    $\begingroup$ 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. $\endgroup$ – Rob Myers Apr 29 '13 at 20:15
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Sebastian Schlecht Apr 29 '13 at 18:40
  • $\begingroup$ @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$. $\endgroup$ – Sebastian Schlecht May 3 '13 at 9:48
  • $\begingroup$ For example: $S=\{1,2,4,6\}$. Hence, $k=4$, $t=13$. But $x_i\neq x_j$ for all $i \neq j$. $\endgroup$ – Sebastian Schlecht May 3 '13 at 9:54
  • $\begingroup$ Of course you are right. I corrected it. $\endgroup$ – Aaron Meyerowitz May 4 '13 at 3:47

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.