7. SYMMETRIC SETS

Up until now we have been looking at lattice polygons. We now extend our investigation to more general sets which are constrained in some way by a lattice. Our lattice will be the integer lattice, unless otherwise stated. It soon becomes clear that for the area to be bounded, we have to add some further condition than ‘not containing any lattice points’. Look at these sets:

Clearly non-convex sets can have infinite area, and even for convex sets the area is not necessarily constrained.

It will be convenient to introduce some new notation. We shall be looking at sets having a simple boundary which determines an interior region (inside) and an exterior region (outside).

An open region (set) will be a region just made up of interior points. A closed region will consist of the interior points and all the boundary points. These definitions will help us to state our discoveries more concisely.

Rather surprisingly, there is a simple result about the areas of not necessarily convex sets. We use A(R) to denote the area of region R, (if such area exists).

Non-Overlap Theorem   Let R_O be an open region which includes O, and suppose a congruent and similarly situated region R_P is placed about each lattice point P. Then if no two of the regions R overlap, A(R) 1.

Looking at the squares at right, the result seems obvious, and you might rightly see this as an extension of the fundamental parallelogram idea for the lattice.

Notice too that although we have drawn the boundaries (it is rather hard not to!) the boundary points do not belong to the open sets. This means, for example, that we could enlarge the squares a little so that they had common boundaries, but the open regions would not overlap (have points in common).

Proof of Theorem Let A denote the area of R_O and let d denote the furthest distance of a boundary point of R_O from O. Consider an n x n square of lattice points with their surrounding regions. These all lie inside an (n + 2d) x (n + 2d) square. We deduce that since the regions do not overlap, the total area of the regions is not greater than the area of this enclosing square. Hence

                       (n + 1)²A     (n + 2d)²,

and so          

                       

In this expression, A and d are fixed, but n can be as large as we please. For the expression to be always true, we require A 1. This completes the proof of the theorem.       

---

We next introduce the idea of symmetry.

We say that our region R is symmetric about O if it is mapped onto itself (left invariant) under a half turn about O.

Another way of saying this is, if P(x, y) belongs to R, then P'(–x, –y) also belongs to R.

Time for an investigation! On a lattice grid, draw a number of convex sets which are symmetric about the origin O, and which contain no other lattice points in their interior. What do you think the maximal area might be? You might like to concentrate on squares, rectangles, and symmetric hexagons. I think the maximal area is:

Check your answer ...

    

              

7. SYMMETRIC SETS

Time for an investigation! On a lattice grid, draw a number of sets which are symmetric about the origin O, and which contain no other lattice points in their interior. What do you think the maximal area might be? You might like to concentrate on squares, rectangles, and symmetric hexagons.

Now here is our main theorem. You have probably conjectured this result already. It was one of the earliest results involving lattice points, being published by the German mathematician Hermann Minkowski [M] (right) in 1896. It became the foundation of a branch of mathematics known as the geometry of numbers. As the name suggests, it is an area where geometry and number theory overlap.

Let L denote the integer lattice.

Minkowski’s Theorem Let R be a convex region with area A, which is symmetric about O.
Then A > 4 implies that R contains points of L other than O.

It is sometimes useful to restate this last sentence in its equivalent contrapositive form:

Then R contains no points of L other than O implies that A 4.

Proof of Minkowski’s Theorem

Let R be symmetric about O and assume A(R) > 4. Let R_O be the set obtained by contracting R about O using a scale factor ¹/₂. The A(R_O ) > 1. Hence by the Non-Overlap Theorem, two of the regions R_P of that theorem overlap. Hence there is a lattice point P such that R_O and R_P overlap.

Let Q be some point in that overlap.

Let Q' be the fourth vertex in the parallelogram OPQQ'. Then Q' belongs to R_O since Q' is to O in R_O as Q is to P in the congruent set R_P.

Let Q" be the reflection of Q' in O. Since R_O is symmetric, Q" belongs to R_O.

Finally, the midpoint of QQ" lies in R_O since R_O is convex. But this midpoint is also the midpoint of OP. We conclude that the lattice point P lies in the original larger region R. Hence R contains a lattice point other than O, and the theorem is proved.

Hardy and Wright [HW] give an alternative proof of this theorem.

Further results

(1) Minkowski’s Theorem is easily generalized to higher dimensions: the inequality for A becomes A > 8 in three dimensions, and more generally, in n dimensions, A > 2 ⁿ. The theorem also holds for a general lattice L, with the inequality becoming A > 4d(L), A > 8d(L), or A > 2 ⁿd(L) respectively, where d(L) is the lattice determinant.

