§1. Gram-Schmidt Orthogonalization  Lecture IX  Page 1

Lecture IX Lattices and Polynomial Factorization

The problem of factoring polynomials is related to root finding since factoring a polynomial in the algebraic closure of its coefficient domain is equivalent to finding roots in that domain. Conversely, we show in this lecture that if we find roots with sufficient accuracy then we can also factor. It was a major open problem to factor integer polynomials efficiently until the breakthrough result from A. K. Lenstra, H. W. Lenstra and Lovász [10]. Kaltofen has shown how to reduce the multivariate polynomial factorization to the univariate case. There are also algorithms to factor polynomials with coefficients that are algebraic numbers. See [5,6,7,9,8,3]. For a history of the problem up to 1986, we refer to Kaltofen’s surveys [1,4].

The fast factorization algorithm depends on an efficient algorithm to “reduce” integer lattices. In Lecture X we introduced lattices and gave an efficient algorithm to reduce lattices in 2 dimensions. In this lecture, we will give an algorithm that is applicable in all dimensions. This is essentially the algorithm in [10], popularly known as the “LLL-algorithm” (or, L-cubed algorithm). The complexity of the LLL-algorithm has been improved by Schönhage [14] and Schnorr [13].

In this lecture, the 2-norm ∥a∥_{2} of a vector a is simply written ∥a∥.

§1. Gram-Schmidt Orthogonalization

Recall the concept of lattices in §X.1. Let A = [a_{1},…, a_{m}] ∈ ^{n×m} be a lattice basis. Note that 1 ≤ m ≤ n. The matrix A is orthogonal if for all 1 ≤ i < j ≤ m, ⟨a_{i}, a_{j}⟩ = 0. The following is a well-known procedure to convert A into an orthogonal basis A^{∗} = [a_{1}^{∗},…, a_{m}^{∗}]:

Gram-Schmidt Procedure Input: A = [a_{1},…, a_{m}], Output: A^{∗} = [a_{1}^{∗},…, a_{m}^{∗}].

1. a_{1}^{∗} ← a_{1}.

2. for i = 2,…, m do

μ_{ij} ← \frac{⟨a_{i}, a_{j}^{∗}⟩}{⟨a_{j}^{∗}, a_{j}^{∗}⟩},  ( for j = 1,…, i − 1)  (1)

a_{i}^{∗} ← a_{i} − ∑_{j=1}^{i−1} μ_{ij} · a_{j}^{∗}.  (2)

This is a very natural algorithm: the student should “see” this algorithm for m = 2, 3. Let us verify that A^{∗} is orthogonal by induction. As basis of induction,

⟨a_{2}^{∗}, a_{1}^{∗}⟩ = ⟨a_{2} − μ_{21}a_{1}^{∗}, a_{1}^{∗}⟩ = ⟨a_{2}, a_{1}^{∗}⟩ − μ_{21}⟨a_{1}^{∗}, a_{1}^{∗}⟩ = 0.

Proceeding inductively, if i > j then

⟨a_{i}^{∗}, a_{j}^{∗}⟩ = ⟨a_{i} − ∑_{k=1}^{i−1} μ_{ik}a_{k}^{∗}, a_{j}^{∗}⟩ = ⟨a_{i}, a_{j}^{∗}⟩ − μ_{ij}⟨a_{j}^{∗}, a_{j}^{∗}⟩ = 0,

as desired. We shall call A^{∗} the Gram-Schmidt version of A. We say that two bases are Gram-Schmidt equivalent if they have a common Gram-Schmidt form.

The algorithm also gives us a constructive proof of this result: if L is any linear subspace of ^{n} and u ∈ ^{n} then u can be decomposed as u = u_{L} + u_{N} where u_{L} ∈ L and u_{N} is normal to L (i.e., ⟨u_{N}, a⟩ = 0 for all a ∈ L). To see that this decomposition is unique, suppose u = u′_{L} + u′_{N} is another decomposition. It is sufficient to prove u′_{L} = u_{L}. But u_{N} −u′_{N} = u′_{L} −u_{L} ∈ L implies u′_{L} − u_{L} is normal to L. The only element of L that is normal to L is the zero vector. This proves u′_{L} − u_{L} = 0, as desired.

Exercise 1.1: In Lecture X.1, we describe three elementary unimodular transformations. Show that only the last one (permuting two columns) does not preserve Gram-Schmidt equivalence.

Let us rewrite (2) as

a_{i} = a_{i}^{∗} + ∑_{j=1}^{i−1} μ_{ij}a_{j}^{∗}.  (3)

Then

⟨a_{i}, a_{i}^{∗}⟩ = ⟨a_{i}^{∗} + ∑_{j=1}^{i−1} μ_{ij}a_{j}^{∗}, a_{i}^{∗}⟩
= ⟨a_{i}^{∗}, a_{i}^{∗}⟩.

Hence (1) may be extended to

μ_{ii}:= \frac{⟨a_{i}, a_{i}^{∗}⟩}{⟨a_{i}^{∗}, a_{i}^{∗}⟩} = 1,

whence (3) simplifies to

a_{i} = ∑_{j=1}^{i} μ_{ij}a_{j}^{∗}.  (4)

In matrix form,

A = A^{∗}M^{T}  (5)

where M^{T} is the transpose of a lower diagonal matrix

M = ( μ_{11} 0  0 ⋯ 0 ; μ_{21} μ_{22} 0  0 ; ⋮ ; μ_{m1} μ_{m2} μ_{m3} ⋯ μ_{mm} ) .  (6)

Since μ_{ii} = 1, it follows that det M = 1 and so the Gram-Schmidt version of A is a unimodular transformation of A. Note M need not be an integer matrix.

Lemma 1

(i) det(A^{T} A) = ∏_{i=1}^{m} ∥a_{i}^{∗}∥^{2}. (ii) ∥a_{i}∥ ≥ ∥a_{i}^{∗}∥ for i = 1,…, m with equality iff a_{i} is orthogonal to all a_{j}^{∗} (j = 1,…, i − 1).

Proof. (i) \begin{matrix}det(A^{T} A) & = & det(MA^{∗T} · A^{∗}M^{T}) \\ & = & det(M) det(A^{∗T} A^{∗}) det(M^{T}) \\ & = & det(A^{∗T} A) \\ & = & ∏_{i=1}^{m} ∥a_{i}^{∗}∥^{2}. \end{matrix}

