An Introduction to Character Theory through the MacWilliams Identity

In coding theory, one of the basic theorems is the MacWilliams identity. For a linear code $C \leq \mathbb{F}_{q}^{E}$ over a finite field $\mathbb{F}_{q}$ with coordinate set $E$, the weight enumerator of its 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 at least the following basic material:

We assume that the reader already knows, at least at a basic level, the following notions:

• 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.)

In this series, I look at proof methods for the MacWilliams identity under the following five broad families.

1. Fourier, character, and Poisson methods.

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

3. Orthogonal polynomials and association schemes.

4. Matroids and Tutte polynomials.

5. Moments and double-counting methods.

This note focuses on the first of these: the Fourier, character-theoretic, and Poisson approach. However, rather than putting terms such as the Fourier transform or the Poisson summation formula centre stage from the outset, I begin with the most basic building block, namely characters of finite abelian groups. In other words, the aim of this second note is to use a proof of the MacWilliams identity as a guide to an introduction to character theory on finite abelian groups.

Last time, I proved the MacWilliams identity using inclusion among supports and Möbius inversion. This time, by contrast, I prove the same identity using characters of finite abelian groups and their orthogonality relations. Where the main actor last time was “inclusion among supports”, the main actors this time are “group duality” and “orthogonality relations of characters”.

By character theory here I do not mean the whole of representation theory of finite groups. What is needed in this note is a homomorphism from a finite abelian group $G$ to the multiplicative group $\mathbb{C}^{\times}$ of non-zero complex numbers:

Such a map is called a character of $G$. Characters of finite abelian groups send group elements to roots of unity in $\mathbb{C}$, and turn addition into multiplication. Moreover, characters satisfy very strong orthogonality relations. Through a fixed identification, these orthogonality relations pick out the condition corresponding to the dual code $C^{\perp}$.

The route in this note is as follows:

If one looks only at the proof of the MacWilliams identity, the number of necessary formulae is not so large. Essentially, everything is condensed into the single orthogonality relation

However, if one uses this formula only as an isolated computation, it becomes harder to see the landscape of character theory as a subject. So in this note I first introduce characters of finite abelian groups, character groups, and annihilators, and then apply them to the MacWilliams identity.

For characters of finite groups and finite Fourier analysis, standard references include Terras [Ter99] and Stein–Shakarchi [SS03]. For trace maps over finite fields and additive characters, see Lidl–Niederreiter [LN97].

Let us begin by changing the point of view on the objects of coding theory slightly. The space $\mathbb{F}_{q}^{E}$ is a vector space over a finite field, but if one forgets about scalar multiplication^{Footnote¹Even so, it is not the case that one can forget it completely and still carry out every argument. Much of the discussion proceeds using only the additive-group structure, but when we later relate the annihilator $C^{\circ}$ to the usual dual code $C^{\perp}$, we use the $\mathbb{F}_{q}$-linearity of $C$, namely that if $a \in \mathbb{F}_{q}$ and $c \in C$, then $ac \in C$.1} and concentrates only on addition, it is also a finite abelian group.

The element $x^{\prime}$ in (G3)For each $x$, there exists an element $x^{\prime} \in G$ such that $x + x^{\prime} = x^{\prime} + x = 0$.(G3) is called the (additive) inverse of $x$. It is immediate that $x^{\prime}$ is uniquely determined for each $x \in G$^{Footnote²If $x^{\prime}$ and $x^{\prime\prime}$ are both inverses of $x \in G$, then $x^{\prime} = x^{\prime} + 0 = x^{\prime} + (x + x^{\prime\prime}) = (x^{\prime} + x) + x^{\prime\prime} = 0 + x^{\prime\prime} = x^{\prime\prime}$. (This proof shows that commutativity (G4) is not needed.)2}, so we write this inverse as $-x \coloneqq x^{\prime}$. The finite field $\mathbb{F}_{q}$ is a finite abelian group with respect to addition. Hence its direct product $\mathbb{F}_{q}^{E}$ is also a finite abelian group. A linear code $C \leq \mathbb{F}_{q}^{E}$ is therefore both a vector subspace and a subgroup of this additive group.

