\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{color}
%%%%%%%%%%%%%%% MACROS specific to this PSET %%%%%%%%%%%%%%%%%%%%%%
\newcommand{\lat}{\mathcal{L}}
\newcommand{\basis}{\mathbf{B}}
\newcommand{\vol}{\mathsf{vol}}
\newcommand{\sh}{\lambda_1}
%\newcommand{\det}{\mathsf{det}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
%%%%%%%%% Vectors and Matrices
\newcommand{\vecv}{\mathbf{v}}
\newcommand{\vecb}{\mathbf{b}}
\newcommand{\matB}{\mathbf{B}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\input{pset-preamble.tex}
\lecture{1}{Vinod Vaikuntanathan}{September 13, 2011}{October 3, 2011}
\subsection*{Notes}
\begin{itemize}
\item This problem set is worth $100$ points.
\item Collaboration is allowed, {\em but you must write up the solutions by yourself without consulting to notes from the discussions}. You must also reference your sources.
\item Grading is based on correctness as well as the clarity of the solutions. When writing proofs, it is generally a good idea to first explain the intuition behind your solution in words (wherever appropriate), before jumping in to the formalisms.
\item {\em Notation:} $\N$ denotes the natural numbers, $\Z$ denotes the integers, $\Q$ denotes rational numbers and $\R$ the set of real numbers.
\end{itemize}
\subsection*{Problem $1$: Fun with Lattice Bases (25 points)}
Consider the basis
\[ \matB = \left( \begin{array}{cc} 123 & 1 \\ 6764 & 55 \end{array} \right) \]
\begin{itemize}
\item (5 points) Which of the following vectors belong to the lattice $\lat(\basis)$?
\[ \vecv_1 = \left( \begin{array}{c} 129 \\ 143 \end{array} \right) \hspace{0.3in}
\vecv_2 = \left( \begin{array}{c} 1/2 \\ 10 \end{array} \right) \hspace{0.3in}
\vecv_1 = \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \]
Briefly justify your answers. (A simple yes/no does not suffice).
\item (5 points) What is the determinant of $\lat(\basis)$?
\item (5 points) Find the Gram-Schmidt orthogonalization of $\basis$. Show your calculations.
\item (5 points) Find a shortest vector in $\lat(\basis)$ (note that there may be many).
\item (5 points) Find a shortest basis of $\lat(\basis)$ (note that there may be many).
\end{itemize}
\subsection*{Problem $2$: More Bases and Determinants (25 points)}
\begin{itemize}
\item (15 points) Prove that for every $n \in \mathbb{N}$, there is a unique full-rank integer lattice $\lat = \lat(\basis) \subseteq \mathbb{Z}^n$
with determinant $1$. [{\em Hint: Show that $\lat(\basis) = \Z^n$.}]
\item (10 points) For any full-rank integer lattice $\lat = \lat(\basis) \subseteq \Z^n$, show that the vector $(\det(\lat),0,0,\ldots,0)^T$ is in the lattice.
\end{itemize}
\subsection*{Problem $3$: Minkowski's Convex Body Theorem (25 points)}
Let $\lat$ be a lattice. Recall that Minkowski's Convex Body Theorem states that
any {\em convex}, {\em centrally symmetric} $n$-dimensional body $S$ with
$\vol(S) > 2^n \det(\lat)$ contains a {\em non-zero} lattice point.
Show that all the three conditions -- convexity, central symmetry and the lower-bound
on the volume -- are necessary for this theorem to be true. Namely, for the lattice
$\lat = \Z^n$, show:
\begin{itemize}
\item (10 points) a convex set $S_1$ with $\vol(S_1) > 2^n \cdot \det(\lat)$ that does not
contain a lattice point. Note that $S_1$ has to be necessarily {\em centrally asymmetric.}
\item (10 points) a centrally symmetric set $S_2$ with $\vol(S_2) > 2^n \cdot \det(\lat)$
that does not contain a lattice point. Note that $S_2$ has to be necessarily {\em non-convex}.
\item (5 points) a convex, centrally symmetric set $S_3$ with $\vol(S_3) = 2^n \cdot \det(\lat)$
that does not contain a non-zero lattice point.
\end{itemize}
The elegance of your solution counts.
\subsection*{Problem $4$: Minkowski's First Theorem (25 points)}
\begin{itemize}
\item (20 points)
Find the analog of Minkowski's first theorem for the $\ell_1$ and $\ell_{\infty}$ norms.
\medskip \noindent
[{\em Hint: Which part of the proof of Minkowski's first theorem is specific to the $\ell_2$ norm?}]
\item (5 points) Show a lattice in $n$ dimensions for which the shortest vector is much {\em smaller} than what Minkowski's theorem predicts. In particular,
show an $n$-dimensional (full-rank) lattice $\lat$ with determinant $1$ such that \[ \sh(\lat) < 10^{-100} \]
\end{itemize}
\vspace{0.4in}
\subsection*{Extra Credit**}
Despite lattices with much shorter vectors than predicted, Minkowski's theorem is tight for general lattices. In particular, there is a family of lattices $\{\lat_n\}_{n\in \mathbb{N}}$ where $\lat_n$ lives in $n$ dimensions, and
\[ \textcolor{red}{\sh(\lat_n) \geq c\cdot \sqrt{n}\cdot \det(\lat_n)^{1/n}}\]
%{\mbox{\textcolor{red}{$1/n$}}} \]
where $c$ is a universal constant independent of $n$.
Show that such a family of lattices exists (your proof doesn't have to construct this family, you merely have to show existence).
\end{document}