Article and note

A Series Learning through the MacWilliams IdentityPart 11 of 12

An Introduction to Lattices and Theta Functions through the MacWilliams Identity

Among the five proof systems for the MacWilliams identity, this note focuses on the proof that appears through lattices and theta functions, and introduces lattices in Euclidean space, dual lattices, covolume, Poisson summation, lattice theta functions, and Construction A. In the main text, after explicitly stating the analytic standard facts that are needed, we mainly prove the case of linear codes over prime fields, and finally outline extensions to general finite fields.

Published:: Jun 25, 2026
Updated:: Jun 25, 2026
Reading time:: 56 min (about 12,183 words)

Tagscoding theoryMacWilliams identitylatticestheta functionsConstruction APoisson summationFourier transformfinite fieldscomplete weight enumeratorexpository note

Introduction

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

C^{\perp} \coloneqq \{ u \in \F_{q}^{E} : u \cdot c = 0 \text{ for all } c \in C \}

where

u \cdot c = \sum_{e \in E} u_{e}c_{e}.

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

\supp(c) \coloneqq \{ e \in E : c_{e} \neq 0 \}, \qquad \wt(c) \coloneqq \card{\supp(c)}.

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

W_{C}(X,Y) \coloneqq \sum_{c \in C} X^{n - \wt(c)} Y^{\wt(c)}.

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:

W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}\bigl( X + (q - 1)Y, X - Y \bigr).

This is the MacWilliams identity.

In this series, we use proofs of the MacWilliams identity as a guide to introductions to neighbouring areas and concepts. For that reason, the series is aimed at readers with the following background:

We assume basic familiarity with elementary coding theory, namely 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.

(It is not necessary to know a proof of the MacWilliams identity.)

In the sections on lattices, we use first-year university linear algebra, especially bases, determinants, transposes, and inverse matrices. For indices of sublattices, we use elementary facts about quotient groups and finite-index subgroups. Readers who do not know Smith normal form may accept the formulae for indices of sublattices and for covolumes as standard facts.

This note does not presuppose Parts 1–10. In the series as a whole, we compare several proofs of the MacWilliams identity, but the content of the previous parts is not needed in order to read this note. The necessary material on lattices, dual lattices, covolumes, Fourier transforms, Poisson summation, theta functions, and Construction A is introduced in the text. However, to follow the proofs of the basic properties of the Fourier transform and of the Poisson summation formula themselves, one uses multivariable calculus, Lebesgue integration, the dominated convergence theorem, the Fubini–Tonelli theorem, and basic Fourier series. This is not dependence on previous parts, but additional background for reading the analytic proofs inside this note in detail. If you only want to follow the main line of the article, you may skip the analytic proofs. In that case, it is enough to accept the following as standard facts used later:

the definition of Schwartz functions and their basic rapid decrease,
the fact that one can construct smooth compactly supported functions, namely bump functions, supported in a sufficiently small neighbourhood of any prescribed point and taking a prescribed value at that point,
the Fourier transform of the Gaussian function,
the fact that the Fourier transform is an automorphism of the Schwartz space,
the fact that the Fourier transform of a product-type function decomposes as a product of the one-coordinate Fourier transforms,
the Poisson summation formula for lattices,
the translated one-dimensional Poisson summation formula.

After reading up to Construction A: From Codes to Lattices, you can check the convention for the Fourier transform and the theorem statements used in Summary of the Fourier Transform and Poisson Summation Formula, and then return to the main line from Lattice Theta Functions. The detailed analytic proofs are collected in Appendix: Proofs of the Fourier Transform and Poisson Summation Formula.

In this series, we view the proof methods for the MacWilliams identity as falling roughly into the following five families. However, this classification is a map of the whole series, and is not required for reading the proof in this note:

Fourier, character, and Poisson-type proofs.
Möbius inversion, lattice-theoretic, shortening-puncturing proofs.
Orthogonal-polynomial and association-scheme proofs.
Matroid and Tutte-polynomial proofs.
Moment and double-counting proofs.

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

lattices, dual lattices, Construction A, theta functions, and Poisson summation.

Compressed into the five families above, it belongs to the Fourier, character, and Poisson family. This is because the transformation formula for lattice theta functions comes from the Poisson summation formula, and that Poisson summation formula is a basic formula in continuous Fourier analysis. That said, character theory on finite abelian groups is not the main actor in this note. The aim here is to use a proof of the MacWilliams identity as a guide to an introduction to lattices in Euclidean space and theta functions.

There is one point to keep in mind. Construction A using the standard integer lattice is most naturally connected with the congruence map $\Z \to \Z/p\Z \cong \F_{p}$ . Therefore, in the main text of this note, we first treat the case where $q = p$ is prime, that is, the MacWilliams identity for $C \leq \F_{p}^{E}$ . For general $q = p^{d}$ , the same idea can also be realised by viewing $\F_{q}$ as a $d$ -dimensional vector space over $\F_{p}$ and passing to blocks, or by using residue fields of rings of integers in number fields. However, as an introduction to lattices and theta functions, it is clearer to see the essence first for $p$ -ary codes. Thus the main line of this note is the prime-field case, and we briefly touch on extensions to general finite fields at the end.

The route of the note is as follows. First, from a $p$ -ary linear code $C \leq \F_{p}^{E}$ , Construction A produces the lattice

\Lat(C) = \left\{ \frac{m}{\sqrt{p}} \in \R^{E} : m \in \Z^{E},\, m \bmod p \in C \right\}

inside the Euclidean space $\R^{E}$ . The dual lattice of this lattice is the lattice constructed from the dual code, $\Lat(C)^{\ast} = \Lat(C^{\perp})$ . We apply the Poisson summation formula to this lattice. When the Gaussian function $x \mapsto \e^{-\pi t\norm{x}^{2}}$ is summed over the lattice points, lattice theta functions and their transformation formula appear. We then go beyond Gaussian functions and use arbitrary Schwartz functions, specifying the one-coordinate sums over residue classes independently. This freedom allows us to extract the complete-weight-enumerator MacWilliams identity as a polynomial identity. Finally, by merging all non-zero symbols into one variable, we obtain the usual Hamming-weight MacWilliams identity.

For the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.

Lattices in Euclidean Space

We first introduce the word lattice. The lattice meant here is a lattice in the sense of Euclidean geometry, and is quite different from the lattice that appears in order theory^{Footnote¹The terminology around this point collides quite heavily. In Japanese, the two meanings of lattice can be distinguished by using “格子” and “束”, but the Japanese word “束” can also refer both to a lattice in order theory and to a bundle, as in a vector bundle. In fact, when the author was first learning matroid theory, he mistakenly thought that the lattice appearing there was a lattice of points in space.1}. In this note, a lattice is a discrete set of points arranged regularly inside Euclidean space.

Definition 2.1.

A subset $\Lat$ of $\R^{n}$ is called a lattice if there exist linearly independent vectors in $\R^{n}$ , $b_{1}, b_{2}, \dots, b_{r} \in \R^{n}$ such that

\Lat = \Z b_{1} + \Z b_{2} + \dots + \Z b_{r} = \left\{ m_{1}b_{1} + \dots + m_{r}b_{r} \mid m_{1}, \dots, m_{r} \in \Z \right\}.

In this case, $r$ is called the rank of $\Lat$ . In particular, when $r = n$ , $\Lat$ is called a full-rank lattice.

The linearly independent vectors $b_1,\dots,b_r$ appearing in the definition are called a lattice basis of $\Lat$ . By linear independence, the expression of each lattice point $m_1b_1+\dots+m_rb_r$ by integer coefficients is unique. When we later mention another lattice basis or a basis matrix, we mean a tuple of such generating vectors and the matrix having those vectors as its columns.

It follows from this definition that a lattice has only finitely many points in any bounded set. Put $B=(b_1\,\cdots\,b_r)$ and write

\Lat=B\Z^r.

The linear independence of $b_1,\dots,b_r$ means that the linear map $B\colon\R^r\to\R^n$ is injective. Therefore the minimum of $\norm{Bu}$ on the unit sphere is positive, and hence there is a constant $c>0$ such that

\norm{Bu}\geq c\norm{u} \qquad(u\in\R^r).

Thus the integer vectors $m$ satisfying

\norm{Bm}\leq R \qquad(m\in\Z^r)

are restricted to the finitely many vectors satisfying $\norm{m}\leq R/c$ . By this local finiteness, there are only finitely many lattice points in a bounded ball, and the numbers $N_{\Lat}(s)$ defined later will also be finite. We will also use this fact when regrouping a theta series according to squared lengths.

In this note, we mainly deal with full-rank lattices in $\R^{E}$ . Here $E$ is a finite set, and we put $n \coloneqq \card{E}$ . If necessary, you may think of $E = \{ 1, 2, \dots, n \}$ .

Example 2.2 (Standard integer lattice).

The most basic lattice is the standard integer lattice $\Z^{n} \subseteq \R^{n}$ . Using the standard basis $\bm{e}_{1}, \dots, \bm{e}_{n}$ , the lattice $\Z^{n}$ can be written as

\Z^{n} = \Z \bm{e}_{1} + \dots + \Z \bm{e}_{n}.

Example 2.3 (One-dimensional lattice).

In $\R$ , for any $\alpha > 0$ ,

\alpha\Z = \{ \alpha m \mid m \in \Z \}

is a lattice. The lattice $\alpha\Z$ is an equally spaced set of points whose spacing is $\alpha$ .

When studying lattices, fundamental domains and their volumes are important. For a full-rank lattice $\Lat = \Z b_{1} + \dots + \Z b_{n} \subseteq \R^{n}$ , consider the half-open parallelepiped

\mathcal{P}(b_{1}, \dots, b_{n}) = \left\{ t_{1}b_{1} + \dots + t_{n}b_{n} \mid 0 \leq t_{i} < 1 \right\}.

This is one fundamental domain that tiles $\R^{n}$ by translations by the lattice. Indeed, if $B=(b_1\,\cdots\,b_n)$ , then $\mathcal P=B[0,1)^n$ . For any $x\in\R^n$ , writing $u=B^{-1}x$ and separating each coordinate into its integer and fractional parts gives a unique expression

x=Bm+Bt, \qquad m\in\Z^n,\quad t\in[0,1)^n.

Thus the family of sets

\{\mathcal P+\lambda:\lambda\in\Lat\}

partitions $\R^n$ disjointly.

Definition 2.4.

Let $b_{1}, \dots, b_{n}$ be a basis of a full-rank lattice $\Lat \subseteq \R^{n}$ . Write $B = (b_{1}\, \cdots \, b_{n})$ for the matrix with these vectors as columns. The number

\vol(\R^{n}/\Lat) \coloneqq \abs{\det B}

is called the covolume of $\Lat$ .

The space $\R^n/\Lat$ is the quotient space obtained by identifying two points whose difference is a lattice vector. Geometrically, it can be regarded as a torus obtained by gluing opposite faces of a fundamental domain. The covolume is defined as the Euclidean volume of that fundamental domain. The average density of lattice points may be thought of as the reciprocal of the covolume, and this intuition is also connected with the fact that the reciprocal of the covolume appears as the coefficient in the Poisson summation formula.

If another lattice basis is chosen and its basis matrix is denoted by $B'$ , then for some invertible integer matrix $U$ we have

B'=BU, \qquad U\in\mathrm{GL}_n(\Z), \qquad \det U=\pm1.

Therefore