(ii) From (3), we get

∥a_{i}∥^{2} = ∥a_{i}^{∗}∥^{2} + ∑_{j=1}^{i−1} μ_{ij}^{2}∥a_{j}^{∗}∥^{2}
≥ ∥a_{i}^{∗}∥^{2},

with equality iff μ_{ij} = 0 for all j. Q.E.D.

From this lemma, we deduce immediately

\sqrt{det A^{T} A} ≤ ∏_{i=1}^{m} ∥a_{i}∥.

In particular, when m = n, we get Hadamard’s determinantal bound

| det A| ≤ ∏_{i=1}^{n} ∥a_{i}∥.

In Lecture VI.7, for the proof of the Goldstein-Graham bound, we needed the complex version of Hadamard’s bound. The preceding proof requires two simple modifications:

1. Instead of the transpose A^{T}, we now use the Hermitian transpose A^{H}, defined as A^{H} := \overline{A}^{T}, where \overline{A} is obtained by taking the complex conjugate of each entry of A.

2. The 2–norm of a complex vector u = (v_{1},…, v_{n}) is defined as ∥v∥ = (∑_{i=1}^{n} |v_{i}|^{2})^{\frac{1}{2}} =

(∑_{i=1}^{n} v_{i}\overline{v}_{i})^{\frac{1}{2}} .

It is easy to verify that the preceding argument goes through. Thus we have the following generalization of Hadamard’s bound:

Theorem 2 Let A = [a_{1},…, a_{m}] ∈ ^{n×m}, 1 ≤ m ≤ n. Then

\sqrt{det(A^{H}A)} ≤ ∏_{i=1}^{m} ∥a_{i}∥.

Equality in this bound is achieved iff A is orthogonal.

§2. Convex Body Theoreom  Lecture IX  Page 4

We revert to the setting in which A is a real n × m matrix. Define

δ(A) := \frac{∥a_{1}∥ · ∥a_{2}∥ ⋯ ∥a_{m}∥}{\sqrt{det(A^{T} A)}}

to be the (orthogonality) defect of A. Note that δ(A) ≥ 1. Intuitively, it measures the amount of A’s distortion from its Gram-Schmidt version.

This suggests the following minimum defect basis problem: given a basis A, find another basis B with Λ(A) = Λ(B) such that δ(B) is minimized. Lovász [2, p. 140] has shown this problem to be NP -complete. For many applications, it is sufficient to find a B such that δ(B) is at most some constant K that depends only on m and n. Call this the K-bounded defect basis problem. In case m = n, Hermite has shown that there exists such a basis B with

δ(B) ≤ K_{n}

where K_{n} depends only on n. The current bound for K_{n} is O(n^{1/4}(0.97n)^{n}). We will show a polynomial-time algorithm in case K = 2^{\binom{m}{2}}.

§2. Minkowski’s Convex Body Theorem

This section is not needed in subsequent developments but serve to illustrate some basic properties of lattices. We assume full-dimensional lattices in this section.

Given any lattice basis A = [a_{1},…, a_{n}] ∈ ^{n×n} we call the set

F(A) :={α_{1}a_{1} + … + α_{n}a_{n} : 0 ≤ α_{i} < 1, i = 1,…, n}

the fundamental parallelopiped of A (or of Λ). The (n-dimensional) volume of F(A) is given by

Vol(F(A)) = | det(A)|.

It is not hard to see that ^{n} is partitioned by the family of sets

u + F(A), u ∈ Λ(A).

Any bounded convex set B ⊆ ^{n} with volume Vol(B) > 0 is called a body. The body is O-symmetric if for all x ∈ B, we have also −x ∈ B.

Theorem 3 (Blichfeldt 1914) Let m ≥ 1 be an integer, Λ a lattice, and B any body with volume

Vol(B) > m det Λ.

Then there exists (m + 1) distinct points p_{1},…, p_{m+1} ∈ B such that the differences

p_{i} − p_{j}

all lie in Λ for all i, j.

Proof. Let A = [a_{1},…, a_{n}] be a basis for Λ and F = F(A) be the fundamental parallelopiped. For u ∈ Λ, define

F_{u} = {x ∈ F : x + u ∈ B}.

Hence (u + F) ∩ B = u + F_{u}. It follows that

∑_{u∈Λ} Vol(F_{u}) = Vol(B) > m · Vol(F).

We claim that there is a point p_{0} ∈ F that belongs to m + 1 distinct set F_{u_{1}},…, F_{u_{m+1}}. If not, we may partition F into

F = F^{(0)} ∪ F^{(1)} ∪ ⋯ ∪ F^{(m)}

where F^{(i)} consists of all those points X ∈ F that belongs to exactly i sets of the form F_{u}, (u ∈ Λ). Then

∑_{u} Vol(F_{u}) = ∑_{i=0}^{m} iVol(F^{(i)}) ≤ mVol(F)

which is a contradiction. Hence p_{0} exists. Since p_{0} belongs to F_{u_{i}} (i = 1,…, m + 1), we see that each of the points

p_{i} := p_{0} + u_{i}

belong to B. It is clear that the points p_{1},…, p_{m+1} fulfill the theorem. Q.E.D.

Note that in the proof we use the fact that Vol(F^{(i)}) is well defined. We now deduce Minkowski’s Convex Body theorem (as generalized by van der Corput).

Theorem 4 (Minkowski) Let B ⊆ ^{n} be an O-symmetric body. For any integer m ≥ 1 and lattice Λ ⊆ ^{n}, if

Vol(B) > m2^{n} det(Λ)

then B ∩ Λ contains at least m pairs of points

±q_{1},…, ±q_{m}

which are distinct from each other and from the origin O.

Proof. Let

\frac{1}{2}B = \{p ∈ ^{n} : 2p ∈ B\}.

Then Vol(\frac{1}{2}B) = 2^{−n}Vol(B) > m · det(Λ). By Blichfeldt’s theorem, there are m + 1 distinct points \frac{p_{1}}{2} ,…, \frac{p_{m}}{2} , \frac{p_{m+1}}{2} ∈ \frac{1}{2}B such that \frac{1}{2}p_{i} − \frac{1}{2}p_{j} ∈ Λ for all i, j. We may assume

