"Combinatorial constructions under group actions"

During the last year most of the work in the project "Combinatorial constructions under group actions" P12642-MAT was devoted to the classification, enumeration, construction and random generation of linear codes. This work was based on results partially derived in the previous project "Construction of finite structures" P10189-PHY. All the old and new results of the last years were now collected into a text book "Codierungstheorie" [2] published at Springer. In international cooperation with the "Lehrstuhl II für Mathematik der Universität Bayreuth" it was possible to write this book. It serves both as an introduction to coding theory, and as a demonstration of the results achieved in joint work on the classification of linear codes.

Professor Adalbert Kerber wrote in the preface of this book:

Besonderer Dank der Autoren gilt der
Deutschen Forschungsgemeinschaft und dem Österreichischen Fonds zur
Förderung der wissenschaftlichen Forschung für hilfreiche finanzielle
Unterstützung begleitender Forschungsprojekte. Die Durchführung
dieser Projekte hat viel zur Vertiefung der Theorie beigetragen,
sie hat zu Implementierungen entsprechender Programme und zum Sammeln
umfangreichen Datenmaterials geführt.

When speaking about classification of linear codes, we are mainly
interested in describing the
*isometry classes* of *linear (n,k)-codes* over a finite field

When classifying objects under a group action you are generally interested in
complete lists of orbit representatives. (Group actions are often diminishing
the numbers of objects dramatically when collecting equivalent objects to one
orbit, here in the case of codes, all isometric codes to one isomorphism class
of codes.) In situations where there are still too
many representatives probabilistic methods can be applied for generating orbit
representatives uniformly at random. I. e., for any orbit the probability that
a generated representative belongs to this orbit does not depend on the
special choice of the orbit. For all orbits this probability is the
fraction 1 divided by the number of different orbits.
The *Dixon-Wilf-algorithm* ([3]) describes such a
probabilistic method. During the last year it was adopted to the random
generation of linear codes
and implemented in the computer algebra system SYMMETRICA [11].
Details about random generation of linear codes can be found in
[7]. This paper was submitted to Aequationes mathematicae, where in
the meantime it is already accepted for publication. Moreover Harald
Fripertinger was presenting these ideas in a lecture at the 41-st Séminaire
Lotharingien de Combinatoire in Domaine Saint-Jacques, Saint-Nabor, in March
1998.
During the year we were generating millions of codes to various parameters
uniformly at random and we were checking them for certain properties.
For instance
we were analyzing the distribution of the *minimum distances* of
*(n,k)*-codes for given parameters *n* and *k*.

Furthermore a program was developed in SYMMETRICA which computes
generator matrices of binary linear *(n,k)*-codes of given minimum distance.
And a database program for handling the optimal minimum distance of linear
codes of length *n* and dimension *k* was implemented. It manipulates lower
and upper bounds for the minimum distance of *(n,k)*-codes as it is described
in the first chapter of [2].

The methods of enumeration, construction and random generation of linear codes
were generalized to the classification of *block codes*. The
corresponding paper [5] was published in the journal "Design,
Codes and Cryptography".

Two further articles were accepted for publication. Their final versions were partially rewritten according to the latest results and to the referees suggestions.

- [6], which will appear in "Discrete Mathematics", describes an application of methods of algebraic combinatorics to a problem stated in music theory. The classification of mosaics (which often occur while analyzing twelve tone compositions, cf. [1][9]) can be done by describing orbits of partitions under certain group actions.
- In [4] details about the enumeration of endofunctions
of given cycle type are presented.
For doing this both methods from
*combinatorial species theory*and basic methods from*enumeration under group actions*can be applied. This article will be published in "The Annales des Sciences Mathematiques du Quebec".

harald.fripertinger@kfunigraz.ac.at,

last changed: January 23, 2001