% Daniel Allcock
% Orbits in the Leech Lattice

\documentclass[12pt]{amsart}
\usepackage{xspace}
\usepackage{euscript}
\usepackage{multicol}

% theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{sublemma}[theorem]{Sublemma}
\newtheorem{algorithm}[theorem]{Algorithm}
\numberwithin{theorem}{section}
\numberwithin{table}{section}
% remark-like environments
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem{claim}{Claim}

% specific objects
\newcommand{\F}{\mathbb{F}}       % finite field
\newcommand{\R}{\mathbb{R}}       % real numbers
\newcommand{\Z}{\mathbb{Z}}       % integers
\newcommand{\Q}{\mathbb{Q}}       % rationals
\newcommand{\leech}{\Lambda} % leech lattice
\newcommand{\co}[1]{\hbox{\it Co}_{\,#1}} % Conway group
\newcommand{\code}{\mathcal{C}} % binary golay code
\newcommand{\cocode}{\code^*} % binary golay cocode
% variable objects
\newcommand{\calO}{\mathcal{O}} % a octad in the golay code
\newcommand{\calP}{\mathcal{P}} % a partion of the 24-set
\newcommand{\calR}{\mathcal{R}} % refinement of that partition
% various operators and relations
\newcommand{\aut}{\mathop{\rm Aut}}
\newcommand{\isomorphism}{\cong}
\newcommand{\tensor}{\otimes}
\newcommand{\sset}{\subseteq}
\newcommand{\congruent}{\equiv}
\newcommand{\dimension}{\mathop{\rm dim}\nolimits}
% handy abbreviations
\newcommand{\slattice}{$\EuScript{S}$-lattice\xspace} 
\newcommand{\slattices}{$\EuScript{S}$-lattices\xspace}
\newcommand{\cset}{$\code$-set\xspace}
\newcommand{\csets}{$\code$-sets\xspace}

% special underlining for table~\ref{tab-shapes}
% \uline underlines without regard for depth,
% \bline backs up, prints blanks, prints some stuff, and underlines
% both blanks and stuff, a little lower than normal underlineing
\newcommand{\uline}[1]{\underline{\smash[b]{#1}}}
\newcommand{\bline}[2]{\setbox1=\hbox{\uline{#1}}\kern-\wd1
\underline{\phantom{\raise1pt\box1}#2}}

% these are used to refer to the possible outcomes of
% algorithm~\ref{algorithm-children} 
\newcommand{\foundframe}{$(\hbox{\romannumeral1}\,)$\xspace}
\newcommand{\mlattice}{$(\hbox{\romannumeral2}\,)$\xspace}
\newcommand{\mlattices}{$(\hbox{\romannumeral3}\,)$\xspace}
\newcommand{\nothing}{$(\hbox{\romannumeral4}\,)$\xspace}
% these are used to refer to the steps of
% algorithm~\ref{algorithm-children}
\newcommand{\seekframe}{1\xspace}
\newcommand{\reduce}{2\xspace}
\newcommand{\child}{3\xspace}
\newcommand{\children}{4\xspace}
\newcommand{\foundslattice}{5\xspace}

% these are used to refer to parts of
% lemma~\ref{lem-lots-of-properties} 
\newcommand{\framefree}{$(a)$\xspace}
\newcommand{\reduced}{$(b)$\xspace}
\newcommand{\inorperp}{$(c)$\xspace}
\newcommand{\ambiguous}{$(d)$\xspace}
\newcommand{\noisotropic}{$(e)$\xspace}
\newcommand{\kernel}{$(f)$\xspace}
\newcommand{\twoclasses}{$(g)$\xspace}
\newcommand{\notwoclasses}{$(h)$\xspace}

% these are used to refer to the possible cases in
% lemma~\ref{lem-most-of-the-work} 
\newcommand{\dsmall}{$(\hbox{\romannumeral1})$\xspace}
\newcommand{\inSlattice}{$(\hbox{\romannumeral2})$\xspace}
\newcommand{\inK}{$(\hbox{\romannumeral3})$\xspace}
\newcommand{\fewshortvecs}{$(\hbox{\romannumeral4})$\xspace}

% these are used to refer to the steps in algorithm~\ref{alg-refine}
\newcommand{\initialize}{1\xspace}
\newcommand{\reducetosextet}{2\xspace}
\newcommand{\refine}{3\xspace}
\newcommand{\finished}{4\xspace}

% these are used to refer to the steps in
% algorithm~\ref{alg-sextet-search} 
\newcommand{\refinepartition}{1\xspace}
\newcommand{\tetrad}{2\xspace}
\newcommand{\threetriads}{3\xspace}
\newcommand{\twotriads}{4\xspace}
\newcommand{\duadandtriad}{5\xspace}
\newcommand{\triotrick}{6\xspace}
\newcommand{\nosextet}{7\xspace}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\title{Orbits in the Leech Lattice}
%
\author{Daniel Allcock}
\address{Department of Mathematics\\University of Texas at Austin\\Austin, TX 78712}
\email{allcock@math.utexas.edu}
\urladdr{http://www.math.utexas.edu/\textasciitilde allcock}
%
\date{2 December 2004}
\thanks{Author partly supported by NSF grants DMS~0070930 and DMS-0231585.}
%

\begin{abstract}
We provide an algorithm for determining whether two vectors in the
Leech lattice are equivalent under its isometry group, the Conway
group $\co0$ of order $\sim8\times10^{18}$.  Our methods rely on and
develop the work of R.~T.~Curtis, and we describe our intended
applications to the symmetry groups of Lorentzian lattices and the
enumeration of lattices of dimension${}\approx24$ with good properties
such as having small determinant.  Our algorithm reduces the test of
equivalence to${}\leq4$ tests under the subgroup $2^{12}{:}M_{24}$,
and a test under this subgroup to${}\leq12$ tests under $M_{24}$.  We
also give algorithms for testing equivalence under these two
subgroups.  Finally, we analyze the performance of the algorithm.
\end{abstract}

\maketitle

\section{Introduction}
\label{sec-intro}

The Leech lattice $\leech$ is a lattice in 24-dimensional Euclidean
space with many remarkable properties, for us the most important of
which is that its isometry group (modulo $\{\pm I\}$) is one of the
sporadic finite simple groups.  The isometry group is called the
Conway group $\co0$, and our purpose is to present an algorithm
for  a computer to determine whether two given
vectors of $\leech$ are equivalent under $\co0$.  The group is fairly
large, or order${}>8\times10^{18}$, so the obvious try-every-isometry
algorithm is useless.  Instead, we use the geometry of $\leech$ to
build a faster algorithm; along the way we build algorithms for the
problem of equivalence of vectors in $\R^{24}$ under the subgroups
$2^{12}{:}M_{24}$ and $M_{24}$, where $M_{24}$ is the Mathieu group permuting the 24
coordinates.  One may implement and use the algorithm without any deep
familiarity with $\co0$ and $M_{24}$, although more background is needed
for the proofs of correctness and the bounds on performance.

The motivation for the algorithm is the problem of extending results
from  
%the work
%of Vinberg 
\cite{vinberg}, 
%Vinberg and Kaplinskaja 
\cite{vinberg-kaplinskaja} and 
%Borcherds
\cite{reb:lzl} on the isometry groups of the unimodular Lorentzian lattices
$I_{n,1}$ to the case $n=24$.  The idea (following \cite{jhc:vinberg-gps} and
\cite{reb:lzl}) is that $\aut I_{n,1}$ is best understood when embedded in
the isometry group of the even unimodular Lorentzian lattice
$II_{25,1}$.  This larger group has a particularly simple structure,
discovered 
%by Conway 
in \cite{jhc:26dim}: its reflection subgroup has a
fundamental domain $\Delta$ with one facet for each element of $\leech$,
and the group $\co\infty$ of affine isometries is the subgroup of
$\aut II_{25,1}$ preserving $\Delta$.  This means that the equivalence
problem of two points in hyperbolic 25-space can be determined by
applying reflections to bring them into $\Delta$, and then testing their
equivalence under $\co\infty$.  Since $\co\infty=\leech{:}\co0$, this
essentially reduces to equivalence-testing under $\co0$.

%Borcherds 
\cite{reb:24-dimensional-classification} and \cite{reb:thesis}
used these techniques involving $II_{25,1}$ to enumerate the
unimodular lattices in dimensions~24 and~25, and the bimodular
lattices of dimension~25.  Similar calculations with $\co\infty$ were
used by 
%Conway, Parker and Sloane 
\cite{jhc:leech-radius} to enumerate
the deep holes of $\leech$ (see \cite{reb:leech-lattice} for an easier
approach), and by 
%Borcherds, Conway and Queen 
\cite{reb:small-holes}
to enumerate the shallow holes.  All of these enumerations required
extremely lengthy hand computation and detailed familiarity with $\leech$
and $\co0$.  There is no reason to doubt these enumerations, but our
algorithm  could be used to verify them.  Also, it might
be useful for working with the fake monster lie algebra (see
\cite{reb:fake-monster}), whose root lattice is $II_{25,1}$.

The algorithm for $\co0$ appears in section~\ref{sec-Co0} and relies
essentially on a theorem of 
%Curtis 
\cite{rtc:slattices}: every
isometry between certain sublattices of $\leech$, called \slattices,
extends to an isometry of $\leech$.  Background on $\leech$, $M_{24}$
and these \slattices appears in section~\ref{sec-background}.  Our
algorithm proceeds by constructing a tree of data, so the natural
worry is that branching in the tree could require an exponential
amount of computation.  In section~\ref{sec-co0-performance} we prove
that this is not a problem: regardless of the height of the tree its
width is bounded by~16.  
The algorithm reduces a test of equivalence of two
vectors either to an application of Curtis' theorem, or to a few tests
(at most~4) of equivalence under $2^{12}{:}M_{24}$, which is much easier to deal
with because it consists of signed permutations.  In
section~\ref{sec-n24} we show how to reduce a test of equivalence
under $2^{12}{:}M_{24}$ to at most~12 tests under $M_{24}$, and in
section~\ref{sec-m24} we provide an algorithm for testing equivalence
under $M_{24}$.  Any other algorithms for $2^{12}{:}M_{24}$ and $M_{24}$ would work
just as well for testing equivalence under $\co0$.  Section~\ref{sec-remarks} contains a few
remarks.

This paper is a development of part of my dissertation
\cite{dja:thesis}, and I is grateful to my ``unofficial'' thesis
advisor R.~Borcherds for suggesting the problem.  The paper has been
rewritten from scratch, and the results of
section~\ref{sec-co0-performance} are completely new.  The algorithm
for $M_{24}$ is also new; the original one involved fewer special cases
but was much more intricate.  The original preprint received limited
circulation under the title ``Recognizing Equivalence of Vectors in
the Leech Lattice''.

\section{Notation and Background}
\label{sec-background}

We use the ATLAS notation for groups \cite{ATLAS}, so we say that a group
has structure $G.H$ if it has a normal subgroup $G$, the quotient by
which is $H$.  If we write $G{:}H$ then the extension splits, and if
we write $G{\cdot}H$ then it does not.  We write $p^n$ for the direct
product of $n$ copies of the cyclic group of order $p$.

To describe $M_{24}$ we follow \cite{jhc:mog}.  Let $\Omega$ be a fixed set of
size~24, and consider $2^\Omega$ as a vector space over the Galois
field $\F_2$, addition being given by symmetric difference.  We often
refer to a size $n$ set as an $n$-ad, or a monad, duad,
triad, tetrad, etc.  The Golay code $\code$ is a subspace of
$2^\Omega$ of dimension~12 and weight(=set-size) distribution
$0^18^{759}12^{2576}16^{759}24^1$.   Elements of
$\code$ are called codewords or $\code$-sets.  The octads and 16-ads of
$\code$ are called {\it special} and the dodecads are called {\it
umbral}; every octad, dodecad and 16-ad appearing in the paper is
special (resp. umbral) unless otherwise noted, so we will drop this
qualifier except for emphasis.  Every pentad of $\Omega$ lies in a
unique octad.  A partition of $\Omega$ into~3 special octads is called
a trio ({\it three o\/}ctads).  Hand-calculations involving $\code$
are best done using Curtis' Miracle Octad Generator (MOG), which
arranges the~24 points of $\Omega$ into a $4\times6$ array, which
falls into three $4\times2$ bricks.  Each brick is an octad
and the set of all three is called the standard trio.  We refer to the
leftmost MOG column as the standard tetrad.  See \cite{jhc:mog} for a wealth
of information about the MOG array (this MOG differs by a reflection
from Curtis' original array \cite{rtc:mog}).

The Mathieu group $M_{24}$ is the group of permutations of $\Omega$ that
preserve $\code$; it is simple of order $244\,823\,040$ and acts
5-transitively on $\Omega$.  Therefore the stabilizers $M_{23}$, $M_{22}$,
$M_{21}$, $M_{20}$ and $M_{19}$ of a monad, duad, triad, tetrad and pentad
are well-defined up to conjugacy.  $M_{24}$ is also transitive on octads
and dodecads; the stabilizer of a dodecad is $M_{12}$, another
of Mathieu's sporadic simple groups.  $M_{24}$ is also transitive on
trios. 

The Golay cocode $\cocode$ is $2^\Omega/\code$, also of
dimension~12. Any element of $\cocode$ has either a unique smallest
representative in $2^\Omega$ (in which case this subset of $\Omega$
has size${}\leq3$ and is usually identified with the element of
$\cocode$) or else has~6 smallest representatives (in which case they
form a sextet, so named because the {\it six} representatives are mutually
disjoint {\it tet\/}rads).  Every tetrad lies in a unique sextet.  If
the image of a subset $X$ of $\Omega$ in $\cocode$ is a sextet then we
say that $X$ represents that sextet.  We call a subset of $\Omega$
small if it has size${}\leq4$ and large otherwise.  If $X\sset\Omega$
does not represent a sextet then the unique small set to which $X$ is
congruent modulo $\cocode$ is called the small representative of $X$.
By transitivity on tetrads, $M_{24}$ is transitive on sextets.  We
define the standard sextet to be the sextet containing the standard
tetrad; this consists of the~6 MOG columns.  The subgroup of $M_{24}$
preserving the standard sextet is called the sextet group and has
structure $2^6{:}3{\cdot}S_6$ and order $138\,240$.

A basic tool in our algorithm for $M_{24}$ is reducing a set
$X\sset\Omega$ modulo $\code$.  By this we mean finding a small set to
which $X$ is congruent modulo $\code$.  When this has size${}\leq3$
then it is uniquely determined and we denote it by $\bar X$, and when
it has size~4 then $X$ represents a sextet, one of whose tetrads is
the small set.  Computing a small representative is just a rephrasing
of the problem of finding a codeword nearest to $X$, for which there
are several algorithms in the literature, e.g., \cite{jhc:decode} and \cite{be'ery:perfect-golay}.

We equip $\R^{24}=\R^\Omega$ with the inner product $x\cdot
y=\frac{1}{8}\sum_{i\in\Omega}x_iy_i$, and by the norm of $x\in\R^{24}$
we mean $x^2=x\cdot x$.  The Leech lattice $\leech$ is the set of
vectors $x$ with integral coordinates $x_i$ satisfying
\begin{enumerate}
\item[(\romannumeral1)] The coordinates are all congruent modulo $2$; write
$m$ for their common  congruence class.
\item[(\romannumeral2)] The set of $i$ for which $x_i$ takes any given value
  modulo~4 is a \cset.
\item[(\romannumeral3)] The sum of the $x_i$ is congruent to $4m$ modulo~8.
\end{enumerate}
One can check that $\leech$ is an even unimodular lattice that
contains vectors of all even norms except~2.  The type of a lattice
vector is half its norm (this isn't important but it is part of
the vocabulary of $\leech$).  $M_{24}$ acts on $\leech$ by permuting
coordinates, and $\code$ acts by negation of coordinates on \csets.
Together they generate a group $2^{12}{:}M_{24}$.  The full group of isometries of
$\leech$ is called $\co0$ in honor of Conway, who found additional
symmetries (see below); it has order $8\,315\,553\,613\,086\,720\,000$
and modulo its center $\{\pm I\}$ it is a simple group.  It acts
transitively on lattice vectors of each of the types $2$, $3$ and $4$
(and $5$ and $7$ too, though we will not need this).
A sublattice $L$ of $\leech$ is called primitive if
$L=(L\tensor\Q)\cap\leech$. 

A beautiful property of $\leech$ is the
simple structure of its residue classes mod~2.  Each class has a
representative of type~0, 2, 3 or~4; such vectors are called short.
The only congruences among short vectors are that each of type~2 or~3
is congruent to its negative, and that vectors of type~4 fall into
sets of $48$, called frames.  Each frame consists of~24 mutually
orthogonal pairs of antipodal vectors, for example the standard frame
consists of the vectors $(0,\dots,0,\pm8,0\dots,0)$, where the~$\pm8$ may occur
in any position.  $\co0$ acts transitively on frames, and the
stabilizer of the standard frame is the group $2^{12}{:}M_{24}$ discussed above.
We also refer to the element of $\leech/2\leech$ represented by the
members of a frame as a frame.

If $x\in\leech$ then we write $\bar x$ for the image of $x$ in
$\leech/2\leech$, and when $\bar x$ is not a frame we write $\hat x$
for a short representative for $\bar x$, which is well-defined up to
sign.  If $L$ is a sublattice of $\leech$ then we write $\bar L$ for
its image in $\leech/2\leech$.

A basic tool in our $\co0$ algorithm is reducing a vector $x\in\leech$
modulo~2, by which we mean finding a short vector $s$ to which $x$ is
congruent modulo $2\leech$.  This can be accomplished using an
algorithm for decoding $\leech$, which means to find a lattice point
closest to any given element of $\R^{24}$.  Such algorithms appear in
\cite{jhc:decode} and \cite{be'ery:perfect-leech}.  To find $s$, decode $x/2$ to obtain
$\lambda\in\leech$.  By \cite{jhc:leech-radius} (see also \cite{reb:leech-lattice}), every point of
$\R^{24}$ lies within $\sqrt2$ of $\leech$, so $(\lambda-x/2)^2\leq2$
and $s=x-2\lambda$ is short.  If $s^2<8$ then we know that $s$ is
actually well-defined up to sign, and we write $\hat x$ for $s$.  I
would like to know if there is a faster algorithm for reducing an
element of $\leech$ mod~2; the problem seems so much more specialized
than the general decoding problem that perhaps a more specialized
algorithm could be faster.

Curtis introduced the concept of an \slattice in \cite{rtc:slattices};
the idea is to consider sublattices $L$ of $\leech$ none of whose
elements represent frames, and for which there is no obvious
enlargement.  Precisely, $L$ is an \slattice if no element of $L$
represents a frame, and for each $x\in L$, $L$ contains $\hat x$ and
$(x-\hat x)/2$.  The type of an \slattice is the formal symbol
$2^a3^b$ where $a$ (resp. $b$) is the number of antipodal pairs of
type~2 (resp.~3) vectors in $L$.  One has $a+b+1=2^{\dimension L}$,
and Curtis completely classified the \slattices, finding~11 orbits
under $\co0$.  (He used a slightly different definition of \slattice,
but his arguments work just as well for this definition, which is from
\cite{ATLAS}.)  While we do not need the classification, we remark
that the largest of the \slattices, of type $2^{27}3^{36}$, plays a
major role in the performance analysis in section~\ref{sec-co0-performance}.  Also, two
\slattices of the same type are $\co0$-equivalent, so referring to an
\slattice by its type is unambiguous (up to $\co0$).  Finally, the
following theorem is implicit in \cite{rtc:slattices} and stated
explicitly in \cite{ATLAS}.  It is essential for the validity of our
$\co0$ algorithm.

\begin{theorem}
\label{thm-slattice-isometries-extend}
Any isometry between two \slattices extends to an isometry of $\leech$.
\end{theorem}

Our final prerequisite is a small tool used in the $\co0$
algorithm: we will need to be able to find an element of $\co0$
carrying any given frame to the standard one.  
It is enough to carry
any given type~4 vector into the standard frame.  
We need the extra
automorphism $\eta$ of $\leech$ discovered 
%by Conway 
in \cite{jhc:dot0}.  We
write $e_i$ for the vector $(0,\dots,0,1,0,\dots,0)$ with the $1$ in
the $i$th place, for each $i$ we write $T(i)$ for the MOG column
containing $i$, and $e_{T(i)}$ for the vector with coordinates equal
to $1$ on $T(i)$ and 0 elsewhere.  The isometry $\eta$ is defined by
first negating the leftmost MOG column (the standard tetrad) and then
sending each $e_i$ to $e_i-\frac{1}{2}e_{T(i)}$.  

\begin{algorithm}
\label{alg-move-to-frame}
Given $v\in\leech$ of type $4$, this algorithm carries $v$ to a
member of the standard frame. 
\begin{center}
\begin{tabular}{rc}
Step 1.&$2\,2\,2\,2\quad2\,\bar2\,\bar2\,\bar2\quad\bar4\,0\,0\,0$\\
Step 2.&$4\,2\,2\,2\quad4\,\bar2\,\bar2\,\bar2\quad\bar5\,\bar1\,\bar1\,\bar1$\\
Step 3.&$3\,3\,3\,3\quad3\,\bar3\,\bar3\,\bar3\quad\bar6\,0\,0\,0$\\
Step 4.&$5\,3\,3\,1\quad5\,\bar3\,\bar3\,\bar1\quad\bar6\,2\,2\,0$\\
Step 5.&$6\,2\,2\,2\quad6\,2\,\bar2\,\bar2\quad\bar4\,0\,4\,4$\\
Step 6.&$4\,4\,4\,4\quad4\,\bar4\,\bar4\,\bar4\quad\bar8\,0\,0\,0$\\
\end{tabular}
\end{center}
By a step ``$AAAA$ $BBBB$ $CCCC$'' we mean the
following operation. Search for a
tetrad on which the absolute values of the coordinates of $w$
are the numbers $AAAA$; if no such tetrad is found, then proceed
to the next step. If one is found, then find
$\sigma\in2^{12}{:}M_{24}$  such that the coordinates of $\sigma(w)$ on
the standard tetrad are exactly the numbers  $BBBB$,  
replace $w$ by  $\eta\circ\sigma(w)$, whose coordinates 
on the standard tetrad are then the numbers  $CCCC$, and
then proceed to the next step. We have written $\overline m$ for
$-m$.  
\end{algorithm}

The proof is a straightforward examination of the list of type~4
vectors in $\leech$ (e.g. \cite[p.~133]{jhc:splag}).  In order to use
the algorithm one must be able to find an element of $M_{24}$ carrying
any given tetrad to the standard one, and be able to find an element
of $\code$ that changes the signs on the standard tetrad in any
desired way.  Both tasks are accomplished with a few precomputed
elements of $M_{24}$ and $\code$.


\section{Orbits under $\co0$}
\label{sec-Co0}

The idea of our algorithm for detecting equivalence of $v,w\in\leech$
under $\co0$ is simple, and best motivated by considering an example
of how the algorithm might work.  Suppose for simplicity that neither
$v$ nor $w$ lies in $2\leech$.  If one represents a frame and the
other does not then they are clearly inequivalent.  If both represent
frames (say $\phi$, $\psi$) then we find $g,h\in \co0$ carrying $\phi$
and $\psi$ to the standard frame.  It is easy to see that $v$ and $w$
are $\co0$-equivalent if and only if $g(v)$ and $h(w)$ are equivalent
under the stabilizer $2^{12}{:}M_{24}$ of the standard frame.  This is
a reduction to a much smaller problem, since the subgroup acts by
signed permutations.  If neither represents a frame then $\hat v$ and
$\hat w$ are well-defined up to sign; we suppose for this example that
$\hat v\cdot v\neq0$ and $\hat w\cdot w\neq0$, which is usually the
case.  We choose $\hat v$ and $\hat w$ so that $\hat v\cdot v$ and
$\hat w\cdot w$ are positive.  Then $v$ and $w$ are $\co0$-equivalent
if and only if the lattice spanned by $v$ and $\hat v$ is
$\co0$-equivalent to that spanned by $w$ and $\hat w$, by an isometry
carrying $v$ to $w$ and $\hat v$ to $\hat w$.  We can enlarge these
two lattices by adjoining the lattice vectors $(v+\hat v)/2$ and
$(w+\hat w)/2$, and then reducing these new vectors modulo~2.  If we
get frames then we can reduce the problem to $2^{12}{:}M_{24}$ as
before, and otherwise we can enlarge our lattices by adjoining the
short representatives of $(v+\hat v)/2$ and $(w+\hat w)/2$.  We can
repeat the process until either we find frames or the lattices stop
growing.  In the former case we reduce to $2^{12}{:}M_{24}$, and in
the latter case we will use a theorem of Curtis
(theorem~\ref{thm-slattice-isometries-extend}) to determine
equivalence or inequivalence.

The main point of the example is that one should keep track of
sublattices of $\leech$, not just vectors.  It also illustrates
various exceptional cases we must deal with, such as what to do when
reducing a vector mod~2 yields the 0 class, or an orthogonal short
vector.

The basic object in our construction is what we call a marked lattice,
which is a nonempty ordered list of linearly independent elements of
$\leech$.  The language reflects the idea that a marked lattice is a
sublattice of $\leech$ equipped with a distinguished basis.  Our
algorithm determines whether two given marked lattices are equivalent
under $\co0$; this solves the equivalence problem for nonzero
$v,v'\in\leech$ because we can apply the algorithm to the
one-dimensional marked lattices they span.  Given a marked lattice, we
will iteratively construct new marked lattices from it until this
process halts, and then study the last ones constructed in order
to obtain information about $L$.  This information is enough to
determine the $\co0$-equivalence or -inequivalence of marked lattices.

We begin with the iterative step.  Given a marked lattice $L$ with
basis $e_1,\dots,e_n$, we define $\ell_y=\sum y_ie_i$ for all
$y\in\{0,1\}^n$.  These are a set of representatives for $L/2L$, and
we regard them as ordered under the lexicographic order of
$\{0,1\}^n$.  Recall that for $v\in\leech$ we write $\bar v$ for the image of
$v$ in $\leech/2\leech$ and when $\bar v$ is not a frame we write 
$\hat v$ for a short
representative of $v$, which 
is well-defined up to sign.  

\begin{algorithm}
\label{algorithm-children}
Given a marked lattice $L$, this algorithm either
\foundframe produces a frame $\phi$, \mlattice produces a marked lattice $M$,
\mlattices produces a set $\{M_\pm\}$ of two marked lattices, or
\nothing terminates without producing anything.  
\begin{enumerate}
\item[Step \seekframe.]
(Applies if there exists $y$ with $\bar\ell_y$ a frame.)  Write $y$ for
  the first such, set $\phi$ equal to the frame $\bar\ell_y$, and
  quit, yielding case \foundframe.
%
\item[Step \reduce.]
(Applies if there exists $y\neq(0,\dots,0)$ with $\bar\ell_y=0$.)  Write
  $y$ for the first such, define $i$ by the condition that the first
  nonzero entry of $y\in\{0,1\}^n$ is the $i$th, define $M$ as the
  marked lattice with basis
  $e_1,\dots,e_{i-1},\ell_y/2,e_{i+1},\dots,e_n$, and quit, resulting
  in case \mlattice.
%
\item[Step \child.]
(Applies if there exists $y$ with $\hat\ell_y$ in neither $L\tensor\Q$
  nor $L^\perp$.)  Write $y$ for the first such, define $s$ to be
  whichever of $\pm\hat\ell_y$ has positive inner product with the
  first of $e_1,\dots,e_n$ with which it has nonzero inner product,
  define $M$ to be the marked lattice with basis $e_1,\dots,e_n,s$,
  and quit, resulting in case \mlattice.
%
\item[Step \children.]
(Applies if there exists $y\neq(0,\dots,0)$ with $\hat\ell_y\perp L$.)
  Write $y$ for the first such, define $M_\pm$ as the marked lattices
  with bases $e_1,\dots,e_n,\pm\hat\ell_y$, and quit, resulting in
  case \mlattices.
%
\item[Step \foundslattice.]
(Applies in all other cases.)  Quit without producing anything,
  resulting in case \nothing.
%
\end{enumerate}
\end{algorithm}

There is nothing to prove except that our constructions make sense.
In step \reduce, $\ell_y/2$
lies in $\leech$ because of the hypothesis $\bar\ell_y=0$, and that
$e_1,\dots,e_{i-1},\ell_y/2,e_{i+1},\dots,e_n$ are linearly
independent because their integral span contains $e_i$.  In steps
\child and \children, $\hat\ell_y$ is determined up to sign---if
$\bar\ell_y$ were zero or a frame then the algorithm would have
stopped at step~\reduce or~\seekframe.  In step~\child, one of
$\pm\hat\ell_y$ is distinguished, but in step~\children neither
is---the two marked lattices $M_\pm$ must be treated equally and only
the set of both of them together is natural.  (They are two different
markings of the same underlying lattice.)  Finally,
step~\foundslattice does not really quit without producing anything,
because it produces a proof that $(L\tensor\Q)\cap\leech$ is an
\slattice; see lemma~\ref{lem-lies-in-slattice} below.

The output of the algorithm is natural in the sense that if $L$ and
$L'$ are marked lattices and $g\in\co0$ carries $L$ to $L'$, then $L$
produces a frame $\phi$ if and only if $L'$ produces a frame $\phi'$,
in which case $g(\phi)=\phi'$, and similarly for the other cases.  To
see this, observe that every criterion and construction in the
algorithm uses only the geometry of $\leech$ and the given ordering of
the basis $e_1,\dots,e_n$.  

A marked lattice which occurs in the output of the algorithm applied
to $L$ is called a child of $L$.  A descendent of $L$ is defined to be
$L$ itself, or a child of $L$, or a child of a child of $L$, and so
on.  We are abusing the usual meaning of the word by regarding $L$ as
a descendent of itself.  We write $\Omega_L$ for the set of childless
descendents of $L$.  Since the construction of children is natural, we
see by induction that $\Omega_L$ is also natural, in the sense that
any $g\in\co0$ carries $\Omega_L$ to $\Omega_{g(L)}$.  

The following
lemma assures us that $\Omega_L$ is finite and nonempty, and that it
can be computed by repeatedly applying
algorithm~\ref{algorithm-children} to find the `family tree' of $L$.
It may appear that this computation of $\Omega_L$ involves an
exponential explosion, on account of the opportunity for 
step~\children to introduce branching into the  tree.  In fact
this does not happen: in section~\ref{sec-co0-performance} we prove 
that $|\Omega_L|\leq4$ except when $L$ lies in an \slattice, when
$|\Omega_L|$ is still bounded by~16.

\begin{lemma}
A child of a marked lattice $L$ strictly contains $L$.
\end{lemma}

\begin{proof}
A child of $L$ constructed by one of steps~\child or~\children is
obtained by adjoining a new linearly independent vector to the basis
for $L$, so the assertion is obvious.  A child $M$ of $L$ constructed
by step~\reduce is obtained by replacing $e_i$ by $\ell_y/2$ in the
basis $(e_1,\dots,e_n)$ for $L$.  Since $\ell_y=e_i+\sum_{j\neq
  i}y_je_j$, we have $e_i=2\cdot(\ell_y/2)-\sum_{j\neq i}y_je_j$, so
that $M$ contains $L$.  Also, $\ell_y/2$ lies in $M$ but not in $L$: if
it lay in $L$ then $\ell_y$ would represent the zero element of
$L/2L$, contrary to the assumption $y\neq(0,\dots,0)$.
\end{proof}

Next we consider a childless descendent $M$ of $L$.
If algorithm~\ref{algorithm-children} applied to $M$
stops at step~\seekframe, with output the frame $\phi$, then we say
that $M$ yields, or produces, or determines, $\phi$.  
Our next result, lemma~\ref{lem-lies-in-slattice}, asserts that if $M$ determines no frame
then $M$  lies in an \slattice.

\begin{sublemma}
\label{sublem-when-lift-is-primitive-lattice}
If the short representatives of the elements of a $d$-dimensional
frame-free subspace of $\leech/2\leech$ lies in a $d$-dimensional
subspace of $\R^{24}$, then their integral span is an \slattice and is
primitive in $\leech$.
\end{sublemma}

\begin{proof}
Write $M_0$ for the integral span of
the short representatives and note that
$\overline{(M_0\tensor\Q)\cap\leech}=\bar M_0$ since one contains the
other and they have the same cardinality.  Obviously $0\in M_0$. If
$v\in(M_0\tensor\Q)\cap\leech$ is nonzero then $\hat v$ lies in
$M_0$. Also,
$(v-\hat v)/2\in(M_0\tensor\Q)\cap\leech$ has smaller norm than
$v$ if we choose $\hat v$ such that $v\cdot\hat v\geq0$.  
By induction on norm, $(v-\hat v)/2$ lies in $M_0$, hence $v=\hat
v+2\cdot(v-\hat v)/2$ does too.  This proves that $M_0$
is primitive, and it follows that it is an \slattice.
\end{proof}

\begin{lemma}
\label{lem-lies-in-slattice}
Suppose $M$ is a childless marked lattice.  If it determines a frame
then $M$ does not lie in an \slattice.  Otherwise, the short
representatives for $\bar M\sset\leech/2\leech$ span an \slattice
which contains $M$, has the same rational span as $M$, and is the
smallest \slattice containing $M$.
\end{lemma}

\begin{proof}
We write $m_y$ for the standard representatives of $M/2M$, just as we
wrote $\ell_y$ for those of $L/2L$.  If the algorithm applied to $M$
yields a frame then some $m_y$ represents a frame.  No member of any
\slattice can do this, so $M$ cannot lie in an \slattice.

Now suppose $M$ is a childless marked lattice with no output from the
algorithm.  Since the algorithm did not halt at step~\seekframe, the
$\hat m_y$ are well-defined up to sign.  Since it did not halt at
step~\reduce, the map $M/2M\to\leech/2\leech$ is injective, so that
$M$ and $\bar M$ have the same dimension.  Since it did not
halt at step~\child or~\children, all the $\hat m_y$ lie in the
rational span of $M$; we write $M_0$ for the lattice they generate.
By sublemma~\ref{sublem-when-lift-is-primitive-lattice}, $M_0$ is an \slattice and is primitive, so it
contains $M$.
Finally, any \slattice containing $M$ must contain the short
representatives for all elements of $M$ and therefore must contain $M_0$. 
\end{proof}

Next we claim that either all the marked lattices $M\in\Omega_L$ yield
frames (in which case we say that $L$ ultimately determines frames) or
none of them do.  By considering the vectors adjoined to $L$ to obtain
its children, one sees that any \slattice containing $L$ also contains
the children.  By induction, any \slattice containing $L$ contains
every descendent of $L$.  By the lemma, if any $M\in\Omega_L$ determines a
frame then $M$ does not lie in any \slattice.  Therefore $L$ doesn't
lie in an \slattice, so no member of $\Omega_L$ lies in an \slattice,
so every member of $\Omega_L$ determines a frame.

If one marked lattice ultimately determines frames and another does
not then they are not $\co0$-equivalent.  We next give necessary and
sufficient conditions for the equivalence of two marked lattices that
both ultimately determine frames.  (This is the generic case.)  Then
we will treat the case where neither does.  If $L=(e_1,\dots,e_n)$ is
a marked lattice that ultimately determines frames, let
$\{\phi_1,\dots,\phi_k\}$ be the set of the frames determined by the
childless descendents of $L$.  For each $i=1,\dots,k$, let $g_i$ be an
element of $\co0$ carrying $\phi_i$ to the standard frame; these can
be found with algorithm~\ref{alg-move-to-frame}.  Then let $e_{i,j}=g_i(e_j)$ for
$j=1,\dots,n$.  We use a similar notation for a second marked lattice
$L'$ of the same dimension $n$.

\begin{theorem}
\label{thm-answer-if-both-determine-frames}
With the notation above, $L$ and $L'$ are $\co0$-equivalent if and
only if there exist $g\in2^{12}{:}M_{24}$ and $i\in\{1,\dots,k\}$ such that
$g(e_{1,j}')=e_{i,j}$ for all $j=1,\dots,n$.
\end{theorem}

\begin{proof}
The `if' direction is trivial.  For the other direction, suppose 
$h\in\co0$ carries $L'$ to $L$; then it carries the frames ultimately
determined by $L'$ to those ultimately determined by $L$.  In
particular, $h(\phi_1')=\phi_i$ for some $i=1,\dots,k$.  Then
$g=g_i\circ h\circ(g_1')^{-1}$ carries
$g_1'(L')=(e_{1,1}',\dots,e_{1,n}')$ to
$g_i(L)=(e_{i,1},\dots,e_{i,n})$.  It also carries the standard frame
to itself and therefore lies in $2^{12}{:}M_{24}$.
\end{proof}

This theorem reduces a test of equivalence under $\co0$ to
$k\leq|\Omega_L|$ tests of equivalence under $2^{12}{:}M_{24}$, so the main worry
from a performance perspective is that $\Omega_L$ might be large.
This turns out to not be a problem: in
section~\ref{sec-co0-performance} we show that $|\Omega_L|\leq4$ when
$L$ ultimately determines frames.

Now suppose $L=(e_1,\dots,e_n)$ is a marked lattice that does not
ultimately determine frames; in this case $L$ lies in an \slattice.
Suppose $M=(f_1,\dots,f_d)$ is a childless descendent, with mod 2
classes $\bar m_y$, $y\in\{0,1\}^d$.  For each $y\neq(0,\dots,0)$, let
$\hat m_y$ be the unique short representative of $\bar m_y$ that has
positive inner product with the first $f_i$ with which it has
nonzero inner product.  (Existence of such an $f_i$ follows from the
condition $\hat m_y\in M\tensor\Q$; if this failed then
step~\child or~\children of algorithm~\ref{algorithm-children} would
have produced at least one child of $M$.)  Define
\begin{align*}
A_{M,y,z}&{}=\hat m_y\cdot\hat m_z&\hbox{for all
  $y,z\in\{0,1\}^d$}\phantom{.}\\
B_{M,y,i}&{}=\hat m_y\cdot e_i&\hbox{for all $y\in\{0,1\}^d$ and
  $i\in\{1,\dots,n\}\phantom{^d}$}. 
\end{align*}
As $M$ varies over $\Omega_L$, we obtain a family of arrays of
integers.  

The next theorem shows that a straightforward comparison of these
arrays determines whether $L$ is $\co0$-equivalent to another marked
lattice $L'$ that lies in some \slattice.  From a performance
perspective the main worry is that the list of $A$'s might be
immense.In
fact it can be immodestly large but not huge:  because $M$ is an
\slattice we have $d\leq 6$.

\begin{theorem}
\label{thm-answer-when-neither-determine-frames}
Suppose $L$ and $L'$ are marked lattices of dimension $n$ that lie in
\slattices, $M'$ is a fixed childless descendent of $L'$, of
dimension say $d'$, and that notation is otherwise as above.  Then $L$
and $L'$ are $\co0$-equivalent if and only if there is a childless
descendent $M$ of $L$, of dimension $d=d'$, such that
\begin{align*}
A_{M,y,z}&{}=A'_{M',y,z}\qquad&\hbox{for all $y,z\in\{0,1\}^d$}\phantom{.}\\
\hbox{and}\qquad
B_{M,y,i}&{}=B'_{M',y,i}&\hbox{for all $y\in\{0,1\}^d$ and
  $i\in\{1,\dots,n\}\phantom{^d}$}. 
\end{align*}
(We have written $A'$ and
$B'$ for the above constructions using $L'$ in place of $L$.)  
\end{theorem}


\begin{proof}
If $g\in\co0$ carries $L'$ to $L$ then it carries $M'$ to some
childless descendent $M$ of $L$, and the naturality of our
constructions imply the stated equalities.  On the other hand, suppose
these equalities hold, for some childless descendent $M$ of $L$.  The
first batch of equalities imply that the map $\hat m_y'\to\hat m_y$
defines an isometry from the integer span $M_0'$ of the $\hat m_y'$ to
the integer span $M_0$ of the $\hat m_y$.  Since $M_0'$ and $M_0$ are
\slattices, Curtis's theorem
(theorem~\ref{thm-slattice-isometries-extend}) implies that this
isometry between $M_0'$ and $M_0$ extends to an isometry $T$ of
$\leech$.  The second batch of equalities imply that $T$ carries
$e_1',\dots,e_n'\in M_0'$ to $e_1,\dots,e_n\in M_0$.
\end{proof}

\section{Orbits under $\co0$: performance}
\label{sec-co0-performance}

Most of this section is devoted to proving the following upper bound
on the amount of branching in the family tree of a marked lattice.
This is very important because it rules out an exponential explosion
in the computation.

\begin{theorem}
\label{thm-main-theorem}
A marked lattice that ultimately determines frames has at most~4
childless descendents.  A marked lattice that lies in an \slattice has
at most~16 childless descendents.
\end{theorem}

The fact that we have a stronger bound in the first case is good
because this is the generic case.  More precisely, is it easy to
estimate the number of lattice vectors of norm${}\leq N$ that lie in
\slattices.  The dominant term comes from the \slattices of type
$2^{27}3^{36}$.  Each is a scaled copy of the dual of the $E_6$ root
lattice and has determinant $3^5$.  Therefore it contains $\sim
V(6,\sqrt N)/3^{5/2}$ vectors of norm${}\leq N$, where $V(d,r)$ is the
volume of a radius-$r$ ball in $\R^d$.  Similarly, $\leech$ contains
$\sim V(24,\sqrt N)/1$ vectors of norm${}\leq N$.  The stabilizer $G$
of one of these \slattices is $2.(3^5.2).U_4(2)$ by
\cite[p.~573]{rtc:mog}, and they are $|\co0|/|G|$ in number.  Putting
these data together shows that a random lattice vector of norm${}\leq
N$ lies in an \slattice with probability
\begin{align*}
\sim\left.\frac{|\co0|}{|G|}\cdot\frac{V(6,\sqrt N)}{3^{5/2}}\right/V(24,\sqrt
N)
&{}=
\frac{2^{23}3^25^57^311^213\cdot 23}{\pi^9\,\sqrt3}\,N^{-9}\\
&{}\approx 5.67\times10^{13}\cdot N^{-9}\;.
\end{align*}
For small $N$ this is a poor estimate because of the \slattices'
intersections; indeed it doesn't drop below~1 until $N=34$.  However
it is easy to treat vectors of small norm directly, with the following
results; we denote orbits of type${}\leq11$ (i.e. $N\leq22$) using the
notation of \cite{jhc:dot0}.  A vector of type~2 or~3 spans an
\slattice, and one of type~4, $6_{32}$, $8_{42}$ or $10_{52}$
represents a frame.  One of type $8_{22}$ is twice a type 2 vector.  A
vector of type $5$, $6_{22}$, $7$, $8_{32}$, $9_{32}$ or $10_{33}$ has
one childless descendent, which appears after~2 generations and is an
\slattice of type $2^23^1$, $2^33^0$, $2^13^2$, $2^23^1$, $2^03^3$ or
$2^13^2$ respectively.  A vector of type $9_{42}$, $10_{42}$ or
$11_{43}$ has one childless descendent; it appears after two
generations and determines a frame.  The most complicated case is a
vector of type $11_{52}$, which has two childless descendents, both
\slattices of type $2^53^2$.
%(The vector's stabilizer happens to exchange these descendents.)  
Considering the sizes of all these orbits
shows that a random vector of norm${}\leq22$ lies in an \slattice with
probability${}\approx.092$.

We will also obtain the following bound on the number of generations
in the family tree:

\begin{theorem}
\label{thm-bound-on-generations}
Suppose $v\in\leech-\{0\}$ and $L_0\sset L_1\sset\dots\sset L_n$ are
marked lattices, $L_0$ being the span of $v$ and $L_i$ a child of
$L_{i-1}$ for $i=1,\dots,n$.  Then
$$
n\leq\log_4(6^6v^2)=\log_4v^2+7.75...
$$
\end{theorem}

To prove theorems~\ref{thm-main-theorem} and~\ref{thm-bound-on-generations} we will need the following
definitions and notation.  $\leech/2\leech$ is equipped with the
quadratic form $Q$ obtained by reducing vectors' types modulo~2.  We
will consider the restriction of $Q$ to subspaces of $\leech/2\leech$,
so we need notation for quadratic forms over $\F_2$.  We write $S$
(`split') and $A$ (`anisotropic') for the 2-variable quadratic forms
$xy$ and $x^2+xy+y^2$, and $\Box$ (`square') and $0$ (`zero') for the
1-variable forms $x^2$ and $0$.  Any $\F_2$ quadratic form is a direct
sum of copies of these forms, and there are isomorphisms $S\oplus
S\isomorphism A\oplus A$, $S\oplus\Box\isomorphism A\oplus\Box$ and
$\Box\oplus\Box\isomorphism\Box\oplus0$.  Any $\F_2$ quadratic form
$q$ has associated bilinear form $b(x,y)=q(x+y)-q(x)-q(y)$.  We
write $B$ for the bilinear form on $\leech/2\leech$, which is given by
reducing lattice vectors' inner products modulo~2.  We call a subspace
isotropic if $Q$ vanishes identically on it; note that this is a
stronger condition than the vanishing of $B$.  Vectors of
$\leech$ of types~2 and~3 we call 
2-vectors and 3-vectors, and their
images in $\leech/2\leech$ we call 2-classes and 3-classes.  If $L$ is a
sublattice of $\leech$ then we call it reduced if
$L/2L\to\leech/2\leech$ is injective; its reduction is defined as
$(L\tensor\Z[\frac{1}{2}])\cap\leech$ and is reduced.  Now suppose $L$
is reduced and $\bar L$ frame-free.  We write $L_0$ for the integer span of 
$\{\hat v |\hbox{$\bar v\in\bar L$ and $\hat v\in L\tensor\Q$}\}$.
Almost all of our arguments refer to $L_0$ rather than $L$ itself.
If $\bar v\in\bar L-\{0\}$ has $\hat v\perp L$ then we call $\bar v$
an ambiguous class and $\hat v$ an ambiguous vector.  The point of
these definitions is that algorithm~\ref{algorithm-children} produces a child of $L$ if
some $\bar v\in\bar L$ has no representative in $L_0$, and it produces
two children when every such class is ambiguous.  The ambiguity is
whether to extend $L$ to a larger marked lattice by adjoining $\hat v$
or $-\hat v$.

\begin{lemma}
\label{lem-no-isotropic-3-space}
Every $7$-dimensional subspace of $\leech/2\leech$ contains a frame,
as does every $3$-dimensional isotropic subspace.
\end{lemma}

\begin{proof}
The first claim follows from the second, since any $\F_2$-quadratic
form of dimension${}\geq7$ contains a 3-dimensional isotropic
subspace.  To prove the second claim, choose three linearly
independent short vectors $e_1$, $e_2$ and $e_3$ representing elements
of the subspace and write $L$ for their integral span.  If any $e_i$
has type~4 then we're done.  Otherwise they all have type~2 (norm~4) and their
pairwise inner products are in $\{0,\pm2\}$.  It is well-known that
any family of norm~$2$ vectors having inner products in $\{0,\pm1\}$
spans a direct sum of $A_n$, $D_n$ and $E_n$ root lattices, so $L$ is
a scaled version of $A_1^3$, $A_2\oplus A_1$ or $A_3$.  Each of these
root systems contains a pair of orthogonal roots, so $L$ contains a
norm~8 (type~4) vector and $\bar L$ contains a frame.
\end{proof}

\begin{proof}[Proof of theorem~\ref{thm-bound-on-generations}:]
If a child of a marked lattice has the same dimension, its determinant
is that of its parent, divided by~4.  If it has larger dimension, its
determinant is at most that of its parent, multiplied by~6.  By
lemma~\ref{lem-no-isotropic-3-space} the latter can occur at most~6
times.  The theorem follows because $L_0$ has determinant $v^2$ and
all the determinants are integers.
\end{proof}

The next three lemmas deal with special arrangements of vectors and
are difficult to motivate without first looking at the proof of
lemmas~\ref{lem-most-of-the-work}.  We recommend jumping straight to
lemma~\ref{lem-lots-of-properties}.

\begin{lemma}
\label{lem-orthogonality-of-2-and-3-vectors}
Consider a $2$-dimensional subspace $V$ of $\leech/2\leech$ with one
class $\tau$ of type $2$ and two classes $\theta_1$ and $\theta_2$ 
of type $3$.  Then either every pair among $\hat\tau$, $\hat\theta_1$
and $\hat\theta_2$ is orthogonal or no pair is.
\end{lemma}

\begin{proof}
By computing $B|_V$ from $Q|_V$ we see that all inner products among the
three vectors are even.  If $\hat\tau$ makes nonzero inner product
with one of the $\hat\theta$'s, say $\hat\theta_1$, then without loss of
generality we may take $\hat\tau\cdot\hat\theta_1=2$ and
$\hat\theta_2=\hat\theta_1-\hat\tau$.  Direct computation shows that
no two are orthogonal.  We have
$\hat\theta_1\cdot\hat\theta_2\neq\pm2$ because otherwise
$\tau=\theta_1-\theta_2$ would be a frame, not a 2-class.  If
$\hat\theta_1\cdot\hat\theta_2\neq0$ then without loss of generality
we have $\hat\theta_1\cdot\hat\theta_2=4$ and
$\hat\tau=\hat\theta_1-\hat\theta_2$, and again direct computation
shows that no two are orthogonal.
\end{proof}

\begin{lemma}
\label{lem-all-are-orthogonal-or-just-one-is}
Suppose $W$ is a $3$-dimensional frame-free subspace of
$\leech/2\leech$ with $Q|_W\isomorphism \Box\oplus0\oplus0$.  Then the
$2$-vectors representing the $2$-classes of $W$ span an \slattice $S$
of type $2^33^0$.  Writing $\theta_1,\dots,\theta_4$ for the 3-classes
of $V$, if two of the $\hat\theta_i$'s are orthogonal to $S$ then all
of them are.  In this case, $\hat\theta_i\perp\hat\theta_j$ for all
$i\neq j$, and there is an \slattice of type $2^{27}3^{36}$ containing
$S$ and  all the $\hat\theta_i$.
\end{lemma}

\begin{proof}
The span $S$ of the $2$-vectors is clearly an \slattice of the specified
type, since they have nonzero even inner products with each
other.  It will be convenient to name the $2$-classes $\tau_1$,
$\tau_\omega$ and $\tau_{\bar\omega}$, the subscripts denoting the nonzero
elements of the finite field $\F_4$; we may take
$\hat\tau_1+\hat\tau_\omega+\hat\tau_{\bar\omega}=0$.  By considering $Q|_W$ one
sees that all inner products of representatives for elements of $W$
are even.  If some $\hat\theta_i$, say $\hat\theta_1$, is not
in $S^\perp$ then without loss of generality we may suppose
$\hat\theta_1\cdot\hat\tau_1=0$, $\hat\theta_1\cdot\hat\tau_\omega=2$ and
$\hat\theta_1\cdot\hat\tau_{\bar\omega}=-2$.  Then $\hat\theta_1+\hat\tau_{\bar\omega}$
and $\hat\theta_1-\hat\tau_\omega$ are also $3$-vectors, are also not in
$S^\perp$, and represent two of the remaining 3-classes of $W$.  We have
proven that if any of the $\hat\theta_i$ is
non-orthogonal to $S$ then at least~3 of them are, which is a
restatement of our second claim.

Now suppose all the $\hat\theta_i$ lie in $S^\perp$; we use new
subscripts, writing $\theta_0$, $\theta_1$, $\theta_\omega$ and
$\theta_{\bar\omega}$ for the 3-classes of $W$.  We may so this so that the
addition table for $W$ is $\tau_a+\tau_b=\tau_{a+b}$,
$\tau_a+\theta_b=\theta_{a+b}$ and $\theta_a+\theta_b=\tau_{a+b}$.
(For purposes of this notation we take $\tau_0=0\in W$.)  The claim
$\hat\theta_i\cdot\hat\theta_j=0$ for $i\neq j$ follows from
lemma~\ref{lem-orthogonality-of-2-and-3-vectors} because
$\hat\theta_i$ is orthogonal to
$\widehat{\theta_i+\theta_j}=\hat\tau_{i+j}$.  All that remains is to
construct the desired \slattice.  For this we note that besides the
$\hat\tau_a$ and $\hat\theta_b$, $\leech$ also contains the sixteen
$3$-vectors
$(\pm\hat\theta_0\pm\hat\theta_1\pm\hat\theta_\omega\pm\hat\theta_{\bar\omega})/2$,
since $\theta_0+\theta_1+\theta_\omega+\theta_{\bar\omega}=0\in W$.  Similarly,
it contains the forty-eight $2$-vectors
$(\pm\hat\tau_a\pm\hat\theta_b\pm\hat\theta_{a+b})/2$ with
$a,b\in\F_4$ and $a\neq0$, the twenty-four $3$-vectors
$\left(\pm(\hat\tau_a+\hat\tau_b)\pm\hat\theta_a\pm\hat\theta_b\right)/2$
with $a,b\in\F_4-\{0\}$, and the twenty-four $3$-vectors
$\left(\pm(\hat\tau_a+\hat\tau_b)\pm\hat\theta_0\pm\hat\theta_c\right)/2$
where $a$, $b$ and $c$ are the nonzero elements of $\F_4$ in any
order.  We have exhibited a $6$-dimensional lattice with fifty-four
$2$-vectors and seventy-two $3$-vectors, which is an \slattice by
sublemma~\ref{sublem-when-lift-is-primitive-lattice}.
\end{proof}

\begin{lemma}
\label{lem-the-lattice-K}
$\co0$ acts transitively on ordered triples $(u,v,w)$ of vectors in
$\leech$ satisfying $u^2=v^2=4$, $w^2=6$, $u\cdot v=u\cdot w=v\cdot
w=2$.  The lattice $K$ spanned by three such vectors is primitive in
$\leech$ and has one ambiguous
class $\bar x$. The pointwise stabilizer of $K$ exchanges the two
short representatives $\pm\hat x$, the lattice obtained adjoining them
to $K$ is not reduced, and its reduction represents a frame.
\end{lemma}

\begin{proof}
By 
%Curtis
\cite[p.~562]{rtc:slattices} we may take $u=(4,-4,0^{22})$ and $w=(5,1^{23})$.
The simultaneous stabilizer of these vectors is the Higman-Sims group
$HS$ of order $44\,352\,000$, and one can enumerate the $2$-vectors having inner product~$2$
with each of $u$ and $w$.  There are $1100$ of them, one of which is
$v=(4,0,-4,0^{21})$.  We will prove transitivity on the $1100$ by
showing that the stabilizer $G$ of $v$ in $HS$ has order $|HS|/1100$.
(It obviously has at least this order.)

We write $K$ for the lattice spanned by $u$, $v$ and $w$.  $G$
preserves each of $w=(5,1,1,1^{21})$, $w-u=(1,5,1,1^{21})$ and
$w-v=(1,1,5,1^{21})$, so it preserves their sum, say
$x=(7,7,7,3^{21})=(3,3,3,(-1)^{21})+2(2,2,2,2^{21})$.  The class $\bar
x\in\bar K$ is ambiguous since the $3$-vector $\hat x=(3^3,-1^{21})$ is
orthogonal  to $K$.  No other class of $\bar K$ is ambiguous because
we have seen that $K$ contains $u$, $v$, $u-v$, $w$, $w-u$ and
$w-v$.  

The stabilizer $G_{\hat x}$ of $\hat x$ fixes $(2^{24})$, which
represents the standard frame.  Therefore $G_{\hat x}\sset
2^{12}{:}M_{24}$, and it is easy to see that $G_{\hat x}=M_{21}$, of
order $20\,160$.  Since $|M_{21}|=|HS|/2200$, and every element of $G$
fixes or negates $\hat x$, we have $|G|\leq|HS|/1100$.  This gives
$|G|=|HS|/1100$, proving the claimed transitivity.  We also see
$[G:G_{\hat x}]=2$, so some element of $G$ negates $\hat x$.  
The $4$-dimensional lattice spanned by $K$ and
$\hat x$ is not reduced since we have already seen that its reduction
contains $(2^{24})$, which represents the standard frame.

To prove the primitivity,  compute the determinant of $K$, which
is~56.  Since the only square dividing~56 is~4, any 3-dimensional
enlargement of $K$ in $\leech$ contains $K$ of index~2.  No such
enlargement exists because $K$ is reduced.
\end{proof}

\begin{lemma}
\label{lem-lots-of-properties}
Suppose $L$ is a marked lattice with two children.  Then 
\begin{enumerate}
\item[\framefree]
$\bar L$ is frame-free.
%
\item[\reduced]
$L$ is reduced.
%
\item[\inorperp]
For all $\ell\in L$, $\hat\ell$ either lies in $L_0$ or is
ambiguous.
%
\item[\ambiguous]
$\bar L$ contains an ambiguous class.
%
\item[\noisotropic]
$\bar L$ contains no isotropic $3$-space.
%
\item[\kernel]
The only elements of $\bar L$ that can be ambiguous are those in
$\ker(B|_{\bar L})$.
%
\item[\twoclasses]
If $L_0$ contains a $2$-vector, then it contains the short
representatives of all the $2$-classes of $\bar L$.
%
\item[\notwoclasses]
If $L_0$ contains no $2$-vectors, then any two independent
$3$-vectors in $L_0$ have inner product $0$ or $\pm3$, and $L_0$ is a
scaled copy of a direct sum of $A_n$, $D_n$ and $E_n$ root lattices.
%
\end{enumerate}
\end{lemma}

\begin{proof}
\framefree, \reduced and \inorperp
hold because  algorithm~\ref{algorithm-children} applied to $L$ does not
stop at any of its first three steps.  We have \ambiguous
because step~$4$ of that algorithm does apply to $L$.  Because of
lemma~\ref{lem-no-isotropic-3-space}, \framefree implies \noisotropic.  If $\bar\ell\in\bar L$
does not lie in $\ker(B|_{\bar L})$ then $\hat\ell$ has odd inner
product with some element of $L$, so \inorperp implies $\hat\ell\in
L_0$.  This proves \kernel.  If $\hat v$ is a $2$-vector of $L_0$ and
$\bar w\in\bar L$ is an ambiguous $2$-class, then 
$\hat w\perp \hat v$, so that
$\hat w+\hat v$ has type~$4$ and $\bar L$ contains a frame,
contradicting \framefree.  This proves \twoclasses.

Now we prove the first part of \notwoclasses.  If $v,w\in L_0$ are
independent $3$-vectors then their inner product is $0$, $\pm1$,
$\pm2$, $\pm3$ or $\pm4$, so it suffices to rule out the cases $v\cdot
w=1$, $2$ or~$4$.  In the last case $v-w$ is a $2$-vector of $L_0$,
contrary to hypothesis.  In the case $v\cdot w=2$, $v-w$ has type~$4$,
contrary to \framefree.  Now we show that $v\cdot w=1$ leads to a
contradiction;  since $\co0$ acts transitively on pairs of $3$-vectors
with inner product~$1$ the following claims can be verified by
checking a single example.  The sum $v+w$ has type~$5$, and the two
possibilities for $\widehat{v+w}$ are $\pm u$, where $u$ has type~$3$
and makes inner product~$1$ with each of $v$ and $w$.  Therefore $u\in
L_0$ by \kernel.  Now, $u+v+w\in2\leech$, and we write $x$ for
$(u+v+w)/2$, which  lies in $L_0$ by \reduced.  Then $x-u$,
$x-v$ and $x-w$ are $2$-vectors of $L_0$, contrary to hypothesis.  The
second part of \notwoclasses follows from the first by mimicking the
argument for lemma~\ref{lem-no-isotropic-3-space}.
\end{proof}

\begin{lemma}
\label{lem-most-of-the-work}
Suppose $L$ is a marked lattice of dimension~$d$ that has two
children.  Then one of the following holds:
\begin{enumerate}
\item[\dsmall]
$d\leq2$; or
%
\item[\inSlattice]
$L$ lies in an \slattice; or
%
\item[\inK]
$L_0$ is a copy of the $3$-dimensional 
lattice $K$ of lemma~\ref{lem-the-lattice-K} and contains $L$; or
%
\item[\fewshortvecs]
$d=3$ and $\dimension L_0\leq1$.
%
\end{enumerate}
\end{lemma}

\begin{proof}
It suffices to assume $d\geq3$ and show that one of \inSlattice, \inK
and \fewshortvecs applies.  We will refer to the assertions of
lemma~\ref{lem-lots-of-properties} simply by their letter.  By \reduced, $\dimension \bar
L=d$.  By \noisotropic, $\bar L$ contains no isotropic $3$-space.
By \ambiguous and \kernel, $\ker(B|_{\bar L})\neq0$.  One can
enumerate the $\F_2$ quadratic forms satisfying these conditions, with
the result that one of following holds:

$d=5$ and $Q|_{\bar L}\isomorphism S\oplus A\oplus0$ or
$S\oplus S\oplus\Box$;

$d=4$ and $Q|_{\bar L}\isomorphism S\oplus\Box\oplus0$ or
$A\oplus 0\oplus0$; or

$d=3$ and $Q|_{\bar L}\isomorphism S\oplus\Box$,
$S\oplus0$, $A\oplus0$ or $\Box\oplus0\oplus0$.

In cases $S\oplus A\oplus0$ and $S\oplus0$, $L_0$ contains a
$2$-vector by \kernel; since the nonzero element of $\ker(B|_{\bar
L})$ is a $2$-class, its representative lies in $L_0$ by \twoclasses.
But then there are no ambiguous classes, contrary to \ambiguous.  We
now treat the remaining cases one by one, splitting the last case into
two parts.  To prove that $L$ lies in an \slattice it suffices to
prove that $L_0$ does and that $\dimension L_0=\dimension L$, because
then $L$ lies in the rational span of an \slattice.  Since \slattices
are primitive (their images in $\leech/2\leech$ satisfy the hypotheses
of sublemma~\ref{sublem-when-lift-is-primitive-lattice}), $L$ lies in
the \slattice itself.  In all cases except $\Box\oplus0\oplus0$ the
equality $\dimension L_0=\dimension L$ is automatic because the
elements of $\bar L-\ker(B|_{\bar L})$ span $\bar L$.

Case $S\oplus S\oplus\Box$: We will show that $L_0$ lies in an \slattice
of type $2^{27}3^{36}$.  Only the $3$-class in $\ker(B|_{\bar L})$ is
ambiguous, so $L_0$ contains $2$-vectors representing the fifteen
$2$-classes of $\bar L$.  These classes may be identified with the
$15$ duads from $\{1,\dots,6\}$, in such a way that
classes have even inner product if and only if the corresponding duads
are disjoint.  In this notation, if $i$, $j$, $k$, $l$, $m$ and $n$
are  $1,\dots,6$ in any order, then ${ij}$, ${kl}$ and
${mn}$ lie in a 2-dimensional  isotropic subspace.
The isotropic subspace containing $12$, $34$ and
$56$ lifts to an \slattice of type $2^33^0$; we choose lifts
$\widehat{12}$, $\widehat{34}$ and $\widehat{56}$ summing to $0$.
Every other duad is disjoint from one of these three and meets the
other two, and we choose the short representative $\widehat{ij}$ of
$ij$ which makes inner product~$-2$ with whichever one of
$\widehat{12}$, $\widehat{34}$ and $\widehat{56}$ it has even inner
product with.  We have
now chosen representatives for all the $2$-classes of $\bar L$, and we
claim that any two with even inner product have inner product~$-2$.
If $\widehat{13}\cdot\widehat{24}=2$ then $\widehat{13}-\widehat{24}$
and $\widehat{56}$ would be orthogonal $2$-vectors and $\bar L$ would
contain a frame.  If $\widehat{13}\cdot\widehat{45}=2$ then
$\widehat{13}-\widehat{45}$ and $\widehat{56}$ would be orthogonal
$2$-vectors and $\bar L$ would contain a frame.  Up to symmetry of our
notation, these are the only cases to check, so the claim is proven.
Next we claim that any pair of our vectors with odd inner product have
inner product~$1$.  If $i$, $j$, $k$, $\ell$, $m$ and $n$ are
$1,\dots,6$ in any order then
$\widehat{ij}+\widehat{k\ell}+\widehat{mn}=0$,
$\widehat{ik}\cdot\widehat{mn}=-2$ and $\widehat{ik}\cdot\widehat{ij}$
and $\widehat{ik}\cdot\widehat{kl}$ lie in $\{\pm1\}$.  Therefore
$\widehat{ik}\cdot\widehat{ij}=1$ for any distinct $i$, $j$ and $k$,
proving the claim.  We have proven that the configuration of the
$2$-vectors is uniquely determined.  That is, we may choose
coordinates on $L_0\tensor\R$ such that $\widehat{12}$ is the vector
$\frac{1}{\sqrt3}(2,2,-1,-1,-1,-1)$ and similarly for the other
$\widehat{ij}$'s, with the $2$'s appearing in the $i$th and $j$th
positions.  (We refer to the standard metric on $\R^6$ and note that
all our vectors have coordinate sum zero.)  Therefore $L_0$ contains
the vectors $\alpha_i=\frac{1}{\sqrt3}(1,\dots,1,-5,1,\dots,1)$, with the
$-5$ in the $i$th position.  Since these have even inner product with
all the $\widehat{jk}$, all represent the ambiguous class of $\bar L$,
say $\bar v$.  This class has type~$3$ and $\hat v$ is orthogonal to $L_0$, so
we may suppose $\hat v=(1,\dots,1)$ in our coordinates.  Since
$\alpha_i\congruent \hat v$ modulo $2\leech$, $\leech$ contains the six
vectors $a_i=(\alpha_i+\hat v)/2$ and also the six vectors $b_i=(\alpha_i-\hat
v)/2$.  The $a_i$ and $b_i$ have type~2.   Adjoining them to the
$\widehat{ij}$ yields the configuration of twenty-seven $2$-vectors
spanning Curtis's \slattice $2^{27}3^{36}$.  We have proven that $L_0$
lies in this \slattice.

Case $S\oplus\Box\oplus0$: We will show that $L_0$ lies in an
\slattice $2^{27}3^{36}$.  By \kernel, $L_0$ contains contains short
representatives for the classes not in $\ker(B|_{\bar L})$; since one
of these is a $2$-class, \twoclasses implies that $L_0$ also contains
a short representatives $a$ for the unique $2$-class in $\ker(B|_{\bar
L})$.  There are 6 other $2$-classes in $\bar L$, which fall into 3
pairs, each pair summing to $\bar a$.  Since each pairs trivially with
$\bar a$ under $B$, we may choose short representatives having inner
product~2 with $a$.  Consideration of $B|_{\bar L}$ shows that vectors
of different pairs have inner product $\pm1$.  A contradiction arises
if any of these inner products is $-1$, so all are $+1$.
It follows that our seven vectors may be taken to be $a=(2,0,0,0)$ and
$(1,\pm\sqrt3,0,0)$, $(1,0,\pm\sqrt3,0)$ and $(1,0,0,\pm\sqrt3)$.  A
simple argument shows that every point in their real span lies at
distance${}<2$ of their integral span $S$.  (The key is that $S$
contains an $A_3$ lattice orthogonal to $a$, scaled to have minimal
norm~6; this scaled $A_3$ has covering radius $\sqrt3$ by
\cite[p.~112]{jhc:splag}.)  This implies that $S$ is primitive in
$\leech$, since $\leech$ has minimal norm~4.  Therefore $L_0=S$.  No
3-vector in $S$ represents $\theta_1$ or $\theta_2$, so $\hat\theta_1$
and $\hat\theta_2$ lie in $L^\perp$.  Now we can use
lemma~\ref{lem-all-are-orthogonal-or-just-one-is}: consider the
3-dimensional subspace of $\bar L$ containing $a$, $\theta_1$,
$\theta_2$ and any other 2-class.  By
lemma~\ref{lem-all-are-orthogonal-or-just-one-is} the short
representatives for this subspace span a 6-dimensional lattice that
lies in (hence rationally spans) the rational span of $L_0$,
$\hat\theta_1$ and $\hat\theta_2$.  Also, this 6-space meets $\leech$
in an \slattice $2^{27}3^{36}$, so $L_0$ lies in the \slattice.

Case $A\oplus0\oplus0$: We will show that $L_0$ lies in an \slattice
$2^{27}3^{36}$.  By \kernel, $L_0$ contains the short representatives
for the $12$ elements of $\bar L-\ker(B|_{\bar L})$, all of type~$3$.
If $L_0$ contained the short representative for any element of
$\ker(B|_{\bar L})$ then it would contain all of them by \twoclasses,
so no class would be ambiguous, contrary to \ambiguous.  Therefore
$L_0$ contains no $2$-vectors.  By \notwoclasses the $3$-vectors of
$L_0$ form a (scaled) root system of dimension~$\leq4$.  Since there
are~$24$ roots, it can only be of type $D_4$.  This $D_4$ is of course
orthogonal to the the \slattice $2^33^0$ spanned by the short
representatives of $\ker(B|_{\bar L})$, and
lemma~\ref{lem-all-are-orthogonal-or-just-one-is} implies that some
\slattice $2^{27}3^{36}$ contains both this \slattice and the $D_4$.
In particular, it contains $L_0$.

Case $S\oplus\Box$: We will show that $L_0$ lies in an \slattice
$2^93^6$.  There is only one ambiguous class, which has type~$3$.
Considering $Q|_{\bar L}$, we see that $L_0$ contains three linearly
independent $2$-vectors, any two having odd inner product.  After
negating one of them we may suppose that either all their inner
products are~$1$ or that two are~$1$ and the third is~$-1$.  In the
latter case the thee vectors form the configuration of figure I.8 of
\cite{rtc:slattices}, and Curtis shows that the three vectors span an \slattice
$2^33^4$.  This would mean that no class is ambiguous, contrary to
\ambiguous.  Therefore all the inner products are~$1$, and the vectors
form the configuration of Curtis' figure I.7.  In this case Curtis
shows that $L_0$ lies in a $4$-dimensional \slattice  $2^93^6$.

Case $A\oplus0$:  We will show that $L_0$ lies in an \slattice of type
$2^{27}3^{36}$.  By \kernel, only the $2$-class could be ambiguous, so
$L_0$ contains twelve short representatives of the six $3$-classes of
$\bar L$.  Also, $L_0$ does not contain any $2$-vectors, for otherwise
no class of $\bar L$ would be ambiguous.  By \notwoclasses the
$3$-vectors form a (scaled) root system of dimension~$\leq3$; since
there are $12$ roots it must have type $A_3$.  We choose coordinates
using the standard inner product on $\R^4$, with
$a_{12}=(\sqrt3,-\sqrt3,0,0)$ and similarly for $a_{ij}$
($i,j=1,\dots,4$ with $i\neq j$), the $\sqrt3$ appearing in the $i$th
place and the $-\sqrt3$ appearing in the $j$th.  We write $b$ for a
$2$-vector representing the $2$-class of $\bar L$, which is of course
orthogonal to the $3$-vectors.  In our coordinates we may take
$b=(1,1,1,1)$.  if $i$, $j$, $k$ and $\ell$ are $1$, $2$, $3$ and $4$,
in any order, then $a_{ij}+a_{k\ell}$ has even type.  Since it is too
short to lie in $2\leech$, it is congruent modulo $2\leech$ to $b$, so
$\leech$ contains the vectors $(a_{ij}+a_{k\ell}+b)/2$.  Consider the
vectors $a_{13}$, $a_{24}$, $b$ and $b'=(a_{12}+a_{34}+b)/2$.  Since
$a_{13}+a_{24}\congruent b$, their images in $\leech/2\leech$ span a
$3$-dimensional space.  Since $a_{13}$ and $a_{24}$ are orthogonal to
the \slattice $2^33^0$ spanned by $b$ and $b'$, lemma~\ref{lem-all-are-orthogonal-or-just-one-is} implies
that all four vectors lie in an \slattice $2^{27}3^{36}$.  
Therefore $L_0$ lies in this \slattice.

Case $\Box\oplus0\oplus0$, with $L_0$ containing a $2$-vector: we will
show that one of cases \inSlattice and \inK applies.  By \twoclasses,
$L_0$ contains the short representatives for all three $2$-classes of
$\bar L$; together these span an \slattice $2^33^0$, say $S$.  By
lemma~\ref{lem-all-are-orthogonal-or-just-one-is}, either all the
short representatives of the $3$-classes are orthogonal to $S$, or
only one is.  In the second case $L_0$ contains a triple of vectors as
in lemma~\ref{lem-the-lattice-K}, hence contains a copy of the lattice
$K$ treated there.  Since $K$ is primitive it equals $L_0$, and since
$\dimension L_0=\dimension L$, $K$ contains $L$.  We have proven that
\inK applies.  Now we treat the all-orthogonal case.  By
lemma~\ref{lem-all-are-orthogonal-or-just-one-is}, representatives
$\hat a_1,\dots,\hat a_4$ for the four $3$-classes are mutually
orthogonal; we write $V$ for their real span and note that
$V\cap\leech$ also contains the vectors $(\pm\hat a_1\pm\hat
a_2\pm\hat a_3\pm\hat a_4)/2$.  Now, $L$ contains a vector $z$ with
$\bar z=a_1$, and we claim that $z$ has nonzero projection into $V$.
If $z\perp V$ then the vectors $(\hat a_1+\hat a_2+\hat a_3+\hat
a_4)/2$ and $(\hat a_1+z)/2$ of $\leech$ have non-integral inner
product, which is impossible.  Since the projection of $z$ has
nonzero, some $\hat a_i$ is not in $L^\perp$ and therefore lies in
$L_0$.  Then $L_0$ has dimension~$3$ and hence the same rational span
as $L$.  Then the usual argument applies: since $L_0$ lies in an
\slattice, so does $L$.  We note for use in the proof of
theorem~\ref{thm-main-theorem} that $L_0$ is the orthogonal direct sum
of $S$ with the span of
a 3-vector.

Case $\Box\oplus0\oplus0$, with $L_0$ containing no $2$-vectors:
either \fewshortvecs holds, or else $L_0$ contains two linearly
independent short vectors; we will show that under the latter
condition, $L$ lies in an \slattice $2^{27}3^{36}$.  We write $b_0$
and $b_1$ for two $3$-classes with short representatives in $L_0$.  We
write $a_1$, $a_\omega$, $a_{\bar\omega}$, $b_\omega$ and $b_{\bar\omega}$ for the other
elements of $\bar L$, using the notation of the proof of
lemma~\ref{lem-all-are-orthogonal-or-just-one-is}.  We choose short representatives $\hat a_1$, $\hat a_\omega$
and $\hat a_{\bar\omega}$ summing to zero.  Since $\hat b_0$ and $\hat b_1$
are orthogonal to the $\hat a$'s, lemma~\ref{lem-all-are-orthogonal-or-just-one-is} implies that $\hat
b_\omega$ and $\hat b_{\bar\omega}$ are also orthogonal to the $\hat a$'s, 
that the $\hat b$'s are all mutually orthogonal, and that the rational
span of all the $\hat a$'s and $\hat b$'s meets $\leech$ in an
\slattice $2^{27}3^{36}$.  We write $V$ for the
real span of $\hat b_\omega$, $\hat b_{\bar\omega}$ and the $\hat a$'s.  Now, $L$
contains some $z$ with $\bar z=b_\omega$; we claim that $z$ has
nonzero projection to $V$:  otherwise, the vectors $(z+\hat b_\omega)/2$
and $(\hat a_1+\hat b_\omega+\hat b_{\bar\omega})/2$ of $\leech$ would have
non-integral inner product.  Therefore one of $\hat a_1$, $\hat a_\omega$,
$\hat a_{\bar\omega}$, $\hat b_\omega$ and $\hat b_{\bar\omega}$ is not in $L^\perp$,
hence lies in $L_0$.  
Since $L_0$ contains no 2-vectors, either $\hat b_\omega$ or $\hat
b_{\bar\omega}$ lies in $L_0$.
Then $L_0$ has the same dimension as $L$; since
$L_0$ lies in an \slattice, $L$ does too.
For use in the proof of theorem~\ref{thm-main-theorem} we note that $L_0$ is spanned
by three mutually orthogonal 3-vectors, since no other element of
$\bar L_0$ has its short representative in $L_0\tensor\Q$.
\end{proof}

\begin{proof}[Proof of theorem~\ref{thm-main-theorem} (frames case):]
Suppose a marked lattice $T$ does not lie in any \slattice, and has
more than four childless descendents.  Then it has a descendent $U$
with two children, one of which, say $V$, has a descendent $W$ with
two children, one of which, say $X$, has a descendent $Y$ with two
children.  Since $T$ does not lie in any \slattice, neither does any
descendent.  Lemma~\ref{lem-most-of-the-work} implies $\dimension Y\leq 3$, and since we
have
$$
1\leq\dimension T\leq\dimension U<\dimension V\leq\dimension
W<\dimension X\leq\dimension Y\leq3\;,
$$
it follows that
\begin{gather*}
\dimension T=\dimension U=1\cr
\dimension V=\dimension W=2\cr
\dimension X=\dimension Y=3\rlap{\hbox{$\;.$}}\cr
\end{gather*}
Since $V$ is obtained from $U$ (and $X$ from $W$) by adjoining a short
vector, $Y$ contains two linearly independent short vectors.  In
particular, $\dimension Y_0>1$, so by
lemma~\ref{lem-most-of-the-work}, $Y_0$ is a copy of $K$ and contains
$Y$.  Now, $U$ has a single basis vector, say $a$, and $V$ has basis
$(a,b)$ with $a\congruent b$ modulo $2\leech$ and $a\perp b$.  Then
$W$ is the reduction of $V$, and $Y$ is obtained by adjoining a short
vector $c$ which is orthogonal to both $a$ and $b$.  We have deduced
that there is a vector $a\in K$ which is orthogonal to two mutually
orthogonal short vectors of $K$, and congruent to one of them modulo
$2\leech$ (hence modulo $2K$).  Now, such $a$ exists, and is unique up
to isometry of $K$ and multiplication by an odd number.  To see this
one considers the short vectors of $K$, all of which are enumerated in
the proof of lemma~\ref{lem-the-lattice-K}, and finds all orthogonal
pairs of such vectors.  Then one checks that $\aut K$ acts
transitively on such pairs, so without loss of generality we may
suppose our pair is $u-v$ and $w$ in the notation of that lemma.  Then
$a$ must be an odd multiple of the generator of their orthogonal
complement in $K$, which is $(-14,14,14,2^{21})$.  We have shown that if
any element of $\leech$ ultimately determines frames and has more
than~4 childless descendents then this one does.  An explicit
calculation yields only~4.
\end{proof}

\begin{proof}[Proof of theorem~\ref{thm-main-theorem} (\/\slattice case):]
If a marked lattice $L$ lies in an \slattice and has more than~16
childless descendents, then the family tree must branch~5 times.
Since \slattices have dimension at most~6, we deduce the existence
of marked lattices $L_i$ of dimension $i$ for each $i=1,\dots,5$,
each with two children, $L_1$ a descendent of $L$, and each 
other $L_i$ a descendent of $L_{i-1}$.  We consider $L_3$; by the
argument for lemma~\ref{lem-most-of-the-work}, one of the following is true:
\begin{enumerate}
\item[(i)] $Q|_{\bar L}\isomorphism S\oplus\Box$ and $L_3$ lies in a
  4-dimensional \slattice,
%
\item[(ii)] $Q|_{\bar L}\isomorphism A\oplus0$ and $L_{3,0}$ is a copy of
  the $A_3$ lattice, scaled to have minimal norm~6,
%
\item[(iii)] $Q|_{\bar L}\isomorphism \Box\oplus0\oplus0$ and $L_{3,0}$ is
  spanned by an \slattice $M$ of type $2^33^0$ and a 3-vector
  orthogonal to $M$, or
%
\item[(iv)] $Q|_{\bar L}\isomorphism \Box\oplus0\oplus0$ and $L_{3,0}$ is
  spanned by~3 mutually orthogonal 3-vectors.
%
\end{enumerate}
Case (i) clearly cannot arise.  In each case (ii)--(iv), the argument
for the frames case shows that $L_{3,0}$ contains orthogonal short
vectors $b$ and $c$ such that $L_1$ is spanned by a vector $v$ in
$\langle b,c\rangle^\perp\sset L_{3,0}$, with $v\congruent b$ or~$c$ modulo
$2\leech$.  In each case, $\{b,c\}$ is unique up to isometry of
$L_{3,0}$, and $L_1$ is spanned by an odd multiple of the generator $a$ of their
orthogonal complement in $L_{3,0}$, which is
easy to find.  In cases (ii) and (iv), $a$ is congruent to neither $b$
nor $c$.  In case (iii), $a$ is a vector of type $6_{22}$, which has
only one childless descendent.
\end{proof}

Theorem~\ref{thm-main-theorem} is the best possible because
the following considerations construct a marked lattice with~16
childless descendents.  Let $E$ be an \slattice $2^{27}3^{36}$ and
$L_3$ the complement in $E$ of~3 mutually orthogonal 3-vectors $e_1$,
$e_2$ and $e_3$. ($\aut(E)$ acts transitively on ordered 4-tuples of
mutually orthogonal 3-vectors in $E$, so there are no choices to
make.)  Then all but three classes of $\bar L_3$ have short
representatives in $L_3$, and these three classes have representatives
$e_1$, $e_2$ and $e_3$.  Adjoining one of the $e_i$ and reducing
yields a lattice $L_4$, with all but two classes of $\bar L_4$ having
short representatives in $L_4$.  These two classes are represented by
the two remaining $e_i$.  Adjoining and reducing again yields $L_5$,
and every class of $\bar L_5$ has a short representative in $L_5$
except one, represented by the last of the $e_i$.  Adjoining and
reducing one last time yields $E$.  It is easy to find a vector in
$L_3$ with two children and $L_3$ among its descendents.  Such a
vector has~16 childless descendents.

\section{Orbits under $2^{12}{:}M_{24}$}
\label{sec-n24}

To test the equivalence of vectors under $2^{12}{:}M_{24}$ we reduce the problem
to several tests under $M_{24}$.  Recall that the normal subgroup
$2^{12}$ of $2^{12}{:}M_{24}$ is a copy of $\code$, acting by negating signs on
\csets. 

\begin{theorem}
\label{thm-n24-equivalence}
Suppose $v,w\in\R^{24}$, $V$ (resp. $W$) is the set of vectors in
$\code\cdot v$ (resp. $\code\cdot w$) with fewest possible negative
coordinates, and $w'\in W$.  Then $v$ and $w$ are $2^{12}{:}M_{24}$-equivalent if
and only if $w'$ is $M_{24}$-equivalent to some element of $V$.
\end{theorem}

The proof is trivial, and the factor determining performance is
clearly the size of $V$; in fact $|V|\leq12$ in all cases.  To verify
this we used the enumeration \cite[p.~284]{jhc:splag} of $M_{24}$-orbits of
subsets $X$ of $\Omega$: for each $X$ we considered the subgroup of
$\{\pm1\}^X$ obtained by restricting \csets to $X$, and found all
coset representatives with fewest possible $-1$'s.  We also verified
$|V|\leq12$ by using an  implementation of our original $M_{24}$ algorithm
to enumerate $M_{24}$-orbits of vectors having all coordinates in
$\{0,\pm1\}$.  For each such vector we computed $V$ by the method
given below.  The extreme case $|V|=12$ occurs when $V$ has support an
umbral dodecad and an odd number of negative coordinates. 

To use theorem~\ref{thm-n24-equivalence} we need to be able to find $V$ and $W$. We may do this by applying one of the
Golay-decoding algorithms in \cite{jhc:decode} or
\cite{be'ery:perfect-golay}. 
These are ``soft'' decoding
algorithms, which means that they view $\code$ as a subset
of $\R^{24}$, with a \cset $\gamma$ corresponding to the vector
with coordinates $-1$ on $\gamma$ and $+1$ elsewhere. Given a vector of
$\R^{24}$, these algorithms return a \cset with maximal inner
product with that vector.  Given $v$ we define the vector $v_0$
whose $i$th coordinate is the sign ($0$, $+1$, or $-1$) of the $i$th
coordinate of $v$.  After applying the Golay decoder to $v_0$ to
obtain a codeword $\gamma$, set $v'=\gamma\cdot v$.  A little thought
verifies that $v'$ has the fewest negative coordinates of any element of
$\code\cdot v$. The Golay
decoders of \cite{jhc:decode} and \cite{be'ery:perfect-golay} 
proceed by computing the inner products of
codewords with a given vector, and returning a codeword with the
largest inner product. (The cleverness of these algorithms lies
doing this with as few computations  as possible.) 
We may run a modified version of the decoder, which returns
{\it every} codeword with maximal  inner
product. Denoting this set of codewords by $C$, we have
$V=C\cdot v$.

If  the support $S\sset\Omega$ of $v$  is disjoint from some
codewords, then finding $V$ this way is inefficient because $C$
will be larger (possibly much larger) than $V$. 
This is only a problem when $S$ is small,
and such cases may be handled by the following shortcut, which
works when $|S|<12$. Let $\gamma$ be a codeword nearest $S$. 
If $\gamma$ is not an octad or does not lie in $S$, then
$V$ consists of just one vector, with all coordinates
positive. If $\gamma$ is an octad lying in $S$ and $v$ has an
even number of negative coordinates on $\gamma$, then again $V$
contains a single vector, with all coordinates positive.
If $\gamma$ is an octad lying in $S$ and $v$ has an
odd number of negative coordinates on $\gamma$, then
$V$ contains 8 vectors, each with all coordinates
positive except for  one  of the eight
points of $\gamma$, which is negative.

\section{Orbits under $M_{24}$}
\label{sec-m24}

The problem of equivalence of vectors $v,w\in\R^{24}$
under $M_{24}$ is not really a question about vectors in $\R^{24}$.
Namely, we write $C_v=(c_1,\dots,c_k)$ where $c_1<\dots<c_k$ are the
distinct values taken by the coordinates of $v$, $P_i$ for the subset
of $\Omega$ where the coordinates of $v$ equal $c_i$, and $\calP_v$ for
the corresponding (ordered) partition $(P_1,\dots,P_k)$ of $\Omega$.
Then $v$ and $w$ are $M_{24}$-equivalent if and only if $C_v=C_w$ and
$\calP_v$ is $M_{24}$-equivalent to $\calP_w$.  Therefore we restrict
ourselves to the problem of equivalence of ordered partitions $\calP$ and
$\calP'$ of $\Omega$.  All partitions in our analysis are ordered, so we
will suppress the qualifier except for emphasis.  The idea is to search
for sextets by reducing members of $\calP$ and $\calP'$ modulo $\code$, and
by several other means.  Our procedure will almost always find them,
reducing the equivalence problem to the sextet group
$2^6{:}3{\cdot}S_6$ of order only $138\,240$.  Of course we must also
treat the special case where no sextets are found.
We do not provide an algorithm for the sextet group; various
combinations of brute force and cleverness are possible.

Suppose $\calP$ is an ordered partition of $\Omega$.  If some member $P$ of
$\calP$ represents a sextet then testing the $M_{24}$-equivalence of $\calP$
with some other ordered partition $\calP'$ can be reduced to the sextet
group (see theorem~\ref{thm-process-sextet} below).  Otherwise, the
unique small representative $\bar P$ of $P$ modulo $\code$ will
typically cut the members of $\calP$ nontrivially, so that $\calP$
determines a finer partition, whose members may themselves be reduced
modulo $\code$, and so on.  We will try to refine $\calP$ as much as
possible in this manner, interrupting the refinement process if a
sextet appears at any point.  To make this precise, suppose
$\calP=(P_1,\dots,P_n)$ is an ordered partition and $X$ a subset of
$\Omega$.  We say that $X$ refines $\calP$ if $X$ is not a union of
members of $\calP$.  In this case, suppose $P_{i_1},\dots,P_{i_m}$
($i_1<\dots<i_m$) are the member of $\calP$ which meet $X$ but do not lie in it;
we define the refinement of $\calP$ by $X$ to be 
$$
(Q_1,\dots,Q_n,P_{i_1}\cap X,\dots,P_{i_m}\cap X)\;,
$$
where $Q_j=P_j-X$ for $j\in\{i_1,\dots,i_m\}$ and $Q_j=P_j$
otherwise.  We say that $\calP$ is refined if no member of $\calP$
represents a sextet and no member's short representative refines
$\calP$.  

\begin{algorithm}[Refinement]
\label{alg-refine}
This algorithm accepts an ordered partition $\calP$ of $\Omega$ and
returns either a sextet $S$ or a refined partition $\calR$ of $\Omega$;
in the latter case we call $\calR$ the refinement of $\calP$.
\begin{enumerate}
\item[Step \initialize.]
Set $\calR=\calP$.
%
\item[Step \reducetosextet.]
If any member of $\calR$ represents a sextet, set $S$ to be the sextet
represented by the first such member, and quit.
%
\item[Step \refine.]
If any member of $\calR$ of size~$5$ or more has small representative
which refines $\calR$, replace $\calR$ by its refinement by $\bar R$, where
$R$ is the first such member, and go back to step~\reducetosextet.
%
\item[Step \finished.]
Quit, returning $\calR$.
\end{enumerate}
\end{algorithm}

\begin{proof}
The algorithm terminates because each refinement increases the number
of members of $\calR$, of which there may be at most~24.  All we have to
show is that $\calR$ is refined when defined.  If $\calR$ is defined, the
algorithm reached step~\finished, so neither step~\reducetosextet
nor~\refine applies to $\calR$.  Since step~\reducetosextet doesn't
apply, no member of $\calR$ represents a sextet, so in particular no
member of $\calR$ has size~4.  Since step~\refine
doesn't apply, no member of $\calR$ of size${}>4$ has small representative
that refines $\calR$.  Since any member of $\calR$ of size${}< 4$ 
is its own short representative, $\calR$ is refined.
\end{proof}

Because our criteria and constructions refer only to $\code$ and the
ordering of $\calP$, the sextet is natural when defined, in the sense
that if the algorithm applied to $\calP$ produces a sextet $S$ and
$g\in M_{24}$, then the algorithm applied to $g(\calP)$ produces the sextet
$g(S)$. Similarly, if $\calP$ has refinement $\calR$ and $g\in M_{24}$ then
$g(\calP)$ has refinement $g(\calR)$.  Refined partitions are rather
special:

\begin{lemma}
\label{thm-refinements}
Suppose $\calR$ is a refined ordered partition of $\Omega$.  Then either
some tetrad is a union of members of $\calR$, or else $\calR$
has one of the~71 shapes listed in table~\ref{tab-shapes}.  (A line beneath some
of the listed sets indicates that their union is a
codeword.) 
\end{lemma}

\begin{table}
\begin{center}
\begin{multicols}{4}
\raggedright
\leavevmode
\llap{$\bullet$\;}3.3.3.3.3.3.3.3\break
\llap{$\bullet$\;}\uline{9.3}.\uline{3.3.3.3}\break
\llap{$\bullet$\;}\uline{10.2}.\uline{3.3.3.3}\break
\llap{$\bullet$\;}\uline{12}.\uline{3.3.3.3}\break
\llap{$\bullet$\;}\uline{13.3}.\uline{3.3.2}\break
\uline{16}.\uline{3.3.2}\break
21.3\break
21.2.1\break
21.1.1.1\break
22.2\break
22.1.1\break
23.1\break
24\break
\llap{$\bullet$\;}\uline{5.3}.\uline{5.3}.\uline{3.3.2}\break
\llap{$\bullet$\;}\uline{5.3}.\uline{5.3}.\uline{5.3}\break
\llap{$\bullet$\;}\uline{5.3}.\uline{5.3}.\uline{6.2}\break
\llap{$\bullet$\;}\uline{5.3}.\uline{5.3}.\uline{8}\break
\llap{$\bullet$\;}\uline{5.3}.\uline{6.2}.\uline{8}\break
\uline{5.1.2}\bline{2}{.6}.10\break
\llap{$\circ$\;}\uline{5.1.1.1}\bline{1.1}{.6}.10\break
\llap{$\bullet$\;}\uline{5.3}.\uline{8}.\uline{3.3.2}\break
\uline{5.3}.\uline{8}.\uline{8}\break
\uline{5.2.1}.\uline{8}.\uline{8}\break
\uline{5.1.1.1}.\uline{8}.\uline{8}\break
\llap{$\bullet$\;}\uline{5.3}.\uline{13.3}\break
\uline{5.3}.\uline{14.2}\break
\uline{5.3}.\uline{16}\break
\uline{5.2.1}.\uline{16}\break
\uline{5.1.1.1}.\uline{16}\break
\uline{6.2}\bline{2}{.6}.10\break
\uline{6.1.1}\bline{1.1}{.6}.10\break
\uline{6.2}\bline{2}{.6}.9.1\break
\llap{$\circ$\;}\uline{6.1.1}\bline{1.1}{.6}.9.1\break
\uline{6.2}.\uline{7.1}.\uline{8}\break
\uline{6.1.1}.\uline{7.1}.\uline{8}\break
\uline{6.2}.\uline{8}.\uline{8}\break
\uline{6.1.1}.\uline{8}.\uline{8}\break
\uline{6.2}\bline{2}{.10}.3.3\break
\llap{$\circ$\;}\uline{6.2}.\uline{13.3}\break
\uline{6.2}.\uline{15.1}\break
\uline{6.1.1}.\uline{15.1}\break
\uline{6.2}.\uline{16}\break
\uline{6.1.1}.\uline{16}\break
\uline{7.1}.\uline{7.1}.\uline{7.1}\break
\uline{7.1}.\uline{7.1}.\uline{8}\break
\uline{7.1}.\uline{8}.\uline{8}\break
\uline{7.1}.\uline{14.2}\break
\uline{7.1}.\uline{14.1.1}\break
\uline{7.1}.\uline{15.1}\break
\uline{7.1}.\uline{16}\break
\uline{8}.\uline{8}.\uline{8}\break
\llap{$\bullet$\;}\uline{8}.\uline{8}.\uline{3.3.2}\break
\uline{8}.\uline{13.3}\break
\uline{8}.\uline{13.2.1}\break
\uline{8}.\uline{13.1.1.1}\break
\uline{8}.\uline{14.2}\break
\uline{8}.\uline{14.1.1}\break
\uline{8}.\uline{15.1}\break
\uline{8}.\uline{16}\break
\llap{$\bullet$\;}\uline{9.3}.\uline{9.3}\break
\llap{$\circ$\;}\uline{9.3}.\uline{10.2}\break
\uline{9.3}.\uline{12}\break
\uline{9.2.1}.\uline{12}\break
\uline{9.1.1.1}.\uline{12}\break
\uline{10.2}.\uline{11.1}\break
\uline{10.1.1}.\uline{11.1}\break
\uline{10.2}.\uline{12}\break
\uline{10.1.1}.\uline{12}\break
\uline{11.1}.\uline{11.1}\break
\uline{11.1}.\uline{12}\break
\uline{12}.\uline{12}\break
\end{multicols}
\end{center}
\caption{Possible shapes of refined partitions; see lemma~\ref{thm-refinements}.
  Each underline means that the union of the underlined sets
  is a codeword. A bullet $\bullet$ indicates that partitions of
  that shape
  determine a sextets in algorithm~\ref{alg-sextet-search}, and a
  circle $\circ$ that partitions of that
  shape are treated by  one of the special cases of
  theorem~\ref{thm-process-refinement}.  Partitions of other listed
  shapes are  treated by the general case of 
  theorem~\ref{thm-process-refinement}.}
\label{tab-shapes}
\end{table}

\begin{proof}
The proof is an uninspiring slog through many cases.  We assume
throughout that no tetrad is a union of members of $\calR$.  What gets
the enumeration off the ground is that a member $R$ of $\calR$ of
size$\geq5$ is disjoint from its small representative---otherwise
$\bar R$ would refine $\calR$.  This means that the only sets that can
appear in $\calR$ are monads, duads, triads and sets of the form
$$
(\hbox{a golay codeword})-(\hbox{$0$, $1$, $2$ or $3$ of its points})\;.
$$
Also, if $R$ is a member of $\calR$ then $\bar R$ refines $\calR$ if and
only if the codeword $R+\bar R$ refines $\calR$.  Table~\ref{tab-shapes} was
obtained by first enumerating those partitions with no large sets,
then those with exactly one large set, then those containing a pentad
and at least one other large set, then those containing a hexad and at
least one other large set, but no pentad, and so on.

As an example of the argument we enumerate the partitions containing
exactly one pentad $p$ and also some other large set.  If there is a
hexad $h$, then the octads $\calO_p$ and $\calO_h$ containing $p$ and $h$
meet in $0$, $2$ or $4$ points because they are \csets.
The last case is impossible because then $\calO_p$ and $\calO_h$ would refine
$\calR$.  If they are disjoint then $\calR$ has shape
$\uline{5.(3)}.\uline{6.(2)}.\uline{(8)}$, where $(n)$
indicates some partition of $n$ points.  
If the $(3)$ is
not a triad or the $(2)$ is not a duad then some tetrad would be a
union of members of $\calR$; therefore $\calR$ has shape
$\uline{5.3}.\uline{6.2}.\uline{(8)}$. 
By hypothesis the $(8)$
contains no pentad, and it cannot contain a monad, duad or tetrad.
Therefore the $(8)$ is a single octad, so $\calR$ has shape
$\uline{5.3}.\uline{6.2}.\uline{8}$, which appears in the table.  

We summarize this argument in a compact notation:

5.6.(13) \& $\calO_p\cap\calO_h=\emptyset$ $\Rightarrow$
         \uline{5.(3)}.\uline{6.(2)}.\uline{(8)} 
	 $\Rightarrow$
         \uline{5.3}.\uline{6.2}.\uline{(8)} 
	 $\Rightarrow$
         \uline{5.3}.\uline{6.2}.\uline{8}.

Continuing with this notation,

5.6.(13) \& $|\calO_p\cap\calO_h|=2$ $\Rightarrow$
\uline{5.1.(2)}\bline{(2)}{.6}.(10)
$\Rightarrow$
\uline{5.1.(2)}\bline{(2)}{.6}.10,
so both 
\uline{5.1.2}\bline{2}{.6}.10
and
\uline{5.1.1.1}\bline{1.1}{.6}.10
appear in the table.

5.7.(12) \& no 6's $\Rightarrow$
\uline{5.(3)}.\uline{7.1}.\uline{(8)}
$\Rightarrow$ tetrad.

5.8.(11) \& no 6's or 7's $\Rightarrow$
\uline{5.(3)}.\uline{8}.\uline{(8)} $\Rightarrow$
\uline{5.(3)}.\uline{8}.\uline{8} or
\uline{5.(3)}.\uline{8}.\uline{3.3.2}; in the latter case we
must have
\uline{5.3}.\uline{8}.\uline{3.3.2}.

5.9.(10) \& no 6's, 7's or 8's $\Rightarrow$
$\calO_p$ meets the 9-ad's dodecad in 2, 4 or 6 points; only the first
case is possible.  Therefore we have
\uline{5.1.(2)}\bline{(2)}{.1.9}.(6) $\Rightarrow$ tetrad.

5.10.(9) \& no 6's through 9's $\Rightarrow$
\uline{5.1.2}\bline{2}{.10}.(6) $\Rightarrow$ tetrad.

5.$N$.($19-N$) for $N=11$ or $12$ $\Rightarrow$ a contradiction since $\calO_p$
  would meet the $N$-ad's dodecad in at least two points, hence refine
  $\calR$. 

5.$N$.($19-N$) for $N=13,\dots,16$ $\Rightarrow$ the $N$-ad's 16-ad meets
  $\calO_p$ in 0, 4, 6 or 8 points; only the first is possible without
  refining $\calR$.  Therefore we have one of
  \uline{5.(3)}.\uline{13.(3)},
  \uline{5.(3)}.\uline{14.(2)},
  \uline{5.(3)}.\uline{15.1} and
  \uline{5.(3)}.\uline{16}.  All cases except those with
   tetrads appear in the table.

Finally, if $\calR$ contains a pentad then it cannot contain a set larger
than a 16-ad, for else $\calO_p$ would meet this set and hence refine $\calR$.
\end{proof}

\begin{algorithm}[Sextet search]
\label{alg-sextet-search}
Suppose $\calP$ is an ordered partition of $\Omega$.  This algorithm
returns either a sextet $S$, or else the refinement $\calR$ of $\calP$
exists and the algorithm returns it.
\begin{enumerate}
\item[Step \refinepartition.]
  Apply algorithm~\ref{alg-refine} (refinement), obtaining either a sextet (in
  which case we set $S$ to be this sextet, and quit), or the
  refinement $\calR$ of $\calP$.
%
\item[Step \tetrad.]
  (Applies if some tetrad is the union of members of $\calR$.)  Set $S$
  to be the sextet containing the first such tetrad, and quit.  (See
  below for the meaning of `first'.)
%
\item[Step \threetriads.]
  (Applies if $\calR$ has 3 triads.) Let $t_1$, $t_2$ and $t_3$ be the
  first three triads, in order.  If $t_1\cup t_2$ represents a sextet
  then set $S$ to be this sextet and quit.  Otherwise, if $t_2\cup
  t_3$ represents a sextet then set $S$ to be this sextet and quit.
  Otherwise, the octads containing $t_1\cup t_2$ and $t_2\cup t_3$
  meet in a tetrad; set $S$ to be the corresponding sextet and quit.
%
\item[Step \twotriads.]  (Applies if $\calR$ has shape $2.3^2.5^2.6$,
  $3^2.5^2.8$, $3^2.5.13$ or $3^2.9^2$.)  Write $t_1$ and $t_2$ for
  the two triads, in order.  If $t_1\cup t_2$ represents a sextet the
  set $S$ to be this sextet and quit.  Otherwise, the octad containing
  $t_1\cup t_2$ meets the first pentad of $\calR$ (or the first nonad in
  case of shape $3^2.9^2$) in one point, which with $t_1$ forms a
  tetrad; set $S$ to be the corresponding sextet and quit.
%
\item[Step \duadandtriad.]
  (Applies if $\calR$ has shape $2.3.5.6.8$.)  The octad containing the
  union of the duad and triad meets the pentad in a single point,
  which with the triad forms a tetrad; set $S$ to be the corresponding
  sextet and quit.
%
\item[Step \triotrick.]
  (Applies if $\calR$ has shape $2.3^2.8^2$.)  Let $t$ be the first
  triad, $\calO$ the union of the small sets, and $T$ the trio consisting
  of $\calO$ and the two octads of $\calR$; set $S$ to be the sextet
  determined by the containments $t\sset\calO\in T$ (see lemma~\ref{thm-trio-lemma}
  below), and quit.
%
\item[Step \nosextet.]
  (Applies in all other cases.) Quit, returning $\calR$.
%
\end{enumerate}
\end{algorithm}

Beyond the fact that the constructions make sense there is nothing to
prove.  For step~\tetrad we need a notion of the first tetrad $T$ which is
a union of members of $\calR$; here is one possibility.  If $\calR$ contains
a tetrad then $T$ is the first such (with respect to the ordering of
$\calR$).  Otherwise, if $\calR$ contains a triad and a monad then $T$ is
the union of the first triad and first monad.  Otherwise, if $\calR$
contains two duads, $T$ is the union of the first two.  Otherwise, if
$\calR$ contains a duad and two monads, $T$ is the union of the duad and
the first two monads.  Otherwise, if $\calR$ contains four monads then
$T$ is the union of the first four.  

For step~\threetriads we must show that the octads containing $t_1\cup
t_2$ and $t_2\cup t_3$ meet in four points (when such octads exist):
this is because they meet in at least 3 (both contain $t_2$) but
cannot coincide (else $t_1\cup t_2\cup t_3$ would like in an octad).
For step~\twotriads, under the condition that $t_1\cup t_2$ does not
represent a sextet, we claim that the octad $\calO$ containing it meets
each pentad (or nonad in the case of shape $3^2.9^2$) once.  In case
$2.3^2.5^2.6$, the sets assemble into $\code$-sets as
$\uline{5.3}.\uline{5.3}.\uline{6.2}$, according to
table~\ref{tab-shapes}.   Then it is clear that $\calO$ meets each octad
$\uline{5.3}$ in at least three points, hence exactly~4, hence
meets each pentad once.    

The same argument applies essentially verbatim in case of shapes 
$3^2.5^2.8$  and $3^2.5.13$.  In case $3^2.9^2$,
$\calR$ has shape $\uline{9.3}.\uline{9.3}$ by table~\ref{tab-shapes}, and
$\calO$ meets each dodecad $\uline{9.3}$ in at least three points,
hence exactly four.  The argument for step~\duadandtriad, with shape
\uline{5.3}.\uline{6.2}.\uline{8}, is the same.  For
step~\triotrick we note that $\calR$ has shape
$\uline{8}.\uline{8}.\uline{3.3.2}$ by table~\ref{tab-shapes}, so
that $\calO$ and the two octads are special, and we apply the following
lemma:

\begin{lemma}
\label{thm-trio-lemma}
If $t$ is a triad, $\calO$ a special octad, and
$T$ a trio, with $t\sset\calO\in T$, then there are octads
$\calO'\in\code$  meeting $\calO$ in exactly $4$ points, including those of
$t$, and disjoint from one of the other 
octads of $T$. All such octads $\calO'$ meet $\calO$ in the same
tetrad.
\end{lemma}

\begin{proof}
$M_{24}$ acts transitively on trios, the stabilizer of a trio
acts transitively on its octads, and the stabilizer of a trio and one
of its octads acts $3$-transitively on the
octad. Therefore it suffices to verify the claim for one
particular inclusion $t\sset\calO\in T$. If we take $T$ to be
the standard trio, then the ``Turyn'' description of $\code$ in
\cite[ch.11, \S12]{jhc:splag} makes this obvious.  (The tetrad is the
unique tetrad containing $t$ that lies in the ``line code''.) 
\end{proof}

\begin{remark}
Finding $\tau$ algorithmically is easy---simply transform $T$ to the
standard trio in such a way that $t$ is carried into one of the MOG
columns. Then $\tau$ is just that column and the sextet is the
standard one. Performing this operation requires finding a suitable
permutation in $M_{24}$, which is easy using a few precomputed
permutations.  Also, such a permutation will be needed anyway in
theorem~\ref{thm-process-sextet} below.
\end{remark}

We say that $\calP$ determines a sextet $S$ if $S$ is the output of
algorithm~\ref{alg-sextet-search} applied to $\calP$.  All the
constructions of the algorithm are natural in the sense that they use
only the ordering on $\calR$  and the
structure of $\code$.  Therefore, if $g\in M_{24}$ and $\calP$ determines
the sextet $S$, then $g(\calP)$ determines the sextet $g(S)$.  On the
other hand, if $\calP$ doesn't determine a sextet then neither does
$g(\calP)$, and $g$ carries the refinement of $\calP$ to that of $g(\calP)$.
Given ordered partitions $\calP$ and $\calP'$ of $\Omega$, if one determines
a sextet and the other does not then they are not $M_{24}$-equivalent.
If both determine sextets then whether they are $M_{24}$-equivalent is
determined by the following theorem, and if neither does then it is
determined by theorem~\ref{thm-process-refinement}.

\begin{theorem}
\label{thm-process-sextet}
Suppose $\calP$ and $\calP'$ are ordered partitions of $\Omega$ that
determine sextets $S$ and $S'$, and let $g,g'\in M_{24}$ carry $S$ and
$S'$ to the standard sextet.  Then $\calP$ and $\calP'$ are
$M_{24}$-equivalent if and only if $g(\calP)$ and $g'(\calP')$ are equivalent
under the sextet group $2^6{:}3.S_6$ of order $138\,240$.
\end{theorem}

\begin{proof}
The `if' part is trivial.  For the converse, suppose $h\in M_{24}$
carries $\calP$ to $\calP'$, so that it carries $S$ to $S'$.  Then $g'\circ
h\circ g^{-1}$ carries $g(\calP)$ to $g'(\calP')$; it also carries the
standard sextet to itself, so it lies in the sextet group.
(This is essentially the argument we used for
theorem~\ref{thm-answer-if-both-determine-frames}.)
\end{proof}

Finding the permutations needed to apply theorem~\ref{thm-process-sextet} is
easy: we can just refer to tables of coset representatives for $M_{23}$
in $M_{24}$, $M_{22}$ in $M_{23}$, $M_{21}$ in $M_{22}$ and $M_{20}$ in $M_{21}$.

\begin{theorem}
\label{thm-process-refinement}
Suppose $\calP$ and $\calP'$ are ordered partitions of $\Omega$ that do not
determine sextets, and let $\calR$ and $\calR'$ be their refinements.  If
$\calR$ and $\calR'$ are not $S_{24}$-equivalent then $\calP$ and $\calP'$ are not
$M_{24}$-equivalent.  If $\calR$ and $\calR'$ are $S_{24}$-equivalent then:
\begin{enumerate}
\item
\label{case-shape1.1.1.5.6.10}
(Applies if both $\calR$ and $\calR'$ have shape $1^3.5.6.10$ or both have shape
$1^3.6^2.9$.) The octad containing the first hexad of $\calR$ contains
two of the monads, and the remaining monad is the first, second or third
monad of $\calR$; define $n=1$, $2$ or $3$ in these cases, and define
$n'$ similarly using $\calR'$ in place of $\calR$.  Then $\calP$ and $\calP'$ are
$M_{24}$-equivalent if and only if $n=n'$.
%
\item
\label{case-shape2.3.6.13}
(Applies if both $\calR$ and $\calR'$ have shape 2.3.6.13.) Let $h$ be the hexad of $\calR$
and $\calO$ the octad containing the duad and triad, and similarly for
$h'$ and $\calO'$.  Then $\calP$ and $\calP'$ are $M_{24}$-equivalent if and only
if $|h\cap\calO|=|h'\cap\calO'|$.
%
\item
\label{case-shape2.3.9.10}
(Applies if both $\calR$ and $\calR'$ have shape 2.3.9.10.)  Let $n$ be the nonad of $\calR$
and $\calO$ the octad containing the duad and triad, and similarly for
$n'$ and $\calO'$.  Then $\calP$ and $\calP'$ are $M_{24}$-equivalent if and only
if $|n\cap\calO|=|n'\cap\calO'|$.
%
\item
\label{case-other-shapes}
(Applies in all other cases.) $\calP$ and $\calP'$ are $M_{24}$-equivalent.
%
\end{enumerate}
\end{theorem}

\begin{proof}
Since $\calP$ and $\calP'$ are $M_{24}$-equivalent if and only if $\calR$ and
$\calR'$ are, we may without loss of generality replace $\calP$ and $\calP'$ by
$\calR$ and $\calR'$ throughout; then the first claim is obvious.  In
cases (\ref{case-shape1.1.1.5.6.10}) through (\ref{case-shape2.3.9.10}),
the criteria used to conclude inequivalence involve only the orderings on
$\calR$ and $\calR'$ and the structure of $\code$, so any conclusion of
inequivalence is justified.  We now treat cases
(\ref{case-shape1.1.1.5.6.10})--(\ref{case-other-shapes})
individually, proving that any conclusion of equivalence is justified.

In case $1^3.5.6.10$, both $\calR$ and $\calR'$ have shape
\hbox{\uline{5.1.1.1}\bline{1.1}{.6}.10} and $n=n'$.  Write $D$
(resp. $D'$) for the dodecad $\uline{5.1.6}$ of $\calR$ (resp. $\calR'$).  By
hypothesis $D$ (resp. $D'$) contains the $n$th monad of $\calR$
(resp. $\calR'$).  Since $M_{24}$ is transitive on dodecads we may suppose
$D'=D$.  Since the stabilizer $M_{12}$ of $D$ is 5-transitive on its
complement we may suppose that for $i\neq n$, the $i$th monad of $\calR$
coincides with that of $\calR'$; write $\delta$ for the duad consisting of
these two monads.  Now, only two octads of $\code$ meet $\Omega-D$
exactly in $\delta$, one of which meets $D$ in the hexad of $\calR$ and one
of which (possibly the same one) meets $D$ in the hexad of $\calR'$.  The pointwise stabilizer
of $\delta$ in $M_{12}$ is $M_{10}$, which contains a permutation exchanging
these two octads, so we may suppose the hexads of $\calR$ and $\calR'$
coincide.  Finally, the setwise stabilizer of this hexad in $M_{10}$  is
$A_6$, acting transitively 
on the remaining six points of $D$.  Therefore we may
suppose that the $n$th monad of $\calR$ coincides with that of $\calR'$,
i.e., $\calR'=\calR$.

In case $1^3.6^2.9$, both have shape
\hbox{\uline{6.1.1}\bline{1.1}{.6}.1.9} and the argument is the same except
that the last step is replaced by $A_6$ acting transitivity on the
decad.

In case $2.3.6.13$, both $\calR$ and $\calR'$ have shape
$\uline{6.2}.\uline{13.3}$.  The essential fact is the
following: the stabilizer $2^4{:}S_6$ of a special octad $\calO$ and a duad
$\delta$ contained in it acts with two orbits on triads $t$ in the
complementary 16-ad.  These orbits are distinguished by whether the
octad containing $t\cup\delta$ meets $\calO$ in~2 or~4 points.

In case $2.3.9.10$, both $\calR$ and $\calR'$ have shape
$\uline{9.3}.\uline{10.2}$, and the essential fact is the
following: the stabilizer $M_{10}.2$ of a dodecad $D$ and a duad $\delta$ in
it acts with two orbits on triads in the complementary dodecad.  These
orbits are distinguished by whether the octad containing $t\cup\delta$
meets $D$ in~2 or~4 points.

Now we treat all other cases.  The common shape of $\calR$ and
$\calR'$ is not one of those marked with a
bullet $\bullet$ in table~\ref{tab-shapes}, because otherwise they
would have determined sextets in
algorithm~\ref{alg-sextet-search}.  The shapes marked with circles $\circ$ are
those we have just treated.  For all remaining shapes in the table,
$M_{24}$ acts transitively on ordered partitions having that shape and
forming \csets in the indicated way.  The
analysis is easier than the cases above, and uses the following facts.
$M_{24}$ acts 5-transitively on $\Omega$ and transitively on octads,
dodecads and trios.  The octad stabilizer acts on the octad by $A_8$,
and acts $3+2$ and $1+3$ transitively on the octad and its complement.
The trio group permutes the three octads of the trio as $S_3$, and the
subgroup preserving each of them acts $3+1+0$ and $2+1+1$ transitively
on the octads in any order.  The stabilizer $M_{12}$ of a dodecad, say
$D$, acts $5+0$, $2+1$, $1+2$ and $0+5$ transitively on $D$ and its
complement.  The setwise stabilizer of a duad $\delta$ not meeting $D$ is
a subgroup $M_{10}.2$; this group contains a permutation preserving each
of the two octads that meet $\Omega-D$ exactly in $\delta$, say $\calO$ and
$\calO'$, and swapping the points of $\delta$.  It also contains a
permutation swapping $\calO$ and $\calO'$ and preserving each point of $\delta$.
The subgroup preserving each point of $\delta$ and each of the two octads
is $A_6$, acting in the natural way on each of the hexads $\calO-\delta$,
$\calO'-\delta$, and transitively on the 10-ad $\Omega-(D\cup\delta)$.  
All these assertions appear explicitly or implicitly in
\cite[ch.~10]{jhc:splag}. 
\end{proof}

\section{Remarks}
\label{sec-remarks}

We close with a few remarks, first on equivalence-testing under
the infinite group $\co\infty=\leech{:}\co0$ and then on possible analogues of our
algorithm for the complex and quaternionic versions of $\leech$.

Since we developed these algorithms in order to sort elements of
$II_{25,1}$ into orbits, we offer here a sketch of how to do this.
Following the line of reasoning in the introduction reduces the to
problem of equivalence of vectors in $\leech\tensor\Q$ under
$\co\infty$.  Borcherds (personal communication) has implemented an
algorithm to quickly find all lattice vectors lying within a given distance
of a given $v\in\leech\tensor\Q$. Coupling this with a decoder for $\leech$,
we may find the set $N_v$ of all nearest neighbors to $v$. Then, given
$v,w\in\leech\tensor\Q$ and $w'\in N_w$, $v$ and $w$ are
$\co\infty$-equivalent if and only if $w-w'$ and $v-v'$ are
$\co0$-equivalent for some $v'\in N_v$.  Of course $w-w'$ and $v-v'$
are in $\leech\tensor\Q$ not $\leech$, but after scaling we may apply
our $\co0$-algorithm.  This reduces the test under $\co\infty$ to at
most $|N_v|$ tests under $\co0$.

Happily, we never
need to worry about $N_v$ having size larger than $25$, because of the
following considerations.
The {diagram} $\Delta_v$ of $v$ is defined as the graph whose
vertices are the elements of $N_v$; two are unjoined
(resp. joined, doubly joined) if their  difference
has type $2$ (resp. $3$, $4$). See \cite{jhc:leech-radius} for more
information about these diagrams. $\Delta_v$ is always the
disjoint union of  spherical and affine Dynkin diagrams of
types $a_n$, $d_n$, $e_n$, $A_n$, $D_n$, and $E_n$ and hence is
a very simple combinatorial object. It is also true that
$|N_v|\leq48$, and in fact if $|N_v|>25$ then $v$ is a deep hole
of $\leech$ and its orbit under $\co\infty$ is completely
determined by the combinatorial type of $\Delta_v$. This means that
a test for equivalence under $\co\infty$ may be reduced to $25$
tests for equivalence under $\co0$. We will usually be able to
do even better than this by using some feature of $\Delta$.
For example, suppose $v$ and $w$ are
shallow holes, each with diagram of type $a_{17}d_7a_1$. Then any
transformation carrying $w$ to $v$ must carry the branch point
$w'$ 
of $\Delta_w$ to the branch point $v'$ of $\Delta_v$. Therefore
$v$ and $w$ are  $\co\infty$-equivalent  if and only if 
$v-v'$ and $w-w'$ are $\co0$-equivalent, so only a single equivalence
test is required. There are in
fact two orbits of shallow holes  with this diagram (see
\cite{reb:small-holes}), so we cannot determine equivalence  by simply inspecting
$\Delta_v$ and $\Delta_w$.

An extension of our ideas in a different direction concerns the
complex and quaternionic versions of $\leech$, whose automorphism
groups are the central extension $6{\cdot}Suz$ of the Suzuki sporadic
group and $2G_2(4)$.  The complex Leech lattice (see
\cite{raw:complex-leech}) is a lattice over $\Z[\omega=\root3\of1]$,
whose underlying real lattice is $\leech$, scaled to have minimal
norm~6.
It
has $3^{12}$ congruence classes modulo
$\theta=\omega-\bar\omega=\sqrt{-3}$, and these have minimal
representatives of norm $\leq9$. The only congruences modulo $\theta$
among these vectors are that each norm~6 vector is congruent to its
multiples by powers of $\omega$, and that the norm~9 vectors fall into
classes (``frames'') of 36 vectors, any two of which are orthogonal or
proportional by a power of $\omega$. The stabilizer of a frame is
$3^5.M_{11}$ ($M_{11}$ being the Mathieu group of order~7920).  In a
manner similar to $2^{12}{:}M_{24}$, $M_{11}$ acts by permuting $12$
complex coordinates, and $3^5$ acts by multiplying the coordinates
by various scalars.  If one proved an analogue of
Curtis' theorem on
\slattices then one could devise an algorithm for equivalence of
vectors in the complex Leech lattice under $6.Suz$. If such an
analogue is true, then its proof should be easier than that of
Curtis's original theorem. The quaternionic Leech lattice (see
\cite{raw:quaternionic-leech}) has an even simpler structure: modulo
$1+i$, every vector is congruent to either 0 or a minimal vector. The
minimal vectors fall into 4095 classes (again called frames), each
consisting of 48 vectors, any two of which are either proportional by
an element of $\{\pm1,\pm i,\pm j,\pm k\}$ or orthogonal. The
stabilizer of a frame is the group $2^6.(2^2\times A_5).2$ of order
$30\,720$, and so an analogue of the $\co0$ algorithm is obvious:
supposing that $1+i$ divides neither $v$ nor $w$, reduce $v$ and $w$
modulo $1+i$, carry each of the resulting frames to the standard one,
and then check for equivalence under the group stabilizing the
frame. The reader should note that one of Wilson's frames
\cite{raw:quaternionic-leech} contains three of ours, with
$3\cdot48=144$ vectors, and has slightly larger stabilizer.

\begin{thebibliography}{99}

\bibitem[Allcock 1996]{dja:thesis}
D.~J. Allcock,
 {\it The {L}eech Lattice and Hyperbolic Geometry},
 Ph.D. thesis, U.C. Berkeley (1996).
\bibitem[Borcherds 1984]{reb:thesis}
R.~E. Borcherds,
 {\it The {L}eech Lattice and Other Lattices},
 PhD thesis, Cambridge University, 1984.
\bibitem[Borcherds 1985]{reb:leech-lattice}
R.~E. Borcherds,
 The {L}eech lattice,
 {\it Proceedings of the Royal Society of London}, A398:365--376,
  1985.
\bibitem[Borcherds 1987]{reb:lzl}
R.~E. Borcherds, 
 Automorphism groups of {L}orentzian lattices,
 {\it Journal of Algebra}, 111:133--53, 1987.
\bibitem[Borcherds 1990]{reb:fake-monster}
R.~E. Borcherds,
 The monster {L}ie algebra,
 {\it Advances in Mathematics}, 53:30--47, 1990.
\bibitem[Borcherds 1988]{reb:24-dimensional-classification}
R.~E.~Borcherds,
The 24-dimensional odd unimodular lattices, in \cite{jhc:splag}, 421-430.
\bibitem[Borcherds et. al. 1988]{reb:small-holes}
R.~E. Borcherds, J.~H. Conway, and L.~Queen,
 The cellular structure of the {L}eech lattice,
 In {\it Sphere Packings, Lattices, and Groups\/} \cite{jhc:splag}, pages
  513--21.
\bibitem[Conway 1969]{jhc:dot0}
J.~H. Conway,
 A group of order 8,315,553,613,086,720,000,
 {\it Bulletin of the London Mathematical Society}, 1:79--88, 1969.
\bibitem[Conway 1983]{jhc:26dim}
J.~H. Conway,
 The automorphism group of the 26-dimensional even unimodular
  {L}orentzian lattice,
 {\it Journal of Algebra}, 80:159--163, 1983.
 Reprinted in \cite{jhc:splag}.
\bibitem[Conway 1988]{jhc:mog}
J.~H. Conway,
 The {G}olay codes and the {M}athieu groups,
 In \cite{jhc:splag}, pages
  299--30.
\bibitem[Conway et. al. 1982]{jhc:leech-radius}
J.~H. Conway, R.~A. Parker, and N.~J.~A. Sloane,
 The covering radius of the {L}eech lattice,
 {\it Proceedings of the Royal Society of London}, A380:261--90, 1982.
 Reprinted in \cite{jhc:splag}.
\bibitem[Conway et. al. 1985]{ATLAS}
J.~H. Conway, R.~T. Curtis, S.~P. Norton, R.~A. Parker, and R.~A. Wilson,
 {\it {A}{T}{L}{A}{S} of Finite Groups},
 Oxford, 1985.
\bibitem[Conway and Sloane 1982]{jhc:vinberg-gps}
J.~H. Conway and N.~J.~A. Sloane,
 {L}eech roots and {V}inberg groups,
 {\it Proceedings of the Royal Society of London}, A384:233--58, 1982.
 Reprinted in \cite{jhc:splag}.
\bibitem[Conway and Sloane 1986]{jhc:decode}
J.~H. Conway and N.~J.~A. Sloane,
 Soft decoding techniques for codes and lattices, including the
  {G}olay code and the {L}eech lattice,
 {\it Institute of Electrical and Electronics Engineers, Transactions
  on Information Theory}, 32:41--50, 1986.
\bibitem[Conway and Sloane 1988]{jhc:splag}
J.~H. Conway and N.~J.~A. Sloane, {\it Sphere Packings, Lattices and
  Groups}, Springer-Verlag 1988.
\bibitem[Curtis 1973]{rtc:slattices}
R.~T. Curtis,
 On subgroups of $\cdot0$, {I}: Lattice stabilizers,
 {\it Journal of Algebra}, 27:549--73, 1973.
\bibitem[Curtis 1976]{rtc:mog}
R.~T. Curtis,
 A new combinatorial approach to ${M}_{24}$,
 {\it Proceedings of the Cambridge Philosophical Society}, 79:25--42,
  1976.
\bibitem[Vardy and Be'ery 1991]{be'ery:perfect-golay}
A.~Vardy and Y.~Be'ery,
 More efficient soft decoding of the {G}olay codes,
 {\it Institute of Electrical and Electronics Engineers, Transactions
  on Information Theory}, 37(3):667--672, 1991.
\bibitem[Vardy and Be'ery 1993]{be'ery:perfect-leech}
A.~Vardy and Y.~Be'ery.
 Maximum likelihood decoding of the {L}eech lattice.
 {\it Institute of Electrical and Electronics Engineers, Transactions
  on Information Theory}, 39(4):1435--1444, 1993.
\bibitem[Vinberg 1972]{vinberg}
E.~B.~Vinberg,
On the groups of units of certain quadratic forms,
{\it Math. Sb.}, 87 (1972) 18--36.
\bibitem[Vinberg and Kaplinskaja 1978]{vinberg-kaplinskaja}
E.~B.~Vinberg and I.~M.~Kaplinskaja,
On the groups $O_{18,1}(Z)$ and $O_{19,1}(Z)$,
{\it Dokl. Akad. Nauk.}, 238 (1978) 1273--1275.
\bibitem[Wilson 1982]{raw:quaternionic-leech}
R.~A. Wilson.
 The quaternionic lattice for $2{G}_2(4)$ and its maximal subgroups.
 {\it Journal of Algebra}, 77:449--466, 1982.
\bibitem[Wilson 1983]{raw:complex-leech}
R.~A. Wilson.
 The complex {L}eech lattice and maximal subgroups of the {S}uzuki
  group.
 {\it Journal of Algebra}, 84:151--188, 1983.
\end{thebibliography}

\end{document}