p_{1} ≻ p_{2} ≻ … ≻ p_{m+1}

where ≻ denotes the lexicographical ordering: p_{i} ≻ p_{j} iff p_{i} ≠ p_{j} and the first non-zero component of p_{i} − p_{j} is positive. Then let

q_{i} := \frac{1}{2}p_{i} − \frac{1}{2}p_{m+1}

for i = 1,…, m. We see that

0, ±q_{1}, ±q_{2},…, ±q_{m}

are all distinct (q_{i} − q_{j} ≠ 0 since p_{i} ≠ p_{j} and q_{i} + q_{j} ≠ 0 since it has a positive component). Finally, we see that

q_{i} ∈ B (i = 1,…, m)

§3. Weakly Reduced Bases  Lecture IX  Page 6

because p_{i} ∈ B and −p_{m+1} ∈ B (since B is O-symmetric) implies \frac{1}{2}(p_{i} − p_{m+1}) ∈ B (since B is convex). This proves that ±q_{1},…, ±q_{m} satisfy the theorem. Q.E.D.

The premise of this theorem can be replaced by Vol(B) ≥ m2^{n} det(Λ) provided we also assume B is compact. As an application, we now give an upper bound on the length of the shortest vector in a lattice.

Theorem 5 In any lattice Λ ⊆ ^{n}, there is a lattice point ξ ∈ Λ such that

∥ξ∥ ≤ \sqrt{\frac{2n}{π}} · det(Λ)^{\frac{1}{n}} .

Proof. Let B be the n-dimensional ball of radius r centered at the origin. Then

Vol(B) = \frac{π^{n/2}}{Γ(\frac{n}{2} + 1)} · r^{n}.

We choose r large enough so that Minkowski’s Convex Body theorem imply B contains a lattice point ξ ∈ Λ:

Vol(B) ≥ 2^{n} det Λ

or

r ≥ \frac{2}{\sqrt{π}} (Γ(\frac{n}{2} + 1) · det(Λ))^{\frac{1}{n}} .

Since Γ(x + 1) ≤ x^{x}, it suffices to choose r so that

r ≥ \sqrt{\frac{2n}{π}}(det(Λ))^{\frac{1}{n}} .

Then ξ ∈ Λ ∩ B satisfies ∥ξ∥ ≤ r. Q.E.D.

If n is large enough, it is known that the constant \sqrt{2/π} can be replaced by 0.32.

Exercise 2.1: Give an upper bound on the length of the shortest vector ξ in a lattice Λ(B) that is not necessarily full-dimensional.

Exercise 2.2: (cf. [12])

i) Show that Vol(B_{n}) = (π^{1/2}Γ(\frac{n}{2} + 1))^{n} where B_{n} is the unit n-ball.

ii) If B is an n × n positive definite symmetric matrix, the set of n-vectors x ∈ ^{n} such that x^{T} Bx ≤ c (c ∈ ) is an ellipsoid E. Determine Vol(E) via a deformation of E into B_{n}.

§3. Weakly Reduced Bases

As an intermediate step towards constructing bases with small defects, we introduce the concept of a weakly reduced basis. The motivation here is very natural. Given a basis B = [b_{1},…, b_{m}], we see that its Gram-Schmidt version B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}] has no defect: δ(B^{∗}) = 1. Although B and B^{∗} are related by a unimodular transformation M, unfortunately M is not generally integer. So we aim to transform B via an integer unimodular matrix into some \overline{B} = [\overline{b}_{1},…, \overline{b}_{m}] that is as close to the ideal Gram-Schmidt version. To make this precise, recall that for i = 1,…, m,

b_{i} = ∑_{j=1}^{i} μ_{ij}b_{j}^{∗}  (7)

where μ_{ij} = \frac{⟨b_{i},b_{j}^{∗}⟩}{⟨b_{j}^{∗},b_{j}^{∗}⟩}, and μ_{ii} = 1.

Definition 1 We say that B is weakly reduced if in the relation (7), the μ_{ij}’s satisfy the constraint

|μ_{ij}| ≤ \frac{1}{2}, (1 ≤ j < i ≤ m).

Weakly reduced bases are as close to its Gram-Schmidt version as one can hope for, using only the elementary unimodular transformations but without permuting the columns. Let us consider how to construct such bases. If B is not weakly reduced, there is a pair of indices (i_{0}, j_{0}), 1 ≤ j_{0} < i_{0} ≤ m, such that

|μ_{i_{0}j_{0}}| > \frac{1}{2}.

Pick (i_{0}, j_{0}) to be the lexicographically largest such pair: recall (previous section) that (i_{0}, j_{0}) is lexicographically larger than (i, j), denoted

(i_{0}, j_{0}) ≻ (i, j),

if either i_{0} > i, or both i_{0} = i and j_{0} > j. Let

c_{0} = ⌊μ_{i_{0}j_{0}}⌉

be the integer closest to μ_{i_{0}j_{0}}. Note that c_{0} ≠ 0. Consider the following unimodular transformation

B = [b_{1},…, b_{i_{0}},…, b_{m}] ⟶ \overline{B} = [\overline{b}_{1},…, \overline{b}_{i_{0}},…, \overline{b}_{m}]

where

\overline{b}_{i} = \{ \begin{matrix}b_{i} & if & i ≠ i_{0} \\ b_{i_{0}} − c_{0}b_{j_{0}} & if & i = i_{0} \end{matrix}

We call the B → \overline{B} transformation a weak reduction step. We observe that \overline{B} and B are Gram-Schmidt equivalent. So we may express \overline{B} in terms of its Gram-Schmidt version (which is still B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}]) thus:

\overline{b}_{i} = ∑_{j=1}^{i} \overline{μ}_{ij}b_{j}^{∗}

where it is easy to check that