\abs{\det B'}=\abs{\det B}\abs{\det U}=\abs{\det B},

and the covolume does not depend on the choice of basis.

Example 2.5.

The covolume of $\Z^{n}$ is $1$ . Also, the covolume of the one-dimensional lattice $\alpha\Z \subseteq \R$ is $\alpha$ .

Intuitively, the smaller the covolume, the more densely the lattice points are packed. For lattices constructed from codes, the larger the code $C$ is, the weaker the congruence condition becomes and the more lattice points appear. For that reason, the covolume will appear in a form inversely proportional to $\card{C}$ .

Proposition 2.6 (Covolumes of sublattices and scalar multiples).

Let $L^{\prime} \subseteq L \subseteq \R^{n}$ be full-rank lattices of finite index. Here $\lbrack L:L^{\prime}\rbrack$ is the number of cosets, equivalently the order of the quotient group $L/L^{\prime}$ . Then

\vol(\R^{n}/L^{\prime}) = \lbrack L:L^{\prime} \rbrack \,\vol(\R^{n}/L).

Also, for $\gamma \in \R \setminus \{ 0 \}$ ,

\vol(\R^{n}/\gamma L) = \abs{\gamma}^{n}\vol(\R^{n}/L).

Proof

Write $L = B\Z^{n}$ . If $L^{\prime} \subseteq L$ has finite index, then there exists an integer matrix $A$ such that

L^{\prime} = BA\Z^{n}.

In this case, $L/L^{\prime}\cong\Z^{n}/A\Z^{n}$ , and by Smith normal form its order is $\abs{\det A}$ . Hence $\lbrack L:L^{\prime} \rbrack = \abs{\det A}$ , and

\vol(\R^{n}/L^{\prime}) = \abs{\det(BA)} = \abs{\det A}\abs{\det B} = \lbrack L : L^{\prime} \rbrack \,\vol(\R^{n}/L).

For scalar multiples, since $\gamma L = (\gamma B) \Z^{n}$ , we get

\vol(\R^{n}/\gamma L) = \abs{\det(\gamma B)} = \abs{\gamma}^{n}\abs{\det B}.

Dual Lattices

We next introduce dual lattices. Just as dual codes are important in coding theory, dual lattices are important in lattice theory.

The standard inner product on $\R^{n}$ is

\inner{x}{y} = x_{1}y_{1} + \dots + x_{n}y_{n}.

If we use the coordinate set $E$ , this is written as

\inner{x}{y} = \sum_{e \in E} x_{e}y_{e}.

The norm defined by this inner product is written as

\norm{x} = \sqrt{\inner{x}{x}}.

Definition 3.1.

For a full-rank lattice $\Lat \subseteq \R^{n}$ , define its dual lattice by

\Lat^{\ast} \coloneqq \{ y \in \R^{n}: \inner{x}{y} \in \Z \text{ for all } x \in \Lat \}.

For the dual of a code, the condition is that the inner product is $0$ over $\F_{p}$ . For the dual of a lattice, the condition is that the real inner product is an integer. In Construction A, reducing the latter integrality condition modulo $p$ gives the former orthogonality condition. This is natural when one looks at the exponential function $\exp(2\pi\iu\inner{x}{y})$ used in the Poisson summation formula. The condition for this function to be invariant under translation by every $\lambda \in \Lat$ is

\exp(2\pi\iu\inner{\lambda}{y})=1,

and this is equivalent to $\inner{\lambda}{y} \in \Z$ . Thus the definition of the dual lattice fits naturally with the Poisson summation formula.

Example 3.2.

The dual lattice of $\Z^{n}$ is $\Z^{n}$ itself. Indeed, for $y \in \R^{n}$ to have integer-valued inner product with all $x \in \Z^{n}$ is equivalent to

\inner{\bm{e}_{i}}{y} = y_{i} \in \Z

for each standard basis vector $\bm{e}_{i}$ .

Example 3.3.

The dual lattice of the one-dimensional lattice $\alpha\Z \subseteq \R$ is

(\alpha\Z)^{\ast} = \alpha^{-1}\Z.

Indeed, for $y \in \R$ to have integer-valued product with every $\alpha m$ ( $m \in \Z$ ) is equivalent to $\alpha y \in \Z$ .

Dual lattices and covolumes are related as follows.

Proposition 3.4.

For a full-rank lattice $\Lat \subseteq \R^{n}$ ,

\vol(\R^{n}/\Lat^{\ast}) = \vol(\R^{n}/\Lat)^{-1}.

Proof

Let $b_{1}, \dots, b_{n}$ be a basis of $\Lat$ , and let $B$ be the matrix having these vectors as columns. Then $\Lat = B\Z^{n}$ . The condition $y \in \Lat^{\ast}$ is equivalent to

\inner{Bm}{y} = m^{\top}B^{\top} y \in \Z

for every $m \in \Z^{n}$ . This is equivalent to $B^{\top}y \in \Z^{n}$ , and therefore

\Lat^{\ast} = (B^{\top})^{-1}\Z^{n}.

This is not just a matrix calculation; it also expresses the correspondence between a basis and its dual basis. Indeed, if the columns of $(B^{\top})^{-1}$ are written as $b_{1}^{\ast}, \dots, b_{n}^{\ast}$ , then they satisfy

\inner{b_{i}}{b_{j}^{\ast}} = \delta_{ij}

with respect to the original basis $b_{1}, \dots, b_{n}$ . Here $\delta_{ij}$ is the Kronecker delta, namely $1$ if $i = j$ and $0$ otherwise. Thus $(B^{\top})^{-1}\Z^{n}$ is the set of all integer combinations of the dual basis. Hence

\vol(\R^{n}/\Lat^{\ast}) = \abs{\det((B^{\top})^{-1})} = \abs{\det B}^{-1} = \vol(\R^{n}/\Lat)^{-1}.

The dual lattice appears on the right-hand side of the Poisson summation formula. In the proof of the MacWilliams identity in this note, the flow is:

duality of codes becomes duality of lattices, and the Poisson summation formula connects sums over a lattice and over its dual lattice.

Construction A: From Codes to Lattices

We now return to coding theory. In the main text of this note, $p$ is a prime number and we identify the finite field with $\F_{p} = \Z/p\Z$ . Let $E$ be the coordinate set, and put $n \coloneqq \card{E}$ . From now on, when an element $a$ of $\F_{p}$ is inserted into a real expression such as an exponential function or $a/\sqrt{p}$ , we use the standard representative $0, 1, \dots, p - 1$ . This convention will be used for residue-class theta functions and for the one-coordinate Poisson summation formula.

Consider the natural reduction map

\rho \colon \Z^{E} \to \F_{p}^{E}, \qquad x \mapsto x\bmod p.

For a $p$ -ary linear code $C \leq \F_{p}^{E}$ , first consider

L(C) \coloneqq \rho^{-1}(C) = \{ m \in \Z^{E} : m \bmod{p} \in C \}.

This is a sublattice of $\Z^{E}$ . Indeed, since $L(C)$ is the inverse image under the reduction map, it is an additive subgroup of $\Z^E$ . Since

p\Z^{E} \subseteq L(C) \subseteq \Z^{E},

the quotient group $\Z^{E}/L(C)$ is finite. Therefore $L(C)$ is a finite-index subgroup of $\Z^{E}$ . As a standard fact following from Smith normal form, any finite-index subgroup of $\Z^{E}$ is a free abelian group of rank $n$ . Thus $L(C)$ has a lattice basis consisting of $n$ linearly independent integer vectors, and is a full-rank lattice in $\R^{E}$ . The lattice $L(C)$ is the unnormalised lattice obtained by lifting the code $C$ into the standard integer lattice $\Z^E$ . In some references, this unnormalised lattice $L(C)$ itself is called the Construction A lattice. In this note, in order to make the correspondence with the dual lattice clean, we multiply further by $1/\sqrt{p}$ and make the following definition.

Definition 4.1 (Construction A).

Let $C \leq \F_{p}^{E}$ be a $p$ -ary linear code. The Construction A lattice obtained from $C$ is defined by

\Lat(C) \coloneqq \frac{1}{\sqrt{p}}L(C) = \left\{ \frac{m}{\sqrt{p}} \in \R^{E} : m \in \Z^{E},\, m \bmod{p} \in C \right\}.

Let us make clear the difference between $L(C)$ and $\Lat(C)$ . The lattice $L(C)$ is the unnormalised lattice obtained by lifting the code $C$ into the standard integer lattice $\Z^E$ , and

\Lat(C) = p^{-1/2}L(C)

is the Construction A lattice obtained from it by a normalisation suited to duality. A lattice in this note is a discrete set of points in Euclidean space, and its coordinates need not be integers. Therefore, for a general $C$ , the normalised lattice $\Lat(C)$ is not necessarily a subset of $\Z^E$ . Also, in lattice theory, an integral lattice means a lattice for which the inner product of any two lattice points is an integer, namely $\Lat\subseteq\Lat^\ast$ . This is a different concept from the standard integer lattice, which means $\Z^E$ itself. The factor $p^{-1/2}$ is a normalisation for making the correspondence with the dual lattice concise. The reason we adopt this normalisation in this note is that the dual lattice takes the very clean form

\Lat(C)^{\ast} = \Lat(C^{\perp}).

Without multiplying by $1/\sqrt{p}$ , the dual lattice would be written in a slightly less transparent form such as $(1/p)L(C^{\perp})$ .

Example 4.2 (Two extreme examples).

When $C = \{ 0 \} \leq \F_{p}^{n}$ ,

L(C) = p\Z^{n}, \qquad \Lat(C) = \sqrt{p}\,\Z^{n}.

On the other hand, when $C = \F_{p}^{n}$ ,

L(C) = \Z^{n}, \qquad \Lat(C) = \frac{1}{\sqrt{p}}\Z^{n}.

These two lattices are dual to each other, and their covolumes are respectively

p^{n/2}, \qquad p^{-n/2}.

Example 4.3 (Binary repetition code of length two).

Let $p = 2$ , and consider

C = \{00,11\}\leq\F_{2}^{2}.

Then

L(C) = \Z(1,1)+\Z(1,-1).

Hence $\Lat(C)=2^{-1/2}L(C)$ has the orthonormal basis

\frac{1}{\sqrt2}(1,1), \qquad \frac{1}{\sqrt2}(1,-1).

Thus $\Lat(C)$ is a lattice obtained from $\Z^2$ by an orthogonal transformation, has covolume $1$ , and is self-dual. This corresponds to $C = C^\perp$ .

We first compute the covolume.

Proposition 4.4.

Let $C \leq \F_{p}^{E}$ be a $k$ -dimensional $\F_{p}$ -linear code. Then

\vol(\R^{E}/\Lat(C)) = p^{n/2-k}.

Proof

The reduction map $\rho \colon \Z^{E} \to \F_{p}^{E}$ is surjective, and $L(C) = \rho^{-1}(C)$ . The map

m + L(C) \mapsto (m \bmod p) + C

is well-defined and gives a group isomorphism $\Z^{E}/L(C) \cong \F_{p}^{E}/C$ . Therefore

\lbrack \Z^{E} : L(C) \rbrack = \card{\F_{p}^{E}/C} = p^{n-k}.

Since $C$ is a $k$ -dimensional $\F_{p}$ -linear space, $\card{C} = p^{k}$ . The covolume of $\Z^{E}$ is $1$ , so Proposition 2.6 (Covolumes of sublattices and scalar multiples).Let $L^{\prime} \subseteq L \subseteq \R^{n}$ be full-rank lattices of finite index. Here $\lbrack L:L^{\prime}\rbrack$ is the number of cosets, equivalently the order of the quotient group $L/L^{\prime}$ . Then $\vol(\R^{n}/L^{\prime}) = \lbrack L:L^{\prime} \rbrack \,\vol(\R^{n}/L).$ Also, for $\gamma \in \R \setminus \{ 0 \}$ , $\vol(\R^{n}/\gamma L) = \abs{\gamma}^{n}\vol(\R^{n}/L).$ Proposition 2.6 gives

\vol(\R^{E}/L(C)) = p^{n - k}.

Next, multiplying $L(C)$ by $1/\sqrt{p}$ multiplies $n$ -dimensional volume by $p^{-n/2}$ , again by Proposition 2.6 (Covolumes of sublattices and scalar multiples).Let $L^{\prime} \subseteq L \subseteq \R^{n}$ be full-rank lattices of finite index. Here $\lbrack L:L^{\prime}\rbrack$ is the number of cosets, equivalently the order of the quotient group $L/L^{\prime}$ . Then $\vol(\R^{n}/L^{\prime}) = \lbrack L:L^{\prime} \rbrack \,\vol(\R^{n}/L).$ Also, for $\gamma \in \R \setminus \{ 0 \}$ , $\vol(\R^{n}/\gamma L) = \abs{\gamma}^{n}\vol(\R^{n}/L).$ Proposition 2.6. Hence

\vol(\R^{E}/\Lat(C)) = p^{-n/2}p^{n-k} = p^{n/2-k}.

We next check the most important duality. Here we use the fact that, for any full-rank lattice $L$ and $\alpha\in\R\setminus\{0\}$ ,

(\alpha L)^\ast=\alpha^{-1}L^\ast.

Indeed, $y\in(\alpha L)^\ast$ is equivalent to $\inner{\alpha x}{y} \in \Z$ , that is, to $\inner{x}{\alpha y} \in \Z$ , for all $x\in L$ .

Theorem 4.5 (Construction A and duality).

Let $C \leq \F_{p}^{E}$ be a linear code. Then

\Lat(C)^{\ast} = \Lat(C^{\perp}).

Proof

First write $L(C) = \rho^{-1}(C)$ . Since $\Lat(C) = p^{-1/2}L(C)$ , we have

\Lat(C)^{\ast} = p^{1/2}L(C)^{\ast}.

It is therefore enough to show that $L(C)^{\ast} = p^{-1}L(C^{\perp})$ .

Let $y \in L(C)^{\ast}$ . Since $p\bm{e}_{j}$ belongs to $L(C)$ for every standard basis vector $\bm{e}_{j}$ ( $j \in E$ ), we have

\inner{y}{p \bm{e}_{j}} \in \Z.

Hence $p y_{j} \in \Z$ for every coordinate. Thus there exists $z \in \Z^{E}$ such that $y = \frac{z}{p}$ .

Moreover, for every $m \in L(C)$ ,

\inner{y}{m} = \frac{1}{p}\sum_{e \in E} z_{e}m_{e} \in\Z.

This means that

\sum_{e \in E}(z_{e} \bmod{p})(m_{e} \bmod{p}) = 0 \quad\text{in } \F_{p}.

Since $m \bmod{p}$ runs over all of $C$ , this is equivalent to $z \bmod{p} \in C^{\perp}$ . Thus $z \in L(C^{\perp})$ , and hence $y \in p^{-1}L(C^{\perp})$ .

Conversely, let $z \in L(C^{\perp})$ and put $y = z/p$ . For any $m \in L(C)$ , we have $z \bmod{p} \in C^{\perp}$ and $m \bmod{p} \in C$ , so

\sum_{e \in E} z_{e}m_{e} \equiv 0 \pmod{p}.

Therefore

\inner{y}{m} = \frac{1}{p}\sum_{e \in E} z_{e}m_{e} \in \Z,

and $y \in L(C)^{\ast}$ . Hence

L(C)^{\ast} = p^{-1}L(C^{\perp})

has been shown. Multiplying this by $p^{1/2}$ gives

\Lat(C)^{\ast} = p^{1/2}p^{-1}L(C^{\perp}) = p^{-1/2}L(C^{\perp}) = \Lat(C^{\perp}).

This theorem is the reason for using Construction A. The duality of codes $C \leftrightarrow C^{\perp}$ is transformed into the duality of lattices $\Lat(C) \leftrightarrow \Lat(C)^{\ast}$ . Therefore, when the Poisson summation formula, which deals with dual lattices, is used, the dual code appears naturally.

This theorem also translates self-orthogonality and self-duality to the lattice side. The inclusion relation between Construction A lattices corresponds to the inclusion relation between the original codes, so

C \subseteq C^{\perp} \iff \Lat(C) \subseteq \Lat(C)^{\ast}.

Indeed, in Construction A, $C \subseteq D$ is equivalent to $\Lat(C) \subseteq \Lat(D)$ . One direction follows from the definition, and the other follows by taking an integer representative $m \in \Z^{E}$ of $c\in C$ and observing that $m/\sqrt{p} \in \Lat(C) \subseteq \Lat(D)$ . Thus the equivalence above follows from $\Lat(C)^{\ast} = \Lat(C^{\perp})$ . Similarly,

C = C^{\perp} \iff \Lat(C) = \Lat(C)^{\ast}.

Summary of the Fourier Transform and Poisson Summation Formula

Here we collect only the definitions and theorem statements for the analytic facts used later, after making explicit the convention for the Fourier transform that we adopt. The detailed proofs are deferred to Appendix: Proofs of the Fourier Transform and Poisson Summation Formula. For the main line, it is enough to accept the contents of this section as standard facts.

For a multi-index

\alpha=(\alpha_1,\dots,\alpha_n)\in\Z_{\geq0}^{n},

write

\lvert\alpha\rvert_1 \coloneqq \alpha_1+\cdots+\alpha_n, \qquad x^\alpha \coloneqq x_1^{\alpha_1}\cdots x_n^{\alpha_n}, \qquad \partial^\alpha \coloneqq \frac{\partial^{\lvert\alpha\rvert_1}} {\partial x_1^{\alpha_1}\cdots\partial x_n^{\alpha_n}}.

Here $\lvert\alpha\rvert_1$ denotes the total degree $\alpha_1+\cdots+\alpha_n$ of the multi-index $\alpha$ . We continue to use $\abs{\cdot}$ for absolute values of numbers and determinants.

Definition 5.1.

A smooth function $f\colon\R^n\to\C$ is called a Schwartz function if, for all multi-indices $\alpha,\beta\in\Z_{\geq0}^{n}$ ,

\sup_{x\in\R^n} \abs{x^\alpha\partial^\beta f(x)} <\infty.

This is a precise way of saying that $f$ and all its partial derivatives tend to $0$ at infinity faster than any polynomial. Indeed, for every non-negative integer $N$ and every multi-index $\beta$ , there exists a constant $A_{N,\beta}$ such that

\abs{\partial^\beta f(x)} \leq A_{N,\beta}(1+\norm{x})^{-N}.

This follows from the fact that, for some constant $C_N>0$ ,

(1+\norm{x})^N \leq C_N\sum_{\lvert\alpha\rvert_1\leq N}\abs{x^\alpha}

can be bounded by finitely many monomials. In particular, if $N>n$ , then $f$ and all its partial derivatives are absolutely integrable. Moreover, the product of a polynomial and a Schwartz function is again a Schwartz function. One can also construct, in the standard way, smooth compactly supported functions supported in a sufficiently small neighbourhood of any prescribed point and taking a prescribed value at that point; such functions are called bump functions. A typical example of a Schwartz function is the Gaussian function

f_{t}(x) = \e^{-\pi t\norm{x}^{2}} \qquad(t > 0).

Definition 5.2.

For a Schwartz function $f \colon \R^{n} \to \C$ , define its Fourier transform by

\what{f}(y) \coloneqq \int_{\R^{n}} f(x)\e^{-2\pi\iu\inner{x}{y}} \dd x.

Here we adopt the convention for the Fourier transform in which the exponent contains $2\pi$ . This convention is well suited to writing the Poisson summation formula compactly. Under this convention, the Fourier transform of the Gaussian function has the following form.

Theorem 5.3 (Fourier transform of the Gaussian function).

Let $t > 0$ , and put $f_{t}(x)=\e^{-\pi t\norm{x}^{2}}$ . Then

\what{f_t}(y) = t^{-n/2}\e^{-\pi \norm{y}^{2}/t}.

Proposition 5.4 (Fourier transform on the Schwartz space).

The following hold for the Fourier transform.

If $f$ is a Schwartz function, then $\what{f}$ is also a Schwartz function.
Under the convention for the Fourier transform adopted above,

$\what{\what{f}}(x) = f(-x)$

holds.
Consequently, the Fourier transform is a linear automorphism of the space of Schwartz functions.
For a one-variable Schwartz function $f \colon \R \to \C$ and

$f_{E}(x) = \prod_{e \in E} f(x_{e}),$

the function $f_E$ is a Schwartz function on $\R^E$ , and

$\what{f_{E}}(y) = \prod_{e \in E} \what{f}(y_{e})$

holds.

The next theorem is the central Poisson summation formula for this note.

Theorem 5.5 (Poisson summation formula).

Let $\Lat\subseteq\R^{n}$ be a full-rank lattice, and let $f\colon\R^{n}\to\C$ be a Schwartz function. Then

\sum_{x\in\Lat}f(x) = \frac{1}{\vol(\R^{n}/\Lat)} \sum_{y\in\Lat^{\ast}}\what{f}(y) \tag{5.1}

holds.

This formula transforms a sum over a lattice into a sum over the dual lattice. The reciprocal of the covolume appears on the right-hand side as a correction for the difference in lattice densities. For example, when $\Lat=\Z^{n}$ , we have $\Lat^{\ast}=\Z^{n}$ and the covolume is $1$ , so the formula takes the form

\sum_{m\in\Z^{n}}f(m) = \sum_{m\in\Z^{n}}\what{f}(m).

For later use with one-coordinate residue-class sums, we also record the form for a translated one-dimensional lattice.

Corollary 5.6 (Translated Poisson summation formula).

Let $f \colon \R \to \C$ be a Schwartz function, let $h > 0$ , and let $x_{0} \in \R$ . Then

\sum_{r \in \Z} f(x_{0} + rh) = \frac{1}{h} \sum_{s \in \Z} \exp(2\pi\iu\,s x_{0}/h)\, \what{f}(s/h) \tag{5.2}

holds.

The Poisson summation formula is the principle underlying this part. The MacWilliams identity over finite abelian groups can be viewed as a finite Poisson summation formula, but in this note we use the Poisson summation formula on Euclidean space. Thus, even though the proof belongs to the same Fourier, character, and Poisson family, it is written in the language of continuous analysis and lattices.

Lattice Theta Functions

Substituting the Gaussian function into the Poisson summation formula gives the transformation formula for lattice theta functions. This is one reason why lattices and theta functions appear in a proof of the MacWilliams identity. From here on, we accept the Poisson summation formula as a tool and return to the main line concerning codes and lattices.

Definition 6.1.

For a full-rank lattice $\Lat \subseteq \R^{n}$ , define its theta function or theta series by

\Theta_{\Lat}(t) \coloneqq \sum_{x \in \Lat} \e^{-\pi t\norm{x}^{2}} \qquad(t > 0).

The theta series is the sum of the Gaussian function over the lattice points, and it converges absolutely. It is a Laplace-type generating function recording the discrete distribution of squared lengths of lattice points. Short vectors contribute more, and long vectors contribute less. For a general Euclidean lattice, $\norm{x}^{2}$ need not be an integer. Thus put

\mathcal R_{\Lat} \coloneqq \{ \norm{x}^{2}:x\in\Lat\},

and for $s\in\mathcal R_{\Lat}$ define

N_{\Lat}(s) \coloneqq \card{\{ x \in \Lat: \norm{x}^{2} = s \}}.

By the local finiteness checked in Lattices in Euclidean Space, there are only finitely many lattice points in a bounded ball, so each $N_{\Lat}(s)$ is finite. Since the theta series is an absolutely convergent series with non-negative terms, we may regroup it according to squared length and write

\Theta_{\Lat}(t) = \sum_{s\in\mathcal R_{\Lat}} N_{\Lat}(s) \e^{-\pi ts}.

In other words, the theta function packages the distribution of squared lengths of lattice points. In standard references, one often uses a complex variable $\tau$ on the upper half-plane

\{ \tau \in \C :\Im \tau > 0 \}

and writes the theta function in the form

\sum_{x \in \Lat} \exp(\pi\iu\tau\norm{x}^{2}).

The definition using $t > 0$ in this note is the restriction of that theta function to the imaginary axis $\tau=\iu t$ . When $t$ is large, the contribution of the origin and short vectors dominates. When $t$ is small, more lattice points make a significant contribution. The transformation formula obtained from Poisson summation connects information about $\Lat$ at $t$ with information about the dual lattice $\Lat^{\ast}$ at $1/t$ , matching these two viewpoints.

Example 6.2 (Theta function of the standard integer lattice).

The theta function of the one-dimensional standard integer lattice $\Z$ is

\Theta_{\Z}(t) = \sum_{m\in\Z}\e^{-\pi t m^{2}} = 1+2\e^{-\pi t}+2\e^{-4\pi t}+2\e^{-9\pi t}+\cdots.

The coefficient $2$ records that the two lattice points $m$ and $-m$ have the same squared length. For $\Z^{n}$ , the sum decomposes coordinate by coordinate, giving

\Theta_{\Z^{n}}(t) = \left(\sum_{m \in \Z} \e^{-\pi t m^{2}}\right)^{n}.

The Poisson summation formula gives the basic transformation formula for theta functions.

Theorem 6.3 (Transformation formula for lattice theta functions).

Let $\Lat \subseteq \R^{n}$ be a full-rank lattice. Then, for every $t > 0$ ,

\Theta_{\Lat}(t) = \frac{1}{\vol(\R^{n}/\Lat)} t^{-n/2}\Theta_{\Lat^{\ast}}(1/t) \tag{6.1}

holds.

Proof

Substitute

f_{t}(x) = \e^{-\pi t\norm{x}^{2}}

into the Poisson summation formula (5.1). By Theorem 5.3,

\what{f_t}(y) = t^{-n/2}\e^{-\pi\norm{y}^{2}/t}.

Hence

\begin{aligned} \Theta_{\Lat}(t) &= \sum_{x \in \Lat} \e^{-\pi t\norm{x}^{2}} \\ &= \frac{1}{\vol(\R^{n}/\Lat)} \sum_{y \in \Lat^{\ast}} t^{-n/2}\e^{-\pi\norm{y}^{2}/t} \\ &= \frac{1}{\vol(\R^{n}/\Lat)} t^{-n/2}\Theta_{\Lat^{\ast}}(1/t). \end{aligned}

This theorem is a duality in the world of theta functions. Viewing the theta function of a lattice $\Lat$ at $t$ corresponds to viewing the theta function of the dual lattice $\Lat^{\ast}$ at $1/t$ . In this note, we combine this duality with Construction A. Since $\Lat(C)^{\ast} = \Lat(C^{\perp})$ , the duality of theta functions is translated into the duality of codes.

Complete Weight Enumerators

The theta function of a Construction A lattice is naturally connected with the complete weight enumerator of a code. The usual Hamming weight enumerator only sees whether a coordinate value is $0$ or non-zero. The complete weight enumerator, on the other hand, also distinguishes the types of non-zero values.

Definition 7.1.

Let $C \leq \F_{p}^{E}$ be a linear code. For each $a \in\F_{p}$ , prepare a variable $T_{a}$ . The complete weight enumerator of $C$ is defined by

\cwe_{C}\bigl( (T_{a})_{a \in \F_{p}} \bigr) \coloneqq \sum_{c \in C} \prod_{e \in E} T_{c_{e}}.

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

T_{0} = X, \qquad T_{a} = Y \quad(a \neq 0),

then

\cwe_{C}\bigl((T_{a})_{a \in \F_{p}} \bigr) = W_{C}(X,Y).

Each term of the complete weight enumerator chooses one variable from each coordinate of the coordinate set $E$ , so it is a homogeneous polynomial of total degree $n$ .

Let us see why the complete weight enumerator appears. A point of the Construction A lattice is written as $x=m/\sqrt p$ . The residue class in each coordinate is determined not by the real coordinate $x_e$ itself, but by the corresponding integer $m_e$ . Thus, for each congruence class $m_e \equiv a \pmod p$ , the set of integers $a+p\Z$ appears. When a lattice-point sum is separated coordinate by coordinate, a different one-coordinate sum appears for each $a \in \F_{p}$ . The natural polynomial recording this is the complete weight enumerator.

We formulate this point using an arbitrary one-variable Schwartz function. Let $f \colon \R \to \C$ be a Schwartz function, and for each $a \in \F_{p}$ set

S_{a}(f) \coloneqq \sum_{m \equiv a \pmod{p}} f\left(\frac{m}{\sqrt{p}}\right). \tag{7.1}

Here $S$ stands for sum. The set of points in the summation index is

\frac{a}{\sqrt p}+\sqrt p\,\Z,

which is a translate of the lattice $\sqrt p\,\Z$ , namely a lattice coset. By the rapid decrease of Schwartz functions, this series converges absolutely. Also consider the function on $\R^{E}$ given by

f_{E}(x) \coloneqq \prod_{e \in E} f(x_{e}).

Proposition 7.2.

Let $C \leq \F_{p}^{E}$ be a linear code, and let $f \colon \R \to \C$ be a Schwartz function. Consider the function on $\R^E$ given by

f_E(x)=\prod_{e\in E}f(x_e).

Then

\sum_{x \in \Lat(C)} f_{E}(x) = \cwe_{C}\bigl((S_{a}(f))_{a \in \F_{p}}\bigr) \tag{7.2}

holds.

Proof

An element of $\Lat(C)$ can be written as $x = \frac{m}{\sqrt p}$ , where $m \in \Z^{E}$ and $m \bmod{p} \in C$ . First,

\sum_{m\in\Z^E} \prod_{e\in E} \left| f\left(\frac{m_e}{\sqrt p}\right) \right| = \left( \sum_{r\in\Z} \left| f\left(\frac r{\sqrt p}\right) \right| \right)^n <\infty.

The right-hand side is finite by the rapid decrease of Schwartz functions. This absolute convergence justifies the rearrangements of sums and the decomposition into coordinatewise products below by Tonelli's theorem. Separating the sum according to residue classes $c = m \bmod{p} \in C$ , we get

\begin{aligned} \sum_{x \in \Lat(C)} f_{E}(x) &= \sum_{c \in C} \sum_{\substack{m \in \Z^{E}\\ m \equiv c \pmod{p}}} \prod_{e \in E} f\left(\frac{m_{e}}{\sqrt{p}}\right) \\ &= \sum_{c \in C} \prod_{e \in E} \sum_{m_{e} \equiv c_{e}\, \pmod{p}} f\left(\frac{m_{e}}{\sqrt{p}}\right) \\ &= \sum_{c \in C} \prod_{e \in E} S_{c_{e}}(f) \\ &= \cwe_{C}\bigl((S_{a}(f))_{a \in \F_{p}}\bigr). \end{aligned}

This proposition shows that a sum over a Construction A lattice can be written as a complete weight enumerator. In particular, when $f$ is a Gaussian function, the left-hand side is a lattice theta function.

Residue-Class Theta Functions

The capital $\Theta_{\Lat}$ denotes the theta function of the whole $n$ -dimensional lattice, while the lower-case $\vartheta_a$ denotes the theta function for a residue class in one coordinate. In this section, we connect the two through the complete weight enumerator.

Using the Gaussian function

g_{t}(x) = \e^{-\pi t x^{2}} \qquad(t > 0),

the one-coordinate sum over a residue class becomes a theta function.

Definition 8.1.

For $a \in \F_{p}$ , define the residue-class theta function by

\vartheta_{a}(t) \coloneqq \sum_{m \equiv a \pmod{p}} \e^{-\pi t m^{2}/p} \qquad(t > 0).

The same sum can also be written as a sum over a coset of the lattice $\sqrt p\,\Z$ :

\vartheta_a(t) = \sum_{r\in\Z} \exp\left( -\pi t \left( \frac{a}{\sqrt p}+r\sqrt p \right)^2 \right).

In other words, $\vartheta_a(t)$ is the sum of the Gaussian function over a coset of the lattice $\sqrt p\,\Z$ .

For $p=2$ , $\vartheta_0(t)$ sums over even integers, while $\vartheta_1(t)$ sums over odd integers. The first few terms are

\vartheta_0(t) = 1+2\e^{-2\pi t}+2\e^{-8\pi t}+\cdots,

and

\vartheta_1(t) = 2\e^{-\pi t/2} +2\e^{-9\pi t/2} +\cdots.

The terms $m=0,\pm2,\pm4,\dots$ contribute to the former, and $m=\pm1,\pm3,\dots$ contribute to the latter.

This is the identity

S_{a}(g_{t}) = \sum_{m \equiv a \pmod{p}} g_{t}(m/\sqrt{p}) = \vartheta_{a}(t).

Therefore Proposition 7.2.Let $C \leq \F_{p}^{E}$ be a linear code, and let $f \colon \R \to \C$ be a Schwartz function. Consider the function on $\R^E$ given by $f_E(x)=\prod_{e\in E}f(x_e).$ Then $\sum_{x \in \Lat(C)} f_{E}(x) = \cwe_{C}\bigl((S_{a}(f))_{a \in \F_{p}}\bigr) \tag{7.2}$ holds.Proposition 7.2 gives the following.

Theorem 8.2.

Let $C \leq \F_{p}^{E}$ . For every $t>0$ ,

\Theta_{\Lat(C)}(t) = \cwe_{C}\bigl((\vartheta_{a}(t))_{a \in \F_{p}}\bigr) \tag{8.1}

holds.

Proof

By the definition of the lattice theta function,

\Theta_{\Lat(C)}(t) = \sum_{x \in \Lat(C)} \e^{-\pi t\norm{x}^{2}}.

If $g_{t}(x) = \e^{-\pi t x^{2}}$ , then

\e^{-\pi t\norm{x}^{2}} = \prod_{e \in E} g_{t}(x_{e}).

Applying Proposition 7.2.Let $C \leq \F_{p}^{E}$ be a linear code, and let $f \colon \R \to \C$ be a Schwartz function. Consider the function on $\R^E$ given by $f_E(x)=\prod_{e\in E}f(x_e).$ Then $\sum_{x \in \Lat(C)} f_{E}(x) = \cwe_{C}\bigl((S_{a}(f))_{a \in \F_{p}}\bigr) \tag{7.2}$ holds.Proposition 7.2 therefore gives

\Theta_{\Lat(C)}(t) = \cwe_{C}\bigl((S_{a}(g_{t}))_{a \in \F_{p}}\bigr) = \cwe_{C}\bigl((\vartheta_{a}(t))_{a \in \F_{p}}\bigr).

This formula is the specialisation of the complete weight enumerator obtained by substituting

T_{a} = \vartheta_{a}(t).

In general, it does not embed the complete weight enumerator injectively into the usual one-variable lattice theta function. Indeed, for every $a \in \F_{p}$ ,

\vartheta_{a}(t) = \vartheta_{-a}(t)

holds. This follows by replacing the summation index by $m\mapsto -m$ . In particular, for $p = 3$ we have $\vartheta_{1}(t) = \vartheta_{2}(t)$ , so the usual one-variable lattice theta function cannot fully distinguish the non-zero symbols. Indeed, consider

C=\{(0,0),(1,1),(2,2)\}\leq\F_3^2.

The dual code is

C^\perp=\{(0,0),(1,2),(2,1)\}.

The complete weight enumerators are

\cwe_C=T_0^2+T_1^2+T_2^2, \qquad \cwe_{C^\perp}=T_0^2+2T_1T_2,

and these two are different. However, after substituting $\vartheta_1(t)=\vartheta_2(t)$ , both become

\vartheta_0(t)^2+2\vartheta_1(t)^2.

This example shows that the usual one-variable lattice theta function obtained from the Gaussian function cannot distinguish the symbols $1$ and $2=-1$ . To extract the complete-weight-enumerator identity, we need to be able to specify residue-class sums independently using arbitrary Schwartz functions. The one-variable family of Gaussian functions alone also does not have enough freedom to vary the $p$ variables of the complete weight enumerator independently. Passing to arbitrary Schwartz functions is a way of extracting the polynomial identity behind the special family of theta functions. The viewpoint of pointing out that residue-class theta functions are not algebraically independent in general, replacing them by formal variables, and then passing to the complete-weight-enumerator identity also appears in Nishimura [Nis01]. In this note, we make this passage to formal variables concrete as the construction of Schwartz functions realising arbitrary evaluation points. Thus it is accurate to regard the theta transformation formula for Gaussian functions as a specialisation of the complete-weight-enumerator MacWilliams identity proved later.

Combining Theorem 6.3 with Theorem 4.5 and Proposition 4.4, the theta function of the Construction A lattice satisfies, with $k \coloneqq \dim_{\F_{p}} C$ ,

\Theta_{\Lat(C)}(t) = p^{k - n/2} t^{-n/2} \Theta_{\Lat(C^{\perp})}(1/t) \tag{8.2}

for the Construction A lattice. This is precisely the theta transformation formula.

The same transformation is visible in the one-coordinate residue-class theta functions. From now on, put

\psi(a) = \exp(2\pi\iu a/p).

The element $a$ appearing in the exponential is read as the standard representative $0, 1, \dots, p - 1$ , according to the convention above. Changing the representative by an integer multiple of $p$ does not change the value, so this is well-defined as a function on $\F_{p}$ . Here $\C^{\times} = \C \setminus \{ 0 \}$ . The function $\psi$ is a homomorphism from the additive group of $\F_{p}$ to $\C^{\times}$ , namely an additive character. Indeed,

\psi(a + a^{\prime}) = \psi(a)\psi(a^{\prime}),

and $\psi \not{\equiv} 1$ .

Proposition 8.3 (One-coordinate residue-class theta transformation).

For every $a \in \F_{p}$ and $t > 0$ ,

\vartheta_{a}(t) = \frac{1}{\sqrt{pt}} \sum_{b \in \F_{p}} \psi(ab)\vartheta_{b}(1/t) \tag{8.3}

holds.

Proof

Put $g_{t}(x) = \e^{-\pi tx^{2}}$ . Substituting

h = \sqrt{p}, \qquad x_{0} = \frac{a}{\sqrt{p}}

into Corollary 5.6 (Translated Poisson summation formula).Let $f \colon \R \to \C$ be a Schwartz function, let $h > 0$ , and let $x_{0} \in \R$ . Then $\sum_{r \in \Z} f(x_{0} + rh) = \frac{1}{h} \sum_{s \in \Z} \exp(2\pi\iu\,s x_{0}/h)\, \what{f}(s/h) \tag{5.2}$ holds.Corollary 5.6, we obtain

\sum_{r \in \Z} g_{t} \left(\frac{a}{\sqrt{p}} + r\sqrt{p} \right) = \frac{1}{\sqrt{p}} \sum_{s \in \Z} \exp(2\pi\iu as/p) \what{g_t} \left(\frac{s}{\sqrt{p}}\right).

By Theorem 5.3,

\what{g_t}(y) = t^{-1/2}\e^{-\pi y^{2}/t},

so we get

\vartheta_{a}(t) = \frac{1}{\sqrt{pt}} \sum_{s\in\Z} \exp(2\pi\iu as/p) \exp\left(-\frac{\pi s^2}{pt}\right).

Splitting this sum according to residue classes $b\in\F_p$ gives

\begin{aligned} &\sum_{s\in\Z} \exp(2\pi\iu as/p) \exp\left(-\frac{\pi s^2}{pt}\right) \\ &\qquad= \sum_{b\in\F_p} \sum_{\substack{s\in\Z\\s\equiv b\pmod p}} \exp(2\pi\iu as/p) \exp\left(-\frac{\pi s^2}{pt}\right) \\ &\qquad= \sum_{b\in\F_p} \psi(ab) \sum_{\substack{s\in\Z\\s\equiv b\pmod p}} \exp\left(-\frac{\pi s^2}{pt}\right) \\ &\qquad= \sum_{b\in\F_p} \psi(ab)\vartheta_b(1/t). \end{aligned}

Here, if $s\equiv b\pmod p$ , then $as \equiv ab \pmod p$ , and so $\exp(2\pi\iu as/p)=\psi(ab)$ . Hence

\vartheta_a(t) = \frac{1}{\sqrt{pt}} \sum_{b\in\F_p}\psi(ab)\vartheta_b(1/t).

When $p = 2$ , we have $\psi(ab) = (-1)^{ab}$ , and hence

\begin{aligned} \vartheta_{0}(t) &= \frac{\vartheta_{0}(1/t) + \vartheta_{1}(1/t)}{\sqrt{2t}}, \\ \vartheta_1(t) &= \frac{\vartheta_0(1/t)-\vartheta_1(1/t)}{\sqrt{2t}}. \end{aligned}

The sum and difference appearing here are the Gaussian specialisations of the change of variables that later become

X + Y, \qquad X - Y

in the Hamming-weight MacWilliams identity.

What we have obtained so far is the transformation formula for lattice theta functions coming from Gaussian functions. However, residue-class theta functions are special functions depending on a single real variable $t$ , and they do not allow the $p$ variables of the complete weight enumerator to vary independently. In the next section, we therefore use arbitrary Schwartz functions and specify the residue-class sums independently, thereby extracting the polynomial identity behind this transformation.

One-Coordinate Poisson Summation Formula

To extract the MacWilliams change of variables, it is enough to look at how the one-coordinate residue-class sums change under the Fourier transform. From here on, we use arbitrary Schwartz functions, not just Gaussian functions. This generalisation lets us treat the $p$ formal variables of the complete weight enumerator independently. Write $\F_{p}^{\times} \coloneqq \F_{p} \setminus \{ 0 \}$ .

For a Schwartz function $f \colon \R \to \C$ , we defined

S_{a}(f) = \sum_{m \equiv a \pmod{p}} f\left(\frac{m}{\sqrt{p}}\right).

Lemma 9.1 (Orthogonality of additive characters).

For every $a \in \F_{p}$ ,

\sum_{b \in \F_{p}}\psi(ab) = \begin{cases} p, & a = 0,\\ 0, & a \neq 0 \end{cases}

holds.

Proof

If $a = 0$ , each term is $1$ , so the sum is $p$ . If $a \neq 0$ , the map $b \mapsto ab$ is a permutation of $\F_{p}$ . Therefore

\sum_{b \in \F_{p}}\psi(ab) = \sum_{u \in \F_{p}}\psi(u) = \sum_{u = 0}^{p - 1}\exp(2\pi\iu u/p).

This is a geometric series of $p$ -th roots of unity whose ratio is not $1$ , so it is $0$ .

Similarly, for the Fourier transform $\what{f}$ , we write

S_{b}(\what{f}) = \sum_{m \equiv b \pmod{p}} \what{f} \left(\frac{m}{\sqrt{p}}\right).

Theorem 9.2 (One-coordinate Poisson summation formula).

For the Schwartz function $f$ defined above and for every $a \in \F_{p}$ ,

S_{a}(f) = \frac{1}{\sqrt{p}} \sum_{b \in \F_{p}} \psi(ab)S_{b}(\what{f}) \tag{9.1}

holds.

Proof

The left-hand side is

S_{a}(f) = \sum_{r \in \Z} f\left(\frac{a + pr}{\sqrt{p}}\right).

This is the sum over the translate of the one-dimensional lattice $\sqrt p\,\Z$ by $a/\sqrt p$ , namely the lattice coset

\frac{a}{\sqrt p} + \sqrt{p}\,\Z.

Substituting

h = \sqrt{p}, \qquad x_{0} = \frac{a}{\sqrt{p}}

\sum_{r \in \Z} f\left(\frac{a}{\sqrt{p}} + r\sqrt{p} \right) = \frac{1}{\sqrt{p}} \sum_{s \in \Z} \e^{2\pi\iu sa/p} \what{f}\left(\frac{s}{\sqrt{p}}\right).

Splitting the integer $s \in \Z$ on the right-hand side according to residue classes $b \in \F_{p}$ gives

\begin{aligned} S_{a}(f) &= \frac{1}{\sqrt{p}} \sum_{b \in \F_{p}} \e^{2\pi\iu ab/p} \sum_{s \equiv b \pmod{p}} \what{f} \left(\frac{s}{\sqrt{p}}\right) \\ &= \frac{1}{\sqrt{p}} \sum_{b \in \F_{p}}\psi(ab)S_{b}(\what{f}). \end{aligned}

This formula is precisely the one-coordinate Fourier transform over the finite field. It is the result of reading the continuous Poisson summation formula residue class by residue class, and the character table $(\psi(ab))_{a, b \in \F_{p}}$ of the finite group $\F_{p}$ appears. In other words, the finite Fourier transform is extracted from the continuous Poisson summation formula.

For later use with formal variables, we also check that residue-class sums can be prescribed arbitrarily.

Lemma 9.3.

For any sequence of complex numbers $(z_{a})_{a \in \F_{p}}$ , there exists a Schwartz function $g \colon \R \to \C$ such that

\sum_{m \equiv a \pmod{p}} g\left(\frac{m}{\sqrt{p}}\right) = z_{a} \qquad(a \in \F_{p}).

Proof

The support of a function is the closure of the set on which the function is non-zero. This uses the same word support as for codewords, but here it means the support of a function. For each representative $a \in \{ 0, 1, \dots, p - 1 \}$ , choose a smooth compactly supported function $\phi_{a}$ supported in a neighbourhood of $a/\sqrt{p}$ . Choose the support so that it contains no point of

\left\{ \frac{m}{\sqrt{p}} : m \in \Z \right\}

other than $a/\sqrt{p}$ . For example, it is enough to make the support contained in an interval of radius less than $1/(3\sqrt{p})$ centred at $a/\sqrt{p}$ . Normalise further so that

\phi_{a}(a/\sqrt{p}) = 1.

Such functions can be constructed by translating and rescaling bump functions used standardly in analysis. Then

g(x) = \sum_{a = 0}^{p - 1} z_{a} \phi_{a}(x)

is smooth and compactly supported, hence a Schwartz function, and each residue-class sum is the prescribed value $z_{a}$ . Indeed, by the choice of support, among the sample points belonging to the residue class $b$ , only $b/\sqrt p$ contributes, and at that point $\phi_b(b/\sqrt p)=1$ while the other $\phi_a$ take the value $0$ . Thus

\begin{aligned} S_b(g) &= \sum_{\substack{m\in\Z\\m\equiv b\pmod p}} g\left(\frac{m}{\sqrt p}\right) \\ &= g\left(\frac{b}{\sqrt p}\right) \\ &= z_b. \end{aligned}

We apply this lemma to $g = \what{f}$ . By Proposition 5.4 (Fourier transform on the Schwartz space).The following hold for the Fourier transform. If $f$ is a Schwartz function, then $\what{f}$ is also a Schwartz function.Under the convention for the Fourier transform adopted above, $\what{\what{f}}(x) = f(-x)$ holds.Consequently, the Fourier transform is a linear automorphism of the space of Schwartz functions.For a one-variable Schwartz function $f \colon \R \to \C$ and $f_{E}(x) = \prod_{e \in E} f(x_{e}),$ the function $f_E$ is a Schwartz function on $\R^E$ , and $\what{f_{E}}(y) = \prod_{e \in E} \what{f}(y_{e})$ holds.Proposition 5.4, the Fourier transform is an automorphism of the space of Schwartz functions, so for any $g$ there exists a Schwartz function $f$ such that $g = \what{f}$ . Thus the values $S_{a}(\what{f})$ can be prescribed arbitrarily. This freedom lets us extract the MacWilliams identity as a polynomial identity from the Poisson summation formula.

From the Poisson Summation Formula to the Complete MacWilliams Identity

Using the preparation so far, we prove the complete-weight-enumerator MacWilliams identity. What we obtain here is not merely the theta transformation formula for Gaussian functions, but a polynomial identity extracted from arbitrary Schwartz functions and the freedom of residue-class sums. In the proof, we first show the equality for an arbitrary evaluation point $z=(z_b)_{b\in\F_p}\in\C^p$ . Then, since both sides are polynomials in the formal variables $T_b$ , we conclude that it is an identity in those formal variables.

Theorem 10.1 (Complete-weight-enumerator MacWilliams identity).

Let $C \leq \F_{p}^{E}$ be a $k$ -dimensional $\F_{p}$ -linear code. For each $b \in \F_{p}$ , prepare a variable $T_{b}$ . Then

\cwe_{C^{\perp}}\bigl((T_{b})_{b \in \F_{p}} \bigr) = \frac{1}{p^{k}} \cwe_{C}\left( \left(\sum_{b \in \F_{p}} \psi(ab) T_{b} \right)_{a \in \F_{p}} \right) \tag{10.1}

holds.

Proof

First fix an arbitrary evaluation point

z=(z_b)_{b\in\F_p}\in\C^p.

By Lemma 9.3 and the invertibility of the Fourier transform, we can choose a Schwartz function $f$ such that

S_{b}(\what{f}) = z_{b} \qquad(b \in \F_{p}).

By Theorem 9.2,

S_{a}(f) = \frac{1}{\sqrt p}\sum_{b \in \F_{p}} \psi(ab) z_{b}. \tag{10.2}

Next, consider the function on $\R^{E}$ given by

f_{E}(x) = \prod_{e \in E} f(x_{e}).

\what{f_{E}}(y) = \prod_{e \in E}\what{f}(y_{e}).

Applying the Poisson summation formula to the Construction A lattice $\Lat(C)$ gives

\sum_{x \in \Lat(C)} f_{E}(x) = \frac{1}{\vol(\R^{E}/\Lat(C))} \sum_{y\in\Lat(C)^{\ast}}\what{f_{E}}(y).

By Proposition 4.4 and Theorem 4.5,

\vol(\R^{E}/\Lat(C)) = p^{n/2 - k}, \qquad \Lat(C)^{\ast} = \Lat(C^{\perp}),

and therefore

\sum_{x \in \Lat(C)} f_{E}(x) = p^{k-n/2} \sum_{y \in \Lat(C^{\perp})} \what{f_{E}}(y). \tag{10.3}

\cwe_{C}\bigl((S_{a}(f))_{a \in \F_{p}}\bigr) = p^{k - n/2} \cwe_{C^{\perp}}\bigl((S_{b}(\what{f}))_{b \in \F_{p}}\bigr).

Since $S_{b}(\what{f}) = z_{b}$ and (10.2) holds, we have

\cwe_{C}\left( \left(\frac{1}{\sqrt{p}} \sum_{b \in \F_{p}} \psi(ab)z_{b} \right)_{a \in \F_{p}} \right) = p^{k - n/2} \cwe_{C^{\perp}}\bigl((z_{b})_{b \in \F_{p}}\bigr).

The complete weight enumerator is a homogeneous polynomial of total degree $n$ , so the factor $1/\sqrt{p}$ on the left-hand side contributes an overall factor $p^{-n/2}$ . Hence

p^{-n/2} \cwe_{C}\left( \left(\sum_{b \in \F_{p}}\psi(ab) z_{b} \right)_{a \in \F_{p}} \right) = p^{k - n/2} \cwe_{C^{\perp}}\bigl((z_{b})_{b \in \F_{p}}\bigr).

Multiplying both sides by $p^{n/2 - k}$ gives the equality (10.1) evaluated at $T_b=z_b$ .

The obtained equality holds for every $z\in\C^p$ . On the other hand, both sides are complex-coefficient polynomials in the formal variables $(T_b)_{b\in\F_p}$ . Therefore the equality also holds as a polynomial identity. This uses the fact that a complex-coefficient multivariable polynomial that vanishes at every point of $\C^p$ by taking the value $0$ is the zero polynomial.

The theta transformation formula for Construction A lattices obtained from Gaussian functions comes back as a specialisation of this complete-weight- enumerator identity. Substitute

T_b=\vartheta_b(1/t) \qquad(b\in\F_p)

into Theorem 10.1 (Complete-weight-enumerator MacWilliams identity).Let $C \leq \F_{p}^{E}$ be a $k$ -dimensional $\F_{p}$ -linear code. For each $b \in \F_{p}$ , prepare a variable $T_{b}$ . Then $\cwe_{C^{\perp}}\bigl((T_{b})_{b \in \F_{p}} \bigr) = \frac{1}{p^{k}} \cwe_{C}\left( \left(\sum_{b \in \F_{p}} \psi(ab) T_{b} \right)_{a \in \F_{p}} \right) \tag{10.1}$ holds.Theorem 10.1. Using Proposition 8.3 in the form

\sum_{b\in\F_p}\psi(ab)\vartheta_b(1/t) = \sqrt{pt}\,\vartheta_a(t),

we get

\begin{aligned} \Theta_{\Lat(C^\perp)}(1/t) &= \cwe_{C^\perp}\bigl((\vartheta_b(1/t))_{b\in\F_p}\bigr) \\ &= p^{-k} \cwe_C\bigl((\sqrt{pt}\,\vartheta_a(t))_{a\in\F_p}\bigr). \end{aligned}

Since the complete weight enumerator is a homogeneous polynomial of total degree $n$ ,

\Theta_{\Lat(C^\perp)}(1/t) = p^{n/2-k}t^{n/2}\Theta_{\Lat(C)}(t)

is obtained. Rearranging this gives

\Theta_{\Lat(C)}(t) = p^{k-n/2}t^{-n/2} \Theta_{\Lat(C^\perp)}(1/t).

This agrees with the theta transformation formula for Construction A lattices obtained in (8.2).

Let us organise where the coefficients come from. From the one-coordinate Poisson summation formula, a factor $p^{-1/2}$ appears in each coordinate. Since the complete weight enumerator is a homogeneous polynomial of total degree $n$ , this becomes $p^{-n/2}$ over all coordinates. On the other hand, the covolume of the Construction A lattice gives the coefficient $p^{k-n/2}$ in the lattice Poisson summation formula. Putting these together, the final coefficient left over is $p^{-k}=1/\card{C}$ .

Let us also check the roles played by lattice theory and analysis in this proof. By Construction A, the code $C$ was turned into the lattice $\Lat(C)$ . By the Poisson summation formula, the sum over $\Lat(C)$ was turned into a sum over the dual lattice $\Lat(C)^{\ast}$ . Since $\Lat(C)^{\ast} = \Lat(C^{\perp})$ , the dual code appeared there. The Poisson summation formula for one-coordinate residue-class sums gave the change of variables for the complete weight enumerator.

Hamming-Weight MacWilliams Identity

From the complete-weight-enumerator version, we obtain the usual Hamming-weight MacWilliams identity. Here $q = p$ , so the target is

W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}\bigl(X + (p - 1)Y, X - Y \bigr).

