Lattices, No Cluster Points

No Cluster Points

Consider an integer lattice S in Rn. Let x be a point in S, and suppose other points of S approach x. Subtract x from everything, and 0 becomes a cluster point.

Let b1 through bn be a basis for S. Normally we multiply these basis elements by integers, to create S, but if real numbers are used, the basis defines a linear transformation from Rn onto itself. Let f implement this linear transformation, and let g be the inverse. Both functions are continuous.

The unit ball in Rn is closed and bounded, hence compact. Apply g, and the result is compact, hence closed and bounded. Therefore the preimage of the unit ball, under f, is bounded. It contains a finite number of cubes, a finite number of points with integer coordinates. These map to a finite number of points of S, contained in the unit ball. This holds for a ball of any size. Therefore any bounded region (which can always be placed inside a larger ball) intersects S in a finite set.

If 0 is a cluster point of S, the unit ball intersects S in an infinite set, and that is a contradiction. Therefore S has no cluster points.

Returning to the unit ball, one of the points of S is closest to the origin - call it y. (I'm pretty sure finding y is np complete.) Place a unit ball around any other point x, and the points in that ball are translates of the points about the origin. In other words, x+y is the lattice point closest to x. The minimum distance, from 0 to y, applies throughout the lattice. No two points are closer than |y|, and every point has at least two neighbors |y| distance away, namely x±y.

Since the points of S can be isolated inside spheres of radius ½|y|, they do not approach any other point in Rn.

Conversely, assume a set of points closed under addition and subtraction includes no cluster points. It is enough to say 0 is not a cluster point. Some ball about 0 contains only 0, and so every point of S consumes a finite volume, and a bounded region can only contain a finite number of points from S. This means S does not approach any point in Rn.

Let b1 through bn be a maximal set of linearly independent vectors drawn from S. If this basis spans S then we have a lattice. If it does not span some point x, then translate x so that it lies inside the unit cell, the parallelatope determined by the basis vectors.

Write x uniquely as the sum of aibi, where the coefficients are real numbers in [0,1).

Suppose one of the coefficients, say a1, is irrational. Multiples of x translate back to distinct points in the unit cell, having distinct values for a1. This is an infinite number of points in a bounded set, which is a contradiction. Therefore all the coefficients of x are rational.

Express the coefficients as a1 through an over a common denominator d. In the following, all coefficients are integers, the coefficients are collectively coprime, and each ai is in the range 0 to d-1.

dx = a1b1 + a2b2 + a3b3 + … anbn

Suppose pk divides d and a1. This means there is some other coefficient, say a2, that is not divisible by p, else all coefficients could be reduced. Let g be the gcd of d and a1, and let h = d/g. Divide through by g and find a formula for hx. The first coefficient remains an integer, while some of the other coefficients, such as a2/g, are rational numbers (not integers). Translate hx to the base cell, and the first term drops to 0. In other words, hx lies on the floor of the base cell. In 3 space, x might have been in the middle of the parallelatope, but hx is on the floor, somewhere in the parallelogram.

Repeat the above procedure in a lower dimension. A point not spanned implies another point not spanned, in a sublattice of the original. Eventually we run out of dimensions, and at that point, d is relatively prime to all the coefficients on the right. Let's make this assumption and move on.

dx = a1b1 + a2b2 + a3b3 + … anbn (d and ai coprime)

Since d and a1 are coprime, a1 is invertible mod d. If ca1 = 1 mod d, let y = cx. Translate y back to the base cell, and the first coefficient is 1/d. thus y is an unspanned point in our base cell.

Adjust the basis by replacing b1 with y. Evaluate dy and find b1 plus a linear combination of b2 through bn. In other words, y and b2 through bn span b1. The original lattice is spanned, plus y.

Let's try to picture this with 3 vectors in 3 space. Let b2 and b3 define a rectangle on the floor, with b1 perpendicular to both. This is a simple rectangular lattice. If d = 21, a new unspanned point y lies inside this box, very close to the floor. In fact, 21y lies on the ceiling of this box, or a nearby box in the first layer.

The projection of y onto the floor is not known; it could be near any of the four corners, or close to the middle of the rectangle.

When b1 is replaced with y, a new layer of cells appears. The floor of each cell is unchanged, but the new cells are shorter, and they may be pushed over, relative to the original cells. We have squashed them down and push them around. But here is the key: if a new point z is present in the base cell spanned by y and b2 through bn, then z, or one of its horizontal translates, is in the original cell spanned by b1 through bn. It happens to be near the floor, but that's not important, as long as the new point z implies an unspanned point in our original cell.

If the process of finding new unspanned points continues forever, the original cell based on b1 through bn contains infinitely many points, and this is a contradiction. The process must terminate, and the basis that results generates all of S. Therefore S is a lattice in real space.

Of course S could be a lattice of a subspace of Rn, if the basis has fewer than n vectors.

In summary, S is a lattice of Rn, or a subspace thereof, iff S is closed under addition and subtraction, and the points of S do not approach any point in Rn.

Complex Space

The same result holds for complex space. This is because a lattice in complex space becomes a lattice in real space, and the topology, i.e. the notion of distance, is the same.