\overline{μ}_{ij} = \frac{⟨\overline{b}_{i}, b_{j}^{∗}⟩}{⟨b_{j}^{∗}, b_{j}^{∗}⟩} = \{ \begin{matrix}μ_{ij} & if & i ≠ i_{0}, \\ μ_{ij} − c_{0}μ_{j_{0}j} & if & i = i_{0} \end{matrix}

As usual, μ_{j_{0}j} = 0 if j > j_{0}. In particular,

|\overline{μ}_{i_{0}j_{0}}| = |μ_{i_{0}j_{0}} − c_{0}| ≤ \frac{1}{2}.

Furthermore, if (i, j) is any index such that (i, j) ≻ (i_{0}, j_{0}) then \overline{μ}_{ij} = μ_{ij} so |\overline{μ}_{ij}| ≤ \frac{1}{2}. This immediately gives us the following.

§4. Reduced Bases  Lecture IX  Page 8

Lemma 6 (Weak Reduction) Given any basis B ∈ ^{n×m}, we can obtain a weakly reduced basis \overline{B} where Λ(B) = Λ(\overline{B}) by applying at most \binom{m}{2} weak reduction steps to B.

§4. Reduced Bases and LLL-algorithm

Let us impose a restriction on weakly reduced bases B: Definition 2 A weakly reduced basis B is reduced if in addition it satisfies

∥b_{i}^{∗}∥^{2} ≤ 2∥b_{i+1}^{∗}∥^{2}

for i = 1,…, m − 1, where B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}] is the Gram-Schmidt version of B. We first show that reduced bases have bounded defect. Lemma 7 If B = [b_{1},…, b_{m}] is a reduced basis then its defect is bounded: δ(B) ≤ 2^{\frac{1}{2}}^{\binom{m}{2}}. Proof. If B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}] is the Gram-Schmidt version of B then we see by induction that

∥b_{i−j}^{∗}∥^{2} ≤ 2^{j}∥b_{i}^{∗}∥^{2}

for 0 ≤ j ≤ i. But from the usual relation

b_{i} = b_{i}^{∗} + ∑_{j=1}^{i−1} μ_{ij}b_{j}^{∗}

and |μ_{ij}| ≤ \frac{1}{2}, we get

∥b_{i}∥^{2} ≤ ∥b_{i}^{∗}∥^{2} + \frac{1}{4} ∑_{j=1}^{i−1} ∥b_{j}^{∗}∥^{2}
≤ ∥b_{i}^{∗}∥^{2} + \frac{1}{4} ∑_{j=1}^{i−1} 2^{i−j}∥b_{i}^{∗}∥^{2}
≤ ∥b_{i}^{∗}∥^{2} (1 + ∑_{j=1}^{i−1} 2^{i−j−2})
≤ 2^{i−1}∥b_{i}^{∗}∥^{2}.

(In fact, the inequality is strict for m ≥ 2.) Hence

∏_{i=1}^{m} ∥b_{i}∥^{2} ≤ 2^{\binom{m}{2}} ∏_{i=1}^{m} ∥b_{i}^{∗}∥^{2}.

Q.E.D.

§4. Reduced Bases  Lecture IX  Page 9

\begin{matrix}c \\ ◯ \end{matrix} Chee-Keng Yap September 10, 1993 To measure how close a basis B is to being reduced, we introduce a real function V (B) defined as follows:

V (B) := ∏_{i=1}^{m} V_{i}(B)

where

V_{i}(B) := ∏_{j=1}^{i} ∥b_{j}^{∗}∥ = \sqrt{det(B_{i}^{T} B_{i})}

and B_{i} consists of the first i columns of B. Observe that V_{i}(B) depends only on the Gram-Schmidt version of B_{i}. In particular, if B′ is obtained by applying the weak reduction step to B, then

V (B′) = V (B)

since B′ and B are Gram-Schmidt equivalent. Since ∥b_{i}∥ ≥ ∥b_{i}^{∗}∥ for all i, we deduce that

V (B) = ∏_{i=1}^{n} ∥b_{i}^{∗}∥^{n−i+1} ≤ \{max_{i} ∥b_{i}∥\}^{\binom{n}{2}}.

Now suppose B = [b_{1},…, b_{m}] is not reduced by virtue of the inequality

∥b_{i}^{∗}∥^{2} > 2∥b_{i+1}^{∗}∥^{2}

for some i = 1,…, m. It is natural to perform the following reduction step which exchanges the ith and (i + 1)st columns of B. Let the new basis be

C = [c_{1},…, c_{m}] ← [b_{1},…, b_{i−1}, b_{i+1}, b_{i}, b_{i+2},…, b_{m}].

Thus c_{j} = b_{j} whenever j ≠ i or i + 1. The choice of i for this reduction step is not unique. Nevertheless we now show that V (B) is decreased.

Lemma 8 If C is obtained from B by a reduction step and B is weakly reduced then

V (C) < \frac{\sqrt{3}}{2}V (B).

Proof. Let C = [c_{1},…, c_{m}] be obtained from B = [b_{1},…, b_{m}] by exchanging columns b_{i} and b_{i+1}. As usual, let B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}] be the Gram-Schmidt version of B with the matrix (μ_{jk})_{j,k=1}^{m} connecting them. Similarly, let C^{∗} = [c_{1}^{∗},…, c_{m}^{∗}] be the Gram-Schmidt version of C with the corresponding matrix (ν_{jk})_{j,k=1}^{m}.

We see that

V_{j}(C) = V_{j}(B), (j = 1,…, i − 1, î, i + 1,…, m).

(Note the convention where ˆ⋯ means ⋯ is elided in a sequence.) This is because for j ≠ i, C_{j} = B_{j}U_{j} where C_{j}, B_{j} denotes the matrix comprising the first j columns of C, B (respectively) and U_{j} is a suitable j × j unimodular matrix. Hence | det(C_{j}^{T} C_{j})| = | det(B_{j}^{T} B_{j})|. It follows that

\frac{V (C)}{V (B)} = \frac{V_{i}(C)}{V_{i}(B)} = \frac{∥c_{i}^{∗}∥}{∥b_{i}^{∗}∥}.  (8)

It remains to relate ∥c_{i}^{∗}∥ to ∥b_{i}^{∗}∥. By the usual relations involving the coefficients μ_{jk} and ν_{j}k, we have

c_{i} = b_{i+1} = b_{i+1}^{∗} + ∑_{j=1}^{i} μ_{i+1,j}b_{j}^{∗} = b_{i+1}^{∗} + μ_{i+1,j}b_{i}^{∗} + ∑_{j=1}^{i−1} ν_{ij}c_{j}^{∗}.  (9)

Hence

