Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 addition 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 have this property? Is there a counting argument that solves this?


A small clarification. The sum of two vectors in this problem is another vector.


Current records:

  • Lower bound: $19$. First given by Brendan McKay over at MO.
  • Upper bound: $30$. First given by Brendan McKay over at MO.

Cross-posted to http://mathoverflow.net/questions/157634/number-of-vectors-so-that-no-two-subset-sums-are-equal

share|improve this question
    
If you have more than 10 vectors, then they are linearly dependent, and you can use the dependence relation to get two equal subset sums. –  Gerry Myerson Feb 7 at 11:37
1  
I retract the 18 vectors suggestion. I do think you can do better than 10, but I don't know how much better. E.g., if the problem were for length 3, you could use the 4 vectors 110, 101, 011, 100. –  Gerry Myerson Feb 7 at 23:36
3  
@Lembik: It's just a loose upper bound; there are $2^k$ possible subsets which must have distinct sums with each element in the range $[0..k]$, so technically it should be $2^k \le (k+1)^{10}$, which gives $k \le 59$. But as I said earlier, it's probably very far from the actual value. –  user21820 Feb 10 at 6:50
1  
If we view the subset sums in the mechanism of the upper bound by @user21820 as random elements of $[0,k]^{10}$, then the Birthday paradox kicks in: if you draw elements (with replacement) from a set of $N$ objects, then you expect reappearances after $O(\sqrt N)$ draws. This doesn't prove anything, but suggests that random search techniques will balk approximately when $2^k$ exceeds $(k+1)^5$. This happens, when $k\ge23$. That is probably closer to the mark than the $59$, but I don't see a way of turning this heuristic into an upper bound. –  Jyrki Lahtonen Feb 12 at 6:39
1  
$n \mapsto \lfloor \frac{1}{2} (n+1) log_2(n+1) \rfloor$ fits the sequence $(1,2,4,5,7,9,12,...)$ exactly and has the correct asymptotic bound. It's almost surely wrong, but so very nice! It predicts that the correct answer for this should be 19. –  user21820 Feb 20 at 11:42

5 Answers 5

UPDATE:

My best result (for vectors with $10$ elements) is $18$.

