Block Korkin–Zolotarev Bases and Successive Minima

C.P.Schnorr

Universitt Frankfurt

Fachbereich Mathematik/Informatik

February 5, 1996

Abstract

Let b_{1}, …, b_{m} ∈ IR^{n} be an arbitrary basis of lattice L that is a block Korkin–Zolotarev basis with block size β and let λ_{i}(L) denote the successive minima of lattice L. We prove that for i = 1, …, m

\frac{4}{i + 3} γ_{β}^{−2 \frac{i−1}{β−1}} ≤ ∥b_{i}∥^{2}/λ_{i}(L)^{2} ≤ γ_{β}^{2 \frac{m−i}{β−1}} \frac{i + 3}{4}

where γ_{β} is the Hermite constant. For β = 3 we establish the optimal upper bound

∥b_{1}∥^{2}/λ_{1}(L)^{2} ≤ (\frac{3}{2})^{\frac{m−1}{2} −1}

and we present block Korkin–Zolotarev lattice bases for which this bound is tight.

We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin–Zolotarev bases. Given a block Korkin–Zolotarev basis b_{1}, …, b_{m} with block size β and x ∈ L(b_{1}, …, b_{m}) a lattice point v can

be found in time β^{O(β)} satisfying ∥x−v∥^{2} ≤ m γβ^{\frac{2m}{β−1}} min_{u∈L} ∥x − u∥^{2}.

1 Introduction

The problem of selecting from all bases for a lattice a canonical basis consisting of short vectors is called reduction theory. Classical reduction theory was developed in the language of quadratic forms by Lagrange (1773), Hermite (1850) and Korkin and Zolotarev (1873) in order to determine the minima of positive definite integral quadratic forms. Recently there has been renewed interest in reduction theory stimulated by a new method in integer programming (H.W. Lenstra, Jr. 1983) and by Lovász’ lattice basis reduction algorithm, see A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász (1982), which has had various applications.

From the computational point of view the reduction theory introduced by Hermite and by Korkin and Zolotarev is the most natural one. On the other hand Korkin–Zolotarev reduced lattice bases are not easy to find for lattices of higher dimensions, see Kannan (1987) and Schnorr (1987) for algorithms. This led Schnorr (1987) to introduce a hierarchy of block Korkin–Zolotarev bases comprising for block size 2 the L^{3}–reduced bases introduced by Lenstra, Lenstra, Lovász (1982). Block Korkin– Zolotarev bases with maximal block size are just Korkin–Zolotarev bases.

In this paper we prove new upper and lower bounds for the ratio ∥b_{i}∥^{2}/λ_{i}^{2} where b_{1}, …, b_{m} is any block Korkin–Zolotarev basis and λ_{i} is the i–th successive minimum of the lattice. These bounds extend the known bounds for L^{3}–reduced bases and for Korkin–Zolotarev bases.

We state in Section 2, Theorems 3 and 4 the new lower and upper bounds for the ration ∥b_{i}∥^{2}/λ_{i}^{2}. We prove these bounds in Section 3. In Section 4 we apply block Korkin–Zolotarev bases to the problem of finding approximate nearest lattice points. In Section 5 we prove that the upper bound ∥b_{1}∥^{2} ≤

(\frac{3}{2})^{\frac{m−1}{2} −1} λ_{1}^{2} is optimal for block Korkin–Zolotarev bases of block size 3. We present block Korkin–Zolotarev bases for which this bound is tight.

2 Reduced Bases and Successive Minima

Let IR^{n} be the n–dimensional real vector space with the Euclidean inner product < , > and the Euclidean norm, called the length, ∥y∥ = ⟨y, y⟩^{1/2}. A lattice L ⊂ IR^{n} is a discrete, additive subgroup of the IR^{m}. Its rank is the dimension of the minimal subspace span(L) that contains L. Each lattice L of rank m has a basis, i.e. a sequence b_{1}, …, b_{m} of linearly independent vectors that generate L as an abelian group,

L = {t_{1}b_{1} + … + t_{m}b_{m} | t_{1}, …, t_{m} ∈ ZZ}.

Let L(b_{1}, …, b_{m}) denote the lattice with basis b_{1}, …, b_{m}. Its determinant d(L) is defined as

d(L) = det[⟨b_{i}, b_{j}⟩]_{1≤i,j≤m}^{1/2}.

This does not depend on the choice of the basis. The i–th successive minimum λ_{i}(L) of a lattice L (with respect to the Euclidean norm) is the smallest real number r such that there are i linearly independent vectors in L of length at most r.

With an ordered lattice basis b_{1}, …, b_{m} ∈ IR^{n} we associate the Gram– Schmidt orthogonalization b̂_{1}, …, b̂_{m} ∈ IR^{n} which can be computed together with the Gram–Schmidt coefficients μ_{i,j} = ⟨b_{i}, b̂_{j}⟩ / ⟨b̂_{j}, b̂_{j}⟩ by the recursion

b̂_{1} = b_{1}, b̂_{i} = b_{i} − ∑_{j=1}^{i−1} μ_{i,j}b̂_{j} for i = 2, …, m.

We have μ_{i,i} = 1 and μ_{i,j} = 0 for i < j. From the above equations we have the Gram–Schmidt decomposition

[b_{1}, …, b_{m}] = [b̂_{1}, …, b̂_{m}] [μ_{i,j}]_{1≤i,j≤m}^{⊤},

where [b_{1}, …, b_{m}] denotes the matrix with column vectors b_{1}, …, b_{m}.

With an ordered lattice basis b_{1}, …, b_{m} of the lattice L we associate the orthogonal projections

π_{i} : span(b_{1}, …, b_{m}) ↦ span(b_{1}, …, b_{i−1})^{⊥} i = 1, …, m ,

where span(b_{1}, …, b_{m}) denotes the linear space generated by the vectors b_{1}, …, b_{m}. We let L_{i} denote the lattice

L_{i} = π_{i}(L) .

