18
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Is this a puzzle or a problem? If it's a problem, did you try smaller dimensions? That might help to guess the pattern. $\endgroup$ Feb 15, 2014 at 12:32
  • $\begingroup$ @AlexDegtyarev Really it's a puzzle at this point although maybe I don't fully understand the distinction. What I mean is that there is no greater goal than my interest in how one would solve the problem. I did however try smaller dimensions and my guess is that the optimal answer is no more than $20$. $\endgroup$
    – Simd
    Feb 15, 2014 at 13:18
  • $\begingroup$ To me, the distinction is that a puzzle is not worth investing too much effort :) $\endgroup$ Feb 15, 2014 at 13:22
  • 3
    $\begingroup$ @AlexDegtyarev Ah well that is not something I can judge for someone else :) If it helps motivate it, the equivalent question for integers rather than vectors has exercised such luminaries as Erdos and others. See e.g. ams.org/journals/proc/1996-124-12/S0002-9939-96-03653-2/… $\endgroup$
    – Simd
    Feb 15, 2014 at 13:24
  • 2
    $\begingroup$ @vzn I assume the idea was only to stress that it is not modulo 2. $\endgroup$
    – user9072
    Feb 16, 2014 at 0:43

4 Answers 4

4
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The third sentence of the 1st para somehow reminds me of the sunflower conjecture and related stuff :-) $\endgroup$
    – Suvrit
    Feb 25, 2014 at 4:11
  • $\begingroup$ Very nice! By a chance, do you use Maple? I wonder how with Maple can one find the sum of, say, 55 largest coefficients of a polynomial. $\endgroup$
    – Seva
    Feb 25, 2014 at 9:38
  • $\begingroup$ Say $P$ is a polynomial in $x$ and $y$. To make a sorted list of the coefficients: sort(subs(x=1,y=1,[op(expand(P))]),`>`). Then use add() to sum the first so many entries. $\endgroup$ Feb 25, 2014 at 10:30
20
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ I think this problem is equivalent to cs.mcgill.ca/~colt2009/papers/004.pdf so at least the asymptotic constant is known to be 2. $\endgroup$
    – marshall
    Feb 16, 2014 at 13:56
  • $\begingroup$ Probably the corners of $I_1\times\cdots\times I_n$ can be cut off too, reducing $7^{10}$ to something smaller. $\endgroup$ Feb 24, 2014 at 0:44
  • $\begingroup$ Cutting off the corners seems to be a problem since the $X_k$s are dependent, and so we have to work with rectangular areas (where a union bound can be used). $\endgroup$
    – Seva
    Feb 24, 2014 at 12:31
  • $\begingroup$ Take the pair $(X_1,X_2)$. For $b=31$, no matter what the first two columns are, the 55 most likely values are together likely enough (at least $1-p$ for some smallish $p$) that $2^b(1-5p) \gt 55^5$, which proves $b\le 30$. I did two columns by exhaustion and didn't try tuning it much. Taking more columns at once should make it better. $\endgroup$ Feb 24, 2014 at 15:13
  • $\begingroup$ Sorry, I cannot follow. Writing $b=31$ and $b\le 30$, did you mean $m=31$ and $m\le 30$? What is the meaning of $55$ in your comment and where $2^b(1-5p)>55^5$ comes from? $\endgroup$
    – Seva
    Feb 24, 2014 at 16:48
10
$\begingroup$

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.

$\endgroup$
18
  • 1
    $\begingroup$ Something to put on OEIS? $\endgroup$ Feb 15, 2014 at 14:32
  • 2
    $\begingroup$ Take a look at $n=4$. Sums $1001+1110$ and $1010+1101$ are the same: $2111$. I hope you can improve the code. $\endgroup$
    – Oleg567
    Feb 15, 2014 at 16:30
  • 2
    $\begingroup$ @Oleg567: Thanks. I thought it was suspicious that my program worked immediately. I'll be back! $\endgroup$ Feb 16, 2014 at 0:13
  • 1
    $\begingroup$ Incidentally, Rob Pratt noted the error earlier, but posted it as an answer that was soon deleted. Thanks Rob. $\endgroup$ Feb 16, 2014 at 0:28
  • 1
    $\begingroup$ Testing if a given set of vectors is a solution is NP-hard I believe. This doesn't of course tell you much about how hard it will be in practice and it tells you nothing about how hard it is to solve the problem we actually want to solve (i.e. what is the optimal number of vectors). $\endgroup$
    – marshall
    Feb 17, 2014 at 7:15
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ There is a quicker way. I use a hash table, with a trick to avoid repeated initialisation. Add the sums to a hash table, stopping when the same sum is already present. No sorting is needed and you stop as soon as the duplicate sum is found, rather than having to find them all. $\endgroup$ Feb 18, 2014 at 9:57
  • $\begingroup$ @Brendan McKay, yes, clever method. If access to the value in hash table takes O(n) of time (like in binary trees (or balanced trees), then this method must be a few times faster. Thank you. $\endgroup$
    – Oleg567
    Feb 18, 2014 at 18:44
  • 1
    $\begingroup$ I found some with 19 sets. I'll add one for your checking to my answer shortly. $\endgroup$ Feb 23, 2014 at 22:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.