Theorem 11.1 (Hamming-weight MacWilliams identity).

Let $C \leq \F_{p}^{E}$ be a linear code. Then

W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}\bigl( X + (p - 1)Y, X - Y \bigr)

holds.

Proof

Put $k \coloneqq \dim_{\F_{p}} C$ . In Theorem 10.1 (Complete-weight-enumerator MacWilliams identity).Let $C \leq \F_{p}^{E}$ be a $k$ -dimensional $\F_{p}$ -linear code. For each $b \in \F_{p}$ , prepare a variable $T_{b}$ . Then $\cwe_{C^{\perp}}\bigl((T_{b})_{b \in \F_{p}} \bigr) = \frac{1}{p^{k}} \cwe_{C}\left( \left(\sum_{b \in \F_{p}} \psi(ab) T_{b} \right)_{a \in \F_{p}} \right) \tag{10.1}$ holds.Theorem 10.1, specialise to

T_{0} = X, \qquad T_{b} = Y \quad(b \neq 0).

The left-hand side is

\cwe_{C^{\perp}}\bigl((T_{b})_{b \in \F_{p}}\bigr) = W_{C^{\perp}}(X, Y).

We compute the variables on the right-hand side. When $a = 0$ ,

\sum_{b \in \F_{p}} \psi(0 \cdot b) T_{b} = X + (p - 1)Y.

