"Combinatorial constructions under group actions"

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:

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* ([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

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.

harald.fripertinger@kfunigraz.ac.at,

last changed: January 23, 2001