An Introduction to Group Actions and Cycle Indices through the MacWilliams Identity

One of the fundamental theorems in coding theory is the MacWilliams identity. Let $E$ be the coordinate set, let $n=\card{E}$, and, for a linear code $C \leq \F_{q}^{E}$ over the finite field $\F_{q}$, consider its dual code

where

For a codeword $c \in \F_{q}^{E}$, write its support and Hamming weight as

Define the weight enumerator of the linear code $C$ by

The MacWilliams identity is the formula saying that the weight enumerator of the dual code can be computed from the weight enumerator of $C$ as follows:

This is the MacWilliams identity.

In this series, I use proofs of the MacWilliams identity as a guide to an introduction to neighbouring areas and concepts. Accordingly, this series is aimed at readers who already know the following basic material in coding theory:

We assume familiarity, at least at a basic level, with

• what a (finite) field is,

• what a linear code over a finite field is,

• what the Hamming weight is,

• what the dual code is.

(There is no problem if you do not know a proof of the MacWilliams identity.)

This note does not assume Parts 1–7. In the latter half, we use a calculation corresponding to the orthogonality of additive characters and the complete weight enumerator, but the necessary definitions and facts are introduced inside this note. Also, this note does not go deeply into the motivation, across the whole series, for separating the proofs into these five families; it is organised so that the proof in this part can be read using only the language of group actions and cycle indices.

In this series, I look at proof methods for the MacWilliams identity under the following five broad families. However, this classification is a map for the series as a whole, and is not necessary in order to read the proof in this note:

1. Fourier, character, and Poisson methods.

2. Möbius inversion, lattice-theoretic, and shortening/puncturing methods.

3. Orthogonal-polynomial and association-scheme methods.

4. Matroid and Tutte-polynomial methods.

5. Moment and double-counting methods.

The proof treated in this note is written, on the surface, in the language of

If compressed into the five families, it is close to the Fourier, character, and Poisson methods. This is because, at the final stage where the dual code $C^{\perp}$ is extracted, the additive characters of the finite field $\F_q$, or equivalently the character table of the additive group $(\F_q,+)$, appear. However, the main subject of this note is not character theory. The aim here is to use a proof of the MacWilliams identity as a guide to an introduction to group actions and cycle indices.

A group action is a language for describing a situation where the elements of a group behave as symmetries of a set. When a group acts on a finite set, that set decomposes into orbits. The formula that counts the number of orbits as an average of numbers of fixed points is Burnside's lemma. Furthermore, if we view group elements as permutations, the object that records their cycle decompositions is the cycle index. In Pólya enumeration, by substituting variables into this cycle index, one can count colourings while taking symmetries into account.

In coding theory, a codeword $c = (c_{e})_{e \in E}$ can be viewed, at each coordinate, as a translation

In other words, one can construct a permutation group from the code $C$. The cycle index of this permutation group records almost exactly the weight enumerator of $C$. Moreover, if we refine the cycle index slightly and record the translation amount $c_{e} \in \F_{q}$ at each coordinate itself, then the complete weight enumerator appears. The viewpoint of this note is to look at the MacWilliams identity through this refined cycle index.

The flow of the note is as follows.

For the relation between cycle indices and weight enumerators of codes, Cameron [Cam02] states that the cycle index of the permutation group associated with a linear code becomes the weight enumerator, up to normalisation. For the relation between complete cycle indices and complete weight enumerators, see Miezaki–Oura [MO19]. For classical treatments of Pólya enumeration and cycle indices, see Pólya [Ply37], Harary–Palmer [HP73], and others. Cameron [Cam95] is also a standard reference for the basic theory of permutation groups.

We begin with the definition of a group action. Here we treat only finite groups. In coding theory, the letter $G$ is often used to denote a generator matrix, but in this note, following the general language of group actions, $G$ denotes a group. Please note that it is not notation for a generator matrix.

A group action is a way to "realise the elements of a group as symmetries of a set". Indeed, for each $g \in G$, we obtain a map

This map is a bijection. Its inverse is $x \mapsto g^{-1} \cdot x$. Thus each element of $G$ defines a permutation of $\Omega$.

Let us also look at an example close to coding theory.

In this example, the group action decomposes $V$ into cosets. This is the feeling that "a group action quotients an object by symmetries".

The first things to look at for a group action are orbits and fixed points.

The orbit is the set of all points that can be reached by moving the point $x$ by elements of the group. The stabiliser is the set of all group elements that do not move the point $x$. The fixed point set is the set of all points not moved by the group element $g$. Note that $\Stab_{G}(x)$ is indeed a subgroup of $G$. This is because the identity fixes $x$, the product of two elements fixing $x$ also fixes $x$, and the inverse of an element fixing $x$ also fixes $x$. There is a basic relation between orbits and stabilisers.