On the other hand, when $a \neq 0$ , Lemma 9.1 gives

\sum_{b \in \F_{p}} \psi(ab) = 0,

and hence

\sum_{b \in \F_{p}^{\times}}\psi(ab) = -1.

Therefore

\sum_{b \in \F_{p}} \psi(ab) T_{b} = X + Y\sum_{b \in \F_{p}^{\times}} \psi(ab) = X - Y.

Thus the right-hand side becomes

\frac{1}{p^{k}} W_{C}\bigl( X + (p - 1)Y, X - Y \bigr).

Since $C$ is a $k$ -dimensional $\F_{p}$ -linear space, $p^{k} = \card{C}$ , and the claim follows.

This derives the MacWilliams identity from Construction A and the Poisson summation formula. In the usual character-theoretic proof, finite sums over the finite set $\F_{p}^{E}$ are computed. By contrast, in the proof in this note, the code is first lifted to a lattice, which is an infinite set, and the Poisson summation formula over that lattice is used. After that, by reading off the one-coordinate sums over residue classes, we return to the MacWilliams identity over the finite field.

A Small Example: The Binary Repetition Code of Length Three

Finally, let us check the formula in a small example. Let $p = 2$ and $E = \{ 1, 2, 3 \}$ , and consider the binary repetition code