The lattice L_{i} has rank m − i + 1 and basis π_{i}(b_{i}), π_{i}(b_{i+1}), …, π_{i}(b_{m}). We have π_{i}(b_{i}) = b̂_{i} and π_{i}(b_{j}) = ∑_{k=i}^{m} μ_{j,k}b̂_{k}.

An ordered basis b_{1}, …, b_{m} of the lattice L ⊂ IR^{n} is a Korkin–Zolotarev basis if it satisfies the conditions

|μ_{i,j}| ≤ 1/2  for 1 ≤ j < i ≤ m,  (1)
∥b̂_{i}∥ = λ_{1}(L_{i}) for i = 1, …, m.  (2)

This definition is equivalent to the one given, in the language of quadratic forms, by Hermite in his second letter to Jacobi (1845) and by Korkin and Zolotarev (1873).

Let b_{1}, …, b_{m} be an ordered basis of the lattice L ⊂ IR^{n}. We call the basis b_{1}, …, b_{m} an β–BKZ basis, i.e. a block Korkin–Zolotarev basis with block size β, if it satisfies (1) and

π_{i}(b_{i}), π_{i}(b_{i+1}), …, π_{i}(b_{i+β−1}) are Korkin–Zolotarev bases for
i = 1, …, m − β + 1.  (3)

The condition (3) means that for i = 1, …, m − 1 the vector b̂_{i} = π_{i}(b_{i}) is a shortest non–zero vector in the lattice π_{i}(L(b_{1}, …, b_{min(i+β−1,m))}) = L(π_{i}(b_{i}), …, π_{i}(b_{min(i+β−1,m)})). If (1) holds and if β = 2 the condition (3) is equivalent to

∥b̂_{i}∥^{2} ≤ ∥π_{i}(b_{i+1})∥^{2} = ∥b̂_{i+1}∥^{2} + μ_{i+1,i}^{2}∥b̂_{i}∥^{2} for i = 1, …, m − 1. (4)

We see that a basis b_{1}, …, b_{m} is 2 - BKZ iff it satisfies (1) and (4). These bases have been introduced by A.K. Lenstra, H.W. Lenstra, Jr. and Lovász (1982). We call a basis b_{1}, …, b_{m} L^{3}-reduced with δ ∈ (\frac{1}{4}, 1] if it satisfies (1) and

δ∥b̂_{i}∥^{2} ≤ ∥b̂_{i+1}∥^{2} + μ_{i+1,i}^{2}∥b̂_{i}∥^{2} for i = 1, …, m − 1. (5)

Lenstra et alii (1983) have in particular considered δ = 3/4. From their work we have the following

Theorem 1 Every basis b_{1}, …, b_{m} of lattice L that is L^{3}–reduced with δ ∈ (\frac{1}{4}, 1] satisfies with α = 1/(δ − \frac{1}{4}):

α^{1−i} ≤ ∥b̂_{i}∥^{2}λ_{i}(L)^{−2} ≤ ∥b_{i}∥^{2}λ_{i}(L)^{−2} ≤ α^{m−1} for i = 1, …, m.

In the limit case δ = 1 we have α = 4/3, and thus every 2 - BKZ basis b_{1}, …, b_{m} of lattice L satisfies for i = 1, …, m

(\frac{3}{4})^{i−1} ≤ ∥b̂_{i}∥^{2}λ_{i}(L)^{−2} ≤ ∥b_{i}∥^{2}λ_{i}(L)^{−2} ≤ (\frac{4}{3})^{m−1} . (6)

A β–BKZ basis b_{1}, …, b_{m} with maximal block size β = m is a Korkin– Zolotarev basis. For these bases we have the following bounds on ∥b_{i}∥^{2}λ_{i}^{−2}, where the upper bound is essentially due to Mahler (1938) and the lower bound is from Lagarias, H.W. Lenstra, Jr., Schnorr (1990).

Theorem 2 Every Korkin–Zolotarev basis b_{1}, …, b_{m} of lattice L satisfies \frac{4}{i+3} ≤ ∥b_{i}∥^{2}λ_{i}(L)^{−2} ≤ \frac{i+3}{4} for i = 1, …, m.

We are going to extend Theorems 1 and 2 to arbitrary β–BKZ bases. For this we use the Hermite constants γ_{m} which is defined as

γ_{m} = sup{λ_{1}(L)^{2}d(L)^{−2/m} : for lattices L of rank m}.

Its value is known for m ≤ 8, see Cassels (1971), Appendix. We have γ_{2}^{2} = \frac{4}{3}, γ_{3}^{3} = 2, γ_{4}^{4} = 4, γ_{5}^{5} = 8, γ_{6}^{6} = 2^{6}/3, γ_{7}^{7} = 2^{6}, γ_{8}^{8} = 2^{8}. It is known that γ_{m} ≤ \frac{2}{3}m for m ≥ 2 and

\frac{m}{2πe} + O(m) ≤ γ_{m} ≤ \frac{0.872m}{πe}(1 + o(1)) as m → ∞,

where the upper bound is due to Kabatyanskii and Levenshtein (1978) and the lower bound follows from the Minkowski–Hlawka theorem, see Cassels (1971), VI. 2.2. Theorems 3 and 4 below will be proved in Section 2.

Theorem 3 Every β-BKZ basis b_{1}, …, b_{m} of lattice L satisfies

∥b̂_{i}∥^{2}λ_{i}(L)^{−2} ≤ γ_{β}^{2 \frac{m−i}{β−1}} for i = 1, …, m

∥b_{i}∥^{2}λ_{i}(L)^{−2} ≤ γ_{β}^{2 \frac{m−1}{β−1}} \frac{i + 3}{4} for i = 1, …, m.

Theorem 3 improves and extends the inequality ∥b_{1}∥^{2} ≤ (6β^{2})^{\frac{m}{β}} λ_{1}(L)^{2} of Schnorr (1987). In particular we have for β = 2, γ_{2}^{2} = \frac{4}{3} that

