Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.