§1. Lattices  Lecture VIII  Page 1

Lecture VIII Gaussian Lattice Reduction

The subject known as the geometry of numbers was initiated by Minkowski. Its power and elegance is comes from converting algebraic problems into a geometric setting (which, we might say, is an inversion of the program of Descartes to algebraize geometry). Cassels [1] (see also [7]) gives a classical treatment of this subject; more recent development is seen in Grötschel, Lovász and Schriver [3]. H. W. Lenstra first introduced these methods to complexity theory, leading to polynomial-time algorithms for integer programming in fixed dimensions. Later, with A. K. Lenstra and Lovász, he also showed that polynomial factorization is polynomialtime. In this lecture, we use 2-dimensional lattices to introduce a key computational problem in the Geometry of numbers: lattice reduction. It turns out that GCD can be viewed as 1dimensional lattice reduction. Here an algorithm of Gauss lays claim to be the natural extension of Euclid’s algorithm to 2-dimensions. The algorithm originally arises in Gauss’s theory of reduction of integral binary quadratic forms [2,6,5]. See [9,8] for some recent work on the Gaussian algorithm.

§1. Lattices

We introduce the terminology of lattices. This is more general than is needed for this lecture.

Fix d ≥ 1. Let S ⊆ ^{d} be a non-empty finite set of real d-vectors. The lattice generated by S is the set of integer linear combinations of the elements in S,

Λ = Λ(S) :={m_{1}u_{1} + m_{2}u_{2} + ⋯ + m_{k}u_{k} : k ≥ 1, u_{i} ∈ S, m_{i} ∈ }.

The set S is called a generating set for the lattice Λ. If S has the minimum cardinality among generating sets for Λ, we call S a basis of Λ. The cardinality of a basis of Λ is the dimension, dim Λ, of Λ. Instead of Λ(S), we also write u if S = {u}; or

Λ(u_{1},…, u_{k}) = u_{1} + u_{2} + ⋯ + u_{k}

if S = {u_{1},…, u_{k}}.

Note that even for d = 1, the dimension of a lattice can be arbitrarily large or even infinite. But in our applications, it is sufficient and customary to restrict Λ to the case where u_{1},…, u_{k} are linearly independent as real vectors. In this case, 1 ≤ k ≤ d. Viewing S as an ordered sequence (u_{1},…, u_{k}) of vectors, we let

A = [u_{1},…, u_{k}] ∈ ^{d×k}

denote a d × k real matrix, and write Λ(A) instead of Λ(S). Under the said convention, A has matrix rank k. We say Λ(A) is full-dimensional iff k = d.

A lattice Λ with only integer coordinates, Λ ⊆ ^{d}, is called an integer lattice. The simplest example of a lattice is the unit integer lattice Λ = ^{d}. A basis for this lattice is the set S = {e_{1},…, e_{d}} of unit vectors in ^{d} (equivalently, the identity matrix E = [e_{1},…, e_{d}] is a basis). If we replace any e_{i} by the vector consisting of all 1’s, we get another basis.

We examine the conditions for two bases A, B to generate the same lattice. If M is a d × d real non-singular matrix, we can transform a basis A to AM.

Definition: A square matrix U ∈ ^{k×k} is unimodular if det U = ±1. A real, integer, etc, unimodular matrix is one whose entries are all real, all integer, etc.

A unimodular matrix U represents a unimodular transformation of lattice bases, A ↦ AU. Note that the inverse of a (real or integer, respectively) unimodular matrix is still (real or integer) unimodular. The next theorem shows why we are interested in integer unimodular matrices.

Theorem 1 Let A, B ∈ R^{d×k} be two bases. Then Λ(A) = Λ(B) iff there exists an integer unimodular matrix U such that A = BU.

Proof. (⇒) Since each column of A is in Λ(B), there is an integer matrix U_{A} such that

A = BU_{A}.

Similarly, there is an integer matrix U_{B} such that

B = AU_{B}.

Hence A = AU_{B}U_{A}. If A′ is an m × m submatrix of A such that det A′ ≠ 0, then A′ = A′U_{B}A_{A} shows that det U_{B}U_{A} = ±1. Since U_{A}, U_{B} are integer matrices this implies | det U_{A}| = | det U_{B}| = 1.

(⇐) If A = BU then Λ(A) ⊆ Λ(B). But since B = AU^{−1}, Λ(B) ⊆ Λ(A). Q.E.D.

Definition: The determinant of a lattice Λ is given by

det Λ := \sqrt{det A^{T} A}

where A is any basis with Λ(A) = Λ.

The previous theorem shows that det Λ is well-defined: if A = BU for some unimodular matrix U (this demonstration does not depend on U being integer) then

det A^{T} A = det U^{T} B^{T} BU = det(U^{T}) det(B^{T} B) det(U)
= det B^{T} B.

Geometrically, det Λ is the smallest volume of a parallelepiped formed by k independent vectors of Λ (k = dim Λ). For instance, the unit integer lattices have determinant 1. For Λ = ^{2}, another pair of independent vectors whose parallelogram has unit area is u = (2, 1), v = (3, 2).

It is easy to check that given any basis A = [a_{1},…, a_{n}], the following transformations of A are unimodular transformations:

(i) Multiplying a column of A by −1:

A′ = [a_{1},…, a_{i−1}, −a_{i}, a_{i+1},…, a_{n}].

(ii) Adding any constant multiple c of one column to another:

A′ = [a_{1},…, a_{j},…, a_{i} + ca_{j},…, a_{n}].

§2. Shortest vectors  Lecture VIII  Page 3

(iii) Permuting two columns of A:

A′ = [a_{1},…, a_{j−1}, a_{i}, a_{j+1},…, a_{i−1}, a_{j}, a_{i+1}, ,…, a_{n}].

We call these the elementary unimodular transformations. If c in (ii) is an integer, then (i), (ii) and (iii) constitutes the elementary integer unimodular transformations.

A fundamental computational problem in lattices is to compute another basis B for a given lattice Λ(A) consisting of “short” vectors. Barring other considerations, the shortest k-sequence (where k = dim Λ(A)) is desirable. In the present lecture, we will give an efficient algorithm in the two dimensional case. For the general case, we defer to a subsequent lecture.

Exercise 1.1: Show that if ad − bc = 1 then (a + b, c + d) = 1.

Exercise 1.2: Determine all bases for the unit integer lattice ^{2} where the components of each basis vector is between −4 and 4. (Distinguish a vector up to sign, as usual.)

§2. Shortest vectors in planar lattices

We show the connection between shortest vector in 2-dimensional lattices and GCD for integers.

Let |u| denote the (Euclidean) length of a vector u ∈ ^{d}. So |u|:= ∥u∥_{2}, using our general notation. The scalar product of two d-vectors u = (a_{1},…, a_{d}) and v = (b_{1},…, b_{d}) is ⟨u, v⟩:= ∑_{i=1}^{d} a_{i}b_{i}. The unit vector along direction u is û:= u/|u|. We have the basic inequality

|⟨u, v⟩| ≤ |u| · |v|.  (1)

Note that the zero vector 0 is always an element of a lattice. We define u ∈ Λ to be a shortest vector in Λ if it has the shortest length among the non-zero vectors of Λ. More generally, we call a sequence

