This year’s Math 256x is a “topics class”
(taught here before, but last in 2001)
that develops the mathematical theory of error-correcting codes
and its connections with other areas of mathematics
ranging from combinatorics to group and representation theory
to projective and algebraic geometry.
We meet *Tuesdays and Thursdays from 11:30 AM to 1:00 PM*
in ~~Room 309~~ **Room 109**
of the Science Center.

If you find a mistake, omission, etc., please let me know by e-mail.

September 3:
Overview

September 5:
Introduction:
Hamming distance and Hamming space;
*n*, *M*, *d*) codes*q*-entropy

September 10: Linear codes
(and isometries of Hamming space)

First problem set:
continuity of the asymptotic rate functions;
a bit on spherical codes;
binary codes with *d* > *n*_{2}

**September 12: No Class**

September 17:
Linear codes and point configurations in projective space
(and introduction of several structures and constructions that
will recur later in the semester)

Second problem set
[*Corrected* Sep.18, see 3ii]:
More about point configurations and the associated linear codes

September 19:
Codes and point configurations, cont’d;
Segre’s theorem on ovals in algebraic projective planes of odd order

September 24:
More on conics, especially over finite fields, and projective spaces
in general; rational normal curves and classical Goppa codes.

We’ll use these
Lecture notes

September 26:
Introduction to weight enumerators and the
MacWilliams identity

See also
Part II
of my *Notices* article
“Lattices, Linear Codes, and Invariants”
(Part I is in the analogous picture for
lattices in Euclidean space, which is developed to an extent
later in the course).

October 1:
Some uses of the MacWilliams identity; Gleason on the
Hamming weight enumerators of self-dual binary codes

October 3:
Gleason for self-dual codes of Type II, III, and IV

October 8:
Existence and uniqueness of the binary Golay codes

Third problem set:
Synthemes, totals, and the projective plane of order 5

October 10:
The binary Golay codes and related structures, cont’d

October 15:
Extremal enumerators and codes; the Mallows-Odlyzko-Sloane theorem

October 17:
The sphere-packing problem; lattices and their theta series

Table listing, in several code and lattice
contexts, the parameters *q*, *F*, Δ,
*q*_{0}*q*_{0})*m*_{0}*m*_{0}*Handbook of Coding Theory*,
citing a preprint by Zhang Shengyang that meanwhile was published in
*Discrete Applied Math.* **91** (1999), 277–286.)

October 22:
Overview of sphere-packing bounds; theta series of unimodular lattices;
extremal theta functions and lattices

October 24:
Type I and Type II lattices (a.k.a. odd and even unimodular lattices)
and their theta series; Construction A

October 29:
Asymptotics of kissing numbers of extremal codes and lattices
via the stationary-phase method

October 31:
Asymptotic impossibility of (nearly-)extremal codes.
Start on Reed-Muller codes

November 5:
Reed-Muller codes, cont’d

November 7:
a bit more on Reed-Muller codes;
introduction to cyclic codes

November 12:
Cyclic codes cont’d: the BCH bound and
BCH
codes;
QR codes,
and Golay codes as QR codes

November 14:
Krawtchouk polynomials
and Lloyd’s theorem
on perfect codes

November 19: Introduction to the
linear programming (LP) bounds
on error-correcting codes

November 21:
orthogonal polynomial basics

November 26:
LP bounds II: an asymptotic upper bound

**November 28: No Class
(Thanksgiving break)**

December 3:
The ternary Golay codes and related objects

The general motivating setup from information theory for
error-correcting block codes (as opposed to other kinds such as
convolutional, let alone cryptographic: we’re aiming to protect against
error, not eavesdropping).
Natural languages such as English are very suboptimal
error-correcting codes (fingerpuinting?); warning about
real-world™ errors beyond the usual scope of the
mathematical theory (eror-collecting colds).
Coming attractions, drawing on combinatorics,
symmetry and groups, linear algebra, finite geometry,
invariant theory, orthogonal polynomials, etc.
Example: the binary Golay code
_{23}

has point stabilizer the sporadic Mathieu group

[formalities about texts, office hours, grading, etc.; see the initial handout]

General setup for block codes:

Fix a finite set *A* (“alphabet”) of
*q*>1 elements (“letters”).

[*q*=1 is vacuous,
as already observed by Lewis Carroll
— in general, a letter from an alphabet of size *q*
carries _{2}(*q*)

For any integer *n*>0 consider the set *A ^{n}*
of

A *code* is a nonempty subset *C* of Hamming space.
*C* is said to be binary, ternary, quaternary, “etc.”
if the alphabet is of size *n* is the *length* of the code.
The key parameters of *C* are *q*, *n*,
the number of elements (“codewords”) of *C*,
and the *minimum (nonzero) distance* *d*_{min}
between codewords. [If there is only one codeword then it is sometimes
convenient to set *d*_{min} = *n* + 1*d*_{min} = ∞** (**”
for a code of length

A basic question of coding theory is how large *M* can get
given *q*, *n*, and *d*
(or more-or-less equivalently how large *d* can get
given *q*, *n*, and *M*).
As is often the case in this kind of combinatorics,
except in trivial cases it is rare that we can get an exact answer
for a given choice of
*q*, *n*, and *M* or *d*,
and even the asymptotic behavior is not known: we can only give
lower and upper bounds, which hardly ever coincide.
Here one standard asymptotic direction is to fix *q*,
let *n*→∞*transmission rate*
*R* = (log_{q}*M*) / *n**error-detection rate*
*d* / *n*

An elementary upper bound is due to
Singleton (1964):
an *n*, *M*, *d*)*M* ≤ *q*^{n−d+1}*M* = 1*d* = *n* + 1*R* + δ ≤ (*n* + 1) / *n**maximum distance separable*,
or *MDS* for short.
We shall see that *q* is a prime power
such a code exists for all *d* and *n* as long as
*d*−1 ≤ *n* ≤ *q*+1*n* much larger than *q*
is very different. Indeed, it follows from the Singleton bound that
asymptotically *R* + δ ≤ 1*q* and large *n*
this bound cannot be attained except for
*R*,δ)=(1,0)*R* > 0*q*
then 1−δ is bounded away from zero.

Two trivial examples of MDS codes are *A ^{n}* itself
(with

An example of an optimal code that is not MDS is the
Hamming code (1950),
with parameters *q* = 2*n*, *M*, *d*) = (7, 16, 3)*n* and *M* would have had
*d*=4.]
The 7 coordinates are identified with the vertices of the
Fano plane
**P**^{2}(**F**_{2})*A* is **F**_{2} = {0,1}*c* is at distance 3 from seven codewords and
at distance 4 from seven other codewords,
with the remaining codeword other than *c* itself being
the antipodal word, at distance 7. Since no two codewords
are at distance less than 3, the “Hamming spheres”
(actually Hamming-distance balls)
of radius 1 about the codewords are disjoint; but each contains
1+7=8 words, and there are 16 of them, so they tile the
^{7}*A*^{7}*M*=16*q*=2*n*=7*d*=4

