Lattices, Sublattice, Covolume, Discriminant

Sublattice

A sublattice of a given lattice is a submodule that is also a lattice. The ring R, and vector space Kn, are common to both the lattice and its sublattice.

The multiples of 7 form a sublattice of the integers within the reals.

Covolume

The covolume of a regular lattice is the determinant of its generators. This is a nonzero element of K.

In Rn, the absolute value of the covolume gives the volume of the base cell, the parallelatope spanned by the generators.

Let T be a regular sublattice of S. Each generator of T is spanned by the generators of S, using elements of R. When representing T in terms of S, each generator becomes a row of n coefficients, taken from R. Do this for all n generators of T and find an n×n matrix P. Given a point in T, described as a linear combination of its generators, multiply by P to find its representation as a point of S.

In K space, the basis of T is P times the basis of S. The covolume of T is the determinant of its basis, which is the determinant of P times the covolume of S.

Index

The index of a sublattice within a larger lattice is the quotient of the two covolumes, which is the determinant of the transforming matrix P, as described above. This is an element of R. In real space, it represents the number of cells of S that fit into a cell of T, although the cells may not pack perfectly. Let's consider an example.

Let S be the unit lattice in the plane, and let T be generated by [2,0] and [1,1]. This is a parallelogram of area 2. You can't place two whole squares inside this parallelogram, but you can if you cut them up and rearrange the pieces.

When S = T

Assume S and T are the same lattice. A transformation P represents the basis of T in terms of the basis of S, while another transformation Q represents the basis of S in terms of the basis of T. The product PQ represents the basis of S in terms of the basis of S. This has to be the identity matrix. Therefore P and Q are inverses, and their determinants are units in R.

With this result in hand, the covolume of a given lattice is well defined, up to associates. A change of basis might multiply the covolume by a unit, but that is all. For instance, if v is one of the vectors in the basis, use -v instead of v, and the covolume is multiplied by -1, which is a unit. This is why we take the absolute value of the covolume of a lattice in real space to get the volume of each cell.

Conversely, assume the index of T in S is a unit. The matrix P that implements the change of basis has an invertible determinant. Use cofactors to find Q, the inverse of P. This is a matrix with elements of R, divided by the determinant of P. This determinant is a unit, hence the matrix lies in R. The vectors of T can be used to span the vectors of S, and the lattices are the same. In summary, a lattice is equal to its sublattice iff the index is a unit, iff the two covolumes are associates in R. The sublattice is merely a change of basis.

After a change of basis, the cell could look quite different, but if it defines the same lattice, it has the same volume. Returning to our squares in the plane, let an alternate representation use the vectors [1,0] and [100,1]. This is an incredibly long and skinny parallelogram, yet it has the same area as the unit square, and defines the same lattice.

Note that the index, which is the quotient of the covolumes, is also well defined, up to a unit.

Lattice Count

Let T be a sublattice of S. The lattice count of T, relative to S, is the number of lattice points of S that lie in any given cell of T. Prove this is well defined by mapping the points of S, in any given cell of T, back to points of S in the base cell of T.

Given a lattice point x taken from S, write it as a unique linear combination of basis vectors in T. In other words, x = c1t1 + c2t2 + c3 t3 + … cntn. Add or subtract whole multiples of t1 through tn, so that the coefficients c1 through cn lie in [0,1). The point x has been translated to a unique point in the base cell. Furthermore, distinct points in the base cell differ by a vector that is not an integer combination of t1 through tn, and cannot be in T. In other words, distinct lattice points in the base cell cannot be translates of each other under T. Hence the number of points of S in any given cell of T is the same, as dictated by the base cell, and the lattice count is well defined.

The points of S in the base cell form the quotient module S/T. Each point represents a coset. The origin represents T.

Remapping the Vector Space

Apply an invertible linear transformation to the entire vector space, and carry the lattice S along with. The new generators are linearly independent, creating a new lattice S′. The covolume of S′ is the covolume of S times the determinant of the linear transformation.

If T is a sublattice of S, carry T along as well, creating T′. Show that T′ is a sublattice of S′, and the index, the ratio of covolumes, is unchanged. Linear maps preserve index.

The representation of a point x in S, as a linear combination of t1 through tn, is unchanged in the image. In other words, x′ = c1t1′ + c2t2′ + … cntn′. We are merely running the original linear equation through the transformation. Therefore a linear transformation preserves the lattice count.

Index Equals Lattice Count

For an integer lattice in real space, the index equals the lattice count.

Apply a linear transformation if necessary, so that the containing lattice is the standard lattice in n space, i.e. the points with integer coordinates. Now each point is associated with a cube in space, a region of volume one. At the same time, the sublattice is spanned by bectors t1 through tn in n space, having integer coordinates. Since points and volume go hand in hand, intuition suggests the number of lattice points in the base cell equals the volume of the base cell, equals the determinant of the vectors t1 through tn that generate the parallelatope. We can prove this by looking at ever larger regions of space.

Each cell of T is closed and bounded, with maximum diameter d. Round d up to the nearest integer.

Let the volume of the cell be w, which is the determinant.

