%% HOW TO USE THIS TEMPLATE:
%%
%% Ensure that you replace "YOUR NAME HERE" with your own name, in the
%% \studentname command below. Also ensure that the "answers" option
%% appears within the square brackets of the \documentclass command,
%% otherwise latex will suppress your solutions when compiling.
%%
%% Type your solution to each problem part within
%% the \begin{solution} \end{solution} environment immediately
%% following it. Use any of the macros or notation from the
%% head.tex that you need, or use your own (but try to stay
%% consistent with the notation used in the problem).
%%
%% If you have problems compiling this file, you may lack the
%% head.tex file (available on the course web page), or your system
%% may lack some LaTeX packages. The "exam" package (required) is
%% available at:
%%
%% http://mirror.ctan.org/macros/latex/contrib/exam/exam.cls
%%
%% Other packages can be found at ctan.org, or you may just comment
%% them out (only the exam and ams* packages are absolutely required).
% the "answers" option causes the solutions to be printed
\documentclass[11pt,addpoints]{exam}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{mathtools}
% any of the following packages may be safely omitted if they are not
% available on your system (but they should be)
\usepackage{fullpage}
\usepackage{times}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
\hypersetup{%
colorlinks=true,% hyperlinks will be colored
}
% required macros -- get head.tex file from course web page
\input{head}
% VARIABLES
\newcommand{\hwnum}{1}
\newcommand{\duedate}{September 23} % changing this does not change the
% actual due date :)
\newcommand{\studentname}{YOUR NAME HERE}
% END OF SUPPLIED VARIABLES
\hwheader % execute homework commands
\begin{document}
\pagestyle{head} % put header on every page
\noindent This homework is due by the \textbf{start of class on
\duedate} via the
\href{}{course
Canvas page}. Start early!
\medskip
\noindent \textbf{Instructions.} Solutions must be typeset in \LaTeX\
(a template for this homework is available on the course web page).
Your work will be graded on \emph{correctness} and \emph{clarity}.
You should only submit work that you believe to be correct; if you
cannot solve a problem completely, you will get significantly more
partial credit if you clearly identify the gap(s) in your solution.
It is good practice to start any long solution with an informal (but
accurate) ``proof summary'' that describes the main idea.
\medskip
\noindent You may collaborate with others on this problem set and
consult external sources. However, you must \textbf{\emph{write your
own solutions}} and \textbf{\emph{list your
collaborators and/or sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
\begin{questions}
\question A set of vectors $\matB = \set{\vecb_{1}, \vecb_{2},
\ldots, \vecb_{m}} \subset \R^{n}$ is called a \emph{generating
set} of a lattice $\lat$ if every $\vecv \in \lat$ can be
expressed as an integer linear combination of vectors in $\matB$.
(This differs from the notion of \emph{basis} in that the
representation need not be unique, so the vectors $\vecb_{i}$ need
not be linearly independent.)
Describe an efficient algorithm that, given a generating set $B =
\set{b_{1}, \ldots, b_{m}} \subset \Z$ of a one-dimensional lattice
$\lat \subset \Z$, outputs a shortest nonzero element of $\lat$.
Make sure the algorithm runs in time polynomial in the \emph{bit
length} of the input set $B$.
\begin{solution}
\end{solution}
\question Construct a basis $\matB$ of a lattice $\lat$ for which
both inequalities $\min_{i} \length{\gs{\vecb}_{i}} \leq
\lambda_{1}(\lat)$ and $\lambda_{1}(\lat) \leq \sqrt{n}
\det(\lat)^{1/n}$ are very loose, by large multiplicative factors.
Do so in the smallest dimension $n$ you can.
\begin{solution}
\end{solution}
\question \emph{Fundamental regions.}
\begin{parts}
\part Prove the following: let $\mathcal{F}$ be any fundamental
region of a lattice $\lat$. Then for any lattice coset $\vecx +
\lat$, the intersection $(\vecx + \lat) \cap \mathcal{F}$ consists
of a single point. (This point is called the ``distinguished
representative'' of the coset in the region $\mathcal{F}$.)
Also prove that given any element of a coset $\vecx+\lat$, finding
its distinguished representative is equivalent to finding the
unique $\vecv \in \lat$ such that $\vecx \in \vecv + \mathcal{F}$.
\begin{solution}
\end{solution}
\part We showed in class that $\piped(\matB) = \matB \cdot
[-\tfrac12, \tfrac12)^{n}$ is a fundamental region of $\lat =
\lat(\matB)$. Describe an efficient algorithm (and prove it
correct) that, given $\matB$ and an arbitrary point $\vecx \in
\R^{n}$ specifying a coset $\vecx+\lat$, outputs the distinguished
representative of the coset in $\piped(\matB)$.
\begin{solution}
\end{solution}
\part Let $\gs{\matB}$ denote the Gram-Schmidt orthogonalization
of $\matB$. Prove that $\piped(\gs{\matB}) = \gs{\matB} \cdot
[-\tfrac12,\tfrac12)^{n}$ is a fundamental region of $\lat =
\lat(\matB)$. Also, describe an efficient algorithm (and prove it
correct) that, given $\matB$ and an arbitrary point $\vecx \in
\R^{n}$ specifying a coset $\vecx+\lat$, outputs the distinguished
representative of the coset in $\piped(\gs{\matB})$.
(\emph{Hint}: for intuition, it may help to find solutions for
two-dimensional lattices first.)
\begin{solution}
\end{solution}
\end{parts}
\question Minkowski's theorem says that $\lambda_{1}(\lat) \leq
\sqrt{n} \cdot \det(\lat)^{1/n}$, where $\lambda_{1}(\lat)$ denotes
the minimum distance in the standard \emph{Euclidean} norm
$\length{\vecx} = \sqrt{\sum_{i} x_{i}^{2}}$, which is also known as
the $\ell_{2}$ norm.
Consider now the $\ell_{p}$ norm for $1 \leq p \leq \infty$, defined
as $\length{\vecx}_{p} = \parens*{\sum_{i} \abs{x_{i}}^{p}}^{1/p}$
and $\length{\vecx}_{\infty} = \max_{i} \abs{x_{i}}$.
Let~$\lambda_{1}^{(p)}$ denote the minimum distance of a lattice in
the $\ell_{p}$ norm. Generalize Minkowski's theorem and proof to
give as tight of an upper bound on $\lambda_{1}^{(p)}$ as you can.
\begin{solution}
\end{solution}
\newcommand{\vor}{\mathcal{V}}
\question Define the \emph{Voronoi cell} $\vor(\lat)$ of a lattice
$\lat$ as the (open) set of all points that are closer to the origin
than to any other lattice point. Formally,
\[ \vor(\lat) = \set{ \vecx \in \R^{n} : \length{\vecx} <
\length{\vecx - \vecv} \text{ for all } \vecv \in \lat \setminus
\set{\veczero}}. \]
Prove that the Voronoi cell is ``essentially'' a fundamental region
of $\lat$, in that its translates by lattice points are pairwise
disjoint, and cover all of $\R^{n}$ except for some rare
``exceptional'' points. Describe these exceptional points, and for
any non-exceptional point, describe which translate
$\vecv + \vor(\lat)$ it lies in.
\emph{Extra credit:} show how to modify $\vor(\lat)$ to make it
``half-open'' (analogously to how we've defined the fundamental
parallelepiped of a lattice), and prove that the modified body is a
true fundamental region.
\begin{solution}
\end{solution}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: