Lattices, The Intersection of Two Lattices

The Intersection of Two Lattices

The intersection of two lattices is often another lattice, though it might live in a lower dimension.

Here is a rather extreme example. Let 1 generate a lattice in R¹, and let π generate another lattice in R¹. Their intersection is 0. Well this is a lattice, in zero dimensions.

Here is a more typical example. the multiples of 2, and of 3, form two lattices in R¹. Their intersection is the multiples of 6, another lattice in R¹. If R is a ufd, and two lattices in R¹ are generated by x and y, the intersection is a lattice generated by lcm(x,y).

If R is a pid the intersection is always a lattice of some dimension. The intersection is an R submodule of a free module, hence it is free. Tensoring either of the parent modules maps onto Kⁿ. Tensoring with a submodule is not always well behaved, but in this case, since modules are torsion free, the tensor product continues to embed in Kⁿ. The image may be a subspace of Kⁿ, whence the lattice lives in a lower dimension. Thus the intersection of two lattices in Kⁿ, or subspaces thereof, gives a third lattice in Kⁿ, or a subspace thereof.

Shifted Lattices

Two shifted lattices may not intersect at all. If they do, shift both lattices by the point c in common. Now they are based at 0, and the lattices intersect in another lattice. Shift this back to c and find the intersection of the two parent lattices.

Rational Vectors

Suppose two n dimensional lattices comprise rational vectors. Run a linear transform so that one basis becomes the standard orthonormal basis, and its lattice becomes the set of points with integer coordinates. the basis of the second lattice becomes a set of vectors with rational coefficients. These are integer coefficients over a common denominator d. Multiply by d and find n linearly independent vectors from the second lattice that have integer coordinates - thus they also belong to the first. The intersection includes n independent vectors, and is an n dimensional lattice.

Although the intersection is always n dimensional, I don't know of an efficient procedure for building a basis. There may not be one.