3
$\begingroup$

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!

$\endgroup$
1

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the experiment! It confirms clearly the intuition. How have you computed the 4.3% and 0.018% ? By trials ? I would be happy with an asymptotic result, something like $Pr(|A|< 2^{n-1})$ tends to $0$, would be perfect. (or even something weaker $Pr(|A| < f(n)) \rightarrow_{\infty} 0$ for any function which is strictly greater than any polynomial. $\endgroup$
    – user50324
    Feb 3, 2015 at 21:00
  • $\begingroup$ @Aaron Meyerowitz: change $N$ to $n$ everywhere in your post. The typo's is quite confusing. $\endgroup$
    – dohmatob
    Jan 10, 2016 at 10:06
  • $\begingroup$ For the potential pairs $(I, J)$, the exact count is $\frac{3^m - 1}{2!} + 1 = (3^m + 1)/2 \le 3^m$. $\endgroup$
    – dohmatob
    Jan 10, 2016 at 15:07
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Interesting approach but I am not convinced. You only need to consider two partial sums which come from disjoint sets, and for each pair the smaller sum must be taken from the larger. Also, many of these differences will be too big (add $9$ $e_i$ which are all over $2^{n-1}$ and take away the sum of of $3$ $e_i$ which are all under $2^{n-1}$). More seriously, $X_j^2$ is quite likely to be larger than $2^n$ once $j$ is much over $\frac{n}{2}$ $\endgroup$ Feb 6, 2015 at 7:03
  • $\begingroup$ Yes, we want to prove that $X_n^2$ will be larger than $2^n$ (with proba $1$). If you suppose the contrary (for e.g Xn to be less than a polynomial), then $X_i^2$ is always much less than $2^n$ and you can apply the fact that each time you add a number, the number of different sums will be multiply by $2$ in general. This leads us to the contradiction: as you said, it is multiplied by $2$ each time, in general. If you suppose $X_n < 2^{n/2 - \epsilon}$, then you can do the same. So, it proves that asymptotically, $X_n > 2^{n/2 - \epsilon}$ with proba = 1, no? Am I missing something? $\endgroup$
    – user50324
    Feb 6, 2015 at 14:43
  • $\begingroup$ Ok, I guess I agree that $Pr(X_i = 2X_{i-1}) \gt \frac{2^n - X_{i-1}^2}{2^n}$ although it might be much greater than. It could be quite likely that $X_{n-5}$ is close to $2^{n-5}$ and then the righthand side where you have $\sim$ would be $1-2^{n-10}.$ $\endgroup$ Feb 7, 2015 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.