(u_{1}, u_{2},…, u_{k}), k ≥ 1

of vectors a shortest k-sequence of Λ if for all i = 1,…, k, u_{i} is the shortest vector in the set Λ \ Λ(u_{1}, u_{2},…, u_{i−1}). We call a vector a kth shortest vector if it appears as the kth entry in some shortest k-sequence. Clearly k ≤ d. For instance, if u, v are both shortest vectors and are independent, then (±u, ±v) and (±v, ±u) are shortest sequences and so both u, v are 2nd shortest vectors. We will not distinguish u from −u when discussing shortest vectors. So we may say u is the unique ith shortest vector if u and −u are the only ith shortest vectors. In a 2-dimensional lattice Λ, the shortest 2-sequence forms a basis for Λ. Hence we may speak of a shortest basis for Λ. But in higher dimensions, a shortest k-sequence (where k > 2 is the dimension of the lattice) need not form a basis of the lattice.

Exercise 2.1: (Dub’e) Consider e_{1}, e_{2},…, e_{n−1}, h where e_{i} is the unit n-vector whose ith com-

ponent equals 1 and all other components equal zero, and h = (\underbrace{\frac{1}{2}, \frac{1}{2},…, \frac{1}{2}}_{n}). Show that

this set of vectors form a basis for the lattice Λ = ∪ (\frac{1}{2} + ). What is the shortest n-sequence of Λ? Show that for n ≥ 5, this shortest n-sequence is not a basis for Λ.

We note that the shortest vector problem is intimately connected to the GCD problem. Suppose d = 1 and u_{1},…, u_{k} are integers. Then Λ = Λ(u_{1},…, u_{k}) = Λ(g) where g = GCD(u_{1},…, u_{k}). So g is the shortest vector in Λ. Hence we can think of computing shortest vectors as a generalization of the GCD problem. Next we turn to 2-dimensions.

In the rest of this lecture, we focus on d = 2 and identify with ^{2}.

So we speak of complex numbers and 2-vectors interchangeably. Thus every lattice Λ ⊆ ^{2} corresponds to a set of complex numbers.

Fundamental Region.

Definition 1 The fundamental region of u ∈ \ {0} is the set F(u) of complex numbers v ∈ such that

1. |v| ≥ |u|;

2. −\frac{|u|^{2}}{2} < ⟨u, v⟩ ≤ \frac{|u|^{2}}{2} .

Condition 2 implies the angle between u and v is at least 60^{∘}. The following figure illustrates the fundamental region of u.

Figure 1. Fundamental Region of u is shaded.

This figure is typical in that, when discussing the fundamental region of a number u ∈ , we usually rotate the axes so that u appears horizontal.

The unit normal to a 2-vector or complex number u is denoted u^{⊥}:= ûı. Note that multiplying a complex number by ı amounts to rotating the corresponding vector counter-clockwise by 90^{∘}.

§3. Coherent Remainder Sequences  Lecture VIII  Page 5

Lemma 2 If v is in the fundamental region of u then the sequence (u, v) is the shortest 2sequence in Λ(u, v). Moreover, this is unique unless |u| = |v|.

Proof. The lemma is clear if |u| = |v|. So assume |u| < |v|. We first show that u is the unique shortest vector of Λ = Λ(u, v). Let w = mu + nv ∈ Λ be a non-zero vector. Projecting w onto u^{⊥},

|⟨w, u^{⊥}⟩| ≥ \frac{|n|\sqrt{3}|v|}{2},  (2)

which implies |w| > |⟨w, u^{⊥}⟩| > |v| ≥ |u| unless |n| ≤ 1. Similarly,

|⟨w, û⟩| ≥ \frac{(|m| − 1/2)|u|}{2},

which implies |w| > |⟨w, û⟩| > |u| unless |m| ≤ 1. If |n| = 1 and |m| = 1, we see that

|w|^{2} = ⟨w, u^{⊥}⟩^{2} + ⟨w, û⟩ > \frac{3}{4}|u|^{2} + \frac{1}{4}|u|^{2} = |u|^{2}.

This proves that is |m| = 1, n = 0, i.e., u is the unique shortest vector.

Now we show that v is the shortest vector in Λ\Λ(u). If w = mu+nv is a second shortest vector, then n ≠ 0. This implies |n| = 1 (otherwise, we showed |w| > |v|). Then |⟨w, û⟩| ≥ |⟨v, û⟩|, with equality iff m = 0. Hence

|w|^{2} ≥ |⟨v, û⟩|^{2} + |⟨v, u^{⊥}⟩|^{2} = |v|^{2},

with equality iff m = 0. Hence w = v. Q.E.D.

Exercise 2.2: Prove equation (1).

Exercise 2.3: Construct the shortest 2-sequence for the lattice Λ(u, v) where u = ( \begin{matrix}9 \\ 5 \end{matrix} ) and

v = ( \begin{matrix}5 \\ 3 \end{matrix} ).

Exercise 2.4: Show how to compute the second shortest vector in Λ(u, v), given that you have the shortest vector w. You may assume that you know m, n ∈ such that w = mu + nv.

Exercise 2.5: (Zeugmann, v.z.Gathen) Let a ≥ b be positive integers. Show that the shortest vector in the lattice Λ ⊆ ^{2} generated by (a(a + 1), 0) and (b(a + 1), 1) is (0, a′) where a′ = a/GCD(a, b). Conclude that integer GCD computation can be reduced to shortest vector in ^{2}.

Exercise 2.6: Show that if v, v′ are distinct members of F(u) then Λ(u, v) ≠ Λ(u, v′).

§3. Coherent Remainder Sequences

Let 0 ≤ α ≤ 1. We say a pair (u, v) of complex numbers is α-coherent if

⟨û, v̂⟩ ≥ α, u ≠ 0, v ≠ 0.

If α = 0 then we simply say coherent; if α = 1/2 then we say strongly coherent. If (u, v) is not coherent, we say it is incoherent. We say a pair (u, v) is ordered if |u| > |v|, otherwise it is inverted. We say (u, v) is admissible if it is ordered and coherent. If (u, v) = (v, u) denotes the non-reflex angle between the vectors u and v, then α-coherence of u, v amounts to

(u, v) ≤ cos^{−1}(α).

Thus (u, v) is strongly coherent means (u, v) ≤ 60^{∘}.

If v is non-zero, we define the coherent quotient quo_{+}(u, v) of u, v to be the j_{0} ∈ such that

|u − j_{0}v| = min_{j}{u − jv}

where j ranges over all j ∈ such that (u − jv, v) is coherent. The coherent remainder of u, v is defined to be

rem_{+}(u, v) := u − quo_{+}(u, v) · v.

The following figure illustrates geometrically the taking of coherent remainders.

Figure 2. Coherent remainder of u, v where quo_{+}(u, v) = 2.

Note that the pair (v, rem_{+}(u, v)) is coherent unless rem_{+}(u, v) = 0. Furthermore,

quo_{+}(u, v) = ⌊\frac{⟨u, v⟩}{|v|^{2}}⌋ .