∥b̂_{i}∥^{2}λ_{i}(L)^{−2} ≤ (\frac{4}{3})^{m−i} for i = 1, …, m

∥b_{i}∥^{2}λ_{i}(L)^{−2} ≤ (\frac{4}{3})^{m−1} \frac{i + 3}{4} for i = 1, …, m

which is almost the upper bound of (6). It is remarkable that if the block size β is a fixed fraction of the rank, i.e. if m/β is fixed, then the upper bounds of Theorem 3 are polynomial in β.

We next consider lower bounds for ∥b_{i}∥^{2}λ_{i}(L)^{−2}, i.e. upper bounds for λ_{i}(L)^{2}∥b_{i}∥^{−2}.

Theorem 4 Every β-BKZ basis b_{1}, …, b_{m} of lattice L satisfies

λ_{i}(L)^{2}∥b_{i}∥^{−2} ≤ γ_{β}^{2 \frac{i−1}{β−1}} \frac{i + 3}{4} for i = 1, …, m.

For i ≤ β the bounds of Theorems 3 and 4 can be replaced by the stronger bounds of Theorem 2.

If the block size β is a fixed fraction of the rank m the upper bounds in Theorem 4 are polynomial in β. For block size β = 2, γ_{β}^{2} = \frac{4}{3} Theorem 4 yields

(\frac{4}{3})^{i−1} \frac{i + 3}{4} ≤ ∥b̂_{i}∥^{2}λ_{i}(L)^{2} for i = 1, …, m

which is almost the lower bound from (6).

The values γβ^{\frac{2}{β−1}} , appearing in Theorems 3 and 4, are known for β = 2, …, 8 :

\begin{matrix}β & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ γβ^{\frac{2}{β−1}} & \frac{4}{3} & 2^{1/3} & 2^{1/3} & 2^{\frac{3}{10}} & 2^{\frac{2}{5}} 3^{− \frac{1}{15}} & 2^{2/7} & 2^{1/4} \\ ≈ & 1.333 & 1.260 & 1.260 & 1.231 & 1.226 & 1.219 & 1.189 \end{matrix}

It is interesting to find the minimal constants c_{β,m} for which

∥b_{1}∥^{2} λ_{1}(L)^{−2} ≤ c_{β,m}

holds for all β–BKZ bases b_{1}, …, b_{m} of rank m. Bachem and Kannan

(1984) show that c_{2,m} = (\frac{4}{3})^{m−1}. We prove in Section 5 that c_{3,m} = \sqrt{\frac{3}{2}}^{m−3} holds for odd m. Thus the upper bounds from Theorem 3 are not optimal

for β ≥ 3. For β = 3 we can replace γβ^{\frac{2}{β−1}} = 2^{1/3} by \sqrt{3/2} ≈ 1.225 which is

even smaller than the value γ6^{\frac{2}{5}} for 6–BKZ bases.

3 Proofs for Theorems 3 and 4.

Proposition 5 For every β–BKZ basis b_{1}, …, b_{m} with m ≥ β we have for

M = max(∥b̂_{m−β+2}∥, …, ∥b̂_{m}∥) that ∥b_{1}∥ ≤ γβ^{\frac{m−1}{β−1}} M.

Proof. We extend the basis b_{1}, …, b_{m} by β − 2 additional vectors to

b_{−β+3}, …, b_{−1}, b_{0}, b_{1}, …, b_{m} (7)

such that

1. ∥b_{i}∥ = ∥b_{1}∥ for i ≤ 0

2. ⟨b_{i}, b_{j}⟩ = 0 for i ≤ 0 , i ≠ j and for j = −β + 3, …, m. The basis 7 is a β–BKZ basis of rank at least 2(β − 1). By definition of the Hermite constant γ_{β} we have

∥b̂_{i}∥^{β} ≤ γ_{β}^{β/2}∥b̂_{i}∥∥b̂_{i+1}∥ ⋯ ∥b̂_{i+β−1}∥ for i = −β + 3, …, m − β + 1.

Multiplication of these m − 1 inequalities yields

∥b̂_{−β+3}∥^{β}∥b̂_{−β+4}∥^{β} ⋯ ∥b̂_{m−β+1}∥^{β} ≤

γ_{β}^{β(m−1)/2}∥b̂_{−β+3}∥^{1}∥b̂_{−β+4}∥^{2} ⋯ ∥b̂_{1}∥^{β−1}∥b̂_{2}∥^{β} ⋯ ∥b̂_{m−β+1}∥^{β}
∥b̂_{m−β+2}∥^{β−1} ⋯ ∥b̂_{m−1}∥^{2}∥b̂_{m}∥^{1}.

This implies

∥b̂_{−β+3}∥^{β−1}∥b̂_{−β+4}∥^{β−2} ⋯ ∥b̂_{0}∥^{2} ∥b̂_{1}∥^{1} ≤
γ_{β}^{β(m−1)/2}∥b̂_{m−β+2}∥^{β−1} ⋯ ∥b̂_{m−1}∥^{2}∥b̂_{m}∥^{1}.

Hence

∥b_{1}∥^{\binom{β}{2}} ≤ γ_{β}^{β(m−1)/2}M^{\binom{β}{2}} and thus ∥b_{1}∥ ≤ γβ^{\frac{m−1}{β−1}} M. □

Corollary 6 Every β-BKZ basis b_{1}, …, b_{m} of the lattice L satisfies

∥b_{1}∥^{2} ≤ γ_{β}^{2 \frac{m−1}{β−1}} \frac{i + 3}{4} λ_{1}(L)^{2} .

Proof. If m ≤ β we have ∥b_{1}∥ = λ_{1}(L) and the claim holds. Now let m > β and let v be a shortest non–zero lattice vector. W.l.o.g. we can assume that v ∉ L(b_{1}, …, b_{m−1}) for otherwise we can reduce m and the claim holds by induction on m. If v ∉ L(b_{1}, …, b_{m−1}) we have

