It is demonstrated how classes of linear (n,k)-codes can be enumerated using cycle index polynomials and other methods from algebraic combinatorics.

At first let me draw your attention to the enumeration of linear
codes. Let p be a prime and let q be a power of p then GF(q)
denotes the finite field of q elements. A *linear
(n,k)-code* over the Galois field GF(q) is a k-dimensional
subspace of the vector space GF(q)^{n}. As usual codewords
will be written as rows x=(x_{1},...,x_{n}). A k ×
n-matrix Γ over GF(q) is called *a generator matrix*
of the linear (n,k)-code C, if and only if the rows of Γ form
a basis of C, so that C={x⋅ Γ | x∈
GF(q)^{k}}. The *Hamming distance* d(x,y) :=
|{i∈ __n__ | x_{i} ≠ y_{i}}| is a metric
on GF(q)^{n}. (The set of integers from 1 to n will be
indicated as __n__.) The *minimal distance* d(C) of a
code C is given by

It can be used to express the quality of a code. A

d(C) := min _{(x,y)∈ C2, x ≠ y}d(x,y).^{.}_{.}

In coding theory two linear (n,k)-codes
C_{1},C_{2} are called *equivalent*, if and
only if there is an isometry (with respect to the Hamming metric)
which maps C_{1} onto C_{2}. This means there is a
linear isomorphism φ: C_{1}→ C_{2} such
that d(x,y)=d(φ(x),φ(y)) for all x,y∈ C_{1}.
It can be shown that such a linear isometry between two linear
(n,k)-codes can always be extended to an isometry of
GF(q)^{n}. (See [10].) Let's investigate the
structure of the group of all linear isometries of
GF(q)^{n}. It is enough to consider an isometry φ
acting on the standard basis {e_{1},..., e_{n}}
where e_{i}=(δ_{i,j})_{j∈
n}. Since φ is a homomorphism,
φ(e_{i})=∑_{j=1}^{n}α_{i,j}e_{j},
where α_{i,j}∈ GF(q). Since φ is an
isometry, for each i there is exactly one j such that
α_{i,j} ≠ 0. This defines a function π:
__n__→ __n__ such that α_{i,π(i)} ≠
0 and φ(e_{i})=α_{i,π(i)}
e_{π(i)}. Since φ is an isomorphism, π must be a
permutation, i.e. π∈ S_{n}. Let's define
ψ(i) := α_{i,π(i)}, then ψ is a mapping
from __n__ to GF(q)^{*} (where GF(q)^{*} denotes
the multiplicative group of the Galois field), and φ can be
identified with the pair (ψ,π). Then the group of all
isometries corresponds to the *wreath product*

which is the semidirect product of GF(q)

GF(q) ^{*}≀ S_{n}= {(ψ,π) | ψ∈ GF(q)^{*}^{n}, π∈ S_{n}},^{.}_{.}

where ψψ

(ψ,π)(ψ',π') = (ψψ _{π}',ππ'),^{.}_{.}

For computing the number of

GF(q) ^{*}≀ S_{n}× GF(q)^{n}→ GF(q)^{n}, ((ψ,π),(x_{1},...,x_{n}))↦ (ψ(1)x_{π-11},..., ψ(n)x_{π-1n}).^{.}_{.}

Let me start with the basic concept of a *finite group
action*. (More details can be found in [11].) Let G denote a multiplicative
finite group and X a nonempty set. A *finite group action*
_{G}X of G on X is described by a mapping

such that g(g'x)=(gg')x, and 1x=x. In other words, there is a group homomorphism δ from G into the

G × X → X, (g,x) ↦ gx, ^{.}_{.}

A group action

δ: G→ S _{X}, g ↦ δ(g) =: g, where g(x) := gx.^{.}_{.}

The equivalence classes are called

x ∼ _{G}x' iff ∃ g ∈ G : x'=gx.^{.}_{.}

The set of all orbits will be denoted by

G(x) := {gx | g ∈ G }. ^{.}_{.}

For each x ∈ X the

G\\X := {G(x) | x∈ X}. ^{.}_{.}

is a subgroup of G. The stabilizer of y=gx is given by G

G _{x}:= { g | gx=x }^{.}_{.}