The character-theoretic proof uses this additive-group structure. In other words, rather than starting with scalar multiplication in the vector space, we first focus on $\mathbb{F}_{q}^{E}$ as an additive group and on its subgroup $C$.

However, the dual code

is defined using the inner product. What is interesting in the character-theoretic proof is that this orthogonal complement with respect to the inner product appears naturally as the characters that are trivial on $C$. For that reason, I begin by introducing characters of finite abelian groups.

The groups considered in this note are abelian, so I write their operation additively. By contrast, the set of non-zero complex numbers

forms a group under multiplication. A character is a map that carries addition to multiplication.

A group homomorphism preserves the identity element^{Footnote³Here we consider a homomorphism $f \colon G \to G^{\prime}$ from a group written additively to a group written multiplicatively. Let $0$ be the identity element of $G$, and let $1_{G^{\prime}}$ be the identity element of $G^{\prime}$. Then $f(0) = f(0)1_{G^{\prime}} = f(0)(f(0)f(0)^{-1}) = (f(0)f(0))f(0)^{-1} = f(0 + 0)f(0)^{-1} = f(0)f(0)^{-1} = 1_{G^{\prime}}$.3}, so one always has $\chi(0) = 1$.

Characters of finite groups always take values among roots of unity. Indeed, let $m$ be the order^{Footnote⁴The order of $x \in G$ is the smallest positive integer $m$ such that $mx \coloneqq \underbrace{x + \dots + x}_{m\text{ times}} = 0$. (If one uses multiplicative notation instead, it is the smallest positive integer $m$ such that $x^{m} \coloneqq \underbrace{x \dotsm x}_{m\text{ times}} = 1$.)4} of $x \in G$. Then $mx = 0$, so

Thus a character sends elements of a finite group to finitely many points on the unit circle in the complex plane.

Let $q = p^{m}$, where $p$ is a prime. Using the trace map of the finite field

one can write additive characters explicitly. For example, define an additive character $\psi$ by

Here $\Tr_{\mathbb{F}_{q}/\mathbb{F}_{p}}(a)$ is an element of $\mathbb{F}_{p}$, so when putting it into the exponential function, we identify $\mathbb{F}_{p} \cong \mathbb{Z}/p\mathbb{Z}$ and use the representatives $0,1,\dots,p-1$. This value depends only on the residue class modulo $p$, so it does not depend on the choice of representative. This $\psi$ is an additive character because the trace map is additive. Indeed,

Moreover, finite field extensions are separable, so $\Tr_{\mathbb{F}_{q}/\mathbb{F}_{p}}$ is not the zero map. In this note I use this fact as a basic fact from finite field theory. Since $\Tr_{\mathbb{F}_{q}/\mathbb{F}_{p}}$ is a non-zero $\mathbb{F}_{p}$-linear map, its image is all of $\mathbb{F}_{p}$. Therefore there exists $a \in \mathbb{F}_{q}$ such that

and for such an $a$ we have

So $\psi$ is non-trivial.

More generally, for $t \in \mathbb{F}_{q}$ define

Then $\psi_{t}$ is also an additive character. When $t = 0$, the character $\psi_{t}$ is trivial. When $t \neq 0$, the map $a \mapsto ta$ is a bijection of $\mathbb{F}_{q}$, so if $\psi_{t}$ were trivial, then $\psi$ would also be trivial. Hence $\psi_{t}$ is non-trivial whenever $t \neq 0$.

Note that when $q = p^{m}$ with $m > 1$, the map $\Tr_{\mathbb{F}_{q}/\mathbb{F}_{p}}$ is a non-zero linear map from the $m$-dimensional $\mathbb{F}_{p}$-vector space $\mathbb{F}_{q}$ to the $1$-dimensional space $\mathbb{F}_{p}$, so its kernel is non-trivial. Therefore, for an additive character coming from the trace, it can happen that