Hence if (u, v) is coherent, quo_{+}(u, v) ≥ 0. If quo_{+}(u, v) < 0 then (u, v) is not coherent. It is easy to see that quo_{+}(u, v) > 0 implies (v, rem_{+}(u, v)) > (u, v).

Definition 2 The coherent remainder sequence (abbreviated, CRS) of u_{0}, u_{1} is the maximal length sequence of complex numbers

Crs(u_{0}, u_{1}) :=(u_{0}, u_{1},…, u_{k}), k ≥ 1

such that

1. Each pair (u_{i−1}, u_{i}) is admissible, i = 1,…, k.

2. u_{i+1} = rem_{+}(u_{i−1}, u_{i}) for all i = 1,…, k − 1.

A pair in the CRS is just any two consecutive members, (u_{i}, u_{i+1}). We can speak of the initial or terminal pair. Note that a pair (u, v) is a terminal pair in some CRS iff (u, v) is a CRS. So we may call (u, v) a “terminal pair” without reference to any larger CRS. The “maximal length” requirement in the definition of a coherent remainder sequence means that if u_{k+1} is the coherent remainder of the terminal pair (u_{k−1}, u_{k}), then either u_{k+1} = 0 or |u_{k+1}| ≥ |u_{k}|. We now show a property of terminal pairs for which u_{k+1} ≠ 0.

Figure 3. A terminal pair (u, v).

Lemma 3 Let u, v ∈ , |u| ≥ |v| > 0 and r = rem_{+}(u, v). If |r| ≥ |v| then one of the following holds (see Figure 3):

(I) r ∈ F(v).

(II) r − v ∈ F(v).

(III) −v ∈ F(r − v).

Proof. Without loss of generality, assume ⟨r, v^{⊥}⟩ > 0 (v^{⊥} points upwards in the figure). Clearly, r belongs to one of the three regions (I), (II) or (III) as shown in the figure. If r is in (I) or (II), it clearly satisfies the lemma. In case (III), r − v lies in region (IV), defined as

{z ∈ : |z| ≤ |v|, |v + z| ≥ |v|, ⟨z, v^{⊥}⟩ ≥ 0}.

The line segment from 0 to r − v intersects the circle centered at −v with radius |v| at some p ∈ . Dropping the perpendicular from −v to the segment Op, we see that

⟨(−v), p⟩ = \frac{|p|^{2}}{2}

and hence ⟨(−v), (r − v)⟩ ≤ \frac{|r−v|^{2}}{2} , i.e., −v ∈ F(r − v). Q.E.D.

This lemma justifies our tacit decision in the definition of a CRS to exclude the possibility that |u_{0}| = |u_{1}|. According to the above lemma, if |u| = |v|, then either v or rem_{+}(u, v) − v is the shortest pair.

Furthermore, note that if (u, v) is a terminal pair, then either rem_{+}(u, v) = 0 or the conditions in this lemma is fulfilled. But in either case, we may conclude:

Corollary 4 Let (u, v) be a terminal pair of a coherent remainder sequence. Then either v or rem_{+}(u, v) − v is a shortest vector in the lattice generated by the initial pair.

Thus we reduce the shortest vector problem to computing coherent remainder sequence.

Lemma 5 Let θ_{i} be the angle between successive entries (u_{i−1}, u_{i}) of a CRS u_{0}, u_{1},…, u_{k}. Either all θ_{i} is zero or the sequence of θ_{i} is strictly increasing.

Exercise 3.1: Prove this.

Remarks: i) The process of successive reduction of 2-vectors by subtracting a multiple of the last vector from the last-but-one vector may be called the “generic Gaussian algorithm”. Our “coherent version” of this generic Gaussian algorithm is the analogue of the non-negative remainder sequences for rational integers. In terms of continued fractions, ours is the analogue of the simple continued fraction. The “standard Gaussian algorithm” is analogous to the symmetric remainder sequences in the integer case or the so-called -continued fractions. See [9] for the description of other variants of the Gaussian algorithm. ii) The study of unimodular transformations is a deep topic which we only touch upon. For some basic properties of the fundamental region, see for example, [4]. In the classical approach

such as in [4], a unimodular transformation U = ( \begin{matrix}a & b \\ c & d \end{matrix} ) transforms a complex number z to

another complex number Uz = (az + b)/(bz + c). The connection to our description is that our

vector ( \begin{matrix}u \\ v \end{matrix} ) becomes the classical z = u/v and converse z becomes our ( \begin{matrix}z \\ 1 \end{matrix} ). Note that

sometimes ‘unimodular matrices’ are defined as having determinant +1 (e.g., [4]). Then the upper-half complex plane is transformed into itself by such transformations.

Exercise 3.2: [Sixty degrees lemma] Let u, v ∈ [ı], |u| ≥ |v|. If (u, v) is not strongly coherent then v is the shortest vector in Λ(u, v). See Figure 4. Note: This exercise shows that a weaker condition than “u ∈ F(v)” can be used: the shortest vector problem is essentially solved once the generating vectors are transformed until the angle between them is at least 60 degrees.

§4. CRS Length  Lecture VIII  Page 9

Figure 4. Sixty Degrees Region of u.

Exercise 3.3: Compute the sequence Crs(33 + 4ı, 20 + ı).

Exercise 3.4: Let (u_{0}, u_{1},…, u_{k}) be a CRS.

i) For any complex θ, the sequence (u_{0}θ, u_{1}θ,…, u_{k}θ) is also a CRS.

ii) Assume u_{1} is real and u_{0} lies in the first quadrant. The angle between consecutive entries always contains the real axis and the subsequent u_{i}’s alternately lie in the first and fourth quadrants.

§4. Bounds on length of CRS

We prove two results in this section. First we bound the length of a CRS in terms of its initial term. Second, we show that a CRS whose initial pair is not α-coherent (0 < α < 1) has bounded length (depending only on α).

Length of a CRS. For any coherent remainder sequence (u_{0}, u_{1},…, u_{k}), we have

|u_{0}| ≥ |u_{1}| > |u_{2}| > ⋯ > |u_{k}| ≥ 1.

We obtain an upper bound on k in terms of |u_{0}|. First we introduce an intermediate sequence

ℓ_{0}, ℓ_{1},…, ℓ_{k−1}

where

ℓ_{i}:= \frac{⟨u_{i}, u_{i+1}⟩}{|u_{i+1}|}.

Lemma 6

i) |u_{i}| ≥ ℓ_{i} for i = 0,…, k − 1. ii) ℓ_{i−1} ≥ |u_{i}| for i = 1,…, k − 1, where, with the possible exception of i = k − 1, the inequality is strict. If ℓ_{k−2} = |u_{k−1}| then ℓ_{k−1} = 0. iii) ℓ_{k−1} < |u_{k}|.

Proof. i) This is immediate. ii) Define

q_{i}:= ⌊\frac{ℓ_{i−1}}{|u_{i}|} ⌋ , (i = 1,…, k).