Consider two large cubes, one inside another, centered at the origin. the outer cube has coordinates running from -p to p, where p is a half integer. This has volume h, which is equal to the number of lattice points inside. Move the walls inward by d to find an inner cube, with volume g, and g lattice points inside.

There can be at most h/w complete cells inside the outer cube. There may be less, if some cells poke out the sides. This is an upper bound on the cells within the outer cube.

Remove any partial cells from the outer cube, i.e. any cells that poke out of the walls, and the remaining cells completely cover the inner cube. The volume of these cells adds up to more than g. There are at least g/w cells in the outer cube.

The cells entirely in the outer cube are bounded between g/w and h/w. The lattice points inside the outer cube are bounded between g and h. Taking quotients, the lattice points per cell are bounded between gw/h and hw/g.

For large p, the ratios g/h and h/g approach 1 from either side. The number of lattice points in a cell is an integer, as is w. The ratio is eventually held between w-½ and w+½, and it has to equal w. Thus the number of lattice points in any cell is equal to the determinant of the basis, or the volume of the base cell. The lattice count equals the index.

Another Proof, Elementary Row Operations

Here's a different proof that can be generalized to more situations (besides real space). Start with T rectangular, where ti is an integer multiple of the ith coordinate. The lattice count inside this box is the product over all the lengthss ti, which is the determinant of the diagonal matrix. So far so good.

Given any matrix of vectors, apply elementary row operations, until the matrix becomes diagonal. At each step, the determinant and the lattice count are multiplied by the same factor. At the end, when the vectors define a rectangular box, the lattice count equals the determinant. Retrace your steps, and the same holds for our original lattice T. Let's have a closer look at those steps.

Swapping two rows, i.e. two coordinates, is an elementary row operation that negates the determinant. Thus the determinant does not change, except for a unit. The base cell doesn't change either; it is spanned by the same vectors. We are merely changing the representation of a point x in the base cell, swapping the coefficients along with the vectors. Thus the lattice count has not changed.

Scale a vector by an integer j. Remember that x is in the base cell iff its representation, relative to t1 through tn, produces coefficients between 0 and 1. Now, x will fall into the second lattice iff all the coefficients lie between 0 and 1, except for the designated coefficient, which can lie between 0 and j. Each point in the base cell of the first lattice corresponds to j points in the base cell of the second. The determinant, and the lattice count, are both multiplied by j.

The third elementary row operation subtracts a multiple of one row from another, but I'm going to place a few restrictions on this operation. Suppose two rows have, in the jth column, entries of a and b, and we want to remove b fromm the second row. Multiply the first by b, and the second by a, then subtract the first from the second. The entry has disappeard, and we're on our way to an upper triangular matrix, and then a diagonal matrix. We only need subtract one vector from another.

This operation does not change the determinant. It takes some geometric intuition to see why the lattice count is preserved. Picture two vectors on the floor, spanning a parallelogram. For convenience, let one of the vectors run along the x axis. A third vector rises up at an angle, building a parallelatope. Subtract the first vector, along the x axis, from the third. This slides the roof over to the left, taking the walls along for the ride. Suppose a point x was inside the cell, but after the roof moves, x is now outside the cell. When the right wall slides across x, leaving it out in the cold, the left wall touches the point x-v1, a translate of x. Points leave and enter the moving cell in lockstep. When the shift is complete, the lattice count is the same.

This is easy to visualize, but it relies on continuity, and that doesn't generalize to other rings and fields. To get around this, build a 100% algebraic proof. The roof suddenly snaps into its new position, with no continuity of motion. Let c1 be the original cell and let c2 be the new cell. Some points are in both c1 and c2, and we don't have to worry about those. Some points are in c1-c2, and some points are in c2-c1. Let x lie in c1-c2, and represent x using the basis of c1, and the basis of c2. Call these representations r1 and r2. The entries in r1 and r2 agree, except for the first component. This will differ, depending on the location of x in c1. If x is on the floor, then the first component doesn't change. Thus x is in both c1 and c2. If x is on the ceiling, 1 has been subtracted from the first component. It use to lie in [0,1), and now it lies in [1,2). Thus x is in c1, and not in c2; but its translate, y = x-v1, whose first component starts out in [-1,0), lies in c2, and not in c1.

What if x is somewhere between the floor and the ceiling? Halfway up the parallelatope, halfway along v3, ½ is subtracted from the first component. If the first component of r1 lies in [0,½), then x is in both cells. If this entry lies in [½,1), then x is in c1-c2. No problem, because y is in c2-c1. Similar reasoning holds for any x between the floor and ceiling. Lattice points correspond, and the lattice count, like the determinant, is unchanged.

Each row operation does the same thing to the determinant and the lattice count, therefore the lattice count equals the determinant, which is the covolume of the lattice, or the index of one lattice inside another.

Discriminant

The discriminant of a lattice is the square of its covolume. This is well defined up to squared units. In real space, the discriminant is a positive number.

Shifted Lattice

A shifted lattice is a lattice that has been shifted by a fixed vector in Kn.

The linear transformation of a shifted lattice is another shifted lattice.