The project "Combinatorial constructions under group actions" P12642-MAT was mainly devoted to the classification, enumeration, construction and random generation of linear codes and regular matroids. 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:
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 GF(q). These classes can be represented as orbits of k-dimensional linear subspaces of GF(q)n under the action of the full monomial groups GF(q)* wr Sn (cf. [11]). Applying various methods from algebraic combinatorics (cf. [13]) it is possible to describe them as orbits of functions from {1,...,n} to the projective geometry PGk-1(q) under the action of the direct product PGLk(q)´Sn of projective linear groups and symmetric groups.
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 ([4]) 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 [16]. Details about random generation of linear codes can be found in [10]. 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. 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.
Matroids are a combinatorial model for independence structures, generalizing different types of dependency relations like for instance linear dependency and algebraic dependency. In this general setting we are speaking of independent and dependent sets, of bases and rank functions of closure operators, hyperplanes and closed sets. A matroid, which can be described by linear dependency in a vector space over a field K is called K-linear. Regular matroids are K-linear for any field K. Considering certain connections between isometry classes of linear codes and the isomorphism classes of binary matrix-matroids, we succeeded in implementing an algorithm which checks binary matroids for regularity. These ideas go back to M. Wild [17][18]. The isomorphism classes of binary matrix matroids can be described as orbits under group actions. Orbit representatives are then checked for regularity by applying a theorem of R. E. Bixby [3]. This way we are checking whether the given matroid is a series extension of the Fano or the dual Fano matroid. By doing this we get some further information about these matroids, for instance the set of all hyperplanes of it, or the set of all closed sets (of given rank). An article collecting all these results is just in preparation.
Furthermore a program was developed in SYMMETRICA which computes generator matrices of binary linear (n,k)-codes of given minimum distance. And there exists a database program in SYMMETRICA for handling binary codes of optimal minimum distance. It manipulates both lower and upper bounds for the minimum distance and generator matrices of binary (n,k)-codes as it is described in the first chapter of [2]. It allows to compute various new codes from a given code by parity check columns, punctuation, shortening, A-construction, Y1-construction and B-construction, direct sum, (u,u+v)-construction or by the tensor product.
The methods of enumeration, construction and random generation of linear codes were generalized to the classification of block codes. The corresponding paper [6] was published in the journal "Design, Codes and Cryptography".
Many of these computational results on codes and matroids were put into "Sloane's On-Line Encyclopedia of Integer Sequences" [15].
Mathematical music theory was another research topic. (Maybe it was not described so explicitly in our research plan, but an invitation to write a longer survey article on this topic and lectures given at three conferences were changing our plans.) The article [9] dealing with the enumeration of mosaics appeared in Discrete mathematics. It 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][12]) can be done by describing orbits of partitions under certain group actions. Harald Fripertinger was presenting these results at two scientific meetings: First at the conference Algebraic Combinatorics and Applications in Gößweinstein (Germany), which was dedicated to the 60-th birthday of Prof. A. Kerber, and then at the 7. Österreichisches Mathematikertreffen in Graz. In addition to this he gave a survey lecture on Enumeration and Construction in Music Theory at the Diderot Forum on Mathematics and Music, which took place in Vienna. A summary of this talk [8] was published in the conference proceedings. Furthermore Harald Fripertinger was invited by M. Boroda, who is the editor of "Musikometrika", to prepare an article about enumeration and construction of motives. This article [7] will appear in a special issue of Musikometrika, which will be dedicated to the concept of motives. This article describes in all details how the number of essentially different (i. e. not similar) motives can be computed and how to construct a (complete) system of representatives of motives. This paper is quite long since all necessary mathematical notions and definitions concerning sets, functions, permutations, elementary number theory, group theory, permutation groups and group actions are presented.
Together with the supervisor of this project an article [14] is prepared which is dealing with some functional equations in, and applications of group actions to astronomy.
In [5] 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". Even though the page proofs for [5] were already corrected the article is still not printed.