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 x–y = 2v for some v in L.

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

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Sunday, November 5th, 2006 at 12:54 am and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

[…] 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 […]

This is, to a large extent, a free space. I don't delete comments unless they're spam, viruses, impersonations, etc. Shameless blog-whoring doesn't count as spam, because that would just be hypocritical.

[…] 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 […]