\documentclass[XUPS,XML,SOM,Unicode,english, NoFloatCountersInSection]{cedram}
\usepackage{xups93-02}
\setcounter{tocdepth}{2}
\graphicspath{{xups93-02_fig}}

\makeatletter
\def\lsectionpart{\let\l@section\l@part}
\makeatother

\begin{document}
\frontmatter

\title{Algebraic curves and sphere packings}

\author[\initial{M.} \middlename{A.} \lastname{Tsfasman}]{\firstname{Michael} \middlename{A.} \lastname{Tsfasman}}

\address{Institute for Information Transmission Problems,
19 Ermolovoi Street, GSP-4 Moscow 101447, Russia\\
\& Laboratoire de Mathématiques Discrètes,
Luminy - Case 930, 13288 Marseille cedex 9, France}
\email{mtsfasman@yandex.ru}

\thanks{Journées X-UPS 1993. Codes géométriques algébriques et arithmétique sur les corps finis. Prépublication du Centre de mathématique de l'École polytechnique, 1993}

\maketitle

\vspace*{-2\baselineskip}
\tableofcontents
\mainmatter

This talk is mostly devoted to problems which resemble greatly questions about
codes, namely to quite a classical problem of dense packing of equal
non-overlapping spheres in ${\Bbb R}^{N}$. It comes out that both direct application
of algebraic-geometric codes and use of intuition developed while studying
them are quite useful. Moreover, here one can see even better the marvelous
integrity of mathematics, two more parts of which --- number theory and that of packings --- being added to coding theory and algebraic geometry.

In the first chapter we give necessary definitions and produce some beautiful
examples. This chapter is quite classical and has nothing to do with either
algebraic geometry or number theory.

The relations with the latter are discussed in the second chapter devoted to
algebraic geometry and number theory constructions of lattices and packings.

\part{Definitions and examples}

How can one pack equal non-overlapping spheres in ${\Bbb R}^{N}$? What is the
density of such packing and how the density behaves for small values of $N$?
For large values of $N$? How to put the asymptotic problem for $N \to
\infty$?

In \S 1 we give some basic definitions and introduce different parameters of
sphere packings. Then we show how to put the problem rigorously. In \S 2 we
give some examples of dense packings. Then, in \S 3 we discuss the asymptotic
setting. The striking similarity between codes and packings is briefly
discussed in \S 4.

\section{Parameters}

\subsubsection*{Packings}
Let us consider the classical problem of {\em packing} equal
non-overlap\-ping spheres in ${\Bbb R}^{N}$. Let $P$ be the set of centers and let
$$
d = d(P) = \mathop{\inf}\limits_{\substack{v, u \in L\\ v \not= u}} |u - v|,
$$
$d$ is the {\em minimum distance} of the packing, which equals the maximum possible
diameter of non-overlapping spheres centered in $P$.

The {\em density} of $P$ is the part of ${\Bbb R}^{N}$ covered by spheres; to be precise,
it can be defined as
$$
\Delta (P) = \mathop{\lim\sup}\limits_{u \to \infty} v (S \cap B_{u})/v (B_{u}),
$$
where
\begin{align*}
S &= \Bigl\{ x \in {\Bbb R}^{N} \bigm|\exists y \in P,\; |x - y| < {d\over 2}\Bigr\}
\\
B_{u} &= \Bigl\{x \in {\Bbb R}^{N} \bigm| |x| \leq u\Bigr\}
\end{align*}
and $v(\cdot )$ is the standard volume in ${\Bbb R}^{N}$.

\subsubsection*{Lattices}
If $P$ is an additive subgroup of ${\Bbb R}^{N}$, we call the packing
$P$ a {\em lattice packing} (or just a {\em lattice}; in this case we use the letter $L$
rather than $P$). Further on we suppose that the rank of $L$ equals~$N$ since
otherwise $\Delta (L) = 0$. If $L$ is a lattice then any choice of a basis $e_{1},
\ldots, e_{N}$ in $L$ defines a map ${\Bbb Z}^{N} \to {\Bbb R}^{N}$; its matrix is
called a {\em generator matrix} of the lattice.

For lattices the definition of $\Delta(L)$ does not depend on the choice of origin
and does not change if we replace the ball $B_{u}$ by a cube (or by any
homothetically increasing solid containing a neighbourhood of the origin).

The volume of the fundamental domain
$$
F = \biggl\{\sum^{N}_{i=1} x_{i} e_{i} \Bigm| 0 \leq x_{i} < 1\biggr\} \subset {\Bbb R}^{N}
$$
equals the absolute value of the determinant of the generator matrix. This
volume is called the {\em determinant} of the lattice and is denoted by
$\det(L)$; we define the discriminant $\discr(L)$ of $L$ as the determinant of the
matrix of inner products $\|(e_{i}, e_{j})\|$, $i, j = 1,\ldots, N$. It is easy to check that
$$
\discr L = (\det L)^{2}.
$$

Let $V_{N} = \pi^{N/2}/\Gamma (N/2 + 1)$ be the volume of unit ball in ${\Bbb R}^{N}$.

For a lattice there is exactly one sphere in each fundamental domain, or --- to be more precise --- the pieces of spheres in the fundamental domain, being
shifted, form just one sphere. Therefore
$$
\Delta (L) = {d(L)^{N} V_{N}\over 2^{N} \det L}.
$$

Note that by the Stirling formula we have
$$
\log_{2} V_{N} = {N\over 2}\cdot \log_{2} \left( {2\pi e\over N}\right) - \log_{2}
\sqrt{\pi \cdot N} + o(1) ;
$$
we write this as
$$
{1\over N} \cdot \log_{2} V_{N} \sim {1\over 2} \cdot \log_{2} \left( \sfrac{2\pi e}{N}\right).
$$

Thus for $N \to \infty$ we get
$$
- {1\over N} \cdot \log_{2} \Delta(L) \sim - \log_{2}
\sqrt{\pi \cdot e\over 2} + \log_{2} \sqrt{N} - \log_{2} d(L) + {1\over N} \cdot
\log_{2} (\det L).
$$

\subsubsection*{Other parameters}
Let us define some other parameters of packings (which
are often more convenient than $\Delta$) setting
\begin{align*}
\delta (P) &= \Delta (P)/V_{N},\\
\lambda(P) &= -(\log_{2} \Delta(P))/N,\\
\nu(P) &= \log_{2} \delta(P) ;
\end{align*}
we call $\delta(P)$ the {\em center density}, and $\lambda(P)$ the {\em density exponent}. Clearly,
$$
\Delta (P) = 2^{-\lambda(P)\cdot N}.
$$

For root lattices it is convenient to use $\delta(P) ; \nu(P)$ is useful to
compute the density of lattices obtained by some specific constructions. The density exponent $\lambda(P)$ is especially important for asymptotic problems.

\subsubsection*{Densest packings}
Set
$$
\lambda(N) = \inf_{P\subset {\Bbb R}^{N}} \lambda(P), \quad\Delta(N) = \sup_{P\subset {\Bbb R}^{N}} \Delta
(P),\ldots
$$

A natural problem of finding the densest possible packing in a given dimension can be decomposed into two problems:
\begin{enumerate}
\item[(A)] Find the precise value of $\lambda(N)$ (or, what is the same, of $\Delta(N)$
or of $\delta(N),\ldots$).
\item[(B)] Find a packing $P$ with $\lambda(P) = \lambda(N)$.
\end{enumerate}

These problems are completely solved only for $N =1$ and $N=2$.

Since $\Delta(P) \leq 1$, we get
$$
\lambda(P) \geq 0
$$
for any packing.

For $N = 1$ the answer is obvious: equal segments cover the whole line, and
hence for this packing $L_{1}$ one has $\Delta (L_{1}) = 1$, i.e., $$
\Delta (1) = 1, \quad\lambda(1) = 0.
$$

For $N = 2$ the problem is not so simple but one can prove that
$$
\Delta (2) = \pi/2\sqrt{3}.
$$
It is easy to check that for the lattice $L_{2}\subset {\Bbb R}^{2} = {\Bbb C}$ generated
by 1 and $\psfrac{1 + \sqrt{-3}}{2}$ we have $\Delta (L_{2}) = \Delta (2) ; L_{2}$ is
called the {\em hexagonal} lattice.

Strangely enough, $\lambda(N)$ is unknown for any $N \geq 3$.

The figures 1, 2, 3 show the densest known packings in dimensions 1, 2, and 3.

\begin{figure}[htb]
\begin{center}
\includegraphics{xups93-02_fig1}
\end{center}
\caption{: $\dim = 1$, $\Delta = 1$}
\end{figure}

\begin{figure}[htb]
\begin{center}
\includegraphics{xups93-02_fig2}
\caption{$\dim = 2$, $\dpl\Delta={\pi\over\sqrt{12}} =0.9069\cdots$}
\end{center}
\end{figure}
In fact, the packing in dimension 2 is obtained by taking a line, putting
spheres of dimension two at the centers of the best packing in dimension one
along this line, then taking a similar row next to it as close as possible,
then another row, and so on. It can be shown that it is essentially unique.

\begin{figure}[htb]
\begin{center}
\includegraphics{xups93-02_fig3}
\caption{$\dim = 3$, $\dpl\Delta={\pi\over\sqrt{18}} =0.7405\cdots$}
\end{center}
\end{figure}

We can do the same in dimension three. Take a plane, put three-dimensional
spheres at the centers ``$a$'' of the best two-dimensional packing. Then we
have to choose the next layer. It can be centered either over ``$b$'' points,
or over ``$c$'' points. Continuing like this we have continually many choices
corresponding to binary sequences, the density being the same. One of these
choices gives the lattice packing you see on the figure.

It is conjectured that this packing is the densest possible. Recently a proof
has been announced, but as yet the mathematical community does not believe in
it.

\subsubsection*{Densest lattices}
For lattice packings we know slightly more. Let\vspace*{-3pt}
$$
\lambda_{\ell} (N) = \inf_{L\subset {\Bbb R}^{N}} \lambda(L), \quad \Delta_{\ell}(N) =\sup_{L\subset {\Bbb R}^{N}} \Delta(L),\ldots
$$
Clearly\vspace*{-3pt}
$$
\lambda_{\ell} (N) \geq \lambda(N), \quad\Delta_{\ell} (N) \leq \Delta(N),\ldots
$$
A lattice $L$ is called {\em unimodular} iff $\det L =1$. The {\em dual lattice}\vspace*{-1pt}
$$
L^{\perp} = \bigl\{ x \in {\Bbb R}^{N} \bigm| (x, \ell)\in {\Bbb Z} \qqbox{for any} \ell \in L\bigr\}
$$
is in this case also unimodular.

The inner product in ${\Bbb R}^{N}$ induces on $L$ a positively definite bilinear
form.

In fact, any integral positively definite bilinear form can be obtained from a
lattice.

Let now $\varphi (x, y)$ be a positively definite bilinear form in $N$ integral
variables, and let $f(x) = \varphi (x, x)$ be the corresponding quadratic form.
Suppose that $\varphi$ is unimodular, i.e., $\discr \varphi =1$. Such forms are in
bijection with unimodular lattices $L$ in ${\Bbb R}^{N}$. Set\vspace*{-3pt}
$$
\gamma (L) = \gamma (\varphi) = \min_{x\in{\Bbb Z}^{N}-\{0\}} f(x).
$$

In lattice terms it is the squared length of the shortest non-zero vector. It is easy to check that\vspace*{-3pt}
\begin{align*}
\Delta (L) &= V_{N}\cdot \left( \sfrac{\gamma (L)}{4}\right)^{N/2} ;
\\
\gamma (L) &= 4 \cdot \left( \sfrac{\Delta (L)}{V_{N}}\right)^{2/N} = 4\cdot (\delta(L))^{2/N}.
\end{align*}
One can naturally extend the definition of $\gamma(\varphi)$ to non-unimodular case:
$$
\gamma (L) = \gamma (\varphi) = \min_{x\in {\Bbb Z}^{N}-\{0\}} \left( \sfrac{f(x)}{\discr \varphi}\right)^{1/N}.
$$
Now let us put
$$
\gamma (N) = \max_{\varphi} \gamma (\varphi),
$$
where maximum is taken over all positively definite bilinear forms in $N$
variables; $\gamma (N)$ and $\Delta_{\ell}(N)$ are related by formulas similar to
those given above.

Note that for $N \to \infty$ we obtain
$$
\lambda(N) \sim \log_{2} \sqrt{2N\over \pi\cdot e\cdot \gamma(N)},
$$
$$
\log_{2} (\gamma(N)) \sim \log_{2} \left( \Psfrac{2N}{\pi e}\cdot \Delta^{2/N}\right) =
-2\cdot \lambda(N) + \log_{2} \left( \sfrac{2N}{\pi e}\right).
$$

Precise values of $\Delta_{\ell}(N)$ are known for $1 \leq N \leq 8$; see the
table where we have collected the values of all the above parameters for these $N$.
$$\arraycolsep4pt
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
 & & & & & & & & \\
N & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ & & & & & & & & \\
\hline
 & & & & & & & & \\
\Delta_{\ell}(N) &1 & 0.907 & 0.740& 0.617 & 0.465 & 0.373 & 0.295 &0.254 \\ & & & & & & & & \\
\delta_{\ell}(N) &0.5 &0.229 &0.177 &0.125 &0.088 &0.072 &0.063 &0.063 \\ & & & & & & & & \\
\lambda_{\ell}(N) &0 &0.070 &0.144 &0.174 &0.221 &0.237 &0.251 &0.247 \\ & & & & & & & & \\
\nu_{\ell}(N)&-1 &-1.792 &-2.5 &-3 &-3.5 &3.792 &-4 &-4 \\ & & & & & & & & \\
\gamma_{\ell}(N) &1 &1.155 &1.260 &1.414 &1.516 &1.665 &1.811 &2 \\ & & & & & & & & \\
\delta_{\ell}(N)^{-2} &4 &12 &32 &64 &128 &192 &256 &256 \\ & & & & & & & & \\
\hline
\end{array}\vspace*{\baselineskip}
$$

Note that within the table $\Delta_{\ell}(N)$ increases and $\gamma_{\ell}(N)$
decreases. It is interesting to know whether it is the case for any $N$.

In the table the integrality of $\delta_{\ell}(N)^{-2}$ attracts attention. We do
not know whether $\delta_{\ell}(N)^{-2}$ is integral for any $N$; note however
that the densest lattice of a given rank can be generated by a matrix with
rational entries and the rationality of $\delta_{\ell}(N)^{-2}$ follows.

\section{Examples}

Now we describe the densest lattices for $N \leq 8$ and introduce some
interesting lattice families.

We construct families $L \subset {\Bbb R}^{N}$ and give the values of $d (L)$ and
$\det (L)$. Other density parameters for these families are given in the table
above.

The simplest family is
$$
{\Bbb Z}^{N} \subset {\Bbb R}^{N} ;
$$
for these lattices
$$
d({\Bbb Z}^{N}) = 1, \quad\det ({\Bbb Z}^{N}) = 1.
$$

\subsubsection*{Root lattices}
Let us consider in ${\Bbb R}^{N+1}$ the following lattice $A_{N}$ of
rank $N$:
$$
A_{N}= \biggl\{ \sum^{N+1}_{i=1} a_{i} e_{i}\Bigm| a_{i}\in {\Bbb Z}, \sum a_{i} = 0\biggr\},
$$
$\{e_{i}\}$ being the standard basis in ${\Bbb R}^{N+1}$.

The lattice $A_{N}$ is generated by vectors
$$
\alpha_{1} = e_{1}-e_{2}, \,\alpha_{2}= e_{2}-e_{3},\ldots, \,\alpha_{N}= e_{N}- e_{N+1} ;
$$
its parameters are
$$
d(A_{N}) = \sqrt{2},\quad \det (A_{N}) = \sqrt{N+1}.
$$

The family $D_{N}\subset {\Bbb R}^{N}$ is defined by
$$
D_{N}= \biggl\{\sum^{N}_{i=1} a_{i} e_{i}\Bigm| a_{i}\in {\Bbb Z}, \;\sum a_{i} \equiv 0 \bmod 2\biggr\}.
$$

The lattice $D_{N}$ is generated by $\alpha_{1} = e_{1} - e_{2}$, $\alpha_{2}= e_{2}-
e_{3}$,\ldots, $\alpha_{N-1} = e_{N-1} - e_{N}$, and $\alpha_{N} = e_{N-1} + e_{N}$;
its parameters are
$$
d (D_{N}) = \sqrt{2}, \quad\det (D_{N}) = 2.
$$

The following important family does exist only for $N=4, 5, 6, 7, 8$. For such
$N$ define the lattice $E_{N}$ in ${\Bbb R}^{8}$ by its basis:
\begin{align*}
\alpha_{1} &= {1\over 2} (e_{1} + e_{8}) - {1\over 2}\cdot (e_{2} + \cdots +
e_{7}),\\
\alpha_{2} &= e_{1}+e_{2},\\
\alpha_{i} &= e_{i} - e_{i-1} \quad\qqbox{for} i = 3,\ldots, N.
\end{align*}

The lattice $E_{8}$ can be given by
$$
E_{8} = \biggl\{\sum^{8}_{i=1} a_{i}\cdot e_{i} \Bigm| 2\cdot a_{i}\in {\Bbb Z}, \; a_{i} -a_{j}\in {\Bbb Z}, \;\sum^{8}_{i=1} a_{i}\in 2\cdot {\Bbb Z}\biggr\};
$$
and the rest $E_{N}$ are intersections of $E_{8}$ with planes of codimension
$(8-N)$. In particular,
\begin{align*}
E_{7} &= \biggl\{ x = \sum^{8}_{i=1} a_{i}\cdot e_{i} \Bigm| x\in E_{8}, \;a_{7} = -a_{8}\biggr\},\\
E_{6} &= \biggl\{ x = \sum^{8}_{i=1} a_{i}\cdot e_{i} \Bigm| x\in E_{7}, \;a_{6} = -a_{7}\biggr\}.
\end{align*}

The parameters are $d(E_{N})= \sqrt{2}$ and $\det (E_{N}) = 9 -N$.

Note that $A_{1} = {\Bbb Z}, D_{3}=A_{3}, E_{4}=A_{4}, E_{5}=D_{5}$. The lattice families $A, D$,
and $E$ are root lattices which arise in many questions: in the theory of Lie
groups and algebras, in the singularity theory, in the theory of rational
surfaces, etc.

\subsubsection*{Lattices $\Gamma$}
Let now $N \geq 8, N \equiv 0 \bmod 4$. Set
$$
\Gamma_{N} =  \biggl\{\sum^{N}_{i=1} a_{i}\cdot e_{i} \Bigm| 2\cdot a_{i}\in {\Bbb Z}, \; a_{i} -
a_{j}\in {\Bbb Z},\; \sum^{N}_{i=1} a_{i}\in 2 {\Bbb Z}\biggr\}.
$$
The lattice $\Gamma_{N}$ is generated by vectors $e_{i} + e_{j}$ and the vector
${1\over 2} \sum^{N}_{i=1} e_{i}$; its parameters are
$$
d (\Gamma_{N}) \geq \sqrt{2}, \quad\det (\Gamma_{N})=1.
$$
Note that $\Gamma_{8} = E_{8}$.

The lattices $A_{1} = {\Bbb Z}, A_{2}, A_{3}=D_{3}, D_{4}, D_{5}, E_{6}, E_{7},
E_{8} = \Gamma_{8}$ have the density coinciding with that from the table. They are
the densest lattices in their dimensions. A proof of this fact can be obtained
by the reduction theory of quadratic forms.

Note that for all the described families
$$
\lambda(L_{N}) \sim \log_{2}\sqrt{N} \to \infty \qqbox{for} N\to \infty.
$$

We shall see that there are lattices which asymptotically behave significantly
better.

For $N \geq 9$ we do not know the precise value of $\lambda_{\ell}(N)$ and only
some bounds are known. As in the case of codes it is natural to call upper
bounds for $\Delta(N)$ and $\Delta_{\ell}(N)$ {\em possibility bounds} and lower ones
{\em existence bounds} (note however that for $\lambda(N)$ possibility bounds are
lower ones, and existence bounds are upper ones).

We do not describe here various methods of constructing dense packings in
dimensions from 9 up to 100000. We need here only the Leech lattice which is a
very beautiful object arising in many questions.

\subsubsection*{Leech lattice}
There exists a unique integral even unimodular lattice
of dimension 24 which has no vector of length $\sqrt{2}$ (recall that a lattice
is called {\em even} iff the scalar square of any of its vectors is even). This
lattice is called {\em Leech lattice} and is denoted by $\Lambda_{24}$; it is
closely connected with Golay $[24, 12, 8]_{2}$-code $C_{24}$. It can be
constructed in many ways. Here is one of the simplest.

The lattice $\Lambda_{24}$ is generated by vectors
$$
V_{i, c} = {1\over \sqrt{8}} \cdot u_{i, c}, \quad 1 \leq i \leq 24, \; c \in C_{24},
$$
where $u_{i, c}$ has $\mp 3$ in $i$-th position and $\pm 1$ in all other
positions, and the upper sign is chosen for a position where the codeword $c$ has 1.

The parameters of the Leech lattice are
$$
\det (\Lambda_{24}) = 1, \quad d(\Lambda_{24}) = 2 ;
$$
therefore,
\begin{gather*}
\delta(\Lambda_{24}) = 1,\; \nu(\Lambda_{24}) = 0, \;\gamma(\Lambda_{24}) = 4,
\\
\Delta(\Lambda_{24}) \approx 0.00193 \qqbox{and} \lambda(\Lambda_{24}) \approx 0.376.
\end{gather*}
The covering radius of the Leech lattice equals $2\sqrt{2}$, i.e., balls of
radius $2\sqrt{2}$ centered at lattice points cover the whole space ${\Bbb R}^{24}$.
One can describe ``deep holes'' of the Leech lattice, i.e., points with distance
$2\sqrt{2}$ from the nearest lattice point.

The automorphism group $Co_{0}$ of the Leech lattice is enormous:
$$
|Co_{0}| = 8315553613086720000.
$$

The maximal sporadic simple group, the Fischer-Gries group (the Monster), can
be realized as the automorphism group of an algebra closely connected to the
Leech lattice.

\subsubsection*{Kissing number}
There is another nice problem concerning sphere packings,
of slightly a different nature (local). How many spheres can touch the given
sphere in an $N$-dimensional space (all spheres being equal)? This number is
called the {\em kissing number}.

The answer is known only in dimensions 1, 2, 3, 8, and 24, the kissing
numbers being respectively 2, 6, 12, 240, and 196560. The examples are
given by local arrangements in the lattices $A_{1}, A_{2}, A_{3}, D_{4},
E_{8}$, and $\Lambda_{24}$.

\section{Asymptotic problems}
For asymptotic problems it is convenient to consider
$$
\wt \lambda = \mathop{\lim \inf}\limits_{N\to \infty} \lambda(N).
$$
To compute $\wt \lambda$, i.e., to understand what is the maximum asymptotic
density $\wt \Delta = 2^{-\wt \lambda N}$ of a high-dimensional packing, is most
likely a very hard problem. We are interested in bounds for this value. The
situation here is similar to that in coding theory, and $\wt \lambda$ is an
analogue of $\alpha_{q}(\delta)$.

A {\em family} of packings is a set $\{P_{N}\}$ of packings, $P^{N}\subset {\Bbb R}^{N}$
where~$N$ runs over an infinite subset of $\NN$.

Let
$$
\lambda(\{P_{N}\}) = \lim \inf \lambda(P_{N}).
$$

We call families with $\lambda(\{P_{N}\}) < \infty$ {\em good families} (they are
analogues of good families of codes, i.e., those with
$k/n \to R > 0$ and $d/n \to \delta > 0$).

One can show that $\mathop{\inf}\limits_{\{P_{N}\}} \lambda(\{P_{N}\}) =
\wt \lambda$.

Similarly for lattices we set
$$
\wt \lambda_{\ell} = \mathop{\lim \inf}\limits_{N\to \infty} \lambda_{\ell}(N) =
\inf_{\{L_{N}\}} \lambda(\{L_{N}\}).
$$

\subsubsection*{Bounds}
Here are the best known estimates of $\wt \lambda$ :

\begin{th*}
$1 \geq \wt \lambda_{\ell} \geq \lambda \geq 0.599$.
\end{th*}

The upper bound which is an existence bound is called the Minkowski bound, the
lower one (a possibility bound) the Kabatyan\-sky-Levenstein bound.

The Kabatyansky-Levenstein bound can be obtained by technique similar to that
of the Mc Eliece-Rodemich-Ramsey-Welch bound in coding theory. The proof of the
former consists of two parts : the first is the linear programing bound for
packing of spheres on $S^{N}\subset {\Bbb R}^{N+1}$ and the second provides a way to
pass from $S^{N}$ to ${\Bbb R}^{N}$, which is based on the following simple
construction. Let $\Lambda_{N}$ be a packing in ${\Bbb R}^{N}$ and let us embed
${\Bbb R}^{N}$ into ${\Bbb R}^{N+1}$ in the natural way (i.e., assuming that vectors from
${\Bbb R}^{N}$ have zero for the last coordinate). Thus ${\Bbb R}^{N}\cap S^{N} =
S^{N-1}$ ; let us consider those balls from $\Lambda_{N}$ which are contained in
the unit $(N-1)$-ball. Lifting their centers to $S^{N}$ we obtain a packing of
$S^{N}$ and its parameters can be estimated through the parameters of
$\Lambda_{N}$.

Here is another bound (Rogers):

\begin{prop*}
$
\Delta(N) \leq \sigma_{N}
$,
where $\sigma_{N}$ is the ratio of the volume of the intersection
$\left( \bigcup^{N+1}_{i=1} B_{i}\cap \Sigma_{N}\right) $ to the volume of
$\Sigma_{N}$, where $\Sigma_{N}$ is the perfect simplex of edge length $2$ and $B_{1},\ldots, B_{N+1}$ are unit balls centered at the vertices of
$\Sigma_{N}$.
\end{prop*}

The Rogers bound gives $\wt \lambda \geq 0.5$ but it is quite useful for moderate
values of $N$.

The Minkowski bound (which is an analogue of the Gilbert-Varshamov bound) can
be obtained by a technique similar to the code-theoretic one. As in the case of
codes almost all linear codes asymptotically lie on the Gilbert-Varshamov
bound, here almost all lattice families have $\lambda(\{L_{N}\}) =1$.

Thus it is known that there exists lattices of density $\Delta \sim 2^{-N}$ but we
do not know how to construct them explicitly. The problem of explicit
construction of dense packings
naturally arises.

\section{Codes and packings}
Between codes and packings there exists a system of beautiful analogies.
Indeed, one can consider an $[n, k, d]_{q}$-code $C\subseteq {\Bbb F}^{n}_{q}$ as
the set of centers of a sphere packing (of radius $t = \left[ \psfrac{d-1}{2}\right] $) in the Hamming metric. Minimum distance of a code corresponds to
the diameter $d(L)$ of a sphere packing.

Linear codes correspond to lattice packings. Indeed, a linear code is a subset
in ${\Bbb F}^{n}_{q}$ which is closed under addition and under multiplication
by
elements of ${\Bbb F}_{q}$, and lattice is closed under addition and multiplication
by integers. Strictly speaking, we can consider ``quasi-linear'' codes, i.e., subsets which are closed under addition and under multiplication by elements of
${\Bbb F}_{p}$ (rather than ${\Bbb F}_{q}$) as an analogue of lattices, but we do not
pursue this idea here.

Let $C$ be a linear $[n, k, d]_{q}$-code. Then the volume (the cardinality) of
the factor-space ${\Bbb F}^{n}_{q}/C$ equals $q^{n-k}$. For a lattice $L \subset
{\Bbb R}^{N}$ the volume of the factor-space ${\Bbb R}^{N}/L$ equals $\det (L)$, i.e., $\log
(\det L)$ is an analogue of the code codimension $(n-k)$. To be definite we
shall assume that in the expression $\log (\det L)$ the $\log$ symbol
corresponds to the binary logarithm.

There are two possible analogues of the dimension $N$ of a lattice (which
equals its rank): the length $n$ and the dimension $k$ of a code. We use the
first one; nevertheless we think that the second can be also of some use.

The density of a packing corresponds to the density of a packing in the Hamming
metric. Note that the density of a lattice packing equals the volume of the
ball of radius $d$ divided by $\det L$. For the density of a packing in the
Hamming metric the analogous statement is also true if we assume the ball
volume to be normalized:
$$
\mbox{the ball volume} = (\mbox{number of points in the ball})/q^{n}.
$$

An analogy between code and lattice parameters is not complete. Indeed, the
density of packing does not change under a homothety $L \mto a\cdot L$.
Hence
one can assume that $d(L) =1$ (or $\det L =1$) and thus a packing has two
essential parameters $N$ and $\Delta$, whence a code has three essential parameters
$n, k$, and $d$. Thus the unique asymptotic parameter $\lambda$ is an analogue of
the pair of code asymptotic parameters $(\delta, R)$.

An asymptotic by good packing family (i.e., with $\lambda \!<\! \infty$ for \hbox{$N \!\to\! \infty$})
is an analogue of an asymptotically good code family (i.e., with \hbox{$R\cdot \delta >0$}
for $n \to \infty$).

The Gilbert-Varshamov bound corresponds to the Minkowski bound; and the
Hamming bound to the condition $\lambda \geq 0$. It is no clear which is a
reasonable analogue of the Plotkin bound in coding theory (this is an
interesting question). The Kabatyansky-Levenstein bound corresponds to the Mc~Elice-Rodemich-Ramsey-Welch bound.

Packings on a sphere correspond to constant-weight codes.

An interesting question about analogies between concrete code families and
lattice families is mostly open. For instance, parity check codes correspond
either to lattices $A_{N}$, or to $D_{N}$.

The $\theta$-function of a lattice corresponds to the code enumerator; this
analogy is quite useful.\enlargethispage{3\baselineskip}

Unimodular lattices correspond to self-dual codes.

We are interested in analogues of algebraic-geometric codes. Below we shall
describe some of them. These analogies are closely connected to a very deep
analogy between algebraic curves over finite fields and algebraic number
fields.\vspace*{-\baselineskip}

\part{Curves, number fields and packings}

To construct sphere packing starting from curves over finite fields or from
algebraic number fields one should first recall the main notions of these two
domains. That of curves was already recalled in the previous talks, \S 1 is
devoted to algebraic number theory. We also stress the parallelism between
number fields and curves over finite fields.

Then we can give some sphere packing constructions, choosing only those that
look both simple, natural and beautiful. Each of then can be used to produce
many interesting examples of lattice packing. To show that they are really good
we study these packing for $N$ tending to infinity.\vspace*{-\baselineskip}

\section{Algebraic number fields}

A finite extension $k$ of ${\Bbb Q}$ is called an algebraic number field. Its
degree $n=[k:{\Bbb Q}]$ equals the dimension of $k$ as a ${\Bbb Q}$-vector space.

\subsubsection*{Algebraic integers}
If $x\in k$ satisfies the relation
$$
x^{m}+ a_{m-1}\cdot x^{m-1} + \cdots + a_{1}\cdot x + a_{0} =0, \quad a_{i}\in {\Bbb Z}
$$
then $x$ is called an algebraic integer or an integral element of $k$.

\begin{prop*}
The sum and the product of algebraic integers are also
algebraic integers.
\end{prop*}

\begin{cor*}
The subset of integers of $k$ is a ring.
\end{cor*}

This ring $O_{k}$ is called the ring of integers of $k$ or its maximal order.
Any subring $O \subseteq O_{k}$ of finite index $[O_{k} : O]$ is called an
order.

\begin{prop*}
For any $z \in k$ there exists $c\in {\Bbb Z}$ such that $c
\cdot z$ is an algebraic integer.
\end{prop*}

Therefore we have
$$
O_{k} = {\Bbb Z} w_{1} + \cdots + {\Bbb Z} w_{n}
$$
for some basis $\{w_{1},\ldots, w_{n}\}$ of $k$ over ${\Bbb Q}$: such a basis is
called a {\em fundamental basis} of $k$.

\subsubsection*{Trace and norm}
Let now $\Sigma = \{\sigma_{1},\ldots, \sigma_{n}\}$ be the set
of distinct embeddings of $k$ into ${\Bbb C}$. Since for any embedding $\sigma_{i}$ such
that $\sigma_{i}(k)$ does not lie in ${\Bbb R}$ the embedding $\bar\sigma_{i}$ does not
coincide with $\sigma_{i}$, these embeddings are present in the set $\Sigma$ in pairs
$(\sigma_{i}, \bar\sigma_{i})$. Thus if $s$ is the number of embeddings $\sigma_{i} : k
\hto {\Bbb C}$ with $\sigma_{i}(k) \subset {\Bbb R}$ (such embeddings are called
real) and $t$ is the number of pairs $(\sigma_{i}, \bar\sigma_{i})$ where $\sigma_{i} \not=
\bar\sigma_{i}$ (such embeddings are called complex) then $s + 2t =n$.

Let us set
$$
\Tr (x) = \Tr_{k/{\Bbb Q}} (x) =\dpl \sum^{n}_{i=1} \sigma_{i}(x),\quad
N (x) = N_{k/{\Bbb Q}} (x) =\dpl \prod^{n}_{i=1} \sigma_{i} (x).
$$
$\Tr (x)$ is called the $(k/{\Bbb Q})$-{\em trace} of $x$, and $N(x)$ the
$(k/{\Bbb Q})$-{\em norm} of
$x$.

If $a_{m}\cdot x^{m} + \cdots + a_{0}=0$ is the minimal equation of $x$ over
${\Bbb Q}$ then $m|n$, moreover
$$
\Tr (x) = -n a_{m-1}/(m a_{m}) \qqbox{and} N (x) = (-1)^{n}
(a_{0}/a_{m})^{n/m}.
$$
The bilinear form $\Tr (x\cdot y)$ is non-degenerate; $N (x) \in {\Bbb Z}$
if and only if $ x \in O_{k}$.

\subsubsection*{Discriminant}
Let $k$ be an algebraic number field of degree $n$ and let
$\{w_{1},\ldots, w_{n}\}$ be its fundamental basis. The integer
\[
D_{k} =\det (\Tr (w_{i}\cdot w_{j}))
\]
is called the (absolute) {\em discriminant}
of $k$.

It can be checked that this definition does not depend on the choice of
$\{w_{1},\ldots, w_{n}\}$.

\begin{th*}
If $n > 1$, i.e., $k \not= {\Bbb Q}$, then $|D_{k}| >1$.
\end{th*}

One can give another definition of $D_{k}$ which follows. Let $s$ be the number
of real embeddings $\sigma_{i}$ and $t$ be the number of conjugate pairs $(\sigma_{j},
\bar \sigma_{j})$ of complex embeddings of $k$. Let $A = {\Bbb R}^{s}\times {\Bbb C}^{t}$ be
a commutative ${\Bbb R}$-algebra of rank $n = s + 2t$, and let $\sigma$ be the following
ring embedding
\begin{align*}
k &\To{\sigma} {\Bbb R}^{s}\times {\Bbb C}^{t},\\
a &\mto (\sigma_{1}(a),\ldots, \sigma_{s}(a) ; \sigma_{s+1}(a),\ldots,
\sigma_{s+t}(a)).
\end{align*}

The image $\sigma(k)$ generates $A$ (over ${\Bbb R}$); check also that
$\sigma(O_{k})$ is a lattice in $A \simeq {\Bbb R}^{n}$.

The following proposition will be used later.

\begin{prop*}
$
|\det \sigma(O_{k})| = 2^{-t}\cdot \sqrt{|D_{k}|}
$.
\end{prop*}

\begin{proof}
Let $\{w_{1},\ldots w_{n}\}$ be a fundamental basis of $k$, let
$\sigma_{j}(w_{i}) = x_{ji}\in {\Bbb R}$ for any $i, j = 1,\ldots, s$, and let
$\sigma_{s+j} (w_{i}) = y_{ji} + \sqrt{-1} \cdot z_{ji}$ for any $i, j = 1,\ldots
, t$, where $y_{ji}$ and $z_{ji}\in {\Bbb R}$. Then
$$
d = \det \sigma (O_{k}) = \det\left[
\begin{array}{cccccccc}
x_{11}&\cdots& x_{s1}& y_{11}& z_{11}&\cdots & y_{t1}&z_{t1}\\ \\
\vdots& &\vdots&\vdots&\vdots& &\vdots&\vdots\\ \\
x_{1n}&\cdots&x_{sn}&y_{1n}&z_{1n}&\cdots &y_{tn}&z_{tn}
\end{array}
\right]
$$
It is clear that $d = d^{*}/(-2\sqrt{-1})^{t}$, where
$$
d^{*} =\det\left[
\begin{array}{cccccc}
x_{11}&\cdots& x_{s1}& y_{11}+\sqrt{-1}\cdot z_{11}& y_{11}-\sqrt{-1}\cdot z_{11}&\cdots \\ \\
\vdots& &\vdots&\vdots&\vdots& \\ \\
x_{1n}&\cdots&x_{sn}&y_{1n}+\sqrt{-1}\cdot z_{1n}&y_{1n}-\sqrt{-1}\cdot z_{1n} &\cdots
\end{array}
\right]
$$
i.e., $D^{*}= \det (\sigma_{i}(w_{j}))$, where $\{\sigma_{1},\ldots, \sigma_{n}\}$
is the full set of embeddings of $k$ into ${\Bbb C}$. Since by the definition of the
trace
$$
\Tr (w_{i}\cdot w_{j}) = \sum^{n}_{\ell=1} \sigma_{\ell} (w_{i})\cdot \sigma_{\ell} (w_{j})
$$
for $1 \leq i, j \leq n$, one has a matrix equality
$$
(\Tr (w_{i}\cdot w_{j})) = {}^{\rm trans} (\sigma_{\ell}(w_{i}))\cdot (\sigma_{\ell}(w_{j}))
$$
where {\em trans} denotes transposition, whence
$$
D_{k}= \det (\Tr(w_{i}\cdot w_{j})) = (d^{*})^{2}
$$
and we are done.
\end{proof}

\subsubsection*{Units}
An element $a \in O_{k}$ is called a {\em unit} if and only if $a^{-1}\in
O_{k}$. Clearly all the units form a group which is denoted $O_{k}^{*}$.
Torsion elements of $O_{k}^{*}$ are roots of unity.
One easily checks that $a\in O_{k}^\ast$ if and only if $N_{k/{\Bbb Q}}(a) = \pm 1$.

The structure of the group $O_{k}^{*}$ is rather simple, it is described by the
famous Dirichlet theorem:

\begin{th*}
$O_{k}^{*}$ is the product of its finite torsion subgroup by
a free abelian group of rank $r = s + t -1$.
\end{th*}

\subsubsection*{Sketch of proof}
Let us consider the map
\begin{align*}
O_{k}^{*} &\To{\log} {\Bbb R}^{s+t}\\
a &\mto (\log |\sigma_{1}(a)|,\ldots, \log |\sigma_{s}(a)| \; ; \;
\log|\sigma_{s+1}(a)|^{2},\ldots )
\end{align*}
Its kernel is the torsion subgroup of $O_{k}^{*}$, and its image $\log
(O_{k}^{*})$ is contained in the hyperplane $H \subset {\Bbb R}^{s+t}$ defined by
$x_{1} + \cdots + x_{s+t} = 0$. Indeed,
$$
|\sigma_{1}(a)|\cdots |\sigma_{s}(a)|\cdot|\sigma_{s+1}(a)|^{2}\cdots|\sigma_{s+t}(a)|^{2} = |N(a)|=1.
$$

One can show that $\log (O_{k}^{*})$ is a lattice in $H$ (of full rank) which
gives the theorem.

The determinant of this lattice
$$
R = R_{k} = \det\left[
\begin{array}{ccc}
\log|\sigma_{1}(u_{1})|&\cdots&\log |\sigma_{1}(u_{s+t-1})|\\ \\ \vdots&
&\vdots\\ \\
\log|\sigma_{s+t-1}(u_{1})|&\cdots&\log |\sigma_{s+t-1}(u_{s+t-1})|
\end{array}
\right]
$$
where $\{u_{1},\ldots, u_{s+t-1}\}$ is a basis of $O_{k}^{*}$ modulo torsion,
is called the {\em regulator} of $k$.

\subsubsection*{Places}
A map $\|\cdot\| : k \to {\Bbb R}$ is called an {\em absolute value}
if the following conditions hold :
\begin{itemize}
\item
$\|0\| = 0$, $\|x\| > 0$ if $x \not= 0$;
\item
there exist $x, y \in k^{*}$ such that $\|x\| \not= \|y\|$;
\item
$\|x\cdot y\| = \|x\|\cdot \|y\|$;
\item
there exists a positive real $\lambda$ such that $\| x + y\| \leq \lambda \cdot (\|x\| + \|y\|)$.
\end{itemize}

Two absolute values $\|\cdot \|_{1}$ and $\|\cdot \|_{2}$ are {\em equivalent}
if there exists a positive real $\theta$ such that $\|\cdot \|_{1} = \|\cdot
\|_{2}^{\theta}$. An equivalence class of absolute values is called a {\em place}
of $k$.

There is a beautiful description of all places of a number field.

Let $\sigma : k \hto {\Bbb C}$ be an embedding of fields. Let us put
$\|x\|_{\sigma} = |\sigma(x)|$ if $\sigma$ is a real embedding (i.e., ${\rm Im} \sigma \subset
{\Bbb R}$), and $\|x\|_{\sigma} = |\sigma(x)|^{2}$ if $\sigma$ is a complex embedding. These
are absolute values. One can check that two such absolute values
$\|\cdot\|_{\sigma}$ and $\|\cdot\|_{\sigma'}$ are equivalent if and only if either $\sigma' = \sigma$, or
$\sigma' = \bar\sigma$. Thus we obtain $s$ {\em real} and $t$ {\em complex} places of $k$.
These places are called {\em infinite} or {\em archimedean}, the set of
infinite places is denoted by $S_{\infty}$.

Let then ${\got p}$ be a maximal ideal of $O_{k}$. For $x \in k^{*}$ let
$$
{\rm ord}_{{\got p}} (x) = {\rm max} \{n \mid x\in {\got p}^{n}\}.
$$
One easily checks that
$$
{\rm ord}_{{\got p}} (x\cdot y) = {\rm ord}_{{\got p}} (x) + {\rm ord}_{{\got p}} (y)
$$
for any $x, y \in k^{*}$, and if also $x + y\in k^{*}$ then
$$
{\rm ord}_{{\got p}} (x + y)\geq {\rm min} \{{\rm ord}_{{\got p}} (x), {\rm ord}_{{\got p}}
(y)\}.
$$

Let us define the corresponding absolute value: for $x \in k^{*}$ let
$$
\|x\|_{{\got p}} = N({\got p})^{-{\rm ord}_{{\got p}}(x)},
$$
where $N({\got p}) = |O_{k}/{\got p}|$. For such an absolute value (and for any one
equivalent to it) a stronger condition holds:
$$
\|x + y\| \leq \lambda \cdot {\rm max} \{\|x\|, \|y\|\}
$$
(which is wrong for archimedean absolute values). Such absolute values are
called {\em non-archimedean}. If ${\got p} \not= {\got p}'$ then the
corresponding absolute
values are not equivalent, i.e., each maximal ideal (each closed point of $\spec O_{k}$) corresponds to a place of $k$. Such places are called \emph{finite} or {\em non-archimedean}.

It comes out that each place of a number field is either infinite or finite. If
$v$ is a place of $k$ then the absolute values defined above are called \emph{normalized} and denoted $\|\cdot\|_{v}$.

Let us recall that if there are no complex places, the number field is called
{\em totally real}, if there are no real places, it is called {\em totally
complex}.

\subsubsection*{Class group}
Let $\got a$ be an ideal of $O_{k}$, and let $a \in k^{*}$.
The set ${\got c} = a^{-1} {\got a}$ is called a {\em fractional ideal}.
The set of non-zero fractional ideals is a group with the composition defined
by
$$
{\got a}\cdot {\got b} = \{ x\cdot y \mid x\in {\got a}, y \in {\got b}\}.
$$
Note that the inverse element is given by
$$
{\got a}^{-1} = \{x \mid  x^{-1}\in {\got a} - \{0\}\}\cup \{0\}.
$$
We call fractional ideals $\got c$ and $\got c_{1}$ {\em equivalent} if ${\got
c}_{1} = a \got c$ for some $a \in k^{*}$. Equivalence classes of
non-zero
fractional ideals form a group $\Cl_{k}$ which is called the (ideal) \emph{class group} of $k$.

\begin{th*}
The group $\Cl_{k}$ is finite for any algebraic number
field $k$.
\end{th*}

The order of the class group $h = h_{k} = |\Cl_{k}|$ is called the {\em class
number} of $k$.

\subsubsection*{Extensions}
Sometimes it is necessary to consider field extensions $K/k,
K$ and $k$ being algebraic number fields. Let $[K : k] = {\rm dim}_{k} K= n$
and let $O_{K}$ and $O_{k}$ be the rings of integers in $K$ and $k$,
respectively. Any $x\in K$ is a root of an irreducible over $k$ equation of the
form
$$
a_{m}\cdot x^{m} + \cdots + a_{0} = 0
$$
where $a_{i}\in O_k$ for $i = 0,\ldots, m$.

Let us define the ({\em relative}) {\em trace} and {\em norm} as
\begin{align*}
\Tr_{K/k}(x) &= -a_{m-1}/a_{m},\\
N_{K/k}(x) &= (-1)^{m} a_{0}/a_{m}.
\end{align*}

\subsubsection*{Different}
Let us consider the following subset in $k$:
$$
{\got B}_{K/k} = \{x \in K \mid \Tr_{K/k}(x\cdot y) \in O_{k} \mbox{ for any } y\in O_{k}\}.
$$
One can easily check that ${\got B}_{K/k}$ is a $O_{K}$-submodule in $K$ which
contains $O_{K}$. Hence there exist a unique ideal ${\got D}_{K/k}$ in $O_{k}$
such that ${\got D}_{K/k}\cdot {\got B}_{K/k} = O_{K}$. The ideal ${\got
D}_{K/k}$ is called the {\em different} of the extensions $K/k$. The ideal
$$
D_{K/k} = \{N_{K/k}(x) \mid  x\in {\got D}_{K/k}\}
$$
in $O_{k}$ is called the (relative) {\em discriminant} of the extension $K/k$.

The relative discriminant $D_{K/{\QQ}}$ equals the ideal in ${\Bbb Z}$ generated by
the absolute discriminant $D_{k}$. Thus $D_{k}$ is defined by $D_{k/{\Bbb Q}}$ up to
a sign.

Let $L \supset K \supset k$ be algebraic number fields. Then ${\got D}_{L/k} =
{\got D}_{L/k}\cdot {\got D}_{K/k}$.

\begin{prop*}
Let the degree of the extension $L/K$ be equal to $m$. Then
$$
D_{L/k} = D^{m}_{K/k}\cdot N_{K/k} (D_{L/K}).
$$
\end{prop*}

\subsubsection*{Unramified extensions}
An algebraic field extension is called \emph{unramified} if $D_{K/k} = (1)$. We have just seen that ${\Bbb Q}$ has no unramified
extensions.

The rule ${\got a} \mto {\got a}\cdot O_{K}$ defines a group homomorphism
$\Cl_{k}\to \Cl_{K}$; the norm map defines a homomorphism $\Cl_{K}\to
\Cl_{k}$. If an extension $K/k$ is unramified and abelian (i.e., normal with
an abelian Galois group $\Gal(K/k)$) then the (global) class field theory gives

\begin{th*}
$\Gal (K/k)$ is isomorphic to the
factor-group
$\Cl_{k}\!/N_{K/k} (\Cl_{k})$.
\end{th*}

Moreover there exists a maximal unramified abelian extension $K_{1}$ which is
called the {\em Hilbert} or {\em absolute class-field} of $k$; $\Gal(K_{1}/k)$ is isomorphic to $\Cl_{k}$.

\begin{th*}
Let $K_{1}$ be the absolute class field of an algebraic
number field $k$. Then the canonical homomorphism $\Cl_{k}\to \Cl_{K_{1}}$
is trivial, i.e., all the ideals of $O_{k}$ become principal in $O_{K_{1}}$.
\end{th*}

\subsubsection*{Class field towers}
As we have seen above ${\Bbb Q}$ has no unramified
extensions. There exist many algebraic number fields $k$ with $h_{k} > 1$;
for these fields the absolute class field $K_{1}$ is an unramified extension of
degree $h_{K}$. If $h_{k_{1}} > 1$ we get the field $K_{2} = (K_{1})_{1}$ which
is an unramified extension $K_{2}/k$ (note that the extension $K_{2}/k$ cannot
be abelian). Iterating this construction we get either
\begin{enumeratea}
\item
$h_{K_{n}} =1$ for some $n$; hence we cannot obtain a larger
unramified extension of $k$ by our construction; or
\item
$h_{K_{n}} >1$ for any $n$ and hence we obtain an infinite unramified
tower $k \subset K_{1}\subset K_{2}\subset \cdots \subset K_{n}\subset\cdots$.
\end{enumeratea}

An algebraic number field which satisfies the last condition is called a field with an {\em infinite class field tower}.

\begin{th*}
There exists a function $f : {\Bbb N} \to {\Bbb N}$ such that if $k$
is an algebraic number field of degree $n$ and $D_{k}$ has at least $f(n)$
distinct prime divisors then $k$ has an infinite class field tower.
\end{th*}

On can give a precise formula for $f(n)$ but we do not need it here.

The discriminant $D_{k}$ of a field satisfying the conditions of this theorem
cannot be small. One can ask how to construct fields with infinite class field
towers and small discriminants. To compare fields of various degrees one should
use the parameter $|D_{k}|^{1/n}$ (note that it is constant in unramified
towers). Here are the best examples discovered by J. Martinet.

\begin{th*}
The field
$$
k = {\Bbb Q} \left( \cos\Psfrac{2\pi}{11}, \sqrt{-46}\right)
$$
of degree $10$ over ${\Bbb Q}$ has an infinite class field tower;
$$
|D_{k}| = 2^{15}\cdot 11^{8}\cdot 23^{5} \qqbox{and} |D_{k}|^{1/n} \approx
92.37.
$$
The field
$$
k = {\Bbb Q} \left( \sqrt{2}, \sqrt{3\cdot 5\cdot 7\cdot 23\cdot 29}\right)
$$
of degree $4$ has an infinite class field tower of totally real fields;
$$
|D_{k}| = 2^{8}\cdot 3^{2}\cdot 5^{2}\cdot 7^{2}\cdot 23^{2}\cdot 29^{2} \qqbox{and} |D_{k}|^{1/n} \approx 1058.57.
$$
\end{th*}

On the other hand using so-called ``explicit formulas'' one can obtain a lower
bound for $|D_{k}|^{1/n}$:

\begin{th*}let $k_{i}$ be algebraic number fields and let $n_{i} =
[k_{i}:{\Bbb Q}] \to \infty$. Let $s_{i}$ be the number of real embeddings and
$t_{i}$ the number of pairs of complex embeddings of $k_{i}$. Suppose that the
limits $\sigma = \lim s_{i}/n_{i}$ and $\tau = \lim t_{i}/n_{i}$ do exist. Then
$$
\lim \inf |D_{k_{i}}|^{1/n_{i}} \geq (4\pi e^{\gamma+1})^{\sigma} \cdot (4\pi e^{\gamma})^{2\tau},
$$
$\gamma$ being the Euler constant. If the generalized Riemann hypothesis is valid
then
$$
\lim \inf |D_{k_{i}}|^{1/n_{i}} \geq (8\pi e^{\gamma+\pi/2})^{\sigma} \cdot (8\pi
e^{\gamma})^{2\tau}.
$$
\end{th*}

\subsubsection*{Curves and number fields}
Algebraic number fields and fields of rational
functions on curves over finite fields are called {\em global fields}. They
have many features in common. Here we briefly describe some of them.

Let $k$ be an algebraic number field and let $O_{k}$ be its ring of integers.
Let $X$ be a curve over ${\Bbb F}_{q}$, $K = {\Bbb F}_{q}(X)$, let $F$ be a finite set of
closed points of $X$, $U = X - F$, and let $O_{F} = {\Bbb F}_{q}[U]$ be the ring of
rational functions which are regular on $U$.\enlargethispage{\baselineskip}

For both rings $O_{k}$ and $O_{F}$ any factor over a maximal ideal is a finite
field.

For $O_{F}$ all these fields contain ${\Bbb F}_{q}$ (the so-called ``case of equal
characteristics''), in the number field case among these fields there is an
extension of ${\Bbb F}_{p}$ for any prime $p$ (the ``case of different
characteristics'').

The notion of a place is in fact good for any global field. One can show that
any place of $K = {\Bbb F}_{q}(X)$ is finite and corresponds to a closed point of
$X$.

We can choose various finite sets $F$ and get various rings $O_{F}$. In the
number case we can choose a finite set $S$ of maximal ideals of~$O_{k}$ and
consider the ring $O_{S}$ which is obtained from $O_{k}$ by inverting non-zero
elements of ideals from $S$; note that $\spec O_{S} = \spec O_{k}- S$ and $O_{\phi} = O_{k}$. Rings of the form $O_{S}$ or $O_{F}$ can be
characterized as those having one-dimensional irreducible regular spectra of
finite type over~${\Bbb Z}$.

The number field case is mostly more difficult than the function field case.
Indeed, $\spec O_{F}$ can be embedded into a proper scheme~$X$ and $\spec O_{k}$
has no ``good'' embedding into a proper scheme. The last fact makes it
indispensable to study infinite places of $\spec O_{k}$.

The field ${\Bbb F}_{q}(T)$, $T$ being a variable, is an analogue of ${\Bbb Q}$ since $k =
{\Bbb F}_{q}(X)$ (where $X$ is a curve over ${\Bbb F}_{q}$) is a finite extension of
${\Bbb F}_{q} (T)$; the ring ${\Bbb F}_{q} [T]$ is an analogue of ${\Bbb Z}$.
Note however, that there is no canonical embedding of ${\Bbb F}_{q} (T)$ into
${\Bbb F}_{q} (X)$ and hence we cannot say that $[{\Bbb F}_{q} (X):{\Bbb F}_{q} (T)]$ is
an analogue of the degree of an algebraic number field.

One can suggest another analogue of the degree, namely, the number of
${\Bbb F}_{q}$-points of $X$. Indeed, if $|X({\Bbb F}_{q})| = N$, then the degree of a
map $f : X \to {\Bbb P}^{1}$ (i.e., the degree of an extension $[{\Bbb F}(X): {\Bbb F}_{q}(T)]$) can not be too small: $\deg f \geq N/(q+1)$, since
any ${\Bbb F}_{q}$-point of $X$ is mapped to an ${\Bbb F}_{q}$-point of $\PP^{1}$ and any fiber of $f$ contains at most $\deg f$ ${\Bbb
F}_{q}$-rational points.

Let a map $f : X \to {\Bbb P}^{1}$ be fixed, and let us fix an ${\Bbb
F}_{q}$-point $\infty$ on $\Bbb P^{1}$. Then we have ${\Bbb P}^{1} -
\{\infty\} = {\Bbb A}^{1}$, ${\Bbb F}_{q} [{\Bbb A}^{1}] = {\Bbb
F}_{q} [T]$ and we can regard the integral closure of ${\Bbb
F}_{q} [T]$ in ${\Bbb F}_{q} (X)$ as an analogue of $O_{k}$. Note that this
closure coincides with $O_{F_{\infty}} = {\Bbb F}_{q} [X - F_{\infty}]$ where
$F_{\infty} = f^{-1}(\infty)$.

The ramification divisor $B_{f}$ of the map $f$ is an analogue of the
different. The discriminant corresponds to the divisor $D = \sum e_{p} p$
where $e_{p}$ is the ramification index of $P\in {\Bbb P}^{1}$. The value $\log
\sqrt{|D_{k}|}$ is an analogue of the genus of a curve.

A fractional ideal ${\got a} = \prod_{\got p} {\got p}^{n_{\got
p}}$, where $\got p$ runs over prime ideals of~$O_{k}$, corresponds to a
divisor on $X$, ${\got a}^{-1}$ corresponds to $L(D)$ and the group $\Pic X$ is an analogue of $\Cl_{k}$.

Note also that ${\Bbb F}_{q} (T)$ has no unramified extensions (just as $\Bbb Q$).

The value $\lim \inf (g/N)$ is an analogue of $\lim \inf \log|D_{k}|/n$.
The ``explicit formulas'' technique gives estimates for both these values.

The question about an adequate analogue of the number of rational points on the
Jacobian is rather delicate. One can suggest that its ``genuine'' analogue is
the product $h_{k} R_{k}$ rather than $h_{k}$.

Units $O^{*}_{S}$ of the ring $O_{S}$ correspond to units $O^{*}_{F}$ of
$O_{F}$; the group~$\mu_{k}$ is an analogue of $\Bbb F^{*}_{q}$. Moreover,
just as in the number field case, $O^{*}_{F}/{\Bbb F}^{*}_{q}$ is a free
abelian group of rank $|F| - 1$ (note that $O^{*}_{S}/\mu_{k} \simeq {\Bbb
Z}^{s+t+|S|-1}$).

There are some other analogies which are less clear but also useful, and we use
them in the next section.\vspace*{-\baselineskip}

\section{Number field and function field lattices}

We are ready to present several constructions of lattices in the context of
number theory and algebraic geometry and to calculate or estimate their
parameters.

These results are quite recent and their discovery was stimulated by the theory
of algebraic-geometric codes.

\subsubsection*{Additive lattices}
Let $k$ an be algebraic number field, of degree $N = s+ 2t$, let $O_{k}$ be its ring of integers, and let
$$
\sigma : k \hto {\Bbb R}^{s}\times {\Bbb C}^{t}
$$
be the standard embedding. The image $L \!=\! \sigma (O_{k})$ is a lattice of rank~$N$.

\subsubsection*{Parameters}
Let us compute the density of $L$. We have already seen above
that
$$
\det L = 2^{-t} \sqrt{|D_{k}|}.
$$

\begin{prop*}
$$
\sqrt{s+t} \geq d(L) \geq \sqrt{s/2 + t}
$$
and if $t = 0$ then
$$
d (L) = \sqrt{N}.
$$
\end{prop*}

\begin{proof}
Let
$$
x = \sigma (f) = (x_{1},\ldots, x_{s} ; y_{1} + \sqrt{-1} \cdot z_{1},\ldots,
y_{t} + \sqrt{-1}\cdot z_{t}).
$$
We have
$$
|\sigma(f)| = \sqrt{\sum^{s}_{j=1} x^{2}_{j} + \sum^{t}_{j=1} (y^{2}_{j} +
z^{2}_{j})}.
$$
For $f = 1$, $|\sigma(1)| = \sqrt{s + t}$.

The arithmetic mean geometric mean inequality yields
\begin{align*}
\sqrt{\sum^{s}_{j=1} x^{2}_{j} + \sum^{t}_{j=1} (y^{2}_{j} +
z^{2}_{j})} &\geq {1\over \sqrt{2}} \cdot \sqrt{\sum^{s}_{j=1} x^{2}_{j} +
2\cdot \sum^{t}_{j=1} (y^{2}_{j} +
z^{2}_{j})}\\
&\geq \sqrt{s+2t\over 2}\cdot \biggl[ \prod^{s}_{j=1} x^{2}_{j} \cdot
\prod^{t}_{j=1}(y^{2}_{j} + z^{2}_{j})^{2}\biggr]^{1/2N}\\
&= \sqrt{{s\over 2} + t} \cdot |N_{K/{\Bbb Q}} (f)|^{1/N}\\
&\geq\sqrt{{s\over 2}+ t},
\end{align*}
since $N_{K/{\Bbb Q}} (f) \in {\Bbb Z}$. In the totally real case
$$
\sqrt{\sum^{N}_{j=1} x^{2}_{j}} \geq \sqrt{N} \cdot \biggl[ \prod^{N}_{j=1}
x^{2}_{j} \biggr]^{1/2N} = \sqrt{N} \cdot |N_{K/{\Bbb Q}} (f)|^{1/N} \geq
\sqrt{N},
$$
and we get the required result.
\end{proof}

\subsubsection*{Unramified towers}
Now let the field $K$ vary so that $N \to \infty$, and
$K$ is either totally real, or totally complex. Then
$$
\lambda(L) \sim -\log_{2} \sqrt{\pi e\over 2} + {1\over N} \cdot \log_{2}
\sqrt{|D_{K}|}.
$$

If we want to construct good lattices the last term should be bounded. It is
definitely so if $K$ runs over an unramified tower of fields over some $K_{0}$,
in which case it is just constant. We get

\begin{th*}If a number field $K_{0}$ of degree $N_{0}$ has an infinite
unramified tower of fields $K \supset K_{0}$which are either totally real, or totally complex, then it yields an asymptotically good family of lattices
$\{L_{N} \subset {\Bbb R}^{N}\}$ with
$$
\lambda(\{L_{N}\}) \sim - \log_{2} \sqrt{\sfrac{\pi e}{2}} + {1\over N_{0}}\cdot
\log_{2} \sqrt{|D_{K_{0}}|}.
$$
\end{th*}

For $K_{0} = {\Bbb Q} \left( \cos \Psfrac{2\pi}{11}, \sqrt{-46}\right) $ we get $\lambda\sim 2.2218$ (recall that $K_{0}$ has an infinite class field tower).

On the other hand, the above ``explicit formulas'' theorem shows that for any
family of fields $K$ we cannot get asymptotically less than $1.193\cdots$ (and
$1.694\cdots$ assu\-ming the generalized Riemann hypothesis).

\subsubsection*{Multiplicative number field lattices}
Up to this moment we have used the
additive groups of global fields. Now we are going to exploit their
multiplicative structure.

\subsubsection*{Construction}
We start with a number field $K$ of degree $N = s + 2t$ and
a finite number of its places $S = S_{\infty} \cup S_{f}$ which includes all
archimedean ones, let $n = |S|$. Let $O^{*}_{S}$ be the set of $S$-units, i.e., $a \in O^{*}_{S}$ if and only if all the prime divisors of its numerator and denominator
belong to $S_{f}$.

There is a natural map
\begin{align*}
O^{*}_{S} &\To{\varphi_{S}} {\Bbb R}^{n},\\
f &\Mto{\hphantom{\varphi_{S}}} \{\log \|f\|_{v}\},
\end{align*}
where $v \in S$, and $\|\cdot\|_{v}$ is the normalized absolute value, i.e., $\|f\|_{v} = |\sigma_{v}(f)|$ for real places, $\|f\|_{v} = |\sigma_{v}(f)|^{2}$ for
complex ones, and $\|f\|_{v} = N (v)^{-\mathrm{ord}_{v}(f)}$ for $v\in S_{f}$. It is clear that
$$
{\rm Ker} \varphi_{S} = \mu_{K}
$$
is the group of roots of 1 in $K$, and that
$$
\im \varphi_{S}\subset H = \left\{ x\in {\Bbb R}^{n} \Bigm| \sum x_{i} = 0\right\}
$$
because of the product formula.

\subsubsection*{Parameters}
Let $R$ be the regulator of $K$ and let $h = h_{K}$ be its
class number. Set $h(f) = \sum_{v} |\log \|f\|_{v}|$ for $f\in
K^{*}$, this is the {\em height function} (sorry that it is denoted by the same
letter as the class number); $h(f) = 0$ if and only if $f\in \mu_{K}$. We set
$$
h(K) = \mathop{\min}\limits_{f\in K^{*}-\mu_{K}} h (a)
$$
and call it the {\em height of the field} $K$.

\begin{prop*}
Let $L_{S} = \varphi_{S} (O^{*}_{S})$. Then
\begin{align*}
\tag{a}
d(L_{S}) &\geq {1\over \sqrt{n}} \cdot h(K),\\
\tag{b}
\rk L_{S} &= n - 1 \qqbox{and} \det L_{S} \leq \sqrt{n} \cdot R\cdot h\cdot\prod_{v \in S_{f}} \log N (v).
\end{align*}
\end{prop*}

We do not prove it here because the function field case that follows is much
simpler and gives better results.

\subsubsection*{Asymptotic behaviour}
To obtain asymptotically good families of lattices
we are going to consider unramified towers of fields. In such towers ${1\over
N}\cdot \log \sqrt{|D_{K}|}$ is constant. Let us for simplicity assume that all
the fields in the tower are totally real.

\begin{th*}
If a number field $K_{0}$ of degree $n_{0}$ has an infinite
unramified tower of totally real fields then the above construction with $S =S_{\infty}$ yields a family of asymptotically good multiplicative lattices
$\{L_{N} = L_{S}\subset {\Bbb R}^{N}\}$ with $N \to \infty$ and
$$
\lambda(\{L_{N}\}) \leq -\log_{2} \sqrt{\pi^{3} e/2} -\log_{2}\log_{e}
\left[ \psfrac{1+\sqrt{5}}{2}\right] + {1\over n_{0}}\cdot \log_{2}|D_{K_{0}}|.
$$
\end{th*}

For $K_{0} = {\Bbb Q} \left( \sqrt{2}, \sqrt{3\cdot 5\cdot 7\cdot 23\cdot 29}\right) $ we get $\lambda \lesssim 8.41$.

\subsubsection*{Function field lattices}
Here is a direct function field analogue of the
previous construction.

\subsubsection*{Construction}
Let\vspace*{-3pt}
$$
O^{*}_{\cP} = \{ f \in K^{*} | \supp (f) \subseteq \cP\}.
$$

Recall that $\cP\subseteq X ({\Bbb F}_{q})$ for a curve $X$ over ${\Bbb F}_{q}$
and $K = {\Bbb F}_{q}(X)$. Let $\Div_{\cP} (X)$ denote the group of
divisors supported in $\cP$, $\Div^{0} (X)$ of those of degree $0,
P_{\cP}(X)$ the subgroup of principal divisors. Let $J_{X} = {\rm
Div}^{0}(X)/P(X)$ be the Jacobian of $X$.

There is a natural map\vspace*{-3pt}
\begin{align*}
O^{*}_{\cP} &\To{\varphi_{\cP}} \Div_{\cP} (X) \simeq {\Bbb Z}^{n},\\
f &\mto (f).
\end{align*}
It is clear that $\ker \varphi_{\cP} = {\Bbb F}^{*}_{q}$ is again the group of
roots of 1 in $K$, and that\vspace*{-3pt}
$$
\im \varphi_{\cP} \subseteq \Div^{0}_{\cP} (X) \simeq A_{n-1} = \left\{ x\in
{\Bbb Z}^{n} \bigm| \sum x_{i} = 0\right\}.
$$
We set\vspace*{-3pt}
$$
L_{\cP} = \varphi_{\cP}(O^{*}_{\cP}) \subseteq A_{n-1} \otimes {\Bbb R} \simeq {\Bbb
R}^{n-1}.
$$

\subsubsection*{Parameters}
Let us estimate the parameters of $L_{\cP}$.

\begin{th*}
Let $L_{\cP} = \varphi_{\cP}(O^{*}_{\cP})$. Then\vspace*{-3pt}
\begin{align*}
\tag{a}d (L_{\cP}) \geq \min_{f\in O^{*}_{\cP} - {\Bbb F}_{q}^{*}} \sqrt{2\cdot \deg f} \geq \sqrt{2\cdot |X({\Bbb F}_{q})|\over q+1},\\
\tag{b}\rk L_{\cP} = n-1 \qbox{and}\\
\det L_{\cP} \leq \sqrt{n} \cdot |J_{X}({\Bbb F}_{q}) | \leq \sqrt{n} \cdot
\left[ 1 + q + {|X({\Bbb F}_{q}) | - q - 1\over g}\right]^{g}.
\end{align*}
\end{th*}

\skpt
\begin{proof}
\begin{enumeratea}
\item
Let $f \in O^{*}_{\cP}$, $f \not\in {\Bbb F}^{*}_{q}$,\vspace*{-3pt}
$$
\varphi_{\cP} (f) = (x_{1},\ldots, x_{n}) \in {\Bbb Z}^{n}.
$$
Then\vspace*{-3pt}
$$
|\varphi_{\cP}(f)| = \sqrt{\sum x_{i}^{2}} \geq \sqrt{\sum |x_{i}|} = \sqrt{2\cdot\deg f},
$$
since $x_{i}\in {\Bbb Z}$, $\sum x_{i}=0$, $\deg f = \sum_{x_{i}>0} x_{i}$. Any $f\in K$ maps ${\Bbb F}_{q}$-points to ${\Bbb F}_{q}$-points of
${\Bbb P}^{1}$. Therefore
$$
|X ({\Bbb F}_{q})| \leq (q + 1) \cdot \deg f
$$
and we get the second inequality.

\item
We know that $\det A_{n-1} = \sqrt{n}$ and
$$
\det L_{\cP} = [A_{n-1} : L_{\cP}]\cdot \det A_{n-1}.
$$
Then
$$
A_{n-1} \simeq \Div^{0}_{\cP} (X) \subset \Div^{0}(X),
$$
and
$$
L_{\cP} \simeq P_{\cP} (X) = P(X) \cap \Div^{0}_{\cP} (X).
$$
Therefore
$$
[A_{n-1} : L_{\cP}] \leq [\Div^{0} (X) : P(X)] = |J_{X}({\Bbb
F}_{q})|.
$$

To prove the second inequality it is sufficient to establish the following
bound for the number of points on the Jacobian:
$$
|J_{X}({\Bbb F}_{q})| \leq \left[ 1 + q + {|X({\Bbb F}_{q}) |-q-q\over
g}\right]^{g}.
$$

Indeed, $|J_{X}({\Bbb F}_{q})| = \prod\limits^{2g}_{i=1}(1 - \omega_{i})$,
$\omega_{i}$ being the Frobenius roots, $|\omega_{i}| = \sqrt{q}$, $\omega_{g+i} =\bar\omega_{i}$. The arithmetic mean geometric mean inequality yields
$$
\prod^{2g}_{i=1} (1 - \omega_{i})= \prod^{g}_{i=1} (q + 1 - \omega_{i} - \bar\omega_{i})\leq
 \biggl[ \dpl{\sum^{g}_{i=1} (q + 1 - \omega_{i} - \bar\omega_{i})\over g} \biggr]^{g},
$$
and the estimate for $|J_{X} ({\Bbb F}_{q})|$ follows from
\[
-\sum^{g}_{i=1} (\omega_{i} + \bar\omega_{i}) = |X({\Bbb F}_{q})| -q -1.\qedhere
\]
\end{enumeratea}
\end{proof}

\subsubsection*{Asymptotic behaviour}
We consider families of curves of growing genus with
$$
{|X({\Bbb F}_{q})|\over g} \to A,
$$
and set $\cP = X({\Bbb F}_{q})$. We get

\begin{th*}
A family of curves $X$ over ${\Bbb F}_{q}$ of growing genus
$g$ such that
$$
{|X({\Bbb F}_{q})|\over g} \to A > 0
$$
yields an asymptotically good family of lattices $\{L_{N} \subset {\Bbb
R}^{N}\}$ with
$$
\lambda(\{L_{N}\}) \leq - \log_{2} \sqrt{\pi e} + \log_{2}\sqrt{q + 1} +
A^{-1} \log_{2} (1 + q + A).
$$
\end{th*}

We are again interested to take the largest possible $A$. Let $q = p^{2m}$,
then we can consider curves with $A = \sqrt{q} -1$. For such curves we can in
fact do better than for an arbitrary family.

\begin{prop*}
For a family of curves $X$ over ${\Bbb F}_{q}$ with
$$
{|X({\Bbb F}_{q})|\over g}\to \sqrt{q} - 1
$$
there is an asymptotic equality
$$
{1\over g}\cdot \log_{2}|J_{X}({\Bbb F}_{q})| \sim \log_{2} q + (\sqrt{q} -1)
\cdot \log_{2} \left( \spfrac{q}{q-1}\right).
$$
\end{prop*}

Using this result we get

\begin{th*}
A family of curves $X$ over ${\Bbb F}_{q}$ of growing genus $g$ such that
$$
{|X({\Bbb F}_{q})|\over g}\to \sqrt{q} - 1
$$
yields an asymptotically good family of lattices $\{L_{N} \subset {\Bbb
R}^{N}\}$ with
$$
\lambda(\{L_{N}\}) \leq - \log_{2} \sqrt{\pi e} + \log_{2} {\sqrt{q +1}\over q -1} + {\sqrt{q}\over \sqrt{q}-1} \cdot \log_{2} q.
$$
\end{th*}

For $q = 9$ we get $\lambda \lesssim 1.8687\cdots$.

\subsubsection*{Congruence constructions}
Now we shall discuss some constructions depending on a divisor.

\subsubsection*{Multiplicative congruence sublattices}
The construction of multiplicative
lattices can be slightly elaborated. We consider some specific sublattices of
$L_{\cP}$.
Let $D$ be a positive divisor on $X$, $D = \sum a_{i} P_{i}$, $r_{i} = \deg
P_{i}$, $N (P_{i}) = q^{r_{i}}$,
$$
a = \deg D = \sum a_{i} r_{i}.
$$

We write $ f \equiv 1 \mod D$ if ${\rm ord}_{P_{i}} (f - 1) \geq
a_{i}$ for any $P_{i}\in \supp D$. Suppose that $\cP \cap \supp D
= \emptyset$. Let
$$
O^{*}_{\cP, D} = \{f \in O^{*}_{\cP} \mid  f \equiv 1 \mod D\},
$$
and consider the lattice $L_{\cP, D} = \varphi_{\cP} (O^{*}_{\cP, D}) \subseteq
L_{\cP}$.

\subsubsection*{Parameters}
Here are the estimates.

\begin{prop*}
Let $L_{\cP, D} = \varphi_{\cP} (O^{*}_{\cP, D})$. Then
\begin{enumeratea}
\item
$d (L_{\cP, D}) \geq \sqrt{2a}$,
\item
$\rk L_{\cP, D} = n-1$ and
$$
\det L_{\cP, D} \leq \sqrt{n} \cdot |J_{X}({\Bbb F}_{q}) | \cdot {q^{a}\over q
- 1}\cdot \prod\left( 1 - q^{-r_{i}}\right).
$$
\end{enumeratea}
\end{prop*}

\skpt
\begin{proof}
\begin{enumeratea}
\item
As above we have\enlargethispage{\baselineskip}
$$
d (L_{\cP, D}) \geq \min_{f \in O^{*}_{\cP, D^{-\{1\}}}} \sqrt{2\cdot \deg f},
$$
and we notice that $\deg f = \deg (f - 1) \geq \deg D = a$.

\item
We have already estimated $\det L_{\cP}$, and we only need to
estimate $[L_{\cP} : L_{\cP, D}]$. Look at the embedding $O^{*}_{\cP}
\hto \prod \hat O^{*}_{P_{i}}$ is the group of units in the completion
of the local ring at $P_{i}$. Let
$$
\hat O^{*}_{P_{i}, a_{i}} = \{ x \in \hat O^{*}_{P_{i}} \mid x \equiv 1 \mod a_{i} P_{i}\}.
$$
We have $O^{*}_{\cP, D} = O^{*}_{\cP} \cap (\prod \hat O^{*}_{P_{i}, a_{i}})$ and
$$
[O^{*}_{\cP} : O^{*}_{\cP, D}] \leq \left[ \prod \hat O^{*}_{P_{i}} : \prod \hat O^{*}_{P_{i}, a_{i}}\right]
= \prod \left[ \left( q^{r_{i}} - 1\right)^{r_{i} (a_{i}-1)}\right].
$$
Then $\ker\varphi_{\cP} = {\Bbb F}_{q}^{*}$ and $0^{*}_{\cP, D} \cap \ker\varphi_{\cP} = \{1\}$, therefore
\[
[O^{*}_{\cP} : O^{*}_{\cP, D}] = (q - 1)\cdot [L_{\cP} : L_{\cP, D}].\qedhere
\]
\end{enumeratea}
\end{proof}

\subsubsection*{Asymptotic behaviour}
Consider the same family of curves as above, let
$\cP = X ({\Bbb F}_{q})$ and let $D$ be such that
$$
\lim {\deg D\over |X ({\Bbb F}_{q})|} = (2\cdot \log_{e} q)^{-1}
$$
(this choice appears to be optimal). We get

\begin{th*}
A family of curves $X$ over ${\Bbb F}_{q}$ of growing genus $g$ such that
$$
{|X ({\Bbb F}_{q})|\over g} \to \sqrt{q} - 1
$$
with the appropriate choice of divisors yields an asymptotically good family of
lattices $\{L_{N} \subset {\Bbb R}^{N}\}$ with
$$
\lambda(\{L_{N}\}) \leq - \log_{2} \sqrt{\pi\over 2} + {1\over 2}\cdot \log_{2}
(\log_{e}q) + {\sqrt{q}\over \sqrt{q} - 1} \cdot \log_{2} q - \log_{2} (q - 1).
$$
\end{th*}

For $q = 2209 = 47^{2}$ we get $\lambda \lesssim 1.3888\cdots$.

\subsubsection*{Number field case}
We can now return to number fields and give a parallel
theory, which is as usual more difficult.

For the totally complex field ${\Bbb Q} ( \cos \Psfrac{2\pi}{11}, \sqrt{-46})$ and
$S_{0} = S_{\infty}$ we get $\lambda \lesssim11.1512\dots$ For the totally real
field ${\Bbb Q} (\sqrt{2}, \sqrt{3{\cdot} 5{\cdot} 7{\cdot} 23{\cdot} 29})$ and $S_{0}
= S_{\infty}$ we get $\lambda \lesssim 8.80$. These are not best choices but what we
get is always much worse than for the function field case.

\subsubsection*{Another approach}
Algebraic curves can also be used to
construct lattices indirectly, that is we construct lattices using algebraic
geometric codes. The construction is less elegant and we come to families of lattices with $\lambda \lesssim 2.30\cdots$ and families of non-lattice packings with $\lambda \lesssim 1.31\cdots$.

\backmatter
\addtocontents{toc}{\protect \lsectionpart}
\nocite{*}
\bibliographystyle{jepplain+eid}
\bibliography{xups93-02}
\end{document}