C = \{ 000, 111 \} \leq \F_{2}^{3}.

The weight enumerator of this code is

W_{C}(X, Y) = X^{3} + Y^{3}.

The dual code is the even-weight code

C^{\perp} = \{ 000, 110, 101, 011 \},

and its weight enumerator is

W_{C^{\perp}}(X, Y) = X^{3} + 3XY^{2}.

Computing the right-hand side of the MacWilliams identity gives

\begin{aligned} \frac{1}{\card{C}} W_{C}(X + Y, X - Y) &= \frac{1}{2}\left((X + Y)^{3} + (X - Y)^{3} \right) \\ &= X^{3} + 3XY^{2}, \end{aligned}

which indeed agrees with $W_{C^{\perp}}(X, Y)$ .

Looking at the Construction A lattice, we have

\Lat(C) = \left\{ \frac{x}{\sqrt{2}} \in \R^{3}: x_{1} \equiv x_{2} \equiv x_{3} \pmod{2} \right\}.

The unnormalised lattice can be written as

L(C) = \Z(2,0,0)+\Z(0,2,0)+\Z(1,1,1).

The elements of the right-hand side have all three coordinates of the same parity. Also,

(0,0,2)=2(1,1,1)-(2,0,0)-(0,2,0),

so all three even-coordinate directions can also be generated. Conversely, if the three coordinates have the same parity, subtracting an integer multiple of $(1,1,1)$ makes all coordinates even, and the remainder can be expressed as an integer combination of $(2,0,0)$ , $(0,2,0)$ , and $(0,0,2)$ . On the other hand, the lattice obtained from $C^{\perp}$ is

\Lat(C^{\perp}) = \left\{ \frac{y}{\sqrt{2}} \in \R^{3}: y_{1} + y_{2} + y_{3} \equiv 0 \pmod{2} \right\}.

The unnormalised lattice can be written as