λ_{1}(L) = ∥v∥ ≥ λ_{1}(L_{i}) = ∥b̂_{i}∥ for i = m − β + 1, …, m.

This shows that λ_{1}(L) ≥ max(∥b̂_{m−β+2}∥, …, ∥b̂_{m}∥) and thus the claim follows from Proposition 5. □

Proof of Theorem 3. Application of Corollary 6 to the lattice L_{i} = π_{i}(L) yields the inequalities

∥b̂_{i}∥^{2} ≤ γ_{β}^{2 \frac{m−i}{β−1}} λ_{1}(L_{i})^{2} for i = 1, …, m. (8)

Moreover we have λ_{1}(L_{i}) ≤ λ_{i}(L). This is because there are i linearly independent vectors of length at most λ_{i}(L) in L and at least one of these vectors v satisfies π_{i}(v) ≠ 0. Hence λ_{1}(L_{i}) ≤ ∥π_{i}(v)∥ ≤ λ_{i}(L). Using the Inequalities 8 and μ_{i,j}^{2} ≤ 1/4 we obtain for i = 1, …, m

∥b_{i}∥^{2} = ∥b̂_{i}∥^{2} + ∑_{j=1}^{i−1} μ_{i,j}^{2} ∥b̂_{j}∥^{2}

≤ γ_{β}^{2 \frac{m−i}{β−1}} λ_{i}(L)^{2} + \frac{1}{4} ∑_{j=1}^{i−1} γ_{β}^{2 \frac{m−j}{β−1}} λ_{j}(L)^{2}

≤ γβ^{\frac{2m}{β−1}} (γ_{β}^{2 \frac{−i}{β−1}} + \frac{1}{4} ∑_{j=1}^{i−1} γ_{β}^{2 \frac{−j}{β−1}} ) λ_{i}(L)^{2}

≤ γ_{β}^{2 \frac{m−1}{β−1}} \frac{i + 3}{4} λ_{i}(L)^{2} .

This proves the second inequalities of Theorem 3. The first inequalities in Theorem 3 follows from 8 and λ_{1}(L_{i}) ≤ λ_{i}(L). □

Proof of Theorem 4. By definition of λ_{i} = λ_{i}(L) we have

λ_{i}^{2} ≤ max{∥b_{j}∥^{2} for j = 1, …, i} .

It follows from ∥b_{j}∥^{2} ≤ ∥b̂_{j}∥^{2} + ∑_{k=1}^{j−1} μ_{j,k}^{2}∥b̂_{k}∥^{2} that

λ_{i}^{2} ≤ \frac{i + 3}{4} max\{∥b̂_{j}∥^{2} for j = 1, …, i\} . (9)

Proposition 5 applied to the β–BKZ basis π_{j}(b_{j}), …, π_{j}(b_{i}) yields the inequalities

∥b̂_{j}∥ ≤ γβ^{\frac{i−j}{β−1}} max\{∥b̂_{i−β+2}∥, …, ∥b̂_{i}∥\} for 1 ≤ j ≤ i − β + 1 (10)

For i − β + 2 ≤ j ≤ i we have that

∥b̂_{j}∥ ≤ ∥π_{j}(b_{i})∥ ≤ ∥b_{i}∥ .

From this and 10 we see that

∥b̂_{j}∥ ≤ γβ^{\frac{i−j}{β−1}} ∥b_{i}∥  for  1 ≤ j ≤ i .

These inequalities and 9 prove Theorem 4:

λ_{i}^{2} ≤ \frac{i + 3}{4} γ_{β}^{2 \frac{i−1}{β−1}} ∥b_{i}∥^{2}  for i = 1, …, m .  □

4 Approximate nearest lattice points

Babai (1986) shows how Lovász lattice reduction can be used to find a point of a given lattice L, nearest within a factor 2^{m/2} to a given point in span(L). Babai poses the question whether the factor 2^{m/2} can be improved using block Korkin–Zolotarev bases. We answer this question in the affirmative.

We let α_{β} denote the maximum of ∥b_{1}∥^{2}/∥b̂_{β}∥^{2} over all Korkin–Zolotarev bases b_{1}, …, b_{β}. The inequality α_{β} ≤ β^{1+ln β} has been shown in Schnorr (1987).

Theorem 7 Let b_{1}, …, b_{m} ∈ ZZ^{n} be a β–BKZ basis of lattice L and x = ∑_{i=1}^{m} x_{i}b_{i} an arbitrary point in span(b_{1}, …, b_{m}). Then the lattice point v = ∑_{j=1}^{m} v_{j}b_{j}, where v_{j} = ⌈x_{j} − ∑_{i=j+1}^{m} v_{i}μ_{i,j}⌋, satisfies

∥x − v∥^{2} ≤ C_{m,β} min_{u∈L} ∥x − u∥^{2} , where C_{m,β} = m γ_{β}^{2 \frac{m−1}{β−1}} α_{β−1} .

Proof The definition of v implies that

∥x − v∥^{2} ≤ (∥b̂_{1}∥^{2} + ⋯ + ∥b̂_{m}∥^{2})/4 .

From Proposition 5 we have the inequality

∥b̂_{i}∥^{2} ≤ γ_{β}^{2 \frac{m−i}{β−1}} max(∥b̂_{m−β+2}∥^{2}, …, ∥b̂_{m}∥^{2}) for 1 ≤ i ≤ m − β + 1 .

This yields

∥x − v∥^{2} ≤ \frac{1}{4} ∑_{j=1}^{m} γ_{β}^{2 \frac{j−1}{β−1}} max(∥b̂_{m−β+2}∥^{2}, …, ∥b̂_{m}∥^{2})

≤ \frac{1}{4} ∑_{j=1}^{m} γ_{β}^{2 \frac{j−1}{β−1}} α_{β−1} ∥b̂_{m}∥^{2}

≤ \frac{m}{4} γ_{β}^{2 \frac{m−1}{β−1}} α_{β−1} ∥b̂_{m}∥^{2} .  (11)