(But Brendan McKay obtained set of 19 vectors: see cited above http://mathoverflow.net link).

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

Example of $17$ sum-free binary vectors:

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

And example of $11$ sum-free binary vectors (just for curious):

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


For $3,4,5,6,7,8,9,10$-dimensional vectors my best results are $4,5,7,9,12,14,16,18$ accordingly.

share|improve this answer
    
How did you do this? There are $2^{170}$ matrices of size $10$ by $17$ so I can't imagine you tried them all! –  felix Feb 10 at 10:01
    
@felix If you were to try examining all such matrices, you would not need to look at as many as $2^{170}$. Rows and columns can be permuted giving any one such matrix possibly as many as $10!\cdot17!$ representations. That still leaves over $10^{30}$ matrices to check, but that's a lot less than $2^{170}\approx10^{51}$. If exhaustive searching is to be used, a clever search algorithm might take advantage of this. –  alex.jordan Feb 11 at 17:58
1  
@alex.jordan True. It's still far too many however and even checking one is laborious. Oleg567 must have found a smart way to do this. –  felix Feb 11 at 18:02
2  
These results are obtained (I assume) by generating random sets of vectors incrementally. That is, generate a random binary vector, then add it to the list if it doesn't create a duplicate sum; stop after failing a certain number of times. When I carry out this procedure, I also obtain maximum sizes of $7,9,11,13,15,17$ for $n=5-10$. –  mjqxxxx Feb 11 at 18:34
    
@mjqxxxx Thank you that is interesting. I suppose this counts the values of $k$ where subset-distinct answers are very common. –  felix Feb 11 at 19:46

Given a particular subset $S'\subset S$, you can think of each position in the sum as a measurement: the $i$-th measurement tells you how many elements of $S'$ have a $1$ in the $i$-th position. Equivalently, the $i$-th measurement gives you the size of $S'\cap A_i$, where $A_i=\{x\in S \;|\; \pi_i(x)=1\}$. How large can $S$ be if you can identify an arbitrary subset using $n$ such measurements? Well, if $|S|=k$, then each measurement can have $k+1$ different outcomes, and so the most information it can give you is $\log_2(k+1)$ bits. Since you need to distinguish between $2^k$ subsets, you need to obtain $k$ bits of information in total, so $$ n \log_2(k+1) \ge k, $$ or $$ \frac{k}{\log_2(k+1)} \le n. $$ For $n=10$, for instance, this implies $|S| \le 59$.

share|improve this answer
    
I think @user21820 got the same bound in the comments by a direct counting argument. –  felix Feb 11 at 19:45
    
Yes, the counting argument and the information argument are equivalent. –  mjqxxxx Feb 11 at 19:58

An SSD-sequence is a sequence of positive integer numbers in which distinct subsets have distinct sums. If we fill our vectors with the binary representations of the elements of such a sequence, we clearly end with a sum-disjoint set of vectors. For istance, taking the SSD-sequence $3,5,6,7$ we have that $011,101,110,111$ are four sum-disjoint vectors in $\{0,1\}^3$. Erdos conjectured that $$M_n = \min\{\max(S)\;|\; S \mbox{ is a SSD sequence of length } n\}$$ satisfies $M_n \geq c\cdot 2^n$ for some constant $c$, and the problem is still open. On the other hand, it is easy to see that $M_n\leq\frac{1}{2}2^n$ by simply taking powers of two (or the identity matrix in our initial problem). Bohman proved in 1996 that the $k$ elements $s_i=a_k-a_{k-i}$ are an SSD-set, where $1\leq i\leq k$ and $\{a_n\}_{n\in\mathbb{N}}$ is the Conway-Guy sequence $$ 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, \ldots$$ defined by $a_0=0,a_1=1$ and $$ a_{n+1} = 2a_n - a_{n-\lfloor\frac{1}{2}+\sqrt{2n}\rfloor}. $$ This gave the bound $M_n\leq 2^{n-2}$ for $n\geq 20$, for istance. Taking $k=11$ we get the eleven-elements SSD set: $$\{594,593,592,590,587,581,570,550,510,433,285\}$$ and by taking binary representations we have eleven sum-disjoint vectors in $\{0,1\}^{10}$ - in general, $n+2$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 20$ - not so many, but still better than the trivial bound.

We are clearly wasting a lot of information, since, for istance, $\{3,4,5,6,8\}$ is not an SSD-set (due to $5+6=8+3$), but the binary representations of $\{3,4,5,6,8\}$ give a five-elements sum-disjoint set of vectors in $\{0,1\}^4$.

Since there are $4$ sum-disjoint vectors in $\{0,1\}^3$, a clever tensor-trick gives that there are at least $\left\lfloor\frac{4n}{3}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$. In the case $n=10$, these thirteen vectors are: $$\begin{array}{*10{c}} 1,0,0,0,0,0,0,0,0,0\\ 0,1,1,0,0,0,0,0,0,0\\ 0,1,0,1,0,0,0,0,0,0\\ 0,1,0,0,0,0,0,0,0,0\\ 0,0,1,1,0,0,0,0,0,0\\ 0,0,0,0,1,1,0,0,0,0\\ 0,0,0,0,1,0,1,0,0,0\\ 0,0,0,0,1,0,0,0,0,0\\ 0,0,0,0,0,1,1,0,0,0\\ 0,0,0,0,0,0,0,1,1,0\\ 0,0,0,0,0,0,0,1,0,1\\ 0,0,0,0,0,0,0,1,0,0\\ 0,0,0,0,0,0,0,0,1,1 \end{array}.$$ For the same reason, since there are $7$ sum-disjoint vectors in $\{0,1\}^5$, there are at least $14$ sum-disjoint vectors in $\{0,1\}^{10}$ and at least $\left\lfloor\frac{7n}{5}\right\rfloor$ sum-disjoint vectors in $\{0,1\}^n$.

Monte-Carlo computations below seem to suggest that there are at least $2n-3$ sum-disjoint vectors in $\{0,1\}^n$ for any $n\geq 4$. In order to fix notation, let $I_n$ be the maximum number of sum-disjoint vectors in $\{0,1\}^n$. If we manage to prove $$I_{n+1}\geq I_n+2,\tag{1}$$ we prove the $2n-3$-bound.

A simple way to achieve $(1)$ would be to take the vectors giving $I_n$, augment them with a zero in the first coordinate, then take the two additional vectors $(1,0,0,\ldots)$ and $(1,1,1,\ldots)$. Unluckyly, this naive construction does not work since $(1,1,1,1)=(1,0,0,0)+(0,1,0,0)+(0,0,1,1)$, but may be we can fix it.

There is also a graph-theoretic interpretation that may be useful. Consider a bipartite undirected graph $G$ with $m$ red nodes and $n$ ($10$ in the original problem) blue nodes (emitters), where distinct blue nodes have distinct neighbourhoods and there are only edges between a blue node and a red node. Every emitter can give a $+1$,$0$ or $-1$ weight to the elements of the set of its outcoming edges; the weight of a blue vertex is the sum of the weigths of its incoming edges. Sum-free property: if for every non-trivial weigth-assignment there exists a blue vertex with non-zero weight, we get $m$ sum-disjoint elements in $\{0,1\}^n$. For istance, the following "sum-free" graph:

A sum-free graph

gives $I_3\geq 4$ through the set of sum-free vectors $110,101,110,001$ corresponding to the neighbourhoods of the red nodes. The graph corresponding to the SSD-set $011,101,110,111$ is even nicer:

Another sum-free graph

In the this paper Lev shows, through the probabilistic method, $$ I_n \geq \frac{1}{\log_2 9}\cdot(1+o(1))\cdot n\log_2(n), $$ and I think it is worth to reproduce its arguments in the specific $n=10$ case. Let $S=\{-1,0,1\}^{17}$. For any $s\in S$, let $m^+$ be the number of positive coordinates of $s$ and $m^-$ the number of negative coordinates of $s$. For a random chosen vector $d\in\{0,1\}^{17}$ the probability of being orthogonal to $s$ is equal to:

$$ \frac{1}{2^{m^+ + m^-}}\sum_{j=0}^{\min(m^-,m^+)}\binom{m^+}{j}\binom{m^-}{j}=\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+},$$