In general, the *sphere-packing bound*
(a.k.a. the *Hamming bound*)
is the observation that if *d* > 2*e**M* can be no larger than *q ^{n}*

What does the Hamming bound look like in the asymptotic regime where we
fix *q* and let *n* and *d* grow
while their ratio δ remains roughly constant?
We need the following fundamental computation.
The number of words at distance *exactly* *e* from
a given word is
*q*−1)^{e} Binomial(*n*, *e*)*q* and let *n*, *e* → ∞*e*/*n* → ε*n*, *e*)*n*, *e*))*n**H*(ε)*H* is the *(binary) entropy function*

This gives us the logarithmic asymptotics of the count

For any

It soon follows that the number of words at distance *at most*
*e* from a given word is given by the same asymptotic formula
*nH _{q}*(ε)+

This bound is better (i.e. smaller) than the asymptotic Singleton bound for small δ (because of the vertical tangent at

Replacing *e* by *d*−1 in the Hamming bound yields the
*Gilbert-(Shannon-)Varshamov bound*, which is a *lower* bound:
there exists an
*n*, *M*, ≥*d*)_{q}*q ^{n}*

It is a perennial source of embarrassment that, while the Gilbert-Varshamov
bound is quite weak for small *n*, the asymptotic form is very hard
to beat; the only improvements known use surprisingly sophisticated
techniques from number theory (curves with many points over finite fields),
and for small *q* (all *q* up to about 40)
the Gilbert-Varshamov bound is still the best we have
for all δ.
[There are similar embarrassments elsewhere in combinatorics, as in
Ramsey theory and Euclidean sphere packing in high dimensions,
where the probabilistic method is asymptotically better than
any known explicit construction.]

We usually take for *q* a prime power, and identify *A*
with a *finite field*, which as usual we denote by *F*
[the alternative *k*, for German *Körper*,
is pre-empted as we shall see a couple of paragraphs below].
Hamming space is then the *F*-vector space*F ^{n}*, and the Hamming distance is translation-invariant,
so

where “wt” is the *(Hamming) weight*:
the weight of any word *w* is its number
*i*: *w _{i}* ≠ 0}

A code *C* ⊆ *F ^{n}*
is said to be

Suppose *C* is a linear (*n*, *M*, *d*) code.
Then *M* = *q ^{k}*

The rate
*R* = (log_{q}*M*) / *n**n*, *k*, *d*]*k*/*n**k* + *d* ≤ *n* + 1.
*F*
is not assumed finite, though then our proof
(which used the pigeonhole principle) does not work.
We shall rarely study linear codes over infinite fields,
but can easily prove the Singleton bound for a linear code
over an arbitrary field: choose any *d*−1*C* consisting
of codewords supported on those coordinates must be zero;
but this subspace has codimension at most
*n*−*d*+1*C*,
so *n*−*d*+1*C*).*k*-dimensional*n*−*m**k*−*m*, 0)*F* is infinite,
which is why we rarely do coding theory over infinite fields
(but see “compressive sensing” for a recent nontrivial
analogue of linear error-correcting codes that works in the context of
linear algebra over **R** or **C**).

The sphere-packing bound of course holds for linear codes
as a special case. The Gilbert-Varshamov bound holds for linear codes
as well, though here we must prove it anew. One way is to mimic our
proof for arbitrary codes, adding one basis vector at a time while the
Hamming spheres of radius *d*−1*F ^{n}*,
and using the invariance of the Hamming metric under translation.
We obtain the same bound, possibly improved by a small factor
(no larger than

Often in mathematics when we introduce a new mathematical structure
we follow it up not just with examples but also with operations that
give new examples from old (direct sums and quotients of groups or
vector spaces, field extensions and polynomial rings, etc.).
Such operations exist for codes too, and we’ve seen a few examples
without calling attention to the general constructions
(e.g. a subset of an *n*, *M*, *d*)*n*, *M*’, *d*’)*M*’ ≤ *M**d*’ ≥ *d**n*, *k*, *d*]*n*’ of the coordinates is an
*n*’, *k*’, *d*’]*k*’ ≥
*k* − (*n*−*n*’)*d*’ ≥ *d**dual*, which is a bijection between
linear codes of length *n* and dimension *k*
and linear codes of length *n* and
*n*−*k**F*^{n} × *F*^{n}
→ *F*

[*Warning*:
since we hardly ever use *F*⊆**R**,
there are usually plenty of nonzero *v* with
*v*,*v*⟩ = 0*v*,*v*⟩*C* is a linear code then
the *dual code* of *C* is

As usual *C*^{⊥⊥} = *C**F ^{n}* are each other’s dual,
as are the repetition code and single-checksum code. In general the
minimum distance of

The dual of the Hamming [7, 4, 3] code is the [7, 3, 4] code whose
nonzero codewords are the line complements; this is a
constant-weight code:
all nonzero words have the same weight, here 4.
That *C* ⊆ *C*^{⊥}*self-orthogonal**c*, *c*’⟩ = 0*c*, *c*’
∈ *C**c*=*c*’*k* ≤ *n*−*k**k* ≤ *n*/2*self-dual code*,
which is a linear code satisfying
*C*^{⊥} = *C**n*
and *n*/2*extended Hamming code*,
the *n*, *k*, *d*]*n*+1, *k*, *d*+1]

*Interlude on isometries:*
Hamming space *A ^{n}* has two natural sources of isometries:
we can apply a permutation of

Two codes *C*, *C*’
of the same length over the same alphabet are said to be
*isomorphic* if
*C*’ = *g*(*C*)*g* of Hamming space, and the
*automorphism group* Aut(*C*) of *C*
is the stabilizer of *C* in the isometry group
*G* of Hamming space (or sometimes the image of that group
in the group of permutations of *C*; this is usually
the same but there are codes whose stabilizer does not act faithfully).

If *C* is linear then translation by any codeword is
an automorphism. But we usually exclude nonzero translations
of linear codes, because the choice of **0**
is part of the vector space structure,
and thus should be fixed by any automorphism.
Of the isometries of *F ^{n}* that preserve

Putting the signed permutation matrices together with translations
*F**)^{n}*G*_{lin}*F**-signed*F**)^{n}*S _{n}*

The interlude on Aut(*C*) also serves as a segue to a
dictionary between linear codes and configurations of points
in finite projective spaces. In applications, and in treatises
aimed at applications, an *n*, *k*, *d*]*I* | *C*)*I* is the identity matrix and *C* is regarded
as a matrix of checksums, so that the first *k* letters
are the message (“information bits”, for a binary code)
and the remaining *n*−*k**S _{n}* symmetry on the coordinates;
and of course choosing any generator matrix for

Here’s one way to think about it,
leading to a nice geometric description of linear codes.
Hamming space *F ^{n}* is quite a concrete vector space,
coming to us with a choice of coordinates, ambiguous only up to
permutation and scaling individual coordinates. But

An [This respects the relevant symmetries: two codes are isomorphicn,k, *] code without identically-zero coordinates is tantamount to a spanning (multi)set S_{C}of n points in. P^{k−1}(F)

