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

1

As I was commenting above, the three hypotheses imply that the three vectors are linearly independent, and span a (6,3,2) code, one which doesn't include the weight 6 word.

Switching to the dual code, $d=2$ this all means that the parity check matrix has to have 6 distinct nonzero columns from $\mathbb{F}_2^3$ whose sum is nonzero.

There are only 7 such columns possible, so I think this is an excellent angle of attack for the problem.

  • 0
    That reduces the brute force to 7 cases, at least!2012-05-09
  • 0
    Don't you need $d\ge3$ to exclude the possibility that there are no repeated columns in the check matrix? I think that you need to factor the existence of high weight vectors somehow. After all, there exists even a binary $(4,3,2)$ consisting of all even weight words.2012-05-09
  • 0
    You're right, I shouldn't have said "distinct". The above post was not meant as a complete solution, just an angle of attack.2012-05-09
0

The words $0,v_1,v_2,v_3,v_1+v_2,v_1+v_3,v_2+v_3,v_1+v_2+v_3$ form a group $C$ under addition. As observed by rschwieb, the given conditions imply that all the 8 vectors are distinct. We get six homomorphisms $f_i$ from $C$ to $\mathbb{Z}_2$ by mapping each vector to its bit at position $i$, $i=1,2,\ldots,6$. Because $|f_i(C)|$ is either 1 (if all the words have a zero at position $i$) or 2 (if both 1 and 0 occur at that position, we get that $|\mathrm{ker}(f_i)|$ is either 4 or 8. Therefore at each of the six bit positions we have a zero in either exactly 4 of the vectors of $C$, or in all 8 of them. Consequently, at each of the six bit positions we have a 1 in exactly four words, or a 0 in all 8 words.

Therefore the sum of the weights of the words of $C$ is divisible by four, and also $\le 4\cdot6=24$. OTOH the given inequalities imply that the sum of the weights is at least 23, so it must be exactly 24. Therefore the total "slack" (= the amount by which the inequality fails to be an equality) in these inequalities is exactly one.

We get a contradiction as follows. If all the vectors $v_i$ have an even weight, then so do the pairwise sums $v_i+v_j,i\neq j$. But the second set of inequalities then produce a total slack of three, which we showed to be impossible. So at least one of the vectors $v_i$ must have odd weight. In order for the first set of inequalities not to produce too much slack, exactly one of the vectors $v_i$, say $v_1$ must be of odd weight, and the other two must have weight four. But in this case $v_2+v_3$ has an even weight, and thus it will produce some slack in the second group of inequalities. Therefore the total slack would be at least two, which is also impossible.

  • 0
    But to be honest, a solution based on case-by-case study (using permutations to reduce the number of cases) is probably better. I was just having fun with the sum of weights. Hopefully you don't mind.2012-05-10