3
$\begingroup$

In Artin's Algebra he presents a method (that I am sure I am butchering) for classifying ideals of a given lattice $\mathbb{Z}[\sqrt{-d}]$ by taking any ideal $I$, choosing an element of minimum norm $\alpha$, drawing a rectangle with points $0,\ \alpha, \ \alpha\sqrt{-d}, \ \alpha + \alpha \sqrt{-d}$, drawing circles of radius $|\alpha|/n$ about the half-lattice points and radius $\alpha$ on the vertices of the rectangle (lattice points), and then applying a theorem that if the circles cover the rectangle, any other element not in the ideal $(\alpha)$ has to be in the half-lattice points.

What is the motivation for this argument, and what is the general method for choosing the right $n$ to cover the rectangle? (Is it bad if $n$ is too big and I use more circles than necessary?)

Edit: And why is the other element not in the $1/n$th lattice points?

1 Answers 1

1

This argument exploits the ordering that the Norm puts on the ideals of a given order (lattice), and the fact that the rectangle you described defines a sublattice of finite index. It might be useful, for purposes of this algorithm, to think about all the algebraic numbers in a given lattice as modulo the sublattice you described.

Consider the example of $d = 5$ and $\alpha = 1$. If you put a circle of radius 1 around the points in the lattice generated by 1 and $\sqrt{-5}$, you will not cover the half-integer $\beta = \frac{1}{2} + \frac{\sqrt{-5}}{2}$. How big of a circle should we draw to cover the remaining part of the fundamental parallelogram? That is, how should we choose $n$? That is an analysis question. We should maximize $n$ to limit any searches over the half-integer points. There are less half-integer points than third-integer points, fourth-integer points, etc., thus we use half-integer points in the algorithm to keep its runtime small.

We cannot let $n$ get arbitrarily large. Note if we consider the ideal generated by $\frac{1}{4}$, the circle centered at $\beta$ of radius $\frac{1}{8}$ will not cover every element of the ideal.