Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 1, 153-161.

On a Hadwiger-Wills Inequality Concerning Lattice Points

Krzysztof Kołodziejczyk^{∗}

Institute of Mathematics, Wrocław University of Technology Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland e-mail: kolodz@im.pwr.wroc.pl

Abstract. There is an interesting inequality due to Hadwiger and Wills which shows that the difference between the number of lattice points in a given planar lattice polygon and the number of lattice points in its translate by an arbitrary vector whose coordinates are not both integers is always greater than or equal to the Euler characteristic of the polygon. In this note we give a few comments on the inequality when planar lattice polygons are replaced by higher dimensional integral polyhedra. Moreover we check the validity of the inequality in the case of planar H-polygons. MSC 1991: 52B20, 52B11, 11H06

1. Introduction and notation

Let ℤ^{N} denote the fundamental lattice of points with integer coordinates in ℝ^{N}. Elements of ℤ^{N} are called lattice points. We say that a simplex Δ ⊂ ℝ^{N} is a lattice simplex if all its vertices belong to ℤ^{N}. A lattice simplex Δ is called fundamental if Δ ∩ ℤ^{N} consists only of the vertices of Δ (fundamental lattice 1-simplexes are simply called lattice segments). A set P ⊂ ℝ^{N} is said to be a polyhedron, if P is the underlying point set of a simplicial cell complex. A polyhedron P is called lattice or integral if all its vertices (0-simplexes) lie in ℤ^{N}. Any lattice polyhedron P can be represented as the union P = ⋃_{i=1}^{m} Δ_{i}, where each Δ_{i} is a fundamental lattice simplex and Δ_{j} \ Δ_{k} ≠ ∅ for j ≠ k (no Δ_{j} is contained in another simplex). By the dimension of a lattice polyhedron P we mean the number

∗Research partially supported by KBN Grant 2 P03A 008 10.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

dim P = max{dim Δ_{i} : i = 1, …, m}.

Any 2-dimensional lattice polyhedron will be called a lattice polygon. In spaces ℝ^{N}, N ≥ 3, we will however be distinguishing between planar (lying in a plane) and nonplanar lattice polygons.

The central notion in this note is the lattice point enumerator G, a functional that associates with a given subset S of ℝ^{N} the number card (S ∩ ℤ^{N}). Thus

G(S) = card (S ∩ ℤ^{N}).

There are many interesting results and problems dealing with lattice points, lattice polyhedra and lattice point enumerator. For more information about these subjects we refer the reader to the following sources [1], [2], [5] and [7]. Among other things in [1] and [7] the reader can find the following interesting result – due to Hadwiger and Wills [3] – establishing a close connection between the lattice point enumerator and the Euler characteristic χ(P) of a lattice polygon P.

Theorem 1. [3] Let P ⊂ ℝ^{2} be a lattice polygon and t ∈ ℝ^{2} \ ℤ^{2}. Then

G(P) − G(t + P) ≥ χ(P).  (1)

Moreover, for each χ ∈ ℤ there are a lattice polygon P with χ(P) = χ and a vector t ∈ ℝ^{2}\ℤ^{2} such that (1) holds with equality.

A special case of the theorem was previously published by Wills in [6]. In [1] and [7] the authors mention that no analogue of inequality (1) is known in spaces ℝ^{N}, N ≥ 3. The main purpose of this note is to give several remarks and comments on inequality (1) when P is an integral polyhedron in ℝ^{N}, N ≥ 3. This will be done in Section 2. In Section 3 we will discuss a variant of inequality (1) when P is an H-polygon (T -polygon), that is, a polygon with vertices in the set H (resp. T) of vertices of a tiling of the plane by regular hexagons (triangles) of unit area.

2. Inequality (1) for integral polyhedra

We start higher dimensional considerations with two slightly more general forms of Theorem 1.

Proposition 1. Suppose that W ⊂ ℝ^{N} is a planar lattice polygon and t is a vector such that t ∈ ℝ^{N} \ ℤ^{N}. Then

G(W) − G(t + W) ≥ χ(W).