c_{i}^{∗} = c_{i} − ∑_{j=1}^{i−1} ν_{ij}c_{j}^{∗}

= (b_{i+1}^{∗} + μ_{i+1,j}b_{i}^{∗} + ∑_{j=1}^{i−1} ν_{ij}c_{j}^{∗}) − (∑_{j=1}^{i−1} ν_{ij}c_{j}^{∗})
= b_{i+1}^{∗} + μ_{i+1,i}b_{i}^{∗}.

The last identity is easily seen if we remember that c_{i}^{∗} is the component of c_{i} normal to the subspace spanned by {c_{1},…, c_{i−1}}. Since we switched b_{i} and b_{i+1} in the reduction step, we must have ∥b_{i}^{∗}∥^{2} > 2∥b_{i+1}^{∗}∥^{2}. Thus

∥c_{i}^{∗}∥^{2} = ∥b_{i+1}^{∗}∥^{2} + μ_{i+1,j}^{2}∥b_{i}^{∗}∥^{2}
≤ ∥b_{i+1}^{∗}∥^{2} + \frac{1}{4}∥b_{i}^{∗}∥^{2}
< \frac{1}{2}∥b_{i}^{∗}∥^{2} + \frac{1}{4}∥b_{i}^{∗}∥^{2} = \frac{3}{4}∥b_{i}^{∗}∥^{2}.

This, with equation (8), proves the lemma. Q.E.D.

Exercise 4.1: Show that the reduction factor of \sqrt{3}/2 in this lemma is tight in the planar case, n = 2 (recall Lecture X).

We now describe a slightly simplified version of the LLL-algorithm, following Mishra [11]. In the following, weak-reduce(B) denotes a function call that returns a weakly reduced basis obtained by repeated application of the weak reduction step to B. Similarly, reduce-step(B) denotes a function that applies a single reduction step to a weakly-reduced B.

Simplified LLL-Algorithm Input: B ∈ ^{n×m}, a basis. Output: A reduced basis \overline{B} with Λ(\overline{B}) = Λ(B). Method:

1. Initialize \overline{B} ← weak-reduce(B).

2. while \overline{B} ≠ reduced do
2.1. \overline{B} ← reduce-step(\overline{B})
2.2. \overline{B} ← weak-reduce(\overline{B}).

Correctness: It is clear that if the algorithm halts, then the output \overline{B} is correct. It remains to prove halting. We may write

B = \frac{1}{d}C  (10)

§5. Short Vectors  Lecture IX  Page 11

for some C ∈ ^{n×m} and d ∈ . We may assume that in any elementary integer unimodular transform of the matrix in (10), the common denominator d is preserved. Hence it is sufficient to focus on the integer part C. If C = [c_{1},…, c_{m}] then ∥c_{i}∥ = d∥b_{i}∥, so

V_{i}(C) = d^{i}V_{i}(B)
V (C) = d^{\binom{n}{2}}V (B)
≤ \{d max_{i=1,...,m} ∥b_{i}∥\}^{\binom{n}{2}}.

If s is the maximum bit-size of entries of B then

log ∥b_{i}∥ = O(s + log n).

Each weak reduction step preserves V (C) but a reduction step reduces it by a factor of \sqrt{3}/2. Since |V (C)| ≥ 1, we conclude that the algorithm stops after

log_{\sqrt{3}/2} V (C) = O(n^{2} log \{d max_{i} ∥b_{i}∥\}) = O(n^{2}(s + log n))

reduction steps. Each weak reduction of B involves one call to the Gram-Schmidt procedure and O(n^{2}) vector operations of the form b_{i} ← b_{i} − cb_{j}, (c ∈ ). These take O(n^{3}) arithmetic operations. We conclude with:

Theorem 9 Given a basis A ∈ ^{n×m}, we can compute a reduced basis B with Λ(A) = Λ(B) using O(n^{5}(s + log n)) arithmetic operations, where s is the maximum bit-size of entries in A.

Exercise 4.2: Bit Complexity. For simplicity, assume s ≥ log n. Show that all intermediate numbers in the LLL-algorithm has bit-size O(ns). Conclude that if we use the classical algorithms for rational arithmetic operations, the bit-complexity of the algorithm is O(n^{7}s^{3}).

Exercise 4.3: By keeping track of the updates to basis in the weak reduction step we can save a factor of n. Using fast integer arithmetic algorithms, we finally get O(n^{5}s^{2}L(ns)).

§5. Short Vectors

Let B = [b_{1},…, b_{m}] ∈ ^{n×m} be a basis and let ξ_{1} ∈ Λ = Λ(B) denote the shortest vector lattice vector, ξ_{1} ≠ 0. Although we do not know if this problem is NP -complete, van Emde Boas (1981) has shown the problem becomes NP -complete if we use the maximum norm instead of the Euclidean norm.

In §3, we show that if Λ is a full-dimensional lattice, ∥ξ_{1}∥ is bounded by \sqrt{\frac{2n}{π}} det(Λ)^{\frac{1}{n}}. We do not even have an efficient algorithm to compute some vector with this bound. The purpose of this lecture is to show that we can construct a vector ξ whose length is bounded by a somewhat larger constant. Moreover, ∥ξ∥ is also bounded relative to the length of the shortest vector: ∥ξ∥/∥ξ_{1}∥ ≤ 2^{(m−1)/2}. The algorithm to find such a ξ is automatic if we can show that ξ can be chosen from a reduced base.

Lemma 10 Let B^{∗} = [b_{1}^{∗},…, b_{m}^{∗}] be the Gram-Schmidt version of B. Then the shortest vector ξ_{1} satisfies

∥ξ_{1}∥ ≥ min_{i=1,...,m} ∥b_{i}^{∗}∥.

Proof. As usual

b_{i} = ∑_{j=1}^{i} μ_{ij}b_{j}^{∗}

for suitable μ_{ij} (and μ_{ii} = 1). Suppose

ξ_{1} = ∑_{i=1}^{k} λ_{i}b_{i} (λ_{i} ∈ , λ_{k} ≠ 0)

for some 1 ≤ k ≤ m. Then

ξ_{1} = ∑_{i=1}^{k} λ_{i} ∑_{j=1}^{i} μ_{ij}b_{j}^{∗}