(*) In general, an *n*, *k*, *d*]*C* with *z* identically-zero coordinates is just an
*n*−*z*, *k*, *d*]*C*_{0}*n* with *z* idle coordinates that contribute
neither information nor error correction; if we can understand
*C*_{0}*C*.

So how to recover the minimum weights *d* and *d**
of *C* and *C*^{⊥} from the
geometry of this configuration *S _{C}*
in the dual projective space? Nonzero codewords

Since any *k*−1*k* of the points in a hyperplane. As for *d**,
a nonzero dual codeword is a nontrivial linear relation on the
coordinates of *C*. We already excluded the most trivial
of relations by requiring that *C* have no nonzero coordinates;
so *d** > 1*d** = 2*S* coincide;
*d** = 3*S* has
distinct points but three of them are collinear; and so forth.
In general, we see that

(In general, δ points in a projective space are said to be “linearly dependent” when they lie on a linear projective subspace of dimension less than δ−1; here there must bed* is the smallest size of a linearly dependent subset ofS.

Note that if *C* has neither an identically zero coordinate
nor a *C*^{⊥}.
This happens *iff* *S* has no subset of
*n*−1*S*, we can reconstruct *C*, then form
the dual code *C*^{⊥}, and find *its*
associated point configuration *S**, which again is *n* points
(permuted in the same way as the points in *S*) with no
*n*−1*n*−*k*−1*k*−1*C*^{⊥⊥} = *C**S** recovers *S*.
So we have a duality between *n*-point**P**^{k−1}**P**^{n−k−1}*n*−1*(Coble-)Gale duality* in
algebraic geometry; see for instance the 1998
article
by Eisenbud and Popescu.

Returning now to our usual setting of a finite field, we can use this
picture to construct and study some basic examples of linear codes.
Suppose for starters that *C** is single-error-correcting, i.e. that
*d* ≥3*S* associated to *C*
are distinct. Thus *n* = #*S***P**^{k−1}(*F*)
= (*q ^{k}*−1) / (

When *k*=2, the Hamming code is MDS, and is the longest
*k**F*.
The same is true trivially for *k*=1*k* ≥ 3*k*=3*n* (distinct) points in the projective
plane **P**^{2}(*F*)*n*-arc”**P**^{2}(*F*)*n*-arcs*n*-arcs

When *n* is small,
it is easy to describe and enumerate *n*-arcs*q* as an incidence relation on
*q*^{2}+*q*+1*q*^{2}+*q*+1*q*+1*n* ≤ 6*n*−1)-arc*n*-arc*A _{n}*
depending only on (

Once *n*>6, the number of extensions of an
*n*−1)-arc*n*-arc*n*-arcs*n*=7*n*-arcs*n*=8*n*=9*J. Combinatorial Theory A* **49** (1988),
26–66, especially Theorems 4.2 and 4.4;
thanks to Nathan Kaplan for this reference.]
When **P**^{2}(**F**_{q})*q*
mod 2 and 3 respectively (e.g. there are no Fano planes except
when *q* is a power of 2, and no affine planes of order 3
if *q* ≡ −1 mod 3*n* grows, in a sense made precise by a theorem
of Mnëv (1988) and memorably described by R. Vakil as
“Murphy’s Law”.

Still we can say something about the largest *n*-arcs,
or equivalently the longest MDS codes of dimension 3
(and dually of dimension *n*−3*q*+1)-arc*n*-arc*n*>*q*+2*q*+1*n*
is either *q*+1*q*+2

• *n* = *q*+2 is possible
*iff* *q* is even;

• *n* = *q*+1 is attained
*only* by conics when *q* is odd.

The latter is a celebrated
theorem of Segre
(*Canad. J. Math.* **7** (1955), 414–416
[NB what Segre calls a “Galois field” γ is our
finite field *F*]);
in our setting, this theorem says that the
*q*+1, 3, *q*−1]*q*+1*q*+2**P**^{2}(*F*)*iff* *q* is even,
while for odd *q* the only ovals are conics.

The upper bound *q*+2 has a purely combinatorial proof, and thus holds for
an arbitrary finite projective plane, not just for algebraic planes;
the same is true for the result that if a plane of order *q*
has a hyperoval then *q* is even. The former result is easy:
given a point *P* of an *n*-arc*q*+1 lines through *P* can go through only one further point
of the arc, for a total of *q*+2. For the latter, observe that since
*P* was an arbitrary point of the arc, *any* line not disjoint from
a hyperoval must meet it in exactly two points; considering all line through a
given point *off* the hyperoval gives a partition of the hyperoval’s
points into pairs, whence *q*+2*q*^{2}+*q*+1 > *q*+2*does* have a hyperoval.
But we won’t worry about geometry over a
“one-element field”, though it can be
**F**_{un} to contemplate such things.]

Still working in the general combinatorial setting, we see that each point *P*
of an oval *O* is on exactly one line *t _{P}*