Clearly, u_{i+1} = u_{i−1} − q_{i}u_{i} for i = 1,…, k − 1. But q_{i} ≥ 1 iff i ≤ k − 1. This proves ℓ_{i−1} ≥ |u_{i}| for i ≤ k − 1. Moreover, if equality is attained for any i then we easily check that ⟨u_{i}, u_{i+1}⟩ = 0. This would imply that i = k − 1 and ℓ_{k−1} = 0, as desired. iii) This follows from the condition q_{k} = 0, for termination of the CRS. Q.E.D.

We summarize this lemma as:

|u_{0}| ≥ ℓ_{0} > |u_{1}| ≥ ℓ_{1} > ⋯ ≥ ℓ_{k−3} > |u_{k−2}| ≥ ℓ_{k−2} ≥_{(∗)} |u_{k−1}| ≥_{(∗∗)} ℓ_{k−1} < |u_{k}|,

where either inequality (∗) is strict or (∗∗) is strict (in which case ℓ_{k−1} = 0).

Lemma 7 For i = 1,…, k − 2, ℓ_{i−1} ≥ ℓ_{i} + ℓ_{i+1}.

Proof.

ℓ_{i−1} = \frac{⟨u_{i−1}, u_{i}⟩}{|u_{i}|}
= \frac{⟨u_{i+1} + u_{i}q_{i}, u_{i}⟩}{|u_{i}|}
= \frac{⟨u_{i+1}, u_{i}⟩}{|u_{i}|} + q_{i}|u_{i}|
> \frac{⟨u_{i+1}, u_{i+2}⟩}{|u_{i+2}|} + |u_{i}| (since ⟨û_{i+1}, û_{i}⟩ > ⟨û_{i+2}, û_{i+1}⟩)
≥ ℓ_{i+1} + ℓ_{i}.

Q.E.D.

Assume k ≥ 3. Then

ℓ_{k−3} > ℓ_{k−2} ≥ |u_{k−1}| ≥ 1.

Let 2 > ϕ > 1.618 be the positive root of X^{2} − X − 1. Then by induction, we have:

Lemma 8 For i = 3,…, k, ℓ_{k−i} > ϕ^{i−3}. In particular, n = ℓ_{0} > ϕ^{k−3} or

k < 3 + log_{ϕ} n.

Length of CRS for non α-coherent pairs. For our second result, we need a simple lemma.

Lemma 9 Let |u| ≥ |v|. If (u, v) is not α-coherent, then ⟨u, ıv⟩ > \sqrt{1 − α^{2}} · |v|^{2}.

Proof. We have ⟨u, ıv⟩^{2} + ⟨u, v⟩^{2} = |uv|^{2}. Since (u, v) is not α-coherent, ⟨u, v⟩^{2} < α^{2}|uv|^{2}, and hence ⟨uı, v⟩^{2} > (1 − α^{2})|uv|^{2} ≥ (1 − α^{2})|v|^{4}. Q.E.D.

Theorem 10 For any 0 < α < 1, there is a constant C = C(α) such that if (u, v) is admissible but not α-coherent, then the coherent remainder sequence of u, v has length at most C.

Proof. We reduce this to a classical result on transformations of the complex plane by real

unimodular matrices U = ( \begin{matrix}a & b \\ c & d \end{matrix} ) with determinant +1 (see [4, p. 350]). Two complex

points z, z′ are equivalent if they are related by such a matrix U:

z′ = Uz = \frac{az + b}{cz + d}.

The classical result states:

For any real γ > 0, there exists a bound C′ = C′(γ) such that any set S of pairwise equivalent complex points satisfying

z ∈ S ⇒ Im(z) ≥ γ, Re(z) ≤ \frac{1}{2}

has size at most C′.

Let (u_{0}, u_{1},…, u_{k}) be the coherent remainder sequence of u, v in the statement of the theorem. Define

S′:={z_{i} : i = 0,…, ⌊(k − 1)/2⌋} ⊆

where z_{i}:= u_{2i+1}/u_{2i}. Notice that the elements of S′ are pairwise equivalent since the relation

( \begin{matrix}u_{0} \\ u_{1} \end{matrix} ) = ⟨q_{1},…, q_{2i}⟩ ( \begin{matrix}u_{2i} \\ u_{2i+1} \end{matrix} )

implies z_{0} is equivalent to z_{i}. The argument of z_{i}’s (being the angle between successive remainders) strictly increases with i. This proves the z_{i}’s are pairwise distinct. Hence |S′| = ⌊(k−1)/2⌋. Finally, if z = u/v ∈ S′, we have that

Im(z) = \frac{⟨uı, v⟩}{|v|^{2}}.

By the previous lemma, |Im(z)| > γ where we define γ = \sqrt{1 − α^{2}}. Also,

Re(z) = \frac{⟨u, v⟩}{|v|^{2}}.

Then 0 ≤ Re(z) < 1 because (u, v) is admissible. The classical result requires |Re(z)| ≤ 1/2. But each z ∈ S′ is equivalent to a point z − 1 with |Re(z − 1)| ≤ 1/2. Hence by replacing each z with z − 1, we get a new set S satisfying the conditions of the classical result. Moreover, |S| = |S′|. We conclude |S′| ≤ C′(γ). Hence k is bounded. Q.E.D.

§5. Symmetric floor and ceiling  Lecture VIII  Page 12

Exercise 4.1: Construct a family of coherent remainder sequences that has lengths that are as long as possible. (cf. [9])

§5. Symmetric floor and ceiling

This section is mainly technical. It introduces the symmetric floor and ceiling functions and derives some elementary bounds.

Define for this lecture, the double norm function,

∥u∥:= log_{2} |u|, u ∈ .

The symmetric floor ⌊x⌋_{s} for a real number x is given by ⌊x⌋ if x ≥ 0 and ⌈x⌉ if x < 0. Similarly we have the symmetric ceiling ⌈x⌉_{s}, where ⌈x⌉_{s} = ⌈x⌉ for x ≥ 0 and ⌈x⌉_{s} = ⌊x⌋ if x < 0. We extend the symmetric floor and ceiling functions to a complex number u = u_{x} + ıu_{y} ∈ :

⌈u⌉_{s} := ⌈u_{x}⌉_{s} + ı⌈u_{y}⌉_{s},
⌊u⌋_{s} := ⌊u_{x}⌋_{s} + ı⌊u_{y}⌋_{s}.

Note that

|⌊u⌋_{s}| ≤ |u| ≤ |⌈u⌉_{s}| , u ∈ .

We introduce the corresponding in-fix notations. For u, b ∈ ,

u divf b := ⌊u/b⌋_{s},
u divc b := ⌈u/b⌉_{s},
u modf b := u − b⌊u/b⌋_{s},
u modc b := u − b⌈u/b⌉_{s}.

The following elementary bounds will be useful:

Lemma 11 Let u ∈ and 0 ≤ m ≤ ∥u∥.

i) ∥u divc 2^{m}∥ = ∥u∥ − m + δ, where 0 ≤ δ < 1.

ii) Let 0 ≤ m ≤ ∥u∥ − 2. Then ∥u divf 2^{m}∥ = ∥u∥ − m − δ, where 0 ≤ δ < \frac{1}{2}.

iii) ∥u modc 2^{m}∥ < m + \frac{1}{2}.

iv) ∥u modf 2^{m}∥ < m + \frac{1}{2}.