Let u ∈ L be the lattice point that is nearest to x. Following Babai we consider two cases.

CASE a: u − v ∈ L(b_{1}, …, b_{m−1}). Then u − v is a nearest lattice point to x′ − v in L(b_{1}, …, b_{m−1}) where x′ ∈ span(b_{1}, …, b_{m−1}) is the orthogonal projection of x. Consequently we have by induction on m

∥x − v∥^{2} = ∥x − x′∥^{2} + ∥x′ − v∥^{2}
≤ (1 + C_{m−1,β}) ∥x − u∥^{2}
≤ C_{m,β} ∥x − u∥^{2}

CASE b: u − v ∉ L(b_{1}, …, b_{m−1}). In this case we have

∥x − u∥^{2} ≥ ∥b̂_{m}∥^{2}/4.

Hence we have from 11 that

∥x − v∥^{2} ≤ \frac{m}{4} γ_{β}^{2 \frac{m−1}{β−1}} α_{β−1} 4 ∥x − u∥^{2}
≤ C_{m,β} ∥x − u∥^{2} .  □

We finally reduce with a different construction for v the constant C_{m,β}

of Theorem 7 to m γ_{β}^{2 \frac{m−1}{β−1}} . The improved constant m γ_{β}^{2 \frac{m−1}{β−1}} is polynomial in β if β is a fixed fraction of m.

Theorem 8 Let b_{1}, …, b_{m} ∈ ZZ^{n} be a β–BKZ basis and x = ∑_{i=1}^{m} x_{i}b_{i} . Suppose that ∥b̂_{k}∥ = max(∥b̂_{m−β+1}∥, …, ∥b̂_{m}∥), m − k + 1 ≤ k ≤ m . Let v = ∑_{i=1}^{m} v_{i}b_{i} be a lattice point such that ∑_{j=k}^{m} |x_{j} −∑_{i=j}^{m} v_{i}μ_{i,j}|^{2} ∥b̂_{i}∥^{2} is minimal for all v_{k}, …, v_{m} ∈ ZZ and |x_{j} − ∑_{i=j}^{m} v_{i}μ_{i,j}| ≤ \frac{1}{2} for j = k − 1, …, 1 . Then we have ∥x − v∥^{2} ≤

m γ_{β}^{2 \frac{m−1}{β−1}} min_{u∈L} ∥x − u∥^{2} .

Proof Let u ∈ L be the lattice point that is nearest to x. CASE a: u − v ∈ L(b_{1}, …, b_{m−1}). Then u − v is a nearest lattice point to x′ − v in L(b_{1}, …, b_{m−1}) where x′ ∈ span(b_{1}, …, b_{m−1}) is the orthogonal projection of x, x′ = x − π_{m−1}(x). Induction on m yields

∥x − v∥^{2} = ∥x − x′∥^{2} + ∥x′ − v∥^{2}
≤ (1 + (m − 1)γ_{β}^{2 \frac{m−2}{β−1}} ) ∥x − u∥^{2}
≤ m γ_{β}^{2 \frac{m−1}{β−1}} ∥x − u∥^{2} .

CASE b: u − v ∉ L(b_{1}, …, b_{m−1}). It follows from the choice of v and k that

∥x − u∥^{2} ≥ \frac{1}{4} λ_{1}(L_{k})^{2} ≥ \frac{1}{4} max( ∥b̂_{m−β+2}∥^{2}, …, ∥b̂_{m}∥^{2}) .

As in the proof of Theorem 7 we have

∥x − v∥^{2} ≤ ( ∥b̂_{1}∥^{2} + ⋯ + ∥b̂_{m}∥^{2} ) / 4
≤ \frac{1}{4} ∑_{j=1}^{m} γ_{β}^{2 \frac{j−1}{β−1}} max(∥b̂_{m−β+2}∥^{2}, …, ∥b̂_{m}∥^{2}) .

Consequently

∥x − v∥^{2} ≤ ∑_{j=1}^{m} γ_{β}^{2 \frac{j−1}{β−1}} ∥x − u∥^{2}

≤ m γ_{β}^{2 \frac{m−1}{β−1}} ∥x − u∥^{2} .  □

Computational bounds. Computing a lattice vector v = ∑_{i=1}^{m} v_{i}b_{i} as in Theorem 7 can be done using the Nearest Vector Algorithm of Kannan (1987). Given a β–BKZ basis b_{1}, …, b_{m} this algorithm enumerates β^{O(β)} many lattice vectors close to x and finds integers v_{m−β+1}, …, v_{m} that minimize ∑_{j=m−β+1}^{m} |x_{j} − ∑_{i=j}^{m} v_{i}μ_{i,j}|^{2} ∥b̂_{i}∥^{2}. A β–BKZ basis can be computed from an arbitrary basis b_{1}, …, b_{m} ∈ ZZ^{n} by the algorithm of Schnorr (1987). This algorithm finds an “approximate” β–BKZ basis using O(nm(β^{O(β)} + m^{2}) log B) arithmetic operations on O(m log B) bit integers where B is the maximal length of the given basis vectors. This algorithm is theoretical.

For practical algorithms performing block Korkin–Zolotarev reduction see Schnorr, Euchner (1991). The Schnorr, Euchner algorithm transforms an arbitrary lattice basis into a δ–approximate β–BKZ basis, δ < 1, which by definition satisfies for i = 1, …, m

δ ∥b̂_{i}∥^{2} ≤ λ_{1}(π_{i}L(b_{1}, …, b_{min(i+β−1,m)}))^{2} .

The Schnorr, Euchner algorithm is not proven to be polynomial time, but in practice its time bound appears to be O(nm(β^{O(β)} + m^{2}) log B). No polynomial time algorithm is known for δ = 1, not even for β = 2.

5 Critical β–BKZ bases for block size 2 and 3