[Proof of
Segre’s theorem, where the key step is in effect
that every triangle inscribed in an oval (i.e., formed by three of its points)
has a “symmedian point”, or equivalently that
every triangle circumscribed about an oval (i.e., formed by three of its tangents)
has a Gergonne point. (For more on these, see X(6) and X(7) in the
“Encyclopedia of Triangle Centers”,
which starts with X(1)=incenter and X(2)=centroid, and has reached
X(5394) and beyond.)
Along the way we use in effect the classical
theorems of
Menelaus *q* is even, the same argument gives an alternative proof
(but valid only for finite algebraic Π) that any three tangents
to an oval, and thus all its tangents, meet at a point.
Here’s another application of Segre’s
result, showing that quadratic polynomials on a *prime* field
*F*=**Z**/*p***Z***f* : *F*→*F**x* ↦ *f* (*x*+*a*)
− *f* (*x*)*a* in *F*.
(And
here’s how I found out about it.)]

Once we know that every conic with a point can be written as
*xy* + *xz* + *yz* = 0*P*(*x*, *y*, *z*) = 0*P*(·)*B*(·,·)*B*(*v*,*w*) =
*P*(*v*+*w*)
− *P*(*v*) − *P*(*w*)*iff*
*P* is. But in characteristic 2,
*B* is also alternating, so if the number of variables is odd
(as it is for a ternary form) there must be at least a one-dimensional
kernel — and in our setting the kernel can be no larger
(if *B* is identically zero then the conic is a double line).
So there is some nonzero *c*, unique up to scaling, for which
*B*(*c*,*v*) = 0*v*. But then
*P*(*v*+*ac*) =
*P*(*v*) + *a*^{2}*P*(*c*)*a*, so if
*P*(*v*+*ac*) = 0*v* is on the conic) then
the line joining *v* to *c* meets the conic
with multiplicity 2 at *v*, so is tangent to the conic,
as claimed.

Once we know that every conic *C* with a rational point is a
rational normal curve of degree 2,
Bézout’s theorem
becomes elementary for the intersection of *C* with any curve.
Indeed once we identify *C* with
**P**^{1}*C* with a curve of degree *d*
becomes a polynomial of degree 2*d* on that
**P**^{1}*d**C*)
or has exactly 2*d* zeros counted with multiplicity
over an algebraic closure. In particular, taking *d*=2*q* is a power of 2
*larger than 4* there are non-conic ovals obtained by
starting from a conic plus its center and removing one point of the conic.
(And it is known that once *q*>8

The *(Hamming) weight enumerator* of a linear code *C*
of length *n*
is a generating function that encodes the counts of words of
weight *w* for each
*w* = 0, 1, …, *n**W _{C}*(

Before giving and proving MacWilliams’ formula relating
*W*_{C}*W*_{C⊥}

- The simplest example is the singleton code {0},
whose weight enumerator is
*X*.^{n} - The repetition code has one word of weight 0
and the remaining words have weight
*n*, so its weight enumerator is*X*+ (^{n}*q*−1)*Y*^{n}. Every linear code has one word of weight 0, so the weight enumerator always has leading term 1· ; in other words,*X*^{n} .*W*_{C}(1,0)=1- Evaluating
*W*_{C}at counts the summands in*X*=*Y*= 1∑ ; in other words,_{c∈C} , which is*W*_{C}(1,1) = #*C**q*for an^{k}[ code.*n*,*k*,*d*] - The code
*F*has weight enumerator^{n}( . This can be seen from the binomial expansion, but can also be seen as a special case of the following result: let*X*+(*q*−1)*Y*)^{n}*C*_{1}and*C*_{2}be[ and*n*_{1},*k*_{1},*d*_{1}][ codes over the same field, and*n*_{2},*k*_{2},*d*_{2}]*C*the[ code whose words are concatenations of arbitrary words in*n*_{1}+*n*_{2},*k*_{1}+*k*_{2}, min(*k*_{1},*k*_{2})]*C*_{1}and . Then*C*_{2} . The proof is immediate from the distributive law. By induction it follows that concatenating any number of linear codes yields a code whose weight enumerator is the product of the weight enumerators of the component codes. [*W*_{C}=*W*_{C1}·*W*_{C2}*Warning*: this simple-minded construction is*not*what “concatenated code” usually means in the theory of error-correcting codes.] Now*F*can be constructed this way from^{n}*n*components each of which is the[1, 1, 1] code*F*, so , and it is clear that*W*= (_{Fn}*W*)_{F}^{n} , from which*W*(_{F}*X*,*Y*) =*X*+(*q*−1)*Y* follows by the product formula.*W*= (_{Fn}*X*+(*q*−1)*Y*)^{n} -
The weight enumerator of the one-checksum code
*C*is a bit trickier to compute — except for the case*q*=2, where a word is in*C**iff*its weight is even. So, we get*W*from the weight enumerator_{C}( *X*+*Y*)^{n}of by extracting the terms whose exponent of*F*^{n}*Y*is even. This is accomplished by the standard trick of substituting− *Y*for and averaging. Thus the weight enumerator of the parity-check code of length*Y**n*is(( + (*X*+*Y*)^{n}*X*−*Y*)^{n}) / 2 .

**Theorem** (MacWilliams identity for binary codes).
*The weight enumerators of any linear binary code C and its dual code
C*^{⊥} * are related by*

*H* of a finite abelian group *G*,
and any function
*f* :*G*→**C**_{h∈H} *f* (*h*)*f* over the *annihilator* of *H*,
which consists of all characters of *G*
whose restriction to *H* is trivial.
For *G* = *F ^{n}*

**Theorem** (MacWilliams identity for Hamming weight enumerators).
*The weight enumerators of any linear code C over a
q-element field and its dual code C*^{⊥} *
are related by*

So, for instance, our formula for the weight enumerator of a
single-checksum code generalizes to
*X*+(*q*−1)*Y*)^{n}
+ (*q*−1)(*X*−*Y*)^{n}) / *q*.

We next develop Pontrjagin duality and Fourier analysis for finite abelian groups, where all the relevantOncespaces are finite dimensional. See for example paragraphs 2 and 3 of page 5 in this chapter of my notes on analytic number theory from 2009 (where this theory is used to describe Dirichlet characters); see also the further remarks on page 8, and Exercise 5 on page 10. The Fourier transform on binary Hamming space C-vector( is an important special case also known by other names such as the “Hadamard transform”. As usual with Fourier analysis there are several choices of normalization in the literature; we’ll use the same normalization that I chose here (page 1385), where the Fourier transform ofZ/2Z)^{n}is the function taking any character χ to f:G→C∑ , which saddles the formula for the inverse Fourier transform with the factor_{g∈G}χ(g)f(g)| and the complex conjugateG|^{−1}χ( . [Forg)we need not worry about the complex conjugate because G= (Z/2Z)^{n}χ( is alwaysg)±1 .]Poisson summation figures in analytic number theory too (see this chapter of the 2009 notes), but again we need only the finite case, which is easier than Poisson summation on

and entirely elementary. (We may cover Poisson summation on Z⊂R, or more generally on lattices Z⊂Rin , when/if we get to the connection between linear codes and Euclidean lattices.)R^{n}

Some applications of the MacWilliams identity:

- Compute
*W*when_{C}*W*_{C⊥}is easier to get at directly. Example: if*C*is a one-error-correcting Hamming code of length , then*n*= (*q*−1) / (^{k}*q*−1)*C*^{⊥}is a constant-weight[ code, so*n*,*k*,*q*^{k−1}] is*W*_{C⊥}(*X*,*Y*)*X*+ (^{n}*q*−1)^{k}*X*^{n−qk}*Y*^{ qk}. MacWilliams then gives us a formula for . Expanding*W*_{C}(*X*,*Y*)*W*in powers of_{C}*Y*then gives where*X*+^{n}*N*_{3}*X*^{n−3}*Y*^{ 3}+*N*_{4}*X*^{n−4}*Y*^{ 4}+*O*(*Y*^{ 5}),*N*_{3}is times the number of collinear triples of points in*q*−1 (check these claims!). Can you compute and account for**P**^{k−1}(*F*)*N*_{4}? This is the start of a neat story at the interface of coding theory and algebraic geometry, about which we alas won’t be able to say much more this term.

More generally, we can compute the weight enumerator of any linear code whose dual is small enough to list one vector at a time. It is still a computationally intractable problem to compute the weight enumerator of a code of large length*n*whose dimension is near*n*/2 (or more generally whose dimension and codimension aren’t very small compared with its length) — all known algorithms are exponential-time — though the MacWilliams identity can help reduce the base of the exponent. - Determine the weight enumerator of MDS codes.
The Hamming weight code of an MDS code depends only on its
parameters
*q*,*n*, and*k*: there’s one word of weight zero, then nothing until weight where each set of*w*=*n*−*k*+1*w*coordinates supports codewords, and then for*q*−1 each set of*w*=*n*−*k*+2*w*coordinates supports( codewords, “etc.” — but the combinatorics can get somewhat intricate, and after our experience*q*−1) (*q*+1−*w*)*counting*MDS codes of dimension 3 and length at least 7 you might be worried that the weight enumerator might not even be the same for all MDS codes of the same alphabet size, length, and dimension. However, the MacWilliams identity makes this clear. If*C*is MDS, then so is*C*^{⊥}; so we know*W*up to multiples of_{C}of ,*Y*^{n−k+1}__and__(by MacWilliams) up to multiplesof ( . These two polynomials are relatively prime, and the sum of their degrees is*X*−*Y*)^{k+1} ; so*n*+2 >*n**W*is determined uniquely, and even with a few dimensions to spare for a ’sanity check” on our computations: the (inhomogeneous) linear system for the coefficients_{C}of must be consistent, and must predict correctly the number of minimum-weight words of both*W*_{C}*C*and .*C*^{⊥} - Weight enumerators and other properties of self-dual (and some nearly self-dual) codes. This will occupy us for the rest of this lecture and some time beyond.

Now consider what this means for the weight enumerator
*W _{C}*(

- All weights are even implies
*W*is invariant under_{C} . Hence*Y*↔ −*Y* is a polynomial in*W*(_{C}*X*,*Y*)*X*and .*Y*^{2} - But the degree
*n*of*W*is even: we’ve already noted that a self-dual code over any field must have_{C}2 | (because*n**C*must have dimension*n*/2). Thus*W*is invariant also under_{C}( ), and is thus a polynomial in*X*,*Y*) ↔ (−*X*,−*Y**X*^{2}and .*Y*^{2} - The ones’-complement involution shows that
*W*is invariant also under the involution_{C}( ). Therefore it is a polynomial in*X*,*Y*) ↔ (*Y*,*X* and*X*^{2}+*Y*^{2} (elementary symmetric functions in*X*^{2}*Y*^{2}*X*^{2}and ; alternatively, write*Y*^{2}*W*as a polynomial in_{C} and*X*^{2}+*Y*^{2} ).*X*^{2}−*Y*^{2} - Finally, MacWilliams gives invariance under the involution
( . This involution fixes*X*,*Y*) ↔ (2^{−½}(*X*+*Y*), 2^{−½}(*X*−*Y*)) , and takes*X*^{2}+*Y*^{2} to*X*^{2}*Y*^{2}( . [The fact that*X*^{2}−*Y*^{2})^{2}/4 is fixed is clear, because that’s the weight enumerator of the*X*^{2}+*Y*^{2}[2,1,2] repetition code{(0,0), (1,1)} which is self-dual.] Now the sum is*X*^{2}*Y*^{2}+ (*X*^{2}−*Y*^{2})^{2}/4( , which gives us nothing new; but the product gives an independent invariant, which we might as well multiply by 4 (weight enumerators must have integer coefficients) to get*X*^{2}+*Y*^{2})^{2}/4δ ._{8}:=*X*^{2}*Y*^{2}(*X*^{2}−*Y*^{2})^{2}

A special property of binary codes is that once a linear code
*C* is self-orthogonal the map taking a codeword *c*
to its weight *modulo 4* is a homomorphism
*C* → 2**Z**/4**Z**.**Z**/2**Z***A*Δ*B*| =
|*A*| + |*B*| − 2|*A*∩*B*|*A*|, |*B*|*A*∩*B*|*A*Δ*B*| ≡
|*A*| + |*B*| mod 4*A*Δ*B*|*C* has
as many words of weight *C* are divisible by 4.
A linear binary code *C* is called
*singly even* in the former case, and
*doubly even* in the latter.
If *C* is self-dual, it is also said to be of
*Type I* if singly even, and of
*Type II* if doubly even.
For example, the

We can detect whether a self-orthogonal binary code *C* is
singly or doubly even from its weight enumerator:
*W _{C}*(1,

The weight enumerator of a Type II code is also invariant under
the substitution of *X*, *iY*)*X*,*Y*)*G*_{I}
generates a larger group *G*_{II} that leaves
invariant any such weight enumerator.
We next describe *G*_{II} and its invariants,
deduce the Gleason theorem for Type II codes,
and obtain some consequences.

[Overview of Gleason I–IV in the context of
complex reflections groups.
[Here’s the paper
“Finite unitary reflection groups” by Shephard and Todd
(*Canad. J. Math.* **6** (1954), 274–304)
that determined all such groups and gave the first proof of the
theorem that these are precisely the finite
subgroups of _{n}(**C**)

[For a picture of the vertices of the regular octahedron permuted by
*G*_{II}/**μ**_{8}_{8}
and its double zeros on the unit disc
*X*^{2}+*Y*^{2}≤1*G*_{I} *G*_{II}

[...]
Thus the weight enumerator of a Type II code of length *n*
has only *n*/24)*n* < 24*W _{C}* = ϕ

It is known that these are the only two Type II codes
of length 16, and there are 9 such codes of length 24
(after which combinatorial explosion soon sets in).
This is the first case where Gleason does not determine
*W _{C}* uniquely, and again (as with Type I)
we can make

Remarkably it is again true that there is a unique such code,
and that removing any coordinate yields a perfect code,
in this case the binary Golay code
_{23}_{24}

A *Type III code* is a self-dual ternary code.
(Recall that “ternary code” means
“code over the *C* is self-orthogonal
*iff*
*c*, *c*⟩ = 0*c*∈*C**iff* every codeword has weight divisible by 3.
This means that *W _{C}*
is invariant under the

We draw the same kind of consequences as before:
it takes only *n*/12)*n*,
and for *n* < 12_{4}^{n/4}*n*/4*n* pairs of words of weight 3,
so some two of them must overlap; but then they
overlap in exactly 2 coordinates, and then they generate
a copy of the tetracode, which must be a direct summand because
the tetracode is self-dual, etc. At *n*=12*W _{C}* that counts words of weight 3
we find that any Type III

Yet again it turns out (and we may show) that there is a unique such code, and that removing any coordinate yields a perfect code, this time the

A *Type IV code* is a quaternary linear code that is its own
*Hermitian* dual, i.e. dual under the sesquilinear pairing

where σ: *a* ↔ *a*^{2}
is the Galois involution of the *C* is the image of
the ordinary linear dual under componentwise application of σ.
A quaternary linear code *C* is contained in its
Hermitian dual *iff*
*c*, *c*⟩ = 0*c*∈*C**iff* every codeword has even weight.
This makes *W _{C}* invariant under the involution

But we already know what quaternary **P**^{2}(**F**_{4})_{3}(**F**_{4})_{3}(**F**_{4})*C* is unique up to isomorphism,
and is called the “hexacode”. Curiously hyperovals
**P**^{2}(**F**_{4})_{24}

Type IV is the final variation on our theme,
at least for Hamming weight enumerators:
there are no *G*_{V}, *G*_{VI}, etc.,
because (using the classification of finite subgroups of
PGL_{2}(**C**))
there are no further cases where the MacWilliams involution
together with a map
*X*, *Y*) ↦ (*X*, ζ*Y*)*X*^{2}
+ (*q*−1) *Y*^{2}*X*^{2}
+ (*q*−1) *Y*^{2})^{n/2}*iff* −1 is a square).

