2
$\begingroup$

The set of all binary vectors with 12 components forms a field with 2^12 elements containing 000000000000 and another 65*63 elements. Is it possible to partition these elements into 65 subgroups of 63 vectors so that each of them is closed under binary addition (XOR)?

For example, if we had 4 components instead of 12, the field contains 0000 and another 3*5 elements, we can partition them as follows:

0000

0001 0010 0011

0100 1000 1100

0101 1010 1111

0110 1011 1101

0111 1001 1110

so that, whenever we add two elements from the same group, we get another from the same group. We have five subgroups closed under XOR that only share the element 0000. Could we do the same with vectors with 12 components? Is there some theorem that governs this property for more components?

Thank you!

Improve this question
$\endgroup$
3
  • $\begingroup$ No! but 65 groups of 63 might be possible. Your small example was 5 groups of 3, not 3 groups of 5. $\endgroup$
    – Aaron Meyerowitz
    Commented Apr 14, 2015 at 17:51
  • $\begingroup$ A set of (non-zero) binary vectors closed under XOR has size $2^k-1$ where $k$ is the size of the largest independent set. $\endgroup$
    – Aaron Meyerowitz
    Commented Apr 14, 2015 at 18:13
  • $\begingroup$ You are right, stress and lack of sleep are screwing with my mind... I corrected the question $\endgroup$
    – bpel
    Commented Apr 14, 2015 at 18:32

1 Answer 1

Reset to default
9
$\begingroup$

$\mathrm{GF}(2^{12})$ is a two-dimensional vector space over $\mathrm{GF}(2^6)$. The one-dimensional subspaces are all disjoint (barring the zero vector), and contain 63 nonzero elements each.

Improve this answer
$\endgroup$

You must log in to answer this question.

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