Number of subsum of a given set of integers

Question

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural:

Given n integers $(e_i)$ chosen (randomly) between $1$ and $2^n$, define $A = \{ \sum_I e_i, \forall I \subset [1,..,n] \}$. The question is to estimate the size of $A$. If we take $\forall i, e_i = 1$, this size of $A$ equals $n+1$, if we take $\forall i, e_i = 2^i$, the size becomes $2^n$. I would guess that in general, it is very unlikely to have a polynomial size for $A$, but I can't prove anything. If some results about the expectancy $|A|$, distribution, or anything is known, I would be very happy to have the links or explanations; or if you have any ideas to solve the problem, of course.

Thanks in advance!

Answer 1

Do you want to know about specific $n$ values or asymptotics?

In the event that $e_i=e_j,$ $|A| \le 2^{n}-2^{n-2}$ otherwise it seems highly likely that it is larger than that and, in any case, that $|A| \gt 2^{n-1}.$ The chance of having some $e_i=e_j$ is about $4.3\%$ for $n=10$ but $1-\prod_{j=1}^{19}(1-\frac{j}{2^{20}}) \approx 0.018\%$ for $n=20.$

The chance of having a case of $e_i+e_j=e_k$ is larger but still goes to $0$ as $n$ increases. If that does happen then $|A| \le 2^n-2^{n-3}$

In $1000$ trials with $n=10$ There were $40$ cases of $e_i=e_j$ and of these $|A|$ ranged from $552$ to $762.$ It the other $960$ cases (with the $e_i$ distinct) the sums ranged from $628$ to $1012.$

In $100$ trials with $N=20$ there were, as expected, no cases of $e_i=e_j.$ The values of $|A|$ ranged between $2^{20}-2^{17.19}$ and $2^{20}-2^{16.02}.$

LATER If you just want a lower bound which grows faster than any polynomial then I will propose $\sqrt{2}^N=2^{N/2}.$ This is of course terrible since the few experiments always had $|A| \gt 2^{N-1}.$ But lets look at the probability that if we just look at $e_1,e_2,\cdots,e_m$ with $2m \le N$ we have all $2^m$ partial sums unique. If there are two sets $I,J$ with $\sum_Ie_i=\sum_Je_j$ then there are two disjoint sets $I,J$ with this property (delete the common elements from both the old $I$ and old $J$.) To get one of these potential disjoint pairs $I,J$ we would split the indices $1,2,\cdot,m$ into three classes:

• used in $I$

• used in $J$ and

• used in neither.

There are $3^m$ ways to do this (actually less than half this since we can ignore any possibility with $I$ or $J$ empty and we don't care which is $I$ and which is $J$.) The probability that a particular split gives equal sums is less than $2^{-N}$ since the maximum element can be one of $2^N$ values but at best, just one of these makes that split work. So the probability that at least one split gives equal sums is less than $\frac{3^m}{2^N}.$ Putting $m=N/2$ gives the probability of this failure at $\left(\frac{\sqrt{3}}{2}\right)^N$ which goes to $0$ exponentially quickly.

Answer 2

Ok, I think I have an answer:

Let $X_i = |\{\sum_J e_j, J \subset [1,2,..,i] \}|.$

Notice that: $Pr(X_i = 2X_{i-1}) \sim \frac{2^n - X_{i-1}^2}{2^n}$. (because, you need the new integer to be different from every difference of two partial sum of the previous integers to double the number of different sums). Then, if we suppose that $X_n \leq P(n)$ where $P$ is a polynomial, this probability tends to 1 as $n$ tends to $\infty$. (because $Pr(X_i = 2X_{i-1}) \geq \frac{2^n - P(n)^2}{2^n} \geq (1- \epsilon)$ for large enough $n$). But in that case, the probability that this will give us something above $P(n)$ is $1$ asymptotically. This lead us to a contradiction. Therefore, the case where $X_n$ is bounded by a polynomial is very unlikely. I think we can do the same (but we have to check carefully the details) for $X_n \leq 2^{n/2 - \delta}$ so the $Pr(X_n \leq 2^{n/2 - \delta}) \rightarrow 0$.

We can probably also relax the condition $Pr(X_i = 2X_{i-1})$ by $Pr(X_i = (1+\delta)X_{i-1})$, to prove something a little bit stronger.

I hope it was understandable, I writed this very quickly because of a lack of time.