Beyond Hamming weight enumerators, there are some further examples
(complete or joint weight enumerators, etc.) where elementary observations
plus MacWilliams yield invariance under a complex reflection group,
or a group close enough to being a complex reflection group that one
can still give a satisfactory explanation of its invariant ring.
See for instance Rains and Sloane’s chapter
“Self-Dual Codes” from the *Handbook of Coding Theory*,
especially Section 6
(“Invariant Theory”, starting on p.29)
on general results and techniques,
and Section 7
(“Gleason’s theorem and generalizations”,
starting on p.47) for many further cases. For example (p.59),
a self-dual quinary code
*C* ⊂
(**Z**/5**Z**)^{n}_{C}(*x*, *y*, *z*)_{C}(*x*, *y*, *z*, *z*, *y*)**C** with
the symmetries of an icosahedron, with a polynomial invariant ring
with generator degrees *z* = *y**W _{C}*.

There are (at least) two natural directions to go with the
Gleason theorems: the extended Golay codes
_{24}_{12}*n*,
which lead to a different flavor of mathematics and some long-open
problems (e.g. it is still unknown whether there exists
a Type II

The Golay codes have symmetry groups that are large
(e.g. large enough to be multiply transitive on the coordinates)
and sporadic. The size indicates that there are various ways to
prove uniqueness: in each case there are various natural objects
on which the group acts uniquely (small subsets of the coordinates,
codewords of given weight, etc.), and we can fix one of them,
try to show there’s still a unique way to fit a code of the
desired properties around it, and then get as a bonus the transitivity
on objects of that type. The fact that the groups are sporadic
suggests that no proof of uniqueness can tell us everything of interest
about the Golay codes: different choices will reveal only different parts
of the structure of the code and its automorphism group, and suggest
generalizations in a different direction. One could give an entire
graduate course on the Golay codes and Mathieu groups (even if
*I* might not be “one” who
could give such a course), but since that’s not an option
I must choose one approach and more-or-less stick with it.
Given what we’ve seen so far, I’ll take the route via
the subgroup
*M*_{21} = PSL_{3}(**F**_{4})*M*_{24} = Aut(G_{24})

Suppose, then, that *C* is a Type II *w* of weight 5 supported on the
remaining 23 coordinates then it is at distance at most 3 from
one of the codewords, and thus at most 4 from one of the words
*c* of *C*;
but *C* is even with minimum distance 8,
so *c* has weight 8 and contains the support
of *w*, and is determined uniquely by that property
(this can be seen directly from the triangle inequality together with
*d*_{min}(*C*)=8*the supports of the 759 minimal words
constitute a (5, 8, 24)
*

If we fix one, two, or three of the 24 coordinates, and consider
only those octads (**P**^{2}(**F**_{4})*A*_{6} and *S*_{6},
namely the triple cover *A*_{6}*S*_{6}.

We already know Π has hyperovals; choose one, and call it *O*.
Every point outside *O* is on three lines meeting *O* in
two points each, and thus gives a “syntheme”,
which in this context is the (somewhat quaint 19th-century) terminology for
a partition of the six points of *O* into three pairs.
But there are ^{3}3!) = 15*O* in two points (here 15 arises as
*O*-points*O**
in the dual project plane Π*.
Indeed we noted already that every point outside *O*
lies on three lines that meet *O*,
and thus only two lines disjoint from *O*,
i.e. two lines of *O**.
So no three lines of *O** meet at a point,
which makes *O** a hyperoval in Π* because
*O**| = 6*O** is called the *dual hyperoval*
of *O* (and indeed it is clear that
*O*** = *O**tangent to* (not “disjoint from”) the oval,
and the construction works for all odd *q*
(and for any choice of projective plane if there’s more than one
plane that admits an oval).

Each of the *O** lines, say *l*, lies on five syntheme points.
This gives *l* at a unique point
and thus appears in exactly one of the five synthemes in *l*.
So *l* determines a partition of the 15 pairs into five synthemes.
But *there are exactly six such partitions*, so *O**
must contain them all! They’re called the
“synthematic totals” or simply “totals”
of the *O*.
We have thus accounted for all the points and lines of Π
(points are 6 oval points and 15 syntheme points, and lines are
15 pairs and 6 totals), and shown in effect that
**P**^{2}(**F**_{4})**P**^{2}(**F**_{4}))
= PΓL_{3}(**F**_{4})**F**_{4})_{n}(*F*)_{n}(*F*)_{n}(*F*)_{n}(*F*)*F*)

Before resuming the construction of
_{24}*O*
*ordered* hyperovals, the stabilizer of an *unordered*
hyperoval *O* is isomorphic with the group
*S*_{6} of permutations of the points of *O*.
This group is generated by simple transpositions, which are not
_{3}(**F**_{4})*simply* transitively on ordered
_{3}(**F**_{4})_{3}(**F**_{4})*O* are at
^{2})^{2}, ρ)*O* lifts to a
_{3}(**F**_{4})*iff* it is an even permutation.
I claim that indeed all the even permutations are
_{3}(**F**_{4})*S*_{6} is
_{3}(**F**_{4})**F**_{4}_{3}(**F**_{4})_{3}(**F**_{4}) →
(**F**_{4})*_{3}(**F**_{4})*A*_{6} is a simple group, so the restriction
of our map *A*_{6}*A*_{6}_{3}(**F**_{4})*O*:
the group is generated by ^{2})*O*, *O*’*g* ∈ PGL_{3}(**F**_{4})*g*(*O*) = *O*’_{3}(**F**_{4}) orbits

