Minkowski’s Theorem

Armed with basic knowledge about lattices in R^n and volumes, we can define two properties of regions that will later prove crucial. A region is convex if given any two points in the region, all points between them are in the region. More formally, given v1 and v2 in the region, we want av1 + (1-a)v2 to be in the region for every real number a between 0 and 1. A region is symmetric if it’s symmetric about the point 0, i.e. if given v1 in the region, the point –v1 is in the region.

Both of these properties are preserved under linear transformations, defined as maps between vector spaces over the same field such that T(v1 + v2) = T(v1) + T(v2) and T(kv) = kT(v) (for a fixed finite basis, every matrix of the right size defines a unique linear transformation and vice versa). To see why, if S is symmetric, then so is T(S): given T(v) in T(S), v is in S, so –v is in S, so that -T(v) = T(-v) is in S. Similarly, if S is convex, then given T(v1) and T(v2) in T(S), we have aT(v1) + (1-a)T(v2) = T(av1) + T((1-a)v2) = T(av1 + (1-a)v2).

Clearly, every nonempty convex, symmetric region contains 0. Given any v in the region, –v is in the region, so that 0.5v + 0.5(-v) = 0 is in the region. Minkowski’s theorem states more: if L is any lattice in V = R^n such that V/L has volume m, and S is a convex, symmetric region of volume more than m2^n, then S contains a point in L other than 0.

The proof of Minkowski’s theorem relies on the intuition that in certain circumstances, if we compress a region to a region of smaller volume, then two points must be collapsed to the same point. To see why, we take the quotient V/2L, where 2L is the set of all points of the form 2v where v is in L.

If A is a matrix corresponding to the lattice L, then |A| has absolute value m. Then 2A corresponds to 2L, and |2A| = 2^n|A| because 2A is formed by multiplying each one of the n rows of A by 2. So V/2L has volume m2^n, which is smaller than the volume of S. This means that two distinct points of S, say x and y, must be collapsed to the same point in V/2L. In other words, x + 2L = y + 2L, so that xy = 2v for some v in L.

Since S is symmetric, the point –y is in S. Since it’s convex, x/2 + (-y)/2 = (xy)/2 is in S. Since x and y are distinct, (xy)/2 is not zero. Further, since xy = 2v, (xy)/2 = v which is in L.

One Response to Minkowski’s Theorem

  1. […] heuer prices malaysia tag heuer professional tag heuer replica tag heuer sunglasses tag heuer uhren tag heuer usati tag heuer watch tag heuer watch bands tag heuer watches tag heuer […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: