What is "automorphism group of an error-correcting code" ?

Question

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

What is "automorphism group of code" ?

PS

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 ?

Answer 1

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.

Answer 2

Here is a view point from the application side.

A codebook $\mathscr C$ of length $n$ over an alphabet $\Sigma$ is a subset $\mathscr C \subset \Sigma^n$. The automorphism group $\mathrm{Aut}(\mathscr C)$ of a codebook is the subset of permutations on $\{1,2,\dotsc,n\}$ (which acts on $\Sigma^n$) that fix $\mathscr C$.

Code designers prefer codes with more structures; so the alphabet $\Sigma = \mathbb F_q$ is usually taken to be finite fields, especially $\mathbb F_2$; less commonly the alphabet is taken to be a ring, such as $\mathbb Z/4\mathbb Z$. Once the field structure is given, code designers will focus on codebooks (subsets of $\mathbb F_q^n$) that happen to be subspaces of $\mathbb F_q^n$. This is the case for all codes mentioned in this page: Hamming, Golay, Reed--Muller, BCH, and their extended versions are all linear codes. And hence the discussion of automorphisms of codes is commonly limited to those codes who already have a lot of algebraic structures. [1]

IMO, there are several reasons why code designers like to talk about automorphism groups:

• It is easier to design the decoder if you have a big Aut.

  • Example: The optimal decoder of the first-order Reed--Muller RM$(1, m)$ is basically a majority voting system, where the "voters" are vectors in $\mathbb F_2^m$.
  • Example: Some belief-propagation decoder of polar codes uses the Aut of RM codes (not the Aut of polar codes) to permute the Tanner graph.

• It is easier to analyze the code performance if its Aut is big enough. Example:

  • Reed--Muller codes achieving capacity over binary erasure channels. The proof uses the fact that the Auts are $2$-transitive.
  • The computation of code invariants, such as weight enumerators and Tutte polynomials, may be 10x or 100x faster if you can "quotient" the computation by the Aut.

• The general paradigm has that the performance of a code is linked to the size of its Aut.

  • Example: Golay codes are so good and have large Auts.
  • Example: Even for codes that are known to be good for other reasons, people would try to figure out its Aut for the sake of "maybe we can improve this code by making Aut larger".

More on the very last bullet point.

Recently, as polar codes succeed in practice, people start looking at ways to improve polar codes further. It is reported that RM codes perform better (in fact, nearly optimal) if a high-complexity decoder is used. So one promising path is to make polar codes, which usually assume a low-complexity decoder, "more RM" and see what we got. The latest result I am aware of proves that almost-RM codes achieve constant rates over binary symmetric channels. [2002.03317]

Hope that RM can achieve capacity over BSC and confirm the long-standing conjecture.

Footnote

[1] Making the codebook a subspace is good in practice because a cellphone/satellite can simply implement an injective linear map $\mathscr E: \mathbb F_q^k \to \mathbb F_q^n$ to encode messages, where $k$ is the dimension of $\mathscr C$ as a vector space over $\mathbb F_q$.