Proof. Take a lattice polygon W lying in a plane π ⊂ ℝ^{N} and t ∈ ℝ^{N} \ ℤ^{N}. Adapting the proof of Theorem 1 we can show that the inequality in question is true for W when t ∈ π.

Suppose now that t ∉ π and denote by π^{∗} the plane t + π. If π^{∗} ∩ ℤ^{N} = ∅ then obviously G(W + t) = 0 and our inequality is satisfied. If π^{∗} ∩ ℤ^{N} ≠ ∅ then take two lattice points x ∈ π and x^{∗} ∈ π^{∗} and put u = x^{∗} − x. Obviously u is a lattice vector and W^{∗} = W + u is a lattice polygon lying in π^{∗}. The vector t^{∗} = t − u is a non-lattice vector in π^{∗}. From the first observation in this proof it follows that for such lattice polygon W^{∗} and non-lattice vector t^{∗} in π^{∗} we have

G(W^{∗}) − G(t^{∗} + W^{∗}) ≥ χ(W^{∗}).

In view of the easily verified relations

G(W^{∗}) = G(W), G(t^{∗} + W^{∗}) = G(t + W) and χ(W^{∗}) = χ(W)

the above inequality becomes

G(W) − G(t + W) ≥ χ(W)

and the proof is complete. □

Proposition 2. If P ⊂ ℝ^{N} is the finite union of pair-wise disjoint planar lattice polygons, then inequality (1) is true for P.

We will use Proposition 1 and the following lemma in our next result.

Lemma 1. If T is a lattice segment or a fundamental lattice triangle in ℝ^{N}, N ≥ 2, then for each t ∈ ℝ^{N} \ ℤ^{N}

G(T + t) ≤ 1.

Proof. In the proof we consider only the case that T is a fundamental lattice triangle. One can use similar reasoning to establish the property for lattice segments.

Suppose on the contrary that for some fundamental lattice triangle

T = conv (x_{1}, x_{2}, x_{3})

and some t ∈ ℝ^{N} \ ℤ^{N} the triangle

T + t = conv (x_{1} + t, x_{2} + t, x_{3} + t)

contains at least two lattice points. Take y_{1}, y_{2} ∈ (T + t) ∩ ℤ^{N}. Thus y_{1} = ∑_{i=1}^{3} α_{i}(x_{i} + t) and y_{2} = ∑_{i=1}^{3} β_{i}(x_{i} + t), where α_{i} ≥ 0, β_{i} ≥ 0 and ∑_{i=1}^{3} β_{i} = ∑_{i=1}^{3} α_{i} = 1. For the points we would have

y_{2} − y_{1} = ∑_{i=1}^{3} β_{i}(x_{i} + t) − ∑_{i=1}^{3} α_{i}(x_{i} + t) =
= ∑_{i=1}^{3}(β_{i} − α_{i})x_{i} + t (∑_{i=1}^{3} β_{i} − ∑_{i=1}^{3} α_{i}) =
= ∑_{i=1}^{3}(β_{i} − α_{i})x_{i}.

The condition ∑_{i=1}^{3} β_{i} = ∑_{i=1}^{3} α_{i} implies that the numbers β_{i} − α_{i} cannot be all of the same sign. So at least one of them must be negative. If only one is negative, say β_{1} − α_{1}, then the point

x_{1} + y_{2} − y_{1} = [1 − (α_{1} − β_{1})]x_{1} + (β_{2} − α_{2})x_{2} + (β_{3} − α_{3})x_{3}

being a convex combination of x_{1}, x_{2}, x_{3} belongs to T. Clearly

x_{1} + y_{2} − y_{1} ∈ T ∩ ℤ^{N} \ {x_{1}, x_{2}, x_{3}}.

This contradicts the fact that T is fundamental.

In the case when two numbers, say β_{1} − α_{1} and β_{2} − α_{2}, are negative the point

x_{3} + y_{1} − y_{2} = [1 − (β_{3} − α_{3})]x_{3} + (α_{1} − β_{1})x_{1} + (α_{2} − β_{2})x_{2}

