Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v\_1,\dots,v\_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S\_1 \subset S$ and $S\_2 \subset S$ have the same sum. Here $\sum\_{v \in S\_i} v$ assumes simple element-wise vector addition where element addition takes place over $\mathbb{R}$. For example, if we take the vectors that are the columns of the identity matrix as $S$ this will do.



> 
> What is the maximum number of vectors one can choose that has this
> property?
> 
> 
> 


I previously asked this question on [MSE](https://math.stackexchange.com/questions/667257/number-of-vectors-so-that-no-two-subset-sums-are-equal) . An explicit construction of $17$ vectors was given by Oleg567 using computer search and an upper bound of $45$ was given by jpvee simply using the observation that $\sum\_{k=1}^{17} {46 \choose k} > (17+1)^{10}$ implies that $46$ vectors is impossible.




---


Lower bound improved to $18$ by Oleg567. Upper bound still stuck at $45$ although it seems implausible the true value is far from the current lower bound.




---


Upper bound of $36$ given by Seva.




---


**Conjecture Feb 24, 2014**. I conjecture the optimal solution size is $\lfloor \frac{1}{2} (n+1) \log\_2(n+1) \rfloor$. For $n=2\dots 15$ this is $2, 4, 5, 7, 9, 12, 14, 16, 19, 21, 24, 26, 29, 32$.




---


New lower bound of $19$ by Brendan McKay.




---


New upper bound of $30$ by Brendan McKay.



Number of vectors so that no two subset sums are equal
Inspired by Seva's probabilistic method, I will show how to **improve the upper bound to 30**. Imagine we have a 0-1 matrix $A$ of 31 rows and 10 columns. I will show that there are two different subsets of the rows that have the same sum.


Define the 10-dimensional random variable $X=(X\_1,\ldots,X\_{10})$ whose value is the sum of a random subset of the rows. This is the same random variable defined by Seva. Seva proceeded by showing that each $X\_j$ is concentrated on a few values. I will improve the bound by considering the components in pairs.


Write $X$ as $(Y\_{12},Y\_{34},Y\_{56},Y\_{78},Y\_{9,10})$, where $Y\_{12}=(X\_1,X\_2)$, $Y\_{34}=(X\_3,X\_4)$, and so forth. The distribution of $Y\_{12}$ depends only on the parameters $w\_{01},w\_{10},w\_{11}$, which are respectively the number of times that 01, 10, 11 occur in the first two columns of $A$. (And so 00 occurs $31-w\_{01}-w\_{10}-w\_{11}$ times.) The probability generating function for $Y\_{12}$ is
$$ F\_{12}(x\_1,x\_2) = 2^{-w\_{01}-w\_{10}-w\_{11}}(1+x\_1)^{w\_{10}} (1+x\_2)^{w\_{01}} (1+x\_1x\_2)^{w\_{11}}. $$
(The coefficient of $x\_1^ax\_2^b$ is the probability that $Y\_{12}=(a,b)$.)
By trying all possible $w\_{01},w\_{10},w\_{11}$, we find that in each case there is some set $K\_{12}$ of 55 values such that 
$$\textrm{Prob}( Y\_{12}\notin K\_{12}) \le p = \frac{300387}{2097152} \approx 0.1432.$$
This calculation is easy for a computer: just expand $F\_{12}$ and sum the largest 55 coefficients. One worst case is $w\_{01}=w\_{10}=10, w\_{11}=11$.


By symmetry, there are also sets $K\_{34},\ldots,K\_{9,10}$ of size 55 containing at least the fraction $1-p$ of $Y\_{34},\ldots,Y\_{9,10}$, respectively. By the union bound, at least the fraction $1-5p$ of $Y$ lies in 
$$K = K\_{12}\times \cdots\times K\_{9,10}.$$
However, $(1-5p)2^{31} > |K| = 55^5$, Therefore, there are two values the same.


It should be possible to do better by grouping the columns even more. I think a non-trivial but plausible computation could handle the 10 columns in two groups of 5.