L(C^{\perp}) = \Z(1,1,0)+\Z(1,0,1)+\Z(0,1,1).

The elements of the right-hand side have even coordinate sum. Conversely, if $y=(y_1,y_2,y_3)\in\Z^3$ has even coordinate sum, then

y = \frac{y_1+y_2-y_3}{2}(1,1,0) + \frac{y_1-y_2+y_3}{2}(1,0,1) + \frac{-y_1+y_2+y_3}{2}(0,1,1).

Since the coordinate sum is even, all three coefficients are integers. The absolute values of the determinants of the basis matrices are $4$ and $2$ , respectively. Taking into account also the change in volume caused by multiplying by $1/\sqrt2$ , we get

\vol(\R^{3}/\Lat(C))=\sqrt2, \qquad \vol(\R^{3}/\Lat(C^{\perp}))=\frac{1}{\sqrt2}.

This example also concretely confirms that the covolumes of dual lattices are reciprocals. By Theorem 4.5, these two lattices are dual to each other. The Poisson summation formula connects the Gaussian-weighted lattice sums over these two lattices. In the Gaussian case, what appears in one coordinate is the sum and difference of residue-class theta sums,

\vartheta_{0}(1/t)+\vartheta_{1}(1/t), \qquad \vartheta_{0}(1/t)-\vartheta_{1}(1/t).

When we pass to arbitrary Schwartz functions and prescribe the residue-class sums after the Fourier transform as the formal variables $X,Y$ , these become $X+Y$ and $X-Y$ . In this example, the only non-zero residue class is $1$ , so there is no difference between the complete weight enumerator and the Hamming weight enumerator.

What Lattices and Theta Functions Did in This Proof

Let us organise the roles played by lattices and theta functions in the proof in this note.

First, Construction A lifted a code to a lattice. The code $C \leq \F_{p}^{E}$ is a finite set, but the Construction A lattice $\Lat(C) \subseteq \R^{E}$ is an infinite set. Nevertheless, its lattice points are controlled by the residue classes in $C$ . That is, for $x \in \Lat(C)$ , we have $\sqrt{p}\,x \in \Z^{E}$ , and reducing this modulo $p$ gives a codeword of $C$ .

Second, the dual code appeared as the dual lattice.

\Lat(C)^{\ast} = \Lat(C^{\perp})

is the equality connecting duality in coding theory with duality in lattice theory. Without this equality, the dual code would not appear even if we used the Poisson summation formula.

Third, decomposition into residue classes expressed a lattice-point sum as a substitution into the complete weight enumerator. When the lattice points are separated by residue class, the complete weight enumerator appears. Using a Gaussian function, that sum is a lattice theta function. Using a general Schwartz function, the variables of the complete weight enumerator can be varied freely.

Fourth, the Poisson summation formula gave the MacWilliams transform. When the Poisson summation formula, which transforms a sum over a lattice into a sum over the dual lattice, is read as a statement about one-coordinate residue-class sums, the character table of the finite field $\F_{p}$ appears. The change of variables given by that character table is the complete-weight- enumerator MacWilliams identity. For the Hamming weight enumerator, specialising all non-zero variables to the same variable $Y$ produces

X + (p - 1)Y, \qquad X - Y.

In one sentence, the key point is as follows.

With Gaussian functions, the theta transformation formula appears; with arbitrary Schwartz functions, the complete-weight-enumerator MacWilliams identity behind it appears.

Concepts Seen in This Part

In this part, while aiming at a proof of the MacWilliams identity, we introduced basic tools concerning lattices and theta functions. They can be organised as follows.

Euclidean lattice

A discrete set of points in $\R^{n}$ obtained as integer linear combinations of finitely many linearly independent vectors. In this note, we mainly treated full-rank lattices.

Covolume

The volume of a fundamental domain of a lattice. For a Construction A lattice, if $C \leq \F_{p}^{E}$ has dimension $k$ , then

\vol(\R^{E}/\Lat(C)) = p^{n/2 - k}.

Dual lattice

The set of vectors having integer-valued inner product with every lattice point. In Construction A,

\Lat(C)^{\ast} = \Lat(C^{\perp})

holds, and duality of codes appeared as duality of lattices.

Poisson summation formula

The formula connecting a sum over a lattice with the sum of the Fourier transform over the dual lattice. This is the deeper principle behind the proof in this note.

Theta function

The function obtained by summing the Gaussian function over lattice points. By the Poisson summation formula, the theta function is connected with the theta function of the dual lattice by a transformation formula.

Construction A

A method for constructing a lattice from a code $C \leq \F_{p}^{E}$ by using integer vectors satisfying the congruence condition $m \bmod{p} \in C$ . It is the most basic construction connecting codes and lattices.

Complete weight enumerator

A weight enumerator that records each symbol $a \in \F_{p}$ by a separate variable $T_{a}$ . The residue-class sums of a Construction A lattice were expressed as a complete weight enumerator.

Looking Back at This Family of Proofs

As stated at the beginning, the proof in this note belongs to the family

Fourier, character, and Poisson-type proofs.

However, the tools appearing on the surface were not character theory of finite abelian groups, but lattices, theta functions, and the Poisson summation formula.

The correspondence in this part can be organised as follows.

Code side	Lattice and analytic side
Code $C$	Construction A lattice $\Lat(C)$
Dual code $C^{\perp}$	Dual lattice $\Lat(C)^{\ast}$
Substitution of residue-class sums into the complete weight enumerator	Sum of product-type functions over the Construction A lattice
MacWilliams change of variables	Finite Fourier transform arising from the one-coordinate Poisson summation formula

At a deeper level, the proof in this note points in the same direction as the character-theoretic proof over finite fields. However, by viewing it not as a character sum over a finite set but as the Poisson summation formula over a continuous space, the Gaussian case gives a theta transformation formula, and the arbitrary Schwartz-function case gives the complete-weight-enumerator MacWilliams identity. This difference is the phenomenon we want to see in this series: the same theorem appearing in the languages of different areas.

The Case of General $q = p^{d}$

This section is an advanced supplement and is an outline of extensions not used in the main proof. You may skip it on a first reading.

In this note, the main text treated codes over $\F_{p}$ because we used the standard integer lattice $\Z^{n}$ and congruences $\bmod{p}$ . How should one think about a general finite field $\F_{q}$ , where $q = p^{d}$ ?

One method is to regard $\F_{q}$ as a $d$ -dimensional vector space over $\F_{p}$ and express each symbol as a block of $d$ $p$ -ary coordinates. In this case, the lattice is constructed inside $\R^{E\times[d]}$ , namely inside a real space of dimension $dn$ . However, one must be careful about duality. Below we write

[d]\coloneqq\{1,\dots,d\}

and explicitly regard the coordinate set as $E\times[d]$ . When $q=p^d$ , the trace of finite fields is defined by

\Tr_{\F_{q}/\F_{p}}(z) = z + z^{p} + \dots + z^{p^{d - 1}}.

As a standard fact, the trace pairing

(x,y)\longmapsto \Tr_{\F_q/\F_p}(xy)

is non-degenerate. Therefore, for any $\F_p$ -basis, there is a trace-dual basis. If $\beta_{1}, \dots, \beta_{d}$ is an $\F_{p}$ -basis of $\F_{q}$ , its trace-dual basis $\beta_{1}^{\vee}, \dots, \beta_{d}^{\vee}$ is the basis satisfying

\Tr_{\F_{q}/\F_{p}}(\beta_{i} \beta_{j}^{\vee}) = \delta_{ij}.

Here $\delta_{ij}$ is the Kronecker delta mentioned above.

We use these two bases separately. For $c=(c_e)_{e\in E}\in\F_q^E$ , expand

c_e=\sum_{j=1}^d c_{e,j}\beta_j \qquad(c_{e,j}\in\F_p)

and define

\Phi_\beta(c) \coloneqq (c_{e,j})_{(e,j)\in E\times[d]} \in \F_p^{E\times[d]}.

Similarly, expand $u=(u_e)_{e\in E}\in\F_q^E$ as

u_e=\sum_{j=1}^d u_{e,j}\beta_j^\vee \qquad(u_{e,j}\in\F_p)

and define

\Phi_{\beta^\vee}(u) \coloneqq (u_{e,j})_{(e,j)\in E\times[d]} \in \F_p^{E\times[d]}.

The dot product on $\F_p^{E\times[d]}$ is the standard inner product

v\cdot w = \sum_{(e,j)\in E\times[d]} v_{e,j}w_{e,j}.

With this notation, for $c,u\in\F_q^E$ ,

\Phi_\beta(c)\cdot\Phi_{\beta^\vee}(u) = \Tr_{\F_q/\F_p}(u\cdot c)

holds. Indeed, in each coordinate,

\Tr_{\F_q/\F_p}(u_e c_e) = \sum_{j=1}^d u_{e,j}c_{e,j}.

Here the ${}^\perp$ in

\Phi_\beta(C)^\perp

denotes the $\F_p$ -dual with respect to the standard inner product on $\F_p^{E\times[d]}$ .

Then

\Phi_{\beta^{\vee}}(C^{\perp}) = \Phi_{\beta}(C)^{\perp}

follows. It is important here that the basis $\beta$ is used on the $C$ side, while the trace-dual basis $\beta^\vee$ is used on the $C^\perp$ side. In general, the same basis is not being used on both sides. Therefore, even if $C=C^\perp$ , the subspaces $\Phi_\beta(C)$ and $\Phi_{\beta^\vee}(C^\perp)$ need not be literally the same under the chosen coordinate representations. Indeed, if $u \cdot c = 0$ , then of course its trace is also $0$ , so $\Phi_{\beta^{\vee}}(u)$ is orthogonal to $\Phi_{\beta}(C)$ . Conversely, suppose that $\Tr_{\F_{q}/\F_{p}}(u \cdot c) = 0$ for all $c\in C$ . Since $C$ is $\F_{q}$ -linear, we have $\lambda c \in C$ for every $\lambda \in \F_{q}$ . Therefore

\Tr_{\F_{q}/\F_{p}}(\lambda (u \cdot c)) = 0 \qquad(\lambda \in \F_{q})

holds. By non-degeneracy of the trace pairing, this implies $u\cdot c=0$ . Thus $u\in C^\perp$ .

From here, we can apply the duality theorem for Construction A proved in the main text to the $p$ -ary linear code over $\F_p^{E\times[d]}$ . In other words, when applying Construction A, we regard the coordinate set as $E\times[d]$ . The choice of an ordering of the real coordinates changes only a coordinate permutation of the lattice. Here $\Phi_\beta(C)$ and $\Phi_{\beta^\vee}(C^\perp)$ are $p$ -ary linear codes inside $\F_p^{E\times[d]}$ . Therefore

\Lat\bigl(\Phi_\beta(C)\bigr)^\ast = \Lat\bigl(\Phi_\beta(C)^\perp\bigr) = \Lat\bigl(\Phi_{\beta^\vee}(C^\perp)\bigr).

This formula is the basic correspondence for viewing the dual code as the dual lattice even over a general finite field.

For the one-coordinate Fourier transform over a general finite field, additive characters are also written using the trace. For example, for $a \in \F_{q}$ , if

\chi_{a}(b) = \exp\left( \frac{2\pi\iu}{p} \Tr_{\F_{q}/\F_{p}}(ab) \right),

then $b \mapsto \chi_{a}(b)$ is a character of the additive group of $\F_{q}$ .

However, the usual Hamming weight counts whether a block is zero or non-zero, and does not agree with the Hamming weight of the $dn$ $p$ -ary coordinates. Thus one must introduce variables that distinguish, block by block, the zero vector from the non-zero vectors. In this viewpoint, one $\F_q$ coordinate is regarded as one block of $\F_p^d$ . For each block, one uses a Schwartz function on $\R^d$ , rather than a one-dimensional Schwartz function. Then one independently specifies the sums over the $p^d=q$ residue classes of $(1/\sqrt p)\Z^d$ . This makes it possible to treat independently the variables of the complete weight enumerator corresponding to each $a\in\F_q$ . Finally, by merging variables according to whether the block is zero or non-zero, one specialises to the Hamming-weight version over $\F_q$ .

Another method is to use the ring of integers $\mathcal{O}_{K}$ of a number field and a prime ideal $\mathfrak{p}$ to realise

\mathcal{O}_{K}/\mathfrak{p} \cong \F_{q}

and perform Construction A inside $\mathcal{O}_{K}^{n}$ . In this case, $\mathcal{O}_{K}^{n}$ is moved to a real Euclidean space by the Minkowski embedding, and the image gives a lattice. Thus the contrast “not a Euclidean lattice, but a lattice obtained from an embedding of a number field” would not be accurate. After the Minkowski embedding, it is still a lattice inside a real Euclidean space. Trace forms and inverse differents appear in the description of the dual lattice. For CM fields, descriptions using Hermitian forms are also natural. This direction is deeply connected with theta functions, modular forms, and algebraic number theory.

Therefore, the proof using lattices and theta functions is most straightforward when $q = p$ . The same idea also exists for general $q = p^{d}$ , but for that one must go one step beyond the standard integer lattice $\Z^{n}$ and deal with block lattices or lattices over number fields. Since the purpose of this note is to provide an entry point to lattices and theta functions, the main text was restricted to $p$ -ary codes.

Appendix: Proofs of the Fourier Transform and Poisson Summation Formula

In this appendix, we collect proofs of the analytic facts whose statements were given in Summary of the Fourier Transform and Poisson Summation Formula. The details of this section are not used in the main proof. They are included for readers who want to check uniform convergence of Schwartz series over lattices, Fourier expansions of lattice-periodic functions, Fourier inversion, and related points. In the Fourier expansion of lattice-periodic functions, we use as a standard theorem the uniform convergence of multivariable Fejér means.

Lemma 17.1 (Uniform convergence of Schwartz series over lattices).

Let $\Lat=B\Z^n$ be a full-rank lattice, and let $K\subseteq\R^n$ be a compact set. Let $f$ be a Schwartz function. Then, for every multi-index $\beta$ , the series

\sum_{m\in\Z^n}\partial^\beta f(x+Bm)