Finally the set of all fixed points of g∈ G is denoted by

|G(x) | = |G |/ |G _{x}|.^{.}_{.}

The main lemma in the theory of enumeration under finite group actions is the so called

X _{g}:= { x | gx=x }.^{.}_{.}

|G\\X | = ^{.}_{.}1 |G |^{.}_{.}

∑

g ∈ G|X _{g}|.^{.}_{.}

Interesting examples for group actions can be found as actions on the set YProof:

^{.}_{.}

∑

g∈ G|X _{g}| =^{.}_{.}

∑

g∈ G^{.}_{.}

∑

x ∈ X_{g}1 = ^{.}_{.}

∑

x∈ X^{.}_{.}

∑

g ∈ G_{x}1 = ^{.}_{.}

∑

x∈ X|G _{x}| =^{.}_{.}

∑

x∈ X^{.}_{.}|G| |G(x)|^{.}_{.}

= |G| ^{.}_{.}

∑

ω∈ G\\X^{.}_{.}

∑

x∈ ω^{.}_{.}1 |G(x)|= |G| ^{.}_{.}

∑

ω∈ G\\X^{.}_{.}

∑

x∈ ω^{.}_{.}1 |ω|= |G| ^{.}_{.}

∑

ω∈ G\\X1 = |G||G\\X|. ^{.}_{.}

- Let
_{G}X be a finite group action, then G acts on Y^{X}by the definitionG × Y ^{X}→ Y^{X}, (g,f)↦ f o g^{-1},^{.}_{.}^{X}is given by|G\\Y ^{X}| =^{.}_{.}1 ^{.}_{.}

∑

g∈ G|Y| ^{c(g)},^{.}_{.}_{X}.**Proof:**A function f∈ Y^{X}is a fixed point of g, if and only if f(g^{-1}x)=f(x) for all x∈ X, i.e. f is constant on each g-orbit (i.e. cycle of g) on X, and c(g) is the number of all these cycles. - Let
_{H}Y be a finite group action, then H acts on Y^{X}by the definitionH × Y ^{X}→ Y^{X}, (h,f)↦ h o f,^{.}_{.}^{X}is given by|H\\Y ^{X}| =^{.}_{.}1 ^{.}_{.}

∑

h∈ H|Y _{h}|^{|X|}.^{.}_{.} - Let
_{G}X and_{H}Y be finite group actions, then the direct product G × H acts on Y^{X}by the definition(G × H) × Y ^{X}→ Y^{X}, ((g,h),f)↦ h o f o g^{-1},^{.}_{.}^{X}is given by|G × H\\Y ^{X}| =^{.}_{.}1 ^{.}_{.}

∑

(g,h)∈ G × H^{.}_{.}|X|

∏

i=1|Y _{hi}|^{ai(g)},^{.}_{.}_{1}(g),...,a_{|X|}(g)) the*cycle type*of the permutation g∈ S_{X}is. (I.e. g decomposes into a product of a_{i}(g) pairwise disjoint cycles of length i for i=1,...,|X|.) Furthermore there is a bijection(G × H)\\Y ^{X}→ G\\(H\\Y^{X}), (G × H)(f)↦ G(H(f)),^{.}_{.}^{X}by g(H(f)) := H(f o g^{-1}). This bijection is due to de Bruijn. - Let
_{G}X and_{G}Y be finite group actions, then G acts on Y^{X}by the definitionG × Y ^{X}→ Y^{X}, (g,f)↦ g o f o g^{-1},^{.}_{.}^{X}is given by|G\\Y ^{X}| =^{.}_{.}1 ^{.}_{.}

∑

g∈ G^{.}_{.}|X|

∏

i=1|Y _{gi}|^{ai(g)},^{.}_{.} - Let
_{G}X and_{H}Y be finite group actions, then the wreath product H≀_{X}G acts in form of the exponentiation on Y^{X}(H≀ _{X}G) × Y^{X}→ Y^{X}, ((ψ,g),f)↦ f̃ ,^{.}_{.}^{-1}x). There is a bijection due to Lehmann ([12][13]) which reduces the action of a wreath product to the action of the group G on the set of all functions from X into the set of all orbits of H on Y:Φ: H≀ _{X}G\\Y^{X}→ G\\(H\\Y)^{X}, (H≀_{X}G(f)) ↦ G(F),^{.}_{.}^{X}is given by F(x)=H(f(x)), and G acts on (H\\Y)^{X}by g(F) := F o g^{-1}. So the number of H≀_{X}G-orbits on Y^{X}is given by|(H≀ _{X}G)\\Y^{X}| =^{.}_{.}1 ^{.}_{.}