We shall use this theorem later when proving Burnside's lemma. Intuitively, it expresses the fact that the larger the orbit of a point is, the fewer symmetries fix that point.

When a group action decomposes a set $\Omega$ into several orbits, Burnside's lemma is the formula that gives the number of these orbits as an average of numbers of fixed points. It is also called the Cauchy–Frobenius lemma.

The point of Burnside's lemma is summed up in the sentence

the number of orbits is the average number of fixed points.

This idea of "averaging along a group action" leads to cycle indices and Pólya enumeration. Averaging also appears in the proof of the MacWilliams identity. However, Burnside's lemma itself does not directly give the dual code $C^{\perp}$. In Burnside's lemma, one averages the number of fixed points over group elements $g \in G$. On the other hand, in the proof of the MacWilliams identity later on, one averages the character values $\psi(u \cdot c)$ over elements $c \in C$ of $C$ as an additive group, and uses their orthogonality to determine whether $u \in C^{\perp}$. What is common is that averaging over group elements acts as a device for extracting symmetry or orthogonality. For this reason, the averaging operation appearing in Burnside's lemma is the entrance to the viewpoint of this note.

We now turn to cycle indices. A permutation $\sigma \in \Sym(\Omega)$ of a finite set $\Omega$ can be decomposed as a product of disjoint cycles. For example, if

then there is one $3$-cycle and one $2$-cycle. Fixed points are regarded as $1$-cycles.

Of course, since $\Omega$ is finite, $c_{\ell}(\sigma) = 0$ for all sufficiently large $\ell$. Also,

In this note, we define the cycle index as an average over the group elements. Strictly speaking, the cycle index is not determined by the abstract group $G$ alone; it depends on how $G$ acts on which finite set $\Omega$. Even for the same group, different actions can give different cycle indices. Some references use the unnormalised version without the factor $1/\card{G}$. Either convention has the same substance, but in Pólya enumeration the averaged version corresponds directly to Burnside's lemma.

For example, if one colours the vertices of the triangle with two colours, one may substitute $s_{1}=2$, $s_{3}=2$ into the variables of the cycle index. This corresponds, in the Pólya enumeration we shall see later, to reading that there are two choices of colour both for cycles of length $1$ and for cycles of length $3$. Then the number of orbits is

In other words, substituting into the cycle index shows that there are four two-colourings up to rotation.

The cycle index does not record all the information of the group action. However, it compresses the information needed for counting colourings very efficiently. We shall see this point in the next section.

Pólya enumeration is a method for counting colourings considered the same under a group action. Here we state the weighted form.

Let the finite set $\Omega$ be the set of "places", and let the finite set $A$ be the set of "colours". A colouring means a map $f \colon \Omega \to A$. If $G$ acts on $\Omega$, then $G$ also acts on the set of all colourings $A^{\Omega}$. The action is defined by

This definition means that we first move the place back by $g^{-1}$ and then look at the colour. It can be thought of as constructing a pullback action on functions from an action on places. We use $g^{-1}$ here so that the action on the set of colourings is also a left action. With this definition, $g\cdot(h\cdot f)=(gh)\cdot f$ holds.

Assign a weight variable $w_{a}$ to each colour $a \in A$. Define the weight monomial of a colouring $f$ by

This weight monomial does not change under the action of $G$. Indeed, $g$ is only permuting the order of the factors in the product. Thus, for an orbit $\mathcal{O}$ of colourings, its weight monomial $\mon(\mathcal{O})$ is well-defined.

What this theorem shows is that the cycle index records all at once the "sum of the weight monomials of the colourings fixed" by the group elements. On a cycle of a permutation $g$, a fixed colouring must be constant. Therefore the term $w_{a}^{\ell}$ appears for a cycle of length $\ell$. This idea of "multiplying the contributions cycle by cycle and averaging over the whole group" is the core of the cycle index.

Burnside's lemma and Pólya enumeration up to this point are preparation for understanding what the cycle index used later records as an "average over the group elements". In the proof of the MacWilliams identity below, we do not directly apply Pólya's enumeration theorem itself. Rather, we apply a cycle-index-like average expression to the permutation group constructed from a code, and finally extract the dual code using the orthogonality of additive characters.

We now return to coding theory. We construct a permutation group from a linear code $C \leq \F_{q}^{E}$. Write $q = p^{m}$, and let $p$ be the characteristic.