hence the probability for $10$ randomly chosen vectors to be simultaneously orthogonal to $s$ is very small. Since the number of elements of $S$ of a given $(m^-,m^+)$-type is just $\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}$, in order to prove $I_{10}\geq 17$ it is sufficient to show that:

$$\sum_{1\leq m^+ + m^- \leq 17}\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}\left(\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+}\right)^{10} <1,$$

that is true by direct computation. Moreover, I am now noticing that through a probabilistic argument (the Hoeffding bound) Seva on MO pushed the upper bound down to $30$.

share|improve this answer
1  
The wheel-graph is great! –  felix Feb 13 at 18:42
    
Unless I'm misunderstanding something, the claim is that knowing the degree of each blue vertex lets you uniquely identify the red nodes that are in a subgraph? This isn't true for the wheel graph shown. Every "pac-man" path around the outside that dips into the center once gives the same degrees to all the blue vertices, no matter where it dips in. –  mjqxxxx Feb 13 at 19:18
1  
I'm referring to the red nodes you've drawn on the $10-1$ ($=\{9,1,10\}$), $10-2$ ($=\{1,2,10\}$), $9-1$ and $1-2$ edges. These four can be turned on to give all vertices zero weight, since $+\{9,1,10\}-\{9,1\}=+\{1,2,10\}-\{1,2\}$. –  mjqxxxx Feb 13 at 22:26
1  
Label the blue nodes 1 through 10 in the following manner: $$ \begin{matrix} &1&&&&4 \\ 2&&3&&5&&6 \\ & \\ &&7&&8 \\ &&&9 \\ & \\ &&&10 \end{matrix} $$ Then there is a cycle (2, 3, 7, 8, 9, 10) of even length, and as above, alternating signs here will zero out all weights (sorry!) –  jpvee Feb 14 at 7:43
1  
@JackD'Aurizio The OP put the link in this question. –  marshall Feb 17 at 17:58

A slight improvement to the upper bound showing that the answer is $\le 47$. Assume contrariwise that a set $S$ of $48$ such vectors would exist. The set $S$ has $$ \sum_{k=1}^{24}{48\choose k}=156\,861\,290\,196\,877 $$ subsets of at most $24$ elements. The sum vectors of those subsets belong to the set $\{0,1,\ldots,24\}^{10}$ that has $25^{10}=95\,367\,431\,640\,625$ elements. Therefore a collision is inevitable by the pigeonhole principle.

share|improve this answer
    
We can, of course, try and tune this up further by using the maximum size of a subset as a parameter. I don't think that we get close to the true value this way though (see my comment under the OP for a heuristic). –  Jyrki Lahtonen Feb 12 at 7:22
    
While I can see that without loss of generality, we can assume that one of the subsets $S_1$ and $S_2$ has cardinality $\le n/2$, I fail to understand why this should be the case for both of them. –  jpvee Feb 12 at 7:40
    