We call a β–BKZ basis b_{1}, …, b_{m} of the lattice L critical for β, m if the value ∥b_{1}∥ / λ_{1}(L) is maximal for all β–BKZ bases of rank m. Bachem and Kannan (1984) present critical 2–BKZ bases b_{1}, …, b_{m}. We establish critical 3–BKZ bases b_{1}, …, b_{m}. We evaluate the constant α_{3} = max ∥b_{1}∥^{2} / ∥b̂_{3}∥^{2}, where the maximum is taken over all Korkin–Zolotarev bases b_{1}, b_{2}, b_{3}. We prove α_{3} = \frac{3}{2} .

We describe a slight variant of the critical 2–BKZ bases of Bachem, Kannan (1984). Let ρ = \sqrt{\frac{3}{4}}. We define the basis matrix A_{m} = [b_{1}, …, b_{m}] ∈ M_{m,m}(IR) by

A_{m} = [ \begin{matrix}1 & \frac{1}{2} \\ & ρ & ρ/2 & & & O \\ & & ρ^{2} & ρ^{2}/2 \\ & & & ... & ... \\ & & & & ... & ... \\ & & O & & & ρ^{m−2} & ρ^{m−2}/2 \\ & & & & & & ρ^{m−1} \end{matrix} ] (12)

The matrices A_{m} satisfy the recursion

A_{m} = [ 1 \frac{1}{2} O ; . . . . . . . . . . . ; ⋮ ; O ⋮ ρ · A_{m−1} ; ⋮ ] .

Theorem 9 (Bachem, Kannan 1984) The column vectors of the matrix A_{m} form a critical 2–BKZ basis.

Proof. It can easily be seen that the vector b_{m} is a shortest vector in L(b_{1}, …, b_{m}) − L(b_{1}, …, b_{m−1}). We have

∥b_{m}∥^{2} = ρ^{2m−4}(ρ^{2} + \frac{1}{4}) = (\frac{3}{4})^{m−2} .

It follows that b_{m} is the shortest vector in the lattice L(b_{1}, …, b_{m}). Therefore λ_{1} = λ_{1}(L(b_{1}, …, b_{m})) satisfies

∥b_{1}∥^{2}λ_{1}^{−2} = (\frac{4}{3})^{m−2} .

Now let b_{1}, …, b_{m} be an arbitrary 2–BKZ basis. Let v = ∑_{i=1}^{m} t_{i}b_{i} be a shortest non–zero lattice vector and μ = max{i | t_{i} ≠ 0}. Then λ_{1} = λ_{1}(L(b_{1}, …, b_{m})) satisfies

λ_{1}^{2} ≥^{1.} ∥π_{μ−1}(v)∥^{2} ≥^{2.} ∥b̂_{μ−1}∥^{2} ≥^{3.} (\frac{3}{4})^{μ−2} ∥b_{1}∥^{2} .

1. holds since π_{μ−1}(v) ≠ 0, 2. holds since π_{μ−1}(b_{μ−1}) is minimal in the lattice π_{μ−1}L(b_{μ−1}, b_{μ}) which contains π_{μ−1}(υ), 3. follows from the inequality 6. We now see that

∥b_{1}∥^{2}λ_{1}^{−2} ≤ (\frac{4}{3})^{μ−2} ≤ (\frac{4}{3})^{m−2} .

This shows that the columns of the matrix 12 form a critical basis. □

A sequence of 3–BKZ bases b_{1}, …, b_{m}. We define the basis matrices B_{m} = [b_{1}, …, b_{m}] as follows.

B_{4} = [ 1 ; \frac{\sqrt{3}}{2}  O ; O  \sqrt{\frac{2}{3}} ; \frac{1}{\sqrt{2}} ] [ \begin{matrix}1 & −\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ & 1 & \frac{1}{3} & \frac{1}{3} \\ O & & 1 & −\frac{1}{2} \\ & & & 1 \end{matrix} ]

= [ 1 −\frac{1}{2}  \frac{1}{2}  \frac{1}{2} ; \frac{\sqrt{3}}{2} \frac{1}{2\sqrt{3}}  \frac{1}{2\sqrt{3}} ; O \sqrt{\frac{2}{3}} −\frac{1}{2} \sqrt{\frac{2}{3}} ; \frac{1}{\sqrt{2}} ]  (13)

The lattice L^{(4)} = L(b_{1}, …, b_{4}) yields a lattice packing of maximal density, i.e. λ_{1}(L^{(4)})^{2} det L^{(4)− \frac{2}{4}} = γ_{4} = \sqrt{2}. Let B_{2}, B_{3} denote the 2 × 2, 3 × 3– matrix in the upper left corner of B_{4}. For arbitrary m = 1, 2, … we define the m × m matrix

B_{m} = diag(d_{1}, …, d_{m}) [μ_{i,j}]_{1≤i,j≤m}^{⊤}

where diag(d_{1}, …, d_{m}) is the m×m diagonal matrix with positive diagonal entries d_{1}, …, d_{m} and M_{m} = [μ_{i,j}]_{1≤i,j≤m}^{⊤} is an upper diagonal matrix with ones on the diagonal. It follows that the μ_{i,j} are the Gram–Schmidt coefficients of the basis b_{1}, …, b_{m} consisting of the column vectors of B_{m}. We define for i = 1, 2, …

d_{2i−1} = \sqrt{\frac{2}{3}}^{i−1} , d_{2i} = \frac{\sqrt{3}}{2} , d_{2i−1}

−μ_{2i,2i−1} = μ_{2i+1,2i−1} = μ_{2i+2,2i−1} = \frac{1}{2} , μ_{2i+k,2i−1} = 0 for k ≥ 3

μ_{2i+1,2i} = μ_{2i+2,2i} = \frac{1}{3} , μ_{2i+k,2i} = 0 for k ≥ 3 .

The matrices M_{m}, B_{m} are upper triangular matrices with four non–zero diagonals. They satisfy for m > 4 the following recursion

