most recent 30 from http://mathoverflow.net 2013-05-24T01:25:51Z http://mathoverflow.net/feeds/question/90218 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90218/what-is-automorphism-group-of-an-error-correcting-code Alexander Chervov 2012-03-04T18:57:16Z 2012-03-06T12:20:48Z

<p><a href="http://en.wikipedia.org/wiki/Binary_Golay_code" rel="nofollow">Here </a> in Wikipedia is written: "The automorphism group of the binary Golay code is the Mathieu group M23." </p> <p>What is "automorphism group of code" ? </p> <p>PS</p> <p>Are there other nice examples of relation between groups and codes ? E.g. if we take the most simple codes - <a href="http://en.wikipedia.org/wiki/Hamming_code" rel="nofollow">Hamming codes</a> what are their automorphism groups ?</p>

http://mathoverflow.net/questions/90218/what-is-automorphism-group-of-an-error-correcting-code/90348#90348 Jyrki Lahtonen 2012-03-06T10:55:08Z 2012-03-06T12:20:48Z

<p>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!</p> <p>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 <a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Muller_code" rel="nofollow">Reed-Muller codes</a>. 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 &amp; 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.</p> <p>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.</p>