4
$\begingroup$

I have a question that involves showing there do not exist vectors $v_1,v_2,v_3 \in \mathbb{Z}_2^6$ such that:

$wt(v_i)\geq4$ for $i \in \{1,2,3\}$

$wt(v_i+v_j)\geq3$ for $i \in \{1,2,3\}$

$wt(v_1+v_2+v_3)\geq2$

where $\mathbb{Z}_2^6$ is the set of binary words of length 6 ($\mathbb{Z}_2$ can be considered as the set of residue classes mod 2, and addition as residue class addition).

and $wt(v)$ is the weight function (the number of 1's in the vector v).


I originally tried finding vectors in $\mathbb{Z}_2^6$ that did satisfy the three conditions above, and couldn't, only to give up and look at the mark scheme, which mentions that the above should be simple to show.

Any hint would be appreciated.

Thanks in advance :)

  • 0
    too much interesting +12012-05-09
  • 0
    what does $\ \mathbb{Z}_2^6$ means?2012-05-09
  • 0
    See the answers to [this question](http://math.stackexchange.com/q/108276/15941)2012-05-09
  • 0
    @dato: It may not have been clear...I've edited my question.2012-05-09
  • 0
    ok thanks @maliky0_o i see2012-05-09
  • 0
    You could always do this by exhaustion, there are only 15+6+1 vectors that satisfy #1! (That's not a good answer, it's just supposed to make you feel like you have an escape plan...)2012-05-09
  • 0
    @rschwieb: Thanks, it didn't occur to me :). But out of the 22 choices for one of the $v_i$'s, you'd have $\binom{22}{3}=1540$ sets of $v_1,v_2,v_3$ to consider (I think...)2012-05-09
  • 0
    Random observations: condition #2 prevents the weight 6 word from being included. Conditions #1+#2+#3 say that the $v_i$ are linearly independent, and that they form a code with minimum distance 2. I can't think of a good reason why a (6,3,2) N-k-d code couldn't exist at the moment... perhaps it does, but it doesn't fit the description above.2012-05-09
  • 0
    @malikyo_o, you're right in theory. However, if some triple $v_1,v_2,v_3$ works, then so will any other triple gotten from this by permuting the six bit positions any which way you want. Consequently we are at liberty to assume that $v_1$ begins with a run of 1s, and ends with a run of 0s. Furthermore, we can assume that $wt(v_1)$ is at least as high as $wt(v_2)$ and $wt(v_3)$. Do you want to try it systematically that way yourself, or would you like me to give you a few more hints?2012-05-09
  • 0
    (cont.) taking that permutations idea a bit further. Let us look at the common 1s shared by $v_1$ and $v_2$. By permuting, we can put these into the beginning, so $v_1$ will be one of $111100$, $111110$, $111111$ (actually rschwieb already explained, why the last cannot occur). Then $v_2$ will also begin with at least two ones (because it will necessarily overlap with those of $v_1$ at at least 2 positions), and after its first zero, it can have any further 1s only at positions, where $v_1$ has 0s. There are not too many cases remaining, me thinks.2012-05-09

2 Answers 2