= λ_{k}b_{k}^{∗} + ∑_{i=1}^{k−1} μ′_{i}b_{i}^{∗}

for some suitable μ′_{i} ∈ . Hence

∥ξ_{1}∥ ≥ |λ_{k}| · ∥b_{k}^{∗}∥ ≥ ∥b_{k}^{∗}∥.

Q.E.D.

We deduced easily from the above:

Lemma 11 If B = [b_{1},…, b_{m}] is a reduced basis then the shortest vector ξ_{1} satisfies

(i) ∥b_{1}∥ ≤ 2^{(m−1)/2}∥ξ_{1}∥,

(ii) ∥b_{1}∥ ≤ 2^{(m−1)/4}(det Λ(B))^{1/m}.

Proof. (i) Let b_{i} be the shortest vector in B. Since B is reduced,

∥b_{1}∥^{2} = ∥b_{1}^{∗}∥^{2} = 2^{i−1}∥b_{i}^{∗}∥^{2} ≤ 2^{m−1}∥ξ_{1}∥^{2}.

(ii) ∥b_{1}∥^{2m} ≤ ∏_{i=1}^{m} 2^{i−1}∥b_{i}^{∗}∥^{2} = 2^{\binom{m}{2}} det(B^{T} B). Q.E.D.

Thus we can use the LLL-algorithm to construct a short vector ξ satisfying both

∥ξ∥/∥ξ_{1}∥ ≤ 2^{(m−1)/2} and ∥ξ∥ ≤ 2^{m/4}(det(B^{T} B))^{1/2m}.

Exercise 5.1: Assuming that m is fixed, show that the shortest vector can be found in polynomial time.

Exercise 5.2: (Babai) A generalization of the short vector problem is the problem of near vector: given a basis B = [b_{1},…, b_{n}] ∈ ^{n×m} and a vector u ∈ ^{n}, find a lattice point b ∈ Λ(B) that is “near to u”:

∥u − b∥ ≤ 2^{(n/2)−1}∥u − b_{1}∥

where b_{1} is the nearest lattice point to u. Show that this problem can be solved in polynomial time.

§6. Reconstructing Minimal Polynomials  Lecture IX  Page 13

§6. Factorization via Reconstruction of Minimal Polynomials

Polynomial factorization from root isolation. Suppose we can reconstruct the minimal polynomial of an algebraic number α when we are given an approximation \overline{α} with sufficient accuracy. This gives rise to a very simple strategy for factoring an integer polynomial G(X) of degree ≥ 2. First isolate any root α of G(X) to the necessary accuracy and find its minimal polynomial F (X). Clearly F (X) is an irreducible factor of G(X). Now we can recursively factor G(X)/F (X).

The remainder of this section considers the problem of reconstructing minimal polynomials.

Approximate roots with guarantees. Suppose we are given a pair

(\overline{α}, s), \overline{α} ∈ , s ∈

where s ≥ 4. In our algorithmic applications, the real Re(\overline{α}) and imaginary Im(\overline{α}) parts of α will be rational numbers, but our mathematical results do not depend on this assumption. Let us call the pair (\overline{α}, s) an approximate root if it comes with the guarantee that there exists an algebraic number α ∈ with minimal polynomial F (X) such that

i)  |α − \overline{α}| ≤ ϵ:= 2^{−5s^{3}},  (11)
ii)  F (X) has bit-size less than s.  (12)

We also say the approximate root (\overline{α}, s) belongs to α. Our main task is to show how to reconstruct F (X) efficiently. This also shows that F (X) is uniquely determined under these guarantees. This suggests that the concept of approximate roots can serve as a representation of the algebraic numbers. Although the representation seems quite simple, it is not clear whether it is useful for general algebraic manipulations. In any case, the question of using approximate roots as a general coding scheme for algebraic numbers is incidental to our purposes.

Lattice points as polynomials. Fix an arbitrary integer m, 1 ≤ m ≤ s, and let

c:= 2^{−4s^{3}}.  (13)

Consider the following matrix

B_{m}:= ( \begin{matrix}Re(\overline{α}^{0}) & Re(\overline{α}^{1}) & ⋯ & Re(\overline{α}^{m}) \\ Im(\overline{α}^{0}) & Im(\overline{α}^{1}) & ⋯ & Im(\overline{α}^{m}) \\ c & 0 & ⋯ & 0 \\ 0 & c & ⋯ & 0 \\ ⋮ & & ... \\ 0 & 0 & & c \end{matrix} ) .  (14)

Clearly B_{m} is a basis for a (m + 1)-dimensional lattice in ^{m+3}. Let the columns of B_{m} be b_{0},…, b_{m},

B_{m} = [b_{0},…, b_{m}],

and consider the following correspondence between polynomials G(X) ∈ [X] of degree at most m and lattice points \overline{G} ∈ Λ(B_{m}):

G(X) = ∑_{i=0}^{m} g_{i}X^{i} ⟺ \overline{G} = ∑_{i=0}^{m} g_{i}b_{i}.  (15)

This is seen to be a bijection once we notice

\overline{G} = (Re(G(\overline{α})), Im(G(\overline{α})), cg_{0}, cg_{1},…, cg_{m}).  (16)

It follows that

∥\overline{G}∥^{2} = Re(G(\overline{α}))^{2} + Im(G(\overline{α}))^{2} + c^{2} ∑_{i=0}^{m} g_{i}^{2}
∥\overline{G}∥^{2} = |G(\overline{α})|^{2} + c^{2}∥G(X)∥^{2}.  (17)

This important identity suggests a connection between the minimal polynomial F (X) and short vectors in the lattice Λ(B_{m}): Assume m is the degree of the minimal polynomial F (X). Then the lattice point \overline{F} corresponding to F (X) has small length since F (\overline{α}) is close to F (α) = 0 and c is small implies ∥\overline{F} ∥ = |F (\overline{α})|^{2} + c^{2}∥F (X)∥ is small. In fact for any \overline{G} ≠ \overline{F} we show that ∥\overline{G}∥ ≥ 2^{m}∥\overline{F} ∥. Intuitively, this means that the LLL-algorithm can distinguish \overline{F} from all other lattice points. One complication is that we do not know in advance the degree m of the minimal polynomial. In any case, the idea is to reduce the search for a minimal polynomial to the search for a short vector in a suitable lattice. The following theorem answers the basic questions of this approach.