even for a non-zero $x \in \mathbb{F}_{q}$. So in general one does not have

This point becomes important later, when comparing $C^{\circ}$ and $C^{\perp}$.

From this point on, I fix one non-trivial additive character of $\mathbb{F}_{q}$ and write it simply as $\psi$. In the character-theoretic proof of the MacWilliams identity, the final result is the same no matter which non-trivial additive character one chooses.

The full set of characters itself forms a group.

The group structure on $\widehat{G}$ is given by pointwise multiplication of characters. That is, for $\chi, \eta \in \widehat{G}$, define

The identity element is the trivial character $1_{G}$, and the inverse of $\chi$ is given by

This theorem means that a finite abelian group has as many characters as it has elements. However, one cannot in general identify $G$ with $\widehat{G}$ naturally. To construct such an identification, one needs an additional choice. There is a natural correspondence between $G$ and $\widehat{\widehat{G}}$, but in general the passage from $G$ to $\widehat{G}$ itself involves a choice. In this note, I later connect $\mathbb{F}_{q}^{E}$ with its character group by choosing a non-trivial additive character $\psi$ and the standard inner product. In coding theory, such a concrete identification is obtained by choosing the standard inner product and a non-trivial additive character.

Note that Theorem 4.2For a finite abelian group $G$, $$\card{\widehat{G}} = \card{G}$$ holds.Theorem 4.2 is a background theorem for general finite abelian groups, and its proof used the fundamental theorem of finite abelian groups as a black box. However, in the case $G=\mathbb{F}_{q}^{E}$ that is actually needed in this note, one can prove the result directly from the concrete description of additive characters of finite fields, without using that general theorem. In the next section, I use that direct proof as the main route.

From this point on, let $E$ be a finite set, and write $n = \card{E}$. Here I fix a non-trivial additive character $\psi$ of $\mathbb{F}_{q}$ and the standard inner product

For $u \in \mathbb{F}_{q}^{E}$, define a map

by

This is a character of the additive group $\mathbb{F}_{q}^{E}$. Indeed, for $v,w \in \mathbb{F}_{q}^{E}$,

There is also another proof using the general cardinality theorem for finite abelian groups. First, as above, one proves that $\Phi$ is a group homomorphism, and then one checks, as in the older argument, that if $\chi_{u}$ is the trivial character, then $u=0$. Indeed, if $u \neq 0$, then for some $i \in E$ one has $u_{i} \neq 0$. Since $\psi$ is non-trivial, there exists $a \in \mathbb{F}_{q}$ such that $\psi(a) \neq 1$. Define $v \in \mathbb{F}_{q}^{E}$ by

Then $u \cdot v = a$, and therefore

So $\chi_{u}$ is not trivial. Thus $\Phi$ is injective. Since $\card{\mathbb{F}_{q}^{E}}=q^{n}$ and Theorem 4.2For a finite abelian group $G$, $$\card{\widehat{G}} = \card{G}$$ holds.Theorem 4.2 gives

any injective map $\Phi$ between these finite sets is also surjective. This alternative proof uses the general cardinality theorem for finite abelian groups, whereas the main proof above does not.

This isomorphism depends on the choice of the non-trivial additive character $\psi$ and the standard inner product. Under that choice, one can identify an element $u \in \mathbb{F}_{q}^{E}$ with the character $v \mapsto \psi(u \cdot v)$. In fact, for the proof of the MacWilliams identity itself, it is not necessary to know that every character of $\mathbb{F}_{q}^{E}$ is of this form. What is needed is only that each $u \in \mathbb{F}_{q}^{E}$ gives rise to a character $\chi_{u}(v)=\psi(u \cdot v)$, and that this character is trivial on $C$ if and only if $u \in C^{\perp}$. However, since this note is intended as an introduction to character theory, I also explain that all characters of $\mathbb{F}_{q}^{E}$ are of this form.

The most basic fact in character theory is that the sum of a non-trivial character vanishes.

This theorem is the orthogonality relation for the whole group. In the MacWilliams identity, however, the sum is taken over a subgroup $C$. The same argument still works in that setting.

