2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Presumably you can say $(1000)+(1000) =(0000)$ but that only adds $1$ or at most $2^{n-2}$ to your answer $\endgroup$
    – Henry
    Jul 12, 2021 at 9:03
  • $\begingroup$ By adding we can get some more. My question is how many more can we get ? Ofcourse zero at the end can be obtained in that way. $\endgroup$
    – Mathslover shah
    Jul 12, 2021 at 9:06
  • $\begingroup$ If you had started with $(1000),(0100),(0010),(0001)$ and could reuse outputs then you can get everything. If you had started with $(1110),(1100),(1010),(1000)$ then you cannot generate $(0001)$ or anything ending in $1$. Similarly for other $n>4$ $\endgroup$
    – Henry
    Jul 12, 2021 at 9:09
  • $\begingroup$ We can not get everything as I have written I have 4 of them and 2- sums are only 6 so maximum 10 can possibly be obtained but there are $15= 2^{4} -1$. When n = 5 we take 8 of them and 2 - sums are ${8 \choose 2} = 28$ so total 36. It seems we can get all of the $2^{5} - 1$ but I guess this is not possible and that is what my question asks why and how. $\endgroup$
    – Mathslover shah
    Jul 12, 2021 at 9:17
  • 1
    $\begingroup$ There are $2^{n-1}$ binary sequences that do not have the first bit set. If you choose your $2^{n-2}$ sequences from those, no combination of them will ever produce a sequence with its first bit set, even if you add more than 2 together. $\endgroup$
    – Jaap Scherphuis
    Jul 12, 2021 at 14:13

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I highly appreciate your effort and the result. Although I cant understand this probabilistic approach. But it seems that for bigger $n$ we can have this equal to zero and hence we can fine a set which generate all of the elements ? $\endgroup$
    – Mathslover shah
    Jul 14, 2021 at 13:07
  • $\begingroup$ The point of the method is that, if the average number of misses with random samples is some value, then there must be a possible sample with at most that value (and also a sample with at least that value) - otherwise the average would be larger (or lower). Unfortunately my bound approaches $32$ as $n\to\infty$, so we can’t get anything better from this analysis. $\endgroup$
    – Milten
    Jul 14, 2021 at 16:41
  • $\begingroup$ @Mathslovershah Just for completion, I made a table showing the exact bound I get for each $n$. I also wanna add that this result really makes me think the problem is possible, since we are able to miss so few (a constant bound!) for any $n$. Unless of course I messed up somewhere. $\endgroup$
    – Milten
    Jul 14, 2021 at 18:24
  • $\begingroup$ Ok may be that we also check if how much the repetition occurs in the sums values. $\endgroup$
    – Mathslover shah
    Jul 14, 2021 at 20:10
  • $\begingroup$ Also what if the we take normal carry addition in binary sequences instead of XoR. My guess was that the repetitions also occur so often that we miss some value. Also every number can be written as binary sum ($ 37 = 2^{5} + 2^{2} + 2^{0}$) so when we take a smaller set we must have alot of repetitions. But for bigger $n$ this might not be the case. $\endgroup$
    – Mathslover shah
    Jul 14, 2021 at 20:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .