Recall that a binary code is a subgroup $C \subset \mathbb F_2^n$; the elements of $C$ are called code words. The Hamming weight of a code word $c\in C$ is the number of $1$s in it. A binary code is self-dual if $C = C^\perp := \{v \in \mathbb F_2^n : \langle v,c\rangle = 0\in \mathbb F_2\}$. Self-dual codes automatically satisfy that all code words have Hamming weight divisible by $2$ (since every element must be orthogonal to itself).

There are many applications for binary codes in which all Hamming weights are divisible by $4$. A famous theorem says that a self-dual code of this type can exist only when $n$ is a multiple of $8$.

Do there exist self-dual codes all of whose Hamming weights are divisible by $8$? What is the smallest one? What dimensions do they exist in?

Note that the binary Golay code, related to the famous Leech lattice, is not of this type, since it has code words with Hamming weight $12$.

  • $\begingroup$ See comments about McEliece's theorem in authors.library.caltech.edu/3411/1/KATieeetit06.pdf (For a cyclic code) McEliece’s theorem relates the highest power of $2$ (more generally $p$) dividing all the Hamming weights of codewords in to the set of zeroes of the check polynomial, (and they discuss generalizations) $\endgroup$ – post.as.a.guest Oct 8 '16 at 7:24
  • $\begingroup$ @post.as.a.guest Thanks! I probably don't want a cyclic code --- the codes that already show up in what I'm working on are things like Ham(8,4) and extended Golay, neither of which is cyclic. $\endgroup$ – Theo Johnson-Freyd Oct 8 '16 at 21:59

Just noticed this question now. No, there are no such self-dual codes beyond the trivial one of length zero.

One way to see this is to mimic the proof of Gleason's theorem: the weight enumerator $W_C(X,Y)$ would have to be invariant under $(X,Y) \mapsto (2^{-1/2}(X+Y), 2^{-1/2}(X-Y))$ (MacWilliams identity) and also $(X,Y) \mapsto (X,e^{2\pi i/8} Y)$. But those linear transformations generate a subgroup of $U_2({\bf C})$ whose image in $PU_2({\bf C})$ is dense, so there are no nonconstant invariant polynomials. [Replacing $e^{2\pi i/8}$ by $i = e^{2\pi i/4}$ yields the group for weight enumerators of Type II codes, whose image in $PU_2({\bf C})$ is the octahedral group -- which is known to be a maximal closed subgroup of $PU_2({\bf C})$, so adding the generator $(X,Y) \mapsto (X,e^{2\pi i/8} Y)$ yields a dense subgroup.]

  • $\begingroup$ Great. I suspected as much, given the way Gleason theorem is stated, but am glad to confirm. $\endgroup$ – Theo Johnson-Freyd Nov 20 '16 at 4:58

We say the Code $C$ is formally self-dual (f.s.d) if the codes $C$ and $C^\perp$ have identical weight distribution. So, a self dual code is f.s.d. Also, f.s.d, code is divisible if there exists an integer $\Delta >1$, such that $\Delta$ divides all the non-zero weights in the code. By $Gleason$-$Pierce$ theorem, there is a complete classification of f.s.d codes over arbitrary field. For your case, you must have $\Delta=8$. There is not simple classification in this case. One approach can be as follows: find $Type$ $II$ self-dual code and then compute $H:=C\otimes C$. So, it seems that the smallest one of such codes depends to smallest $Type$ $II$ code. Also, I think the paper Paper is useful for further studying to answer your question.

  • $\begingroup$ Thanks! But I am confused about two things. First, I've always taken the statement of Gleason--Pierce as allowing $\Delta = 8$ among the Type II cases, but perhaps that is a misreading? Second, I believe that $C \otimes C$ is not self-dual. Indeed, if $C$ is self-dual, then its dimension is half the ambient dimension, so then $C \otimes C$ should have dimension 1/4 the ambient dimension. $C \oplus C$ is self-dual, but does has the same $\Delta$ as has $C$. $\endgroup$ – Theo Johnson-Freyd Oct 8 '16 at 15:19
  • $\begingroup$ On the other hand, starting with $C\otimes C$ is what I would like to do. Note that if $C$ is Type II, then for $C\otimes C$ we have $\Delta = 16$, since it is multiplicative for tensor product. Perhaps there is room to fit in some more codewords to build up a self-dual code, at the cost of dropping $\Delta$ to $8$. (Whether there is room of course will depend on $C$.) $\endgroup$ – Theo Johnson-Freyd Oct 8 '16 at 15:23
  • $\begingroup$ Sorry, it's not multiplicative. Take $Ham(8,4) \otimes Ham(8,4)$. The "pure" words, of the form $a \otimes b$ for $a,b \in Ham(8,4)$, have Hamming weight 16. (Assuming neither $a$ nor $b$ is $0$ or $(1,1,\dots,1)$.) But if $a \neq a'$ and $b\neq b'$ then typically $\langle a \otimes b, a' \otimes b'\rangle = \langle a ,a' \rangle \langle b,b' \rangle = 2\cdot 2$, where $\langle,\rangle$ counts the number of spots where the words are both "1" (so that $\langle a,a\rangle = $ weight of $a$), and so $a\otimes b + a'\otimes b'$ has Hamming weight $16 + 16 - 2\cdot 4 = 24$. $\endgroup$ – Theo Johnson-Freyd Oct 8 '16 at 17:56
  • $\begingroup$ You are right. $C\otimes C$ is not self-dual in general, if $C$ is self-dual. Also, as you confused I am confused too about $\Delta=4$. But I think the theorem do not say about the case $\Delta=8$. $\endgroup$ – Shahrooz Janbaz Oct 9 '16 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.