is a convex combination of x_{1}, x_{2}, x_{3} and therefore belongs to T. This again gives a contradiction and shows that in T +t we can have at most one lattice point. The proof is complete.

□

In connection with Lemma 1 the next question is: How many lattice points can a translate of a fundamental lattice simplex contain, if the translation is not on a lattice vector? It will be illustrated by an example that even in ℝ^{3} such a translate can contain as many lattice points as we wish.

Example 1. In ℝ^{3} let us consider lattice tetrahedra

Δ_{k} = conv {(1, 0, 0), (0, 1, 0), (1, 1, 0), (0, 0, 2k)}, k ≥ 1.

[figure: (\frac{3}{2}, \frac{1}{2}, 0); (\frac{3}{2}, \frac{3}{2}, 0); (\frac{1}{2}, \frac{3}{2}, 0); x; y; z; (\frac{1}{2}, \frac{1}{2}, 2); Fig. 1. Tetrahedron Δ_{1} and its translate upon vector t = (\frac{1}{2}, \frac{1}{2}, 0).]

Of course each Δ_{k} is a fundamental lattice tetrahedron with G(Δ_{k}) = 4 and χ(Δ_{k}) = 1. Take t = (\frac{1}{2}, \frac{1}{2}, 0) ∈ ℝ^{3} \ ℤ^{3}. It is easy to check that

(Δ_{k} + t) ∩ ℤ^{3} = {(1, 1, 0), (1, 1, 1), …, (1, 1, k)}.

So G(Δ_{k} + t) = k + 1 and inequality (1) does not hold for Δ_{k} when k ≥ 3. □

Example 1 makes clear that no generalization of inequality (1) can be expected for Ndimensional lattice polyhedra, N ≥ 3. Therefore in the following we consider only lattice polygons, in particular nonplanar lattice polygons.

The next question appearing in this context is if inequality (1) holds at least for all nonplanar lattice polygons in ℝ^{N}. The following example illustrates that the answer to this question is also negative.

Example 2. Let us consider nonplanar lattice polygons

P_{k} = ⋃_{j=0}^{k}{(x, y, z) ∈ ℝ^{3} : |x| + |y − 2j| = 1, 0 ≤ z ≤ 1}, k ≥ 1.

[figure: x; y; z; Fig. 2. Polyhedron P_{2}.]

It is easy to check that for such nonplanar lattice polygons we have

G(P_{k}) = 6k + 8 and χ(P_{k}) = −k.

[figure: x; y; z; Fig. 3. Polyhedron P_{2} + (\frac{1}{2}, \frac{1}{2}, 0).]

Also easily can be checked that for t = (\frac{1}{2}, \frac{1}{2}, 0) we have

G(P_{k} + t) = 8k + 8.

Apparently inequality (1) is not true for P_{k}. □

But for the nonplanar lattice polygons P_{k} from Example 2 we have

G(P_{k}) − G(t + P_{k}) ≥ 2χ(P).

One can ask if the following inequality G(P) − G(t + P) ≥ 2χ(P) holds for all nonplanar lattice polygons. Again the answer is negative. Theorem 1 implies that there exist a lattice polygon P_{1} ⊂ ℝ^{2} and a vector t^{∗} = (t_{1}, t_{2}) ∈ ℝ^{2} \ ℤ^{2} such that

G(P_{1}) − G(P_{1} + t^{∗}) = χ(P_{1}) > 0.

In ℝ^{3} let us consider the nonplanar lattice polygon

P = (P_{1} × {0}) ∪ [(P_{1} × {0}) + (0, 0, 1)].

Take t = (t_{1}, t_{2}, 0). It can be easily checked that G(P) − G(P + t) = χ(P) = 2χ(P_{1}) > 0. Therefore for such a P we cannot have G(P) − G(t + P) ≥ 2χ(P).

Inequality (1) is true however for a restricted class of nonplanar lattice polygons in ℝ^{N}. A lattice (nonplanar) polygon P is said to be well-decomposed if P can be represented in the form