v) If ∥u∥ ≥ ∥v∥ then ∥u divc 2^{m}∥ ≥ ∥v divf 2^{m}∥.

Proof. Parts iii), iv) and v) are easy. The lower bound in i) and upper bound in ii) are also easy. As for the upper bound in i) and lower bound in ii),

|u divc 2^{s}|^{2} < 2^{−2m}[(|u_{x}| + 2^{m})^{2} + (|u_{y}| + 2^{m})^{2}]

§6. Regular Matrices  Lecture VIII  Page 13

≤ 2^{−2m}[|u|^{2} + 2^{m}(|u_{x}| + |u_{y}|) + 2^{2m}]
≤ 2^{−2m}[4|u|^{2}],
|u divf 2^{s}|^{2} > 2^{−2m}[(|u_{x}| − 2^{m})^{2} + (|u_{y}| − 2^{m})^{2}]
≥ 2^{−2m}[|u|^{2} − 2^{m}(|u_{x}| + |u_{y}|)]
≥ 2^{−2m}[|u|^{2}/2].

Taking logarithms to base 2, we get the result. Q.E.D.

Lemma 12 Let u, v, a, b ∈ .

i) ∥u∥ ≤ ∥v∥ + 3 implies ∥u + v∥ = ∥u∥ + ϵ where −0.19 < log_{2}(7/8) ≤ ϵ ≤ log_{2}(9/8) < 0.17.

ii) ∥a + b∥ ≥ ∥b∥ + 3 implies ∥a∥ = ∥a + b∥ + ϵ where −0.19 < log_{2}(7/8) ≤ ϵ ≤ log_{2}(9/8) < 0.17.

Proof. i) We note that |u + v|^{2} = |u|^{2} + |v|^{2} + 2⟨u, v⟩. Hence

|u + v|^{2} ≥ |u|^{2} + |v|^{2} − 2|u| · |v| = (|u| − |v|)^{2} ≥ (7|u|/8)^{2}.

Similarly,

|u + v|^{2} ≤ |u|^{2} + |v|^{2} + 2|u| · |v| = (|u| + |v|)^{2} ≤ (9|u|/8)^{2}.

ii) Apply part i) with u = a + b and v = −b, so a = u + v. Q.E.D.

§6. Regular Matrices and the Half-Gaussian Algorithm

We use the matrix notation of Lecture II to describe the algorithm. In fact, there will be considerable parallel in the integer HGCD algorithm and what we now present. But there are technical problems to overcome.

Thus, an elementary matrix is one of the form ( \begin{matrix}q & 1 \\ 1 & 0 \end{matrix} ) where q ≥ 1 is a positive integer,

denoted ⟨q⟩. A regular matrix is a finite product M = ⟨q_{1}⟩⟨q_{2}⟩ ⋯ ⟨q_{k}⟩ of zero or more elementary matrices, denoted M = ⟨q_{1}, q_{2},…, q_{k}⟩. (We note the notational ambiguity with scalar product when k = 2.) We say M transforms a pair (u, v) to (u′, v′) if

( \begin{matrix}u \\ v \end{matrix} ) = M ( \begin{matrix}u′ \\ v′ \end{matrix} )

which we also write as a “derivation”

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{M} ( \begin{matrix}u′ \\ v′ \end{matrix} ) .  (3)

A vector ( \begin{matrix}u \\ v \end{matrix} ) or pair (u, v) is said to straddle a real number r if ∥u∥ ≥ r > ∥v∥. A vector

( \begin{matrix}u \\ v \end{matrix} ) is said to be coherent, admissible, etc, if the pair (u, v) is coherent, admissible, etc. The

derivation in equation (3) is called a reduction if M is regular, (u, v) and (u′, v′) are admissible. The following fact is a key element of our approach.

§7. Development  Lecture VIII  Page 14

Lemma 13 (Reduction Lemma) If (3) represents a reduction, then (u′, v′) is a pair in the coherent remainder sequence of u, v.

Proof. Let M = ⟨q_{1},…, q_{k}⟩, k ≥ 0. We use induction on k. If k = 0, the result is obvious. If k = 1, we use the geometrically obvious fact, that v′ is unique. If k ≥ 2, write

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{⟨q_{1},...,q_{k−1}⟩} ( \begin{matrix}u′′ \\ u′ \end{matrix} ) ⟶^{⟨q_{k}⟩} ( \begin{matrix}u′ \\ v′ \end{matrix} )

where u′′ = u′q_{k} + v′. We check that (u′′, u′) is admissible. Hence we have a reduction from (u, v) to (u′′, u′). By induction, (u′′, u′) is a pair in the coherent remainder sequence of u, v. This implies (u′, v′) is a pair in the same sequence. Q.E.D.

Specification of the Half Gaussian Algorithm. Input to the Algorithm is a pair (u, v) of admissible Gaussian integers. The algorithm is to compute a regular matrix M^{∗} such that if

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{M^{∗}} ( \begin{matrix}u^{∗} \\ v^{∗} \end{matrix} )

then (u^{∗}, v^{∗}) is admissible (unless (u, v) is terminal in which case M^{∗} = E). Furthermore, (u^{∗}, v^{∗}) either is terminal with

∥v^{∗}∥ ≥ \frac{∥u∥}{2} + c

or, (u^{∗}, v^{∗}) straddles ∥u∥/2 + c:

∥u^{∗}∥ ≥ \frac{∥u∥}{2} + c > ∥v^{∗}∥.

Here c is a sufficiently large integer constant. Although we will assume c = 4 in the sequel, we shall keep this constant explicit in our derivations, to show where this slack is needed.

As in Lecture II, we conlude that if we can construct a Half-Gaussian algorithm with running time Θ(M_{B}(n) log n) then we can construct the full algorithm to compute a shortest basis in the same time complexity. Hence, we focus on the Half-Gaussian problem.

§7. Development of the Half-Gaussian Algorithm

In order to recursively solve the Half Gaussian Algorithm, we set up a slightly more general situation. Assume we are given a pair (u, v) of Gaussian integers that is admissible but nonterminal. But we are also given an integer m such that

8 ≤ m ≤ n,  where n:= ∥u∥.  (4)

Our goal is to compute the regular matrix M^{∗} such that

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{M^{∗}} ( \begin{matrix}u^{∗} \\ v^{∗} \end{matrix} )

such that (u^{∗}, v^{∗}) is admissible. Furthermore, (u^{∗}, v^{∗}) either forms a terminal pair satisfying

∥v^{∗}∥ ≥ n − \frac{m}{2} + c  (5)

or straddles n − (m/2) + c:

∥u^{∗}∥ ≥ n − \frac{m}{2} + c > ∥v^{∗}∥.  (6)

We shall call equation (6) the “straddling case” and equation (5) the “non-straddling case”.

In order to compute such a M^{∗}, we first break up u, v thus

( \begin{matrix}u_{0} & u_{1} \\ v_{0} & v_{1} \end{matrix} ):= ( \begin{matrix}u divc 2^{n−m} & u modc 2^{n−m} \\ v divf 2^{n−m} & v modf 2^{n−m} \end{matrix} ) .  (7)

Applying lemma 11, we see

