Lattice Theory and Geometry of Numbers
Informally, a lattice is an infinite arrangement of points
spaced with sufficient regularity that one can shift any point
onto any other point by some symmetry of the
arrangement. More formally, a lattice can be defined as a discrete
subgroup of a finite-dimensional vector space (the subgroup is
often required not to lie within any subspace of the vector space, which can
be expressed formally by saying that the quotient of the space by the
lattice is compact).
The simplest and most
commonly-studied example of
a lattice (the "integer grid") is formed by the points all Cartesian
coordinates of which are integers.
Other types of lattices arise in crystallography and in
sphere packing, where they are
used to describe the locations of atoms or spheres.
Lattices are also particularly important in the theory of periodic tilings, since they describe the set of
translational symmetries of a tiling.
- Catalogue of lattices, N. J. A. Sloane, AT&T Labs Research.
See also Sloane's sphere-packing and lattice theory publications.
- Connect the dots.
Ed Pegg asks how many sides are needed in a (self-crossing) polygon,
that passes through every point of an n*n grid.
I added a similar puzzle with circular arcs.
- Crystallographic
topology. C. Johnson and M. Burnett of Oak Ridge National Lab use
topological methods to understand and classify the symmetries of the
lattice structures formed by crystals. (Somewhat technical.)
- Equilateral
triangles. Dan Asimov asks how large a triangle will fit into a
square torus; equivalently, the densest packing of equilateral triangles
in the pattern of a square lattice.
There is only one parameter to optimize, the angle of the triangle to
the lattice vectors; my answer
is that the densest packing occurs when
this angle is 15 or 45 degrees, shown below.
(If the lattice doesn't have to be square, it is possible to get density
2/3; apparently this was long known, e.g. see Fáry,
Bull. Soc. Math. France 78 (1950) 152.)
Asimov also asks for the smallest triangle that will always cover at least
one point of the integer lattice, or equivalently a triangle
such that no matter at what angle you place copies of it on an integer lattice,
they always cover the plane; my guess is that the worst angle is parallel
and 30 degrees to the lattice, giving a triangle with 2-unit sides
and contradicting an earlier answer to Asimov's question.
- Grid subgraphs.
Jan Kristian Haugland looks for sets of lattice points that induce
graphs with high degree but no short cycles.
- Mike Kolountzakis' publications include several recent papers on lattice tiling.
- Lattice pentagons.
The vertices of a regular pentagon are not the subset of any lattice.
- The
no-three-in-line problem.
How many points can be placed in an n*n grid with no three
on a common line? The solution is known to be between 1.5n and
2n. Achim Flammenkamp discusses some new computational results
including bounds on the number of symmetric solutions.
- Polyominoes, figures formed from subsets
of the square lattice tiling of the plane. Interesting problems
associated with these shapes include finding all of them, determining
which ones tile the plane, and dissecting rectangles or other shapes
into sets of them. Also includes related
material on polyiamonds, polyhexes, and animals.
- Russian math olympiad problem on lattice
points.
Proof that, for any five lattice points in convex position,
another lattice point is on or inside
the inner pentagon of the five-point star they form.
- Spiral tilings.
These similarity tilings are formed by applying the exponential function
to a lattice in the complex number plane.
- Triangulations with many different areas.
Eddie Grove asks for a function t(n) such that any n-vertex convex polygon
has a triangulation with at least t(n) distinct triangle areas,
and also discusses a special case in which the vertices are points in a
lattice.
- Untitled,
Forbes Gallery, 1987, Ken Goldberg.
- Voronoi diagrams of lattices.
Greg Kuperberg
discusses an algorithm for constructing the Voronoi cells in a planar
lattice of points. This problem is closely related to some important
number theory: Euclid's algorithm for integer GCD's, continued
fractions, and good approximations of real numbers by rationals.
Higher-dimensional generalizations (in which the Voronoi cells form
zonotopes) are much harder -- one can find a basis of
short vectors using the well-known LLL algorithm, but this doesn't
necessarily find
the vectors corresponding to Voronoi adjacencies. (In fact, according
to Senechal's Quasicrystals and Geometry, although the set
of Voronoi adjacencies of any lattice generates the lattice, it's not
known whether this set always contains a basis.)
From the Geometry Junkyard,
computational
and recreational geometry pointers.
Send email if you
know of an appropriate page not listed here.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