In the earlier example, $C$ acted by translations on the whole space $V=\F_q^E$. Here we consider a different action. The previous action was for decomposing the whole space $V=\F_q^E$ into cosets of $C$. The action used here is for looking at the cycle type of the permutation obtained on each coordinate fibre $\{e\}\times\F_q$. Since the purpose is different, the set acted on is also changed from $V$ to $\Omega_C=E\times\F_q$, defined below. For each coordinate $e$, prepare one copy of $\F_q$, and on that copy $\{e\}\times\F_q$ translate by $c_e$. With this construction, whether each coordinate of a codeword is zero or non-zero, and hence the Hamming weight, becomes visible as the cycle type of a permutation. To distinguish the non-zero values themselves, we shall need the complete cycle index introduced later.

Consider the set

This is the set obtained by placing one copy of $\F_q$ for each coordinate $e \in E$. If desired, one can also view the fibre above $e$ under the projection

as $\{e\}\times\F_q$. Below, however, for readers meeting this for the first time, we shall call it the "$e$-th copy". For a codeword $c = (c_{e})_{e \in E} \in C$, define a permutation $\sigma_{c}$ of $\Omega_{C}$ by

Thus, on the $e$-th copy $\{e\}\times\F_q$, we translate $\F_{q}$ by $c_{e}$.

In what follows, we use this injection to index the elements of $G(C)$ by codewords $c \in C$, and write averages over $G(C)$ as averages over $C$.

Computing the cycle index of this permutation group $G(C)$ gives the weight enumerator. First look at one coordinate. If $c_{e} = 0$, then the map $a \mapsto a + c_{e}$ is the identity map, so it has $q$ $1$-cycles on $\F_{q}$. On the other hand, if $c_{e} \neq 0$, then $a \mapsto a + c_{e}$ is a non-trivial translation. In the additive group of the finite field $\F_{q}$, the additive order of a non-zero element $c_{e}$ is $p$. Therefore each orbit of this translation has length $p$, and $\F_{q}$ decomposes into $q/p$ $p$-cycles. Here it is important that the cycle length is $p$, not $q$. As an additive group, $\F_q$ is an $m$-dimensional vector space over $\F_p$, so for any non-zero element $d$ we get a cycle of length $p$ of the form

Thus the whole of $\F_q$ splits into $q/p$ $p$-cycles. For example, when $q=4$, the characteristic is $p=2$. Therefore a non-zero translation $a\mapsto a+d$ does not make the four points of $\F_4$ into a single $4$-cycle, but splits them into two $2$-cycles.

This viewpoint, in which the ordinary cycle index of the permutation group obtained from a code records the Hamming weight enumerator, appears in Cameron [Cam02]. In this note, we later refine this viewpoint by adding translation amounts so that it corresponds to the complete weight enumerator.

From Theorem 7.2 (Cycle index of the permutation group of a code)Let $C \leq \F_{q}^{E}$ be a linear code, and let $q = p^{m}$. The cycle index of the permutation group $G(C)$ defined above is $$\Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots) = \frac{1}{\card{C}} \sum_{c \in C} s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}. \tag{7.1}$$Theorem 7.2, we see that the cycle index of $G(C)$ essentially contains the weight enumerator of $C$. To read this without using fractional powers, set

Then $$\Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots) = \frac{1}{\card{C}} \sum_{c \in C} s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}. \tag{7.1}$$(7.1) can be written as

Thus, in the ordinary cycle index, $s_{1}$ and $s_{p}$ are the ingredients for $U_{0}$ and $U_{1}$ respectively, and we obtain

Here we read not $s_{1}$ and $s_{p}$ themselves, but their powers $U_{0}, U_{1}$ as the variables of the weight enumerator.

In other words, the Hamming weight of a codeword can be read as the cycle type of the corresponding permutation. Zero coordinates produce $q$ fixed points, and non-zero coordinates produce $q/p$ $p$-cycles. In this sense, the weight enumerator is a specialisation of the cycle index.

The ordinary cycle index seen in the preceding section is enough to record the Hamming weight enumerator. However, the ordinary cycle index has one weakness. It regards permutations simply as permutations and records only their cycle lengths. For this reason, it does not distinguish which value each non-zero component $c_{e} \neq 0$ has.

For example, when $q = 5$, both $c_{e} = 1$ and $c_{e} = 2$ give a translation $a \mapsto a + c_{e}$ that is a $5$-cycle. Thus the ordinary cycle index alone cannot see the difference between $1$ and $2$. This is not a problem for the Hamming weight enumerator, since all non-zero values are identified there, but to write the MacWilliams identity more naturally in the language of cycle indices, it is useful to refine the record so that it remembers the translation amount at each coordinate.

What we want to retain here is the additional labelled information consisting of the coordinate fibre $\{e\}\times\F_q$ of $\Omega_C=E\times\F_q$ and the translation amount $c_e$ used on it. This information cannot be recovered from the cycle type of the permutation $\sigma_c$ alone. In the special situation of the translation permutation group constructed from a code, we record this labelled information so that it corresponds to the complete weight enumerator.