converges absolutely and uniformly with respect to $x\in K$ . In particular, the lattice sum

\sum_{\lambda\in\Lat}\abs{f(\lambda)}

converges. Moreover, the periodised series

\sum_{\lambda\in\Lat}f(x+\lambda)

is smooth and may be differentiated term by term.

Proof

Since $B$ is invertible, there exists $c>0$ such that

\norm{Bm}\geq c\norm{m} \qquad(m\in\Z^n).

Also, since $K$ is bounded, there is $M>0$ such that $\norm{x}\leq M$ ( $x\in K$ ). Hence

\norm{x+Bm} \geq c\norm{m}-M \qquad(x\in K).

By the rapid decrease of Schwartz functions, for every $N$ there is a constant $A_{\beta,N}$ such that, after absorbing finitely many small $m$ into the constant, we have the estimate

\sup_{x\in K} \abs{\partial^\beta f(x+Bm)} \leq A_{\beta,N}(1+\norm{m})^{-N}.

If $N>n$ , the right-hand side is summable over $m\in\Z^n$ . By the Weierstrass test, the series converges absolutely and uniformly on $K$ . The same argument applies to all partial derivatives, so the periodised series is smooth and can be differentiated term by term.

This lemma shows that the series obtained by summing a Schwartz function over a lattice converges absolutely. Intuitively, the number of lattice points grows only polynomially, while a Schwartz function decreases faster than any polynomial. Since the Gaussian function is a Schwartz function, theta series also converge absolutely.

We prove Theorem 5.3.

Proof

We first treat the one-dimensional case. Put

I_{t}(y) \coloneqq \int_{\R} \e^{-\pi t x^{2}} \e^{-2\pi\iu xy} \dd x.

Since $x\e^{-\pi t x^{2}}$ is absolutely integrable, we may differentiate under the integral sign, and obtain

\begin{aligned} I_{t}^{\prime}(y) &= \int_{\R} (-2\pi\iu x) \e^{-\pi t x^{2}} \e^{-2\pi\iu xy} \dd x \\ &= \frac{\iu}{t} \int_{\R} \frac{\dd}{\dd x}\left(\e^{-\pi t x^{2}}\right) \e^{-2\pi\iu xy} \dd x. \end{aligned}

Integrating by parts, the boundary term vanishes by the rapid decrease of the Gaussian function, and

\begin{aligned} I_{t}^{\prime}(y) &= -\frac{\iu}{t} \int_{\R} \e^{-\pi t x^{2}} \frac{\dd}{\dd x} \left(\e^{-2\pi\iu xy}\right) \dd x \\ &= -\frac{2\pi y}{t} I_{t}(y). \end{aligned}

Therefore

I_{t}(y) = I_{t}(0)\e^{-\pi y^{2}/t}.

We now recall the standard Gaussian integral. Put

A \coloneqq \int_{\R}\e^{-\pi u^{2}}\dd u.

Since the integrand is non-negative, Tonelli's theorem and the change to polar coordinates give

\begin{aligned} A^{2} &= \int_{\R^{2}} \e^{-\pi(u^{2} + v^{2})} \dd u \dd v \\ &= \int_{0}^{2\pi} \int_{0}^{\infty} \e^{-\pi r^{2}} r \dd r \dd\theta \\ &= 1. \end{aligned}

Since $A > 0$ , we have $A = 1$ . The change of variables $u = \sqrt t\,x$ gives

I_{t}(0) = \int_{\R} \e^{-\pi t x^{2}} \dd x = t^{-1/2},

and hence

I_{t}(y) = t^{-1/2}\e^{-\pi y^{2}/t}.

For general $n$ , write $x = (x_{1}, \dots, x_{n})$ and $y = (y_{1}, \dots, y_{n})$ . Then

\e^{-\pi t\norm{x}^2} \e^{-2\pi\iu\inner{x}{y}} = \prod_{j=1}^{n} \e^{-\pi t x_{j}^{2}} \e^{-2\pi\iu x_{j} y_{j}}.

This function is absolutely integrable, so Fubini's theorem gives

\begin{aligned} \what{f_t}(y) &= \prod_{j=1}^{n} I_{t}(y_{j}) \\ &= \prod_{j=1}^{n} t^{-1/2}\e^{-\pi y_{j}^{2}/t} \\ &= t^{-n/2}\e^{-\pi\norm{y}^{2}/t}. \end{aligned}

In this note, we use Theorem 5.3 as a basic formula of standard Fourier analysis.

We prove Proposition 5.4 (Fourier transform on the Schwartz space).The following hold for the Fourier transform. If $f$ is a Schwartz function, then $\what{f}$ is also a Schwartz function.Under the convention for the Fourier transform adopted above, $\what{\what{f}}(x) = f(-x)$ holds.Consequently, the Fourier transform is a linear automorphism of the space of Schwartz functions.For a one-variable Schwartz function $f \colon \R \to \C$ and $f_{E}(x) = \prod_{e \in E} f(x_{e}),$ the function $f_E$ is a Schwartz function on $\R^E$ , and $\what{f_{E}}(y) = \prod_{e \in E} \what{f}(y_{e})$ holds.Proposition 5.4.

Proof

(1)

For a multi-index $\beta \in \Z_{\geq 0}^{n}$ , the function $x^{\beta} f(x)$ is absolutely integrable. Therefore, by the dominated convergence theorem, we may differentiate under the integral sign any number of times, obtaining

\partial_{y}^{\beta} \what{f}(y) = \what{ \bigl((-2\pi\iu x)^{\beta} f \bigr) }(y). \tag{17.1}

Here

(-2\pi\iu x)^{\beta} = \prod_{j=1}^{n} (-2\pi\iu x_{j})^{\beta_{j}}.

On the other hand, for a Schwartz function $h$ and a multi-index $\alpha$ , integration by parts in each coordinate gives

\what{\partial^{\alpha} h}(y) = (2 \pi \iu)^{\lvert\alpha\rvert_1} y^{\alpha} \what{h}(y). \tag{17.2}

Since a Schwartz function decreases rapidly together with all its partial derivatives, all boundary terms in the integrations by parts are $0$ .

Combining (17.1) and (17.2), for arbitrary multi-indices $\alpha$ and $\beta$ we get

y^{\alpha} \partial_{y}^{\beta} \what{f}(y) = (2\pi\iu)^{-\lvert\alpha\rvert_1} \what{ \partial^{\alpha} \bigl((-2\pi\iu x)^{\beta} f \bigr) }(y).

From the definition of the Fourier transform, for an absolutely integrable function $g$ ,

\abs{\what{g}(y)} \leq \int_{\R^{n}} \abs{g(x)} \dd x.

Therefore

\abs{ y^{\alpha} \partial_{y}^{\beta} \what{f}(y) } \leq (2\pi)^{-\lvert\alpha\rvert_1} \int_{\R^{n}} \abs{ \partial^{\alpha} \bigl((-2\pi\iu x)^{\beta} f(x)\bigr) } \dd x.

The right-hand side is finite and does not depend on $y$ . Hence

\sup_{y \in \R^{n}} \abs{ y^{\alpha} \partial_{y}^{\beta} \what{f}(y) } < \infty.

Since $\alpha$ and $\beta$ were arbitrary, $\what{f}$ is a Schwartz function.

(2)

We next prove the second assertion. For $\varepsilon > 0$ , put

G_{\varepsilon}(y) \coloneqq \e^{-\pi\varepsilon\norm{y}^{2}}

and define

I_{\varepsilon}(x) \coloneqq \int_{\R^{n}} \what{f}(y) \e^{2\pi\iu\inner{x}{y}} G_{\varepsilon}(y) \dd y.

By the first assertion, $\what{f}$ is a Schwartz function, and in particular is absolutely integrable. Since also $0 < G_{\varepsilon}(y) \leq 1$ , the dominated convergence theorem gives

\lim_{\varepsilon \downarrow 0} I_{\varepsilon}(x) = \int_{\R^{n}} \what{f}(y) \e^{2\pi\iu\inner{x}{y}} \dd y. \tag{17.3}

Substituting the definition of the Fourier transform gives

\begin{aligned} I_{\varepsilon}(x) &= \int_{\R^{n}} \int_{\R^{n}} f(u) \e^{-2\pi\iu\inner{u}{y}} \e^{2\pi\iu\inner{x}{y}} G_{\varepsilon}(y) \dd u\dd y. \end{aligned}

Here

\int_{\R^{n}} \abs{f(u)} \dd u \int_{\R^{n}} G_{\varepsilon}(y) \dd y < \infty,

so Fubini's theorem applies. Interchanging the order of integration and using Theorem 5.3, we get

\begin{aligned} I_{\varepsilon}(x) &= \int_{\R^{n}} f(u) \left( \int_{\R^{n}} G_{\varepsilon}(y) \e^{-2\pi\iu\inner{u-x}{y}} \dd y \right) \dd u \\ &= \int_{\R^{n}} f(u) \varepsilon^{-n/2} \e^{-\pi\norm{u - x}^{2}/\varepsilon} \dd u. \end{aligned}

With the change of variables $u = x + \sqrt{\varepsilon}\, v$ , this becomes

I_{\varepsilon}(x) = \int_{\R^{n}} f(x + \sqrt{\varepsilon}\,v) \e^{-\pi\norm{v}^{2}} \dd v.

The Schwartz function $f$ is bounded, and $\e^{-\pi\norm{v}^{2}}$ is absolutely integrable, so the dominated convergence theorem applies again. Also, by Fubini's theorem and the one-dimensional Gaussian integral $\int_{\R}\e^{-\pi u^2}\dd u=1$ , we have $\int_{\R^n}\e^{-\pi\norm{v}^{2}}\dd v=1$ . Hence

\begin{aligned} \lim_{\varepsilon \downarrow 0} I_{\varepsilon}(x) &= f(x) \int_{\R^{n}} \e^{-\pi\norm{v}^{2}} \dd v \\ &= f(x). \end{aligned}

From this and (17.3), we obtain the Fourier inversion formula

f(x) = \int_{\R^{n}} \what{f}(y) \e^{2 \pi \iu\inner{x}{y}} \dd y. \tag{17.4}

Replacing $x$ by $-x$ in (17.4) gives

\begin{aligned} \what{\what{f}}(x) &= \int_{\R^{n}} \what{f}(y) \e^{-2\pi\iu\inner{y}{x}} \dd y \\ &= f(-x), \end{aligned}

as desired.

(3)

Write the Fourier transform as $\mathcal{F}$ and the reflection operator as $(Rf)(x) = f(-x)$ . The second assertion means $\mathcal{F}^{2} = R$ . Since $R^{2}$ is the identity operator,

\mathcal{F}^{4} = (\mathcal{F}^{2})^{2} = R^{2} = \id.

Thus $\mathcal{F}^{-1} = \mathcal{F}^{3}$ , and the Fourier transform is a linear automorphism of the space of Schwartz functions.

(4)

Considering derivatives and polynomial multiplication in each coordinate shows that $f_{E}$ is also a Schwartz function on $\R^{E}$ . Moreover,

\int_{\R^{E}} \prod_{e \in E}\abs{f(x_{e})} \dd x = \left( \int_{\R}\abs{f(u)} \dd u \right)^{\card{E}} <\infty,

so Fubini's theorem applies. Therefore

\begin{aligned} \what{f_{E}}(y) &= \int_{\R^{E}} \prod_{e \in E} f(x_{e}) \e^{-2 \pi \iu\sum_{e \in E} x_{e} y_{e}} \dd x \\ &= \int_{\R^{E}} \prod_{e \in E} \left( f(x_{e}) \e^{-2\pi\iu x_{e} y_{e}} \right) \dd x \\ &= \prod_{e \in E} \int_{\R} f(x_{e}) \e^{-2\pi\iu x_{e} y_{e}} \dd x_{e} \\ &= \prod_{e \in E} \what{f}(y_{e}). \end{aligned}

Lemma 17.2 (Fourier expansion of a lattice-periodic function).

Let $\Lat = B\Z^{n}$ be a full-rank lattice, and put

\mathcal{P}=B[0,1)^{n}, \qquad V=\abs{\det B}.

Then $\Lat^{\ast}=(B^{\top})^{-1}\Z^{n}$ . For a smooth $\Lat$ -periodic function $H\colon\R^{n}\to\C$ , define

c_y \coloneqq V^{-1} \int_{\mathcal P} H(x)\e^{-2\pi\iu\inner{x}{y}}\dd x \qquad(y\in\Lat^{\ast}).

Then

H(x) = \sum_{y\in\Lat^{\ast}} c_y \e^{2\pi\iu\inner{x}{y}}

holds. This series converges absolutely and uniformly.

Proof

Put $h(u)=H(Bu)$ . Then $h$ is a smooth periodic function on the standard torus $\R^{n}/\Z^{n}$ . Writing $y=(B^{\top})^{-1}m$ ( $m\in\Z^{n}$ ), the change of variables $x=Bu$ gives

c_y = \int_{[0,1)^{n}} h(u)\e^{-2\pi\iu\inner{m}{u}}\dd u.

Thus the problem is reduced to Fourier series on the standard torus.

On the standard torus, the Fourier coefficients of a smooth periodic function decrease faster than any polynomial order. Indeed, put

\Delta \coloneqq \sum_{j=1}^{n}\frac{\partial^{2}}{\partial u_{j}^{2}}.

For any non-negative integer $N$ , periodic integration by parts gives

(1+4\pi^{2}\norm{m}^{2})^{N} c_{(B^{\top})^{-1}m} = \int_{[0,1)^{n}} (1-\Delta)^{N}h(u) \e^{-2\pi\iu\inner{m}{u}}\dd u.

The boundary terms cancel by periodicity. The right-hand side is uniformly bounded by a constant independent of $m$ , so there is a constant $A_N$ such that

\abs{c_{(B^{\top})^{-1}m}} \leq A_N(1+\norm{m}^{2})^{-N}.

If $N>n/2$ , the right-hand side is summable over $m\in\Z^{n}$ . By the Weierstrass test, the Fourier series converges absolutely and uniformly.