We pause to note some exceptional behavior of the permutation groups
*A*_{6} *S*_{6}*S*_{6}*A*_{6}

Our copy *S*_{6}*O***S*_{6}*S*_{6}, alone among all symmetric groups, has an
outer automorphism, and we can see it in the simultaneous action
of the hyperoval stabilier on *O* *O**^{1}2^{1}3^{1}*S*_{5} maps to a transitive subgroup
(indeed a sharply *S*_{6}_{2}(**Z**/5**Z**)**Z**/5**Z***iff*
they share a *unless* they overlap; thus a total, considered as
a collection of 5 triple transpositions,
is mapped under an outer automorphism to a collection of
5 overlapping simple transpositions, i.e. a clique of size 5 in the
line graph
of the complete graph *K*_{6}.
For each of the six vertices *p*
of this *K*_{6},
the 5 edges through *p* are such a clique,
and it is easy to see that there are no others
(the other maximal cliques are triangles,
which correspond to the one wrong turn that one might make
when constructing a total).

The other exceptional object is the
triple cover
*A*_{6}*A*_{6}.
The simple alternating groups *A _{n}*
all have double covers, which are their preimages in
the universal covers of the orthogonal groups

*Further remarks*: One can likewise use (hyper)ovals to prove the
uniqueness of the projective planes of orders 2, 3, and 5,
and count their automorphisms.
For *q*=2 (respectively *q*=3),
a hyperoval (resp. oval) *O* has four points, six secants, and
three points off *O* where two secants meet
(so here we get not an outer automorphism
*S*_{6} → *S*_{6}*S*_{4} → *S*_{3}*S*_{4}*S*_{4} then arises as the affine linear group
_{2}(**Z**/2**Z**)*q*=2 setting (stabilizer of a line in the projective plane),
and the projective linear group
_{2}(**Z**/3**Z**)*q*=3 (automorphism group of the projective line,
which is isomorphic with *O*).
Once you’ve done this exercise,
try the *q*=5 case,
where the ovals have six points, and synthemes and totals again
come into play but are combined in a different way from what we saw
for *q*=4.

Let *C*_{1} be the code generated by
(characteristic functions) of lines in Π
and *C*_{0} be the even subcode
*C*_{1}*C* is self-dual, and thus doubly even
because the generators have weight 8.
The *C* that we started with
contains *c* | 000)*c* ∈ *C*_{0}*c* | 111)*c* ∈ *C*_{1}*C*_{0}*C*_{0} has dimension 9 (and minimum weight 8),
and thus that *C*_{0})^{⊥}*C*.