Thus, for each $a \in \F_{q}$, prepare a variable $x_{a}$. Here $x_a$ is a variable of the complete weight enumerator, and is different notation from $\Zcycle_{G,\Omega}$, which denotes the ordinary cycle index. To a codeword $c \in C$, associate the monomial

This records which translation $a \mapsto a + c_{e}$ is used on each coordinate fibre $\{e\}\times\F_q$.

For a standard treatment of the MacWilliams identity itself for complete weight enumerators, see MacWilliams–Sloane [MS77, Chapters 5 and 19]. What this note emphasises, however, is the point that this identity can be read as an identity for the complete cycle index of the translation permutation group constructed from a code.

With this definition,

Thus the complete cycle index is the complete weight enumerator normalised as an average over the group elements. One should note that the complete cycle index in this note is not the ordinary cycle index itself that is defined standardly for a general permutation group. Whereas the ordinary cycle index looks only at cycle lengths of permutations, the $\cZ_C$ of this note is a record that retains the labels coming from the code, namely the coordinate fibre $\{e\}\times\F_q$ and the translation amount $c_e$. Thus $\cZ_C$ is not determined by the cycle type of the permutation alone, but depends on the expression involving the coordinate values $c_e$ of the codeword $c$. What is called a complete cycle index in the literature is sometimes defined as a larger polynomial recording the cycle lengths of permutations together with information about the group element, using variables such as $s(h,i)$. In this note, we use $\cZ_C$ only for translation permutation groups coming from codes, specialised to the form that corresponds directly to the complete weight enumerator, and then averaged by dividing by $\card{C}$. This viewpoint is in line with the relation between complete cycle indices and complete weight enumerators treated by Miezaki–Oura [MO19]. Here we extract only the part needed for the variable transformation in the MacWilliams identity.

The Hamming weight enumerator is a specialisation of the complete weight enumerator. Indeed, if we set

then, for any $c \in C$,

Hence

The important point here is that the variable transformation

in the MacWilliams identity comes from a more symmetric transformation at the level of complete weight enumerators. That transformation is given by the character table of the additive group $(\F_q,+)$ of the finite field $\F_q$. We shall see this in the next section.

From here on, we transform variables on the finite set $\F_q$ as in a finite Fourier transform. The basis describing that transform is given by the characters of the additive group $(\F_q,+)$.

To prove the MacWilliams identity at the level of complete weight enumerators, fix a non-trivial additive character of the finite field $\F_{q}$. That is, take a map $\psi \colon \F_{q} \to \C^{\times}$ satisfying

and not identically equal to $1$. In particular, when $q=p$, one may think of $\psi(a)=\exp(2\pi \sqrt{-1}a/p)$. For a general $q=p^m$, one obtains such an additive character by using the trace map from $\F_q$ to $\F_p$ and defining

Here $\Tr_{\F_q/\F_p}(a)$ is an element of $\F_p$, but inside the exponential function we represent it by one of $0,1,\dots,p-1$ and read it as an integer.

For the standard background on Fourier analysis on finite groups and character tables, see Terras [Ter99]. For the trace map and additive characters of finite fields, Lidl–Niederreiter [LN83] is standard.

We shall use only the following property.

Next, define a one-coordinate transform of the variables $x_{a}$. For each $b \in \F_{q}$, set

This is the result of multiplying the variable vector $(x_{a})_{a \in \F_{q}}$ by the character table of the additive group $(\F_q,+)$ of $\F_{q}$. Indeed, for $b \in \F_q$, if we set

then $\chi_b$ is an additive character of $(\F_q,+)$, and as $b$ runs over all of $\F_q$, all additive characters appear exactly once. The placement of the indices is a matter of convention, but in this note we define the new $b$-th variable by $x_b^\ast=\sum_a\psi(ab)x_a$. Some references use conventions involving $\psi(-ab)$ or the transpose matrix. With the convention in this note, we define $x_b^\ast=\sum_a\psi(ab)x_a$ so that, when expanded later, the sum $\sum_{c\in C}\psi(u\cdot c)$ appears. If we consider the matrix indexed by rows and columns $a, b \in \F_{q}$,

then $$x_{b}^{\ast} \coloneqq \sum_{a \in \F_{q}} \psi(ab) x_{a}. \tag{9.1}$$(9.1) can be written as

In Pólya enumeration, we substituted

into the cycle index. Here, for the complete cycle index, we substitute the variable transformation given by the character table of the additive group $(\F_q,+)$. This transformation produces the complete weight enumerator of the dual code.

We prove the MacWilliams identity for complete weight enumerators. This is also a formula for a variable transformation of the complete cycle index.