@jpvee: The idea here is that if we get a repeated sum vector with both subsets small, then we have already shown that the set $S$ didn't work. –  Jyrki Lahtonen Feb 12 at 7:43
    
Thanks for the clarification; I understand your argument now. –  jpvee Feb 12 at 8:15
1  
Using Jyrki's argument, the upper bound can still be slightly improved to $\le 45$, since $$\sum_{k=1}^{17} {46\choose k} = 3\,652\,326\,252\,869 > 3\,570\,467\,226\,624 = (17+1)^{10}.$$ –  jpvee Feb 12 at 8:40

The Least Upper Bound is 45.

Proof: Consider vectors of the following form, $$V_r=(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10})$$ $$V_1=(1,1,0,0,0,0,0,0,0,0)$$ $$V_2=(1,0,1,0,0,0,0,0,0,0)$$ $$V_3=(1,0,0,1,0,0,0,0,0,0)$$ $$V_4=(1,0,0,0,1,0,0,0,0,0)$$ $$V_5=(1,0,0,0,0,1,0,0,0,0)$$ $$V_6=(1,0,0,0,0,0,1,0,0,0)$$ $$V_7=(1,0,0,0,0,0,0,1,0,0)$$ $$V_8=(1,0,0,0,0,0,0,0,1,0)$$ $$V_9=(1,0,0,0,0,0,0,0,0,1)$$ We consider all subsets $V^n=\{V_{f(k)},V_{f(k+1)},...,V_{f(n)}\}$. Notice that, $$V:=\sum_{k=1}^n V_{f(k)}=(n,a_2,...).$$

There are $\binom{10}{n}$ such subsets where $\{f(k),f(k+1),...,f(n)\}$ uniquely determines the sum vector $V$ by virtue of placing 1's into the positions $\{f(k)+1,f(k+1)+1,...,f(n)+1\}$.

Similarly we proceed to include the following 8 into this set of 9; $$V_{10}=(1,1,1,0,0,0,0,0,0,0)$$ $$V_{11}=(1,1,0,1,0,0,0,0,0,0)$$ $$V_{12}=(1,1,0,0,1,0,0,0,0,0)$$ $$V_{13}=(1,1,0,0,0,1,0,0,0,0)$$ $$V_{14}=(1,1,0,0,0,0,1,0,0,0)$$ $$V_{15}=(1,1,0,0,0,0,0,1,0,0)$$ $$V_{16}=(1,1,0,0,0,0,0,0,1,0)$$ $$V_{17}=(1,1,0,0,0,0,0,0,0,1)$$

Now we look at all subsets $V^n=\{V_{f(k)},V_{f(k+1)},...,V_{f(n)}\}$ of this bigger set. By the same argument as above any subset of this new set has a uniquely determined sum. In checking the argument you will need to rename the index, but the argument remains intact.

It remains to be shown both sets taken together still posses this property.

Updating our previous observation to this new set, $$V:=\sum_{k=1}^n V_{f(k)}=(n,m+1,a_3,...) \; \; \text{with } V_1$$ $$V:=\sum_{k=1}^n V_{f(k)}=(n,m,a_3,...).\; \; \text{without } V_1$$ where $m$ is the number of vectors from our new set.

The possible overlap occurs when: 1)We choose $m+1$ vectors from our new set. 2)We choose $m$ vectors with $V_1$

We know this two choices are mutually exclusive because the vector in the first case and not in the second, say it's $f(k)$, adds a $1$ in position $(f(k)+3 )mod \; 10$.

I hope this is enough to see where this is going, next we add 7 more vectors with the first 3 entries as 1's like $(1,1,1,a_4,...)$. Then we add 6 more vectors, then 5 and so on.

Hence we get a total of $\sum_{k=1}^9 k=45$ vectors.

I am tired and sleepy so I cut the proof short. I hope this helps.

share|improve this answer
    
Thank you for this although I would be very surprised if there were a solution with $45$ vectors. Am I right that is your claim? –  felix Feb 15 at 13:19
1  
@Genomeme: Sorry, but your argument doesn't work. Note that $(1,0,1,0) + (1,1,0,1) = (1,1,1,0) + (1,0,0,1)$. –  jpvee Feb 15 at 15:58
    
@jpvee I see. Thanks. Well, I gave it a try. :) –  jvargas Feb 15 at 20:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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