25
$\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 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 https://mathoverflow.net/questions/157634/number-of-vectors-so-that-no-two-subset-sums-are-equal

$\endgroup$
24
  • $\begingroup$ 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. $\endgroup$ Feb 7, 2014 at 11:37
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 7, 2014 at 23:36
  • 3
    $\begingroup$ @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. $\endgroup$
    – user21820
    Feb 10, 2014 at 6:50
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 12, 2014 at 6:39
  • 1
    $\begingroup$ $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. $\endgroup$
    – user21820
    Feb 20, 2014 at 11:42

4 Answers 4

5
+50
$\begingroup$

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

$\endgroup$
21
  • 1
    $\begingroup$ The wheel-graph is great! $\endgroup$
    – user35671
    Feb 13, 2014 at 18:42
  • $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Feb 13, 2014 at 19:18
  • 1
    $\begingroup$ 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\}$. $\endgroup$
    – mjqxxxx
    Feb 13, 2014 at 22:26
  • 1
    $\begingroup$ 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!) $\endgroup$
    – jpvee
    Feb 14, 2014 at 7:43
  • 1
    $\begingroup$ @JackD'Aurizio The OP put the link in this question. $\endgroup$
    – marshall
    Feb 17, 2014 at 17:58
5
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ How did you do this? There are $2^{170}$ matrices of size $10$ by $17$ so I can't imagine you tried them all! $\endgroup$
    – user35671
    Feb 10, 2014 at 10:01
  • $\begingroup$ @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. $\endgroup$
    – 2'5 9'2
    Feb 11, 2014 at 17:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – user35671
    Feb 11, 2014 at 18:02
  • 2
    $\begingroup$ 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$. $\endgroup$
    – mjqxxxx
    Feb 11, 2014 at 18:34
  • $\begingroup$ @mjqxxxx Thank you that is interesting. I suppose this counts the values of $k$ where subset-distinct answers are very common. $\endgroup$
    – user35671
    Feb 11, 2014 at 19:46
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I think @user21820 got the same bound in the comments by a direct counting argument. $\endgroup$
    – user35671
    Feb 11, 2014 at 19:45
  • $\begingroup$ Yes, the counting argument and the information argument are equivalent. $\endgroup$
    – mjqxxxx
    Feb 11, 2014 at 19:58
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$ Feb 12, 2014 at 7:22
  • $\begingroup$ 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. $\endgroup$
    – jpvee
    Feb 12, 2014 at 7:40
  • $\begingroup$ @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. $\endgroup$ Feb 12, 2014 at 7:43
  • $\begingroup$ Thanks for the clarification; I understand your argument now. $\endgroup$
    – jpvee
    Feb 12, 2014 at 8:15
  • 1
    $\begingroup$ 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}.$$ $\endgroup$
    – jpvee
    Feb 12, 2014 at 8:40

You must log in to answer this question.