Let me say a little more in words about the meaning of this orthogonality relation. If a character $\chi$ is identically $1$ on $H$, then the sum is simply $1$ added $\card{H}$ times, so it equals $\card{H}$. On the other hand, if $\chi$ oscillates even slightly on $H$, its values cancel one another in the complex plane, and the sum becomes $0$.

We give a name to the characters that are trivial on a subgroup.

The set $H^{\circ}$ is a subgroup of $\widehat{G}$. Indeed, the trivial character $1_{G}$ lies in $H^{\circ}$ because $1_{G}(h)=1$ for every $h \in H$. Also, if $\chi,\eta \in H^{\circ}$, then for every $h \in H$ one has

and similarly

So the subgroup conditions are satisfied. Using annihilators, Corollary 6.2 (Orthogonality relation on a subgroup)Let $G$ be a finite abelian group, and let $H \leq G$ be a subgroup. For $\chi \in \widehat{G}$, $$\sum_{h \in H}\chi(h) = \begin{cases} \card{H}, & \chi(h) = 1 \text{ for all } h \in H,\\ 0, & \text{otherwise} \end{cases}$$ holds.Corollary 6.2 can be rewritten as

Now apply this formula to $G=\mathbb{F}_{q}^{E}$ and $H=C$. Let me first organise where the objects under discussion live.

$C^{\perp}$

This is a subspace of $\mathbb{F}_{q}^{E}$, consisting of all vectors orthogonal to $C$ under the inner product.

$\widehat{\mathbb{F}_{q}^{E}}$

This is the full set of characters of the additive group $\mathbb{F}_{q}^{E}$.

$C^{\circ}$

This is a subgroup of $\widehat{\mathbb{F}_{q}^{E}}$, consisting of all characters that are trivial on $C$.

$u \mapsto \chi_{u}$

This is an isomorphism depending on the fixed choice of $\psi$ and the standard inner product, and it connects $\mathbb{F}_{q}^{E}$ with $\widehat{\mathbb{F}_{q}^{E}}$.

So, strictly speaking, $C^{\perp}$ and $C^{\circ}$ live in different places. The former is a subspace of $\mathbb{F}_{q}^{E}$, whereas the latter is a subgroup of $\widehat{\mathbb{F}_{q}^{E}}$. Accordingly, whenever I say that they “correspond” below, I mean correspondence through the fixed isomorphism $u \mapsto \chi_{u}$.

I connect $\mathbb{F}_{q}^{E}$ and its character group by the isomorphism from Theorem 5.1The map $$\Phi \colon \mathbb{F}_{q}^{E} \to \widehat{\mathbb{F}_{q}^{E}}, \qquad u \mapsto \chi_u$$ is a group isomorphism.Theorem 5.1

Through this isomorphism, the annihilator of $C$ corresponds to $C^{\perp}$.

As already noted, even for a non-trivial additive character $\psi$, one does not in general have

In particular, when $q=p^{m}$ with $m>1$, the standard additive character built from the trace has a non-trivial kernel. Therefore, from $\chi_{u}(c)=\psi(u\cdot c)=1$ one cannot conclude immediately that $u\cdot c=0$. In the proof below, one uses the $\mathbb{F}_{q}$-linearity of $C$ at this point.

Here we use the following auxiliary fact. If $\psi$ is a non-trivial additive character of $\mathbb{F}_{q}$ and $d \in \mathbb{F}_{q}$ satisfies $d \neq 0$, then

is also a non-trivial additive character. Indeed, $a \mapsto ad$ is a bijection of $\mathbb{F}_{q}$, and if $\psi(ad)=1$ held for every $a$, then $\psi$ would be identically $1$ on all of $\mathbb{F}_{q}$.

This theorem says that, through the fixed isomorphism $u \mapsto \chi_{u}$, the condition $u \in C^{\perp}$ is equivalent to saying that the corresponding character $\chi_{u}$ is trivial on $C$. This is the central viewpoint in the character-theoretic proof.