Binary Sequences and Combinatorics I have the following problem:
Consider binary sequences of length $n$. We know there are $2^{n}$ of them. Now I take $2^{n-2}$ of them (except the zero sequence). If we take only 2- sums can we generate the remaining sequences ?.
Example: $n =4$. Take 4 of them. Lets take
$(1000),
(0010),
(1001),
(0100),$
The possible 2 - sums are
$(1000) + (0010) =(1010), (1000) + (1001)=(0011), (1100), (1011), (0110), (1101).$
Here I dont have enough sums to generate all the remaining sequences.
What about this in general. My guess says that it is not possible.
Any hints towards this will highly be appreciable.
Edit:The problem can be reformulated as taking any set with $n$ elements. Take $2^{n-2}$ non - empty subsets. Can we obtain all the remaining subsets by the 2 - symmetric differences of these elements. By 2 - symmetric I mean the symmetric difference of two subsets from our list.
 A: Partial result using probabilistic methods (but the result is deterministic). I claim that, for any $n$, you can choose the generators so that the pairwise sums will miss at most $31$ of the target binary sequences.
I'll use $\oplus$ for the XOR sum. Let $X_1,\ldots,X_k$ be $k=2^{n-2}$ bit-strings chosen independently uniformly at random (the "generators"). I claim that the $m=\binom k2$ pairwise sums $Y_{ij} := X_i \oplus X_j$, $i\ne j$, are uniformly distributed and pairwise independent. We have
$$
\newcommand{\P}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\V}{\mathbb V}
\P(Y_{ij} = y) = \sum_{x}\P(X_j = y \oplus x) \P(X_i = x) = 2^{-n},
$$
proving that they're uniform. It's clear that $Y_{ij}$ and $Y_{kl}$ are independent for $i,j,k,l$ distinct. In the case $l=i$, we have
$$ \begin{split}
\P(Y_{ij} = y_1 \wedge Y_{ik} = y_2)
&= \sum_{x}\P(X_j = y_1 \oplus x \wedge X_k = y_2\oplus x) \P(X_i = x) \\
&= \sum_{x}\P(X_j = y_1 \oplus x) \P(X_k = y_2\oplus x) \P(X_i = x) \\
&= 2^{-2n},
\end{split} $$
proving pairwise independence. Note that they're not 3-independent though, as $Y_{ij} \oplus Y_{ik} = Y_{jk}$.
Now let $I_{ij}^y$ be the indicator variable of the event that $Y_{ij}=y$, and let $I^y = \sum_{i<j}I_{ij}^y$. Let $J^y$ indicate that $I^y=0$, i.e. that we miss $y$. Let $p=2^{-n}$. We have $\E I^y = mp$ and $\V I^y=mp(1-p)$ (here we use pairwise independence). Using Cantelli's inequality (the one-sided version of Chebyshev), we get
$$
\E J^y 
= \P(I^y = 0) 
\le \P(I^y-\E I^y \le -\E I^y) 
\le \frac{\V I^y}{\V I^y + (\E I^y)^2}
= \frac{1-p}{1-p+mp}.
$$
Note that $m=2^{2n-5} - 2^{n-3}$, which gives us
$$
\E(\textrm{number of misses})
= \E\left(\sum_y J^y\right) 
\le 2^n \frac{1-p}{1-p+mp} 
< 32
$$
for all $n$. Since the expected number of misses is $<32$, there must exist some choice of the $X_i$'s that has $\le 31$ misses.
Note that if we had used Chebyshev instead of Cantelli, we would get the weaker result of $\le 32$ misses for $n\ge 8$.
By the way, here are the bounds way get for each $n$:
$$
\begin{array}{c|c}
n&1&2&3&4&5&6&7&8&9&\ge10 \\
\hline
\textrm{Bound}&(2)&(4)&7&11&16&22&26&28&30&31 \\
\hline
\textrm{Bound}/2^n &(1)&(1)&.86&.69&.50&.34&.20&.11&.059&\to0
\end{array}
$$