∥u_{1}∥ < n − m + \frac{1}{2}  (8)
∥v_{1}∥ < n − m + \frac{1}{2}  (9)
∥u_{0}∥ = m + δ, (0 ≤ δ ≤ 1)  (10)
≥ ∥v_{0}∥.  (11)

Lemma 14 Suppose ∥v∥ ≥ n − \frac{m}{2} + c, with u, v strongly coherent. Then (u_{0}, v_{0}) is coherent.

Proof. Now ⟨u, v⟩ = ⟨u_{0}, v_{0}⟩2^{2(n−m)} + B where

B = 2^{n−m}[⟨u_{0}, v_{1}⟩ + ⟨u_{1}, v_{0}⟩] + ⟨u_{1}, v_{1}⟩
|B| < 2^{2(n−m)+1}[|u_{0}| + |v_{0}|] + 2^{2(n−m)+1}
< 2^{2(n−m)+1/2}(2|u_{0}| + \sqrt{2})
< 2^{2(n−m)+(1/2)}2^{m+2+(1/2)} = 2^{2n−m+3}.

Thus ∥B∥ ≤ 2n − m + 3. But u, v are strongly coherent means

∥⟨u, v⟩∥ ≥ ∥u∥ + ∥v∥ − 1 ≥ 2n − \frac{m}{2} + c − 1.

We check that m ≥ 2(7 − c) = 6 (equation (4)) implies ∥⟨u, v⟩∥ ≥ ∥B∥ + 3. By lemma 12(ii), ∥⟨u_{0}, v_{0}⟩2^{2(n−m)}∥ ≥ ∥⟨u, v⟩∥ − 1/2 > ∥B∥. This proves that ⟨u, v⟩ and ⟨u_{0}, v_{0}⟩2^{2(n−m)} has the same sign. So (u_{0}, v_{0}) is coherent. Q.E.D.

Henceforth, assume the conditions of this lemma hold.

In this case, consider a regular matrix M = ( \begin{matrix}p & q \\ r & s \end{matrix} ) such that

( \begin{matrix}u_{0} & u_{1} \\ v_{0} & v_{1} \end{matrix} ) ⟶^{M} ( \begin{matrix}u′_{0} & u′_{1} \\ v′_{0} & v′_{1} \end{matrix} )

where (u′_{0}, v′_{0}) is admissible. Moreover, (u′_{0}, v′_{0}) is either the “non-straddling case” (cf. equation (5)) with

∥v′_{0}∥ ≥ ∥u_{0} − \frac{m}{2} + c,  (12)

or the “straddling case” (cf. equation (6)) with

∥u′_{0}∥ ≥ ∥u_{0}∥ − \frac{m}{2} + c > ∥v′_{0}∥.  (13)

[Note: this is essentially the inductive hypothesis.] Since m ≤ ∥u_{0}∥ ≤ m + 1, this means

∥u′_{0}∥ ≥ \frac{m}{2} + c > ∥v′_{0}∥ − 1.  (14)

Recall that p is an upper bound on the entries of M. Inverting M,

( \begin{matrix}u′_{0} & u′_{1} \\ v′_{0} & v′_{1} \end{matrix} ) = ± ( \begin{matrix}s & −q \\ −r & p \end{matrix} ) ( \begin{matrix}u_{0} & u_{1} \\ v_{0} & v_{1} \end{matrix} ) = ( \begin{matrix}su_{0} − qv_{0} & su_{1} − qv_{1} \\ −ru_{0} + pv_{0} & −ru_{1} + pv_{1} \end{matrix} ) .  (15)

Bounds on ∥u′∥, ∥v′∥. a) First we bound ∥p∥: From u_{0} = u′_{0}p + v′_{0}q we get

∥u_{0}∥ = ∥u′_{0}p∥ + ϵ_{0}, \frac{1}{2} < ϵ_{0} < 1,

since u′_{0}, v′_{0} are assumed to be coherent and |u′_{0}p| ≥ |v′_{0}q|. Thus

∥p∥ = ∥u_{0}∥ − ∥u′_{0}∥ − ϵ_{0}  (16)
≤ m − (\frac{m}{2} + c) − \frac{1}{2}, (by (13)or(12))  (17)
< \frac{m}{2} − c.  (18)

b) Next we upper bound ∥u′_{1}∥ and ∥v′_{1}∥: From u′_{1} = su_{1} + qv_{1}, we get |u′_{1}| ≤ 2|p|2^{n−m+(1/2)},

∥u′_{1}∥ < n − m + ∥p∥ + 2 < n − \frac{m}{2} − c + 2.  (19)

Exactly the same reasoning gives

∥v′_{1}∥ < n − \frac{m}{2} − c + 2.  (20)

c) Now we lower bound ∥u′∥. We see that

∥u′_{0}2^{n−m}∥ ≥ [(m/2) + c] + [n − m] = n − \frac{m}{2} + c.

Comparing this bound to equation (19), the inequality ∥u′_{2}2^{n−m}∥ ≥ ∥u′_{1}∥+3 holds (since c = 4). This yields our desired lower bound for ∥u′∥:

∥u′∥ = ∥u′_{0}2^{n−m} + u′_{1}∥  (21)
= ∥u′_{0}2^{n−m}∥ + ϵ,  (−(1/2) ≤ ϵ < 0.3)  (22)
≥ n − \frac{m}{2} + c − \frac{1}{2}.  (23)

d) We upper bound ∥v′∥. From equation (14),

∥v′_{0}2^{n−m}∥ < [\frac{m}{2} + c + 1] + [n − m] = n − \frac{m}{2} + c + 1.

Comparing this bound to equation (20), the inequality ∥v′_{0}2^{n−m}∥ ≥ ∥v′_{1}∥ + 3 holds, using c = 4. Hence we conclude that

∥v′∥ = ∥v′_{0}2^{n−m} + v′_{1}∥  (24)
= ∥v′_{0}2^{n−m}∥ + ϵ′,  (−(1/2) ≤ ϵ′ ≤ 0.3)  (25)
≤ n − \frac{m}{2} + c + \frac{3}{2}.  (26)

A. STRADDLING CASE: First let us assume (u′_{0}, v′_{0}) is straddling ∥u_{0}∥ − (m/2) + c as in equation (13).

Let M = ⟨q_{1},…, q_{k}⟩ where k ≥ 1.

Our goal is to ensure that the pair (u′, v′) is admissible. We show how toggling or backing up can save the situation. If (u′, v′) is not admissible, it could be either inverted or incoherent. We consider these two possibilities in turn.

A.1. (u′, v′) is inverted. We assume ∥u′∥ ≤ ∥v′∥ and let

u′′:= u′q_{k} + v′.  (27)

Hence

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{⟨q_{1},...,q_{k−1},q_{k}−1⟩} ( \begin{matrix}u′′ \\ u′ \end{matrix} ) ⟶^{⟨q_{k}⟩} ( \begin{matrix}u′ \\ v′ \end{matrix} ) .  (28)

This is the easy case, because we simply backup one step, from (u′, v′) to (u′′, u′). This is justified by the following lemma.

Lemma 15 Assume that u′_{0}, v′_{0} are strongly coherent.

