Math 254A, UC Berkeley, Fall 2001 (Kedlaya) Problem Set 3: Lattices Due in class Monday, September 17

References. Neukirch, Sections 1.4 and 1.5. For LLL (and in general if you’re interested in algorithms in number theory) see Cohen’s A Course in Computational Algebraic Number Theory, especially Chapter 2. For more on lattices in general, the magnum opus is Sphere Packings, Lattices and Groups by Conway and Sloane.

Please submit any seven of the following problems.

Lattices.

1. Neukirch I.4.1 (modified): Show that a ℤ-submodule Γ of ℝ^{n} is a (complete) lattice if and only if Γ is discrete and ℝ^{n}/Γ is compact.

2. Let a, b, c ∈ ℤ be nonzero, pairwise coprime integers not all of the same sign. Suppose that the equation ax^{2}+by^{2}+cz^{2} ≡ 0 (mod 2|abc|) has a solution with gcd(x, y, z, 2abc) = 1. Show that there exists a subgroup L of ℤ^{3} of index 2|abc| such that for every (x, y, z) ∈ L, ax^{2} + by^{2} + cz^{2} ≡ 0 (mod 2|abc|).

3. (Hasse-Minkowski theorem) In the notation of the previous problem, make ℤ^{3} into a lattice under the norm |(x, y, z)| = |a|x^{2} + |b|y^{2} + |c|z^{2}. Prove that there is a nonzero element (x, y, z) of L satisfying |x| ≤ \sqrt{|bc|}, |y| ≤ \sqrt{|ca|}, |z| ≤ \sqrt{|ab|}, and that in fact this triple is a nonzero solution of ax^{2} + by^{2} + cz^{2} = 0.

The Minkowski space of a number field.

1. Neukirch I.5.2: Show that the convex, centrally symmetric set

X_{t} = {(z_{τ}) ∈ K_{ℝ}| ∑_{τ} |z_{τ}| < t}

has volume Vol(X_{t}) = 2^{r}π^{s} \frac{t^{n}}{n!}, where r and 2s are the numbers of real and complex embeddings.

2. Neukirch I.5.3: Show that in every ideal 𝔞 ≠ 0 of 𝔬_{K} there exists an a ≠ 0 such that

| Norm(a)| ≤ M[𝔬_{K} : 𝔞],

where M = \frac{n!}{n^{n}} (\frac{4}{π})^{s} \sqrt{| Disc(K)|}.

3. Let K be a number field such that | Disc(K)| = 1. Prove that K = ℚ. (Hint: use the previous exercise.)

Interlude: The LLL algorithm. In this section, we describe a constructive version of Minkowski’s lattice point theorem, due to Lenstra, Lenstra and Lovász (LLL). This result gives a weaker bound than Minkowski’s theorem, but yields a highly practical algorithm for finding short vectors in a lattice.

Let v⃗_{1}, …, v⃗_{n} be a basis of the lattice L. Let w⃗_{1}, …, w⃗_{n} be the Gram-Schmidt orthogonalization of this basis; namely, w⃗_{1} = v⃗_{1} and

w⃗_{i} = v⃗_{i} − ∑_{j=1}^{i−1} \frac{v⃗_{i} · w⃗_{j}}{w⃗_{j} · w⃗_{j}} w⃗_{j}.

(Note that the w⃗_{i} will not necessarily lie in L itself, only in the real vector space L ⊗_{ℤ} ℝ.) Put μ_{i,j} = (v⃗_{i} · w⃗_{j})/(w⃗_{j} · w⃗_{j}) for 1 ≤ j < i ≤ n. We say the basis is LLL-reduced if

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

and

|w⃗_{i} + μ_{i,i−1}w⃗_{i−1}|^{2} ≤ \frac{3}{4}|w⃗_{i−1}|^{2}  (2)

for i = 2, …, n.

1. Let v⃗_{1}, …, v⃗_{n} be an LLL-reduced basis of the lattice L. Prove that

Vol(L) ≤ ∏_{i=1}^{n} |v⃗_{i}| ≤ 2^{n(n−1)/4} Vol(L)

|v⃗_{j}| ≤ 2^{(i−1)/2}|w⃗_{i}| 1 ≤ j < i ≤ n

|v⃗_{1}| ≤ 2^{(n−1)/4} Vol(V)^{1/n}.

2. Let v⃗_{1}, …, v⃗_{n} be an arbitrary basis of the lattice L, and set k = 2. Show that the following algorithm necessarily terminates, and that the resulting basis is LLL-reduced.

(a) For i = 2, …, n, replace v⃗_{i} by itself plus a suitable linear combination of v⃗_{1}, …, v⃗_{i−1} so that |μ_{i,j}| ≤ 1/2 for j < i.

(b) If (2) holds for i = 2, …, n, stop. Otherwise, choose the smallest i for which (2) fails, then switch v⃗_{i−1} and v⃗_{i} and go back to (a).

(Hint: consider how the quantity ∏_{i=1}^{n} |w⃗_{i}|^{n−i} changes.)

3. Write a Magma program to convert an arbitrary basis of a lattice into an LLL-reduced basis. Your program should also call the built-in Magma function to perform LLL reduction and compare answers.

4. Suppose you are given an LLL-reduced basis v⃗_{1}, v⃗_{2}, v⃗_{3} of a rank 3 lattice. Give an algorithm for finding the shortest nonzero vector in the lattice. (Hint: you can write down a finite list of linear combinations of basis vectors such that the shortest vector must appear in this list.)