Skip to main content
7 of 7
added 344 characters in body
Seva
  • 23k
  • 2
  • 59
  • 141

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

Seva
  • 23k
  • 2
  • 59
  • 141