The Minkowski Bound

Since Ben is being frivolous I’m going to try to pick up the math blogging. I’m finally back in Berkeley (after a delightful afternoon at coblogger David’s new apartment in Boston).

The last week at Mathcamp I taught a class on quadratic imaginary number theory. While preparing for this class (and with a bunch of hints from Jared Weinstein) I finally understand the relationship between two “different” uses of Minkowski’s theorem in elementary algebraic number theory. Warning, this is a bit detailed for a blog post.

The first use appears on the Ross problem sets. We want to show that any rational integer p for which -1 is a quadratic residue modulo p is of the form a^2+b^2. Since -1 is a quadratic residue, there exists x such that x^2+1 =0 \mod p. So look at the lattice of points (a,b) = (1,x) \mod p (where the congruence is componentwise). It is easy to see that for any lattice point here we have p \mid (a^2+b^2). In order to get a^2+b^2=p we need only find a nonzero lattice point inside the circle a^2+b^2 < 2p. Since the area of this circle is 2 \pi p while four times the are of the fundamental domain is 4p, Minkowski’s theorem guarantees the existence of such a lattice point.

The other use of Minkowski’s theorem I had in mind is the famous Minkowski bound. The usual statement of this (for quadratic imaginary number fields) is that in the ring of integers R of the number field \mathbb{Q}(\sqrt{d}) any ideal class contains an ideal of norm smaller than B (where B is \sqrt{d}/\pi up to an annoying factor of 2). I didn’t want to talk about ideal classes, but if you restrict your attention to trying to distinguish number rings with unique factorization, then you can use a more elementary statement of the Minkowski bound. Namely, if every rational prime smaller than B factors into primes (not just irreducibles) in R, then R has unique factorization. (That is, if every ideal of small norm is principle, then all ideals are principle.)

Let’s relate this to the previous use of Minkowski’s theorem. First we need some way to see when rational integers factor into a product of primes in R. The number field \mathbb{Q}(\sqrt{d}) is the splitting field of some polynomial f (either f=x^2+d or f=x^2 + x + (1-d)/4). Let z be a root of f. Since, \mathbb{Z}[z]/p \cong \mathbb{Z}/p[x]/f(x) we see that p is prime in R if and only if f is prime in \mathbb{Z}/p[x]. Since polynomial rings over a field have unique factorization and since f has degree 2, we see that p is prime if and only if f doesn’t have a root in \mathbb{Z}/p.

On the other hand, suppose that p has a factor q in R. Then \mathbb{Z}[z]/q is a quotient of \mathbb{Z}[z]/p. Since it is a nontrivial quotient of a ring with p^2 elements it must have p elements, and is thus a field. Hence q is prime.

Combining the last two paragraphs we see that, in order to prove unique factorization in R we need only show that if f has a nontrivial root in \mathbb{Z}/p then p is the norm of something in R. This is again a question about finding a certain nonzero lattice point. We again build a lattice of points with p \mid N(a+bz). However, we cannot guarantee a lattice point of norm smaller than 2p anymore, since d could be large.

Here induction saves the day! Suppose that p is the smallest rational prime causing a problem. Now suppose that we have a lattice point with N(a+bz) = kp for k smaller than p. Since k is smaller than p, we see that k factors as a product of primes in R. With a little work this actually implies that there is another element whose norm is p (basically you cancel out the prime factors of k from both sides). Hence, we only need to find a lattice point with N(a+bz) < p^2. Now the area of the ellipse grows quadratically, while the area of the fundamental domain grows linearly. Hence if the first problem p is larger than the Minkowski bound then there’s no problem at all!

Explicitly, suppose that f = x^2 + d, then the area of the ellipse is \pi p^2 / \sqrt{d} while the area of the fundamental domain is 4p. Thus, the Minkowski bound is \sqrt{d} / \pi. The formula in the other case is not much trickier.

9 thoughts on “The Minkowski Bound

  1. Is the Minkowski bound really the right optic here?

    Trivially if x^2 + y^2 = p then (-1/p) = 1; on the other hand, if (-1/p) = 1 then by elementary considerations there exists a quadratic form of discriminant -4 that represents p. (If m^2 + 1 = kp, take px^2 +2mxy + k y^2.) Now the fact that Q(i) has class number 1 intervenes: our second quadratic form of discriminant -4 must be equivalent to the form x^2 + y^2, so the latter represents p as well.

    This is quite general. If D is a negative discriminant, there is a quadratic character such that every prime represented by a positive definite binary quadratic form of discriminant D is in the kernel of the quadratic character. Conversely every prime in the kernel of the quadratic character is shown (in the same elementary manner as above) to be represented by some form of discriminant D. Therefore when the class number h(D) = 1, so that all forms of discriminant D are equivalent, every such form represents every prime in the kernel of the quadratic character.

    Now that these two phenomena (class number 1, and quadratic forms representing everything passing a congruence test) can be seen to be directly related, it’s not so surprising when a Minkowski-type bound can be used to show for a particular discriminant that one or the other of them obtains.

  2. Noah, can you do me a big favor and submit this to the 15th carnival of mathematics, to be hosted in a week on I’ve heard complaints about the fact that too much of the material submitted lately is high school-level, and personally I think the more algebraic number theory it has, the better.

  3. I certainly didn’t mean to imply that there was anything deep or surprising going on here. Just that I hadn’t seen before how close the use of the Minkowski bound echoes the other uses of Minkowski’s theorem that I was more familiar with. Perhaps it wasn’t totally necessary for me to go into details on why “these two phenomena (class number 1, and quadratic forms representing everything passing a congruence test)… are related.” But I did want to explain that it was elementary and didn’t require understanding ideals or the class group. The heart of this post was intended to be the fact that Minkowski’s theorem actually comes in in the same way for the two arguments.

  4. Oh, I know… I’ve even seen that connection before, although without a proof (it’s in a book by Davenport about number theory that introduces this whole theory without ever invoking number fields). But it’s fairly obscure, and almost all other number theory textbooks I’ve seen gloss over it, saying nothing about Minkowski theory except for proving the lattice point and linear forms theorems. Chances are, it’s going to be reasonably challenging to the grad students who read the carnival.

  5. Er, my comment was a reply to Dave Savitt’s comment. I have to admit I don’t understand how this carnival thing works. Why do I have to submit a post? I mean linking is free, I don’t have to give permission for someone to link.

  6. Noah, I think the idea is that the organizer of the carnival should not have to scan the entire mathematics blogosphere for entries, but rather to have them suggested. The blogosphere is just too big for people to try to do carnivals just based on their own reading.

  7. That makes sense, but then shouldn’t people be allowed to nominate other people’s posts? It seems conterproductive to have Alon have to go commenting here and at the everything seminar and whereever else, instead of just nominating them himself.

Comments are closed.