It remains only to check that this uniformly convergent series agrees with the original function. Here we use the standard theorem on Fourier series on the standard torus that the multivariable Fejér kernel made as a product of one-variable Fejér kernels is an approximate identity, and that the Fejér means of a continuous periodic function converge uniformly. On the other hand, Fejér means are finite sums made from Fourier coefficients. Since the Fourier coefficients are absolutely summable, the Fejér means also converge uniformly to the ordinary Fourier series. Therefore the Fourier series converges uniformly to $h$ . Returning to $x=Bu$ gives the claim.

We prove Theorem 5.5 (Poisson summation formula).Let $\Lat\subseteq\R^{n}$ be a full-rank lattice, and let $f\colon\R^{n}\to\C$ be a Schwartz function. Then $\sum_{x\in\Lat}f(x) = \frac{1}{\vol(\R^{n}/\Lat)} \sum_{y\in\Lat^{\ast}}\what{f}(y) \tag{5.1}$ holds.Theorem 5.5.

Proof

Write $\Lat=B\Z^{n}$ , and put

\mathcal P=B[0,1)^{n}, \qquad \overline{\mathcal P}=B[0,1]^n, \qquad V=\vol(\R^{n}/\Lat)=\abs{\det B}.

For a Schwartz function $f$ , define

P_{f}(x) \coloneqq \sum_{\lambda \in \Lat} f(x + \lambda).

This is plainly $\Lat$ -periodic. Applying Lemma 17.1 (Uniform convergence of Schwartz series over lattices).Let $\Lat=B\Z^n$ be a full-rank lattice, and let $K\subseteq\R^n$ be a compact set. Let $f$ be a Schwartz function. Then, for every multi-index $\beta$ , the series $\sum_{m\in\Z^n}\partial^\beta f(x+Bm)$ converges absolutely and uniformly with respect to $x\in K$ . In particular, the lattice sum $\sum_{\lambda\in\Lat}\abs{f(\lambda)}$ converges. Moreover, the periodised series $\sum_{\lambda\in\Lat}f(x+\lambda)$ is smooth and may be differentiated term by term.Lemma 17.1 to the compact set $K=\overline{\mathcal P}$ , the series and the series of all partial derivatives converge absolutely and uniformly on $\overline{\mathcal P}$ , and therefore also on $\mathcal P$ . This justifies exchanging sums and integrals over $\mathcal P$ . For smoothness and termwise differentiation, it is enough to apply the same lemma to compact sets contained in neighbourhoods of arbitrary points.

Apply Lemma 17.2 (Fourier expansion of a lattice-periodic function).Let $\Lat = B\Z^{n}$ be a full-rank lattice, and put $\mathcal{P}=B[0,1)^{n}, \qquad V=\abs{\det B}.$ Then $\Lat^{\ast}=(B^{\top})^{-1}\Z^{n}$ . For a smooth $\Lat$ -periodic function $H\colon\R^{n}\to\C$ , define $c_y \coloneqq V^{-1} \int_{\mathcal P} H(x)\e^{-2\pi\iu\inner{x}{y}}\dd x \qquad(y\in\Lat^{\ast}).$ Then $H(x) = \sum_{y\in\Lat^{\ast}} c_y \e^{2\pi\iu\inner{x}{y}}$ holds. This series converges absolutely and uniformly.Lemma 17.2 to $P_f$ . The Fourier coefficient for $y\in\Lat^{\ast}$ is

\begin{aligned} c_y &= V^{-1} \int_{\mathcal P} \sum_{\lambda\in\Lat} f(x+\lambda) \e^{-2\pi\iu\inner{x}{y}}\dd x . \end{aligned}

Since the convergence on the fundamental domain is uniform and absolute, we may interchange the sum and the integral. Thus

\begin{aligned} c_y &= V^{-1} \sum_{\lambda\in\Lat} \int_{\mathcal P} f(x+\lambda) \e^{-2\pi\iu\inner{x}{y}}\dd x . \end{aligned}

Make the change of variables $u=x+\lambda$ . Since $y\in\Lat^{\ast}$ , we have $\inner{\lambda}{y}\in\Z$ , and hence

\e^{2\pi\iu\inner{\lambda}{y}}=1.

Therefore

\begin{aligned} c_y &= V^{-1} \sum_{\lambda\in\Lat} \int_{\mathcal P+\lambda} f(u) \e^{-2\pi\iu\inner{u}{y}}\dd u . \end{aligned}

Since we are using a half-open fundamental domain, the family of sets $\{\mathcal P+\lambda:\lambda\in\Lat\}$ partitions $\R^n$ disjointly. Hence

c_y = V^{-1} \int_{\R^{n}} f(u)\e^{-2\pi\iu\inner{u}{y}}\dd u = V^{-1}\what{f}(y).

By Proposition 5.4 (Fourier transform on the Schwartz space).The following hold for the Fourier transform. If $f$ is a Schwartz function, then $\what{f}$ is also a Schwartz function.Under the convention for the Fourier transform adopted above, $\what{\what{f}}(x) = f(-x)$ holds.Consequently, the Fourier transform is a linear automorphism of the space of Schwartz functions.For a one-variable Schwartz function $f \colon \R \to \C$ and $f_{E}(x) = \prod_{e \in E} f(x_{e}),$ the function $f_E$ is a Schwartz function on $\R^E$ , and $\what{f_{E}}(y) = \prod_{e \in E} \what{f}(y_{e})$ holds.Proposition 5.4, $\what{f}$ is a Schwartz function. Therefore the lattice sum on the right, $\sum_{y\in\Lat^{\ast}}\what{f}(y)$ , also converges absolutely. From Lemma 17.2 (Fourier expansion of a lattice-periodic function).Let $\Lat = B\Z^{n}$ be a full-rank lattice, and put $\mathcal{P}=B[0,1)^{n}, \qquad V=\abs{\det B}.$ Then $\Lat^{\ast}=(B^{\top})^{-1}\Z^{n}$ . For a smooth $\Lat$ -periodic function $H\colon\R^{n}\to\C$ , define $c_y \coloneqq V^{-1} \int_{\mathcal P} H(x)\e^{-2\pi\iu\inner{x}{y}}\dd x \qquad(y\in\Lat^{\ast}).$ Then $H(x) = \sum_{y\in\Lat^{\ast}} c_y \e^{2\pi\iu\inner{x}{y}}$ holds. This series converges absolutely and uniformly.Lemma 17.2,

P_f(x) = \frac{1}{V} \sum_{y\in\Lat^{\ast}} \what{f}(y) \e^{2\pi\iu\inner{x}{y}}

holds. Finally, substituting $x=0$ gives

\sum_{\lambda\in\Lat}f(\lambda) = \frac{1}{V} \sum_{y\in\Lat^{\ast}}\what{f}(y).

This is exactly (5.1).

We prove Corollary 5.6 (Translated Poisson summation formula).Let $f \colon \R \to \C$ be a Schwartz function, let $h > 0$ , and let $x_{0} \in \R$ . Then $\sum_{r \in \Z} f(x_{0} + rh) = \frac{1}{h} \sum_{s \in \Z} \exp(2\pi\iu\,s x_{0}/h)\, \what{f}(s/h) \tag{5.2}$ holds.Corollary 5.6.

Proof

Put $g(x) = f(x + x_{0})$ . By the definition of the Fourier transform and the change of variables $u = x + x_{0}$ ,

\what{g}(y) = \exp(2\pi\iu\,x_{0} y) \what{f}(y).

Applying the usual Poisson summation formula to the lattice $h\Z$ gives

\sum_{r \in \Z} g(rh) = \frac{1}{h} \sum_{s \in \Z} \what{g}(s/h).

The left-hand side is $\sum_{r \in \Z} f(x_{0} + rh)$ , and substituting the formula above into the right-hand side gives the claim.

Next Time

At this point, the derivation of the MacWilliams identity from the viewpoint of lattices and theta functions, which is the main claim of this note, is complete. What follows is a preview within the series.

Next time, we look at the MacWilliams identity from the viewpoints of zeta functions and Riemann–Roch-type formulae. In the proof in this note, we constructed a lattice from a code, obtained the transformation formula for lattice theta functions in the Gaussian case, and extracted the complete-weight-enumerator MacWilliams identity in the arbitrary Schwartz-function case. Next time, we attach a zeta function to a code, and view the MacWilliams identity from the side of its functional equation and a Riemann–Roch-type dimension formula.

The main actors next time are

zeta functions of codes → Riemann–Roch-type formulae → functional equations → the MacWilliams identity

. Even though it is the same MacWilliams identity, next time it will appear not as the Poisson summation formula for lattices, but in the form of an arithmetic functional equation.

Footnotes

The terminology around this point collides quite heavily. In Japanese, the two meanings of lattice can be distinguished by using “格子” and “束”, but the Japanese word “束” can also refer both to a lattice in order theory and to a bundle, as in a vector bundle. In fact, when the author was first learning matroid theory, he mistakenly thought that the lattice appearing there was a lattice of points in space. ↩

References

[CS99] J. H. Conway and N. J. A. Sloane. Sphere packings, lattices and groups. Springer-Verlag, New York, vol. 290, pp. lxxiv+703, 1999. doi:10.1007/978-1-4757-6568-7 Citation contextFor the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.↩
[Ebe94] Wolfgang Ebeling. Lattices and codes. Friedr. Vieweg & Sohn, Braunschweig, pp. xvi+178, 1994. doi:10.1007/978-3-322-96879-1 Citation contextFor the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.↩
[Ser73] J.-P. Serre. A course in arithmetic. Springer-Verlag, New York-Heidelberg, vol. No. 7, pp. viii+115, 1973 Citation contextFor the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.↩
[BE72] Michel Broué and Michel Enguehard. Polynômes des poids de certains codes et fonctions thêta de certains réseaux. Ann. Sci. École Norm. Sup. (4), vol. 5, pp. 157–181, 1972. http://www.numdam.org/item?id=ASENS_1972_4_5_1_157_0 Citation contextFor the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.↩
[Key12] David Keyes. F_p-codes, theta functions and the Hamming weight MacWilliams identity. Adv. Math. Commun., vol. 6, no. 4, pp. 401–418, 2012. doi:10.3934/amc.2012.6.401 Citation contextFor the relation between Construction A, codes, and lattices, Conway–Sloane [CS99] and Ebeling [Ebe94] are standard references. For lattices, theta functions, and Poisson summation, Serre [Ser73] is also a classical and readable reference. A pioneering reference on the relation between weight enumerators of binary codes and lattice theta functions is Broué–Enguehard [BE72]. For an analytic proof of the Hamming-weight MacWilliams identity for $p$ -ary linear codes from theta functions, see Keyes [Key12]. In this note, we do not develop all these general theories, but instead state the analytic standard facts that are needed and extract only the part required for the case of linear codes over $\F_{p}$ . The case over general $\F_{p^{d}}$ is described at the end as an outline of an extension.↩
[Nis01] Shigeto Nishimura. Duality of codes and theta functions. Sci. Math. Jpn., vol. 53, no. 1, pp. 113–118, 2001 Citation contextThis example shows that the usual one-variable lattice theta function obtained from the Gaussian function cannot distinguish the symbols $1$ and $2=-1$ . To extract the complete-weight-enumerator identity, we need to be able to specify residue-class sums independently using arbitrary Schwartz functions. The one-variable family of Gaussian functions alone also does not have enough freedom to vary the $p$ variables of the complete weight enumerator independently. Passing to arbitrary Schwartz functions is a way of extracting the polynomial identity behind the special family of theta functions. The viewpoint of pointing out that residue-class theta functions are not algebraically independent in general, replacing them by formal variables, and then passing to the complete-weight-enumerator identity also appears in Nishimura [Nis01]. In this note, we make this passage to formal variables concrete as the construction of Schwartz functions realising arbitrary evaluation points. Thus it is accurate to regard the theta transformation formula for Gaussian functions as a specialisation of the complete-weight-enumerator MacWilliams identity proved later.↩

This series

A Series Learning through the MacWilliams Identity · Part 11 of 12

PreviousAn Introduction to Heat Kernels and Trace Formulas through the MacWilliams Identity

Back to series list

Disclaimer

Articles on this site are based on the operator's personal understanding, investigation, and research notes. I try to keep the content accurate, but it may contain errors or incomplete explanations. I do not guarantee its accuracy, completeness, usefulness, or currentness.

Please use the information on this site at your own judgment and responsibility. To the extent permitted by law, the operator is not liable for damages, losses, or disadvantages arising from using, or being unable to use, information on this site.

If you notice an error, unclear explanation, broken link, or insufficient citation, please contact the operator. I will review the content and, when appropriate, correct, update, or remove it.

§1Introduction

§2Lattices in Euclidean Space

§3Dual Lattices

§4Construction A: From Codes to Lattices

§5Summary of the Fourier Transform and Poisson Summation Formula

§6Lattice Theta Functions

§7Complete Weight Enumerators

§8Residue-Class Theta Functions

§9One-Coordinate Poisson Summation Formula

§10From the Poisson Summation Formula to the Complete MacWilliams Identity

§11Hamming-Weight MacWilliams Identity

§12A Small Example: The Binary Repetition Code of Length Three

§13What Lattices and Theta Functions Did in This Proof

§14Concepts Seen in This Part

§15Looking Back at This Family of Proofs

§16The Case of General q=pdq = p^{d}q=pd

§17Appendix: Proofs of the Fourier Transform and Poisson Summation Formula

§18Next Time

Footnotes

References

This series

Disclaimer

Introduction

Lattices in Euclidean Space

Dual Lattices

Construction A: From Codes to Lattices

Summary of the Fourier Transform and Poisson Summation Formula

Lattice Theta Functions

Complete Weight Enumerators

Residue-Class Theta Functions

One-Coordinate Poisson Summation Formula

From the Poisson Summation Formula to the Complete MacWilliams Identity

Hamming-Weight MacWilliams Identity

A Small Example: The Binary Repetition Code of Length Three

What Lattices and Theta Functions Did in This Proof

Concepts Seen in This Part

Looking Back at This Family of Proofs

The Case of General $q = p^{d}$

Appendix: Proofs of the Fourier Transform and Poisson Summation Formula

Next Time