\documentclass{toc}

\tocdetails{%
   volume=4, number=2, year=2008, firstpage=21,
     received={November 15, 2006},
        published={May 10, 2008}
}

\runningauthor{Mikl{\'o}s Ajtai}
\runningtitle{Optimal bounds for lattice parameters and Schnorr's algorithm}
%% for the shortest vector problem}
   
\copyrightauthor{Mikl\'{o}s Ajtai}

\bibliographystyle{tocplain}

\newtheorem{cond}{}
\renewcommand{\thecond}{\rm(\arabic{cond})}
\newcommand{\semmi}[1]{{}}

\newcommand\eee{\mathrm e}  %%%%%%% LB added
\newcommand\rrr{\mathbb R}

\newcommand\rand{{\tt rand}}
\newcommand\norm{{\tt norm}}
\newcommand\vl{\texttt{vl}}
\newcommand\domain{\textrm{domain}}
\newcommand\ext{{\tt ext}}
\newcommand\calq{{\cal Q}}
\newcommand\cala{{\cal A}}
\newcommand\calb{{\cal B}}
\newcommand\cald{{\cal D}}
\newcommand\calh{{\cal H}}
\newcommand\cali{{\cal I}}
\newcommand\calu{{\cal U}}
\newcommand\calm{{\cal M}}
\newcommand\caln{{\cal N}}
\newcommand\calv{{\cal V}}
\newcommand\calg{{\cal G}}
\newcommand\calc{{\cal C}}
\newcommand\calk{{\cal K}}
\newcommand\calp{{\cal P}}
\newcommand\calr{{\cal R}}
\newcommand\cals{{\cal S}}
\newcommand\calf{{\cal F}}
\newcommand\call{{\cal L}}
\newcommand\calt{{\cal T}}
\newcommand\boldk{{\bf K}}
\newcommand\boldr{{\bf R}}
\newcommand\boldb{{\bf b}}
\newcommand\lege{{\lfloor\!\lfloor}}
\newcommand\rege{{\rfloor\!\rfloor}}
\newcommand{\enp}[1]{End proof #1}

\newcommand\err{{\mathbb R}}    %%%%%%% **** LB redefined **** %%%%%%
\renewcommand\phi{\varphi}
\renewcommand\epsilon{\varepsilon}
\renewcommand\theta{\vartheta}
\newcommand\nev[1]{}
\newcommand\huhu{{\tau}}
\newcommand\vege{\end{document}}
\newcommand\start{{\tt start}}

\begin{document}

\begin{frontmatter}[classification=float]

\title{Optimal lower bounds for the Korkine-Zolotareff parameters
   of a lattice and for Schnorr's algorithm for the\\ shortest
   vector problem \footnote{A preliminary version of
this paper has appeared in the Proc.
 35th ACM Symp. on Theory of
Computing~\cite{Ajtai}.}}

\author[miklos]{Mikl\'os Ajtai}

\begin{abstract} Schnorr's algorithm for finding an approximation for
the shortest nonzero vector in an $n$-dimensional lattice depends on a
parameter $k$.  He proved that for a fixed $k \leq n$ his algorithm (block
$2k$-reduction) provides a lattice vector whose length is greater than
the length of a shortest nonzero vector in the lattice by at most a
factor of                 
$(2k)^{2n/k}$.  
(The time required by the algorithm
depends on $k$.)  We show that if $k=o(n)$, this bound on the
performance of Schnorr's algorithm cannot be improved (apart from a
constant factor in the exponent).  Namely, we prove the existence of a
basis in $\err^n$ which is KZ-reduced on all $k$-segments and where the
ratio $\| b_1 \| / {\tt shortest}(L)$ is at least $k^{cn/k}$.  Noting
that such a basis renders all versions of Schnorr's algorithm idle (output =
input), it follows that the quantity $k^{cn/k}$ is a lower bound on
the
approximation ratio any version of Schnorr's algorithm can achieve on
the shortest vector problem.  This proves that Schnorr's analysis of the
approximation ratio of his algorithm is optimal apart from the constant
in the exponent.  We also solve an open problem formulated by Schnorr
about the Korkine-Zolotareff lattice constants $\alpha_{k}$.  We show
that his upper bound $\alpha_{k}\le k^{1+\ln k}$ is the best possible
apart from a constant factor in the exponent.  We prove a similar result
about his upper bound $\beta_{k}\le 4k^{2}$, where $\beta_{k}$ is
another lattice constant with an important role in Schnorr's analysis of
his algorithm.
\end{abstract}

\tockeywords{Approximation algorithm, lattice, shortest vector problem, 
geometry of numbers, basis reduction, LLL reduction, Schnorr's algorithm, 
Korkine-Zolotarev basis, random lattice}
\tocams{68Q25, 68W40, 68W25, 11H55, 11H99, 52C07, 60D05}
\tocacm{F.2.2, G.2}
\end{frontmatter}

\section{Introduction}

\subsection{Historical background, related results}

 One of the most
important tasks of the algorithmic theory
of lattices is to find a short nonzero
vector in a given lattice.  Although there
is no known polynomial time algorithm which
finds a shortest nonzero vector in an
$n$-dimensional lattice, Lov\'asz's
algorithm also known as LLL reduction
published in a paper of A.~Lenstra,
H.~Lenstra, L.~Lov\'asz~\cite{LLL}, finds a
vector which is longer than the shortest
vector by a factor of at most $2^{n-1/
2}$.  In this algorithm we repeatedly have
to find short bases in two-dimensional
lattices.  The two-dimensional problem was
already solved by Gauss~\cite{Gauss},
 (see also Lagrange~\cite{Lagrange}).
 In 1987 C.~P.~Schnorr gave an algorithm which is a
generalization of the LLL reduction (see~\cite{Schnorr}).  
In this algorithm we have
to find short bases in $2k$-dimensional
lattices.  If we want a polynomial time
algorithm then we may use the maximal $k$
where a short basis can be found in
polynomial time.  Schnorr has proved that
if $k$ is fixed then the approximation
factor in his algorithm is at most
$(2k)^{2n/k}$.   
        \nev{102}

We will prove that Schnorr's upper bound about his algorithm cannot be
improved apart from a constant factor in the exponent. The proof is
based on the construction of a lattice $L$  and a basis
$b_{1}, \ldots, b_{n}$ in it, with the
property that Schnorr's algorithm, given $b_{1}, \ldots, b_{n}$ as an input,
immediately terminates and gives $b_{1}$ as an approximation of the
shortest nonzero vector of $L$. For a more detailed formulation of
this result we need the following two (well-known) definitions.

\begin{definition}\hfill
\begin{enumerate}
\item
Let $b_{1},\ldots  ,b_{n}$ be a basis of the
lattice $L$.  Applying the Gram-Schmidt
orthogonalization to this basis we get a
sequence of vectors
$b_{1}^{*},\ldots  ,b_{n}^{*}$ with the property
that $b_{i}^{*}$, $i=1,2,\ldots  ,n$ are
pairwise orthogonal, $b_{1}=b_{1}^{*}$ and
for all $i=1,\ldots  ,n$ we have
$b_{i}^{*}=b_{i}-\sum_{j=1}^{i-1}
\mu_{i,j}b_{j}^{*}$
where $\mu_{i,j}= (b_{i}\cdot
b_{j}^{*}) \Vert b_{j}^{*} \Vert^{-2}
$.
If $P_{i}$ is the projection of the
$n$-dimensional space onto the subspace
orthogonal to $b_{1},\ldots  ,b_{i-1}$ then
$b_{i}^{*}=P_{i}b_{i}$.  We call the basis
$b_{1},\ldots  ,b_{n}$ size-reduced if
$|\mu_{i,j}|\le {1/ 2}$ for all $1\le
j<i\le n$.  It is important for us that
given an arbitrary basis $b_{1},\ldots  ,b_{n}$
it is easy to construct a size-reduced
basis $d_{1},\ldots  ,d_{n}$ so that
$b_{i}^{*}=d_{i}^{*}$ for $i=1,\ldots  ,n$.
\nev{118}

\item Let $b_{1},\ldots  ,b_{n}$ be a basis of the
$n$-dimensional lattice $L$.  For each
$i=1,\ldots  ,n$ let $P_{i}$ be the orthogonal
projection of the $n$-dimensional space
onto the subspace orthogonal to the vectors
$b_{1},\ldots  ,b_{i-1}$.  Let $b_{i}^{*}= P_{i}
b_{i}$. $b_{1},\ldots  ,b_{n}$ is a
Korkine-Zolotareff basis (or a
Korkine-Zolotareff reduced basis, see~\cite{KZ}) if it is
size-reduced, and $b_{i}^{*}$ is a shortest
nonzero vector in the lattice $P_{i}L$, for
all $i=1,\ldots  ,n$. \nev{5080}
\end{enumerate}
\end{definition}

We show that (apart from a constant factor
in the exponent) the mentioned upper bound, about the performance of
Schnorr's algorithm, cannot be improved. Namely there is an
$\epsilon'>0$ so that for every $k\le \epsilon' n$ there
exists a lattice and size reduced basis, $b_{1},\ldots  ,b_{n}$  in it so
that,
for every $i=1,\ldots  ,n-k+1$, the vectors $P_{i}b_{i},\ldots  ,P_{i}b_{i+k-1}$
form a Korkine-Zolotareff basis in the subspace generated by them.
 Consequently, Schnorr's algorithm is inactive on
$b_{1},\ldots  ,b_{n}$
and so the short vector produced by the algorithm is $b_{1}$. However
the construction will show that the ratio of $\| b_{1} \|
/\lambda_{1}(L)
$, where $\lambda_{1}(L)$ is the length of the shortest nonzero vector
in $L$, is
at least $k^{c n/k}$. So starting from this basis the output of
Schnorr's algorithm is not better
than the proven upper bound (apart from the mentioned  constant factor).
   R.~Kannan~\cite{Kannan1} constructed a lattice with
these properties for LLL reduction, that
is, for the $k=2$ case.  His construction
is explicit while our present construction
for an arbitrary $k$ is probabilistic.
Still we keep several important properties
of Kannan's example.  Although we give a
tight lower bound on the approximation
provided by Schnorr's algorithm, still two
questions remain open.  (1) What is the
largest $k$ where a short basis, in the
sense of Schnorr's algorithm, can be found
in time polynomial in $n$?  (2) It is
possible that if the same lattice is
presented with another basis then Schnorr's
algorithm gives a better result.  (The
largest $k$ for which there is a known
polynomial time deterministic algorithms is
$k=O(\log n/\log \log n)$ given by
R.~Kannan in~\cite{Kannan}, and for
probabilistic algorithms it is $k=O(\log
n)$ given by M.~Ajtai, R.~Kumar, and
D.~Sivakumar in~\cite{ARS}.  
Therefore the approximation factor in deterministic
polynomial time version of Schnorr's algorithm is
$\exp\left({O((\log \log n)^{2}(\log n)^{-1}n)}\right)$
while in the probabilistic version it is
$\exp\left({O((\log\log n)(\log n)^{-1}n)}\right)$.) \nev{103}

In a recent paper~\cite{Schnorr1}, Schnorr
describes a practical algorithm for finding
short vectors in lattices which in practice
outperforms the known algorithms (there is
no proven upper bound guaranteeing the good
performance).  There are concepts about
lattice bases which play a role in 
both~\cite{Schnorr1} and the present paper.  The
two papers complement each other in the
sense that one shows the positive the other
the negative effect of a basis with random
behavior on the performance of algorithms.
                \nev{105}

%%\subsection{\label{S1}The statements of the main results}
\subsection{\label{S1}The main results}

Our proof about the worst-case performance
of Schnorr's algorithm is based on
the following random construction of a 
$k$-dimensional lattice $L=L_{k,{c}}$.

\begin{definition}
Assume the random
variables $\mu_{i,j}$, $1\le j\le i-2 \le k-2$ 
are independent and 
uniformly distributed over
the interval $(-{1/ 2}, {1/2})$.  We define a lower
triangular $k\times k$ matrix
$$
A^{(k,{c})}=(A_{i,j})_{i=1,\ldots
,k,j=1,\ldots  ,k}\,.
$$
The definition of the entries is the following.
\begin{align*}
&A_{i,i} = k^{-{c} i/k}, && \text{for $i=1,\ldots,k$},\\
&A_{i,i-1} = \frac{1}{2} A_{i-1,i-1} = \frac{1}{2}k^{-{c} (i-1)/k}, && 
\text{for $i=2,\ldots  ,k$, and}\\
&A_{i,j} = \mu_{i,j}A_{j,j}, && \text{if $1\le j\le
i-2 \le k-2$}\,.
\end{align*}
This implies that the $i$th row
of the matrix $(A_{i,j})$ is of the
following form: \nev{5000} \vskip 10pt
\centerline{ $ \mu_{i,1}k^{-{c} /k}  \
\ \ \ldots  \ \ \ \mu_{i,i-2}
k^{-{c} (i-2)/k}
 \ \ \ \frac{1}{2}k^{-{c} (i-1)/k}\ \ \ k^{-{c} i/k}\
\ \ 0\ \ \ldots  \ \ 0 $}

\vskip 10 pt \noindent
$L_{k,{c}}$ will denote the lattice in
$\err^{k}$ generated by the rows of
$A^{(k,{c})}$.
 \nev{5005}
\end{definition}

The following theorem describes the
properties of the lattice $L_{k,{c}}$
which will be crucial in our proof about
the worst-case behavior of Schnorr's
algorithm. \nev{5006}

\begin{theorem} \label{T0} For all
sufficiently small ${c}>0$  there is an
$\alpha>0$  so that for all sufficiently
large positive integers $k$ with a
probability of at least $1-\eee^{-\alpha k}$
we have the following.
Let $a_{i}$ be the $i$th row of the matrix
$A^{(k,{c})}$. Then $a_{1},\ldots  ,a_{k}$ is a
Korkine-Zolotareff reduced basis of the
lattice $L_{k,c}$. In particular the first
row of this matrix  is a  nonzero
shortest vector
   of the lattice,
with length $A_{1,1}=k^{-{c}/ k}$.
Moreover for all $i=2,\ldots  ,k$, if $P_{i}$ is
the projection
of $\err^{k}$ to the subspace orthogonal to
$a_{1},\ldots  ,a_{i-1}$ then in the 
$(k-i)$-dimensional lattice $P_{i}L_{k,c}$, the
vector $P_{i}a_{i}$ is a nonzero shortest
vector with length
$A_{i,i}=k^{-{c} i/k}$.
   \nev{5007}

\end{theorem}

The theorem implies that if we apply the
Gram-Schmidt orthogonalization to the
basis $a_{1},\ldots  ,a_{k}$ of $L_{k,{c}}$
then we get a basis $a_{i}^{*}$  (of
$\err^{k}$)  with
$a_{i}^{*}=k^{-ci/k}e_{i}$, where
$e_{i}$ is the $i$th unit vector.

We will use the lattice $L_{k,{c}}$ in
the way described below. We will construct
(at random) an
$n$-dimensional lattice given with a basis
$b_{1},\ldots  ,b_{n}$, so that for every
segment
$b_{s},\ldots  ,b_{s+k-1}$ of this basis, if we
take the orthogonal projections of the
vectors
$b_{s},\ldots  ,b_{s+k-1}$ to the subspace
generated by $b_{1},\ldots  ,b_{s+k-1}$, then
the resulting sequence
$b_{s}',\ldots  ,b_{s+k-1}'$
    is like the basis
$a_{1},\ldots  ,a_{k}$  from \expref{Theorem}{T0}
multiplied by a constant factor. This and
the described properties of the basis
$a_{1},\ldots  ,a_{k}$  will make it possible to
show that Schnorr's  algorithm is inactive
on the basis  $b_{1},\ldots  ,b_{n}$. (The
length of a shortest nonzero vector in the
lattice generated by $b_{1},\ldots  ,b_{n}$ will
be estimated through Minkowski's convex
body theorem.)      \nev{5002}


The  basis $b_{1},\ldots  ,b_{n}$  has a very
concise definition similar to the
definition of the lattice $L_{k,c}$
(although for the proofs
we will
reformulate it into a longer but more
natural definition.)  Our construction will
depend on a constant $c>0$ and we show that
if $c$ is sufficiently small then the
constructed lattice and basis meet our
requirements.  Assume now that a constant
$c>0$ is fixed.  The $i$th unit vector in $\err^{n}$
will be denoted by $e_{i}$.       
\nev{106}                         

\begin{definition}
Let $n,k$, $k\le n$ be
positive integers and let $c>0$ be a real
number and let $f_{i}= k^{c(n-i+1)/k}e_{i} $ 
for $i=1,\ldots  ,n$.  Suppose
further that
$\mu_{i,j}$, $i=1,\ldots  ,n$, $j=1,\ldots  ,i-2$ are
mutually independent random variables,
uniformly distributed over 
the interval $({-{1 / 2}},{1 / 2})$.  Let
$b_{1}=f_{1}$ and for all $i=2,\ldots  ,n$ let
$b_{i}=f_{i}+({1 / 2})f_{i-1}+\sum_{j=1}^{i-2}{\mu_{i,j}}f_{j}$.
It is easy to see that the vectors
$b_{1},\ldots  ,b_{n}$ are linearly independent.
Let $\Lambda(n,k,c)$ be the lattice
generated by $b_{1},\ldots  ,b_{n}$.  The basis
$(b_{1},\ldots  ,b_{n})$ will be denoted by
$B(n,k,c)$.  If the values of $n,k,c$ are
fixed then $\Lambda(n,k,c)$ and $B(n,k,c)$
are random variables.
\nev{107}
\end{definition}

Clearly this definition implies that the
$n\times n$ matrix whose rows are
$f_{1},\ldots  ,f_{n}$ is  lower triangular,
and its $i$th row is \vskip 10pt
$$
\mu_{i,1}
k^{c{n/ k}}   
 \ldots \    \mu_{i,i-2} k^{c(n-(i-2)+1)/k)}
  \  \  \
\frac{1}{2}k^{c(n-(i-1)+1)/k}
  \  \  \
k^{c(n-i+1)/k}
  \
    0  \ldots   0
 $$


\vskip 10pt
\noindent
As a consequence
$\Lambda_{n,k,c}=k^{c(n+1)/k}L_{n,c}$
and we get the basis $b_{1},\ldots  ,b_{n}$  of
$\Lambda_{n,k,c}$ by multiplying the rows
of the matrix $A^{(n,c)}$ by
$k^{c(n+1)/k}$. \nev{5008}



\begin{theorem} \label{T1} For all sufficiently small
$c>0$, there exists $\epsilon'>0$ so that if
 $n$ is a sufficiently
large integer, and $k$ is an integer with
$k\le \epsilon' n$ then the
following holds.  Assume that $L,$
$(b_{1},\ldots  ,b_{n})$ are the
corresponding random values of the random
variables $\Lambda(n,k,c)$, $B(n,k,c)$.
Then with a positive probability
the following conditions are satisfied.

\begin{cond} \label{TC1}
$\Vert
b_{1}\Vert=\exp\left({c\frac{n}{k}\log k}\right) $,
$\lambda_{1}(L)\le 2n^{1/2} \exp\left({c\frac{n+1}{2k}\log k}\right)$, 
and so
$$
\Vert
b_{1}\Vert/\lambda_{1}(L)\ge   \frac{1}{2}
n^{-{1/2}}k^{c(n-1)/(2k)}\ge
k^{{c}{n/(3k)}}\,,
$$
   \end{cond}

\begin{cond} \label{TC2} for all $i=1,\ldots  ,n-2k+1$,
the vectors
$P_{i}b_{i},\ldots  ,P_{i}b_{i+2k-1}$ form a
Korkine-Zolotareff basis of
the lattice generated by them. \nev{109}
 \end{cond}

\end{theorem}

\begin{corollary} \label{CC1}
The quantity  $k^{cn/(3k)}$ is a lower bound on the
approximation
ratio any version of Schnorr's algorithm can achieve on the shortest
vector
problem, hence Schnorr's upper bound on the approximation ratio of his
algorithm is optimal apart from the value of the constant in the
exponent.
   \end{corollary}


\begin{proof}
Take a basis satisfying the properties guaranteed in \expref{Theorem}{T1}. 
Then all versions of Schnorr's algorithm are idle on this basis 
(they do not change the basis). Therefore the algorithm's guess at
the shortest vector is $b_1$, which is a factor of $k^{cn/(3k)}$ longer 
than the shortest vector in the lattice by \expref{Theorem}{T1}.
\end{proof}


\begin{remark}\hfill
\begin{enumerate}
\item The theorem does not
provide a lower bound on the ``positive probability''
so it does not give a way to construct a
lattice and a basis with the properties
described in the theorem. We will see,
however, from the proof that for all
$c_{1}>0$ there is a $c_{2}>0$ so that
if $k\ge c_{2} \log
n$ then $L$  and $(b_{1},\ldots  ,b_{n})$  
meet the requirements of the theorem with a
probability $p\ge
1-n^{-c_{1}}$. For smaller values of $k$,
$p$  can be exponentially small, so in this
case the theorem does not give a
construction. We will see that even in
this case there is a probabilistic
construction for $L$ and $(b_{1},\ldots ,b_{n})$  
with the required properties. \nev{5009}
\item The theorem holds, \eg, with any
$\epsilon'<
{c /10}$ (this is not the best upper
bound on $\epsilon'$), and the final
inequality
$n^{-{1/ 2}}k^{c(n-1)/(2k)}\ge
({1/2})k^{cn/(4k)}$
follows from this inequality.
However if
$\epsilon'$  is much larger than $c$, then
the final inequality does not hold since
the factor
$n^{-{1/ 2}}$  will dominate and so we
will have $(1 / 2) n^{-{1/ 2} }
k^{c(n-1)/(2k)}
<1 $.
\end{enumerate}
\end{remark}

In this paper we also solve an open problem
asked by Schnorr about the geometry of
lattices, which is related to the analysis
of his algorithm.

\begin{definition}
 For all positive integers $k$, the
Korkine-Zolotareff
constant is $\alpha_{k} =\sup \Vert
b_{1}\Vert ^{2}/\Vert b_{k}^{*}\Vert^{2} $,
where the supremum is taken over all            
$k$-dimensional lattices $L$ and over all       
Korkine-Zolotareff bases $b_{1},\ldots  ,b_{k}$
in $L$.
\end{definition}

 Schnorr proves that
$\alpha_{k}\le
k^{1+\log k}$ and asks whether
$\alpha_{k}=k^{O(1)}$.
We show that actually his upper bound is optimal up to a
constant factor in the exponent. Namely we prove the following.

\begin{theorem} \label{A3.1} There is an $\epsilon>0$ so that the
value of the Korkine-Zolotareff constant $\alpha_{k}$ is at least
$k^{\epsilon \log k}$ for all $k=1,2,\ldots  $ \nev{795} \end{theorem}

We will prove this result in \expref{Section}{S2}. It will be an immediate
consequence of \expref{Theorem}{A3}. 
We note that the proof of \expref{Theorem}{T1} and 
\expref{Theorem}{A3.1} are both based on  random lattice
constructions. The two random constructions are similar but not
identical. In
fact, the construction used in the proof of \expref{Theorem}{A3.1} requires
sharper estimates and so that proof involves more
work.


  Another lattice constant
$\beta_{k}$ is even more important for the
determination of the approximation factor
provided by Schnorr's algorithm.
$\beta_{k}$ defined as
\[
\beta_{k}=
 \sup \left\lbrace \Bigl(\bigl(\prod_{i=1}^{k}\Vert
b_{i}^{*} \Vert^{2}\bigr) \bigl(\prod_{i=k+1}^{2k}
\Vert b_{i}^{*}\Vert \bigr)^{-2}\Bigr)^{{1/ k}}
\right\rbrace
\]
where the supremum is taken over  
all $2k$-dimensional lattices $L$ and over
all Korkine-Zolotareff bases
$b_{1},\ldots  ,b_{2k}$ of $L$.  Schnorr gives
the upper bound $\beta_{k}\le 4k^{2}$ and
uses it in the analysis of his algorithm.
We show that this upper bound is tight
apart from a constant in the exponent, that
is, there is an $\epsilon>0$ so that
$\beta_{k}\ge k^{\epsilon}$ for all
$k=1,2,\ldots  $. \nev{110}

To prove the lower bound on $\beta_{k}$ we
will use the random lattice
$L=\Lambda(2k,2k,c)$ with a sufficiently
small $c>0$ and show that with a high
probability the basis $B(2k,2k,c)$ is a
Korkine-Zolotareff basis in $L$. (Since
$\Lambda(k,k,c)=k^{c(k+1)/k}L_{k,c}$,
\expref{Theorem}{T0} implies this statement
with $2k$ in the place of $k$.)          
For
the lower bound on $\alpha_{k}$ we use a
modified form of the random lattice
$\Lambda(k,k,c)$, namely we will have
$\Vert f_{i}\Vert =\exp\left({-c(\log (k-i+1))^{2}}\right)$ 
for $i=1,\ldots  ,k-c_{1}$, and $\Vert f_{i}
\Vert = \exp\left({-c(\log c_{1})^{2}}\right)$ for
$i=k-c_{1}+1,\ldots  ,k$, where $c_{1}$ is an
integer sufficiently large with respect to
$c$ (but it does not depend on $k$).
Otherwise the definition remains unchanged
and we prove that with high
probability $B(k,k,c)$ is a
Korkine-Zolotareff basis for the modified
$B$.

\subsection{Motivation} The main
motivation for
this work is that Schnorr's algorithm gives
the best proven approximation of the
shortest nonzero vector in an
$n$-dimensional lattice.  So it is
important to know how good is its
performance.  
Moreover, no algorithm is known
outside the framework of LLL and Schnorr's algorithm 
which gives comparable results.  
%
Therefore a lower
bound on the algorithm shows the hardness
of the approximate shortest vector problem
at least according to our present
knowledge.  This limit on our knowledge
seems to be serious since the approximation
factor of Schnorr's algorithm has not been
improved since its publication in 1987,
apart from the increase of the largest $k$
that can be used in poly-time
(see~\cite{ARS}),
but this did not affect the overall
structure of the $n$-dimensional algorithm.
Another possible use of the lattices
constructed in this work is that we may try
to find a better algorithm for finding an
approximation of the shortest nonzero
vector in a lattice by attacking this
problem in the case of the counterexamples. 
Our probabilistically
constructed lattices may be very good from
this point of view because there seems to
be no easy way to find a shorter vector in
them than the one produced by Schnorr's
algorithm.  Motivated by this we formulate
an open problem.  In this open problem we
present a specific random lattice
($\Lambda(n,k,c)$ for some choice of $k$
and $c$) with the shortest known nonzero
vector in it (which is $b_{1}$) and ask for
a polynomial time algorithm which finds a
nonzero vector shorter (or much shorter)
than $b_{1}$.  We may expect that a
solution for this problem will contain some
new idea about lattice algorithms, while it
seems easier to attack the approximate
shortest vector problem in a specific
lattice than in its generality.  On the
other hand if no solution for this problem
will be found for a long time then the
lattice (which may also be generated
together with a known short vector) may be
useful for cryptographic purposes.
                                 \nev{112}


\paragraph{Open problem.} Give a
probabilistic algorithm $\cala$ and a
positive integer $c_{1}$ so that for all
positive integers $t,s$
and for all sufficiently
large integers $n$
 if $\cala
$ gets $c={1/t}$, $k=\lfloor s\log
n\rfloor$, $n$, and a random value of
$B(n,k,c)=(b_{1},\ldots  ,b_{n})$ 
as an input then with a
probability of at least $1/ 2$ (for the
randomizations of both $B$ and $\cala$) and
in time $n^{c_{1}}$ the algorithm $\cala$
finds a vector
$x\in \Lambda(n,k,c)$ so that $x\not= 0$
and
\nev{113}
\begin{itemize}
\item[(i.)] $\Vert x\Vert <\Vert b_{1}\Vert$, or (a stronger requirement)
\item[(ii.)] $\Vert x\Vert <\frac{1}{2}\Vert b_{1}\Vert$.
\end{itemize}
\nev{114}

\begin{remark} The choice of $k$ in
the open
problem is based on the fact that currently
the largest $k$ so that a
Korkine-Zolotareff basis can be found in
probabilistic polynomial time is $k=O(\log
n)$ (see~\cite{ARS}), and so Schnorr's
algorithm can be used with block length
$k$.  Therefore our open problem can be
solved by improving this bound and still
using Schnorr's algorithm.
\end{remark}
                      \nev{115}



\vskip 5pt

  In the proof of \expref{Theorem}{T1} we
represent our lattice elements by sequences
of integers in a similar way as it was done
by R.~Kannan in~\cite{Kannan}.  In fact his
estimate about the number of such sequences
which correspond to a short lattice vector
remain valid in our case and is used in our
proof.  A similar bound was also used by
M.~Furst and R.~Kannan in~\cite{FK}.
\nev{116}





\subsection{The history of the problem with
some
technical details} The history of finding
short vectors in lattices starts with the
works of Lagrange  and Gauss.
Both of them considered the problem of
finding a shortest
nonzero vector in two-dimensional lattices.
In the nineteenth century Hermite,
Zolotareff and Minkowski considered the
problem of $n$-dimensional lattices as part
of the reduction theory of quadratic forms.
Although a large number of theorems in the
theory of lattices were dealing with the
existence of short vectors in lattices
(e.g.  Minkowski's convex body theorem)
these were mainly existence theorems
without giving any efficient method for finding  
short vectors.  In 1983 A.~Lenstra,
H.~Lenstra and L.~Lov\'asz found the first
polynomial time algorithm for factoring
polynomials with rational coefficients.
Their solution was based on an algorithm
which finds a vector not longer than
$2^{(n-1)/2}$ times the shortest
nonzero vector.  Since then this method,
the LLL reduction, has been used for the    
solution of a large number of both
theoretical and practical problems.  For
example it was used to disprove the Mertens
conjecture~\cite{OR} and to break several
proposed cryptosystems (see e.g.~\cite{LO}).
        \nev{117}





The LLL reduction starts with an arbitrary
basis $b_{1},\ldots  ,b_{n}$ of the lattice $L$
and then it gradually ``improves'' the
basis.  In each step we replace two
consecutive elements of the basis by two
new elements.  Roughly speaking the goal of
these exchanges is to get a size reduced
basis $b_{1},\ldots  ,b_{n}$ where for each $i$
in the two-dimensional lattice $K$
generated by $P_{i}b_{i}$ and
$P_{i}b_{i+1}$, the shortest vector is
$P_{i}b_{i}$ and $(P_{i}b_{i},P_{i}b_{i+1})$
is a size reduced basis of $K$.  We try to reach this
goal by picking an $i$ where this is not
true and replacing $b_{i}, b_{i+1}$ by
two other vectors so that they satisfy this
condition.  (In order to do this we
have to find the shortest nonzero vector in
$K$, extend it into a size-reduced basis of
$K$; this way we have the new $P_{i}b_{i},    
P_{i+1}b_{i}$, then find the corresponding
new $b_{i}$ and $b_{i+1}$.  All of these
steps can be done easily.)  In picking $i$
we give preference to those pairs where we
are far away from our goal according to
some reasonable measure.  In a polynomial
number of steps, although we will not
necessarily reach a situation where each
pair satisfies the condition, still we can
ensure that each pair will be close to it.
This will guarantee that the ratios $\Vert
b_{i}^{*}\Vert / \Vert b_{i+1}^{*}\Vert $
remain below a constant bound, namely
$\Vert b_{i}^{*}\Vert / \Vert
b_{i+1}^{*}\Vert \le \sqrt 2$ for all
$i=1,\ldots  ,n$.  It is easy to see that
$\lambda_{1}(L)$, the length of the
shortest nonzero vector, is bounded from
below by $\min_{i} \Vert b_{i}^{*} \Vert $
and so $\Vert b_{1}\Vert \le 2^{(n-1)/2}\lambda_{1}(L) $.
(Indeed if $u$ is a
shortest nonzero vector then we consider
the sequence $P_{i}u$, $i=1,\ldots  ,n$.
We have $\Vert u\Vert =\Vert P_{1} u\Vert
\ge $ $\Vert P_{2}u\Vert\ge \ldots   \ge $ $
\Vert P_{n}u\Vert =0 $. Let $j$ be the
smallest integer so that $\Vert
P_{j}u \Vert=0 $. By the definition of
$b_{j^{*}}$ we have that
$P_{j-1}u=k b_{j}^{*}$, where
$k\not= 0$ is an integer and so $\Vert
u\Vert
\ge \Vert b_{j}^{*}\Vert $.) \nev{119}

C.~P.~Schnorr has improved the
approximation factor of the algorithm by
working with $k$ consecutive basis elements
$b_{i},\ldots  ,b_{i+k-1}$ instead of just $2$.
This generalization creates significant new
problems.  What should be our goal for the
$k$-blocks of basis elements and what will
play the role of the inequality $\Vert
b_{i}^{*}\Vert / \Vert b_{i+1}^{*} \Vert
\le \sqrt 2$?  Perhaps most important is
the difficulty that we have to prove
everything for $k$-dimensional lattices
instead of two-dimensional lattices where
the arising problems do not cause
significant difficulties.
\nev{120}

Schnorr gave the following answers to these
questions.  (We just give a rough
simplified sketch of his algorithm.)  The
goal is that every block
$b_{i},\ldots  ,b_{i+k-1}$ should have the
property that
$P_{i}b_{i},\ldots  ,P_{i}b_{i+k-1}$
Korkine-Zolotareff basis in the
lattice generated by them.  Therefore in
each step we select somehow an $i$ so that
this does not hold and replace the $k$
basis vectors $b_{i},\ldots  ,b_{i+k-1}$ by $k$
new vectors so that we have now a
Korkine-Zolotareff basis.  (For this step
we have to find a Korkine-Zolotareff basis
in the $k$-dimensional lattice generated by
$P_{i}b_{i},\ldots  ,P_{i}b_{i+k-1}$.  For
polynomial time algorithms as we mentioned
already this limits the size of $k$ to
$O(\log n)$ or $O(\log n/\log \log n)$.)
Again we cannot hope in polynomial time to
reach a stage where every block of length
$k$ provides a Korkine-Zolotareff basis,
but we may reach a stage where every block
is close to it according to some reasonable
measure.  We may get an upper bound on
$\Vert b_{1}\Vert/\lambda_{1}(L) $
essentially by getting an upper bound on
$\Vert b_{i}^{*}\Vert /\Vert b_{i+k-1}^{*}
\Vert $ for all $i=1,\ldots  ,n-k+1$.  This
leads to the task, of finding an upper
bound on $\Vert d_{1}\Vert^2 / \Vert
d_{k}^{*} \Vert^2$ for every 
$k$-dimensional lattice $J$, where
$d_{1},\ldots  ,d_{k}$ is a Korkine-Zolotareff
basis in $J$.  In other words we need the
value of the Korkine-Zolotareff constant
defined earlier.  Schnorr gave the upper
bound $\alpha_{k}\le k^{1+\log k}$ and from
this he got an upper bound on $\Vert
b_{1}\Vert/\lambda_{1}(L) $.  However, with
another method (that we describe shortly),
he gave a better upper bound on $\Vert
b_{1}\Vert/\lambda_{1}(L) $ which made
likely that the truth is $\alpha_{k}\le
k^{O(1)} $ (this would have provided the
same upper bound on $\Vert
b_{1}\Vert/\lambda_{1}(L) $).  In this
paper we show that surprisingly Schnorr's
upper bound on $\alpha _{k}$ is tight, that
is, there is an $\epsilon>0$ with
$\alpha_{k}\ge k^{\epsilon \log k}$ for all
$k$. \nev{121a}

  The other method used by
Schnorr which gives the better upper bound
on $\Vert b_{1}\Vert/\lambda_{1}(L) $ is
the following.  Instead of considering
blocks of length $k$ let us consider blocks
of basis elements of length $2k$,
$b_{i},\ldots  ,b_{i+2k-1}$.  (We may simplify
the picture and speed up the algorithm if
we consider only the case when $n=mk$ and
$i=tk+1$.)  The algorithm will be the same
but now instead of $\Vert b_{i}^{*}\Vert^2/
\Vert b_{i+k-1}^{*}\Vert^{2} $ we are
interested in the geometric mean of such
ratios on an interval of length $k$.  That
is, we consider the quantity 
$$
\Bigl(\bigl(\prod_{j=i}^{i+k-1}\Vert b_{j}^{*}
\Vert^{2}\bigr) \bigl(\prod_{j=i+k}^{i+2k-1} \Vert
b_{j}^{*}\Vert \bigr)^{-2}\Bigr)^{{1/ k}}\,.
$$
This quantity also can be used to give an
upper bound on $\Vert
b_{1}\Vert/\lambda_{1}(L) $.  Again we need
an upper bound on the ratio, that is, we
need an upper bound for the corresponding
ratio for every $2k$-dimensional lattice
with every possible choice of a
Korkine-Zolotareff basis.  By our
definition given earlier the smallest such
upper bound is the lattice constant
$\beta_{k}$.  Schnorr proved that         
$\beta_{k}\le 4k^{2} $ and this lead him to
the upper bound $(2k)^{2n/k}$ on       
the approximation factor.  In this paper we
show that this upper bound is tight apart
from a constant factor in the exponent,
that is, there is an $\epsilon>0$ so that
$\beta_{k} \ge k^{\epsilon}$ for all $k$.
\nev{121}

The lower bound on $\beta_{k}$ only shows
that the analysis given by Schnorr about
his algorithm cannot be improved by
improving the upper bound on $\beta_{k}$
but does not prove in itself that the
algorithm cannot perform always better.  We
prove this latter statement by constructing
a lattice $L$ and
a basis $b_{1},\ldots  ,b_{n}$ so that applying
Schnorr's algorithm to this basis the
resulting approximation factor, that is,
$\Vert b_{1}\Vert/\lambda_{1} (L) $ is only
$k^{\epsilon{n/ k}}$ for some constant
$\epsilon$, that is, apart from the factor
$\epsilon>0$ it is the same as Schnorr's
upper bound.  Our basis $b_{1},\ldots  ,b_{n}$
will have the property that it is size-reduced and for any consecutive block of
$2k$ basis vectors $b_{i},\ldots  ,b_{i+2k-1}$,
the vectors
$P_{i}b_{i},\ldots  ,P_{i}b_{i+2k-1}$ form a
Korkine-Zolotareff basis of
the lattice generated by them and
\hfill\break 
$$\left(\left(\prod_{j=i}^{i+k-1}\Vert
P_{i}b_{j}^{*} \Vert^{2}\right)
\left(\prod_{j=i+k}^{i+2k-1} \Vert
P_{i}b_{j}^{*}\Vert \right)^{-2}\right)^{{1/ k}}\ge
k^{\epsilon}$$ where
$\epsilon>0$ is a constant. \nev{122}

\begin{remark}\hfill
\begin{enumerate}
 \item In Schnorr's paper~\cite{Schnorr} several different algorithms
are presented.  Our lower bounds are valid
even for the versions, $k$-reduction and
block $2k$-reduction, where there is no
polynomial time limit on the running time
of the algorithm.  The reason is that the
basis that we provide for the lower bound
has the property that starting from it
Schnorr's algorithm immediately terminates.
               \nev{123}

\item A random lattice construction has been used
to create problems with worst-case/average-case 
equivalence~\cite{Ajt1}.  Another random lattice
construction lead to a conjectured $0-1$ law
for lattice properties testable in polynomial 
time.

The present way of randomizing lattices is
different from both of these although the     
choice of randomization was motivated by
the randomization method of~\cite{Ajt2}.
\nev{124}
\end{enumerate}
\end{remark}

\section{Sketch of the proofs of Theorems~\ref{T0} and~\ref{T1}}
First we give an equivalent definition
for the random lattice $\Lambda(n,k,c)$,
which is longer but more natural and has a
clear motivation.
        \nev{525}

We will construct a size reduced basis $(b_{1},\ldots ,b_{n})$ so that
$$
b_{i}^{*}=f_{i} =
\exp\left(c\frac{n-i+1}{k }\log k\right)e_{i}\,,
$$
$i=1,\ldots ,n$.
Assume that we have such a lattice.  Minkowski's convex body theorem
implies that $2n^{1/2}(\det L)^{1/n}$ is an upper bound on
the length of the shortest nonzero vector in any lattice.
Now
\[
(\det L)^{1/n}=\bigl(\prod_{i=1}^{n} \Vert b_{i}^{*}\Vert\bigr)^{1/n}
=\exp\left(c \frac{n+1}{2k} \log k\right)\,.
\]  
Since $\Vert b_{1}\Vert=\exp\left(c(n / k)\log k\right)$,
we get (using that $k\le \epsilon' n$ and that we may choose
$\epsilon'$ with, \eg, $\epsilon'< c /10$) that $\Vert
b_{1}\Vert/\lambda_{1}(L)\ge k^{\epsilon{n/k}}$.  (This is the
only point where we use the assumption $k\le {\epsilon'} n$.  For larger
values of $k$ we would need a better upper bound on $\lambda_{1}(L)$).
This holds also if $(b_{1},\ldots ,b_{n}) =B(n,2k,c)$.
For the proof of \expref{Theorem}{T1} we have to show that
$(P_{i}b_{i},\ldots ,P_{i}b_{i+2k-1})$ is a Korkine-Zolotareff basis in
the lattice generated by them for $i=1,\ldots ,n-2k +1$.

The vectors $b_{1}^{*},\ldots  ,b_{n}^{*}$ are
already fixed and we have to define
$b_{1},\ldots  ,b_{n}$.
$b_{1}^{*},\ldots  ,b_{n}^{*}$ uniquely
determine
the projections $P_{i}$. Indeed $P_{i}$ was
defined as the orthogonal projection of
$\err^{n}$ onto the subspace $S$ orthogonal
to $b_{1},\ldots  ,b_{i-1}$. The vectors
$b_{1},\ldots  ,b_{i-1}$ generate the same
subspace as the vectors
$b_{1}^{*},\ldots  ,b_{i-1}^{*}$. Therefore $S$,
and so $P_{i}$, are uniquely determined by
$b_{1}^{*},\ldots  ,b_{i}^{*}$. We do not define
the vectors $b_{i}$ directly but define
first the vectors $P_{j}b_{i}$ for
$j=n,\ldots  ,1$ recursively by recursion on $j$
starting at $n$ and going downwards.  (At
the end we get $b_{i}$ since
$P_{1}b_{i}=b_{i}$.)  This means that we
build up the vectors $b_{i}$ from their
projected images by going backwards through
the sequence of projections $P_{i}$.  For
$j=n$ we do not have any choices, by the
definitions of $b_{i}^{*}$ and $P_{j}$ we
have $P_{n}b_{i}=0$ if $i<n$ and
$P_{n}b_{n}=b_{n}^{*} $.
\nev{126}

The basic principle of this process is the
following.  Assume that $P_{j}b_{i}$ has
been already defined for a fixed $j$ and
for all $i$.  These elements generate an
$n-j+1$-dimensional lattice $L_{j}$ in the
$n-j+1$-dimensional subspace generated by
$b_{j}^{*},\ldots  ,b_{n}^{*}$.  We will define
a $(n-(j-1)+1)$-dimensional lattice $L_{j-1}$
in the subspace generated by
$b_{j-1}^{*},\ldots  ,b_{n}^{*}$ so that
$P_{j}L_{j-1}=L_{j}$.  Therefore if
$L_{j-1}$ is given somehow then
$P_{j-1}b_{i}$ must be an element $x$ of
$L_{j-1}$ with the property that
$P_{j}x=P_{j}b_{i}$.  Since we want our
basis to be size reduced there are at most
two possible choices for $x$ since
$P_{j-1}b_{i} $ and $b_{j-1}^{*}$ has been
already fixed.  If in the definition of a
size reduced basis we replace the
requirement $|\mu_{i,j}|\le 1/2$ by
$-1/2 < \mu_{i,j} \le 1/2$
then the choice of $b_{i}$ is uniquely
determined by the lattice $L_{j-1}$.
Therefore our only task is the selection of
the lattice $L_{j-1}$ if we know already
the lattice $L_{j}$.  The conditions for
this selection are the following: lattice
$L_{j-1}$ must be chosen from a given space
whose dimension is larger by $1$ than the
dimension of $L_{j}$, it must contain a
given vector $b_{j-1}^{*}$ orthogonal to
$L_{j}$, and we have to choose it in a way
that a given orthogonal projection will map
$L_{j-1}$ onto $L_{j}$.  There are
infinitely many different choices for
$L_{j-1}$ with these properties.  We will
see that there is a very natural way to do
it at random.  However we will not do it
completely at random since we want, that
with a high probability, the
vector $P_{j-1}b_{j-1}=b_{j-1}^{*}$ is
no longer than the vector $P_{j-1}b_{j}$
(this is a consequence of the requirement
that $P_{j-1}b_{j-1}$ is the first element
of a Korkine-Zolotareff basis.)  To make
this requirement easily satisfiable we try
to make $ P_{j-1} b_{j}$ which is an
inverse image of $b_{j}^{*}$ as large as
possible, otherwise we choose everything at
random.  Below we formulate this lattice
selection problem in an abstract setting
and define the randomization there.
\nev{127}

We formulate a lemma below describing the
random
extension of an arbitrary $m$-dimensional     
lattice $L$. We will apply this lemma with
$m := n-j+1$ and  $L := L_{j}$.               
Assume now,
for the formulation of the following
lemma, that $L$ is an arbitrary lattice in
$\err^{m}$ and $a\in L$ so that $a$ is
contained in a basis of $L$.  Assume
further that $\kappa>0$.  Let $P$ be the
orthogonal projection $P$ of $\err^{m+1}$
to $\err^{m}$ defined by 
$P(y_{1},\ldots  ,y_{m},y_{m+1}) =
(y_{1},\ldots ,y_{m})$.  We are
interested in lattices $K$ in $\err^{m+1}$
so that $(0,\ldots,0 ,\kappa)\in K$, 
$PK=L$, the shortest vector $w\in
K$ with $Pw=a$ is as long as possible,
otherwise $K$ is random in some sense.
\nev{324}

The assumption $(0, \ldots , 0,\kappa)\in K$
implies that for every $K$
we have $\Vert w\Vert^{2} \le \Vert
a\Vert^{2} +({\kappa}/2)^{2}$ if
$w\in K$ and $Pw=a$.  However this upper
bound is reached for the vector 
$(a,\kappa/2)$, therefore we
will deal only with lattices $K$ so that
$(a,\kappa/2) \in K$.
The following lemma describes a natural
randomization of a lattice $K$ with these
properties.  The definition of the
randomization formally depends on an
arbitrarily chosen basis of $L$ containing
$a$ but the lemma states that the
randomization is in fact independent from
the choice of this basis. \nev{325}



\begin{lemma} \label{A0} Assume that
$m$ is a positive integer, $L\subseteq
\err^{m}$ is a lattice, $a\in L$,
$a\not=0$, $\kappa>0$ is a real number and
$x_{1},\ldots  ,x_{m-1}\in L$ so that $\lbrace
x_{1},\ldots  ,x_{m-1},a\rbrace$ is a basis of
$L$.  Depending on
$m,\kappa,L,a,x_{1},\ldots  ,x_{m-1}$ we define
a random variable $Y$ whose values will be
lattices in $\err^{m+1}$.  We pick $m-1$
real numbers $\xi_{1},\ldots  ,\xi_{m-1}$
independently and with uniform
distributions from the interval $(0,1)$.  A
random value ${{{K}}}$ of $Y$ will be the
lattice in $\err^{m+1}$ generated by the
vectors $(x_{i},\xi_{i}\kappa)$, 
$i=1,\ldots  ,m-1$, the vector 
$(a,\kappa/2)$ and the vector
$(0,\ldots ,0,\kappa)$. \nev{623}
Then the distribution of\, $Y$ does not
depend on the choice of the vectors
$x_{1},\ldots  ,x_{m-1}$ and it does not change
if we replace the vector $a$ by the vector
$-a$.  Moreover for each possible value
${{{K}}}$ of $Y$ and for each $x\in L$
there is a unique real number $\sigma_{x}$,
$-1/2 \le \sigma_{x}< 1/2$ so
that $(x,\sigma_{x}\kappa)\in K$ 
and if $x$ is linearly
independent of the vector $a$ then the
distribution of $\sigma_{x}$ is uniform over
the interval $[-{1/ 2},{1/2})$.
\nev{624}
\end{lemma}

We return now to our basis construction.
We will use \expref{Lemma}{A0} with the
following substitutions: $m := n-j+1$;
$L := L_{j}$; $a:= b_{j}^{*}$; 
$\err^{m}$ is the subspace generated by
$b_{j}^{*},\ldots  ,b_{n}^{*}$;
$\err^{m+1}$ is the subspace generated by
$b_{j-1},b_{j}^{*},\ldots  ,b_{n}^{*}$;
$(0,\ldots 0,\kappa) := b_{j-1}^{*} $.  

\begin{sloppypar}
Let $K$ be the random
lattice defined in the lemma.  The property
$(a,\kappa/2) \in K$
implies that $({1}/{2})b_{j-1}^{*}+b_{j}^{*}\in L_{j-1}$ and
clearly $P_{j}((1/2)b_{j-1}^{*}+b_{j}^{*})=b_{j}^{*} $.  The
other elements of $L_{j}$ depend on the
random choices defined by the random
variable $Y$ of the lemma. \nev{128}
\end{sloppypar}

As we have told, if $L_{j-1}$ is given, the
choice for $P_{j-1}b_{i}$ is unique with
the condition $\mu_{i,j-1}\in (-{1/2},{1/2}]$.  This completes the
definition of $P_{j-1}b_{i}$ for all $i$
and so the definition of the basis
$b_{1},\ldots  ,b_{n}$.  It is an immediate
consequence of the definition that
$b_{1},\ldots  ,b_{n}$ are linearly independent
and $b_{i}^{*}$ is really the vector that
we have selected in advance for this role.
The condition $\mu_{i,j-1}\in (-{1/2},{1/2}]$ guarantees that it is a
size reduced basis.  \expref{Lemma}{A0}
implies that this definition is equivalent
to our original definitions of
$\Lambda(n,k,c)$, $B(n,k,c)$.  Indeed,
since we could pick the basis elements
$\lbrace x_{i} \rbrace$ in an arbitrary
way, using the basis
$P_{j}b_{j},\ldots  ,P_{j}b_{n}$ gives the
original definition. \nev{129}

We prove that with a positive probability
for the randomization of $\Lambda(n,k,c)$
we have that for each $i=1,\ldots  ,n-k+1$ the
elements $P_{i}b_{i},\ldots  ,P_{i}b_{i+k-1}$
form a  Korkine-Zolotareff
basis of the lattice generated by them,
provided that $c>0$ is a sufficiently small
constant.
 For this proof
we do not need
the whole $n$-dimensional lattice.  The
lattice construction can be described by
restricting our attention to the elements
of this $k$-dimensional lattice.  In fact
if we multiply every element of this
lattice by a suitable real number
(depending on $n,k$, and $i$) we get a
lattice whose distribution is the same as
the distribution of $\Lambda(k,k,c)$.  We
will show that $b_{1},\ldots  ,b_{k}$ is a
Korkine-Zolotareff basis in
$\Lambda(k,k,c)$ with a probability of at
least $1-\eee^{-\alpha k}$ where $\alpha>0$ is
a constant.  This implies that there is a
constant $c'>0$ so that if $k>c'\log n$
then the probability that
$P_{i}b_{i},\ldots  ,P_{i}b_{i+k-1}$ is a
Korkine-Zolotareff basis for all
$i=1,\ldots  ,n-k+1$, is close to $1$.  (For
smaller integers $k$, this probability is
not close to $1$ but still it is not 0.
For the proof of this fact we may either
use Lov\'asz's Local Lemma, or a more
direct argument which also provides a
construction.) This completes the sketch of
the proof of \expref{Theorem}{T1}.
        \nev{130}


\section{The proofs of Theorems~\ref{T0} and~\ref{T1}}  
  First we prove \expref{Theorem}{T1}
together with the lower bound on
$\beta_{k}$, and then the lower bound on
$\alpha_{k}$.  The proof about the lower
bound on $\alpha_{k}$ has the same
structure than the lower bound proof for
$\beta_{k}$, but in places it requires
different and somewhat sharper and more
difficult estimates.  In principle it would
be possible  to give the proof for
$\beta_{k}$ only and then point out the
differences.  However in this case,
it would be 
very difficult to check the
correctness of the second proof.  Therefore
we include the complete proof for
$\alpha_{k}$ as well, although this
includes some repetitions.
 \nev{621}

\begin{definition}
If $n$ is a positive integer
then the set $\lbrace 1,\ldots  ,n\rbrace $ will
be denoted by $\caln_{n}$. $\caln_{0}$ will
be the empty set. \nev{622}
\end{definition}


We will use the following observation in
the proof of \expref{Lemma}{A0}.
       \nev{625}

\begin{lemma} \label{A0.1} Suppose that
$\xi_{1},\ldots  ,\xi_{k}$ are independent
random variables,
uniformly distributed over the interval $(0,1)$.
Assume further that $A=\lbrace
a_{i,j}\rbrace $ is a $k$ by $k$ matrix
with integer entries and with determinant
$\pm 1$.  For each $i=1,\ldots  ,k$ let
$\rho_{i}=\sum_{j=1}^{k}a_{i,j}\xi_{j}$ and
let $\nu_{i}=\rho_{i}-\lfloor \rho_{i}
\rfloor$, where $\lfloor x \rfloor$ is the
largest integer which is not greater than
the real number $x$.
\nev{626}
Then each $\nu_{i}$  
is uniformly distributed over
$[0,1)$ and the random
variables $\nu_{1},\ldots  ,\nu_{k}$ are
independent. \end{lemma}
\nev{627}

\begin{proof}  It is sufficient to show that
the vector $(\nu_{1},\ldots  ,\nu_{k})$
is uniformly distributed over
the $n$-dimensional unit cube $Q_{k}$.  The
vector $(\rho_{1},\ldots  ,\rho_{k})$ 
is in the $k$-dimensional
parallelepiped $P$ which has a vertex at
$0$ and whose edges starting from $0$ are
the columns of $A$.  The linear
transformation $A$ takes $Q_{k}$ into $P$.
Since the determinant of $A$ is $\pm 1$ we
have that the distribution of the vector
$\rho=(\rho_{1},\ldots  ,\rho_{k})$ 
is uniform over $P$.  We get the
vector $\nu=(\nu_{1},\ldots ,\nu_{k})$ 
by reducing it
modulo $Q_{k}$.  Since both $Q_{k}$ and $P$
are basic parallelepipeds of the same
lattice (the lattice of points with integer
coordinates) this reduction is a one-to-one
map which preserves the $k$-dimensional
volume.  Therefore the fact that $\rho$ 
is uniformly distributed over
$P$ implies that $\nu$
is uniformly distributed over $Q_{k}$.
\end{proof} \nev{628}

\begin{proof}[Proof of \expref{Lemma}{A0}]
Since
$a,x_{1},\ldots  ,x_{m-1}$ are linearly
independent and $\kappa\not=0$ we have that
the vectors $(x_{i},\xi_{i}\kappa)$,
$i=1,\ldots  ,m-1$, $(a,\kappa/2)$ 
and the vector $(0,\ldots ,0,\kappa)$ 
are also linearly independent and so they 
form a basis of $K$.  We will use this fact 
in the proof.
        \nev{629}

Let $z_{1},\ldots ,z_{m-1}\in L$ so that
$z_{1},\ldots  ,z_{m-1},a$ is a basis of $L$.
Assume that we take a random value
${{{K}}}$ of $Y$ using the basis
$x_{1},\ldots  ,x_{m-1},a$.  It is sufficient to
show that with probability $1$, for each
$i=1,\ldots  ,m-1$ there is a unique real number
$\nu_{i}\in (0,1)$ so that 
$(z_{i},\nu_{i}\kappa) \in K$,
moreover the random variables $\nu_{i}$,
$i=1,\ldots  ,k$ defined this way 
are uniformly distributed over
$(0,1)$ and they are
mutually independent.
\nev{630}

First we consider the special case when
there are integers $t_{i}$, $i=1,\ldots  ,m-1$
so
that $z_{i}=x_{i}+t_{i}a$ , $i=1,\ldots  ,m-1$.
By the definition of $\xi_{i}$ we have
$(x_{i},\xi_{i}\kappa) \in K$.  
This can be written in the form
of $(z_{i}- t_{i}a, \xi_{i}\kappa)\in K$.  
Using that $(a, \kappa/2)\in K$ 
we get that 
$(z_{i},(\xi_{i}+t_{i}/2)\kappa))\in K$
and so 
$(0,\ldots,0,\kappa)\in K$ implies the
existence of $\nu_{i}$.  If $\nu_{i}$ is
not unique then $(0,\ldots  ,0,\theta\kappa)\in K$ 
for some $\theta\in (0,1)$, in contradiction to the
fact that 
$(0,\ldots,0,\kappa)$ is a basis vector of
$K$.  Since $\nu_{i}$ is the
fractional part of $\xi_{i}+t_{i}/2$ and $\xi_{i}$ 
is uniformly distributed over  $(0,1)$,
we have that $\nu_{i}$
is also uniformly distributed over $(0,1)$.
 \nev{644}

We consider now the general case assuming
only that $(z_{1},\ldots  ,z_{m-1},a)$ is a basis
of $L$. We have
$z_{i}=t_{i}a_{i}+\sum_{j=1}^{m-1}\alpha_{i,j}x_{j}$
for $i=1,\ldots  ,m-1$, where all of the
coefficients $t_{i}$ and $\alpha_{i,j}$
are integers. Let $w_{i}=z_{i}-t_{i}a$,
$i=1,\ldots  ,m-1$. Clearly
$(w_{1},\ldots  ,w_{m-1},a)$  is a basis of $L$.
It is sufficient to prove that our
assertion holds with $z_{i} := w_{i}$,    
$i=1,\ldots  ,m-1$, since if this is
true then we may apply the already proven
special case with $x_{i} :=w_{i}$.        
In other
words, we have to prove now the assertion
for the special case when
the basis vectors $z_{1},\ldots  ,z_{m-1}$
can be written in the form
$z_{i}=\sum_{j=1}^{m-1}\alpha_{i,j}x_{j}$,
$i=1,\ldots  ,m-1$, where  $\alpha_{i,j}$ is an
integer
for
$i=1,\ldots  ,m-1$, $j=1,\ldots  ,m-1$.
 Since both $(z_{1},\ldots  ,z_{m-1},a)$      
and $(x_{1},\ldots  ,x_{m},a)$ are            
bases of $L$, we have that
the determinant $|\alpha_{ij}|$ is $\pm 1$.
        \nev{645}

By the definition of $K$ we have
$( x_{j},\xi_{j}\kappa ) \in K$.
For each fixed $i$ we take the
linear combinations of these vectors with
coefficients $\alpha_{i,j}$.  We get that
$(z_{i},(\sum_{j=1}^{m-1}\alpha_{i,j}\xi_{j})\kappa)
\in K$.  Let $\nu_{i}$ be the
fractional part of $
\sum_{j=1}^{m-1}\alpha_{i,j}\xi_{j} $.
Clearly with a probability $1$ we have
$\nu_{j}\in (0,1)$.  Moreover \expref{Lemma}{A0.1} 
implies that each $\nu_{i}$ 
is uniformly distributed over
$(0,1)$ and the
random variables $\nu_{1},\ldots  ,\nu_{k}$ are
independent.
\nev{646}

Let $x\in L$. We have
$x=ta+\sum_{i=1}^{m-1}b_{i}x_{i} $, where
$t,b_{1},\ldots  ,b_{m-1}$ are integers.
Since $(x_{i}, \xi_{i}\kappa) \in K$, 
$i=1,\ldots  ,m-1$ and 
$(a,\kappa/2) \in K$ we
have that $(x, \sigma' \kappa) \in K$,
where $\sigma' =
{t/2}+ \sum_{i=1}^{n-1}b_{i}\xi_{i} $.
Let $\sigma_{x}$ the unique element of the
interval $[-{1/2},{1/2})$ so that
for a suitable integer $s$ we have
$\sigma'+s =\sigma_{x}$. 
$(0,\ldots ,0,\kappa) \in K$
implies that $(x,\sigma_{x}\kappa) \in K$.
Assume that contrary to our assertion
$\sigma_{x}$ is not unique.  By taking the
difference of the two vectors 
$(x,\sigma_{x} \kappa)$ for two
different values of $\sigma$ we get that
there is a $\theta\in (0,1)$ with 
$(0,\ldots, 0, \theta \kappa) \in K$ 
which contradicts to the fact that
$(0,\ldots ,0,\kappa)$ is a
basis vector of $K$.
\end{proof}
\nev{647}

\begin{definition}\hfill
\begin{enumerate}
\item  Assume that $m$ is a
positive integer, $L\subseteq \err^{m}$ is
a lattice, $\kappa>0$ is a real number and
$a\in L$, $a\not=0$.  The random variable
$Y$ defined in \expref{Lemma}{A0} will be
denoted by $\ext_{m,\kappa,L,a}$.
\nev{648}

We define a random variable $\rand_{n,h}$ whose values will be lattices
in $\err^{n}$.  The definition depends on two parameters: a positive
integer $n$ and a function $h$ with the property
$\domain(h)\supseteq\lbrace 1,..,n\rbrace $, (only the values of $h$ on
$\lbrace 1,\ldots  ,n\rbrace $ will be used in the definition, but
notationally it will be more convenient to allow functions with larger
domains).  The values of $h$ will be positive real numbers.  Assume that
$n$ and $h$ are given.  We define the random variable $\rand_{n,h}$ by
recursion on $n$.  At the same time we will prove by induction on $n$
that for each possible value $L$ of $\rand_{n,h}$ there is a minimal
positive real number $\nu(L)$ so that 
$(0,\ldots  ,0,\nu(L)) \in L$.
$\rand_{1,h}$ will be always the one-dimensional lattice consisting
of all of the real numbers $ih(1)$, where $i$ is an integer.  Clearly
$\nu(L)$ is $h(1)$.  Assume that the random variable $\rand_{n-1,h}$ has
been defined with values in $\err^{n-1}$ for some $n>1$.  Then first we
take a random value $L$ of $\rand_{n-1,h}$.  Let 
$a=( 0,\ldots  ,0,\nu(L)) \in L $.  
Now we randomize $\ext_{n-1,h(n),L,a}$.
Its value is a lattice ${{{K}}}\subseteq \err^{n}$, this will be the
value of the random variable $\rand_{n,h}$.  By the definition of
$\ext_{n,h(n),L,a}$ the vector $( 0,\ldots  ,0,h(n) )$ is in
${{{K}}}$ which proves the existence of $\nu({{{K}}})$.
      \nev{649}

\item If $n$ is a positive integer then $\pi^{(i,n)}$ will denote the
orthogonal projection of $\err^{n}$ onto $\err^{i}$ defined by
$\pi^{(i,n)}( y_{1},\ldots  ,y_{i}, y_{i+1},\ldots  ,y_{n}) =$ $
( y_{1},\ldots  ,y_{i}) $. $\pi^{(0,n)}$ will be that map of
$\err^{n}$ into the zero-dimensional space $\err^{0}$ (consisting only
of the vector $0$).  If the value of $n$ is clear from the context we
will write $\pi^{(i)}$ for $\pi^{(i,n)}$.
\nev{650}

\item We say that the lattice $L\subseteq
\err^{n}$ is triangular
if it has a basis
$a_{i}=(
\alpha_{i,1},\ldots  ,\alpha_{i,n}) $,
$i=1,\ldots  ,n$ so that for all $i=1,\ldots  ,n$,
$\alpha_{i,i}\not=0$ and for all
$j=1,\ldots  ,i-1$ we have $\alpha_{i,j}=0$.
(The condition $\alpha_{i,i}\not=0$ can be
omitted since for a basis it follows from
the other conditions).  We will say that
the basis $a_{1},\ldots  ,a_{n}$ is a triangular
basis of $L$. \nev{654}

We can formulate the definition of triangularity in the following
equivalent form: $L$ is triangular iff for each $i=1,\ldots  ,n$ there is a
real number $\alpha\not=0$ so that $( 0,\ldots  ,0,\alpha) \in
\pi^{(i)}(L)$.
\end{enumerate}
\end{definition}
\nev{655}

\begin{remark} The triangularity of the lattice
$L$ depends on the way it is
embedded in $\err^{n}$.  In particular this property is {\em not}
invariant under isometric isomorphisms of lattices.  Namely there is a
lattice $L \subseteq \err^{n}$ and there is a unitary transformation $U$
of $\err^{n}$ so that $L$ is triangular but $UL$ is not, where
$UL=\lbrace Ux \mid x\in L\rbrace $.
\end{remark}
 \nev{656}
 
The following lemma is an immediate consequence of the definitions.
        \nev{657}

\begin{lemma} \label{A1} Assume that $n,i$ are positive integers,
$i\le n$, $L\subseteq \err^{n}$ is a triangular lattice, then
$\pi^{(i)}L$ is a triangular lattice in $\err^{i}$.\end{lemma}
\nev{658}

\begin{lemma} \label{A2} Assume that $n$ is a positive integer,
$h$ is a function defined on the set of all positive integers whose
values are positive real numbers.  Then each value $L$ of the random
variable $\rand_{n,h}$ is a triangular lattice. \end{lemma}
        \nev{659}

\begin{proof}  The recursive definition of
the random variable $\rand_{n,h}$
implies that for all $i=1,\ldots  ,n$ we have that $(0,\ldots ,0,h(i)) \in \pi^{(i)}(L) $, which proves the
triangularity of $L$.
\end{proof}
\nev{660}

Suppose that $L\subseteq \err^{n}$ is a
triangular
lattice. Our next goal is to associate with
each $x\in L$ a sequence of integers
$a_{1},\ldots  ,a_{n}$, which will behave in a
similar way as sequence of coefficients
in an orthogonal basis. In particular we
will want to get a lower bound on
$\Vert x\Vert^{2} $ using the sequence
$a_{1},\ldots  ,a_{n}$.  We will derive this
sequence by applying an integer version of
the Gram-Schmidt orthogonalization to the
triangular basis and following the
projections of vector $x$  during this
orthogonalization.
We will be able to achieve integrality
since we will use lattice vectors during
the whole process. These lattice
vectors will not be necessarily in the
lattice $L$. Triangularity implies
that for each
$i=1,\ldots  ,n$, $\pi^{(i)}(L)\subseteq
\err^{i}$
is an $i$-dimensional lattice. We
will be able to use these lattices instead
of $L$    at the corresponding stages of
the process. As a first step we define a
sequence of vectors
$\wp_{i,L}\in \pi^{(i)}(L) $, $i=1,\ldots  ,n$
so that $\wp_{i,L}$ and
$e_{i}$ are parallel  (in $\err^{(i)}$).
 We may consider $\wp_{i,L}$
as the result of the
orthogonalization of the triangular basis.
\nev{5060}

\begin{sloppypar}
\begin{definition} Suppose that $L\subseteq
\err^{n}$ is a triangular lattice.  For
each $i=1,\ldots  ,n$ there is a $v=(
v_{0},\ldots  ,v_{i})\in \pi^{(i)}L $ so
that $v_{1}= \cdots  =v_{i-1}=0$ and $v_{i}>0$.
$v$ is unique up to a constant factor, so
there is a unique vector $v$ with this
property if we add the requirement that
$v_{i}$ is minimal.  We will denote this
vector by $\wp_{i,L}$.  Clearly every
triangular basis of $\pi^{(i)}(L)$ contains
$\wp_{i,L}$ or $-\wp_{i,L}$.
\end{definition} \nev{664}
\end{sloppypar}

\begin{remark}
We will define $a_{i}$ in the following
way. We consider the set
$$
S_{x}=\lbrace \pi^{(i)}(x)+t\wp_{i,L} \mid t=0,\pm 1,\pm2,\ldots   \rbrace\,.
$$
 From the
elements of $S_{x}$ we take an
$y_{0}=\pi^{(i)}(x)+t_{0}\wp_{i,L}$ whose
$i$th component is minimal in absolute
value (preferring $1/ 2$ over
${-{1/2}}$). $a_{i}$ will be defined
by the equation
$\pi^{(i)}(x)=y_{0}+a_{i}\wp_{i,L}$.
\nev{5062}

The set $S_{x}$ can be also
defined as $S_{x}=\lbrace y\in
\pi^{(i)}(L) \mid
\pi^{(i-1)}(y)=\pi^{(i-1)}(x) \rbrace$.
Then we get
$y_{0}$ as a function of $\pi^{(i-1)}(x)$.
Since we will need this function later, we
will use it in the final definition of
$a_{i}$ given in \expref{Lemma}{D1} below.
\end{remark}
 \nev{5061}

\begin{definition}
If $L\subseteq \err^{n}$ is a triangular
lattice, then for each $i\in [0,n-1]$ we
define a function $\calu_{i,L}$ whose
domain will be $\pi^{(i)}(L)$ and whose
range will be in $\pi^{(i+1)}(L)$.  We
claim that for each $x\in \pi^{(i)}(L)$,
there is a unique real number $\xi$ in the
interval $(-{1/ 2},{1/2}]$ so that
$( x,0) +\xi\wp_{i+1,L}\in
\pi^{(i+1)}(L)$.  Indeed, since
$x=\pi^{(i)}y$ for some $y\in L$ we have
that $x'=\pi^{(i+1)}y\in \pi^{(i+1)}L$ and
we get the vector $x'$ by extending $x$ with
a new component.  Since $\wp_{i+1,L}$ is
contained in a triangular basis of
$\pi^{(i+1)}(L)$ we can write $x'$ in the
form of $( x,0)+ \xi\wp_{i+1,L}
$.  The uniqueness of $\xi$ follows also
from the fact that $\wp_{i_1,L}$ is
contained in a triangular basis.  We define
a function $\calu_{i,L}$ mapping
$\pi^{(i)}L$ into $\pi^{(i+1)}$ by
$\calu_{i,L}(x)=( x,0) +\xi
\wp_{i+1,L}$ where $\xi$ is the unique real
number in $(-{1/ 2},{1/ 2}]$ so
that $( x,0) +\xi\wp_{i+1,L}\in
\pi^{(i+1)}(L)$.
\end{definition} \nev{665}

\begin{lemma} \label{D1} Assume that
$n$ is a positive integer, $L\subseteq
\err^{n}$ is a triangular lattice.  Then
for all $x\in L$ there is a uniquely
determined sequence of integers
$a_{1},\ldots,a_{n}$ so that for all
$j=1,\ldots ,n$ we have 
$$
\pi^{(j)}
x=\calu_{j-1,L}(\pi^{(j-1)}x
)+a_{j}\wp_{j,L}\,.
$$
For this sequence
$a_{1},\ldots  ,a_{n}$ we have 
$$
\Vert
x\Vert^{2}\ge \sum_{j=1}^{n} \Bigl(\min \bigl\lbrace
|a_{j}|,\bigl||a_{j}|-\frac{1}{2}\bigr|\bigr\rbrace\Bigr)^{2}\Vert \wp_{j,L}\Vert^{2}\ge
\frac{1}{4}\sum_{j=1}^{n} a_{j}^{2}\Vert
\wp_{j,L}\Vert^{2}\,.
$$
\nev{666}
  \end{lemma}

\begin{proof}  The vectors $\pi_{j}x$
and $\calu_{j-1,L}(\pi^{(j-1)}x)$ differ
only in their $j$th coordinates.  Since
both are in $\pi^{(j)}L$ their difference
$d= \pi_{j}x -\calu_{j-1,L}(\pi^{(j-1)}x) $
is a vector in $\pi^{(j)}L$ whose only
nonzero coordinate is the $j$th one.
$\wp_{i,L}$ is a basis vector of
$\pi^{(j)}(L)$ therefore $d=a_{j}\wp_{j,L}$
for some integer $a_{j}$.  Since
$\wp_{j,L}\not= 0$, $a_{j}$ is unique.  Let
$x=( x_{1},\ldots  ,x_{n}) $.  By
the definition of
$\calu_{j-1,L}(\pi^{(j-1)}x)$, the $j$th
coordinate of $\calu_{j-1,L}(\pi^{(j-1)}x)$
can be written in the form of $\xi
\wp_{j,L} $ where $\xi \in (-{1/
2},{1/2}]$.  Therefore $x_{j}=(\xi +
a_{j}) \wp_{j,L}$.  If $\xi_{j}$ and
$a_{j}$ has identical signs or $a_{j}=0$
then $|\xi+a_{j}|\ge |a_{j}|$.  Otherwise
$|\xi +a_{j}|\ge \bigl||a_{j}| - {1/ 2}\bigr|$.
This and the fact that the numbers $a_{i}$
are integers imply the final sequence of
inequalities.
\end{proof}
\nev{667}

\begin{definition}\hfill
\begin{enumerate}
\item If $n$ is a positive integer,
$L\subseteq \err^{n}$ is a triangular
lattice, $1\le i<l\le n$ are integers and $x\in L$ then the unique
sequence $a=( a_{1},\ldots  ,a_{n})$ whose existence is
guaranteed by \expref{Lemma}{D1} will be denoted $\theta^{(x,L)}=(
\theta^{(x,L)}_{1},\ldots  ,\theta^{(x,L)}_{n} ) $.
\nev{670}

\item If $a=( a_{1},\ldots  ,a_{n}) $
is a sequence of integers
then $\start(a)$ will be the largest positive integer $i$ so that
$a_{1}=\cdots = a_{i}=0$.  If there is no such positive integer then
$\start(a)=0$. \nev{674} 4.  Assume that $L$ is a triangular lattice.
For each $x\in L$ and $i=1,\ldots  ,n$ let $y(i)$ be the unique element of
$L$ so that $\pi^{(i)}x=\pi^{(i)}y(i)$ and $\calu_{j,L}(\pi^{(j)}y(i))=
\pi^{(j+1)}y(i)$ for each $j=i,\ldots  ,n-1$.  The uniqueness of $y(i)$
follows from the equality $y(i)=\calu_{n-1,L}(\ldots  \calu_{i,L}(x)\ldots  )$.
We will denote the vector $y(i)$ by $\phi(x,i)$.
        \nev{674}

\item If $L$ is a triangular lattice then we
define a basis
$\boldb_{i,L}$, $i=1,\ldots  ,n$ in the following way. $b_{1,L}=\wp_{n,L}$
and for all $i=2,\ldots  ,n-1$, $\boldb_{i,L}=\phi(\wp_{n-i+1},n-i+1)$.
\nev{675}

\item In the following we will assume that
$\err^{0} \subseteq \err^{1}
\subseteq \ldots  \subseteq \err^{n}$.  Namely if $i<j$ we will identify the
vector $( x_{1},\ldots  ,x_{i}) \in \err^{i}$ with the vector
$( x_{1},\ldots  ,x_{i},0,\ldots  ,0) \in \err^{j} $.  (A cleaner way
to do this would have been to define $\err^{n}$ as the set of all of the
infinite sequences $x_{1},\ldots  ,x_{n},x_{n+1},\ldots  $ of real numbers so that
$0=x_{n+1}=x_{n+2}=\cdots  $.)
\nev{676}
\end{enumerate}
\end{definition}

\begin{lemma} \label{D1.1} Assume that $L$ is a triangular lattice.
Then the basis $\boldb_{i,L}$, $i=1,\ldots  ,n$ is size reduced. \end{lemma}
\nev{677}

\begin{proof} 
By the definition of
$\boldb_{i,L}$ we have
$\pi^{(n-i+1)}\boldb_{i,l}=\wp_{n-i+1,L}$.  Since relative to the basis
$\boldb_{i,L}$ we have $P_{i}=\pi^{(n-i+1)}$, where $P_{i}$ is from the
definition of the Gram-Schmidt orthogonalization, we have that
$\boldb_{i,L}^{*}=\wp_{n-i+1,L}$.
We have
$\boldb_{i,L}=\calu_{n-1,L}(\ldots  \calu_{n-i+1,L}(\wp_{n-i+1,L})\ldots  )$.
When we apply $\calu_{n-j,L}$ we get the $n-j+1$th coordinate of the
vector $\boldb_{i,L}$ which is $\mu_{i,j}$.  Therefore the definition of
$\calu$ implies that $\mu_{i,j}\in (-{1/ 2},{1/2}]$ and so
$|\mu_{i,j}|\le {1/ 2}$.
\end{proof}
\nev{678}


%%%%%%bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb



\begin{definition}\hfill
\begin{enumerate}
\item Let $\alpha_{k} =\sup
|b_{1}|^{2}/|b_{k}^{*}|^{2} $, where the
supremum is taken over all $k$-dimensional           
lattices $L$ and over all                            
Korkine-Zolotareff bases $b_{1},\ldots  ,b_{k}$ in $L$.
The quantity  
$\alpha_{k}$ is the Korkine-Zolotareff constant.
\nev{680}

\item We define another lattice constant
$\beta_{k}$ which depends on
lattices of dimension $2k$. 
$$
\beta_{k}= \sup\left\lbrace
\Bigl(\bigl(\prod_{i=1}^{k}\Vert b_{i}^{*} 
\Vert^{2}\bigr) \bigl(\prod_{i=k+1}^{2k} \Vert
b_{i}^{*}\Vert \bigr)^{-2}\Bigr)^{{1/ k}} \right\rbrace
$$
where the supremum is
taken over all $2k$-dimensional lattices $L$   
and over all                                   
Korkine-Zolotareff bases $b_{1},\ldots  ,b_{2k}$ of $L$. \nev{684}
\end{enumerate}
\end{definition}

In~\cite{Schnorr} Schnorr proves that $\alpha_{k}\le k^{1+\log k}$ and
asks whether $\alpha_{k}=k^{O(1)}$.
  In \expref{Theorem}{A3} we will show
that actually Schnorr's upper bound is tight namely there is an
$\epsilon>0$ so that $\alpha_{k}>k^{\epsilon \log k }$ for all
$k=1,2,\ldots$.  In \expref{Theorem}{B1} we show that Schnorr's upper bound on
$\beta_{k}$, $\beta_{k}\le 4k^{2}$ is also the best possible apart from
a constant factor in the exponent.  Schnorr's estimate of the
approximation factor of his algorithm depends on the an upper bound on
$\beta_{k}$.  \expref{Theorem}{B1} implies that this analysis cannot be
improved by giving a better upper bound on $\beta_{k}$.  This in itself
does not imply a lower bound on the worst-case performance of the
algorithm.  However based on the probabilistic lattice construction in
the proof of \expref{Theorem}{B1} we will be able to construct a lattice
with a basis which shows that the approximation factor in the worst-case
is the same as in the upper bound apart from a constant factor in the
exponent (\expref{Theorem}{B6} and \expref{Theorem}{B7}). \nev{686}


\begin{theorem} \label{B1} There is
an $\alpha >0$ so that if $c>0$ is a
sufficiently small real number, $n$ is a
positive integer, and $L$ is a random value
of the random variable $\rand_{n,h}$, where
$h(x)=\exp({(cx/  n)} \log n )=
n^{c{x/n}}$, then the following holds: \nev{687} With a probability of at least
$1-\eee^{-\alpha n}$ the sequence
$b_{i}=\boldb_{i,L}$, $i=1,\ldots  ,n$ is a
Korkine-Zolotareff reduced basis of the 
$n$-dimensional lattice $L$.  Moreover the
Gram-Schmidt orthogonalization procedure
applied to the basis $b_{1},\ldots  ,b_{n}$
yields the orthogonal vectors
$b_{i}^{*}=\wp_{n-i+1,L}$, $i=1,\ldots  ,n$.  If
$n=2m$ where $m$ is an integer then we have
\[
\Bigl(\bigl(\prod_{i=1}^{m}\Vert b_{i}^{*}
\Vert^{2}\bigr) \bigl(\prod_{i=m+1}^{2m} \Vert
b_{i}^{*}\Vert \bigr)^{-2}\Bigr)^{{1/ m}} =
n^{2c}\,.
\]
\end{theorem} \nev{688}

This theorem clearly implies \expref{Theorem}{T0}.

\paragraph{Proof of \expref{Theorem}{B1}}

In the proof we will use the following
properties of the lattice $L$, where $L$ is a random value of
$\rand_{n,h}$. \nev{689}

\begin{lemma} \label{H0} Suppose that $n$ is a positive integer, $h$ is
an arbitrary function on the set of positive integers with positive real
values and $L$ is a possible value of the random variable $\rand_{n,h}$.
Then the following requirements are met.
        \nev{690}

\begin{cond} \label{H1} L is a triangular lattice and for all
$i=1,\ldots  ,n $, $ \pi^{(i)}\wp_{i,L}=( 0, \ldots , 0,h(i) ) $
\end{cond}
\nev{694}

\begin{cond} \label{H2} $\calu_{i}(\wp_{i,L})= ( 0,\ldots  ,0,
h(i), \frac{1}{2} h(i+1) ) $ for all $i=1,\ldots  ,n-1$ \end{cond}
\nev{695}

\begin{cond} \label{H3} for all $i=1,\ldots  ,n-1$ and for all integers $t$
we have $\calu_{i}(t\wp_{i,L})= ( 0,\ldots  ,0, th(i), \frac{1}{2}
h(i+1) ) $ \end{cond} \end{lemma}
        \nev{696}

\begin{remark}
In this lemma the function
$h$ is not necessarily the same as
the function defined in \expref{Theorem}{B1}.
\nev{697}
\end{remark}

\begin{proof}
\ref{H1} The triangularity of
$L$ is an immediate consequence of
the definitions of $\rand$ and $\ext$. $\wp_{i,L}$ takes the role of the
vector $( 0,\ldots  ,0, \kappa ) $ in the definition of
$\ext_{i-1,\kappa,\bar L,a}$ where in our case $\bar L=\pi^{(i-1)}(L)$
and $\kappa=h(i) $.
\nev{698}

\ref{H2} By the definition of $\rand_{n,h}$ we have that
$\pi^{(i+1)}(L)=\ext_{n,\kappa,L',a} $, where $\kappa= h(i+1) $,
$L'=\pi^{(i)}(L)$, and $a=\wp_{i,L}=( 0,\ldots , 0, h(i) ) $.
This definition also implies that $( a,\kappa/2) \in
L' $, that is,
$$
\Bigl( 0,\ldots  ,0, h(i), \frac{1}{2} h(i+1) \Bigr)
\in \pi^{(i+1)}(L)\,.
$$
Therefore the definition of $\calu_{i}$ and
$\wp_{i+1,L}=( 0,\ldots , 0, h(i+1) ) $ implies \ref{H2}.
\ref{H3} is an immediate consequence of \ref{H2}.
\end{proof} \nev{699}

We return to the proof of \expref{Theorem}{B1}.  First we estimate the
probability of the following event $A$: ``$\wp_{n,L}$ is not a shortest
nonzero vector in $L$.''  Let $a=( a_{1},\ldots  ,a_{n} )$ be a
sequence of integers.  We estimate the probability of the event $A_{a}$:
``there is an $x\in L$, $x\not=0$ so that $\Vert x\Vert < \Vert
\wp_{n}\Vert $ and $\theta^{(x,L)}=a$.''  Let $\start(a)=i$.  This
implies that $i<n$ otherwise because of $a_{1}=\cdots  =a_{n}=0$ we would
have $x=0$.  The condition $\start(a)=0$ also implies $\pi^{(i)}x=0$,
$\pi^{(i+1)}x\not=0$.  The latter inequality holds since otherwise we
would have $\pi^{(i+1)}x=\calu_{i}(0)+a_{i+1}\wp_{i+1,L}=0$ and
therefore $a_{i+1}\wp_{i+1,L}=0$ which is impossible since $a_{i+1}\not=
0$ and $\wp_{i+1,L}\not=0$.  We distinguish four cases depending on $i$.
\nev{700}

In the proof we will use repeatedly the following simple fact
        \nev{7004}

\begin{cond} \label{B2} If $h(x)=\exp\Bigl(\frac{cx}{n}\log n\Bigr)$ 
then
$h(n-n(\log n)^{-1})=h(n)\eee^{-c}$. \end{cond} \nev{7005}

Case I. $i> n-n(\log n)^{-1} $ or $n<({{5/4}})^{1/(2c)}$.  We
show that in this case $P(A_{a})=0$ since there is no $x\in L$ with
$\Vert x\Vert < \Vert \wp_{n} \Vert $ and $\theta^{x,L}=a$.  Indeed,
assume that there is an $x\in L$ with these properties. $\start(a)=i$
implies $a_{1}=\cdots  =a_{i}=0$ and so according to the definition of
$\theta^{(x,L)}=a$ we have $\pi^{(j)}(x)=0$ for $j=1,\ldots  ,i$.
$a_{i+1}\not=0$ therefore $\pi^{(i)}(x)=0$ implies
$$
\pi^{(i+1)}(x)=a_{i+1}\pi^{(i+1)}\wp_{i+1,L}= ( 0,\ldots  ,0, a_{i+1}
h(i+1) )\,.
$$
If $i=n-1$ this implies $\Vert x\Vert \ge \wp_{n,L}$
in contradiction to our assumption.  Therefore $i<n-1$. \ref{H3}
implies that 
$$
\pi^{(i+2)}(x)=\calu_{i+1}( a_{i+1} \pi^{(i+1)}\wp_{i,L})=
\Bigl( 0,\ldots  ,0, a_{i+1}h(i+1),\frac{1}{2} h(i+2)\Bigr)\,.
$$
Consequently
$$
\Vert x\Vert^{2} \ge \Vert \pi^{(i+2)}x\Vert^{2} \ge
(h(i+1))^{2}+\frac{1}{2} (h(i+2))^{2}= n^{2c\frac{i+1}{n}}+\frac{1}{2}n^{2c\frac{i+2}{n}}\ge {\frac{5}{4}}n^{2c{i/ n}}\,.
$$
So the condition $i>n-n(\log n)^{-1} $ implies that 
$$
\Vert x\Vert^{2}\ge
{\frac{5}{4}}n^{2c{(n-n(\log n)^{-1}) n ^{-1}}} = {\frac{5}{4}}
\exp\left({2c(1- (\log n)^{-1})\log n}\right) = \frac{5}{4}\eee^{2c \log n}\eee^{-2c} >
\eee^{2c\log n}= \Vert \wp_{n,L}\Vert^{2}
$$
in contradiction to our
assumption.  We consider now the condition 
$n<({{5/4}})^{1/(2c)}$.   We have
$$
\log \Vert x\Vert^{2}\ge \log \Bigl({\frac{5}{4}}n^{2c{i/ n}}\Bigr)=
\log {\frac{5}{4}}+2cin^{-1}\log n = 
2c\log n\Bigl(\frac{i}{n}+(2c\log n)^{-1} \log{\frac{5}{4}}\Bigr)\,.
$$  
To give a lower bound on this we use that
$n<({\frac{5}{4}})^{1/(2c)}$ implies 
$(2c \log n)^{-1} \log {\frac{5}{4}} >1$.  
Therefore 
$$
\log \Vert x \Vert^{2}> 2c\log n\Bigl(\frac{i}{n}+1\Bigr)\ge 
2c \log n\ge \log \Vert \wp_{n,L}\Vert^{2}\,.
$$
\nev{706}

Case II. $n-n(\log n)^{-1}\ge i $, $n> ({{5/4}})^{1/(2c)} $ and
$|S_{a}|>(n-i')/10$ where $i'=\max \lbrace i, \lceil {n/
2}\rceil\rbrace $ and $S_{a}= \lbrace j\in [i',n] \mid a_{j}
\not=0\rbrace $.  We show that in this case $P(A_{a})=0$ since there is
no $x\in L$ with $\theta^{x,L}=a$ and $\Vert x\Vert <\Vert \wp_{n}\Vert
$.  Indeed assume that there is an $x\in L$ with these properties.  By
\expref{Lemma}{D1} we have 
\begin{multline*}
\Vert x\Vert^{2} \ge \frac{1}{4}\sum\lbrace
\Vert \wp_{j} \Vert^{2} \mid a_{j}\not=0, j\in [i',n] \rbrace\ge 
\frac{1}{4} |S_{x}|\Vert \wp_{i'}\Vert^{2}\ge  \frac{1}{4}
|S_{x}|(h(i'))^{2}>\\  \frac{1}{4} \frac{1}{10}(n-i')\exp\left({2c\frac{i'}{n}\log n}\right)=  \frac{1}{40}(n-i')\exp({2c \log n})\exp\left({-2c\frac{n-i'}{n}\log n}\right)
\ge\\ \frac{1}{40}(n-i')\exp\left({2c \log n}\right)
\exp\left({-2c\frac{n/2}{n}\log n}\right) \ge
\frac{1}{40}(n-n(\log n)^{-1})\eee^{-c\log n}\Vert \wp_{n,L}^{2} \Vert\,.
\end{multline*}
Since $n>({{5}/{4}})^{1/(2c)} $ and $c$ is sufficiently small we
have $\frac{1}{40}(n-n(\log n)^{-1}) \eee^{-c\log n}\ge 1$ and therefore
$\Vert x\Vert\ge \Vert \wp_{n,L}\Vert $ in contradiction to our indirect
assumption.
                 \nev{707}


Case III. $n-n(\log n)^{-1} \ge i $, $n> ({{5/4}})^{1/(2c)} $,
$|S_{a}|\le (1/10) (n-i')$ and $i>\lfloor {n/2} \rfloor$.
(The last inequality implies $i'=i$.)  For each fixed $i>\lfloor {n/
2}\rfloor, $ we estimate the probability of the event $A_{a} \wedge
\start(a)=i$.  Suppose that $L$ and $a$ are fixed so that there is an
$x\in L$ with $\theta^{(x,L)}=a$, $i=\start(a)$.  By the definition of
$\theta^{(x,L)}$, $x$ is unique with this property.  Let $Q=[i+2,n-1]
\backslash S_{a} $.  If $j\in Q$ then $\theta^{(x,L)}_{j}=a_{j}=0$ and
so $\pi^{(j)}(x)=\calu_{j-1,L}(\pi^{(j-1)}x)$ and therefore by the
definition of $\calu_{j-1,L}$ we have that
$\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}$ for a uniquely defined
$\rho_{j} \in (-{1/2},{1/ 2}] $.  Let $M=h(n)(h(i))^{-1}$ and
let $A_{a}'$ be the event that ``the number of integers $j\in Q$ with
$|\rho_{j}|< (n-i)^{-{1/ 5}}M$ is at least $(n-i) / 2$.''  We show
that $A_{a}$ implies $A_{a}'$ and therefore $P(A_{a})\le P(A_{a}')$,
then we will prove an upper bound on $P(A')$.  Assume that $\neg
A_{a}'$.  Then there are at least $3(n-i)/10$ integers $j\in Q$
so that $|\rho_{j}|\ge (n-i)^{-{1/ 5}} M$. Therefore 
\begin{multline*}
\Vert x\Vert^{2} \ge 
\sum_{j\in Q}\rho_{j}^{2}\Vert \wp_{j}\Vert^{2}
\ge \frac{3}{10}(n-i) (n-i)^{-{2/ 5}}M^{2}(h(i))^{2}
\ge\\ \frac{3}{10}(n-i)^{{3/ 5}}(h(n)(h(i))^{-1})^{2}(h(i))^{2}= 
\frac{3}{10}(n-i)^{{3/ 5}}(h(n))^{2}> \Vert \wp_{n,L} \Vert^{2}\,,
\end{multline*}
that is, $\neg A_{a}$ holds, which completes the proof of 
the implication               
$A_{a}'\Rightarrow A_{a}$.    
\nev{708}

Now we estimate $P(A_{a}')$.  Suppose $j\in Q$. $\rho_{j} $ was defined
by the conditions 
$$
\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}\,,
$$
$\rho_{j} \in (-{1/ 2},{1/ 2}] $.  Therefore the definitions of
$\rand $, $\ext$ and \expref{Lemma}{A0} implies that if $\pi^{(j-1)}(x)$ is
linearly independent of $\wp_{j-1}$ then $\rho_{j}$ 
is uniformly distributed over
$[-{1/ 2},{1/ 2}]$.  However if
$\pi^{(j-1)}(x)\not =0$ and $\wp_{j-1}$ are linearly dependent then by
\ref{H1} $\start(a)= j-1$.  Since $i=\start(a)$, $i\le j$, $Q\subseteq
[i+2, n]$ this contradicts to $j\in Q$. Therefore the distribution of
$\rho_{j}$ is uniform over $ [-{1/ 2},{1/ 2}] $.  The definition
of $\rand $ implies that random variables $\rho_{j}$, $j\in Q$ are
mutually independent.  Therefore the probability that ``the number of
integers $j\in Q$ with $|\rho_{j}| < (n-i)^{-{1/ 5}}M$ is at least
$({n-i })/{ 2}$'' is no more than $2^{n-i}(2(n-i)^{-{1/
5}}M)^{{1/ 2}(n-i)} $.  We get that
\nev{709}

\begin{cond} \label{H5} $P(A_{a})\le P(A_{a}') \le
2^{n-i}(2(n-i)^{-{1/ 5}}M)^{{1/ 2}(n-i)} $. \nev{740} \end{cond}

\begin{definition}
Assume that $n$ is a positive integer $h$ is an arbitrary
function defined on the set of positive integers with positive real
values, $L$ is a possible value of the random variable $\rand _{n,h}$
and $a=( a_{1},\ldots  ,a_{n}) $ is a sequence of integers.  We
say that the sequence $a$ is acceptable if there is at least one
possible value $L$ of the random variable $\rand_{n,h}$ and an $x\in L$
with $a=\theta^{x,L} $ and $\Vert x\Vert < \Vert \wp_{n}\Vert $.
\end{definition}
\nev{744}

The following lemma is an estimate on the number of acceptable
sequences.  It was formulated and proved, in a somewhat different
context and with different terminology, by R.~Kannan in~\cite{Kannan}.
These differences however do not affect the validity of the upper bound
and its proof.
                    \nev{745}

\begin{lemma}[Kannan] \label{B3}  Assume that $c>0$ and
$n,i$, $i\le n$ are positive integers, $h$ is an arbitrary function
defined on the set of positive integers with positive real values, $L$
is a possible value of the random variable $\rand _{n,h}$ and $a=(
a_{1},\ldots  ,a_{n}) $ is an acceptable sequence with $\start(a)=i$.
Then for all $j=i,\ldots  ,n$ we have $|a_{j}|< h(n)(h(j))^{-1}$.  Moreover
the number of acceptable sequences with $\start(a)\ge i$ is at most
$$
\prod_{j=i}^{n}(1+2 h(n)(h(j))^{-1})\le 3^{n-i}\prod_{j=i}^{n}(
h(n)(h(j))^{-1})\,.
$$  \nev{746}\end{lemma}

\begin{remark}
In this lemma the function $h$
is not necessarily the same as
in \expref{Theorem}{B1}. \nev{747}
\end{remark}

\begin{proof}[Proof of \expref{Lemma}{B3}]  Assume
that $a$ is an acceptable sequence and
let $L$ be a value of $\rand_{n,h}$ where there is an $x\in L$ with
$\Vert x\Vert\le \wp_{n,L} $ and $\theta^{(x,L)}=a$.  According to the
definition of $a_{j}$ we have $\pi^{(j)} (x)=(\calu_{j-1,L}(\pi^{(j-1)}x
))+a_{j}\wp_{j,L}$.  Therefore 
$$
{h}(n)= \Vert \wp_{n,L}\Vert >\Vert
x\Vert \ge \Vert \pi^{(j)}x \Vert \ge |a_{j}|\Vert \wp_{j}\Vert =
|a_{j}| {h}(j)
$$
which implies the inequality $|a_{j}|<
{h}(n)({h}(j))^{-1}$. \nev{748}

If $a$ is an acceptable sequence with $\start(a)\ge i$ then $a_{j}=0$
for all $j=1,\ldots  ,i$.  By the inequality proven above, for each $j>i$ the
number of choices for $a_{j}$ is at most $1+2{h}(n)({h}(j))^{-1}$.
\nev{749}
\end{proof}

We continue now the proof of Case III. For a fixed $i>{n/ 2}$ let
$p_{i}$ be the probability of the following event: there is an
acceptable sequence $a$ so that $A_{a}$.  Clearly 
$$
p_{i} \le \sum
\lbrace P(A_{a}) \mid \text{$a$ is acceptable and $i=\start(a)$}\rbrace\,.
$$
Using
our upper bound \ref{H5} on $P(A_{a})$ and the upper bound 
in \expref{Lemma}{B3} for the number of acceptable sequences we get 
$$
p_{i}\le
2^{n-i}(2(n-i)^{-{1/5}}M)^{(n-i)/2} 3^{n-i}\prod_{j=i}^{n}
\left({h}(n)({h}(j))^{-1}\right)\,.
$$
Using that for all $j\in [i,n]$ we have
${h}(n)({h}(j))^{-1}\le {h}(n)({h}(i))^{-1}=M$ we get that
$$
p_{i}\le
3^{n-i}2^{(n-i)/2} M^{3(n-i)/2}(n-i)^{-(n-i)/10}\,.
$$
We give an upper bound on $M$.
$$
M=h(n)/h(i)=
\exp\left({c\frac{n-i}{ n}\log n}\right)= 
\exp\left({c\frac{n-i}{ n}(\log\frac{n}{ n-i}+ \log(n-i))}\right)\,.
$$  
Since the
function $(1 / x) \log x $ takes its maximum at $x=\eee$ in the interval
$[1,\infty )$, we have that $(1/x) \log x \le 1/\eee < 1$ if
$x\ge 1$.  This yields 
$$
M\le \eee^{c}\exp\left({c\frac{n-i}{ n} \log(n-i)}\right)\le
\eee^{c}\eee^{c\log(n-i)}\le \eee^{c}(n-i)^{c}\,.
$$
Substituting this into the
upper bound on $p_{i}$ and using that $c$ is sufficiently small we get
$p_{i}\le (n-i)^{-(n-i)/20}$.  Therefore the probability that
there is an $i$ so that $A_{a}$ holds for a suitably chosen $a$ is at
most 
$$
\sum_{i={n/2}}^{n-n(\log n)^{-1}} (n-i)^{-(n-i)/20}\,.
$$
It is easy to see that in this sum the largest term (with
$i=n-n(\log n)^{-1}$) is greater than the sum of the others.  So we get
$$
p_{i}\le 2\Bigl(\frac{n}{ \log n}\Bigr)^{- {1/ 20}\frac{n}{\log n} }\le
2\exp\left({-\frac{1}{ 20}{n-n\log \log n(\log n)}^{-1}}\right)
\le \eee^{-n/21}\,.
$$
\nev{750}

Case IV. $n> ({{5/ 4}})^{1/(2c)} $, $|S_{a}|\le 
(n-i')/10$ and $i\le \lfloor {n/2} \rfloor $.  (The last inequality
implies $i'= \lfloor {n/ 2} \rfloor $.)
                \nev{754}

For each acceptable sequence $a$ with $\start(a)\le {n/ 2}$ we will
give an upper bound on the probability of the event $A_{a}$.  Then we
will estimate the number of acceptable sequences with this property.
\nev{756}

Suppose that $L$ and $a$ are fixed so that there is an $x\in L$ with
$\theta^{(x,L)}=a$.  We have
$$
\pi^{(j)}(x)=(\calu_{j-1,L}(\pi^{(j-1)})x)+ a_{j}\wp_{j}
$$
for all
$j=0,\ldots  ,n-1$.  Let $Q=[{n/ 2},n-1]\backslash S_{a} $.  If $j\in Q$
then 
$$
\theta^{(x,L)}_{j}=a_{j}=0 \quad \text{and so}\quad
\pi^{(j)}(x)=\calu_{j-1,L}(\pi^{(j-1)}x)
$$
and therefore by the
definition of $\calu_{j-1,L}$ we have that
$\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}$ for a uniquely defined
$\rho_{j} \in (-{1/ 2},{1/ 2}] $.  Let $A_{a}'$ be the event
that ``the number of integers $j\in Q$ with $|\rho_{j}|< n^{-\tau}$ is
at least $n/4$,'' where $\tau<1/4$ is chosen so that $c$ is
sufficiently small with respect to $\tau$.  (This definition is somewhat
different from                    
the corresponding definition in Case III.)  We show that
$A_{a}$ implies $A_{a}'$ and therefore $P(A_{a})\le P(A_{a}')$;
then we will prove the claimed upper bound on $P(A')$.
\nev{757}

Assume that $\neg A_{a}'$.  Then there are at least $n/5$
integers $j\in Q$ so that $|\rho_{j}|\ge n^{-\tau} $.  Therefore 
\begin{align*}
\Vert
x\Vert^{2} \ge \sum_{j\in Q}\rho_{j}^{2}\Vert \wp_{j}\Vert^{2} &
\ge  \frac{1}{5}n n^{-2\tau}\Bigl(\frac{hn}{2}\Bigr)^{2}= \frac{1}{5}
n^{1-2\tau}\Bigl(\frac{hn}{2}\Bigr)^{2} \\ &= \frac{1}{5}
n^{1-2\tau}\exp\left({-2c\frac{n-(n/2)}{n}\log n}\right)= 
\frac{1}{5} n^{1-2\tau} n^{-c}\,.
\end{align*}
Since $\tau<{1/ 4}$ and $c>0$ is sufficiently small with
respect to $ \tau$ this implies that $\Vert x\Vert^{2} >n^{2c} =
({h}(n))^{2}= $ $\wp_{n}^{2} $, that is, $\neg A_{a}$ holds, which
completes the proof of 
the implication                  %% LB the implication added
$A_{a}'\Rightarrow A_{a}$.       %% LB \rightarrow --> \Rightarrow 
\nev{756}

In Case III we have seen that the random variables $\rho_{j}$ are
independent and 
%% LB5 each have uniform distribution on -->
uniformly distributed over 
$[-{1/ 2}, {1/2}] $.  
Therefore the probability that ``the number of integers $j\in Q$
with $|\rho_{j}| < n^{-\tau}$ is at least ${n / 4}$'' is no more
than $2^{n/ 2}(2n^{-\tau})^{{n/ 4}} $.  We get that
\nev{757}

\begin{cond} \label{H6} $P(A_{a})\le P(A_{a}') \le 2^{n/
2}(2n^{-\tau})^{{n/ 4}} $. \nev{758} \end{cond}

Now we estimate the number of acceptable sequences with $\start(a)\le
n/2$.  This is no more than the total number of acceptable
sequences without any restrictions.  By \expref{Lemma}{B3} this number is
at most $\prod _{j=1}^{n}3^{n}h(n)(h(j))^{-1}$.  Therefore if $p$ is the
probability of the event that there is an acceptable sequence $a$ so
that $\start(a)\le n / 2$ and $A_{a}$ holds then using our upper
bounds we get
$$
p\le 2^{n/ 2}(2n^{-\tau})^{{n/ 4}}
3^{n}\prod_{j=1}^{n}( {h}(n)({h}(j))^{-1})\,.
$$
Using that
$h(j)=\exp\left(({c{j/ n})\log n}\right)$ 
we can calculate the value of the product exactly: 
$$
\prod_{j=1}^{n}({h}(n)({h}(j))^{-1})= 
(\eee^{c\log n})^{n} \exp\left({-c\frac{n(n+1)}{2n}\log n}\right)= 
 \exp\left({c \frac{n-1}{2} \log n}\right)\,.
$$
\nev{759}

Substituting this inequality in the upper bound on $p$ we get: 
$$
\log
p\le \frac{n}{2}\log 2 - \tau(\log n+\log 2)\frac{n}{4}+ n\log 3 + c\frac{n-1}{2}\log n\,.
$$
Since $c>0$ is sufficiently small with respect to
$\tau$ the term $-(\tau {n/ 4})\log n$ will dominate in absolute
value therefore $p\le n^{-\tau n/8}$.  This is our upper bound
on the probability that there is an $x\in L\backslash \lbrace 0, \pm
\wp_{n,L}\rbrace $ with $\Vert x\Vert \le \Vert \wp_{n,L} \Vert $.
\nev{760}

Summarizing the results of the four different cases we get the
following:
\nev{764}

\begin{lemma} \label{B5}  If $L$ is the random lattice defined in
\expref{Theorem}{B1}, then the probability that $\wp_{n,L}$ is not a
shortest nonzero vector of $L$ is at most $3\eee^{-n/21}$.
\nev{765} \end{lemma}


Suppose that $L$ is a random value of
$\rand_{n,{h}}$.  We show now that with
high probability for all $i=1,\ldots  ,n$,
$\wp_{i,n}$ is a shortest nonzero vector in
$\pi^{(i)}(L)$.  Indeed if we multiply
every element of $\pi^{(i)}L$ by the number
$h(n)(h(i))^{-1}$ we get an $i$-dimensional
triangular lattice $K$.  We have
$\wp_{j,K}=h(n)(h(i))^{-1}\wp_{j,L}$ for
all $j=1,\ldots  ,i$.  Therefore 
\begin{align*}
\Vert
\wp_{j,K} \Vert = h(n)(h(i))^{-1} \Vert
\wp_{j,L} \Vert &= \exp\left({c\frac{n}{n} \log n}\right)  %%% ** n/n ?? ** %%
\exp\left({-c\frac{i}{n}\log n }\right)
\exp\left({c\frac{j}{n} \log n}\right)\\ &= 
\exp\left({c\frac{n-(i-j)}{n}\log n}\right) =h(n-(i-j))\,.
\end{align*}
Therefore $\Vert \wp_{i,K}\Vert =h(n)$, $\Vert
\wp_{i-1,K}\Vert =h(n-1)$, \ldots  ,$\Vert
\wp_{1,K}\Vert =h(n-i+1)$.  This and the
definition of $\rand$ implies that the
lattice $K$ can be embedded into another
triangular lattice $J$ so that
$\wp_{i,K}=\wp_{n,J},
\wp_{i-1,K}=\wp_{n-1,J}, 
\ldots  ,\wp_{1,K}=\wp_{1+(n-i),J} $ and $J$ is
a random value of $\rand_{n,h}$.  \expref{Lemma}{B5} implies that with a probability
of at least $1-3\eee^{-n/21}$ we have
that 
$\wp_{n,J}=\wp_{i,K}=h(n)(h(i))^{-1}\wp_{i,L}$ 
is a shortest nonzero vector in $J$.
Suppose that for some outcome of the
randomization it is a shortest nonzero
vector in $J$.  Since $K\subseteq J$, it is
also a shortest nonzero vector in $K$ and
finally since $\pi^{i}(L)=h(n)^{-1}(h(i))K
$, the vector $\wp_{i,L}=
h(n)^{-1}(h(i))\wp_{i,K} $ is a shortest
nonzero vector in $\pi^{i}(L)$ with a
probability of at least $1-3\eee^{-n/21}$.  
The probability that this happens for
all $i=1,\ldots  ,n$ simultaneously is at least
$1 -3n\eee^{-n/21}\ge $ 
$1-\eee^{-n/22}$ if $n $ is sufficiently large.  
The definition of the
basis $b_{i}=\boldb_{i,L}$ implies that
$\pi^{(i)}b_{n-i+1}=\wp_{i,L}$, therefore
if we apply the Gram-Schmidt
orthogonalization procedure to the basis
$b_{i}$ then we get $b_{i}^{*}=\wp_{i}$ and
so the probability that $b_{i}$ is a
Korkine-Zolotareff basis is at least 
$1-\eee^{-n/22}$. Now  
$$
\Vert \wp_{j,L}\Vert =h(j)=
\exp\left({c\frac{j}{n}\log n}\right)
$$
implies the last equation of the Theorem.

This concludes the proof of \expref{Theorem}{B1} 
(and \expref{Theorem}{T0}). \nev{766}

\begin{definition}
Assume that $B=( b_{1},\ldots  ,b_{n} ) $ is a basis
of the lattice $L$ and $1\le i\le n$.  Then $P_{i}^{(B)}$ will denote
the orthogonal projection of $L$ onto the subspace orthogonal to
$b_{1},\ldots  ,b_{i-1}$.
\end{definition}
\nev{767}

\begin{theorem} \label{B6} There exists an $\alpha>0$, so that if $c>0$
is sufficiently small, $k,n$ are positive integers $2\le k\le n$, and
$L$ is a random value of $\rand_{n,g}$ where 
$g(j)=\exp (({c{j/ k})\log k})$, 
$b_{i}=\boldb_{i,L}$ for $i=1,\ldots  ,n$, and $B=(
b_{1},\ldots  ,b_{n}) $, then the following holds.  Assume that $p_{n,
k}$ is the probability of the following event: ``For all $i=1,\ldots  ,n-k$
the orthogonal projections of
$P_{i}^{(B)}b_{i},\ldots  ,P_{i}^{(B)}b_{i+k-1}$ is a Korkine-Zolotareff
basis of the $k$-dimensional lattice generated by these vectors.''
\nev{777} Then $p_{n,k}\not=0$ and $p_{n,k}\ge 1-(n-k) \eee^{-{\alpha} k} $.
\nev{778}\end{theorem}

\begin{proof}
The second inequality is an
immediate consequence of \expref{Theorem}{B1}.  Indeed for a fixed $i$ let $K$ be the lattice generated by
$P_{i}^{(B)}b_{i},\ldots  ,P_{i}^{(B)}b_{i+k-1}$.  Clearly
$P_{i}^{(B)}b_{i}=\pi^{(i)}b_{i}$.  Therefore 
$$
\exp\left({c\frac{k-i}{k} \log k}\right)K
$$ 
is a value of the random variable $\rand_{k,h}$ where
$h(j)=\exp\left(({c{j/ k})\log k}\right)$.  
Therefore, by \expref{Theorem}{B1}, the
probability that $P_{i}^{(B)}b_{i},\ldots  ,P_{i}^{(B)}b_{i+k-1}$ is not a
Korkine-Zolotareff basis is at most $\eee^{-{\alpha} k}$.  The fact that
there are at most $n-k $ choices for $i$ implies the second inequality
in the conclusion of the theorem.
        \nev{779}

If $n$ is sufficiently large with respect to $k$ then the proven second
inequality does not imply $p_{n,k}\not = 0$.  Still it can be shown by
the Lov\'asz Local Lemma that it holds.  Actually the present situation is
a very simple special case of Lov\'asz's lemma so a direct proof and a
corresponding probabilistic construction can be easily given based on
the following observation. \nev{780}

Let $0<\epsilon <{1/ 10}$.  Suppose that $Q(x,y)$ is a binary
relation on the finite set $A$ so that if $x,y$ are chosen at random,
independently and with uniform distribution from $A$ then $P(Q(x,y))>
1-\epsilon$.  For each $\tau>0$ let $A_{\tau}$ be the set of all $x\in A
$ with the property that if we take a random $y \in A$ with uniform
distribution then $P(Q(x,y))\ge 1- \tau$.  Then $|A|^{-1}|A_{\tau}|\ge
1-{\epsilon / \tau}$.  Indeed if we count the number of pairs
$( x,y) $ with $\neg Q(x,y)$ for all $x\in A\backslash
A_{\tau}$ together then we get that this number is at least
$(|A|-|A_{\tau}|)\tau |A|$.  On the other hand from our assumption we
know that this number is at most $\epsilon |A|^{2}$ which implies that
claimed inequality.
        \nev{784}

If we pick now $\tau = \sqrt{\epsilon}$ then we have
$|A|^{-1}|A_{\tau}|\ge 1-\sqrt{\epsilon}$.  Therefore for each $x\in
A_{\tau}$ the number of elements $y\in A_{\tau}$ with $Q(x,y)$ is at
least $|A|-2\sqrt{\epsilon}|A|$.  This implies that if $x_{0}\in
A_{\tau}$ then we may pick a sequence of elements
$x_{0},x_{1},x_{2},\ldots  ,x_{m}$ recursively (for an arbitrary $m$) so that
for all $i=1,\ldots  ,m$, $x_{i}\in A_{\tau}$ and $Q(x_{i-1},x_{i})$.  This
recursive construction can be turned into an algorithm if the validity
of the relation $Q(x,y)$ can be algorithmically decided.  This implies
that although we may not be able to decide with high probability whether
an element is in $A_{\tau}$ but we can tell about all of the elements of
$A_{\tau/2}$ with high probability that they are in $A_{\tau}$.
Therefore picking random elements and testing them whether they are in
$A_{\tau}$ (with high probability) we can build the sequence
$x_{0},x_{1},\ldots  ,x_{m}$.
\nev{785}

This recursive procedure makes it possible to prove the existence of a
basis with high probability and with the required properties even in the
case when $k$ is small compared to $n$.  To get a construction we need
that for dimension at most $k$ we are able to verify whether a given
vector is a nonzero shortest vector of the lattice.  However if we are
able to perform Schnorr's algorithm with parameter $k$, then we have
already this ability.  (By polynomial time computation we can find the
shortest vector in dimension $O(\log n)$.  This seems to match the lower
bound for the $k$ where with high probability we get Korkine-Zolotareff
bases in all of the blocks of length $k$.  However it is not clear
whether the constant factors of $\log n$ in the bounds really overlap.)
\end{proof}
\nev{786}

\begin{theorem} \label{B7} There exist $\epsilon>0,\epsilon'>0$ so that
for all positive integers $k,n$, $k\le \epsilon' n$, there is an
$n$-dimensional lattice $L$ and a basis $b_{1},\ldots  ,b_{n}$ in $L$ so that
if $b_{1}^{*},\ldots  ,b_{n}^{*}$ are the orthogonal vectors that we get
through Gram-Schmidt orthogonalization from the basis $b_{1},\ldots  ,b_{n}$
then the following holds.  For each $s=1,\ldots  ,n-2k-1$ we have
$$
\Bigl(\bigl(\prod_{i=s+1}^{k}\Vert b_{i}^{*} \Vert^{2}\bigr) \bigl(\prod_{i=s+k+1}^{2k}
\Vert b_{i}^{*}\Vert \bigr)^{-2}\Bigr)^{{1/ k}} \le k^{\epsilon \log k}\,,
$$
$\Vert b_{1}\Vert /\lambda_{1}(L)\ge k^{\epsilon \frac{n}{ k} } $, where
$\lambda_{1}(L)$ is the length of the shortest nonzero vector in $L$.
\nev{787} \end{theorem}

\begin{proof} $L$ will be a lattice whose
existence is guaranteed by \expref{Theorem}{B6} with $2k$ in the place of $k$.
We have 
$$
\Vert
b_{i}^{*}\Vert=g(n-i+1)= \exp\left({c\frac{n-i+1}{ 2k}\log 2k}\right)\,.
$$  
This implies
the first inequality.  According to Minkowski's convex body theorem we
have 
$$
\lambda_{1}(L)\le n^{1/2}(\det(L))^{1/n}=n^{1/2}
\Bigl(\prod_{i=1}^{n}\Vert b_{i}^{*}\Vert \Bigr)^{1/n}\,.
$$
Using that and
$k\le \epsilon' n$ we get $\Vert b_{1}\Vert /\lambda_{1}(L)\ge
k^{\epsilon {n/k} } $. \nev{788}
\end{proof}


\section{\label{S2}  The lower bound on the
Korkine-Zolotareff constant $\alpha_{k}$}

\begin{definition}  For each positive
integer $k
$ and real number $c$ we define a function
$\calf_{k,c}$ whose domain is the set of
all positive integers.  For all $i=1,\ldots  ,k$
let $\calf_{k,c}(i)=\eee^{c(\log k)^{2}}$ and
for all $i=k,k+1,\ldots  $ let
$\calf_{k,c}(i)=\eee^{c(\log i)^{2}}$.
\end{definition}
\nev{789}

\begin{theorem} \label{A3} Assume that $c>0$ is a sufficiently
small real number and $c_{1}>0$ is a sufficiently large positive
integer.  For all $n=1,2,\ldots $ if $L$ is a random value of the random
variable $\rand_{n,\calf_{c_{1},c}}$ then the following holds.
With a probability of at least $1/ 2$ the sequence
$b_{i}=\boldb_{i,L}$, $i=1,\ldots  ,n$ is a Korkine-Zolotareff reduced basis
of the $n$-dimensional lattice $L$.  Moreover the Gram-Schmidt
orthogonalization procedure applied to the basis $b_{1},\ldots  ,b_{n}$
yields the orthogonal vectors $b_{i}^{*}=\wp_{n-i+1,L}$, $i=1,\ldots  ,n$.
If $n$ is sufficiently large with respect to $c_{1}$ and $c$ then we
have $\Vert b_{1}\Vert \Vert b_{n}^{*}\Vert^{-1}\ge n^{c\log n}c_{1}^{-c
\log c_{1}}$.\nev{794}
\end{theorem}


\expref{Theorem}{A3.1} formulated in \expref{Section}{S1} is an immediate
consequence of \expref{Theorem}{A3}. 

\paragraph{Proof of \expref{Theorem}{A3}.} In the following
lemma we summarize
some of the elementary properties of the function $\calf_{k,c}$.
%% $\calf_{k,c}$z.
                                                  \nev{796}

\begin{lemma} \label{D3} There exist $\alpha_{1}>0,\alpha_{2 }>0$ so
that if $0<c <1$ and $k$ is a positive integer then there is an 
$\alpha_{3}>0$ so that for all positive integers $n$, $i$, $n\ge i$ the
following inequalities hold.
\nev{797}

\begin{cond} \label{D3.1} if $i\ge \frac{n}{2}$ then \nev{798}

$$ \calf_{k,c}(n) (\calf_{k,c}(i))^{-1}\le \alpha_{1} 
  n^{2c\log({n/i})} \, ; $$

if $i\ge \frac{n}{2} >k $ then \nev{799}

$$ \calf_{k,c}(n) (\calf_{k,c}(i))^{-1}\ge \alpha_{2} 
 n^{2c\log({n/i})} \, ; $$ \end{cond}

\begin{cond} \label{D3.2} for all $\delta>0$ if $c>0$ is sufficiently
small and $\max \lbrace i,k \rbrace \ge {n- {2 \log n}}$ then \nev{800}
$$(1-\delta) \calf_{k,c}(n) \le \calf_{k,c}(i) \, ;$$ \end{cond}

\begin{cond} \label{D3.4} if $0<\xi<1$, $c$ is sufficiently small with
respect to $\xi$, $n$ is sufficiently large with respect to $c$ and
$\xi$, $ {n/ 2}<i<n-\log n$ then 
$\calf_{k,c}(n)(\calf_{k,c}(i))^{-1} \le (n-i)^{\xi}$ . \nev{804}
\end{cond}
\end{lemma}

\begin{proof}
\ref{D3.1}. $\alpha_{1}$ and
$\alpha_{2}$ are chosen when $c$
and $k$ are already fixed so we may assume that $i$ and $n$ are
sufficiently large with respect to $c$ and $k$.  Therefore
$\calf_{k,c}(n)= \eee^{c(\log n)^{2}}$ and 
$\calf_{k,c}(i)=\eee^{c(\log i)^{2}}$. 
\begin{align*}
c(\log n)^{2} &= c\Bigl(\log i +\log\frac{n}{i}\Bigr)^{2} =  c(\log
i)^{2} +2c\log i\log \frac{n}{ i}+ c\Bigl(\log \frac{n}{i}\Bigr)^{2}\\ &= c(\log
i)^{2} +2c\log n \log \frac{n}{i}+ 2c(\log i -\log n) \log \frac{n}{ i} +
c\Bigl(\log \frac{n}{i}\Bigr)^{2}\,.
\end{align*}
The assumption $n\ge i\ge {n/ 2}$ implies
that the absolute values of the last two terms remain below an absolute
constant.  Therefore the ratio of $\calf_{k,c}(n)n^{-2c \log ({n/ i})}$ and 
$\calf_{k,c}(i)$ remains between two positive constants.
                                      \nev{805}

\ref{D3.2}.
We have
\begin{multline*}
\calf_{k,c}(n-2\log n) = 
\exp\left({c(\log (n-2 \log n))^{2}}\right) \\= 
\exp\left({c \Bigl(\log \Bigl(n\Bigl(1-\frac{2 \log n }{n}
\Bigr)\Bigr)\Bigr)^{2}}\right) =  
\exp\left({c\Bigl( \log n + \log\Bigl(1- \frac{2\log n}{n} 
\Bigr)\Bigr)^{2 }}\right) \\=  \eee^{c(\log n)^{2}}
\exp\left({2c \log n \log\Bigl(1-\frac{2\log n}{n}\Bigr)
 + \Bigl(\log\Bigl(1-\frac{2\log n}{n}\Bigr)\Bigr)^{2} }\right)\,.
\end{multline*}
\nev{806}

The assumption that $c>0$ is sufficiently small implies that we may
assume that $n$ is sufficiently large.  Since $|\log (1- ({2 \log n})/{
n})|< 2 {(2/n) \log n}$ the exponent in the second factor remains
below $\epsilon$ in absolute value for any $\epsilon>0$ if $n$ is
sufficiently large and the first factor is $\calf_{k,c}(n)$.  Since
$\calf_{k,c}(i)$ is monotone in the interval $[n-2\log n,n]$ this
implies \ref{D3.2}.
\nev{807}


\ref{D3.4}.  Inequality \ref{D3.1} implies that there is an absolute
constant $c_{2}>0$ so that
$$\calf_{k,c}(n)(\calf_{k,c}(i))^{-1} \le
c_{2}n^{2c\log({n/i})}\,.
$$
Therefore we have to prove that
$(n-i)^{\xi}c_{2}^{-1}n^{-2c\log({n/i})}\ge 1 $ provided that
${n/ 2} \le i< n-\log n$, $c>0$ is sufficiently small with respect
to $\xi$ and $n$ is sufficiently large with respect to $c$ and $\xi$.
Taking the logarithm of both sides of the inequality we get 
$$
\xi \log
(n-i) -\log c_{2}-2c\log n(\log n -\log i)\ge 0\,.
$$
We consider the left
hand side as a function of $i$.  Let $f(x)=\xi \log (n-x) -\log
c_{2}-2c\log n(\log n -\log x)$.  The derivative of $f$ is
$$
f'(x)=-\frac{\xi}{ n-x}+\frac{2c \log n}{x}\,.
$$
The function $f'(x)$ is
continuous on the interval $[{n/ 2}, n-1]$ and it has a single root
$$
x_{0}=\frac{n}{1+ \xi/(2c \log n)}
$$
 in it (for this latter fact we
use that $n$ is sufficiently large with respect to $c$).  Therefore
$f'({n/ 2})>0$ and $f'(n-1)<0$ implies that the function $f$ is
increasing from ${n/ 2}$ till $x_{0}$ and then it is decreasing from
$x_{0}$ till $n-1$.  So we can prove our inequality $\xi \log (n-i)
-\log c_{2}-2c\log n(\log n -\log i)\ge 0$ for all $i\in [{n/ 2},
n-\log n ]$ by checking it at the endpoints.  If $i={n/ 2}$ then
$\log n -\log i\le \log 2$ and $\log (n-i)\ge ({1/ 2})\log n$,
therefore the assumption that $c$ is sufficiently small with respect to
$\xi $ implies the inequality.  If $i=n-\log n$ then $\log n -\log i <
2n^{-1}\log n $ so the term containing $(\log n -\log i) $ is negligible
compared to $\xi \log (n-i)\ge \xi \log\log n$.
\end{proof} 
\nev{807}

In this proof we will write $\calf$ for
$\calf_{c_{1},c}$. First we estimate the probability of the following
event $A$: ``$\wp_{n,L}$ is not a shortest nonzero vector in $L$.''  Let
let $a=( a_{1},\ldots  ,a_{n} )$ be a sequence of integers.  We
estimate the probability of the event $A_{a}$: ``there is an $x\in L$,
$x\not=0$ so that $\Vert x\Vert < \Vert \wp_{n}\Vert $ and
$\theta^{(x,L)}=a$.''  Let $\start(a)=i$. 
Then $A_a$ implies     
that $i<n$
(otherwise we would have $x=0$).  We also have $\pi^{(i)}(x)=0$,
$\pi^{(i+1)}(x)\not=0$.  We distinguish four cases depending on $i$;
in each case, we shall estimate $P(A_a)$.      
        \nev{808}

Case I. $\max \lbrace i,c_{1} \rbrace >n-(\log n)^{2}$.  We show that in
this case $P(A_{a})=0$ since there is no $x\in L$ with $\Vert x\Vert <
\Vert \wp_{n} \Vert $ and $\theta^{x,L}=a$.  Indeed assume that there is
an $x\in L$ with these properties. $\start(a)=i$ implies
$a_{1}=\cdots  =a_{i}=0$ and so according to the definition of
$\theta^{(x,L)}=a$ we have $\pi^{(j)}(x)=0$ for $j=1,\ldots  ,i$.
$a_{i+1}\not=0$ and $\pi^{(i+1)}(x)=a_{i+1}\pi^{(i+1)}\wp_{i+1,L}=
( 0,\ldots  ,0, a_{i+1} \calf(i+1) ) $.  If $i=n-1$ this implies
$\Vert x\Vert \ge \wp_{n,L}$ in contradiction to our assumption.
Therefore $i<n-1$. \ref{H3} implies that 
$$
\pi^{(i+2)}(x)=\calu_{i+1}(
a_{i+1} \pi^{(i+1)}\wp_{i,L})= ( 0,\ldots  ,0,
a_{i+1}{\calf}(i+1),\frac{1}{2} {\calf}(i+2))\,.
$$
Consequently
$$
\Vert x\Vert^{2} \ge \Vert \pi^{(i+2)}x\Vert^{2} \ge
({\calf}(i+1))^{2}+\frac{1}{ 4} ({\calf}(i+2))^{2}\,.
$$
So the assumption
$\max \lbrace {i,c_{1}}\rbrace >n-(\log n)^{2}$ and \ref{D3.2} implies
that $\Vert x\Vert^{2}\ge ({\calf}(n))^{2}= \Vert \wp_{n,L}\Vert^{2} $
in contradiction to our indirect assumption.
\nev{809}

Case II. $n-(\log n)^{2}\ge \max \lbrace i, c_{1} \rbrace $ and
$|S_{a}|>({1}/{10}) |n-i'|$ where $i'=\max \lbrace i, \lceil 
{n/ 2}\rceil\rbrace $ and $S_{a}= \lbrace j\in [i',n] \mid  a_{j}
\not=0\rbrace$.  In this   
case we will use the following inequality:
\nev{840}

\begin{cond} \label{P4} for all $\gamma >0$, for all $c$ with
$0<c<{1/ 20}$, for all sufficiently large $n$ and for all $x$ with
${n/ 2}\le x <n - (\log n)^{2}$ we have 
$(n-x)n^{-4c\log({n/x})}>\gamma$. \nev{844}\end{cond}

Taking the logarithm of the left hand side of the inequality we get
$\ell=\log (n-x) -4c \log n (\log n -\log x)$.  Since $x\ge {n/ 2}$ we
have $\log n -\log x= \int _{x}^{n} {1/ y}\, dy \le 
\int_{x}^{n}{1/ (n/2)}\,dy= 2n^{-1}(n-x) $.  This implies that $\ell\ge 
\log (n-x)-8cn^{-1}(n-x)\log n$.  If $n-x\le \sqrt {n}$ then the assumption
$x<n-(\log n )^{2}$ implies that $\ell\ge \log((\log n)^{2})-
8cn^{-1}n^{1/2}\log n\ge \log \gamma $ if $n$ is sufficiently
large.               \nev{845}


If $n-x \ge \sqrt {n}$ then $\ell\ge ({1/ 2 })\log n - 
8cn^{-1}n\log n\ge$ 
$ ({1/2 })\log n - 8c\log n $.  Since $c<{1/ 20}$ this implies
that $\ell\ge \log \gamma$ which completes the proof of \ref{P4}.
\nev{846}


We return now to the discussion 
of Case II. We show that in this case again  
$P(A_{a})=0$ since there is no $x\in L$ with $\theta^{x,L}=a$ and $\Vert
x\Vert <\Vert \wp_{n}\Vert $.  Indeed assume that there is an $x\in L$
with these properties.  By \expref{Lemma}{D1} and \expref{Lemma}{D3} we have
\begin{align*}
\Vert x\Vert^{2} &\ge \frac{1}{4}\sum\lbrace \Vert \wp_{j} \Vert^{2} \mid
a_{j}\not=0, j\in [i',n] \rbrace\ge \frac{1}{4} |S_{x}| \cdot \Vert
\wp_{i'}\Vert^{2}\ge |S_{x}|(\calf(i'))^{2}  \\ &> \frac{1}{4}
\alpha_{1}^{2}\frac{1}{10}(n-i')n^{-4c\log({n/i'})}(\calf(n))^{2}= 
\alpha_{1}^{2}\frac{1}{40}(n-i')n^{-4c\log({n/i'})}\Vert \wp_{n}
\Vert^{2}\,.
\end{align*}
Since $i'\ge {n/ 2}$ and $c$ is sufficiently small,
inequality \ref{P4} is applicable with 
the substitutions                      
$x := i'$, $\gamma := 40\alpha_{1}^{-2}$ 
and we get $\Vert x \Vert^{2}\ge \Vert
\wp_{n}\Vert^{2} $ in contradiction to our indirect assumption.  (Our
assumption $n-(\log n)^{2}\ge \max\lbrace i,c_{1}\rbrace $ implies that
$n>c_{1}$. $c_{1}$ is sufficiently large with respect to $c$ by the
assumptions of \expref{Theorem}{A3}, and so $n$ is also sufficiently large
with respect to $c$ as required in \ref{P4}.)
        \nev{847}


Case III. $n-(\log n)^{2}\ge \max\lbrace i,c_{1}\rbrace $, $|S_{a}|\le
 (n-i')/10$ and $i>\lfloor {n/ 2} \rfloor$.  (The last
inequality implies $i'=i$.)  
We estimate $P(a)$ in terms of $i$.  
\nev{848}

Suppose that $L$ and $a$ are fixed so that there is an $x\in L$ with
$\theta^{(x,L)}=a$.  By the definition of $\theta^{(x,L)}$, $x$ is
unique with this property.  Moreover if we follow the recursive
definition of the randomization of $L=\rand_{n, {\calf}}$ then in each
step together with $\pi^{(j)}(L)$ we also get $\pi^{j}(x)$ since by the
definition of $\theta^{x,L}$ we have
$\pi^{(j)}(x)=(\calu_{j-1,L}(\pi^{(j-1)})x)+ a_{j}\wp_{j}$.
\nev{849}

Let $Q=[i+2,n-1] \backslash S_{a} $.  If $j\in Q$ then
$\theta^{(x,L)}_{j}=a_{j}=0$ and so
$\pi^{(j)}(x)=\calu_{j-1,L}(\pi^{(j-1)}x)$ and therefore by the
definition of $\calu_{j-1,L}$ we have that
$\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}$ for a uniquely defined
$\rho_{j} \in (-{1/ 2},{1/ 2}] $.  Let
$M={\calf}(n)({\calf}(i))^{-1}$ and let $A_{a}'$ be the event that ``the
number of integers $j\in Q$ with $|\rho_{j}|< (n-i)^{-{1/5}}M$ is
at least $(n-i)/ 2$.''  We show that $A_{a}$ implies $A_{a}'$ and
therefore $P(A_{a})\le P(A_{a}')$, then we will prove an upper bound on
$P(A')$.  Assume that $\neg A_{a}'$.  Then there are at least $4
(n-i)/10$ integers $j\in Q$ so that $|\rho_{j}|\ge (n-i)^{-{1/5}}M$. 
Therefore 
\begin{align*}
\Vert x\Vert^{2} &\ge \sum_{j\in Q}\rho_{j}^{2}\Vert
\wp_{j}\Vert^{2}\ge \frac{4}{ 10}(n-i) (n-i)^{-{2/5}}M^{2}({\calf}(i))^{2}\\ &\ge \frac{4}{10} (n-i)^{{3/5}}
\bigl(\calf(n)(\calf(i)) ^{-1}\bigr)^{2} ({\calf}(i))^{2}\ge  \frac{4}{10}
(n-i)^{{3/ 5}}({\calf}(n))^{2}\ge \wp_{n}^{2}
\end{align*}
so we reached a
contradiction.  Therefore $\neg A_{a}$ holds, which completes the proof
of the implication               
$A_{a}'\Rightarrow A_{a}$.       
\nev{850}

Now we estimate $P(A_{a}')$.  Suppose $j\in Q$. $\rho_{j} $ was defined
by the conditions $\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}$,
$\rho_{j} \in (-{1/ 2},{1/ 2}] $.  Therefore the definitions of
$\rand $, $\ext$ and \expref{Lemma}{A0} imply that if $\pi^{(j-1)}(x)$ is
linearly independent of $\wp_{j-1}$ then $\rho_{j}$ 
is uniformly distributed over $[-{1/ 2},{1/ 2}]$.  
However if
$\pi^{(j-1)}(x)\not =0$ and $\wp_{j-1}$ are dependent then by \ref{H1}
$\start(a)= j-1$.  Since $i=\start(a)$, $Q\subseteq [i+2, n]$ this
contradicts to $j\in Q$. Therefore the distribution of $\rho_{j}$ is
uniform over $ [-{1/ 2},{1/ 2}] $.  The definition of $\rand $
implies that the random variables $\rho_{j}$, $j\in Q$ are mutually
independent.  Therefore the probability that ``the number of integers
$j\in Q$ with $|\rho_{j}| < (n-i)^{-{1/5}}M $ is at least 
${(n-i)/ 2}$'' is no more than
 $2^{n-i}(2(n-i)^{-{1/5}}M)^{(n-i)/2} $.  We get that
\nev{854}

\begin{cond} \label{P5} $P(A_{a})\le P(A_{a}') \le
2^{n-i}(2(n-i)^{-{1/5}}M)^{(n-i)/2} $. \nev{855} \end{cond}


We use here the notion that a sequence 
$a=( a_{1},\ldots  ,a_{n})$ 
is \emph{acceptable}
as defined before the statement of \expref{Lemma}{B3}.  
In this case we use the definition with $h := \calf$.  
            \nev{856}


%   LB3  reorganized next para [MA]
% The probability $p_{i}$ that for a fixed $i>{n\over 2}$ there is an
% acceptable sequence $a$ so that $A_{a}$ holds is at most $ \sum \lbrace
% P(A_{a})\ |\ a$ is acceptable and $i=\start(a) \rbrace$.  Using our
% upper bound \ref{P5} on $P(A_{a})$ and the upper bound 
% in \expref{Lemma}{B3} for the number of acceptable sequences we get 
\begin{sloppypar}
For a fixed $i>{n/ 2}$, let $p_{i}$ denote the probability
that there is an acceptable sequence $a$ with $\start(a)=i$ so that
$A_a$ holds.  By the union bound,
$p_i \le  \sum \lbrace P(A_{a}) \mid a$ is acceptable and
$\start(a)=i \rbrace$.  
\end{sloppypar}
$$
p_{i,}\le
2^{n-i}(2(n-i)^{-{1/5}}M)^{(n-i)/2} 3^{n-i}\prod_{j=i}^{n}(
{\calf}(n)({\calf}(j))^{-1})\,.
$$  
Using that for all $j\in [i,n]$ we have
$$
{\calf}(n)({\calf}(j))^{-1}\le {\calf}(n)({\calf}(i))^{-1}=M
$$
we get that 
$p_{i}\le 3^{n-i}2^{3(n- i)/2} M^{3(n-i)/2}(n-i)^{-(n-i)/10}$.  
By \ref{D3.4} $M\le (n-i)^{\xi}$
for a small constant $\xi>0$ so we get $p_{i}\le (n-i)^{-(n-i)/20}$.  
Therefore the probability that there is an $i$ so that
$A_{a}$ holds for a suitably chosen $a$ is at most 
$$
\sum_{i={n/2}}^{n-(\log n)^{2}} (n-i)^{-(n-i)/20}\le
\sum_{k=(\log n)^{2}}^{\infty} k^{-k/20}\,.
$$
We have that 
$ k^{-k/20} / (k+1)^{-(k+1)/20}\ge (k+1)^{1/ 20}$ 
therefore the first term
in the sum (with $k=(\log n)^{2}$) is greater than the sum of the others
so we get that the probability is smaller than 
$$
2((\log n)^{2})^{-(\log n)^{2}/20} \le 
\exp\left(-\frac{(\log n) \log\log n}{11}\right)
$$ 
if $n$ is sufficiently large; this, however, follows from 
$n-(\log n)^{2} > c_{1}$.
\nev{857}

Case IV. $n-(\log n)^{2}\ge \max\lbrace i,c_{1}\rbrace $, $|S_{a}|\le
(n-i')/10$ and $i\le \lfloor {n/ 2} \rfloor $.  (The last
inequality implies $i'= \lfloor {n/ 2} \rfloor $.) \nev{858}

For each acceptable sequence $a$ with $\start(a)\le {n/ 2}$ we will
give an upper bound on the probability of the event $A_{a}$.  Then we
will estimate the number of acceptable sequences $a$ with $A_{a}$.
        \nev{859}

Suppose that $L$ and $a$ are fixed so that there is an $x\in L$ with
$\theta^{(x,L)}=a$.  We have
$\pi^{(j)}(x)=(\calu_{j-1,L}(\pi^{(j-1)})x)+ a_{j}\wp_{j}$ for all
$j=0,\ldots  ,n-1$.
\nev{860}

Let $Q=[{n/ 2},n-1]\backslash S_{a} $.  If $j\in Q$ then
$\theta^{(x,L)}_{j}=a_{j}=0$ and so
$\pi^{(j)}(x)=\calu_{j-1,L}(\pi^{(j-1)}x)$ and therefore by the
definition of $\calu_{j-1,L}$ we have that
$\pi^{(j)}(x)=\pi^{(j-1)}(x)+\rho_{j} \wp_{j}$ for a uniquely defined
$\rho_{j} \in (-{1/ 2},{1/ 2}] $.  Let $A_{a}'$ be the event
that ``the number of integers $j\in Q$ with $|\rho_{j}|< n^{-\tau}$ is
at least $n/ 4$,'' where $\tau<1/4$ is chosen so that $c$ is
sufficiently small with respect to $\tau$.  (This definition is somewhat
different from the corresponding definition in Case III.)  We show that
$A_{a}$ implies $A_{a}'$ and therefore $P(A_{a})\le P(A_{a}')$, then we
will prove an upper bound on $P(A_{a}')$.  Assume that $\neg A_{a}'$.
Then there are at least $n/5$ integers $j\in Q$ so that
$|\rho_{j}|\ge n^{-\tau} $.  Therefore 
$$
\Vert x\Vert^{2} \ge \sum_{j\in
Q}\rho_{j}^{2}\Vert \wp_{j}\Vert^{2}\ge \frac{1}{5}n
n^{-2\tau}({\calf}({n}/{2}))^{2}= \frac{1}{5}
n^{1-2\tau}({\calf}({n}/{2}))^{2}\,.
$$
Thus \ref{D3.4} implies that
$\Vert x\Vert^{2} \ge ({\calf}(n))^{2}= $ $\wp_{n}^{2} $, that is, $\neg
A_{a}$ holds, which completes the proof of
the implication                 
$A_{a}'\Rightarrow A_{a}$.      
\nev{864}

In Case III we have seen that the random variables $\rho_{j}$ are
independent and 
uniformly distributed over
$[-{1/ 2}, {1/2}] $.  
Therefore the probability that ``the number of integers $j\in Q$
with $|\rho_{j}| < n^{-\tau}$ is at least ${n / 4}$'' is no more
than $2^{n/ 2}(2n^{-\tau})^{{n/ 4}} $.  We get that
\nev{865}

\begin{cond} \label{P6} $P(A_{a})\le P(A_{a}') \le 2^{n/
2}(2n^{-\tau})^{{n/ 4}} $. \nev{866} \end{cond}

% The probability $p$ that there is an acceptable sequence $a$ so that
% $A_{a}$ holds is at most $ \sum \lbrace P(A_{a})\ |\ a$ is acceptable
% and $\start(a)\le {n\over 2}\rbrace$.  
Let $p$ denote the probability that there is an acceptable sequence
$a$ with $\start(a)\le {n/ 2}$ so that $A_a$ holds.  Again
by the union bound, 
$p \le  \sum \lbrace P(A_{a}) \mid a$ is acceptable
 and $\start(a)\le {n/ 2}\rbrace$.  
%
We use \ref{P6} as an upper
bound on $P(A_{a})$.  The number of acceptable sequences with the given
property is not greater than the total number of acceptable sequences
and for this we use the upper bound $3^{n}\prod_{j=1}^{n}{\calf}(n)(
{\calf}(j))^{-1}$ provided by \expref{Lemma}{B3}. \nev{867}

To get an upper bound on this product we need a lower bound on 
$\prod_{j=1}^{n}( {\calf}(j))^{-1} \ge 
c_{2}\prod_{j=1}^{n}\eee^{-c(\log j)^{2}} $, 
where $c_{2}>0$ depends only on $c$ and $c_{1}$.  Using that
$$
\int (\log x)^{2} dx = x(\log x)^{2} -2x\log x + 2x+C
$$
we give an upper
bound on $\sum_{j=1}^{n}c(\log j)^{2}$.  Since the function $(\log
x)^{2}$ is monotone we have \nev{868}
\begin{align*}
 \sum_{j=1}^{n}c(\log j)^{2} & \le
     c\int_{1}^{n} (\log x)^{2} dx +(\log n)^{2}   \cr
     & =  c\left(n(\log n)^{2} -2n\log n + 2n - 2 +(\log n)^{2}\right). 
                                                            \nev{869}
\end{align*}
Substituting this inequality in the upper bound on $p$ we get:
\begin{align*}
p &\le 2^{n/2}(2n^{-\tau})^{n/4}3^{n}
\eee^{cn(\log n)^{2}}\exp\Bigl({-c\bigl(n(\log n)^{2} -2n\log n + 2n - 2+
(\log n)^{2}\bigr)}\Bigr)\\
& \le 2^{n/ 2}(2n^{-\tau})^{{n/ 4}} 3^{n}
\exp\bigl({2cn\log n -2cn -c (\log n)^{2}+ 2c )}\bigr)\,.
\end{align*}
Therefore, if $c>0$ is sufficiently small
with respect to $\tau$ then $p\le n^{-\tau n/8}$.  In other
words in Case IV the probability that there is an $a$ so that $A_{a}$
holds for some suitably chosen $a$ is at most $n^{-\tau n/8}$
assuming                 
$\tau<{1/ 4}$ and $c$ is sufficiently small with respect to
$\tau$. 
\nev{870}

Summarizing the results of the four different cases we get the
following:
\nev{874}

\begin{lemma} \label{D5}  If $L$ is the random lattice defined in
\expref{Theorem}{A3}, then the probability that $\wp_{n,L}$ is not a
shortest nonzero vector of $L$ is at most 
$\exp\left(-{(1/12}) \log n \log\log n\right)$.  
If $n\le c_{1}$ then $\wp_{n,L}$ is always a shortest
nonzero vector. \nev{875} \end{lemma}


Suppose that $L$ is a random value of $\rand_{n,{\calf}}$.  The
definition of the random variable $\rand$ implies that $\pi^{(i)}L$ for
any $i\le n$ is a random value of $\rand_{i,{\calf}}$.  Therefore \expref{Lemma}{D5} implies that the probability $q_{n}$ 
of the event that               
there is an $i\le n$
such that                       
$\wp_{i,L}$ is not a shortest nonzero vector in $\pi^{(i)}(L)$ is at
most 
$$
\sum_{t=c_{1}}^{n}\exp\left(-\frac{(\log t) \log\log t}{21}\right)\,.
$$  
As $n\to\infty$, this series converges (because it is dominated by
$\sum_{t=1}^{\infty} t^{-2}$);
therefore, if $c_{1}$ is
sufficiently large then $q_{n}\le {1/ 2}$.  If $i\le c_{1}$ then
$\pi^{(i)}L$ has an orthogonal basis consisting of vectors of the same
length so each of them is a shortest nonzero vector.  This also implies
that $q_{n}=0$ for $n\le c_{1}$.  Therefore $q_{n}\le {1/ 2}$ for
all positive integers $n$.  The definition of the basis $\boldb_{i,L}$,
$i=1,\ldots  ,n$ implies that $\pi^{(n-i+1)}\boldb_{i,L}=\wp_{n-i+1,L}$ and
so applying the Gram-Schmidt orthogonalization process to it indeed
yields the vectors $b_{i}^{*}=\wp_{n-i+1,L}$, $i=1,\ldots  ,n$.  The fact
that $\wp_{i,L}$ is a shortest vector in $\pi^{(i)}(L)$ for all
$i=1,\ldots  ,n$ then   
implies that $\boldb_{i,L}$ is a
Korkine-Zolotareff basis.  The final inequality of the theorem holds
since $\Vert b_{1}\Vert= \Vert \wp_{n,L} \Vert= {\calf}(n) \ge n^{c\log
n} $ and $\Vert b_{n}^{*}\Vert=\Vert \wp_{1,L}\Vert = c_{1}^{c_{1} \log
c_{1}} $.
This concludes the proof of \expref{Theorem}{A3}. \nev{877}

\bibliography{a002}


\begin{tocauthors}
\begin{tocinfo}[miklos]
  Mikl\'{o}s Ajtai\\% \tocabout{}\\
  IBM Almaden Research Center\\
  ajtai\tocat almaden\tocdot ibm\tocdot com
  %% \url{home page}
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
  \begin{tocabout}[miklos]
    {\sc Mikl\'{o}s Ajtai} received his Ph.\,D. from the Hungarian
    Academy of Sciences in 1975.  His advisor was Andr\'as Hajnal. He
    worked in the following areas: axiomatic set theory (independence
    proofs), lattice theory (posets with meet and join),
    combinatorics, the theory of random graphs, complexity theory,
    sorting networks, the theory of lattices ($n$-dimensional 
    grids) and their applications to complexity theory
    and cryptography. He is a member of the Hungarian Academy of
    Sciences and was an invited speaker at ICM in 1998.  He received
    the Knuth prize in 2003, and the IBM Corporate Award in 2000.
\end{tocabout}
\end{tocaboutauthors}

\end{document}
