Introduction

Introduction

The methods and results presented in this paper are interesting in the framework of classification of discrete structures [13],[10]. Very often discrete structures can be described as equivalence classes of certain objects. If these equivalence classes can be expressed as orbits under a group G acting on a set X -- i.e. there is a mapping G × X→ X, (g,x)↦ gx such that g₁(g₂x)=(g₁g₂)x and 1x=x -- then there exist some combinatorial and algebraic methods for the classification of these structures. For instance each element in the discrete structure of unlabelled graphs can be considered as the set of all possible labellings of a given graph which is the orbit of a labelled graph under the action of the symmetric group; or the isometry classes of block-codes are orbits of special wreath-products. In a first step one can enumerate these structures by applying the Cauchy-Frobenius-Lemma, which says that the number of G-orbits is the average number of fixed points

^._. 1

|G|
^._.
∑
g∈ G |X_g|, X_g := {x∈ X | gx=x}. ^._.

In a second step certain properties of these structures can be described by weight functions or by their stabilizer (the stabilizer of x∈ X is the subgroup G_x := {g∈ G | gx=x} of G) and the numbers of structures with these additional properties can be computed by the Pólya-de Bruijn-Redfield-Theory or by Burnsides Lemma. The more details of a structure are specified and prescribed by parameters the closer comes the enumeration procedure to the construction of all structures with given properties. The most ambitious task is the computation of complete lists of representatives of a discrete structure, which can be done by arranging both algebraic and combinatorial algorithms in a very tricky way. Having computed these lists we can investigate each representative for its properties. When the numbers of representatives get too large in order to compute complete lists, it is useful, helpful and makes sense to compute representatives uniformly at random. This way we can produce unprejudiced lists of representatives which can be used to check hypotheses on them and afterwards we can try to prove the valid ones.

Let A be a finite alphabet, then an [n,m] block code C over A is an m-subset of Aⁿ. In order to describe the isometry classes of block codes we need the notion of wreath products. The wreath product S_A≀ S_n is a group formed by a set {(ψ,π) | ψ∈ S_Aⁿ, π∈ S_n} with multiplication (ψ,π)(ψ', π')=(ψψ'_π, ππ'), where ψψ'_π(i) := ψ(i)ψ'_π(i) and ψ'_π(i) := ψ'(π^-1i). (For more details on group actions and wreath products cf. [12].)

Two [n,m] codes C₁ and C₂ will be called equivalent, if and only if there is some (ψ,π) in the full monomial group S_A≀ S_n such that

C₁=(ψ,π)(C₂) := {(ψ,π)f | f∈ C₂},^._.

where (ψ,π)f(i)=ψ(i)f(π^-1i). (I.e. S_A≀ S_n acts in form of the exponentiation on Aⁿ which induces an action on the set of all subsets of Aⁿ.) The equivalence classes under this group action are exactly the isometry classes of [n,m] codes.

In previous papers [6][4][3][5] we were dealing with the enumeration of isometry classes of linear (n,k) codes over a finite field GF(q). In this situation we had to determine the number of isometry classes of k-dimensional subspaces of GF(q)ⁿ, which can be described as orbits under the action of GF(q)^*≀ S_n. Of course, each linear (n,k)-code over GF(q) is an [n,q^k] block code.

harald.fripertinger "at" uni-graz.at, May 10, 2016

Introduction