Automorphism groups of self-dual codes

  • Automorphismengruppen selbstdualer Codes

Günther, Annika; Nebe, Gabriele (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2009)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2009


This thesis treats linear block codes, which are classically used in the storage and transmission of digital information. The dual of such a code is the orthogonal space with respect to a Euclidian or Hermitian scalar product. A code which equals its dual is called self-dual. Self-dual codes are of particular interest, for instance since invariant theory provides an overview of the possible weight distributions of these codes, which can be used to prove that certain codes are optimal in error recognition and error correction. The automorphism group of a linear code consists of those coordinate permutations which leave the code (as a set) invariant. Automorphisms establish a certain additional structure on a code. In the case of cyclic codes, for instance, which are invariant under a cyclic shift of the coordinates, this additional structure gives rise to more efficient algorithms for decoding. This thesis investigates linear codes from a representation theoretic point of view, i.e. a code is viewed as a module for the group algebra A over the ground field which is formed by the code's automorphism group. For a given permutation group G, necessary and sufficient criteria are developed for the existence of a self-dual G-invariant code. In particular, a characterization is given for the existence of a self-dual G-invariant Type II code. These are codes over a finite field of characteristic 2 which form a generalization of the so-called doubly-even binary codes. A binary code is said to be doubly-even if all of its Hamming weights are multiples of 4. Moreover, imitating the Kneser neighborhood method, an algorithm is developed to find all self-dual G-invariant codes. In the case where A is semisimple, formulae are given for the number of self-dual G-invariant codes, basically depending on the composition factors of one such code, viewed as an A-module. Using a result by Dickson it is proven that there exists a self-dual G-invariant Type II code of length N, which is a multiple of 8, if and only if G lies in the alternating group on N points and there exists a G-invariant self-dual code of length N (for the latter, an easy representation theoretic criterion is given). To this aim, self-dual Type II codes are viewed as self-dual isotropic subspaces of a quadratic space V, and the group G (as a subgroup of the symmetric group) is naturally embedded into the orthogonal group O of this space. As a subgroup of O, the group G acts on the set of all self-dual isotropic subspaces of V, and a code is G-invariant if and only if the corresponding subspace is stabilized by G. The stabilizer of a self-dual isotropic subspace of V always lies in the kernel of the so-called Dickson invariant, a homomorphism of O which restricts to the sign on the symmetric group. To determine the set of all self-dual G-invariant codes of length N, the neighbor graph of all such codes is introduced. Two codes C,D are adjacent in this graph if and only if their intersection is a maximal submodule of C. It is proven that the neighbor graph is always connected, such that one can determine the whole set of all self-dual G-invariant codes by starting with just one such code, successively computing neighbors in the graph. To illustrate this very efficient algorithm, for some simple groups G all binary codes are determined for which G embeds transitively in the automorphism group. The computation can be simplified using certain canonical automorphisms of the neighbor graph, such that the computation of neighbors can be restricted to orbit representatives of a certain group action. A criterion for the completeness of such a classification is provided by the above-mentioned formulae for the number of self-dual G-invariant codes, if the characteristic of the ground field does not divide the group order. These formulae are proven via a Morita equivalence, reducing the problem to the counting of self-dual linear codes, which is well understood.