Here in Wikipedia is written: "The automorphism group of the binary Golay code is the Mathieu group M23."

What is "automorphism group of code" ?


Are there other nice examples of relation between groups and codes ? E.g. if we take the most simple codes - Hamming codes what are their automorphism groups ?

  • 4
    $\begingroup$ For a binary code $C$ the automorphism group is just the group of permutations of the coordinates that permute $C$. (For a code of length $n$ over an arbitrary field $k$, it's the stabilizer of $C$ in the semidirect product of $S_n$ with $(k^*)^n$; when $|k|=2$ you don't see the $k^*$ factor.) For the Hamming code of length $7$ this is $GL_3({\bf Z}/2{\bf Z})$; for the extended Hamming code of length $8$, it's affine $GL_3$. This should be thoroughly explained in standard texts such as MacWilliams and Sloane. $\endgroup$ – Noam D. Elkies Mar 4 '12 at 19:23
  • $\begingroup$ I think it is the integral isometry group of an associated lattice. The three books I have in this direction are SPLAG by Conway and Sloane, more introductory Lattices and Codes by Wolfgang Ebeling, also From Error Correcting Codes Through Sphere Packing to Simple Groups by Thomas M. Thompson. I quite like the Ebeling book, see my answers to my own question at mathoverflow.net/questions/69444/… $\endgroup$ – Will Jagy Mar 4 '12 at 19:31
  • 1
    $\begingroup$ @W.Jagy: Aut$(C)$ is certainly contained in the isometries of the associated lattice (modulo $\lbrace \pm 1 \rbrace^n$), but sometimes there are other automorphisms: $E_7$ and $E_8$ have more isometries than you get from the Hamming and extended Hamming codes. $\endgroup$ – Noam D. Elkies Mar 4 '12 at 19:44
  • $\begingroup$ @Noam, I suspected something might be different, so I just mentioned the books. I've never paid attention to codes...Oh, about use of the @ sign, Gerry Myerson told me on MSE that the first three characters of the other person's on-site name are what matter, as far as them being informed by the software that there is a message and where it is. I'm guessing it is similar on MO. It is hard to tell if I see a message before the usual delay about being informed (the little envelope at the top of the page, next to my name, turns orange). $\endgroup$ – Will Jagy Mar 4 '12 at 20:04
  • 1
    $\begingroup$ The @user message notification is a SE 2.0 feature which does not work on MO at all. $\endgroup$ – Emil Jeřábek Mar 6 '12 at 17:09

The commenters got it right. The automorphism group of a binary code is the set of permutations of coordinates that stabilizes the code. If instead of using the binary alphabet we use a ternary, quaternary,... alphabet, then there is some variation in that some sources allows signed permutations of coordinates. After all, these are also automorphisms that preserve the Hamming distance (or Lee distance) between a pair of inputs. Whichever way gives you a more interesting group is the way to go!

In addition to the celebrated Golay codes (binary and ternary) some other families of codes have a useful group of automorphisms. I will list the Reed-Muller codes. These codes have length $n=2^m$, and the code $RM(r,m)$ has dimension $$ k=\sum_{i=0}^r{m\choose i}.$$ Their coordinate positions can naturally be put into a bijective correspondence with the vectors $v$ of the $m$-dimensional space $F_2^m$ over the field of two elements in such a way that all the the affine linear transformations $f_{A,u}:v\mapsto Av+u$ for all $A\in GL_m(F_2), u,v\in F_2^m$ become automorphisms of the codes. The Hamming codes belong to the hierarchy of Reed-Muller codes --- the extended Hamming code of length $2^m$ is the code $R(m-2,m)$. It is known (see MacWilliams & Sloane) that this is the full automorphism group of the code $RM(r,m)$, when $r\lt m-1$. The codes $RM(m,m)$ (resp. $RM(m-1,m)$) consists of all the binary words of length $2^m$ (resp. of all the binary words of an even weight), and both these codes are stable under all the permutations of the $2^m$ bit positions.

Also the extended BCH-codes have a useful group of automorphisms. In this case the bit positions can be put into a bijective correspondence between the elements $x$ of the finite field $F=GF(2^m)$. The codes can be defined by means of power sum equations, and it is easy to see that the affine linear mappings $x\mapsto ax+b, a\in F^*, b\in F$ are all automorphisms. Together with Frobenius automorphisms, $x\mapsto x^{2^i}$, those will form the entire group of automorphisms in many a case, but unfortunately I'm not up to speed about exactly when that happens. This is a much smaller group of automorphisms in comparison to that of the Reed-Muller codes. Yet, it is doubly transitive, and many an algebraic proof has been simplified by this fact.

  • $\begingroup$ @Jyrki Lahtonen Thank you for the answer! May I ask you to clarify. Do you mean that Affine transformations of F_2^m become automorphisms of Reed-Muller ? What parameters (n,k) of RM you mean ? $\endgroup$ – Alexander Chervov Mar 6 '12 at 11:33
  • $\begingroup$ Sorry about leaving it somewhat sketchy, @Alexander. Does it look clearer now? $\endgroup$ – Jyrki Lahtonen Mar 6 '12 at 16:36

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.