i) ∥v′_{0}∥ ≥ ∥u′_{0}∥ − 1. ii) (u′, v′) is coherent. iii)(u′′, u′) is admissible.

Proof. i) This follows from the equalities ∥v′∥ = ∥v′_{0}∥ + n − m + ϵ (|ϵ| ≤ 1/2) and ∥u′∥ = ∥u′_{0}∥ + n − m + ϵ′ (|ϵ′| ≤ 1/2).

ii) Note that

⟨u′, v′⟩ = 2^{2(n−m)}⟨u′_{0}, v′_{0}⟩ + B′  (29)

where

B′ = 2^{n−m}[⟨u′_{0}, v′_{1}⟩ + ⟨u′_{1}, v′_{0}⟩] + ⟨u′_{1}, v′_{1}⟩
|B′| < 2^{n−m}2^{n−(m/2)+2−c}[|u′_{0}| + |v′_{0}|] + 2^{2n−m+4−2c}
≤ 2^{2n−(3m/2)+4−c}[|u′_{0} + 2^{(m/2)−c}]
≤ 2^{2n−(3m/2)+5−c}|u′_{0}|.

The strong coherence of u′_{0}, v′_{0} implies

∥2^{2(n−m)}⟨u′_{0}, v′_{0}⟩∥ ≥ 2n − 2m − 1 + ∥u′_{0}∥ + ∥v′_{0}∥
≥ 2n − 2m − 1 + (m/2 + c) + (∥u′_{0}∥ − 1)
≥ 2n − (3m/2) − 2 + c + ∥u′_{0}∥.

Comparing the two expressions,

∥2^{2(n−m)}⟨u′_{0}, v′_{0}⟩∥ > ∥B′∥

since 2c > 7. This proves ⟨u′, v′⟩ and ⟨u′_{0}, v′_{0}⟩ have the same sign. iii) First we have the ordering property since ∥u′′∥ = ∥u′q_{k} + v′∥ > ∥u′∥ by coherence of u′, v′. Next we have the coherence property since ⟨u′′, u′⟩ = q_{k}|u′|^{2} + ⟨u′, v′⟩ > 0, again by coherence of u′, v′. Q.E.D.

Then we have to step forward to reach a pair that is terminal pair or straddling n − (m/2) + c. This is can be done with at most 3 steps since ∥u′∥ ≤ ∥v′∥ ≤ n − (m/2) + c + (3/2).

A.2. (u′, v′) is incoherent. We now also assume that (u′, v′) is not inverted. Let

u′′:= u′ + v′.  (30)

We first note:

Lemma 16 (u′′, u′) is coherent.

Proof. We have ⟨u′′, u′⟩ = ⟨u′ + v′, u′⟩ ≥ |u′|^{2} − |u′| · |v′| > 0. Q.E.D.

SUBCASE A.2.1: q_{k} > 1. We apply the toggling transformation to M:

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{⟨q_{1},...,q_{k−1},q_{k}−1⟩} ( \begin{matrix}u′ \\ u′′ \end{matrix} ) ⟶^{⟨1⟩} ( \begin{matrix}u′′ \\ −v′ \end{matrix} ) .  (31)

We consider backing up to (u′, u′′) or perhaps going forward again to (u′′, −v′). There are two possibilities. SUBCASE A.2.1.1: ∥u′∥ > ∥u′′∥. Hence (u′, u′′) is admissible and we can backup to (u′, u′′), in effect replacing M by

⟨q_{1},…, q_{k} − 1⟩.

But we want to obtain a straddling admissible pair. There are two possibilities: if (u′′, v′) is coherent, and recalling (u′, v′) is incoherent, then we see that (u′, u′′) is already a terminal pair. [In fact, u′′ ∈ F(v′).] On the other hand, if (u′′, v′) is incoherent, we can advance from (u′, u′′) to (u′′, −v′). Since ∥v′∥ is upper bounded by n − (m/2) + c + (3/2), in an additional 3 remaindering steps, we obtain a pair that straddles n − (m/2) + c.

SUBCASE A.2.1.2: ∥u′∥ ≤ ∥u′′∥. We get

∥u′′∥ ≥ ∥u′∥ > ∥v′∥

Hence we may toggle,

M ← MT = ⟨q_{1},…, q_{k} − 1, 1⟩

and thus obtain the admissible pair (u′′, −v′). Again, in at most 3 steps, we obtain a pair to straddle n − (m/2) + c.

SUBCASE A.2.2: q_{k} = 1. We consider the following scenario where we backup one or two steps:

( \begin{matrix}u \\ v \end{matrix} ) ⟶^{⟨q_{1},...,q_{k−2}⟩} ( \begin{matrix}u′ + q_{k−1}u′′ \\ u′′ \end{matrix} ) ⟶^{q_{k−1}} ( \begin{matrix}u′′ \\ u′ \end{matrix} ) ⟶^{⟨1⟩} ( \begin{matrix}u′ \\ v′ \end{matrix} ) .  (32)

Again consider two possibilities. SUBCASE A.2.2.1: ∥u′′∥ > ∥u′∥. We just backup one step to the admissible pair (u′′, u′). We note that v′ lies in the region (see Figure 5)

(I) = {z : |z + u′| ≥ |u′|, |z| ≤ |u′|, ⟨u′, z⟩ ≤ 0}.

We also see that u′′ lies in region (II). Hence this subcase is a terminal one (in fact, −u′ ∈ F(v′)).

Figure 5. Subcase 2.1: ∥u′′∥ > ∥u′∥.

SUBCASE A.2.2.2: ∥u′′∥ ≤ ∥u′∥. First note that (u′′, u′) is terminal in this subcase. We backup two steps to the pair (u′ + q_{k−1}u′′, u′′). But first we must make sure that k ≥ 2. This is immediate because if k = 1 then (u′′, u′) = (u, v), contradicting our assumption that (u, v) is non-terminal. We note that ∥u′ + q_{k−1}u′′∥ > ∥u′′∥ since (u′, u′′) is coherent. Also ⟨u′ + q_{k−1}u′′, u′′⟩ > 0. Thus (u′ + q_{k−1}u′′, u′′) is admissible. Refer to Figure 6.

Figure 6. Subcase 2.2: ∥u′′∥ ≤ ∥u′∥.

We now claim that the pair (u′ + q_{k−1}u′′, u′′) is terminal. This is because their coherent remainder is u′ which, by the assumption of this case, causes inversion.

B. NON-STRADDLING CASE: Now let us assume ∥v′_{0}∥ ≥ ∥u_{0}∥ − (m/2) + c as in equation (12).

§8. Half Gaussian Algorithm  Lecture VIII  Page 20

This case is settled by the following.

Lemma 17 If (u′_{0}, v′_{0}) is non-straddling, then (u′, v′) is not α-coherent, for a suitable constant α.

Proof. We know that (u′_{0}, v′_{0}) is terminal which means the angle between u′_{0}, v′_{0} is at least 60^{∘}. Hence

∥⟨u′_{0}, v′_{0}⟩∥ ≤ ∥u′_{0}∥ + ∥v′_{0}∥ − 1
< (∥u′∥ − n + m + 0.17) + (∥v′∥ − n + m + 0.17) − 1,
∥2^{2(n−m)}⟨u′_{0}, v′_{0}⟩∥ < ∥u′∥ + ∥v′∥ − 0.66.

