Authors Mikl{\'o}s Ajtai,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51
http://theoryofcomputing.org
Optimal lower bounds for the
Korkine-Zolotareff parameters of a lattice
and for Schnorr’s algorithm for the
shortest vector problem ∗
Miklós Ajtai
Received: November 15, 2006; published: May 10, 2008.
Abstract: Schnorr’s algorithm for finding an approximation for the shortest nonzero vec-
tor in an n-dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ 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 Rn which is KZ-reduced on
all k-segments and where the ratio kb1 k/shortest(L) is at least kcn/k . Noting that such
a basis renders all versions of Schnorr’s algorithm idle (output = input), it follows that the
quantity kcn/k is a lower bound on the approximation ratio any version of Schnorr’s algo-
rithm can achieve on the shortest vector problem. This proves that Schnorr’s analysis of
∗ A preliminary version of this paper has appeared in the Proc. 35th ACM Symp. on Theory of Computing [2].
ACM Classification: F.2.2, G.2
AMS Classification: 68Q25, 68W40, 68W25, 11H55, 11H99, 52C07, 60D05
Key words and phrases: Approximation algorithm, lattice, shortest vector problem, geometry of num-
bers, basis reduction, LLL reduction, Schnorr’s algorithm, Korkine-Zolotarev basis, random lattice
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2008 Miklós Ajtai DOI: 10.4086/toc.2008.v004a002
M IKL ÓS A JTAI
the approximation ratio of his algorithm is optimal apart from the constant in the expo-
nent. We also solve an open problem formulated by Schnorr about the Korkine-Zolotareff
lattice constants αk . We show that his upper bound αk ≤ k1+ln k is the best possible apart
from a constant factor in the exponent. We prove a similar result about his upper bound
βk ≤ 4k2 , where βk is another lattice constant with an important role in Schnorr’s analysis
of his algorithm.
1 Introduction
1.1 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ász’s algorithm also known as LLL reduction published in a paper
of A. Lenstra, H. Lenstra, L. Lovász [12], finds a vector which is longer than the shortest vector by a
factor of at most 2n−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 [6], (see also Lagrange [11]). In
1987 C. P. Schnorr gave an algorithm which is a generalization of the LLL reduction (see [14]). 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 .
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 b1 , . . . , bn
in it, with the property that Schnorr’s algorithm, given b1 , . . . , bn as an input, immediately terminates and
gives b1 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.
Definition 1.1.
1. Let b1 , . . . , bn be a basis of the lattice L. Applying the Gram-Schmidt orthogonalization to this ba-
sis we get a sequence of vectors b∗1 , . . . , b∗n with the property that b∗i , i = 1, 2, . . . , n are pairwise or-
thogonal, b1 = b∗1 and for all i = 1, . . . , n we have b∗i = bi − ∑i−1 ∗ ∗ ∗ −2
j=1 µi, j b j where µi, j = (bi ·b j )kb j k .
If Pi is the projection of the n-dimensional space onto the subspace orthogonal to b1 , . . . , bi−1 then
b∗i = Pi bi . We call the basis b1 , . . . , bn size-reduced if |µi, j | ≤ 1/2 for all 1 ≤ j < i ≤ n. It is
important for us that given an arbitrary basis b1 , . . . , bn it is easy to construct a size-reduced basis
d1 , . . . , dn so that b∗i = di∗ for i = 1, . . . , n.
2. Let b1 , . . . , bn be a basis of the n-dimensional lattice L. For each i = 1, . . . , n let Pi be the orthogonal
projection of the n-dimensional space onto the subspace orthogonal to the vectors b1 , . . . , bi−1 . Let
b∗i = Pi bi . b1 , . . . , bn is a Korkine-Zolotareff basis (or a Korkine-Zolotareff reduced basis, see [10])
if it is size-reduced, and b∗i is a shortest nonzero vector in the lattice Pi L, for all i = 1, . . . , n.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 22
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
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 ε 0 > 0 so that for every
k ≤ ε 0 n there exists a lattice and size reduced basis, b1 , . . . , bn in it so that, for every i = 1, . . . , n − k + 1,
the vectors Pi bi , . . . , Pi bi+k−1 form a Korkine-Zolotareff basis in the subspace generated by them. Conse-
quently, Schnorr’s algorithm is inactive on b1 , . . . , bn and so the short vector produced by the algorithm
is b1 . However the construction will show that the ratio of kb1 k/λ1 (L), where λ1 (L) is the length of the
shortest nonzero vector in L, is at least kcn/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 [8] con-
structed 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 im-
portant 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 [9], and for probabilistic algorithms it is k = O(log n) given by M. Ajtai, R. Ku-
mar, and D. Sivakumar in [4]. Therefore the approximation factor in deterministic polynomial time
2 (log n)−1 n) while in the probabilistic version it is
version of Schnorr’s algorithm is exp O((log log n)
exp O((log log n)(log n)−1 n) .)
In a recent paper [15], 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 [15] 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.
1.2 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 = Lk,c .
Definition 1.2. Assume the random variables µi, j , 1 ≤ j ≤ i − 2 ≤ k − 2 are independent and uniformly
distributed over the interval (−1/2, 1/2). We define a lower triangular k × k matrix
A(k,c) = (Ai, j )i=1,...,k, j=1,...,k .
The definition of the entries is the following.
Ai,i = k−ci/k , for i = 1, . . . , k,
1 1
Ai,i−1 = Ai−1,i−1 = k−c(i−1)/k , for i = 2, . . . , k, and
2 2
Ai, j = µi, j A j, j , if 1 ≤ j ≤ i − 2 ≤ k − 2 .
This implies that the ith row of the matrix (Ai, j ) is of the following form:
µi,1 k−c/k . . . µi,i−2 k−c(i−2)/k 1 −c(i−1)/k
2k k−ci/k 0 . . . 0
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 23
M IKL ÓS A JTAI
Lk,c will denote the lattice in Rk generated by the rows of A(k,c) .
The following theorem describes the properties of the lattice Lk,c which will be crucial in our proof
about the worst-case behavior of Schnorr’s algorithm.
Theorem 1.3. For all sufficiently small c > 0 there is an α > 0 so that for all sufficiently large positive
integers k with a probability of at least 1 − e−αk we have the following. Let ai be the ith row of the
matrix A(k,c) . Then a1 , . . . , ak is a Korkine-Zolotareff reduced basis of the lattice Lk,c . In particular the
first row of this matrix is a nonzero shortest vector of the lattice, with length A1,1 = k−c/k . Moreover
for all i = 2, . . . , k, if Pi is the projection of Rk to the subspace orthogonal to a1 , . . . , ai−1 then in the
(k − i)-dimensional lattice Pi Lk,c , the vector Pi ai is a nonzero shortest vector with length Ai,i = k−ci/k .
The theorem implies that if we apply the Gram-Schmidt orthogonalization to the basis a1 , . . . , ak of
Lk,c then we get a basis a∗i (of Rk ) with a∗i = k−ci/k ei , where ei is the ith unit vector.
We will use the lattice Lk,c in the way described below. We will construct (at random) an n-
dimensional lattice given with a basis b1 , . . . , bn , so that for every segment bs , . . . , bs+k−1 of this ba-
sis, if we take the orthogonal projections of the vectors bs , . . . , bs+k−1 to the subspace generated by
b1 , . . . , bs+k−1 , then the resulting sequence b0s , . . . , b0s+k−1 is like the basis a1 , . . . , ak from Theorem 1.3
multiplied by a constant factor. This and the described properties of the basis a1 , . . . , ak will make it
possible to show that Schnorr’s algorithm is inactive on the basis b1 , . . . , bn . (The length of a shortest
nonzero vector in the lattice generated by b1 , . . . , bn will be estimated through Minkowski’s convex body
theorem.)
The basis b1 , . . . , bn has a very concise definition similar to the definition of the lattice Lk,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 ith unit vector in Rn will
be denoted by ei .
Definition 1.4. Let n, k, k ≤ n be positive integers and let c > 0 be a real number and let fi = kc(n−i+1)/k ei
for i = 1, . . . , n. Suppose further that µi, j , i = 1, . . . , n, j = 1, . . . , i − 2 are mutually independent random
variables, uniformly distributed over the interval (−1/2, 1/2). Let b1 = f1 and for all i = 2, . . . , n let
bi = fi + (1/2) fi−1 + ∑i−2 j=1 µi, j f j . It is easy to see that the vectors b1 , . . . , bn are linearly independent.
Let Λ(n, k, c) be the lattice generated by b1 , . . . , bn . The basis (b1 , . . . , bn ) will be denoted by B(n, k, c).
If the values of n, k, c are fixed then Λ(n, k, c) and B(n, k, c) are random variables.
Clearly this definition implies that the n × n matrix whose rows are f1 , . . . , fn is lower triangular, and
its ith row is
1 c(n−(i−1)+1)/k c(n−i+1)/k
µi,1 kcn/k . . . µi,i−2 kc(n−(i−2)+1)/k) k k 0...0
2
As a consequence Λn,k,c = kc(n+1)/k Ln,c and we get the basis b1 , . . . , bn of Λn,k,c by multiplying the rows
of the matrix A(n,c) by kc(n+1)/k .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 24
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
Theorem 1.5. For all sufficiently small c > 0, there exists ε 0 > 0 so that if n is a sufficiently large
integer, and k is an integer with k ≤ ε 0 n then the following holds. Assume that L, (b1 , . . . , bn ) are
the corresponding random values of the random variables Λ(n, k, c), B(n, k, c). Then with a positive
probability the following conditions are satisfied.
(1). kb1 k = exp c nk log k , λ1 (L) ≤ 2n1/2 exp c n+1
2k log k , and so
1
kb1 k/λ1 (L) ≥ n−1/2 kc(n−1)/(2k) ≥ kcn/(3k) ,
2
(2). for all i = 1, . . . , n − 2k + 1, the vectors Pi bi , . . . , Pi bi+2k−1 form a Korkine-Zolotareff basis of the
lattice generated by them.
Corollary 1.6. The quantity kcn/(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 approxima-
tion ratio of his algorithm is optimal apart from the value of the constant in the exponent.
Proof. Take a basis satisfying the properties guaranteed in Theorem 1.5. 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 b1 , which is a factor of kcn/(3k) longer than the shortest vector in the lattice by
Theorem 1.5.
Remark 1.7.
1. 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 c1 > 0 there is a c2 > 0 so that if k ≥ c2 log n then L and
(b1 , . . . , bn ) meet the requirements of the theorem with a probability p ≥ 1 − n−c1 . 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 (b1 , . . . , bn ) with
the required properties.
2. The theorem holds, e. g., with any ε 0 < c/10 (this is not the best upper bound on ε 0 ), and the final
inequality n−1/2 kc(n−1)/(2k) ≥ (1/2)kcn/(4k) follows from this inequality. However if ε 0 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 kc(n−1)/(2k) < 1.
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.
Definition 1.8. For all positive integers k, the Korkine-Zolotareff constant is αk = sup kb1 k2 /kb∗k k2 ,
where the supremum is taken over all k-dimensional lattices L and over all Korkine-Zolotareff bases
b1 , . . . , bk in L.
Schnorr proves that αk ≤ k1+log k and asks whether αk = kO(1) . We show that actually his upper
bound is optimal up to a constant factor in the exponent. Namely we prove the following.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 25
M IKL ÓS A JTAI
Theorem 1.9. There is an ε > 0 so that the value of the Korkine-Zolotareff constant αk is at least kε log k
for all k = 1, 2, . . .
We will prove this result in Section 4. It will be an immediate consequence of Theorem 4.2. We
note that the proof of Theorem 1.5 and Theorem 1.9 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
Theorem 1.9 requires sharper estimates and so that proof involves more work.
Another lattice constant βk is even more important for the determination of the approximation factor
provided by Schnorr’s algorithm. βk defined as
( )
k 2k 1/k
βk = sup ∏ kbi k ∏ kbi k
∗ 2 ∗ −2
i=1 i=k+1
where the supremum is taken over all 2k-dimensional lattices L and over all Korkine-Zolotareff bases
b1 , . . . , b2k of L. Schnorr gives the upper bound βk ≤ 4k2 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 ε > 0 so that
βk ≥ kε for all k = 1, 2, . . ..
To prove the lower bound on βk we will use the random lattice L = Λ(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 Λ(k, k, c) = kc(k+1)/k Lk,c , Theorem 1.3 implies this statement with 2k in the place of k.) For the
lower bound on αk we use a modified form of the random lattice Λ(k, k, c), namely we will have k fi k =
exp −c(log(k − i + 1))2 for i = 1, . . . , k − c1 , and k fi k = exp −c(log c1 )2 for i = k − c1 + 1, . . . , k,
where c1 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.
1.3 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 [4]), 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 (Λ(n, k, c) for some choice of k and c) with the shortest known nonzero vector
in it (which is b1 ) and ask for a polynomial time algorithm which finds a nonzero vector shorter (or
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 26
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
much shorter) than b1 . 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.
Open problem. Give a probabilistic algorithm A and a positive integer c1 so that for all positive
integers t, s and for all sufficiently large integers n if A gets c = 1/t, k = bs log nc, n, and a random value
of B(n, k, c) = (b1 , . . . , bn ) as an input then with a probability of at least 1/2 (for the randomizations of
both B and A) and in time nc1 the algorithm A finds a vector x ∈ Λ(n, k, c) so that x 6= 0 and
(i.) kxk < kb1 k, or (a stronger requirement)
(ii.) kxk < 12 kb1 k.
Remark 1.10. 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 [4]),
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.
In the proof of Theorem 1.5 we represent our lattice elements by sequences of integers in a similar
way as it was done by R. Kannan in [9]. 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 [5].
1.4 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ász 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 [13] and to break several proposed cryptosystems (see
e.g. [7]).
The LLL reduction starts with an arbitrary basis b1 , . . . , bn of the lattice L and then it gradually “im-
proves” 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 b1 , . . . , bn where for each i in
the two-dimensional lattice K generated by Pi bi and Pi bi+1 , the shortest vector is Pi bi and (Pi bi , Pi bi+1 )
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 27
M IKL ÓS A JTAI
is a size reduced basis of K. We try to reach this goal by picking an i where this is not true and re-
placing bi , bi+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 Pi bi , Pi+1 bi , then find the corresponding new bi and bi+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 kb∗i k/kb∗i+1 k remain below a constant bound, namely kb∗i k/kb∗i+1 k ≤ 2 for all
i = 1, . . . , n. It is easy to see that λ1 (L), the length of the shortest nonzero vector, is bounded from below
by mini kb∗i k and so kb1 k ≤ 2(n−1)/2 λ1 (L). (Indeed if u is a shortest nonzero vector then we consider
the sequence Pi u, i = 1, . . . , n. We have kuk = kP1 uk ≥ kP2 uk ≥ . . . ≥ kPn uk = 0. Let j be the smallest
integer so that kPj uk = 0. By the definition of b j∗ we have that Pj−1 u = kb∗j , where k 6= 0 is an integer
and so kuk ≥ kb∗j k.)
C. P. Schnorr has improved the approximation factor of the algorithm by working with k consecu-
tive basis elements bi , . . . , bi+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 inequal-
ity kb∗i k/kb∗i+1 k ≤ 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 sig-
nificant difficulties.
Schnorr gave the following answers to these questions. (We just give a rough simplified sketch of
his algorithm.) The goal is that every block bi , . . . , bi+k−1 should have the property that Pi bi , . . . , Pi bi+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 bi , . . . , bi+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 Pi bi , . . . , Pi bi+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 kb1 k/λ1 (L) essentially by getting an upper bound on kb∗i k/kb∗i+k−1 k for all i = 1, . . . , n − k + 1.
This leads to the task, of finding an upper bound on kd1 k2 /kdk∗ k2 for every k-dimensional lattice J, where
d1 , . . . , dk 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 αk ≤ k1+log k and from this he got an upper bound
on kb1 k/λ1 (L). However, with another method (that we describe shortly), he gave a better upper bound
on kb1 k/λ1 (L) which made likely that the truth is αk ≤ kO(1) (this would have provided the same upper
bound on kb1 k/λ1 (L)). In this paper we show that surprisingly Schnorr’s upper bound on αk is tight,
that is, there is an ε > 0 with αk ≥ kε log k for all k.
The other method used by Schnorr which gives the better upper bound on kb1 k/λ1 (L) is the fol-
lowing. Instead of considering blocks of length k let us consider blocks of basis elements of length 2k,
bi , . . . , bi+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 kb∗i k2 /kb∗i+k−1 k2 we
are interested in the geometric mean of such ratios on an interval of length k. That is, we consider the
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 28
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
quantity
i+k−1 i+2k−1 −2 1/k
∏ kb∗j k2 ∏ kb∗j k .
j=i j=i+k
This quantity also can be used to give an upper bound on kb1 k/λ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 βk . Schnorr proved that βk ≤ 4k2 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 ε > 0 so that βk ≥ kε for all k.
The lower bound on βk only shows that the analysis given by Schnorr about his algorithm cannot
be improved by improving the upper bound on β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 b1 , . . . , bn
so that applying Schnorr’s algorithm to this basis the resulting approximation factor, that is, kb1 k/λ1 (L)
is only kεn/k for some constant ε, that is, apart from the factor ε > 0 it is the same as Schnorr’s upper
bound. Our basis b1 , . . . , bn will have the property that it is size-reduced and for any consecutive block
of 2k basis vectors bi , . . . , bi+2k−1 , the vectors Pi bi , . . . , Pi bi+2k−1 form a Korkine-Zolotareff basis of the
lattice generated by them and
! !−2 1/k
i+k−1 i+2k−1
∏ kPi b∗j k2 ∏ kPi b∗j k ≥ kε
j=i j=i+k
where ε > 0 is a constant.
Remark 1.11.
1. In Schnorr’s paper [14] 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.
2. A random lattice construction has been used to create problems with worst-case/average-case
equivalence [3]. 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 [1].
2 Sketch of the proofs of Theorems 1.3 and 1.5
First we give an equivalent definition for the random lattice Λ(n, k, c), which is longer but more natural
and has a clear motivation.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 29
M IKL ÓS A JTAI
We will construct a size reduced basis (b1 , . . . , bn ) so that
∗ n−i+1
bi = fi = exp c log k ei ,
k
i = 1, . . . , n. Assume that we have such a lattice. Minkowski’s convex body theorem implies that
2n1/2 (det L)1/n is an upper bound on the length of the shortest nonzero vector in any lattice. Now
n
n+1
(det L) = ∏ kbi k
1/n ∗ 1/n
= exp c log k .
i=1 2k
Since kb1 k = exp (c(n/k) log k), we get (using that k ≤ ε 0 n and that we may choose ε 0 with, e. g., ε 0 <
c/10) that kb1 k/λ1 (L) ≥ kεn/k . (This is the only point where we use the assumption k ≤ ε 0 n. For larger
values of k we would need a better upper bound on λ1 (L)). This holds also if (b1 , . . . , bn ) = B(n, 2k, c).
For the proof of Theorem 1.5 we have to show that (Pi bi , . . . , Pi bi+2k−1 ) is a Korkine-Zolotareff basis in
the lattice generated by them for i = 1, . . . , n − 2k + 1.
The vectors b∗1 , . . . , b∗n are already fixed and we have to define b1 , . . . , bn . b∗1 , . . . , b∗n uniquely deter-
mine the projections Pi . Indeed Pi was defined as the orthogonal projection of Rn onto the subspace S or-
thogonal to b1 , . . . , bi−1 . The vectors b1 , . . . , bi−1 generate the same subspace as the vectors b∗1 , . . . , b∗i−1 .
Therefore S, and so Pi , are uniquely determined by b∗1 , . . . , b∗i . We do not define the vectors bi directly
but define first the vectors Pj bi for j = n, . . . , 1 recursively by recursion on j starting at n and going
downwards. (At the end we get bi since P1 bi = bi .) This means that we build up the vectors bi from their
projected images by going backwards through the sequence of projections Pi . For j = n we do not have
any choices, by the definitions of b∗i and Pj we have Pn bi = 0 if i < n and Pn bn = b∗n .
The basic principle of this process is the following. Assume that Pj bi 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 , . . . , b∗n . We will define a (n − ( j − 1) + 1)-dimensional lattice
L j−1 in the subspace generated by b∗j−1 , . . . , b∗n so that Pj L j−1 = L j . Therefore if L j−1 is given somehow
then Pj−1 bi must be an element x of L j−1 with the property that Pj x = Pj bi . Since we want our basis to
be size reduced there are at most two possible choices for x since Pj−1 bi and b∗j−1 has been already fixed.
If in the definition of a size reduced basis we replace the requirement |µi, j | ≤ 1/2 by −1/2 < µi, j ≤ 1/2
then the choice of bi 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 Pj−1 b j−1 = b∗j−1 is no
longer than the vector Pj−1 b j (this is a consequence of the requirement that Pj−1 b j−1 is the first element
of a Korkine-Zolotareff basis.) To make this requirement easily satisfiable we try to make Pj−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.
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
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 30
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
the following lemma, that L is an arbitrary lattice in Rm and a ∈ L so that a is contained in a basis
of L. Assume further that κ > 0. Let P be the orthogonal projection P of Rm+1 to Rm defined by
P(y1 , . . . , ym , ym+1 ) = (y1 , . . . , ym ). We are interested in lattices K in Rm+1 so that (0, . . . , 0, κ) ∈ K,
PK = L, the shortest vector w ∈ K with Pw = a is as long as possible, otherwise K is random in some
sense.
The assumption (0, . . . , 0, κ) ∈ K implies that for every K we have kwk2 ≤ kak2 + (κ/2)2 if w ∈ K
and Pw = a. However this upper bound is reached for the vector (a, κ/2), therefore we will deal only
with lattices K so that (a, κ/2) ∈ 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.
Lemma 2.1. Assume that m is a positive integer, L ⊆ Rm is a lattice, a ∈ L, a 6= 0, κ > 0 is a real number
and x1 , . . . , xm−1 ∈ L so that {x1 , . . . , xm−1 , a} is a basis of L. Depending on m, κ, L, a, x1 , . . . , xm−1 we de-
fine a random variable Y whose values will be lattices in Rm+1 . We pick m − 1 real numbers ξ1 , . . . , ξm−1
independently and with uniform distributions from the interval (0, 1). A random value K of Y will be
the lattice in Rm+1 generated by the vectors (xi , ξi κ), i = 1, . . . , m − 1, the vector (a, κ/2) and the vector
(0, . . . , 0, κ). Then the distribution of Y does not depend on the choice of the vectors x1 , . . . , xm−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 ∈ L there is a unique real number σx , −1/2 ≤ σx < 1/2 so that (x, σx κ) ∈ K and if x is
linearly independent of the vector a then the distribution of σx is uniform over the interval [−1/2, 1/2).
We return now to our basis construction. We will use Lemma 2.1 with the following substitutions:
m := n − j + 1; L := L j ; a := b∗j ; Rm is the subspace generated by b∗j , . . . , b∗n ; Rm+1 is the subspace
generated by b j−1 , b∗j , . . . , b∗n ; (0, . . . 0, κ) := b∗j−1 .
Let K be the random lattice defined in the lemma. The property (a, κ/2) ∈ K implies that
(1/2)b∗j−1 + b∗j ∈ L j−1 and clearly Pj ((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.
As we have told, if L j−1 is given, the choice for Pj−1 bi is unique with the condition µi, j−1 ∈
(−1/2, 1/2]. This completes the definition of Pj−1 bi for all i and so the definition of the basis b1 , . . . , bn .
It is an immediate consequence of the definition that b1 , . . . , bn are linearly independent and b∗i is really
the vector that we have selected in advance for this role. The condition µi, j−1 ∈ (−1/2, 1/2] guarantees
that it is a size reduced basis. Lemma 2.1 implies that this definition is equivalent to our original defi-
nitions of Λ(n, k, c), B(n, k, c). Indeed, since we could pick the basis elements {xi } in an arbitrary way,
using the basis Pj b j , . . . , Pj bn gives the original definition.
We prove that with a positive probability for the randomization of Λ(n, k, c) we have that for each
i = 1, . . . , n−k +1 the elements Pi bi , . . . , Pi bi+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 Λ(k, k, c).
We will show that b1 , . . . , bk is a Korkine-Zolotareff basis in Λ(k, k, c) with a probability of at least
1 − e−αk where α > 0 is a constant. This implies that there is a constant c0 > 0 so that if k > c0 log n then
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 31
M IKL ÓS A JTAI
the probability that Pi bi , . . . , Pi bi+k−1 is a Korkine-Zolotareff basis for all i = 1, . . . , 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ász’s Local Lemma, or a more direct argument which also provides a construction.)
This completes the sketch of the proof of Theorem 1.5.
3 The proofs of Theorems 1.3 and 1.5
First we prove Theorem 1.5 together with the lower bound on βk , and then the lower bound on αk . The
proof about the lower bound on αk has the same structure than the lower bound proof for β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 β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 αk as well, although this includes some repetitions.
Definition 3.1. If n is a positive integer then the set {1, . . . , n} will be denoted by Nn . N0 will be the
empty set.
We will use the following observation in the proof of Lemma 2.1.
Lemma 3.2. Suppose that ξ1 , . . . , ξk are independent random variables, uniformly distributed over the
interval (0, 1). Assume further that A = {ai, j } is a k by k matrix with integer entries and with determinant
±1. For each i = 1, . . . , k let ρi = ∑kj=1 ai, j ξ j and let νi = ρi − bρi c, where bxc is the largest integer which
is not greater than the real number x. Then each νi is uniformly distributed over [0, 1) and the random
variables ν1 , . . . , νk are independent.
Proof. It is sufficient to show that the vector (ν1 , . . . , νk ) is uniformly distributed over the n-dimensional
unit cube Qk . The vector (ρ1 , . . . , ρ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 Qk into P. Since the
determinant of A is ±1 we have that the distribution of the vector ρ = (ρ1 , . . . , ρk ) is uniform over P. We
get the vector ν = (ν1 , . . . , νk ) by reducing it modulo Qk . Since both Qk 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 ρ is uniformly distributed over P
implies that ν is uniformly distributed over Qk .
Proof of Lemma 2.1. Since a, x1 , . . . , xm−1 are linearly independent and κ 6= 0 we have that the vectors
(xi , ξi κ), i = 1, . . . , m − 1, (a, κ/2) and the vector (0, . . . , 0, κ) are also linearly independent and so they
form a basis of K. We will use this fact in the proof.
Let z1 , . . . , zm−1 ∈ L so that z1 , . . . , zm−1 , a is a basis of L. Assume that we take a random value K of
Y using the basis x1 , . . . , xm−1 , a. It is sufficient to show that with probability 1, for each i = 1, . . . , m − 1
there is a unique real number νi ∈ (0, 1) so that (zi , νi κ) ∈ K, moreover the random variables νi , i =
1, . . . , k defined this way are uniformly distributed over (0, 1) and they are mutually independent.
First we consider the special case when there are integers ti , i = 1, . . . , m − 1 so that zi = xi + ti a ,
i = 1, . . . , m − 1. By the definition of ξi we have (xi , ξi κ) ∈ K. This can be written in the form of (zi −
ti a, ξi κ) ∈ K. Using that (a, κ/2) ∈ K we get that (zi , (ξi + ti /2)κ)) ∈ K and so (0, . . . , 0, κ) ∈ K implies
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 32
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
the existence of νi . If νi is not unique then (0, . . . , 0, ϑ κ) ∈ K for some ϑ ∈ (0, 1), in contradiction to the
fact that (0, . . . , 0, κ) is a basis vector of K. Since νi is the fractional part of ξi + ti /2 and ξi is uniformly
distributed over (0, 1), we have that νi is also uniformly distributed over (0, 1).
We consider now the general case assuming only that (z1 , . . . , zm−1 , a) is a basis of L. We have
zi = ti ai + ∑m−1 j=1 αi, j x j for i = 1, . . . , m − 1, where all of the coefficients ti and αi, j are integers. Let
wi = zi − ti a, i = 1, . . . , m − 1. Clearly (w1 , . . . , wm−1 , a) is a basis of L. It is sufficient to prove that our
assertion holds with zi := wi , i = 1, . . . , m − 1, since if this is true then we may apply the already proven
special case with xi := wi . In other words, we have to prove now the assertion for the special case when
the basis vectors z1 , . . . , zm−1 can be written in the form zi = ∑m−1 j=1 αi, j x j , i = 1, . . . , m − 1, where αi, j is
an integer for i = 1, . . . , m − 1, j = 1, . . . , m − 1. Since both (z1 , . . . , zm−1 , a) and (x1 , . . . , xm , a) are bases
of L, we have that the determinant |αi j | is ±1.
By the definition of K we have (x j , ξ j κ) ∈ K. For each fixed i we take the linear combinations of
these vectors with coefficients αi, j . We get that (zi , (∑m−1 j=1 αi, j ξ j )κ) ∈ K. Let νi be the fractional part of
∑ j=1 αi, j ξ j . Clearly with a probability 1 we have ν j ∈ (0, 1). Moreover Lemma 3.2 implies that each νi
m−1
is uniformly distributed over (0, 1) and the random variables ν1 , . . . , νk are independent.
Let x ∈ L. We have x = ta + ∑m−1 i=1 bi xi , where t, b1 , . . . , bm−1 are integers. Since (xi , ξi κ) ∈ K, i =
1, . . . , m − 1 and (a, κ/2) ∈ K we have that (x, σ 0 κ) ∈ K, where σ 0 = t/2 + ∑n−1 i=1 bi ξi . Let σx the unique
element of the interval [−1/2, 1/2) so that for a suitable integer s we have σ 0 + s = σx . (0, . . . , 0, κ) ∈
K implies that (x, σx κ) ∈ K. Assume that contrary to our assertion σx is not unique. By taking the
difference of the two vectors (x, σx κ) for two different values of σ we get that there is a ϑ ∈ (0, 1) with
(0, . . . , 0, ϑ κ) ∈ K which contradicts to the fact that (0, . . . , 0, κ) is a basis vector of K.
Definition 3.3.
1. Assume that m is a positive integer, L ⊆ Rm is a lattice, κ > 0 is a real number and a ∈ L, a 6= 0.
The random variable Y defined in Lemma 2.1 will be denoted by extm,κ,L,a .
We define a random variable randn,h whose values will be lattices in Rn . The definition depends
on two parameters: a positive integer n and a function h with the property domain(h) ⊇ {1, .., n},
(only the values of h on {1, . . . , n} 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 randn,h by recursion on n. At
the same time we will prove by induction on n that for each possible value L of randn,h there
is a minimal positive real number ν(L) so that (0, . . . , 0, ν(L)) ∈ L. rand1,h will be always the
one-dimensional lattice consisting of all of the real numbers ih(1), where i is an integer. Clearly
ν(L) is h(1). Assume that the random variable randn−1,h has been defined with values in Rn−1 for
some n > 1. Then first we take a random value L of randn−1,h . Let a = (0, . . . , 0, ν(L)) ∈ L. Now
we randomize extn−1,h(n),L,a . Its value is a lattice K ⊆ Rn , this will be the value of the random
variable randn,h . By the definition of extn,h(n),L,a the vector (0, . . . , 0, h(n)) is in K which proves
the existence of ν(K).
2. If n is a positive integer then π (i,n) will denote the orthogonal projection of Rn onto Ri defined by
π (i,n) (y1 , . . . , yi , yi+1 , . . . , yn ) = (y1 , . . . , yi ). π (0,n) will be that map of Rn into the zero-dimensional
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 33
M IKL ÓS A JTAI
space R0 (consisting only of the vector 0). If the value of n is clear from the context we will write
π (i) for π (i,n) .
3. We say that the lattice L ⊆ Rn is triangular if it has a basis ai = (αi,1 , . . . , αi,n ), i = 1, . . . , n so that
for all i = 1, . . . , n, αi,i 6= 0 and for all j = 1, . . . , i − 1 we have αi, j = 0. (The condition αi,i 6= 0
can be omitted since for a basis it follows from the other conditions). We will say that the basis
a1 , . . . , an is a triangular basis of L.
We can formulate the definition of triangularity in the following equivalent form: L is triangular
iff for each i = 1, . . . , n there is a real number α 6= 0 so that (0, . . . , 0, α) ∈ π (i) (L).
Remark 3.4. The triangularity of the lattice L depends on the way it is embedded in Rn . In particular this
property is not invariant under isometric isomorphisms of lattices. Namely there is a lattice L ⊆ Rn and
there is a unitary transformation U of Rn so that L is triangular but UL is not, where UL = {Ux | x ∈ L}.
The following lemma is an immediate consequence of the definitions.
Lemma 3.5. Assume that n, i are positive integers, i ≤ n, L ⊆ Rn is a triangular lattice, then π (i) L is a
triangular lattice in Ri .
Lemma 3.6. Assume that n is a positive integer, h is a function defined on the set of all positive inte-
gers whose values are positive real numbers. Then each value L of the random variable randn,h is a
triangular lattice.
Proof. The recursive definition of the random variable randn,h implies that for all i = 1, . . . , n we have
that (0, . . . , 0, h(i)) ∈ π (i) (L), which proves the triangularity of L.
Suppose that L ⊆ Rn is a triangular lattice. Our next goal is to associate with each x ∈ L a sequence
of integers a1 , . . . , an , 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 kxk2 using the sequence a1 , . . . , an . 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, . . . , n, π (i) (L) ⊆ Ri 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 ℘i,L ∈ π (i) (L), i = 1, . . . , n so that ℘i,L and ei are
parallel (in R(i) ). We may consider ℘i,L as the result of the orthogonalization of the triangular basis.
Definition 3.7. Suppose that L ⊆ Rn is a triangular lattice. For each i = 1, . . . , n there is a v =
(v0 , . . . , vi ) ∈ π (i) L so that v1 = · · · = vi−1 = 0 and vi > 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 vi is minimal. We will denote this
vector by ℘i,L . Clearly every triangular basis of π (i) (L) contains ℘i,L or −℘i,L .
Remark 3.8. We will define ai in the following way. We consider the set
Sx = {π (i) (x) + t℘i,L | t = 0, ±1, ±2, . . .} .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 34
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
From the elements of Sx we take an y0 = π (i) (x) + t0℘i,L whose ith component is minimal in absolute
value (preferring 1/2 over −1/2). ai will be defined by the equation π (i) (x) = y0 + ai℘i,L .
The set Sx can be also defined as Sx = {y ∈ π (i) (L) | π (i−1) (y) = π (i−1) (x)}. Then we get y0 as a
function of π (i−1) (x). Since we will need this function later, we will use it in the final definition of ai
given in Lemma 3.10 below.
Definition 3.9. If L ⊆ Rn is a triangular lattice, then for each i ∈ [0, n − 1] we define a function Ui,L
whose domain will be π (i) (L) and whose range will be in π (i+1) (L). We claim that for each x ∈ π (i) (L),
there is a unique real number ξ in the interval (−1/2, 1/2] so that (x, 0) + ξ℘i+1,L ∈ π (i+1) (L). Indeed,
since x = π (i) y for some y ∈ L we have that x0 = π (i+1) y ∈ π (i+1) L and we get the vector x0 by extending
x with a new component. Since ℘i+1,L is contained in a triangular basis of π (i+1) (L) we can write x0 in
the form of (x, 0) + ξ℘i+1,L . The uniqueness of ξ follows also from the fact that ℘i1 ,L is contained in a
triangular basis. We define a function Ui,L mapping π (i) L into π (i+1) by Ui,L (x) = (x, 0) + ξ℘i+1,L where
ξ is the unique real number in (−1/2, 1/2] so that (x, 0) + ξ℘i+1,L ∈ π (i+1) (L).
Lemma 3.10. Assume that n is a positive integer, L ⊆ Rn is a triangular lattice. Then for all x ∈ L there
is a uniquely determined sequence of integers a1 , . . . , an so that for all j = 1, . . . , n we have
π ( j) x = U j−1,L (π ( j−1) x) + a j℘j,L .
For this sequence a1 , . . . , an we have
n
1 2 1 n 2
kxk2 ≥ ∑ min |a j |, |a j | − k℘j,L k2 ≥ ∑ a j k℘j,L k2 .
j=1 2 4 j=1
Proof. The vectors π j x and U j−1,L (π ( j−1) x) differ only in their jth coordinates. Since both are in π ( j) L
their difference d = π j x − U j−1,L (π ( j−1) x) is a vector in π ( j) L whose only nonzero coordinate is the jth
one. ℘i,L is a basis vector of π ( j) (L) therefore d = a j℘j,L for some integer a j . Since ℘j,L 6= 0, a j is
unique. Let x = (x1 , . . . , xn ). By the definition of U j−1,L (π ( j−1) x), the jth coordinate of U j−1,L (π ( j−1) x)
can be written in the form of ξ℘j,L where ξ ∈ (−1/2, 1/2]. Therefore x j = (ξ + a j )℘j,L . If ξ j and a j
has identical signs or a j = 0 then |ξ + a j | ≥ |a j |. Otherwise |ξ + a j | ≥ |a j | − 1/2 . This and the fact
that the numbers ai are integers imply the final sequence of inequalities.
Definition 3.11.
1. If n is a positive integer, L ⊆ Rn is a triangular lattice, 1 ≤ i < l ≤ n are integers and x ∈ L then the
unique sequence a = (a1 , . . . , an ) whose existence is guaranteed by Lemma 3.10 will be denoted
(x,L) (x,L)
ϑ (x,L) = (ϑ1 , . . . , ϑn ).
2. If a = (a1 , . . . , an ) is a sequence of integers then start(a) will be the largest positive integer i so
that a1 = · · · = ai = 0. If there is no such positive integer then start(a) = 0. 4. Assume that L
is a triangular lattice. For each x ∈ L and i = 1, . . . , n let y(i) be the unique element of L so that
π (i) x = π (i) y(i) and U j,L (π ( j) y(i)) = π ( j+1) y(i) for each j = i, . . . , n − 1. The uniqueness of y(i)
follows from the equality y(i) = Un−1,L (. . . Ui,L (x) . . .). We will denote the vector y(i) by ϕ(x, i).
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 35
M IKL ÓS A JTAI
3. If L is a triangular lattice then we define a basis bi,L , i = 1, . . . , n in the following way. b1,L = ℘n,L
and for all i = 2, . . . , n − 1, bi,L = ϕ(℘n−i+1 , n − i + 1).
4. In the following we will assume that R0 ⊆ R1 ⊆ . . . ⊆ Rn . Namely if i < j we will identify the
vector (x1 , . . . , xi ) ∈ Ri with the vector (x1 , . . . , xi , 0, . . . , 0) ∈ R j . (A cleaner way to do this would
have been to define Rn as the set of all of the infinite sequences x1 , . . . , xn , xn+1 , . . . of real numbers
so that 0 = xn+1 = xn+2 = · · · .)
Lemma 3.12. Assume that L is a triangular lattice. Then the basis bi,L , i = 1, . . . , n is size reduced.
Proof. By the definition of bi,L we have π (n−i+1) bi,l = ℘n−i+1,L . Since relative to the basis bi,L we
have Pi = π (n−i+1) , where Pi is from the definition of the Gram-Schmidt orthogonalization, we have
that b∗i,L = ℘n−i+1,L . We have bi,L = Un−1,L (. . . Un−i+1,L (℘n−i+1,L ) . . .). When we apply Un− j,L we get
the n − j + 1th coordinate of the vector bi,L which is µi, j . Therefore the definition of U implies that
µi, j ∈ (−1/2, 1/2] and so |µi, j | ≤ 1/2.
Definition 3.13.
1. Let αk = sup |b1 |2 /|b∗k |2 , where the supremum is taken over all k-dimensional lattices L and over
all Korkine-Zolotareff bases b1 , . . . , bk in L. The quantity αk is the Korkine-Zolotareff constant.
2. We define another lattice constant βk which depends on lattices of dimension 2k.
( )
k 2k 1/k
∏ kb∗i k2 ∏ kb∗i k
−2
βk = sup
i=1 i=k+1
where the supremum is taken over all 2k-dimensional lattices L and over all Korkine-Zolotareff
bases b1 , . . . , b2k of L.
In [14] Schnorr proves that αk ≤ k1+log k and asks whether αk = kO(1) . In Theorem 4.2 we will
show that actually Schnorr’s upper bound is tight namely there is an ε > 0 so that αk > kε log k for all
k = 1, 2, . . .. In Theorem 3.14 we show that Schnorr’s upper bound on βk , βk ≤ 4k2 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 βk . Theorem 3.14 implies that this analysis cannot be
improved by giving a better upper bound on β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 Theorem 3.14 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
(Theorem 3.22 and Theorem 3.23).
Theorem 3.14. There is an α > 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 randn,h , where h(x) = exp((cx/n) log n) = ncx/n , then the
following holds: With a probability of at least 1 − e−αn the sequence bi = bi,L , i = 1, . . . , n is a Korkine-
Zolotareff reduced basis of the n-dimensional lattice L. Moreover the Gram-Schmidt orthogonalization
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 36
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
procedure applied to the basis b1 , . . . , bn yields the orthogonal vectors b∗i = ℘n−i+1,L , i = 1, . . . , n. If
n = 2m where m is an integer then we have
m 2m −2 1/m
∏ kb∗i k2 ∏ kb∗i k
= n2c .
i=1 i=m+1
This theorem clearly implies Theorem 1.3.
Proof of Theorem 3.14 In the proof we will use the following properties of the lattice L, where L is a
random value of randn,h .
Lemma 3.15. 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 randn,h . Then the following
requirements are met.
(3). L is a triangular lattice and for all i = 1, . . . , n, π (i)℘i,L = (0, . . . , 0, h(i))
(4). Ui (℘i,L ) = (0, . . . , 0, h(i), 21 h(i + 1)) for all i = 1, . . . , n − 1
(5). for all i = 1, . . . , n − 1 and for all integers t we have Ui (t℘i,L ) = (0, . . . , 0,th(i), 12 h(i + 1))
Remark 3.16. In this lemma the function h is not necessarily the same as the function defined in Theo-
rem 3.14.
Proof. (3) The triangularity of L is an immediate consequence of the definitions of rand and ext. ℘i,L
takes the role of the vector (0, . . . , 0, κ) in the definition of exti−1,κ,L̄,a where in our case L̄ = π (i−1) (L)
and κ = h(i).
(4) By the definition of randn,h we have that π (i+1) (L) = extn,κ,L0 ,a , where κ = h(i+1), L0 = π (i) (L),
and a = ℘i,L = (0, . . . , 0, h(i)). This definition also implies that (a, κ/2) ∈ L0 , that is,
1
0, . . . , 0, h(i), h(i + 1) ∈ π (i+1) (L) .
2
Therefore the definition of Ui and ℘i+1,L = (0, . . . , 0, h(i + 1)) implies (4). (5) is an immediate conse-
quence of (4).
We return to the proof of Theorem 3.14. First we estimate the probability of the following event
A: “℘n,L is not a shortest nonzero vector in L.” Let a = (a1 , . . . , an ) be a sequence of integers. We
estimate the probability of the event Aa : “there is an x ∈ L, x 6= 0 so that kxk < k℘n k and ϑ (x,L) = a.” Let
start(a) = i. This implies that i < n otherwise because of a1 = · · · = an = 0 we would have x = 0. The
condition start(a) = 0 also implies π (i) x = 0, π (i+1) x 6= 0. The latter inequality holds since otherwise
we would have π (i+1) x = Ui (0) + ai+1℘i+1,L = 0 and therefore ai+1℘i+1,L = 0 which is impossible since
ai+1 6= 0 and ℘i+1,L 6= 0. We distinguish four cases depending on i.
In the proof we will use repeatedly the following simple fact
(6). If h(x) = exp cxn log n then h(n − n(log n)−1 ) = h(n)e−c .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 37
M IKL ÓS A JTAI
Case I. i > n − n(log n)−1 or n < (5/4)1/(2c) . We show that in this case P(Aa ) = 0 since there is
no x ∈ L with kxk < k℘n k and ϑ x,L = a. Indeed, assume that there is an x ∈ L with these properties.
start(a) = i implies a1 = · · · = ai = 0 and so according to the definition of ϑ (x,L) = a we have π ( j) (x) =
0 for j = 1, . . . , i. ai+1 6= 0 therefore π (i) (x) = 0 implies
π (i+1) (x) = ai+1 π (i+1)℘i+1,L = (0, . . . , 0, ai+1 h(i + 1)) .
If i = n − 1 this implies kxk ≥ ℘n,L in contradiction to our assumption. Therefore i < n − 1. (5) implies
that 1
π (i+2) (x) = Ui+1 (ai+1 π (i+1)℘i,L ) = 0, . . . , 0, ai+1 h(i + 1), h(i + 2) .
2
Consequently
1 i+1 1 i+2 5
kxk2 ≥ kπ (i+2) xk2 ≥ (h(i + 1))2 + (h(i + 2))2 = n2c n + n2c n ≥ n2ci/n .
2 2 4
So the condition i > n − n(log n)−1 implies that
5 −1 −1 5 5
kxk2 ≥ n2c(n−n(log n) )n = exp 2c(1 − (log n)−1 ) log n = e2c log n e−2c > e2c log n = k℘n,L k2
4 4 4
in contradiction to our assumption. We consider now the condition n < (5/4)1/(2c) . We have
5 5 i 5
log kxk2 ≥ log n2ci/n = log + 2cin−1 log n = 2c log n + (2c log n)−1 log .
4 4 n 4
To give a lower bound on this we use that n < ( 54 )1/(2c) implies (2c log n)−1 log 54 > 1. Therefore
i
log kxk2 > 2c log n + 1 ≥ 2c log n ≥ log k℘n,L k2 .
n
Case II. n − n(log n)−1 ≥ i, n > (5/4)1/(2c) and |Sa | > (n − i0 )/10 where i0 = max{i, dn/2e} and
Sa = { j ∈ [i0 , n] | a j 6= 0}. We show that in this case P(Aa ) = 0 since there is no x ∈ L with ϑ x,L = a and
kxk < k℘n k. Indeed assume that there is an x ∈ L with these properties. By Lemma 3.10 we have
1 1 1
kxk2 ≥
4 ∑ {k℘j k2 | a j 6= 0, j ∈ [i0 , n]} ≥ |Sx |k℘i0 k2 ≥ |Sx |(h(i0 ))2 >
4 4
0
n − i0
1 1 0 i 1 0
(n − i ) exp 2c log n = (n − i ) exp(2c log n) exp −2c log n ≥
4 10 n 40 n
1 n/2 1
(n − i0 ) exp (2c log n) exp −2c log n ≥ (n − n(log n)−1 )e−c log n k℘n,L
2
k.
40 n 40
Since n > (5/4)1/(2c) and c is sufficiently small we have 40 1
(n − n(log n)−1 )e−c log n ≥ 1 and therefore
kxk ≥ k℘n,L k in contradiction to our indirect assumption.
Case III. n − n(log n)−1 ≥ i, n > (5/4)1/(2c) , |Sa | ≤ (1/10)(n − i0 ) and i > bn/2c. (The last inequality
implies i0 = i.) For each fixed i > bn/2c, we estimate the probability of the event Aa ∧ start(a) = i.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 38
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
Suppose that L and a are fixed so that there is an x ∈ L with ϑ (x,L) = a, i = start(a). By the definition
(x,L)
of ϑ (x,L) , x is unique with this property. Let Q = [i + 2, n − 1]\Sa . If j ∈ Q then ϑ j = a j = 0 and so
π ( j) (x) = U j−1,L (π ( j−1) x) and therefore by the definition of U j−1,L we have that π ( j) (x) = π ( j−1) (x) +
ρ j℘j for a uniquely defined ρ j ∈ (−1/2, 1/2]. Let M = h(n)(h(i))−1 and let A0a be the event that “the
number of integers j ∈ Q with |ρ j | < (n − i)−1/5 M is at least (n − i)/2.” We show that Aa implies A0a and
therefore P(Aa ) ≤ P(A0a ), then we will prove an upper bound on P(A0 ). Assume that ¬A0a . Then there
are at least 3(n − i)/10 integers j ∈ Q so that |ρ j | ≥ (n − i)−1/5 M. Therefore
3
kxk2 ≥ ∑ ρ 2j k℘j k2 ≥ (n − i)(n − i)−2/5 M 2 (h(i))2 ≥
j∈Q 10
3 3
(n − i)3/5 (h(n)(h(i))−1 )2 (h(i))2 = (n − i)3/5 (h(n))2 > k℘n,L k2 ,
10 10
that is, ¬Aa holds, which completes the proof of the implication A0a ⇒ Aa .
Now we estimate P(A0a ). Suppose j ∈ Q. ρ j was defined by the conditions
π ( j) (x) = π ( j−1) (x) + ρ j℘j ,
ρ j ∈ (−1/2, 1/2]. Therefore the definitions of rand, ext and Lemma 2.1 implies that if π ( j−1) (x) is
linearly independent of ℘j−1 then ρ j is uniformly distributed over [−1/2, 1/2]. However if π ( j−1) (x) 6= 0
and ℘j−1 are linearly dependent then by (3) start(a) = j − 1. Since i = start(a), i ≤ j, Q ⊆ [i + 2, n]
this contradicts to j ∈ Q. Therefore the distribution of ρ j is uniform over [−1/2, 1/2]. The definition of
rand implies that random variables ρ j , j ∈ Q are mutually independent. Therefore the probability that
“the number of integers j ∈ Q with |ρ j | < (n − i)−1/5 M is at least (n − i)/2” is no more than 2n−i (2(n −
i)−1/5 M)1/2(n−i) . We get that
(7). P(Aa ) ≤ P(A0a ) ≤ 2n−i (2(n − i)−1/5 M)1/2(n−i) .
Definition 3.17. 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 randn,h and
a = (a1 , . . . , an ) 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 randn,h and an x ∈ L with a = ϑ x,L and kxk < k℘n k.
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 [9]. These
differences however do not affect the validity of the upper bound and its proof.
Lemma 3.18 (Kannan). Assume that c > 0 and n, i, i ≤ 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 randn,h and a = (a1 , . . . , an ) is an acceptable sequence with start(a) = i. Then for all j =
i, . . . , n we have |a j | < h(n)(h( j))−1 . Moreover the number of acceptable sequences with start(a) ≥ i
is at most
n n
∏(1 + 2h(n)(h( j))−1 ) ≤ 3n−i ∏(h(n)(h( j))−1 ) .
j=i j=i
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 39
M IKL ÓS A JTAI
Remark 3.19. In this lemma the function h is not necessarily the same as in Theorem 3.14.
Proof of Lemma 3.18. Assume that a is an acceptable sequence and let L be a value of randn,h where
there is an x ∈ L with kxk ≤ ℘n,L and ϑ (x,L) = a. According to the definition of a j we have π ( j) (x) =
(U j−1,L (π ( j−1) x)) + a j℘j,L . Therefore
h(n) = k℘n,L k > kxk ≥ kπ ( j) xk ≥ |a j |k℘j k = |a j |h( j)
which implies the inequality |a j | < h(n)(h( j))−1 .
If a is an acceptable sequence with start(a) ≥ i then a j = 0 for all j = 1, . . . , i. By the inequality
proven above, for each j > i the number of choices for a j is at most 1 + 2h(n)(h( j))−1 .
We continue now the proof of Case III. For a fixed i > n/2 let pi be the probability of the following
event: there is an acceptable sequence a so that Aa . Clearly
pi ≤ ∑{P(Aa ) | a is acceptable and i = start(a)} .
Using our upper bound (7) on P(Aa ) and the upper bound in Lemma 3.18 for the number of acceptable
sequences we get
n
pi ≤ 2n−i (2(n − i)−1/5 M)(n−i)/2 3n−i ∏ h(n)(h( j))−1 .
j=i
Using that for all j ∈ [i, n] we have h(n)(h( j))−1 ≤ h(n)(h(i))−1 = M we get that
pi ≤ 3n−i 2(n−i)/2 M 3(n−i)/2 (n − i)−(n−i)/10 .
We give an upper bound on M.
n−i n−i n
M = h(n)/h(i) = exp c log n = exp c (log + log(n − i)) .
n n n−i
Since the function (1/x) log x takes its maximum at x = e in the interval [1, ∞), we have that (1/x) log x ≤
1/e < 1 if x ≥ 1. This yields
c n−i
M ≤ e exp c log(n − i) ≤ ec ec log(n−i) ≤ ec (n − i)c .
n
Substituting this into the upper bound on pi and using that c is sufficiently small we get pi ≤ (n −
i)−(n−i)/20 . Therefore the probability that there is an i so that Aa holds for a suitably chosen a is at most
n−n(log n)−1
∑ (n − i)−(n−i)/20 .
i=n/2
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
n −1/20 logn n
1
−1
pi ≤ 2 ≤ 2 exp − n − n log log n(log n) ≤ e−n/21 .
log n 20
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 40
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
Case IV. n > (5/4)1/(2c) , |Sa | ≤ (n − i0 )/10 and i ≤ bn/2c. (The last inequality implies i0 = bn/2c.)
For each acceptable sequence a with start(a) ≤ n/2 we will give an upper bound on the probability
of the event Aa . Then we will estimate the number of acceptable sequences with this property.
Suppose that L and a are fixed so that there is an x ∈ L with ϑ (x,L) = a. We have
π ( j) (x) = (U j−1,L (π ( j−1) )x) + a j℘j
for all j = 0, . . . , n − 1. Let Q = [n/2, n − 1]\Sa . If j ∈ Q then
(x,L)
ϑj = aj = 0 and so π ( j) (x) = U j−1,L (π ( j−1) x)
and therefore by the definition of U j−1,L we have that π ( j) (x) = π ( j−1) (x) + ρ j℘j for a uniquely defined
ρ j ∈ (−1/2, 1/2]. Let A0a be the event that “the number of integers j ∈ Q with |ρ j | < n−τ is at least n/4,”
where τ < 1/4 is chosen so that c is sufficiently small with respect to τ. (This definition is somewhat
different from the corresponding definition in Case III.) We show that Aa implies A0a and therefore
P(Aa ) ≤ P(A0a ); then we will prove the claimed upper bound on P(A0 ).
Assume that ¬A0a . Then there are at least n/5 integers j ∈ Q so that |ρ j | ≥ n−τ . Therefore
1 hn 2 1 hn 2
kxk2 ≥ ∑ ρ 2j k℘j k2 ≥ nn−2τ = n1−2τ
j∈Q 5 2 5 2
1 1−2τ n − (n/2) 1
= n exp −2c log n = n1−2τ n−c .
5 n 5
Since τ < 1/4 and c > 0 is sufficiently small with respect to τ this implies that kxk2 > n2c = (h(n))2 =
℘n2 , that is, ¬Aa holds, which completes the proof of the implication A0a ⇒ Aa .
In Case III we have seen that the random variables ρ j are independent and uniformly distributed
over [−1/2, 1/2]. Therefore the probability that “the number of integers j ∈ Q with |ρ j | < n−τ is at least
n/4” is no more than 2n/2 (2n−τ )n/4 . We get that
(8). P(Aa ) ≤ P(A0a ) ≤ 2n/2 (2n−τ )n/4 .
Now we estimate the number of acceptable sequences with start(a) ≤ n/2. This is no more than
the total number of acceptable sequences without any restrictions. By Lemma 3.18 this number is at
most ∏nj=1 3n 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) ≤ n/2 and Aa holds then using our upper bounds we get
n
p ≤ 2n/2 (2n−τ )n/4 3n ∏ (h(n)(h( j))−1 ) .
j=1
Using that h( j) = exp ((c j/n) log n) we can calculate the value of the product exactly:
n
n(n + 1) n−1
∏(h(n)(h( j)) ) = (e ) exp −c 2n log n = exp c 2 log n .
−1 c log n n
j=1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 41
M IKL ÓS A JTAI
Substituting this inequality in the upper bound on p we get:
n n n−1
log p ≤ log 2 − τ(log n + log 2) + n log 3 + c log n .
2 4 2
Since c > 0 is sufficiently small with respect to τ the term −(τn/4) log n will dominate in absolute value
therefore p ≤ n−τn/8 . This is our upper bound on the probability that there is an x ∈ L\{0, ±℘n,L } with
kxk ≤ k℘n,L k.
Summarizing the results of the four different cases we get the following:
Lemma 3.20. If L is the random lattice defined in Theorem 3.14, then the probability that ℘n,L is not a
shortest nonzero vector of L is at most 3e−n/21 .
Suppose that L is a random value of randn,h . We show now that with high probability for all i =
1, . . . , n, ℘i,n is a shortest nonzero vector in π (i) (L). Indeed if we multiply every element of π (i) L by the
number h(n)(h(i))−1 we get an i-dimensional triangular lattice K. We have ℘j,K = h(n)(h(i))−1℘j,L for
all j = 1, . . . , i. Therefore
n
−1
i j
k℘j,K k = h(n)(h(i)) k℘j,L k = exp c log n exp −c log n exp c log n
n n n
n − (i − j)
= exp c log n = h(n − (i − j)) .
n
Therefore k℘i,K k = h(n), k℘i−1,K k = h(n−1), . . . ,k℘1,K k = 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 ℘i,K = ℘n,J ,℘i−1,K =
℘n−1,J , . . . ,℘1,K = ℘1+(n−i),J and J is a random value of randn,h . Lemma 3.20 implies that with a
probability of at least 1 − 3e−n/21 we have that ℘n,J = ℘i,K = h(n)(h(i))−1℘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 ⊆ J, it is also a shortest nonzero vector in K and finally since π i (L) = h(n)−1 (h(i))K, the vector
℘i,L = h(n)−1 (h(i))℘i,K is a shortest nonzero vector in π i (L) with a probability of at least 1 − 3e−n/21 .
The probability that this happens for all i = 1, . . . , n simultaneously is at least 1 − 3ne−n/21 ≥ 1 − e−n/22
if n is sufficiently large. The definition of the basis bi = bi,L implies that π (i) bn−i+1 = ℘i,L , therefore if
we apply the Gram-Schmidt orthogonalization procedure to the basis bi then we get b∗i = ℘i and so the
probability that bi is a Korkine-Zolotareff basis is at least 1 − e−n/22 . Now
j
k℘j,L k = h( j) = exp c log n
n
implies the last equation of the Theorem.
This concludes the proof of Theorem 3.14 (and Theorem 1.3).
(B)
Definition 3.21. Assume that B = (b1 , . . . , bn ) is a basis of the lattice L and 1 ≤ i ≤ n. Then Pi will
denote the orthogonal projection of L onto the subspace orthogonal to b1 , . . . , bi−1 .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 42
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
Theorem 3.22. There exists an α > 0, so that if c > 0 is sufficiently small, k, n are positive integers
2 ≤ k ≤ n, and L is a random value of randn,g where g( j) = exp((c j/k) log k), bi = bi,L for i = 1, . . . , n,
and B = (b1 , . . . , bn ), then the following holds. Assume that pn,k is the probability of the following event:
(B) (B)
“For all i = 1, . . . , n − k the orthogonal projections of Pi bi , . . . , Pi bi+k−1 is a Korkine-Zolotareff basis
of the k-dimensional lattice generated by these vectors.” Then pn,k 6= 0 and pn,k ≥ 1 − (n − k)e−αk .
Proof. The second inequality is an immediate consequence of Theorem 3.14. Indeed for a fixed i let K
(B) (B) (B)
be the lattice generated by Pi bi , . . . , Pi bi+k−1 . Clearly Pi bi = π (i) bi . Therefore
k−i
exp c log k K
k
is a value of the random variable randk,h where h( j) = exp ((c j/k) log k). Therefore, by Theorem 3.14,
(B) (B)
the probability that Pi bi , . . . , Pi bi+k−1 is not a Korkine-Zolotareff basis is at most e−αk . The fact that
there are at most n − k choices for i implies the second inequality in the conclusion of the theorem.
If n is sufficiently large with respect to k then the proven second inequality does not imply pn,k 6= 0.
Still it can be shown by the Lovász Local Lemma that it holds. Actually the present situation is a very
simple special case of Lovász’s lemma so a direct proof and a corresponding probabilistic construction
can be easily given based on the following observation.
Let 0 < ε < 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 − ε. For
each τ > 0 let Aτ be the set of all x ∈ A with the property that if we take a random y ∈ A with uniform
distribution then P(Q(x, y)) ≥ 1 − τ. Then |A|−1 |Aτ | ≥ 1 − ε/τ. Indeed if we count the number of pairs
(x, y) with ¬Q(x, y) for all x ∈ A\Aτ together then we get that this number is at least (|A| − |Aτ |)τ|A|.
On the other hand from our assumption we know that this number is at most ε|A|2 which implies that
claimed inequality.
√ √
If we pick now τ = ε then we have |A|−1√ |Aτ | ≥ 1 − ε. Therefore for each x ∈ Aτ the number of
elements y ∈ Aτ with Q(x, y) is at least |A| − 2 ε|A|. This implies that if x0 ∈ Aτ then we may pick a
sequence of elements x0 , x1 , x2 , . . . , xm recursively (for an arbitrary m) so that for all i = 1, . . . , m, xi ∈ Aτ
and Q(xi−1 , xi ). 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τ but we can tell about all of the elements of Aτ/2 with high
probability that they are in Aτ . Therefore picking random elements and testing them whether they are in
Aτ (with high probability) we can build the sequence x0 , x1 , . . . , xm .
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.)
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 43
M IKL ÓS A JTAI
Theorem 3.23. There exist ε > 0, ε 0 > 0 so that for all positive integers k, n, k ≤ ε 0 n, there is an n-
dimensional lattice L and a basis b1 , . . . , bn in L so that if b∗1 , . . . , b∗n are the orthogonal vectors that
we get through Gram-Schmidt orthogonalization from the basis b1 , . . . , bn then the following holds. For
each s = 1, . . . , n − 2k − 1 we have
k 2k −2 1/k
∏ kb∗i k2 ∏
kb∗i k ≤ kε log k ,
i=s+1 i=s+k+1
n
kb1 k/λ1 (L) ≥ kε k , where λ1 (L) is the length of the shortest nonzero vector in L.
Proof. L will be a lattice whose existence is guaranteed by Theorem 3.22 with 2k in the place of k. We
have
∗ n−i+1
kbi k = g(n − i + 1) = exp c log 2k .
2k
This implies the first inequality. According to Minkowski’s convex body theorem we have
n 1/n
λ1 (L) ≤ n1/2 (det(L))1/n = n1/2 ∏ kb∗i k .
i=1
Using that and k ≤ ε 0 n we get kb1 k/λ1 (L) ≥ kεn/k .
4 The lower bound on the Korkine-Zolotareff constant αk
Definition 4.1. For each positive integer k and real number c we define a function Fk,c whose domain
2
is the set of all positive integers. For all i = 1, . . . , k let Fk,c (i) = ec(log k) and for all i = k, k + 1, . . . let
2
Fk,c (i) = ec(log i) .
Theorem 4.2. Assume that c > 0 is a sufficiently small real number and c1 > 0 is a sufficiently large
positive integer. For all n = 1, 2, . . . if L is a random value of the random variable randn,Fc1 ,c then the
following holds. With a probability of at least 1/2 the sequence bi = bi,L , i = 1, . . . , n is a Korkine-
Zolotareff reduced basis of the n-dimensional lattice L. Moreover the Gram-Schmidt orthogonalization
procedure applied to the basis b1 , . . . , bn yields the orthogonal vectors b∗i = ℘n−i+1,L , i = 1, . . . , n. If n is
−c log c1
sufficiently large with respect to c1 and c then we have kb1 kkb∗n k−1 ≥ nc log n c1 .
Theorem 1.9 formulated in Section 1.2 is an immediate consequence of Theorem 4.2.
Proof of Theorem 4.2. In the following lemma we summarize some of the elementary properties of
the function Fk,c .
Lemma 4.3. There exist α1 > 0, α2 > 0 so that if 0 < c < 1 and k is a positive integer then there is an
α3 > 0 so that for all positive integers n, i, n ≥ i the following inequalities hold.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 44
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
(9). if i ≥ n2 then
Fk,c (n)(Fk,c (i))−1 ≤ α1 n2c log(n/i) ;
if i ≥ n2 > k then
Fk,c (n)(Fk,c (i))−1 ≥ α2 n2c log(n/i) ;
(10). for all δ > 0 if c > 0 is sufficiently small and max{i, k} ≥ n − 2 log n then
(1 − δ )Fk,c (n) ≤ Fk,c (i) ;
(11). if 0 < ξ < 1, c is sufficiently small with respect to ξ , n is sufficiently large with respect to c and
ξ , n/2 < i < n − log n then Fk,c (n)(Fk,c (i))−1 ≤ (n − i)ξ .
Proof. (9). α1 and α2 are chosen when c and k are already fixed so we may assume that i and n are
2 2
sufficiently large with respect to c and k. Therefore Fk,c (n) = ec(log n) and Fk,c (i) = ec(log i) .
n 2 n n 2
c(log n)2 = c log i + log = c(log i)2 + 2c log i log + c log
i i i
n n n 2
2
= c(log i) + 2c log n log + 2c(log i − log n) log + c log .
i i i
The assumption n ≥ i ≥ n/2 implies that the absolute values of the last two terms remain below an
absolute constant. Therefore the ratio of Fk,c (n)n−2c log(n/i) and Fk,c (i) remains between two positive
constants.
(10). We have
Fk,c (n − 2 log n) = exp c(log(n − 2 log n))2
2 log n 2 2 log n 2
= exp c log n 1 − = exp c log n + log 1 −
n n
c(log n)2
2 log n 2 log n 2
=e exp 2c log n log 1 − + log 1 − .
n n
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 ε
in absolute value for any ε > 0 if n is sufficiently large and the first factor is Fk,c (n). Since Fk,c (i) is
monotone in the interval [n − 2 log n, n] this implies (10).
(11). Inequality (9) implies that there is an absolute constant c2 > 0 so that
Fk,c (n)(Fk,c (i))−1 ≤ c2 n2c log(n/i) .
Therefore we have to prove that (n − i)ξ c−1
2 n
−2c log(n/i) ≥ 1 provided that n/2 ≤ i < n − log n, c > 0
is sufficiently small with respect to ξ and n is sufficiently large with respect to c and ξ . Taking the
logarithm of both sides of the inequality we get
ξ log(n − i) − log c2 − 2c log n(log n − log i) ≥ 0 .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 45
M IKL ÓS A JTAI
We consider the left hand side as a function of i. Let f (x) = ξ log(n − x) − log c2 − 2c log n(log n − log x).
The derivative of f is
ξ 2c log n
f 0 (x) = − + .
n−x x
The function f 0 (x) is continuous on the interval [n/2, n − 1] and it has a single root
n
x0 =
1 + ξ /(2c log n)
in it (for this latter fact we use that n is sufficiently large with respect to c). Therefore f 0 (n/2) > 0
and f 0 (n − 1) < 0 implies that the function f is increasing from n/2 till x0 and then it is decreasing
from x0 till n − 1. So we can prove our inequality ξ log(n − i) − log c2 − 2c log n(log n − log i) ≥ 0
for all i ∈ [n/2, n − log n] by checking it at the endpoints. If i = n/2 then log n − log i ≤ log 2 and
log(n − i) ≥ (1/2) log n, therefore the assumption that c is sufficiently small with respect to ξ 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 ξ log(n − i) ≥ ξ log log n.
In this proof we will write F for Fc1 ,c . First we estimate the probability of the following event A:
“℘n,L is not a shortest nonzero vector in L.” Let let a = (a1 , . . . , an ) be a sequence of integers. We
estimate the probability of the event Aa : “there is an x ∈ L, x 6= 0 so that kxk < k℘n k and ϑ (x,L) = a.” Let
start(a) = i. Then Aa implies that i < n (otherwise we would have x = 0). We also have π (i) (x) = 0,
π (i+1) (x) 6= 0. We distinguish four cases depending on i; in each case, we shall estimate P(Aa ).
Case I. max{i, c1 } > n − (log n)2 . We show that in this case P(Aa ) = 0 since there is no x ∈ L with
kxk < k℘n k and ϑ x,L = a. Indeed assume that there is an x ∈ L with these properties. start(a) = i
implies a1 = · · · = ai = 0 and so according to the definition of ϑ (x,L) = a we have π ( j) (x) = 0 for
j = 1, . . . , i. ai+1 6= 0 and π (i+1) (x) = ai+1 π (i+1)℘i+1,L = (0, . . . , 0, ai+1 F(i + 1)). If i = n − 1 this implies
kxk ≥ ℘n,L in contradiction to our assumption. Therefore i < n − 1. (5) implies that
1
π (i+2) (x) = Ui+1 (ai+1 π (i+1)℘i,L ) = (0, . . . , 0, ai+1 F(i + 1), F(i + 2)) .
2
Consequently
1
kxk2 ≥ kπ (i+2) xk2 ≥ (F(i + 1))2 + (F(i + 2))2 .
4
So the assumption max{i, c1 } > n − (log n) and (10) implies that kxk2 ≥ (F(n))2 = k℘n,L k2 in contra-
2
diction to our indirect assumption.
Case II. n − (log n)2 ≥ max{i, c1 } and |Sa | > (1/10)|n − i0 | where i0 = max{i, dn/2e} and Sa = { j ∈
0
[i , n] | a j 6= 0}. In this case we will use the following inequality:
(12). for all γ > 0, for all c with 0 < c < 1/20, for all sufficiently large n and for all x with n/2 ≤ x <
n − (log n)2 we have (n − x)n−4c log(n/x) > γ.
Taking the logarithm of the left hand side ofR the inequality we get ` = log(n − x) − 4c log n(log n −
log x). Since x ≥ n/2 we have log n − log x = xn 1/y dy ≤ xn 1/(n/2) dy = 2n−1 (n − x). This implies
R
√
that ` ≥ log(n − x) − 8cn−1 (n − x) log n. If n − x ≤ n then the assumption x < n − (log n)2 implies that
` ≥ log((log n)2 ) − 8cn−1 n1/2 log n ≥ log γ if n is sufficiently large.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 46
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
√
If n−x ≥ n then ` ≥ (1/2) log n−8cn−1 n log n ≥ (1/2) log n−8c log n. Since c < 1/20 this implies
that ` ≥ log γ which completes the proof of (12).
We return now to the discussion of Case II. We show that in this case again P(Aa ) = 0 since there is
no x ∈ L with ϑ x,L = a and kxk < k℘n k. Indeed assume that there is an x ∈ L with these properties. By
Lemma 3.10 and Lemma 4.3 we have
1 1
kxk2 ≥
4 ∑{k℘j k2 | a j 6= 0, j ∈ [i0 , n]} ≥ |Sx | · k℘i0 k2 ≥ |Sx |(F(i0 ))2
4
1 2 1 0 1 0
> α1 (n − i0 )n−4c log(n/i ) (F(n))2 = α12 (n − i0 )n−4c log(n/i ) k℘n k2 .
4 10 40
Since i0 ≥ n/2 and c is sufficiently small, inequality (12) is applicable with the substitutions x := i0 ,
γ := 40α1−2 and we get kxk2 ≥ k℘n k2 in contradiction to our indirect assumption. (Our assumption
n − (log n)2 ≥ max{i, c1 } implies that n > c1 . c1 is sufficiently large with respect to c by the assumptions
of Theorem 4.2, and so n is also sufficiently large with respect to c as required in (12).)
Case III. n − (log n)2 ≥ max{i, c1 }, |Sa | ≤ (n − i0 )/10 and i > bn/2c. (The last inequality implies
0
i = i.) We estimate P(a) in terms of i.
Suppose that L and a are fixed so that there is an x ∈ L with ϑ (x,L) = a. By the definition of ϑ (x,L) ,
x is unique with this property. Moreover if we follow the recursive definition of the randomization of
L = randn,F then in each step together with π ( j) (L) we also get π j (x) since by the definition of ϑ x,L we
have π ( j) (x) = (U j−1,L (π ( j−1) )x) + a j℘j .
(x,L)
Let Q = [i + 2, n − 1]\Sa . If j ∈ Q then ϑ j = a j = 0 and so π ( j) (x) = U j−1,L (π ( j−1) x) and
therefore by the definition of U j−1,L we have that π ( j) (x) = π ( j−1) (x) + ρ j℘j for a uniquely defined
ρ j ∈ (−1/2, 1/2]. Let M = F(n)(F(i))−1 and let A0a be the event that “the number of integers j ∈ Q with
|ρ j | < (n − i)−1/5 M is at least (n − i)/2.” We show that Aa implies A0a and therefore P(Aa ) ≤ P(A0a ), then
we will prove an upper bound on P(A0 ). Assume that ¬A0a . Then there are at least 4(n − i)/10 integers
j ∈ Q so that |ρ j | ≥ (n − i)−1/5 M. Therefore
4
kxk2 ≥ ∑ ρ 2j k℘j k2 ≥ (n − i)(n − i)−2/5 M 2 (F(i))2
j∈Q 10
4 2 4
≥ (n − i)3/5 F(n)(F(i))−1 (F(i))2 ≥ (n − i)3/5 (F(n))2 ≥ ℘n2
10 10
so we reached a contradiction. Therefore ¬Aa holds, which completes the proof of the implication
A0a ⇒ Aa .
Now we estimate P(A0a ). Suppose j ∈ Q. ρ j was defined by the conditions π ( j) (x) = π ( j−1) (x) +
ρ j℘j , ρ j ∈ (−1/2, 1/2]. Therefore the definitions of rand, ext and Lemma 2.1 imply that if π ( j−1) (x) is
linearly independent of ℘j−1 then ρ j is uniformly distributed over [−1/2, 1/2]. However if π ( j−1) (x) 6= 0
and ℘j−1 are dependent then by (3) start(a) = j − 1. Since i = start(a), Q ⊆ [i + 2, n] this contradicts
to j ∈ Q. Therefore the distribution of ρ j is uniform over [−1/2, 1/2]. The definition of rand implies that
the random variables ρ j , j ∈ Q are mutually independent. Therefore the probability that “the number of
integers j ∈ Q with |ρ j | < (n − i)−1/5 M is at least (n − i)/2” is no more than 2n−i (2(n − i)−1/5 M)(n−i)/2 .
We get that
(13). P(Aa ) ≤ P(A0a ) ≤ 2n−i (2(n − i)−1/5 M)(n−i)/2 .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 47
M IKL ÓS A JTAI
We use here the notion that a sequence a = (a1 , . . . , an ) is acceptable as defined before the statement
of Lemma 3.18. In this case we use the definition with h := F.
For a fixed i > n/2, let pi denote the probability that there is an acceptable sequence a with
start(a) = i so that Aa holds. By the union bound, pi ≤ ∑{P(Aa ) | a is acceptable and start(a) = i}.
n
pi, ≤ 2n−i (2(n − i)−1/5 M)(n−i)/2 3n−i ∏(F(n)(F( j))−1 ) .
j=i
Using that for all j ∈ [i, n] we have
F(n)(F( j))−1 ≤ F(n)(F(i))−1 = M
we get that pi ≤ 3n−i 23(n−i)/2 M 3(n−i)/2 (n − i)−(n−i)/10 . By (11) M ≤ (n − i)ξ for a small constant ξ > 0
so we get pi ≤ (n − i)−(n−i)/20 . Therefore the probability that there is an i so that Aa holds for a suitably
chosen a is at most
n−(log n)2 ∞
∑ (n − i)−(n−i)/20 ≤ ∑ k−k/20 .
i=n/2 k=(log n)2
We have that k−k/20 /(k + 1)−(k+1)/20 ≥ (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 /20 (log n) log log n
2((log n) ) ≤ exp −
11
if n is sufficiently large; this, however, follows from n − (log n)2 > c1 .
Case IV. n − (log n)2 ≥ max{i, c1 }, |Sa | ≤ (n − i0 )/10 and i ≤ bn/2c. (The last inequality implies
0
i = bn/2c.)
For each acceptable sequence a with start(a) ≤ n/2 we will give an upper bound on the probability
of the event Aa . Then we will estimate the number of acceptable sequences a with Aa .
Suppose that L and a are fixed so that there is an x ∈ L with ϑ (x,L) = a. We have π ( j) (x) =
(U j−1,L (π ( j−1) )x) + a j℘j for all j = 0, . . . , n − 1.
(x,L)
Let Q = [n/2, n − 1]\Sa . If j ∈ Q then ϑ j = a j = 0 and so π ( j) (x) = U j−1,L (π ( j−1) x) and
therefore by the definition of U j−1,L we have that π ( j) (x) = π ( j−1) (x) + ρ j℘j for a uniquely defined
ρ j ∈ (−1/2, 1/2]. Let A0a be the event that “the number of integers j ∈ Q with |ρ j | < n−τ is at least
n/4,” where τ < 1/4 is chosen so that c is sufficiently small with respect to τ. (This definition is some-
what different from the corresponding definition in Case III.) We show that Aa implies A0a and therefore
P(Aa ) ≤ P(A0a ), then we will prove an upper bound on P(A0a ). Assume that ¬A0a . Then there are at least
n/5 integers j ∈ Q so that |ρ j | ≥ n−τ . Therefore
1 1
kxk2 ≥ ∑ ρ 2j k℘j k2 ≥ nn−2τ (F(n/2))2 = n1−2τ (F(n/2))2 .
j∈Q 5 5
Thus (11) implies that kxk2 ≥ (F(n))2 = ℘n2 , that is, ¬Aa holds, which completes the proof of the
implication A0a ⇒ Aa .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 48
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
In Case III we have seen that the random variables ρ j are independent and uniformly distributed
over [−1/2, 1/2]. Therefore the probability that “the number of integers j ∈ Q with |ρ j | < n−τ is at least
n/4” is no more than 2n/2 (2n−τ )n/4 . We get that
(14). P(Aa ) ≤ P(A0a ) ≤ 2n/2 (2n−τ )n/4 .
Let p denote the probability that there is an acceptable sequence a with start(a) ≤ n/2 so that Aa
holds. Again by the union bound, p ≤ ∑{P(Aa ) | a is acceptable and start(a) ≤ n/2}. We use (14) as
an upper bound on P(Aa ). 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 3n ∏nj=1 F(n)(F( j))−1
provided by Lemma 3.18.
2
To get an upper bound on this product we need a lower bound on ∏nj=1 (F( j))−1 ≥ c2 ∏nj=1 e−c(log j) ,
where c2 > 0 depends only on c and c1 . Using that
Z
(log x)2 dx = x(log x)2 − 2x log x + 2x +C
we give an upper bound on ∑nj=1 c(log j)2 . Since the function (log x)2 is monotone we have
n Z n
∑ c(log j)2 ≤ c 1
(log x)2 dx + (log n)2
j=1
= c n(log n)2 − 2n log n + 2n − 2 + (log n)2 .
Substituting this inequality in the upper bound on p we get:
2
p ≤ 2n/2 (2n−τ )n/4 3n ecn(log n) exp −c n(log n)2 − 2n log n + 2n − 2 + (log n)2
≤ 2n/2 (2n−τ )n/4 3n exp 2cn log n − 2cn − c(log n)2 + 2c) .
Therefore, if c > 0 is sufficiently small with respect to τ then p ≤ n−τn/8 . In other words in Case IV
the probability that there is an a so that Aa holds for some suitably chosen a is at most n−τn/8 assuming
τ < 1/4 and c is sufficiently small with respect to τ.
Summarizing the results of the four different cases we get the following:
Lemma 4.4. If L is the random lattice defined in Theorem 4.2, then the probability that ℘n,L is not a
shortest nonzero vector of L is at most exp (−(1/12) log n log log n). If n ≤ c1 then ℘n,L is always a
shortest nonzero vector.
Suppose that L is a random value of randn,F . The definition of the random variable rand implies
that π (i) L for any i ≤ n is a random value of randi,F . Therefore Lemma 4.4 implies that the probability
qn of the event that there is an i ≤ n such that ℘i,L is not a shortest nonzero vector in π (i) (L) is at most
n
(logt) log logt
∑ exp − 21
.
t=c1
∞
As n → ∞, this series converges (because it is dominated by ∑t=1 t −2 ); therefore, if c1 is sufficiently large
(i)
then qn ≤ 1/2. If i ≤ c1 then π L has an orthogonal basis consisting of vectors of the same length so each
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 49
M IKL ÓS A JTAI
of them is a shortest nonzero vector. This also implies that qn = 0 for n ≤ c1 . Therefore qn ≤ 1/2 for all
positive integers n. The definition of the basis bi,L , i = 1, . . . , n implies that π (n−i+1) bi,L = ℘n−i+1,L and
so applying the Gram-Schmidt orthogonalization process to it indeed yields the vectors b∗i = ℘n−i+1,L ,
i = 1, . . . , n. The fact that ℘i,L is a shortest vector in π (i) (L) for all i = 1, . . . , n then implies that bi,L is a
Korkine-Zolotareff basis. The final inequality of the theorem holds since kb1 k = k℘n,L k = F(n) ≥ nc log n
c log c
and kb∗n k = k℘1,L k = c11 1 . This concludes the proof of Theorem 4.2.
References
[1] * M. A JTAI: Random lattices and a conjectured 0—1 law about their polynomial time
computable properties. In Proc. 43rd FOCS, pp. 733–742. IEEE Computer Society, 2002.
[FOCS:10.1109/SFCS.2002.1181998]. 2
[2] * M. A JTAI: The worst-case behavior of Schnorr’s algorithm approximating the short-
est nonzero vector in a lattice. In Proc. 35th STOC, pp. 396–406. ACM Press, 2003.
[STOC:10.1145/780542.780602]. ∗
[3] * M. A JTAI: Generating hard instances of lattice problems. In J. K RAJI ČEK, editor, Complexity of
computations and proofs, volume 13 of Quaderni di Matematica, pp. 1–32. Seconda Universita di
Napoli, 2004. Preliminary version: Proc. 28th STOC, 1996, pp. 99–108. 2
[4] * M. A JTAI , R. K UMAR , AND D. S IVAKUMAR: A sieve algorithm for the shortest lattice vector
problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 1996. [STOC:10.1145/380752.380857].
1.1, 1.3, 1.10
[5] * M. L. F URST AND R. K ANNAN: Succinct certificates for almost all subset problems. SIAM
Journal on Computing, 18:550–558, 1989. [SICOMP:10.1137/0218037]. 1.3
[6] * C. F. G AUSS: Recursion der “untersuchungen über die eigenschaften der positiven ternären
quadratische formen von ludwig august seeber, dr. der philosophie, ordentl. professor der univer-
sität in freiburg, 1831, 248 s. in 4.”. Journal für die reine und angewandte Mathematik, 20:312–320,
1840. 1.1
[7] * A. M. O DLYZKO J. C. L AGARIAS: Solving low-density subset sum problems. Journal of the
Association for Computing Machinery, 32(1):229–246, 1985. [JACM:10.1145/2455.2461]. 1.4
[8] * R. K ANNAN: Algorithmic geometry of numbers. In Annual Review of Computer Science, vol-
ume 2, pp. 231–269. Annual Reviews Inc., 1987. 1.1
[9] * R. K ANNAN: Minkowski’s convex body theorem and integer programming. Mathematics of
Operation Research, 12(3):415–440, 1987. 1.1, 1.3, 3
[10] * A. KORKINE AND G. Z OLOTAREFF: Sur les formes quadratiques. Mathematische Annalen,
6:366–389, 1873. [Springer:p56345710m4p6214]. 2
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 50
O PTIMAL BOUNDS FOR LATTICE PARAMETERS AND S CHNORR ’ S ALGORITHM
[11] * J. L. L AGRANGE: Recherches d’arithmétique. In M. J.-A. S ERRET, editor, Oeuvres de La-
grange, volume 3, pp. 698–701. Gauthier-Villars, 1869. (article cca 1773). 1.1
[12] * A. K. L ENSTRA , H. W. L ENSTRA , AND L. L OV ÁSZ: Factoring polynomials with rational
coefficients. Mathematische Annalen, 261:515–534, 1982. [Springer:lh1m24436431g068]. 1.1
[13] * A. M. O DLYZKO AND H. TE R IELE: Disproof of the Mertens conjecture. Journal für die reine
und angewandte Mathematik, 357:138–160, 1985. 1.4
[14] * C.-P. S CHNORR: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical
Computer Science, 53:201–224, 1987. [TCS:10.1016/0304-3975(87)90064-8]. 1.1, 1, 3
[15] * C.-P. S CHNORR: Lattice reduction by random sampling and birthday methods. In Proc. 20th
Ann. Symp. on Theoretical Aspects of Computer Science (STACS’03), volume 2607 of Lecture
Notes in Computer Science, pp. 145–156. Springer, 2003. [STACS:qjpadpmwabty52g4]. 1.1
AUTHOR
Miklós Ajtai
IBM Almaden Research Center
ajtai almaden ibm com
ABOUT THE AUTHOR
M IKL ÓS A JTAI received his Ph. D. from the Hungarian Academy of Sciences in 1975. His
advisor was András 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.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 21–51 51