Number of vectors so that no two subset sums are equal

Question

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

Answer 1

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.

Answer 2

Following marshall's comment below, I (sadly) had to completely re-write my original answer.

A famous open conjecture of Paul Erdos, first stated about 80 years ago, is that if all subset sums of an integer set $S\subset[1,n]$ are pairwise distinct, then $|S|<\log_2n+O(1)$ as $n\to\infty$. (Here $\log_2$ denotes the base-$2$ logarithm.) In modern terms, a subset of an abelian group, all of whose subset sums are pairwise distinct, is called dissociated. Similarly to Erdos' original problem, one can ask how large can dissociated subsets of other "natural" sets in abelian groups be. Say, you are asking what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$, and this particular problem has been studied by a number of authors. It is known that the largest size of its dissociated subset is $$ \frac12(1+o(1))\,n\log_2 n; $$ see, for instance, this paper by Bshouty for details and a historical account.

---

Added 19.02.14 / Edited 24.02.14

A bug in my original post fixed, what I can show is that for $n=10$, at most $36$ vectors can be found. Perhaps, with some effort this can be pushed a little further to yield an even smaller bound. Here is the argument.

Assuming that $S=\{s_1,\ldots,s_m\}$ is a dissociated subset of $\{0,1\}^n$, for each $i\in[m]$ and $k\in[n]$ write $s_i=(s_{i1},\ldots,s_{in})$ and $w_k:=s_{1k}+\dotsb+s_{mk}$. Choose $\epsilon_1,\ldots,\epsilon_m\in\{0,1\}$ independently of each other and randomly with ${\mathsf P}(\epsilon_i=0)={\mathsf P}(\epsilon_i=1)=1/2$, and let $X_k:=\epsilon_1s_{1k}+\dotsb+\epsilon_ms_{mk}$ $(k\in[n])$; thus, $X_1,\ldots,X_n$ are random variables with $X_k\sim B(w_k,1/2)$ and $\epsilon_1s_1+\dotsb+\epsilon_ms_m=(X_1,\ldots,X_n)$.

Fix an integer $b\ge 0$ and for each $k\in[n]$, let $I_k$ denote the block of $b$ consecutive integers, centered around $w_k/2$. (If $w_k$ and $b$ are of the same parity, there is a unique such block, otherwise there are two blocks.) Write $p_w(b)$ for the length $w+1-b$ tail of the binomial distribution $B(w,1/2)$; that is, $p_w(b)$ is the probability that a random variable with this distribution will not take one of its $b$ most probable values. We then have ${\mathsf P}(X_k\notin I_k)=p_{w_k}(b)\le p_m(b)$ for each $k\in[n]$; hence, by the union bound, $X_k\in I_k$ holds for all $k\in[n]$ with probability at least $1-n\cdot p_m(b)$.

We now observe that $X_1\in I_1,\ldots,X_n\in I_n$ means that $\epsilon_1s_1+\dotsb+\epsilon_ms_m\in I_1\times\dotsb\times I_n$, the probability of which is $2^{-m}T$, where $T$ is the number of subsets sums of $S$ (that is, the number of choices of $\epsilon_1,\ldots,\epsilon_m$) that fall into the box $I_1\times\dotsb\times I_n$. However, since $S$ is dissociated, the number of such subset sums does not exceed the total number of integer points inside $I_1\times\dotsb\times I_n$, which is $b^n$. As a result, we get $$ 2^{-m}b^n \ge 1-n\cdot p_m(b), \tag{$\ast$} $$ and to show that $m\le 36$ it remains to notice that ($\ast$) is invalid for $n=10,\ m=37$, and $b=11$.

Answer 3

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...

---

Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, with 2 inequivalent solutions, example

10
11

$n=3$: best is 4, with 2 inequivalent solutions, example

110
101
011
111

$n=4$: best is 5, with 48 inequivalent solutions, example

1100
1011
0111
1110
1111

$n=5$: best is 7, with 877 inequivalent solutions, example

11100
11010
11001
10111
01111
11110
11111

$n=6$: best is 9, with 114227 inequivalent solutions, example

111000
100111
010111
001111
110110
111100
111011
111110
111101

$n=7$: best is 12, with 118485 inequivalent solutions, example

1000000
0100000
0010000
1001000
1101100
1001011
0011110
1110010
0111010
0111001
0100111
1010101

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my combinatorial data page.

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 27620 sets of size 19 but there are more. Here is one:

0001111011
1010111100
1011010001
0111010100
1110110111
1101000101
1011100010
0100110011
0110010001
0101101100
1101101101
0110100011
0001010110
0000110110
1100011010
1000101001
0010001111
1000010111
0110001000

In a separate answer I prove an upper bound of 30 for $n=10$. However I will be quite surprised if even 20 is possible.

Answer 4

I get $18$ sum-free binary vectors recently.

(UPDATE: It is not top-result now. Brendan McKay obtained $\large\bf 19$ sum-free binary vectors. See his answer, update Feb 24.)

A few examples of $18$ sum-free binary vectors:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$;

$\qquad(1,0,0,0,1,1,1,1,0,1)$,
$\qquad(0,1,0,1,0,0,1,0,1,0)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,0,1,1,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,1,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,0,1,0,1,1,0,1,0,0)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$.

---

(Here is discussion of sum testing - as wide comment for Brendan McKay)

Testing of all sums is slow, when you'll generate all sums, and compare each-other. If there are $n$ vectors, then there are $N=2^n$ sums. Naive comparison will take $O(N^2)=O(2^{2n})$ of time.

Good way to construct all sums:

shown on an example of $5$ vectors $a,b,c,d,e$.

There are $2^5=32$ sums.

1-st step: Constructing of sums:

0) $s[0]=0$;
1) $s[1]=a$;
2) $s[2]=b+s[0]$, $s[3]=b+s[1]$;
3) $s[4]=c+s[0]$, $s[5]=c+s[1]$, $s[6]=c+s[2]$, $s[7]=c+s[3]$;
4) $s[8+i]=d+s[i]$, where $i=0,1,...,7$;
5) $s[16+i]=e+s[i]$, where $i=0,1,...,15$.

Time capacity is $O(n\times N) = O(n\times 2^n)$.

2-nd step: Sorting of sums:

Fast sorting methods are quick-sort, heap-sort etc...

Time capacity is $O(N \log N) = O(2^n \times n)$.

3-nd step: Comparison of neighboring sums:

for each $i = 1,..,N-1$ just compare $s[i-1]$ and $s[i]$.

Time capacity is $O(N) = O(2^n)$.

So, total time capacity is $O(n\times N) = O(n\times 2^n)$. Much faster than $O(N^2)$.