But equation (29) shows that

|⟨u′, v′⟩| < |2^{2(n−m)}⟨u′_{0}, v′_{0}⟩| + B′

where

B′ = 2^{2n−(3m/2)+5−c}|u′_{0}|.

Noting that

∥B′∥ ≤ (∥u′∥ + ∥v′∥ − 0.66) − 2

we conclude that

∥⟨u′, v′⟩∥ < (∥u′∥ + ∥v′∥ − 0.66) + log_{2}(5/4) < ∥u′∥ + ∥v′∥ − 0.33.

Hence if we pick α = 2^{−0.33}, the lemma follows. Q.E.D.

Summary. We have shown that if

( \begin{matrix}u_{0} & u_{1} \\ v_{0} & v_{1} \end{matrix} ) ⟶^{M} ( \begin{matrix}u′_{0} & u′_{1} \\ v′_{0} & v′_{1} \end{matrix} )

where (u′_{0}, v′_{0}) is coherent. If (u′_{0}, v′_{0}) is non-straddling, then (u′, v′) is not α-coherent. Otherwise, it straddles ∥u_{0}∥−(m/2)+c and in a constant number of multiplication steps and remaindering steps, we can produce a regular matrix M^{∗} such that

( \begin{matrix}u_{0} & u_{1} \\ v_{0} & v_{1} \end{matrix} ) ⟶^{M^{∗}} ( \begin{matrix}u_{0}^{∗} & u_{1}^{∗} \\ v_{0}^{∗} & v_{1}^{∗} \end{matrix} )

such that if

( \begin{matrix}u^{∗} \\ v^{∗} \end{matrix} ) = ( \begin{matrix}u_{0}^{∗} & u_{1}^{∗} \\ v_{0}^{∗} & v_{1}^{∗} \end{matrix} ) ( \begin{matrix}2^{m} \\ 1 \end{matrix} )

then (u^{∗}, v^{∗}) is admissible. Moreover, either (u^{∗}, v^{∗}) is terminal with ∥v^{∗}∥ ≥ ∥u∥ − (m/2) + c, or it straddles ∥u∥ − (m/2) + c.

Hence, regardless of whether (u′_{0}, v′_{0}) is straddling or not, we can produce the desired matrix M^{∗} in a constant number of multiplication and remaindering steps. We call this the “fixing up” of M to produce M^{∗}. Moreover, this multiplication and remaindering operations involve numbers of bit size at most ∥u∥ + O(1) = n + O(1). Thus the fixing up takes O(M_{B}(n)) where M_{B}(n) is the bit complexity of multiplying two n-bit binary integers.

§8. Half Gaussian Algorithm

We can now present the Half-Gaussian Algorithm:

Procedure Half-Gaussian: Input: (u, v) that is admissible. Output: regular matrix M^{∗} that transforms (u, v) to

(u^{∗}, v^{∗}) such that (u^{∗}, v^{∗}) is admissible (unless M^{∗} = E) and either straddles (∥u∥/2) + c or is terminal with ∥v^{∗}∥ ≥ (∥u∥/2) + c.

[1] If (u, v) is not strongly coherent, then we return M^{∗} ← E.

[2] Let n ← ⌈∥u∥⌉ and m ← ⌈n/2⌉.

[3] FIRST RECURSION. The goal is to compute a regular M_{1}^{∗} that transforms (u, v) to (u_{1}^{∗}, v_{1}^{∗}) that is either terminal or straddles n − (m/2) + c.

[3.1]If ∥v∥ < n − (m/2) + c or m ≤ 8, then let M_{1}^{∗} ← E and go to step [4]. [3.2]Construct (u_{0}, v_{0}) ← (u divc 2^{m}, u divf 2^{m}). [3.3]Recursively call Half-Gaussian on (u_{0}, v_{0}) to compute M_{1}. [3.4]Fixup M_{1} to M_{1}^{∗} using the above theory.

[4] Let (u, v) be transformed by M_{1}^{∗} to (u_{1}^{∗}, v_{1}^{∗}).

[5] If (u_{1}^{∗}, v_{1}^{∗}) is terminal or straddles n/2, we can return M_{1}^{∗}.

[6] Otherwise, compute the elementary matrix M to transform (u_{1}^{∗}, v_{1}^{∗}) to (v_{1}^{∗}, w_{1}^{∗}) which is renamed (x, y) ← (v_{1}^{∗}, w_{1}^{∗}). Note that ∥x∥ ≥ n/2. If (x, y) straddles n/2, we return the product M^{∗}M.

[7] Let n′ ← ⌈∥x∥⌉ and m′ ← 2(n′ − ⌈∥y∥/2⌉).

[8] SECOND RECURSION. The goal is to compute a regular M_{2}^{∗} that transforms (x, y) to (x_{1}^{∗}, y_{1}^{∗}) that is either terminal or straddles n′ − (m′/2) + c.

[8.1]If ∥y∥ < n′ − (m′/2) + c or m′ ≤ 8, then let M_{2}^{∗} ← E and go to step [9]. [8.2]Construct (x_{0}, y_{0}) ← (x divc 2^{m′}, x divf 2^{m′}). [8.3]Recursively call Half-Gaussian on (x_{0}, y_{0}) to compute M_{2}. [8.4]Again fixup M_{2} to M_{2}^{∗} according to our theory.

[9] FINALLY, it is easy to fixup M_{2}^{∗} to M_{3}^{∗} so that M^{∗} transforms (x, y) to (u′, v′) as specified for this procedure. Return M_{1}^{∗}MM_{3}^{∗}.

The complexity analysis of this procedure is standard, and achieves the bound O(nL^{2}(n)). Again, by another standard calculation, this implies that the problem of computing the shortest 2-sequence of the lattice generated by an input pair of Gaussian integer u, v ∈ [ı] is O(nL^{2}(n)).

References

[1] J. W. S. Cassels. An introduction to the Geometry of Numbers. Springer-Verlag, Berlin, 1971.

[2] J. W. S. Cassels. Rational Quadratic Forms. Academic Press, 1978.

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

[4] L. K. Hua. Introduction to Number theory. Springer-Verlag, 1982.

[5] J. C. Lagarias. Worst-case complexity bounds for algorithms in the theory of integral quadratic forms. Journal of Algorithms, 1:184–186, 1980.

[6] W. Scharlau and H. Opolka. From Fermat to Minkowski: Lectures on the Theory of numbers and its historical development. Undergraduate Textss in Mathematics. Springer-Verlag, New York-Berlin, 1985.

[7] Carl Ludwig Siegel. Lectures on the Geometry of Numbers. Springer-Verlag, 1988. Notes by B. Friedman, rewritten by K. Chandrasekharan, with assistance of R. Suter.

[8] B. Vallée and P. Flajolet. The lattice reduction algorithm of Gauss: an average case analysis. IEEE Foundations of Computer Science, 31:830–839, 1990.

[9] Brigitte Vallée. Gauss’ algorithm revisited. Journal of Algorithms, 12:556–572, 1991.