Theorem 12 (Correctness) Let (\overline{α}, s) be an approximate root belonging to α. With 1 ≤ m ≤ s and c = 2^{−4s^{2}}, construct the basis B_{m} as above. Let F (X) be the minimal polynomial of α and

C:= 2^{2s}c = 2^{2s−4s^{3}}.

(i) If \overline{G} ∈ Λ(B_{m}) satisfies ∥\overline{G}∥ ≤ C then G(α) = 0.

(ii) If m = deg F (X) then ∥\overline{F} ∥ ≤ C.

(iii) If m = deg F (X) then for any lattice point \overline{G} ∈ Λ(B_{m}), G(α) ≠ 0 implies ∥\overline{G}∥ > 2^{s}C.

It is easiest to understand this theorem by seeing how it justifies the following algorithm for reconstructing minimal polynomials:

Minimal Polynomial Algorithm: Input: (\overline{α}, s) with guarantees (11) and (12). Output: F (X), the minimal polynomial of α. Method:

for m = 1, 2,…, do forever 1. Construct the basis B_{m}.

2. Use the LLL-algorithm to find a reduced basis B for B_{m}.

3. Let \overline{G} be the first vector in B, and G(X) the corresponding polynomial.

4. Let H(X) be the primitive part of G(X).

5. If ∥\overline{H}∥ ≤ C then output H(X) and halt.

Correctness: Let F (X) be the minimal polynomial of α. Part (i) of the theorem shows that the algorithm cannot halt at any stage m where m < deg F. So suppose we have reached stage m = deg F. From part (ii), the shortest vector in Λ(B_{m}) has length at most C. Let \overline{G} be first vector in the reduced basis. By a property of reduced bases (Lemma 11(i)), ∥\overline{G}∥ ≤ 2^{s} · C. Then part (iii) of the theorem implies G(α) = 0. Hence the primitive part of G(X) must be the minimal polynomial F (X). Therefore in stage m = deg F, the polynomial H(X) is indeed equal to F (X). Hence H(X) will satisfy the condition ∥\overline{H}∥ ≤ C necessary for halting. So our algorithm will surely halt at the correct stage, and when it halts, the output is correct. This concludes the correctness proof.

Remark: Our constants ϵ, c and C has Θ(s^{3}) bits each. In the original paper [6], the corresponding constants use only Θ(s^{2}) bits. But they only proved the equivalent of part (iii). Our proof of part (i) forces us to use Ω(s^{3}) bits. Still, there is not much difference in complexity between computing roots to Θ(s^{3}) bits of accuracy as opposed to Θ(s^{2}) bits. This is because Newton iteration can be used once we have about s^{2} bits of accuracy (Lecture VI).

Proof of the Correctness Theorem. The rest of this section concerns this proof. We will be using the fact that the guarantees (11) and (12) imply

∥F (X)∥_{∞} ≤ 2^{s−1}, deg(F) ≤ s − 1, |α| ≤ 2^{s}.

First we need the following estimate.

Lemma 13 Let F (X) ∈ [X] have degree ≤ m, α, \overline{α} ∈ such that M ≥ max\{1, |α|, |\overline{α}|\} and |α − \overline{α}| ≤ ϵ. Then

|F (α) − F (\overline{α})| ≤ ϵ · ∥F ∥_{∞}m^{2}M^{m}\}.

Proof. Let F (X) = ∑_{i=0}^{m} f_{i}X^{i}. Then

|F (α) − F (\overline{α})| = ∑_{i=0}^{m} f_{i}(α^{i} − \overline{α}^{i})

≤ ∑_{i=0}^{m} |f_{i}| · |α − \overline{α}| · (∑_{j=0}^{i−1} |\overline{α}|^{j}|α|^{i−j−1})

≤ ∥F ∥_{∞} · ϵ · ∑_{i=0}^{m} iM^{i}.

By the Cauchy-Schwartz inequality,

∑_{i=0}^{m} iM^{i} ≤ (∑_{i=0}^{m} i^{2})^{\frac{1}{2}} (∑_{i=0}^{m} M^{2i})^{\frac{1}{2}} ≤ (m^{3/2}) · (m^{\frac{1}{2}} M^{m}) = m^{2}M^{m}.

Q.E.D.

Let us now prove part (i) of the theorem. From (17) and the assumption ∥\overline{G}∥ ≤ C, we get

|G(\overline{α})| ≤ C and c∥G(X)∥ ≤ C.  (18)

The latter inequality implies

∥G(X)∥ ≤ c^{−1}C = 2^{2s}.

By Lemma 13, we get

|G(α) − G(\overline{α})| ≤ ϵ · ∥G∥_{∞} · m^{2} · 2^{sm}

using the fact that |α| ≤ 2^{s}. Hence

|G(α) − G(\overline{α})| ≤ 2^{−5s^{3}} · 2^{2s} · 2^{s} · 2^{s^{2}}
≤ 2^{−4s^{3}}  (since s ≥ 4).  (19)
|G(α)| ≤ |G(α) − G(\overline{α})| + |G(\overline{α})|
≤ 2^{−4s^{3}} + C
≤ 2C.

Let F (X) = ∑_{i=0}^{n} f_{i}X^{i} be the minimal polynomial of α and α = α_{1}, α_{2},…, α_{n} be the conjugates of α. Observe that

f_{n}^{m} ∏_{i=1}^{n} G(α_{i})  (20)

is symmetric in the α_{i} and of degree m in α_{i}. But the elementary symmetric functions in the α_{i}’s are f_{1}/f_{m}, f_{2}/f_{m},…, f_{m−1}/f_{m}. Applying the fundamental theorem on symmetric functions, we conclude that the expression (20) gives an integer. Since |f_{n}| ≤ 2^{s}, |α_{i}| ≤ 2^{s}, we get

|G(α_{i})| ≤ ∑_{j=0}^{m} |g_{j}∥α_{i}|^{j}

≤ ∥G∥_{∞} ∑_{j=0}^{m} 2^{sj}
≤ 2^{2s} · 2^{sm+1} ≤ 2^{2s^{2}}.

Hence

