\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
\usepackage{psfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\lecture{11}{October 19, 2005}{Madhu Sudan}{Kyomin Jung}
Today, we will give a definition of lattice in $\mathbb{R}^n$ and
study its two specifications, by primal basis and dual basis. Then
we will focus on the problem of finding shortest vectors in a given
lattice. For this problem, we will present the Gauss algorithm that
finds exact solution for the 2 dimensional case, and LLL(Lenstra,
Lenstra, Lovasz,'82) algorithm that finds a $2^{n}$ approximation
solution in polynomial time of $n$ for the $n$ dimensional case.
\section{Motivation}
Think of the following problem. Given $G(x)\in \mathbb{Z}[x]$,
$d,N\in \mathbb{N}$ and $c>0$,\\
Find $g=\sum_{i=0}^d g_i x^i\in \mathbb{Z}[x], H(x)\in \mathbb{Z}[x]$ such that\\
$$g(x)=G(x)\cdot H(x) \ \ (\rm{mod} \ N)$$
where $(\rm{mod} \ N)$ means modulo for each coefficients, and
$|g_i|\le c$ for each $0\le i\le d$.
This can be expressed as a system of linear equations,
$$\forall \ 0\le i\le d, \ \ g_i=\sum_{j}G_j H_{i-j} +q_i N$$
where $q_i\in \mathbb{Z}$. We can obtain non-zero integer solutions
for $g_i$'s, $H_i$'s and $q_i$'s by solving above linear equations.
But, how can we obtain a solution that satisfies $|g_i|\le c$?
Naturally this problem induces the concept of lattice and the
problem of finding a solution with small non-zero norm.
\section{Lattice and its basis}
First we give a definition of a lattice in $\mathbb{R}^n$.
\begin{definition}
$\L\in \mathbb{R}^n$ is a lattice if it satisfies
1) $x,y\in \L \ \rightarrow\ x+y\in \L $ and $-x\in \L$.
2) $\L$ is a discrete set in $\mathbb{R}^n$.
\end{definition}
Where a set $A\in \mathbb{R}^n$ is called a discrete set if there
exist $\delta>0$ s.t. $\forall x\in A, \ \ Ball(x,\delta)\cap
A=\{x\}.$
\begin{definition}
For a given finite set $M\in \mathbb{R}^n$, we define
$$L_M=\{\sum_{i}c_i m_i | c_i\in \mathbb{Z} , m_i\in M\}.$$
If a lattice $L$ is equal to $L_M$ for some $M$, we say that $M$ is
a (primal) basis of $L$, and $L$ is generated by
$M$.\end{definition}
Note that for any $M\in \mathbb{R}^n$, $L_M$ is closed under
addition and subtraction, but it is not always discrete. A
sufficient condition for $L_M$ to be discrete, hence $L_M$ to be a
lattice, is, $M$ is finite and $M\in \mathbb{Q}^n$. Now we will show
that essentially this is a necessary condition too.
First, we show that any lattice $L$ in $\mathbb{R}^n$ have a finite
basis. Let $k=\rm{rank}(L)$ as a subset of $\mathbb{R}^n$. Let
$\{b_1, b_2,\ldots b_k\}\subset L$ be a linearly independent subset
of $L$. Then there are finitely many points of $L$ that is in the
$k$-dimensional parallelogram formed by $b_1, b_2,\ldots b_k$,
because $L$ is discrete. These points together with $b_i$'s form a
finite basis of $L$.
By similar argument, one can show that if $L$ is a lattice in
$\mathbb{R}^n$, there exist an invertible linear transform
$T:\mathbb{R}^n\rightarrow \mathbb{R}^n$ so that $T$ sends $L$ into
$\mathbb{Q}^n$, and $T$ is ``almost'' distance preserving. So from
now on we will assume that $L\in \mathbb{Q}^n$ and it has a finite
basis.\\
Now we show that given $L\in \mathbb{Q}^n$ with a finite basis
$\{b_1, b_2,\ldots b_m\}$, we can find a basis of $L$ whose size is
equal to the rank of $L$ in time polynomial of $n$. We may assume
that $b_i\in \mathbb{Z}^n$ by multiplying lcm of denominators of
$b_i$. Note that replacing $b_i$ with $b_i+\sum_{j=1, j \ne i}^m c_j
b_j$ $,c_j\in \mathbb{Z}$ gives another basis for $L$.
So, given a basis
$$\left(
\begin{array}{cccc}
| & | & \ldots & | \\
b_1 & b_2 & \ldots & b_m \\
| & | & \ldots & | \\
\end{array}
\right),$$
we can obtain a new basis of the form
$$\left(
\begin{array}{cccc}
g_1 & 0 & \ldots & 0 \\
| & | & \ldots & | \\
b^{(1)}_1 & b^{(1)}_2 & \ldots & b^{(1)}_m \\
| & | & \ldots & | \\
\end{array}
\right)$$
where $g_1$ is the gcd of $b_{1i}'s$. Similarly, we can obtain a
basis of the form
$$\left(
\begin{array}{ccccc}
g_1 & 0 & 0 &\ldots & 0 \\
| & g_2 & 0 &\ldots & 0 \\
| & | & g_3 &\ldots & 0 \\
\ldots & \ldots & \ldots &\ldots & 0 \\
| & | & | & \ldots g_j\ldots & 0 \\
b^{(j)}_1 & b^{(j)}_2 & b^{(j)}_3 &\ldots b^{(j)}_j\ldots & b^{(j)}_m\\
| & | & | & \ldots |\ldots & | \\
\end{array}
\right)$$
where $g_j$ is the gcd of $b^{(j-1)}_{ji}$'s, $j\le i\le m$. In this
way we can find a basis whose size is $k=\rm{rank}(L)\le n$ in
poly($n$) time.
\section{Dual specification of a lattice}
Given $M^*=\{b^*_1, b^*_2,\ldots b^*_k\} \in \mathbb{Q}^n$, define
$$L^*_{M^*}=\{v\in Q^n\ |\ \forall j\in
\{1,2,\ldots k\}, \in Z\}.$$
If a lattice $L\in \mathbb{Q}^n$ is equal to $L^*_{M^*}$, we say
that $M^*$ is a dual basis of $L$. Note that if rank$(M^*)}{|b_i|^2}$. So it can be done in polynomial time.
The $\frac{3}{4}$ factor in step 2 guarantees that LLL algorithm
goes back to step 1 at most polynomially many times over $n$, so the
algorithm runs in polynomial time over $n$. In the next lecture we
will prove that its output gives a $2^{n}$ factor approximation to a
shortest vector.
\section{References}
\begin{enumerate}
\item A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz, Factoring Polynomials with Rational Coefficients,
Math. Ann. 261, 1982.
\item Subhash Khot, Hardness of approximating the shortest vector problem in lattices,
in Proc. 45th Symposium on Foundations of Computer Science, 2004.
\item D. Micciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant,
in Proc. 39th Symposium on Foundations of Computer Science 1998.
\item M. Ajtai, The shortest vector problem in l 2 is NP-hard for randomized reductions,
In Proceedings of the thirtieth annual ACM symposium on theory of
computing, 1998.
\end{enumerate}
\end{document}