P = P_{1} ∪ ⋃_{i=1}^{m} T_{i},

where P_{1} is a lattice planar polygon and each T_{i}, i = 1 …, m, is either an isolated lattice point, or a lattice segment, or a fundamental lattice triangle such that the intersections P_{1}∩T_{1} and T_{n} ∩ (P_{1} ∪ ⋃_{i=1}^{n−1} T_{i}), n = 2, …, m, do not contain two lattice segments. It is not difficult to check that the nonplanar lattice polygons from Example 2 do not satisfy the definition.

Theorem 2. Inequality (1) is true for any well-decomposed lattice polygon in ℝ^{N}.

Proof. Let P = P_{1} ∪ ⋃_{i=1}^{m} T_{i} be a well-decomposed lattice polygon in ℝ^{N} and t ∈ ℝ^{N} \ ℤ^{N}. Denote

P_{k} = P_{1} ∪ ⋃_{i=1}^{k−1} T_{i}, k = 2, …, m + 1.

We will check inductively that inequality (1) is true for the polygon P = ⋃_{k=1}^{m+1} P_{k}. The lattice polygon P_{1} lies in a plane π ⊂ ℝ^{N}. From Proposition 1 it follows that inequality (1) is satisfied for P_{1}. So assume now that inequality (1) is true for P_{k} and consider the polygon P_{k+1}. For P_{k+1} the following holds

G(P_{k+1} + t) = G[(P_{k} + t) ∪ (T_{k+1} + t)] =
= G(P_{k} + t) + G(T_{k+1} + t) − G[(P_{k} ∩ T_{k+1}) + t] ≤
≤ G(P_{k} + t) + G(T_{k+1} + t).  (2)

If T_{k+1} is an isolated point then G(T_{k+1} + t) = 0, G(P_{k+1}) = G(P_{k}) + 1 and χ(P_{k+1}) = χ(P_{k}) + 1. In view of the relations and our induction hypothesis, inequality (2) takes the form

G(P_{k+1} + t) ≤ G(P_{k} + t) ≤ G(P_{k}) − χ(P_{k}) ≤ G(P_{k+1}) − χ(P_{k+1}),

which means that inequality (1) is satisfied for P_{k+1}.

Suppose now that T_{k+1} is a lattice segment or a fundamental lattice triangle. From inequality (2), our induction hypothesis, and Lemma 1 we get

G(P_{k+1} + t) ≤ G(P_{k}) − χ(P_{k}) + 1.  (3)

If T_{k+1} is a lattice segment having a, 0 ≤ a ≤ 2, common lattice points with P_{k} then G(P_{k+1}) = G(P_{k}) + 2 − a and χ(P_{k+1}) = χ(P_{k}) + 1 − a. In this case, from inequality (3) we obtain

G(P_{k+1} + t) ≤ G(P_{k}) − χ(P_{k}) + 1 = G(P_{k+1}) + a − 2 − χ(P_{k+1}) − a + 1 + 1 =
= G(P_{k+1}) − χ(P_{k+1})

and inequality (1) is satisfied for P_{k+1}.

Finally let us consider the case that T_{k+1} is a fundamental lattice triangle. Denote by a and b the number of common lattice points and lattice segments in P_{k} ∩ T_{k+1}, respectively. With this notation we simply have

G(P_{k+1}) = G(P_{k}) + 3 − a

and

χ(P_{k+1}) = χ(P_{k}) + b − a + 1.

Taking the above two relations into account we get from inequality (3) the following

G(P_{k+1} + t) ≤ G(P_{k}) − χ(P_{k}) + 1 =
= G(P_{k+1}) + a − 3 − χ(P_{k+1}) + b − a + 1 + 1 =
= G(P_{k+1}) − χ(P_{k+1}) + b − 1.

Since P is well-decomposed we obviously have b − 1 ≤ 0. Using this we get

G(P_{k+1} + t) ≤ G(P_{k+1}) − χ(P_{k+1}).

So, in either of the three possible cases inequality (1) is satisfied for P_{k+1} and the validity of our theorem follows now by induction. □

