\documentclass[12pt]{article}
\usepackage{amsfonts, amsthm, amsmath}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0pt}
\setlength{\parindent}{20pt}

\def\CC{\mathbb{C}}
\def\FF{\mathbb{F}}
\def\NN{\mathbb{N}}
\def\PP{\mathbb{P}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\gotha{\mathfrak{a}}
\def\gothm{\mathfrak{m}}
\def\gotho{\mathfrak{o}}
\DeclareMathOperator{\Disc}{Disc}
\DeclareMathOperator{\Trace}{Trace}
\DeclareMathOperator{\Norm}{Norm}
\def\bv{\vec{v}}
\def\bw{\vec{w}}

\def\head#1{\medskip \noindent \textbf{#1}.}
\def\fixme#1{\textbf{FIXME! #1}}
\DeclareMathOperator{\Vol}{Vol}

\begin{document}

\begin{center}
\bf
Math 254A, UC Berkeley, Fall 2001 (Kedlaya) \\
Problem Set 3: Lattices\\
Due in class Monday, September 17
\end{center}

\head{References} Neukirch, Sections 1.4 and 1.5. For LLL (and in general
if you're interested in algorithms in number theory) see Cohen's
\emph{A Course in Computational Algebraic Number Theory}, especially
Chapter~2. 
For more on lattices
in general, the magnum opus is \emph{Sphere Packings, Lattices and Groups}
by Conway and Sloane.

Please submit any \emph{seven} of the following problems.

\head{Lattices}

\begin{enumerate}
\item Neukirch I.4.1 (modified): Show that a $\ZZ$-submodule $\Gamma$
of $\RR^n$
is a (complete) lattice if and only if $\Gamma$ is discrete and $\RR^n/\Gamma$
is compact.
\item Let $a,b,c \in \ZZ$ be nonzero, pairwise
coprime integers
not all of the same sign. Suppose that the equation $ax^2+by^2 + cz^2 \equiv 0
\pmod{2|abc|}$ has a solution with $\gcd(x,y,z,2abc) = 1$.
Show that there exists
a subgroup $L$ of $\ZZ^3$ of index $2|abc|$ such that for every
$(x,y,z) \in L$, $ax^2+by^2+cz^2 \equiv 0 \pmod{2|abc|}$.
\item (Hasse-Minkowski theorem)
In the notation of the previous problem,
make $\ZZ^3$ into a lattice under the norm $|(x,y,z)| = 
|a|x^2+|b|y^2+|c|z^2$. Prove that there is a nonzero element $(x,y,z)$ of $L$
satisfying $|x|\leq \sqrt{|bc|}$, $|y| \leq \sqrt{|ca|}$,
$|z| \leq \sqrt{|ab|}$, and that in fact this triple is a nonzero
solution of $ax^2+by^2+cz^2 = 0$.
\end{enumerate}

\head{The Minkowski space of a number field}

\begin{enumerate}
\item 
Neukirch I.5.2: Show that the convex, centrally symmetric set
\[
X_t = \{ (z_\tau) \in K_{\RR} | \sum_{\tau} |z_{\tau}| < t \}
\]
has volume $\Vol(X_t) = 2^r \pi^s \frac{t^n}{n!}$,
where $r$ and $2s$ are the numbers of real and complex embeddings.
\item
Neukirch I.5.3: Show that in every ideal $\gotha \neq 0$ of $\gotho_K$
there exists an $a \neq 0$ such that
\[
|\Norm(a)| \leq M [\gotho_K:\gotha],
\]
where $M = \frac{n!}{n^n} \left( \frac{4}{\pi} \right)^s \sqrt{|\Disc(K)|}$.
\item
Let $K$ be a number field such that $|\Disc(K)| = 1$. Prove that $K = \QQ$.
(Hint: use the previous exercise.)
\end{enumerate}

\head{Interlude: The LLL algorithm}
In this section, we describe a constructive version of Minkowski's lattice
point theorem, due to Lenstra, Lenstra and Lov\'asz (LLL). This result
gives a weaker bound than Minkowski's theorem, but yields a highly
practical algorithm for finding short vectors in a lattice.

Let $\bv_1, \dots, \bv_n$ be a basis of the lattice $L$. Let $\bw_1,
\dots, \bw_n$ be the Gram-Schmidt orthogonalization of this basis; namely,
$\bw_1 = \bv_1$ and
\[
\bw_{i} = \bv_i - \sum_{j=1}^{i-1} \frac{\bv_i \cdot \bw_j}{\bw_j \cdot \bw_j}
\bw_j.
\]
(Note that the $\bw_i$ will not necessarily lie in $L$ itself, only in the
real vector space $L \otimes_{\ZZ} \RR$.)
Put $\mu_{i,j} = (\bv_i \cdot \bw_j)/(\bw_j \cdot \bw_j)$
for $1 \leq j < i \leq n$.
We say the basis is \emph{LLL-reduced} if
\begin{equation}
|\mu_{i,j}| \leq \frac{1}{2} \qquad 1 \leq j < i \leq n
\end{equation}
and
\begin{equation} \label{lovasz}
|\bw_i + \mu_{i,i-1} \bw_{i-1}|^2 \leq \frac{3}{4} |\bw_{i-1}|^2
\end{equation}
for $i=2, \dots, n$.

\begin{enumerate}
\item 
Let $\bv_1, \dots, \bv_n$ be an LLL-reduced basis of the lattice $L$.
Prove that
\begin{gather*}
\Vol(L) \leq \prod_{i=1}^n |\bv_i| \leq 2^{n(n-1)/4} \Vol(L) \\
|\bv_j| \leq 2^{(i-1)/2} |\bw_i| \qquad 1 \leq j < i \leq n \\
|\bv_1| \leq 2^{(n-1)/4} \Vol(V)^{1/n}.
\end{gather*}
\item
Let $\bv_1, \dots, \bv_n$ be an arbitrary basis of the lattice $L$,
and set $k=2$.
Show that the following algorithm necessarily terminates, and that
the resulting basis is LLL-reduced.
\begin{enumerate}
\item[(a)] For $i=2, \dots, n$, replace $\bv_i$ by itself plus a
suitable
linear combination of $\bv_1, \dots, \bv_{i-1}$ so that
$|\mu_{i,j}| \leq 1/2$ for $j < i$.
\item[(b)] If (\ref{lovasz}) holds for $i=2, \dots, n$, stop. Otherwise,
choose the smallest $i$ for which (\ref{lovasz}) fails, then switch
$\bv_{i-1}$ and $\bv_i$ and go back to (a).
\end{enumerate}
(Hint: consider how the quantity $\prod_{i=1}^n |\bw_i|^{n-i}$ changes.)
\item
Write a Magma program to convert an arbitrary basis of a lattice into
an LLL-reduced basis. Your program should also call the built-in Magma
function to perform LLL reduction and compare answers.
\item
Suppose you are given an LLL-reduced basis
$\bv_1, \bv_2, \bv_3$ of a rank 3 lattice. Give an algorithm for finding the
shortest nonzero vector in the lattice. (Hint: you can write down a finite
list of linear combinations of basis vectors such that the shortest vector
must appear in this list.)
\end{enumerate}

\end{document}