(2) There are various ways of generalizing Minkowski’s Theorem. For example Sawyer [Sa] obtains a result for planar convex sets with a measure of asymmetry. Scott [S1] obtains an analogue for planar convex sets which are not necessarily symmetric, but satisfy a certain boundedness condition. If in E² we constrain the boundary of our convex symmetric set to have a built in degree of curvature, then Melzac [Me] shows that the upper bound on the area A can be reduced from 4.

(3) A rather simpler result is the observation by Scott [S2] that Minkowski’s Theorem continues to hold for a convex planar set which has a chord through the origin which has midpoint at O (that is, is symmetric in O), and which partitions the set into two regions of equal area. This is generalized to 3 dimensions in Scott [S3]. A further curious result in the plane concerns convex sets which are partitioned by the axes into four regions of equal area [S4].

(4) Essentially, Minkowski’s Theorem can be generalized by modifying (a) the convexity condition, (b) the symmetry condition, or (c) the lattice point condition. Scott [S5] gives an overview of these possibilities, together with an extensive bibliography.

(5) George Szekeres [Sz] finds an inequality in the opposite direction. Let P be a parallelogram (in the plane) with O at its centre, but containing no other lattice points. If the side directions are specified, then the maximal value of the area of P satisfies: max A(P) > 2(1 + 1/ 5), and this result is best possible. Ennola [E] extends this result to planar symmetric convex domains to obtain: max A(P) > 12. Szekeres [Sz2] extends his result to three dimensions, obtaining max V(P) > 2 for the corresponding parallelopiped. (Curiously, the extension appears in print before the original problem!) There are probably further results of this type awaiting discovery.

(6) Joseph Hammer [H1] shows that if K is a planar set, centrally symmetric about O, and with A(K) > , then K can be rotated about O so as to contain at least two more lattice points. He obtains similar results when O is the centre of gravity of K, and for rotation about a general interior point. In [H2] he shows that a convex planar set K, symmetric about O, and with P A contains at least four more lattice points. Again, there is a similar result when O is the centre of gravity of K. Sawyer [Sa2] looks for the planar convex set, symmetric about O, and of maximal area, for which there is a rotation about O for which the rotated set contains only the origin.

References

[E] Ennola, V., On the lattice constant of a symmetric convex domain, Journal of the London Mathematical Society, 36 (1961) 135 – 138.

[H1] Hammer, J., On some analogues to a theorem of Blichfeldt in the Geometry of Numbers, American Mathematical Monthly 75 (1968) 157 – 160.

[H2] Hammer, J., Some relatives of Minkowski’s Theorem for 2 dimensional lattices, American Mathematical Monthly 73 (1966) 744 – 746.

[HW] Hardy, G.H., Wright, E. M., An introduction to the theory of numbers, Oxford (Edition 4 1960), page 33.

[Me] Melzac, Z. A., Minkowski’s theorem with curvature limitations, Canadian Mathematical Bulletin 2 (1959) 151 – 158.

[M]  Minkowski, H., Geometrie der Zahlen, Leipzig and Berlin, 1896.

[Sa] Sawyer, D. B., The lattice determinant of asymmetrical convex regions (II), Proceedings of the London Mathematical Society 3 (1955), 197 – 218.

[Sa2] Sawyer, D. B., Lattice points in rotated convex sets, Quarterly Journal of Mathematics Oxford 13 (1962), 221 – 228.

[S1] Scott, P. R., An analogue of Minkowski’s theorem in the plane, Journal of the London Mathematical Society (2) 8 (1974) 647 – 651.

[S2]  Scott, P. R., On Minkowski’s theorem, Mathematics Magazine 47 (5) (1974) 277.

[S3]  Scott, P. R., Convex bodies and lattice points, Mathematics Magazine 48 (2) (1975) 110 – 112.

[S4]  Scott, P. R., A new extension of Minkowski’s theorem, Bulletin of the Australian Mathematical Society 18 (3) (1978) 403 – 406.

[S5]  Scott, P. R., Modifying Minkowski’s theorem, Journal of Number Theory, 29 (1988) 13 – 20.

[Sz] Szekeres, G., On a problem of the lattice plane, Journal of the London Mathematical Society 12 (1937) 88 – 93.

[Sz2] Szekeres, G., Note on lattice points within a parallelopiped, Journal of the London Mathematical Society 12 (1937) 36 – 39.