We end this section with a remark that Theorem 2 is a generalization of Theorem 1 and Proposition 1 since, obviously, any planar lattice polygon is a well-decomposed integral polygon.

3. Inequality (1) for H-polygons

To consider an analogue of inequality (1) for H-polygons we first need to rephrase Theorem 1. Clearly, if we translate a lattice polygon by a vector with integer coordinates then the polygon and its translate have the same number of lattice points. In view of this one can see that Theorem 1 may be rephrased in the following way:

Theorem 1^{∗}. Let P be an arbitrary lattice polygon in ℝ^{2} and P′ its translate. Then we have G(P) − G(P′) = 0 when P′ is a lattice polygon and G(P) − G(P′) ≥ χ(P) otherwise.

The aim of this short section is to show that neither of the statements in Theorem 1^{∗} is true for H-polygons. Here it can happen (see the triangles in Fig. 4) that an H-polygon P and its translate P′ being also an H-polygon can contain a different number of H-points.

[figure: P; P′; Fig. 4; P; P′; Fig. 5]

Fig. 5 illustrates that the other statement of Theorem 1^{∗} is not true either. Let P be the H-polygon consisting of four sides of the rectangle. Its translate P′ is no longer an Hpolygon. Here we have card(P ∩ H) = 4, card(P′ ∩ H) = 6 and χ(P) = 0. Consequently, an analogue of inequality (1) does not hold for H-polygons.

The reason for the failure of inequality (1) in the case of H-polygons seems to be the fact that H is not a lattice. But H is the union of two lattices, whose points can be simply distinguished by means of the hexagonal tiling edges. We will denote one of the two lattices by H^{+} and (if necessary) the second one by H^{−}. All H-points in H^{+} have three tiling edges leaving the vertex in the same three directions, and all points in H^{−} have edges which leave in the three opposite directions, see [4].

With this notation we can comment on both statements of Theorem 1^{∗}. The following two propositions – in which x′ and P′ denote translates of x and P, respectively – can be easily proved.

Proposition 3. If an H-polygon P has a vertex x such that both x and x′ are in H^{+} (H^{−}), then every pair of corresponding vertices y and y′ belongs to the same lattice H^{+} or H^{−} and card(P ∩ H) = card(P′ ∩ H).

Proposition 4. Suppose that all vertices of P lie in H^{+} and P′ is not an H-polygon. Then

card(P ∩ H^{+}) − card(P′ ∩ H^{+}) ≥ χ(P).

Let us notice that without the assumption that all vertices belong to H^{+} Proposition 4 can fail, see again Fig. 5.

Adapting the proof of Theorem 1 one can check that Theorem 1^{∗} remains true when instead of H-polygons we would consider T -polygons.

Acknowledgment. The author would like to thank Jörg M. Wills for the encouragement to look at inequality (1) in the two settings considered in this note.

References

[1] Gritzmann, P.; Wills, J. M.: Lattice points. In: Handbook of Convex Geometry (ed. by P. M. Gruber and J. M. Wills), Elsevier, New York 1993.

[2] Gruber, P. M.; Lekkerkerker, C. G.: Geometry of Numbers. North-Holland, Amsterdam 1987.

[3] Hadwiger, H.; Wills, J. M.: Neuere Studien über Gitterpolygone. J. Reine Angew. Math. 280 (1975), 61–69.

[4] Kołodziejczyk, K.; Reay, J. R.: Primitive and mensurable hex-triangles. Geom. Dedicata 43 (1992), 233–241.

[5] Lagarias, J. C.: Point lattices. In: Handbook of Combinatorics (ed. by R. Graham, M. Grötschel and L. Lovász), Elsevier, New York 1995.

[6] Wills, J. M.: Über konvexe Gitterpolygone. Comment. Math. Helv. 48 (1973), 188–194.

[7] Wills, J. M.: Kugellagerungen und Konvexgeometrie. Jber. d. Dt. Math.-Verein. 92 (1990), 21–46.

Received September 25, 1997; revised version February 9, 1998