We need to study *C*_{0})^{⊥}*C* is self-dual and
contains *c* | 000)*c* ∈ *C*_{0}*c* | ???)*C*
must have its Π part *c*
*C*_{0})^{⊥}*C*_{0})^{⊥}*w* such that
*w*, *l*⟩*l* varies over the 21 lines.
It readily follows that either *w* is 0 or it has weight
at least 5, with equality *iff* it is one of the lines.
Now, as an extension of our earlier observations on doubly even codes,
since *C*_{0} is doubly even every coset of
*C*_{0}*C*_{0})^{⊥}*C*_{1}*C*_{0}*C*_{0}
is contained in its dual, which has minimum weight 5,
it follows that *C*_{0} has minimum weight 8,
which is one property we’ll need if *C* is to have
minimum weight 8. Further examples of low-weight
words *C*_{0})^{⊥}_{2} _{4}*C*_{1} contains
the *C*_{1})^{⊥}*C*_{0})^{⊥}*w* such that
*w*, *l*⟩*l*. If such *w* has weight
at least 6 then it has 4 collinear points, and is thus
congruent *C*_{0}*C*_{0})^{⊥}*C*_{0})^{⊥}*C*_{0}*C*_{0}*C*_{0})^{⊥}*C*_{0}*any* three binary words
*w _{i}*

[…]

Here are some more details about the
(re)construction of the

Each of the special codes suggested by Gleason’s Theorem
(extended Hamming,
_{24}_{12}*n* for which Gleason’theorem
does not determine the weight enumerator uniquely and then making
the enumerator unique by incrementing the minimum weight,
doubling it from (say) *e* to 2e
(this *e* is *n* has *m* undetermined coefficients
then we can try incrementing the minimum weight *m* times,
finding that the condition
_{min}(*C*) ≥ (*m*+1)*e**W _{C}* uniquely. We call the resulting
polynomial the

We can describe each of our four cases as follows.
Dehomogenize *W _{C}* by setting

**Proposition**
(Mallows-Odlyzko-Sloane 1975).
*Suppose all the coefficients of the power series for
F*_{0}* are positive,
and the q ^{k} coefficient in the power series expansion of
*Δ

The hypothesis holds for each of our four Types of self-dual codes, so we obtain:

**Corollary.**

*
i) A Type I code of length n has minimum distance at most
**n*/8) + 2*
ii) A Type II code of length n has minimum distance at most
*

iii) A Type III code of length n has minimum distance at most

iv) A Type IV code of length n has minimum distance at most

*Proof* of Proposition, using the invariance of the
formal residue of a power series:
see this TeX page.
[This approach is simpler than the original proof from 1975, though
that proof gives further information that we’ll return to next time.
The approach we use here does let us give formulas for the
*q*^{m+1} coefficient

[General introduction to Euclidean lattices, the
Hermite constant
(best lattice packing of equal spheres), etc.,
with material mostly contained in the first chapter of
“SPLAG” = * Sphere Packings, Latiices,
and Groups* by Conway and Sloane.
For the analogue in the setting of unimodular lattices and their
theta series, see also
Part I of my

The analogue for sphere packings of the Gilbert-Varshamov bound is the
*Minkowski-Hlawka bound*,
which holds for packings not just of spheres but of translates of
an arbitrary centrally-symmetric convex body *B*
**R**^{n}*B* is bounded and has positive volume. It looks simpler
than the Gilbert-Varshamov bound because real vector spaces have
nontrivial homothecies:
while all balls in a given Hamming space “look” different,
*B* = *B*+*B**B*,
and thus has volume ^{n} Vol(*B*)^{−n}*n*^{½}*l*^{p} balls*p* > 2*does* get exponential improvements (but still not by
explicit lattices, except for rather large *p* —
NB *l*^{∞} balls pack with density 1);
but the Poisson summation formula, together with positivity of the
Fourier transforms of Gaussian functions, prevents such improvements
for *p* = *2**x*|^{p})*p* < 2*p* < 2

Elkies, N.D., Odlyzko, A.M., and Rush, J.A.: On the packing densities of superballs and other bodies,ForInvent. Math.105(1991), 613–639.

If *L* is unimodular, then (as for a self-dual binary code)
the map taking a lattice vector *v* to its norm
*v*, *v*⟩ mod 2 *even*
(= “Type II”) when this homomorphism is trivial.
Again this can happen only for *n* divisible by 8,
which we prove using theta functions though there is also an
algebraic proof. (See the first part of Serre’s
*A Course in Arithmetic*, which also treats modular forms
and the theta functions of unimodular lattices in the final chapter.)
Whether or not this homomorphism is trivial, it’s given by
*v* ↦ ⟨*v*, *c*⟩ mod 2 *c*, because *L* is unimodular,
and *c* is determined uniquely mod 2*L*.
Such *c* is said to be a *characteristic vector*
of the lattice; such vectors form a coset of 2*L* in *L*
called the *characteristic coset*.
(The same information is carried by the translate of *L*
formed by all *c*/2 for *c* in this coset;
this translate is known as the “shadow” of *L*.)
The lattice is even *iff* the zero vector is characteristic
*iff* the characteristic coset is trivial.
*iff* *L* is its own shadow.
Now the norm of any coset of 2*L* in *L*
is constant mod 4, but the characteristic coset has constant norm
mod 8. For example, the characteristic vectors of the
**Z**^{n}*n* mod 8*n* mod 8*L*.

Construction A associates to any binary linear code
*C* ⊆ (**Z**/2**Z**)^{n}*L _{C}* ⊂

[*Remarks* on some nonlattice periodic sphere packings:
Construction *L _{C}* makes sense for any binary code

Back to the case of linear codes *C* and lattices *L _{C}*:
the theta series

for *Y*.
[The notation “*L*⟨2⟩” means
the lattice *L* with all inner products multiplied by 2;
for *L*=**Z***A*_{1}_{2}(**Z**)*X*, *Y*)*X*, *iY*)*X*, *Y*)*i*)^{½}(*X*+*Y*,
*X*−*Y*) / 2^{½}_{(Z+½)⟨2⟩}(τ)_{Z⟨2⟩}(τ))*X* and *Y* takes the weight enumerator of the
extended Hamming code _{E8}_{24} =
*X*^{4} *Y*^{4} (*X*^{4}−*Y*^{4})

