EXPERIMENTAL MATHEMATICS – TUTORIAL 3
1. Lattices
Write a function lattice2d which takes as input (v1,v2,range1,range2) (where v1 and
v2 are vectors, typically 2d vectors) and returns a list of the points in the lattice with basis
{v1, v2} whose first coefficient (i.e., the coefficient of v1) is in the range range1 and the
second is in the range range2.
Note that Macaulay2 distinguishes between vectors and lists: one can go back and forth
between the two using vector and entries.
Experiment with your function and the square lattice (basis (1, 0) and (0, 1)). In Macaulay2
you can use
needsPackage "VectorGraphics";
listPlot(L,Join=>false)
to visualize the list L of points.
Try a couple more lattices.
Compare the plots for lattice2d for the lattices given by
• (1, 0) and (0, 1), both ranges -2..2
• (2, 3) and (3, 5), both ranges -20..20
You may want to restrict the viewing window for the second plot; in Macaulay2,
listPlot(L,Join=>false,ViewPort=>{vector{-2,-2},vector{2,2}})
Repeat the previous exercise, this time with triplets of vectors (in three, or possibly higher,
dimensional space).
1
2 EXPERIMENTAL MATHEMATICS – TUTORIAL 3
2. LLL part 1
Reproduce the LLL calculation from Example 5 in the lecture notes.
In Example 5, check that the first column b1 is indeed a shortest nonzero vector in the
lattice.
Now check that the second column b2 is a shortest lattice element not in SpanZ(b1).
Is the third column b3 a shortest lattice element not in SpanZ(b1,b2)?
3. LLL part 2 To get a better sense of how the LLL algorithm works, we’re going to reimplement
it from scratch. Here’s the pseudo-code version:
Input : {b1,b2, . . . ,bn} (as a matrix)
Repeat two steps unti l LLL reduced basis found :
Step 1: Gram−−Schmidt−l ike orthogonalization
for i = 1 to n do
for j = i− 1 to 1 do
m ← nearest integer of µij = bi·b
∗
j
b∗j ·b∗j
bi ← bi −mbj
Step 2: Check condition 2 and swap
for i = 2 to n do
i f ‖b∗i + µi,i−1b∗i−1‖2 < 34‖b∗i−1‖2 then
swap bi−1 and bi
go back to step 1
Output {b1,b2, . . . ,bn} (as a matrix)
Note that Macaulay2 distinguishes between matrices and nested lists: one can go back
and forth between the two using matrix and entries.
A suggestion of how to implement Gramm-Schmidt orthogonalization, which is needed for
step 1, is given in tutorial3-GS.m2.
Check that your implementation produces the same result as the built-in function on the
example of the lectures.
EXPERIMENTAL MATHEMATICS – TUTORIAL 3 3
4. Recognizing algebraic numbers
(if time permits)
An algebraic integer is a root α of a monic polynomial with integer coefficients:
f(α) = 0, f(x) = xn + an−1xn−1 + · · ·+ a1x+ a0, ai ∈ Z.
Given an algebraic integer α, its minimal polynomial is the monic integer polynomial f of
smallest degree d such that f(α) = 0. We refer to d as the degree of α.
For instance, α =
√
2 has minimal polynomial x2 − 2.
Suppose you have a real number α and you think it might be an algebraic integer of degree
d. Reduce the problem of finding the minimal polynomial of α to an instance of the integer
relation problem.
Apply your strategy from the previous exercise to find the minimal polynomial for
α = 1 +
√
1 +
√
1 +
√
2,
which seems like it might have degree ≤ 8, doesn’t it?
Let H = {z ∈ C | =(z) > 0}. The Dedekind eta function η : H → C is defined by
η(z) = q1/24
∞∏
n=1
(1− qn), q = e2piiz
Consider the number
α =
η2
(√−5/2)
2η2
(
2
√−5)
Figure out whether α may be algebraic. If yes, what is its minimal polynomial (and
degree)?
Figure out whether pi (yes, the pi) is algebraic. If yes, what is its minimal polynomial
(and degree)?