\begin{aligned}M_{m} & = & [ 1 −\frac{1}{2} \frac{1}{2} \frac{1}{2} 0 …; 1 \frac{1}{3} \frac{1}{3} 0 …; . . . . . . . . . . . . ; ⋮ ; O ⋮ M_{m−2} ; ⋮ ] \\ B_{m} & = & [ 1 −\frac{1}{2}  \frac{1}{2}  \frac{1}{2} 0 …; \frac{\sqrt{3}}{2} \frac{1}{2 \sqrt{3}} \frac{1}{2 \sqrt{3}} 0 …; . . . . . . . . . . . . . . . . . . . . ; ⋮ ; ⋮ ; ⋮ ; O ⋮  \sqrt{\frac{2}{3}} B_{m−2} ; ⋮ ; ⋮ ] \end{aligned}

Let b_{1}, …, b_{m} be the column vectors of B_{m}, B_{m} = [b_{1}, …, b_{m}] and let L^{(m)} = L(b_{1}, …, b_{m}) be the lattice generated by b_{1}, …, b_{m}.

Theorem 10 The column vectors b_{1}, …, b_{m} of B_{m} form a 3–BKZ basis.

Proof. The vectors b_{1}, …, b_{4} form a Korkin–Zolotarev basis since the vector b̂_{i} is minimal in π_{i}(L^{(4)} for i = 1, …, 4. The lattice L^{(4)} yields the lattice sphere packing E_{4}, the lattice packing of maximal density for dimension 4, see Conway, Sloane (1988). We see from the recursive structure of B_{m} = [b_{i,j}]_{1≤i,j≤m} that

[b_{i,j}]_{2k+1≤i,j≤2k+5} = (\frac{2}{3})^{k/2} B_{4} for k = 0, …, ⌊(m − 5)/2⌋ .

This implies that the basis π_{i}(b_{i}), π_{i}(b_{i+1}), π_{i}(b_{i+2}) is Korkin–Zolotarev for i = 1, …, m − 2. □

We let L^{(k)} denote the lattice that is generated by the column vectors b_{1}, …, b_{k} of the matrix B_{k}.

Lemma 11 The basis b_{1}, …, b_{2k+1} consisting of the column vectors of B_{2k+1}

satisfies ∥b_{1}∥ / λ_{1}(L^{2k+1}) = \sqrt{\frac{3}{2}}^{k−1} for k = 1, 2, …

Proof. We have for k = 1, 2, 3, … that

∥b_{2k+1}∥ = \sqrt{\frac{2}{3}}^{k−1} = ∥b̂_{2k−1}∥ .

Moreover b_{2k+1} is the shortest vector in L(b_{1}, …, b_{2k+1}) − L(b_{1}, …, b_{2k−1}). This is because ∥b_{2k+1}∥ = ∥b̂_{2k−1}∥ and b_{1}, …, b_{2k+1} is a 3–BKZ basis.

Applying the above property of b_{2k+1} inductively we see that the short-

est non–zero vector in L^{(2k+1)} has length \sqrt{\frac{2}{3}} ^{k−1} which proves the claim. □

In order to show that the basis b_{1}, …, b_{2k+1} of lattice L^{(2k+1)} is a critical 3–BKZ basis we need an upper bound on ∥b_{1}∥ / λ_{1}(L) which holds for all 3–BKZ bases of any lattice L. Let α_{β} be the lattice constant

α_{β} = max ∥b_{1}∥^{2} / ∥b̂_{β}∥^{2}

where the maximum is taken over all Korkin–Zolotarev bases b_{1}, …, b_{β}. The following theorem improves the upper bound ∥b_{1}∥^{2} λ_{1}(L)^{−2} ≤ α_{β}^{k} from Schnorr (1987).

Theorem 12 Every β–BKZ basis b_{1}, …, b_{m} of lattice L for which k = (m − 1)/(β − 1) is integer satisfies ∥b_{1}∥^{2} λ_{1}(L)^{−2} ≤ α_{β}^{k−1}.

Proof. Let v = ∑_{i=1}^{m} t_{i}b_{i} be a shortest non–zero vector in L. We can assume that v ∉ L(b_{1}, …, b_{m−β+1}) since otherwise we can reduce k and the induction hypothesis for k − 1 yields ∥b_{1}∥^{2} λ_{1}(L)^{−2} ≤ α_{β}^{k−2}. From v ∉ L(b_{1}, …, b_{m−β+1}) we see that π_{m−β+1}(v) ≠ 0. Since π_{m−β+1}(b_{m−β+1}), …, π_{m−β+1}(b_{m}) is a Korkin–Zolotarev basis we have

∥b̂_{m−β+1}∥ ≤ ∥π_{m−β+1}(v)∥ ≤ λ_{1}(L) .

Moreover ∥b̂_{1+(β−1)(j−1)}∥^{2} ≤ α_{β} ∥b̂_{1+(β−1)j}∥^{2} holds for j = 1, …, k − 1 since the basis b_{1}, …, b_{m} is β–BKZ. Therefore

∥b_{1}∥^{2} ≤ α_{β}^{k−1} ∥b̂_{m−β+1}∥^{2} ≤ α_{β}^{k−1} λ_{1}(L)^{2} . □

Theorem 13 α_{3} = \frac{3}{2} , i.e. α_{3}^{−1/2} is the height of the tetrahedron with side length 1.

Proof. Let b_{1}, b_{2}, b_{3} be a Korkin–Zolotarev basis with ∥b_{1}∥ = 1 and minimal ∥b̂_{3}∥, i.e. α_{3} = ∥b_{1}∥^{2} ∥b̂_{3}∥^{−2} = ∥b̂_{3}∥^{−2}. Consider the projection μ_{3,1}b_{1} + μ_{3,2}b̂_{2} of b_{3} in span (b_{1}, b_{2}). We claim that μ_{3,1}b_{1} + μ_{3,2}b̂_{2} must be a “deep hole” for the lattice L(b_{1}, b_{2}), i.e. a point that has maximal distance from the lattice points. If μ_{3,1}b_{1} + μ_{3,2}b̂_{2} is not a deep hole for the lattice L(b_{1}, b_{2}) we can change μ_{3,1}, μ_{3,2} such that the minimal distance of μ_{3,1}b_{1} + μ_{3,2}b̂_{2} from L(b_{1}, b_{2}) increases. This permits to decrease ∥b̂_{3}∥ without violating the properties of Korkin–Zolotarev bases.

There are at most two deep holes in the ground mesh of the basis b_{1}, b_{2}, namely the points that have equal distance to 0, b_{1}, b_{2} (b_{1}, b_{2}, b_{1} + b_{2}, respectively).

[figure: ∘; ∘; 0; b_{1}; b_{2}; b_{1} + b_{2}]

deep holes ∘ in the ground mesh

W.l.o.g. we can assume that μ_{3,1}b_{1} + μ_{3,2}b̂_{2} has equal distance from 0, b_{1} and b_{2}. It follows from ∥b_{2}∥^{2} = μ_{2,1}^{2} + ∥b̂_{2}∥^{2} ≥ ∥b_{1}∥^{2} = 1, |μ_{2,1}| ≤ \frac{1}{2} that

∥b̂_{2}∥ ≥ \frac{\sqrt{3}}{2} . (14)

Let ∥b̂_{2}∥ = \frac{\sqrt{3}}{2} + ε with ε ≥ 0. We have

\begin{aligned}∥μ_{3,2}b̂_{2}∥ & = & \frac{\sqrt{3}}{6} if ε = 0 \\ ∥μ_{3,2}b̂_{2}∥ & ≤ & \frac{\sqrt{3}}{6} + ε for ε ≥ 0 . \end{aligned}  (15)

This is because ε = 0 implies that ∥b_{1}∥ = ∥b_{2}∥ = ∥b_{1} − b_{2}∥ = 1 and thus μ_{3,1}b_{1} + μ_{3,2}b̂_{2} = \frac{b_{1}+b_{2}}{3} . Moreover the b̂_{2}–coordinate of the deep hole μ_{3,1}b_{1} + μ_{3,2}b̂_{2} does not increase faster in ε than ∥b̂_{2}∥. We see from ∥π_{2}(b_{3})∥ ≥ ∥b̂_{2}∥ that ∥b̂_{3}∥^{2} + μ_{3,2}^{2}∥b̂_{2}∥^{2} ≥ ∥b̂_{2}∥^{2}, and thus

∥b̂_{3}∥^{2} ≥ ∥b̂_{2}∥^{2} − μ_{3,2}∥b̂_{2}∥^{2}
{15,16 \atop ≥} (\frac{\sqrt{3}}{2} + ε)^{2} − (\frac{\sqrt{3}}{6} + ε)^{2}
≥ \frac{3}{4} − \frac{1}{12} = \frac{2}{3}

holds for the basis matrix B_{3} = [b_{1}, b_{2}, b_{3}]. This proves that α_{3} = \frac{3}{2}. □

Theorem 14 The lattice basis b_{1}, …, b_{2k+1} defined by the basis matrix B_{2k+1} is a critical 3–BKZ basis.

Proof. Lemma 11 shows that ∥b_{1}∥ / λ_{1}(L^{(2k+1)}) = \sqrt{\frac{3}{2}}^{k−1}. On the other hand every 3–BKZ basis b′_{1}, …, b′_{2k+1} of lattice L satisfies ∥b′_{1}∥ / λ_{1}(L) ≤ \sqrt{α_{3}}^{k−1} by Theorem 12, where α_{3} = \frac{3}{2} by Theorem 13. This shows that ∥b_{1}∥ / λ_{1}(L^{(2k+1)}) is maximal for 3–BKZ bases of rank 2k + 1. □

Acknowledgement. The author wishes to thank Brigitte Vallée for her participation in starting this work.

References

[1] L. Babai: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6 (1986), 1–13.

[2] A. Bachem and R. Kannan: Lattices and the basis reduction algorithm. TR, Carnegie Mellon University (1984), 22 pages.

[3] J.W.S. Cassels: An introduction to the geometry of numbers. Springer-Verlag, Berlin, New York (1971).

[4] J.H. Conway and H.J.A. Sloane: Sphere Packings, Lattices and Groups. Springer–Verlag, New York Berlin (1988).

[5] M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.P. Schnorr and J. Stern: An improved low–density subset sum algorithm. To appear in computational complexity.

[6] M. Grtschel, L. Lovász, and A. Schrijver: Geometric algorithms and combinatorial optimization. Springer–Verlag, Berlin, 198.

[7] C. Hermite: Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres, Deuxième lettre du 6 août 1845. J. Reine Angew. Math. 40 (1850), 279–290.

[8] R. Kannan: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12 (1987), 415–440.

[9] A. Korkine, and G. Zolotareff: Sur les formes quadratiques. Math. Ann. 6 (1873), 366–389.

[10] J.C. Lagarias, H.W. Lenstra, Jr., and C.P. Schnorr: Korkin– Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10 (1990), 333–348.

[11] J.L. Lagrange: Recherches d’arithmétique, Nouv. Mém. Acad. Berlin (1773), 265–312. Œvres, vol. VIII, 693–753.

[12] A.K. Lenstra, H.W. Lenstra, Jr., and L. Lovász: Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515– 534.

[13] H.W. Lenstra, Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8 (1983), 538–548.

[14] L. Lovász: An algorithmic theory of numbers, graphs and convexity. CBMS–NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986.

[15] K. Mahler: A theorem on inhomogeneous diophantine inequalities. Nederl. Akad. Wetensch., Proc. 41 (1938), 634–637.

[16] C.P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53 (1987), 201–224.

[17] C.P. Schnorr and M. Euchner: Lattice basis reduction: improved algorithms and solving subset sum problems. Proceedings of Fundamentals of Computation Theory, FCT’91, Ed. L. Budach, Springer LNCS 529, (1991), pp. 68–85.