Automorphism groups of self-dual codes

Günther, Annika; Nebe, Gabriele

doi:29439

Automorphism groups of self-dual codes = Automorphismengruppen selbstdualer Codes

Günther, Annika (Author)

2009

Verantwortlichkeitsangabevorgelegt von Annika Günther

ImpressumAachen : Publikationsserver der RWTH Aachen University 2009

Umfang149 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2009

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Nebe, Gabriele (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2009-08-28

Online
URN: urn:nbn:de:hbz:82-opus-29402
URL: https://publications.rwth-aachen.de/record/51261/files/Guenther_Annika.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Code (Genormte SW) ; Nachbarschaftsgraph (Genormte SW) ; Morita-Äquivalenz (Genormte SW) ; Darstellungstheorie (Genormte SW) ; Existenz (Genormte SW) ; Modul (Genormte SW) ; linearer Code (Genormte SW) ; Typ 2 (Genormte SW) ; Mathematik (frei) ; Typ II (frei) ; linear code (frei) ; neighbor graph (frei) ; dickson invariant (frei) ; type II (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 11T71

Kurzfassung
Diese Arbeit behandelt klassische lineare Blockcodes, wie sie zur Fehlererkennung und Fehlerkorrektur bei der Übertragung und Speicherung von Daten verwendet werden. Der duale Code zu einem solchen linearen Code ist der Orthogonalraum bezüglich eines Euklidischen oder Hermiteschen Skalarprodukts. Ist ein Code mit seinem dualen Code identisch, so heißt er selbstdual. Selbstduale Codes sind von besonderem mathematischen Interesse, zum Beispiel da die Invariantentheorie einen Überblick über mögliche Gewichtszähler liefert und somit den Nachweis erbringen kann, das gewisse Codes optimale fehlerkorrigierende Eigenschaften haben. Die Automorphismengruppe eines Codes besteht aus den Koordinatenpermutationen, die den Code (als Menge) invariant lassen. Besitzt ein Code gewisse Automorphismen, so verleiht ihm dies zusätzliche Struktur. Im Fall der zyklischen Codes etwa, die invariant sind unter zyklischer Koordinatenpermutation, ermöglicht diese zusäzliche Struktur besonders effiziente Decodieralgorithmen. In der vorliegenden Arbeit werden Codes aus darstellungstheoretischer Sicht betrachtet, das heißt, ein Code wird als Modul über der Gruppenalgebra A aufgefasst, die durch seine Automorphismengruppe über dem Grundkörper gebildet wird. Für eine gegebene Permutationsgruppe G werden in bestimmten Fällen notwendige und hinreichende Kriterien für die Existenz eines G-invarianten selbstdualen Codes bestimmt. Insbesondere wird die Situation charakterisiert, in der ein selbstdualer G-invarianter Typ II-Code existiert. Dies sind Codes über Körpern der Charakteristik 2, die eine Verallgemeinerung der doppelt geraden binären Codes darstellen, Ein binärer Code heißt doppelt gerade, falls die Hamming-Gewichte aller Codewörter durch 4 teilbar sind. Weiter wird in Anlehnung an die Knesersche Nachbarschaftsmethode ein Verfahren entwickelt, mit dem sich die Menge C aller selbstdualen G-invarianten Codes algorithmisch bestimmen lässt. Es werden Formeln entwickelt, mit denen sich die Anzahl der selbstdualen G-invarianten Codes a priori, im Wesentlichen aus den Kompositionsfaktoren eines solchen Codes, aufgefasst als A-Modul, bestimmen lässt, falls A halbeinfach ist. Unter Zuhilfenahme eines Ergebnisses von Dickson wird bewiesen, dass genau dann ein selbstdualer G-invarianter Typ II-Code einer durch 8 teilbaren Länge N existiert, wenn G in der alternierenden Gruppe auf N Punkten liegt und ein selbstdualer G-invarianter Code der Länge N existiert (hierfür wird ein einfaches darstellungstheoretisches Kriterium gegeben). Dazu werden selbstduale Typ II-Codes als selbstduale isotrope Teilräume eines quadratischen Raums V beschrieben und G auf natürliche Weise in die orthogonale Gruppe O dieses quadratischen Raums eingebettet. Als Untergruppe von O operiert G auf dem der Menge aller selbstdualen isotropen Teilräume von V, und ein selbstdualer Typ II-Code ist G-invariant genau dann, wenn der entsprechende Teilraum von V unter G stabilisiert wird. Der Stabilisator eines selbstdualen isotropen Teilraums von V liegt nun im Kern der sogenannten Dickson-Invariante, eines Homomorphismus von O, der auf der symmetrischen Gruppe zum Signum einschränkt. Zur algorithmischen Bestimmung aller G-invarianten selbstdualen Codes der Länge N wird der Nachbarschaftsgraph aller solcher Codes eingeführt. Zwei Codes C,D sind adjazent in diesem Graphen genau dann, wenn ihr Schnitt ein maximaler Teilmodul von C ist. Es wird bewiesen, dass dieser Graph stets zusammenhängend ist und daher die Menge aller selbstdualen G-invarianten Codes durch sukzessive Berechnung von Nachbarn bestimmt werden kann, sobald ein einziger solcher Code bekannt ist. Zur Illustration werden für gewisse einfache Gruppen G alle selbstdualen binären Codes bestimmt, deren Automorphismengruppe eine transitive Untergruppe enthält, welche isomorph zu G ist. Die Berechnungen werden durch gewisse kanonische Automorphismen des Nachbarschaftsgraphen erleichtert, indem der Nachbarschaftsalgorithmus auch auf die Suche nach Bahnenvertretern beschränkt werden kann. Ein Kriterium für die Vollständigkeit einer solchen Klassifikation liefern die Formeln zur Bestimmung der Anzahl aller selbstdualen G-invarianten Codes, falls A halbeinfach ist. Diese Formeln werden mit Hilfe einer Morita-Äquivalenz bewiesen, die das Problem der Anzahlbestimmung im Wesentlichen auf das wohlbkannte Problem der Anzahlbestimmung linearer selbstdualer Codes reduziert.

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.

Fulltext:
PDF