∑

g∈ G|H\\Y| ^{c(g)}.^{.}_{.}

^{.}_{.}

∑

ω∈ G\\XW(ω) = ^{.}_{.}1 |G|^{.}_{.}

∑

g∈ G^{.}_{.}

∑

x∈ X_{g}w(x). ^{.}_{.}

Another concept is the enumeration of orbits of given stabilizer
type. We have already seen that the stabilizer type of an orbit
G(x) is the conjugacy class of the stabilizer G_{x}. Having
detailed information on the *subgroup lattice* of the acting
group it is possible to determine the number of orbits of
stabilizer type Ũ , where Ũ is the conjugacy class of
U≤ G. In my PhD thesis [7] all
the enumeration formulae are given for group actions of the form
1,2,3 and 4 on Y^{X}.

Finally let me introduce the *cycle index* of a finite
group action. Let _{G}X be a finite group action, then the
cycle index of G acting on X is the following polynomial in the
indeterminates x_{1},...,x_{|X|} over **Q**.

where (a

Z(G,X) := ^{.}_{.}1 |G|^{.}_{.}

∑

g∈ G^{.}_{.}|X|

∏

i=1x _{i}^{ai(g)},^{.}_{.}

- Let
_{H}Y be a finite group action, then S_{n}× H acts on Y^{n}according to (*) and H-orbits on Y^{n}is given by^{.}_{.}∞

∑

n=0|(S _{n}× H)\\Y^{n}|x^{n}= Z(H,Y)|_{xi=∑j=0∞ xij}=Z(H,Y)|_{xi=(1)/(1-xi)}.^{.}_{.} - The group action of above can be restricted to the set of all
injective mappings from
__n__to Y. The corresponding generating function is^{.}_{.}∞

∑

n=0|(S _{n}× H)\\Y^{n}_{inj}| x^{n}= Z(H,Y)|_{xi=1+xi},^{.}_{.}

Returning to the enumeration of linear codes, we translate the
equivalence relation for linear (n,k)-codes into an equivalence
relation for generator matrices of linear codes, and these
generator matrices are considered to be functions Γ:
__n__→ GF(q)^{k} \ {0} where Γ(i)
is the i-th column of the generator matrix Γ. (We exclude
0-columns for obvious reasons.)

Theorem:The matrices corresponding to the two functions Γ_{1}and Γ_{2}fromnto GF(q)^{k}\ {0} are generator matrices of two equivalent codes, if and only if Γ_{1}and Γ_{2}lie in the same orbit of the following action of GL_{k}(q) × GF(q)^{*}≀ S_{n}as permutation group on (GF(q)^{k}\ {0})^{n}:

(A,(ψ,π))(Γ) = Aψ(⋅)Γ(π ^{-1}⋅),^{.}_{.}or, more explicitly,

(A,(ψ,π))(Γ)(i) := Aψ(i)Γ(π ^{-1}(i) ).^{.}_{.}

Following Slepian [15], we use the following notation:

**T**_{nkq}:=- the number of orbits of functions Γ:
__n__→ GF(q)^{k}\ {0} under the group action of Theorem *, i.e. T_{nkq}=|(GL_{k}(q) × GF(q)^{*}≀ S_{n})\\(GF(q)^{k}\ {0})^{n}|. **S**_{nkq}:=- the number of equivalence classes of linear (n,k)-codes over
GF(q) with no columns of zeros. (A linear (n,k)-code has columns of
zeros, if and only if there is some i∈ n such that
x
_{i}=0 for all codewords x, and so we should exclude such columns.)

As initial values we have S

S _{nkq}= T_{nkq}-T_{n, k-1, q}.^{.}_{.}

- T
_{nkq}is the number of orbits of functions from n to GF(q)^{k}\ {0} without any restrictions on the rank of the induced matrix. - All matrices which are induced from functions Γ of the same orbit have the same rank.
- The number of orbits of functions Γ which induce matrices
of rank less or equal k-1 is T
_{n,k-1,q}.

where Γ∈ (GF(q)

(π,A)(Γ) = AΓπ ^{-1},^{.}_{.}

and the representation of GL

GF(q) ^{*}\\GF(q)^{k}\ {0} =: PG_{k-1}(q)^{.}_{.}

Theorem:The isometry classes of linear (n,k)-codes over GF(q) are the orbits of GL_{k}(q) × S_{n}on the set of mappings PG_{k-1}(q)^{n}. This set of orbits is equal to the set of orbits of GL_{k}(q) on the set S_{n}\\PG_{k-1}(q)^{n}, which can be represented by a complete set of mappings of different content, if the content of f∈ PG_{k-1}(q)^{n}is defined to be the sequence of orders of inverse images |f^{-1}(x)|.

Thus the set of isometry classes of linear (n,k)-codes over GF(q) is equal to the set of orbits of GL_{k}(q) on the set of mappings f∈ PG_{k-1}(q)^{n}of different content that form k × n-matrices of rank k.

The particular classes of elements with orders of inverse images |f^{-1}(x)|≤ 1 are the classes consisting of Hamming codes.

Knowing the cycle index of PGL_{k}(q) acting on
PG_{k-1}(q) equation (*) can be applied
for computing T_{nkq}. When restricting the group action of
PGL_{k}(q) × S_{n} to an action on the set
of all injective functions Γ: __n__ →
GF(q)^{*}\\(GF(q)^{k} \ {0}) one can
derive the number of classes of *injective codes*, which are
codes without proportional columns.

In [15] Slepian explained
how the cycle index of GL_{k}(2) can be computed using
results of Elspas [5]. In
[6] the author generalized this
concept for computing the cycle indices of GL_{k}(q) and
PGL_{k}(q) acting on GF(q)^{k} or
PG_{k-1}(q) respectively. These cycle indices are now
available in the computer algebra package SYMMETRICA [16]. (See [8] for more details on the
implementation.) They were applied for computing the tables of
linear codes over GF(9), which can be found on the next pages.

Isometry classes of linear (n,k)-codes over
GF(9)

n\k | 1 | 2 | 3 | 4 |

1 | 1 | 0 | 0 | 0 |

2 | 1 | 1 | 0 | 0 |

3 | 1 | 2 | 1 | 0 |

4 | 1 | 5 | 3 | 1 |

5 | 1 | 8 | 12 | 4 |

6 | 1 | 17 | 62 | 28 |

7 | 1 | 27 | 430 | 475 |

8 | 1 | 54 | 4150 | 28856 |

9 | 1 | 91 | 42401 | 2.417364 |

10 | 1 | 168 | 413259 | 197.609449 |

11 | 1 | 275 | 3.762158 | 14874.498092 |

12 | 1 | 477 | 31.881605 | 1.029632.967128 |

13 | 1 | 764 | 252.307220 | 65.891528.575554 |

14 | 1 | 1247 | 1873.439094 | 3920.491447.510867 |

15 | 1 | 1937 | 13111.695528 | 217978.744960.455289 |

Isometry classes of injective linear
(n,k)-codes over GF(9)

n\k | 1 | 2 | 3 | 4 |

1 | 1 | 0 | 0 | 0 |

2 | 0 | 1 | 0 | 0 |

3 | 0 | 1 | 1 | 0 |

4 | 0 | 2 | 2 | 1 |

5 | 0 | 2 | 7 | 3 |

6 | 0 | 2 | 38 | 21 |

7 | 0 | 1 | 250 | 409 |

8 | 0 | 1 | 2178 | 26436 |

9 | 0 | 1 | 19067 | 2.206042 |

10 | 0 | 1 | 153106 | 176.938649 |

11 | 0 | 0 | 1119490 | 13005.200885 |

12 | 0 | 0 | 7.444639 | 876508.494146 |

13 | 0 | 0 | 45.193018 | 54.475570.780948 |

14 | 0 | 0 | 251.681833 | 3140.099483.972559 |

15 | 0 | 0 | 1291.732944 | 168727.736939.110698 |

is called the

(

Γ _{1}0 0 Γ _{2})

In [15] Slepian proves that
every decomposable linear (n,k)-code is equivalent to a direct sum
of indecomposable codes, and that this decomposition is unique up
to equivalence and order of the summands. Slepian used a generating
function scheme for computing the numbers R_{nk2}. However
after constructing these codes the author realized that in some
situations this formula doesn't work correctly. For that reason we
are giving another formula to determine R_{nkq}. For the
rest of this article let n≥ 2.

Theorem:The number R_{nkq}is equal towhere

S _{nkq}-^{.}_{.}

∑

a^{.}_{.}

∑

b^{.}_{.}n-1

∏

j=1 a_{j}≠ 0( ^{.}_{.}

∑

c=(c_{1},...,c_{aj})∈ ℕ^{aj}j≥ c_{1}≥ ...≥ c_{aj}≥ 1, ∑c_{i}=b_{j}U(j,a,c)), ^{.}_{.}and where the first sum is taken over the cycle types a=(a

U(j,a,c) = ^{.}_{.}j

∏

i=1Z( S _{ν(i,aj,c)},ν(i,a) |_{j},c)_{xℓ=Rjiq}, ν(i,a_{j},c) = |{1≤ l≤ a_{j}| c_{l}=i}|,^{.}_{.}_{1},...,a_{n-1}) of n, (which means that a_{i}∈ ℕ_{0}and ∑ia_{i}=n) such that ∑a_{i}≤ k, while the second sum is over the (n-1)-tuples b=(b_{1},...,b_{n-1})∈ ℕ^{n-1}_{0}, for which a_{i}≤ b_{i}≤ i a_{i}, and ∑b_{i}=k. The numerical results show that for fixed q and n the sequence of R_{nkq}is unimodal and symmetric. (It is easy to prove that this sequence must be symmetric, but the proof of the unimodality is still open.)

The numbers of classes of indecomposable linear codes over GF(9) are given in the next two tables.

Isometry classes of indecomposable linear
(n,k)-codes over GF(9)

n\k | 1 | 2 | 3 | 4 |

1 | 1 | 0 | 0 | 0 |

2 | 1 | 0 | 0 | 0 |

3 | 1 | 1 | 0 | 0 |

4 | 1 | 3 | 1 | 0 |

5 | 1 | 6 | 6 | 1 |

6 | 1 | 14 | 49 | 14 |

7 | 1 | 24 | 402 | 402 |

8 | 1 | 50 | 4097 | 28353 |

9 | 1 | 87 | 42296 | 2412712 |

10 | 1 | 163 | 413066 | 197.562376 |

11 | 1 | 270 | 3.761800 | 14874.037714 |

12 | 1 | 471 | 31.880975 | 1.029628.744436 |

13 | 1 | 758 | 252.306117 | 65.891492.470922 |

14 | 1 | 1240 | 1873.437231 | 3920.491159.098191 |

15 | 1 | 1930 | 13111.692422 | 217978.742798.601836 |

Isometry classes of indecomposable injective
linear (n,k)-codes over GF(9)

n\k | 1 | 2 | 3 | 4 |

1 | 1 | 0 | 0 | 0 |

2 | 0 | 0 | 0 | 0 |

3 | 0 | 1 | 0 | 0 |

4 | 0 | 2 | 1 | 0 |

5 | 0 | 2 | 5 | 1 |

6 | 0 | 2 | 36 | 13 |

7 | 0 | 1 | 248 | 369 |

8 | 0 | 1 | 2177 | 26181 |

9 | 0 | 1 | 19066 | 2203858 |

10 | 0 | 1 | 153105 | 176.919574 |

11 | 0 | 0 | 1119489 | 13005.047772 |

12 | 0 | 0 | 7.444639 | 876507.374648 |

13 | 0 | 0 | 45.193018 | 54.475563.336302 |

14 | 0 | 0 | 251.681833 | 3140.099438.779534 |

15 | 0 | 0 | 1291.732944 | 168727.736687.428860 |

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