|f_{n}^{m} ∏_{i=1}^{n} G(α_{i})| ≤ |f_{n}|^{m} · |G(α)| · ∏_{i=2}^{n} |G(α_{i})|
≤ 2^{sm} · 2C · (2^{2s^{2}})^{n−1}
≤ C · 2^{2s^{3}}
< 1.

Hence G(α_{i}) = 0 for some i. But the α_{i}’s are conjugates so G(α) = 0. This proves part (i) of the theorem.

We now show part (ii) of the theorem. Let F (X) be the minimal polynomial of α. We must bound ∥\overline{F} ∥ from above. By assumption,

∥F (X)∥_{∞} ≤ 2^{s}, |α| ≤ 2^{s}

and by Lemma 13,

|F (\overline{α})| = |F (\overline{α}) − F (α)|
≤ ϵ · ∥F ∥_{∞} · s^{2} · 2^{s^{2}}
≤ 2^{−5s^{3}} · 2^{s} · 2^{s} · 2^{s^{2}}
≤ 2^{−4s^{3}}

Hence

∥\overline{F} ∥ = (|F (\overline{α})|^{2} + c^{2}∥F (X)∥^{2})^{\frac{1}{2}}
≤ ((2^{−4s^{3}})^{2} + (2^{−4s^{3}} · 2^{s})^{2})^{\frac{1}{2}}
≤ 2^{2s−4s^{3}} = C.

To prove part (iii), we need a lower bound on G(α) where G(α) ≠ 0.

Lemma 14 Let F (X), G(X) ∈ [X] be non-constant and relatively prime. Suppose

m ≥ max{deg F, deg G}
M ≥ 1 + max{∥F ∥_{∞}, ∥G∥_{∞}}

Then at any root α of F (X),

|G(α)| ≥ \frac{1}{m^{m}M^{3m}} .

Proof. Let deg F = k, deg G = ℓ. So k ≥ 1, ℓ ≥ 1 and there exists A(X), B(X) ∈ [X] such that deg A ≤ ℓ − 1, deg B ≤ k − 1 and

A(X)F (X) + B(X)G(X) = 1.  (21)

We rewrite equation (21) using (the transpose of) Sylvester’s matrix S = S(F, G) (see Lecture III.3):

S^{T} · ( a_{ℓ−1} ; ⋮ ; a_{0} ; b_{k−1} ; ⋮ ; b_{0} ) = ( \begin{matrix}0 \\ · \\ · \\ · \\ 0 \\ 1 \end{matrix} )

where S is a (k + ℓ)-square matrix each of whose rows have non-zero entries that are either the coefficients of F (X) or of G(X). Since det S is the resultant of F and G, so det S ≠ 0. Then by Cramer’s rule,

b_{i} = \frac{det S_{i}}{det S}

where S_{i} is obtained by replacing a suitable column of S^{T} by the (k + ℓ)-vector (0,…, 0, 1)^{T}. Using Hadamard’s bound,

|b_{i}| ≤ | det S_{i}| ≤ m^{m}M^{2m−1}

since each row of S has 2-norm at most \sqrt{m}M. Using Cauchy’s bound that |α| ≤ M, we get

|B(α)| ≤ | ∑_{i=0}^{k−1} b_{i}α^{i}|

≤ ∑_{i=0}^{k−1}(m^{m}M^{2m−1})M^{i}
≤ m^{m}M^{3m−1}

From (21) we get B(α) · G(α) = 1 and hence G(α) ≥ m^{−m}M^{1−3m}.

Q.E.D.

We conclude the proof of part (iii) of the theorem: let \overline{G} ∈ Λ(B_{m}) and G(α) ≠ 0. We must bound ∥\overline{G}∥ from below. Let assume

∥G(X)∥ ≤ 2^{3s}

since otherwise

∥\overline{G}∥ ≥ c∥G(X)∥ > c · 2^{3s} = 2^{s} · C,

and we are done. Note that G(X) and F (X) are relatively prime because F (X) is a minimal polynomial. Applying Lemma 14, we see that (with M = 2^{3s}, m = s),

|G(α)| ≥ s^{−s}2^{−9s^{2}} = 2^{−s log s−9s^{2}} > 2^{s+1}C.

Again we apply Lemma 13 to get |G(α) − G(\overline{α})| ≤ 2^{−4s^{3}} < C (just as equation (19) above). Finally,

|G(\overline{α})| ≥ |G(α)| − |G(α) − G(\overline{α})|
≥ 2^{s+1}C − C > 2^{s}C.

This completes the proof of the Correctness Theorem.

It is evident that the bounds used in proving part (iii) are very generous.

Exercise 6.1: Estimate the complexity of this factorization procedure.

References

[1] B. Buchberger, G. E. Collins, and R. Loos (eds.). Computer Algebra. Springer-Verlag, 1983.

[2] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988.

[3] Chung jen Ho. Topics in algebraic computing: subresultants, GCD, factoring and primary ideal decomposition. PhD thesis, Courant Institute, New York University, June 1989.

[4] E. Kaltofen. Polynomial factorization 1982-1986. Department of Computer Science Report 86-19, Rensselaer Polytechnic Institute, September 1986.

[5] Erich Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM Journal Computing, 12:469–489, 1985.

[6] R. Kannan, A. K. Lenstra, and L. Lovász. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math.Comp., 50:235–250, 1988.

[7] Susan Landau. Factoring polynomials over algebraic number fields. SIAM Journal Computing, 14:184–195, 1985.

[8] A. K. Lenstra. Factoring multivariate polynomials over algebraic number fields. SIAM Journal Computing, 16:591–598, 1987.

[9] A.K. Lenstra. Factoring multivariate integral polynomials. Theoretical Computer Science, 34:207–213, 1984.

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

[11] Bud Mishra. Lecture Notes on Lattices, Bases and the Reduction Problem. Techical Report 300, NYU-Courant Institute, Robotics Laboratory, June 1987.

[12] Morris Newman. Integral Matrices. Pure and Applied Mathematics Series, vol. 45). Academic Press, New York, 1972.

[13] C. P. Schnorr. A more efficient algorithm for lattice basis reduction. Journal of Algorithms, 9:47–62, 1988.

[14] Arnold Schönhage. Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm. Proc. 11th ICALP, pages 436–447, 1984. Lecture Notes in Comp. Sci., No. 172.