This story generalizes in various directions (the space of lattices
**R**^{n}*L* is any lattice with rational inner products
then θ_{L} is a modular form of weight
*n*/2_{2}(**R**^{n}*N*)_{2}(**Z**^{n}*N*_{2}(**Z**^{n}*c*/τ_{2}(**Z***L* whose duals are isomorphic with
*L*⟨1/*N*⟩*N*=2 or 3,
such as *D*_{4}*A*_{2}*N*=2, and dimension 12 for *N*=3.)
Here the rings of modular forms behave much as they do for
*N*=2
and *N*=3.
This again gives rise to notions of extremal theta series
and extremal lattices (such as the above records),
with results analogous to what we saw for Type II lattices.

Construction A generalizes in several ways, with
**Z**⟨2⟩**Z**⟨2⟩*L*_{0}*L*_{1}*C* of length *n* with alphabet
*L*_{1}/*L*_{0}*L _{C}* between

[For more on “shadows” and their weight enumerators or
theta series, see also Chapter 5 (starting on page 26)
and also pages 48–49 and 73–75 of
Rains-Sloane,
and also my two papers
“a characterization of the
**Z**^{n} lattice”
and
“Lattices and codes with long shadows”.]

For a statement and proof sketch of the stationary-phase asymptotics
that we use, see this write-up
(and note the two Exercises at the end).
There are naturally plenty of sources for this and related techniques
in general; for instance it is a recurring [no pun intended] theme
in Stanley’s *Enumerative Combinatorics*.

See this write-up outlining a proof of the Mallows-Odlyzko-Sloane theorem.

**CORRECTED** Nov.2 (and replaced *k* by *F*
for the field, because we need *k* for the dimension):

Reed-Muller codes
*r*, *m*)*n* = 2^{m}*F*^{3}*F* = **Z**/2**Z***r*, *m*)*r*
on *k ^{m}* (and thus automatically has automorphisms
at least by the affine linear group

The minimum weight is actually easier: I claim that
*r*, *m*)^{m−r}*r* *F ^{m}*

[The same inductive technique shows that if
*c*∈RM(*r*, *m*)^{m+1−r}^{m+1−r}−wt(*c*)^{m−r}*Information and Control* **30** (1976), 380–395).]

To obtain the dimension of *r*, *m*)*F ^{m}*,
and write any polynomial function

It follows that
*m*−1−*r*, *m*)^{m} − dim(RM(*r*, *m*))*r* *m*−1−*r**F ^{m}* of any monomial of degree <

We saw that *r*, *m*)*r* ≤ *m*−1*r* ≤ *m*−1*m*)^{m−1}*m*)^{m−1}^{m−1}±2^{ρ}*m*−1)/2) ≤ ρ ≤ *m*−1*F*; we already noted that we can show inductively
that the weight is either ^{m−1}^{m−1}±2^{ρ}*r*, *m*)^{v} where
*v* = floor((*m*−1)/*r*)*r*
*F ^{m}*

and each subset of *e* monomials has weight a power of 2
that’s at least ^{m−re}^{|J|−1}^{v}*c*), QED.

The weight enumerator of *r*, *m*)*r* and *m*.
It is trivial for *r*=0, and easy for *r*=1
(where all weights are ^{m−1}*r*=2
the enumerator can be obtained from the theory of quadratic forms.
By MacWilliams we thus know the weight enumerator also for
*r* ≥ *m*−3*r* only a handful of cases have been computed;
for large *m* (and *r* in *m*−4]_{min} for both the code and its dual.

We easily generalize the construction of Reed-Muller codes by
making *F* an arbitrary finite field and regarding the
polynomials of degree *r**F ^{m}*

Once *q*>2 we cannot expect that most of these codes will have
any nontrivial divisibility condition on their Hamming weights;
for instance, the single-checksum code of degree
*q*−1)*m*−2*r*:
for *r*=1 all nonzero weights are
*q ^{m}* (for constant functions) and

Away from characteristic 2 it is simpler to proceed as follows:
define *c*(0)*n*. Then each of the translates
*c*(*a*)*c*(0)^{2}+*n*−1*q*/*n*) = +1*F* so that
^{2} = −*n**c*(*a*), *c*(*b*)) = −1*a*, *b* mod *n**c*(*a*)*n*+1,
while the cyclic QR code of length *n* is generated by
differences
*c*(*a*) − *c*(*b*)

At the end of the Krawtchouk/Lloyd notes we need the fact that
the Krawtchouk polynomial
*K _{e}*(

The Krawtchouk polynomials for given *q* and *n*
are orthogonal.
We shall apply some general results about orthogonal polynomials,
which are classical but not well-known, at least not known as well
as they would have been ome decades ago. So most of this class
will be devoted to developing the results we shall use.
This material is still standard enough that special-purpose lecture notes
should not be necessary; for references, I think the relevant chapters of
Körner’s *Fourier Analysis* contain everything
we shall use, while Szegö’s *Orthogonal Polynomials*
has a more extensive treatment of the topic.

- Definition/construction of orthogonal polynomials
*P*_{i} - Roots of
*P*are real, distinct, and in interior of support interval_{i} - Three-term recurrence and Darboux-Christoffel formula
- Roots are interlaced (also for linear combinations of
*P*and_{i}*P*_{i+1})

We show that for fixed *q* and
δ ∈ [0, (*q*−1)/*q*]
the asymptotic rate *R* = log_{q}(*M*) / *n**d*/*n**R* log *q* ≤ *H _{q}*(ι)

we introduced back in mid-September, and

[...]

When a system {*P _{i}*} of orthogonal polynomials
does allow for a closed form for the triple products

The stationary-phase estimates on *K _{i}*(

[Taking ι=10/150 and 11/150 in the relation between δ and ι at the transition points, and multiplying the resulting δ’s by 150, gives the estimates

Here are extended lecture notes
for existence and uniqueness of the extended ternary Golay code
_{12}*M*_{12},
and the perfect Golay code
_{11}*M*_{11}.
(The lecture notes are “extended” because we won’t
cover the development via Steiner systems in class; see my
Math 155 notes for this approach;
the relation between affine, inversive, and projective planes
is developed in the notes for
17 February ‘09.)

A couple of addenda:

1)
We noted already
that Leech’s construction of his lattice
Λ_{24}
from _{24}_{12}*A*_{2})^{12}**Z**^{24}_{24}*Co*_{0}_{24},
*M*_{24})_{12},
*M*_{12})

2) [...]