A Closer Look at Lattice Points in Rational Simplices ^{1}

Matthias Beck ^{2} Dept. of Mathematics, Temple University Philadelphia, PA 19122

                       matthias@math.temple.edu

Submitted: March 19, 1999; accepted: September 14, 1999

Abstract. We generalize Ehrhart’s idea ([Eh]) of counting lattice points in dilated rational polytopes: Given a rational simplex, that is, an n-dimensional polytope with n + 1 rational vertices, we use its description as the intersection of n + 1 halfspaces, which determine the facets of the simplex. Instead of just a single dilation factor, we allow different dilation factors for each of these facets. We give an elementary proof that the lattice point counts in the interior and closure of such a vectordilated simplex are quasipolynomials satisfying an Ehrhart-type reciprocity law. This generalizes the classical reciprocity law for rational polytopes ([Ma], [Mc], [St]). As an example, we derive a lattice point count formula for a rectangular rational triangle, which enables us to compute the number of lattice points inside any rational polygon.

1 Introduction

One of the exercises on the greatest integer function [x] in an elementary course in Number Theory is to prove the statement

[\frac{t − 1}{a}] = − [\frac{−t}{a}] − 1  (1)

for any integers t, a ≠ 0. Geometrically, this is a special instance of a much more general theme. Consider the interval [0, \frac{1}{a}], viewed as a 1-dimensional rational polytope. (A rational polytope is a polytope whose vertices are rational.) Now we dilate this polytope by an integer factor t > 0, and count the number of integer points (”lattice points”) in the dilated polytope. It is straightforward that this number in the open dilated polytope is [\frac{t−1}{a}], whereas in the closure there are [\frac{t}{a}] + 1 integer points.

More generally, let P be an n-dimensional convex rational polytope in ℝ^{n}. For t ∈ ℤ_{>0}, let L(P^{∘}, t) = # (tP^{∘} ∩ ℤ^{n}) and L(\overline{P}, t) = # (t\overline{P} ∩ ℤ^{n}) be the number of lattice points in the interior of the dilated polytope tP = {tx : x ∈ P} and its closure, respectively. That is, if P denotes the above 1-dimensional polytope, we have

L(P^{∘}, t) = [\frac{t − 1}{a}] and L(\overline{P}, t) = [\frac{t}{a}] + 1 .

1This work is part of the author’s Ph.D. thesis.

Mathematical Reviews Subject Numbers: 05A15, 11D75.

2http://www.math.temple.edu/∼matthias

There are two remarkable features hidden in these expressions: First, we have

Theorem 1 L(P^{∘}, t) and L(\overline{P}, t) are quasipolynomials in t.

A quasipolynomial is an expression of the form c_{n}(t) t^{n} + … + c_{1}(t) t + c_{0}(t), where c_{0}, …, c_{n} are periodic functions in t. Theorem 1 is easily verified for our onedimensional polytope by writing [x] = x − {x}, where {x} denotes the fractional part of x. Moreover, viewing both these quasipolynomials as algebraic expressions in the integer variable t, (1) becomes a reciprocity law:

Theorem 2 L(P^{∘}, −t) = (−1)^{n}L(\overline{P}, t).

Both Theorem 1 and 2 are true for any rational polytope P. The proof of Theorem 1 is due to Ehrhart, who initiated the study of the lattice point count in dilated polytopes ([Eh]). He conjectured Theorem 2, which was first proved by Macdonald (for the case that P has integer vertices, [Ma]), later also by McMullen ([Mc]), and Stanley ([St]).

We generalize the notion of dilated polytopes for rational simplices, that is, rational polytopes of dimension n with n + 1 vertices. We use the description of a simplex as the intersection of n + 1 halfspaces, which determine the facets of the simplex: Instead of dilating the simplex by a single factor, we allow different dilation factors for each facet.

Definition 1 Let the rational simplex S_{A} be given by

S_{A} = {x ∈ ℝ^{n} : A x ≤ b} ,

with A ∈ M_{(n+1)×n}(ℤ), b ∈ ℤ^{n+1}. Here the inequality is understood componentwise. For t ∈ ℤ^{n+1}, define the vector-dilated simplex S_{A}^{(t)} as

S_{A}^{(t)} = {x ∈ ℝ^{n} : A x ≤ t} .

For those t for which S_{A}^{(t)} is nonempty and bounded, we define the number of lattice points in the interior and closure of S_{A}^{(t)} as

L (S_{A}^{∘}, t) = # ((S_{A}^{(t)})^{∘} ∩ ℤ^{n}) and L (\overline{S_{A}}, t) = # (S_{A}^{(t)} ∩ ℤ^{n}) ,

respectively.

Geometrically, we fix for a given simplex the normal vectors to its facets and consider all possible positions of these normal vectors that ’make sense’. The previously defined quantities L(P^{∘}, t) and L(\overline{P}, t) can be recovered from this new definition by choosing t = tb. The corresponding result to Theorems 1 and 2 is Theorem 3 L (S_{A}^{∘}, t) and L (\overline{S_{A}}, t) are quasipolynomials in t ∈ ℤ^{n+1}, satisfying

L (S_{A}^{∘}, −t) = (−1)^{n}L (\overline{S_{A}}, t) .  (2)

A quasipolynomial in the d-dimensional variable t is the obvious generalization of a quasipolynomial in a 1-dimensional variable.

We give an elementary proof of Theorem 3, only relying on (1) and a basic lemma on quasipolynomials. Theorems 1 and 2 follow as immediate corollaries, considering the fact that any polytope can be triangulated into simplices. In fact, the original motivation for Theorem 3 was to construct an elementary proof of Theorem 2.

2 A lemma on quasipolynomials

Lemma 4 Let q(t_{1}, …, t_{m}) be a quasipolynomial, and fix a_{1}, …, a_{m}, c_{0}, …, c_{m}, d ∈ ℤ, d ≠ 0. Then

Q_{1}(t) = Q_{1}(t_{0}, t_{1}, …, t_{m}) = \begin{aligned}[ & \frac{c_{0}t_{0}+...+cmtm−1}{d} & ] \\ & ∑ \\ & k=1 \end{aligned} q (t_{1} + a_{1}k, …, t_{m} + a_{m}k)

and

Q_{2}(t) = \begin{aligned}[ & \frac{c_{0}t_{0}+...+cmtm}{d} & ] \\ & ∑ \\ & k=0 \end{aligned} q (t_{1} + a_{1}k, …, t_{m} + a_{m}k)

are also quasipolynomials.

Remark. Here and in the following we define a finite series ∑_{k=a}^{b} … for both cases a ≤ b and a > b, in the usual way:

∑_{k=a}^{b} … = \{ \begin{matrix}∑_{k=a}^{b} … & if a ≤ b \\ 0 & if a = b + 1 \\ − ∑_{k=b+1}^{a−1} … & if a ≥ b + 2 \end{matrix}  (3)

Proof. We will prove the statement for Q_{2}; the proof for Q_{1} follows in a similar fashion. After writing q in all its terms and multiplying out the binomial expressions, it suffices to prove that

Q_{3}(t) = \begin{aligned}[ & \frac{c_{0}t_{0}+...+cmtm}{d} & ] \\ & ∑ \\ & k=0 \end{aligned} f (t_{1} + a_{1}k, …, t_{m} + a_{m}k) k^{j}

is a quasipolynomial, where j is a fixed nonnegative integer and f is a periodic function in m variables. Consider a period p which is common to all the arguments of f, that is, f (x_{1} + p, …, x_{m} + p) = f (x_{1}, …, x_{m}). To see that Q_{3} is a quasipolynomial, use the properties of f to write it as

Q_{3}(t) = f (t_{1}, …, t_{m}) \begin{matrix}[ & \frac{c_{0}t_{0}+...+cmtm}{dp} & ] \\ & ∑ \\ & k=0 \end{matrix}(kp)^{j}

+ f (t_{1} + a_{1}, …, t_{m} + a_{m}) \begin{matrix}[ & \frac{c_{0}t_{0}+...+cmtm−d}{dp} & ] \\ & ∑ \\ & k=0 \end{matrix}(1 + kp)^{j} +

+ f (t_{1} + 2a_{1}, …, t_{m} + 2a_{m}) \begin{matrix}[ & \frac{c_{0}t_{0}+...+cmtm−2d}{dp} & ] \\ & ∑ \\ & k=0 \end{matrix}(2 + kp)^{j} + … +

+ f(t_{1} + (p − 1)a_{1}, …, t_{m} + (p − 1)a_{m}) \begin{matrix}[ & \frac{c_{0}t_{0}+...+cmtm−(p−1)d}{dp} & ] \\ & ∑ \\ & k=0 \end{matrix}(p − 1 + kp)^{j} .

Upon expanding all the binomials, putting the finite sums into closed forms, and writing [x] = x − {x}, the only dependency on t is periodic (with period dividing dp) or polynomial. □

3 Proof of Theorem 3

We induct on the dimension n. First, a 1-dimensional rational simplex S_{A} is an interval with rational endpoints. Hence S_{A}^{(t)} is given by

\frac{t_{1}}{a_{1}} ≤ x ≤ \frac{t_{2}}{a_{2}} ,

so that we obtain

L (S_{A}^{∘}, t) = [\frac{t_{2} − 1}{a_{2}}] − [\frac{t_{1}}{a_{1}} ] and L (\overline{S_{A}}, t) = [\frac{t_{2}}{a_{2}} ] − [\frac{t_{1} − 1}{a_{1}}] .

These are quasipolynomials, as can be seen, again, by writing [x] = x − {x}. Furthermore, by (1),

L (S_{A}^{∘}, −t) = [\frac{−t_{2} − 1}{a_{2}}] − [\frac{−t_{1}}{a_{1}} ] = − [\frac{t_{2}}{a_{2}} ] + [\frac{t_{1} − 1}{a_{1}}] = −L (\overline{S_{A}}, t) .

Now, let S_{A} be an n-dimensional rational simplex. After harmless unimodular transformations, which leave the lattice point count invariant, we may assume that the defining inequalities for S_{A} are

a_{11}x_{1}  ≤ b_{1}
a_{21}x_{1} + … + a_{2n}x_{n}  ≤ b_{2}
⋮
a_{n+1,1}x_{1} + … + a_{n+1,n}x_{n} ≤ b_{n+1} .

(Actually, we could obtain an lower triangular form for A; however, the above form suffices for our purposes.) Hence there exists a vertex v = (v_{1}, …, v_{n}) with v_{1} = \frac{b_{1}}{a_{11}} and another vertex w = (w_{1}, …, w_{n}) whose first component is not \frac{b_{1}}{a_{11}} . After switching x_{1} to −x_{1}, if necessary, we may further assume that v_{1} < w_{1}. Since w satisfies all equalities but the first one, it is not hard to see that w has first component w_{1} = r_{2}b_{2} + … + r_{n}b_{n} for some rational numbers r_{2}, …, r_{n}; write this number as w_{1} = \frac{c_{2}b_{2}+...+c_{n}b_{n}}{d} with c_{2}, …, c_{n}, d ∈ ℤ. Viewing the defining inequalities of the vector-dilated simplex S_{A}^{(t)} as

\frac{t_{1}}{a_{11}} ≤ x_{1}  ≤ \frac{c_{2}t_{2}+...+c_{n}t_{n}}{d}
a_{22}x_{2} + … + a_{2n}x_{n}  ≤ t_{2} − a_{21}x_{1}
⋮
a_{n+1,2}x_{2} + … + a_{n+1,n}x_{n} ≤ t_{n+1} − a_{n+1,1}x_{1} ,

we can compute the number of lattice points in the interior and closure of S_{A}^{(t)} as

L (S_{A}^{∘}, t) = \begin{aligned}[ & \frac{c_{2}t_{2}+...+cntn−1}{d} & ] \\ & ∑ \\ & m=[ \frac{t_{1}}{a_{11}} ]+1 \end{aligned} L (S_{B}^{∘}, t_{2} − a_{21}m, …, t_{n+1} − a_{n+1,1}m)  (4)

and

L (\overline{S_{A}}, t) = \begin{matrix}[ & \frac{c_{2}t_{2}+...+cntn}{d} & ] \\ ∑ \\ m=[ \frac{t_{1}−1}{a_{11}} ]+1 \end{matrix} L (\overline{S_{B}}, t_{2} − a_{21}m, …, t_{n+1} − a_{n+1,1}m) ,  (5)

respectively, where

B = ( a_{22} … a_{2n} ; ⋮ ; a_{n+1,2} … a_{n+1,n} ) ∈ M_{n×(n−1)}(ℤ) .

Note that if we start with some t ∈ ℤ^{n+1} which satisfies Definition 1, then the dilation parameters for S_{B} in (4) and (5) will ensure well-definedness of the lattice point count operators. L (S_{B}^{∘}, t) and L (\overline{S_{B}}, t) are, by induction hypothesis, quasipolynomials satisfying the reciprocity law (2). Hence, by Lemma 4, L (S_{A}^{∘}, t) and L (\overline{S_{A}}, t) are also quasipolynomials. Note that we again use (3) to define these expressions for all t ∈ ℤ^{n+1}. Furthermore,

L (S_{A}^{∘}, −t) = \begin{aligned}[ & \frac{−c_{2}t_{2}−...−cntn−1}{d} & ] \\ & ∑ \\ & m=[ \frac{−t_{1}}{a_{11}} ]+1 \end{aligned} L (S_{B}^{∘}, −t_{2} − a_{21}m, …, −t_{n+1} − a_{n+1,1}m)

=^{(2),(3)} − \begin{matrix}[ & \frac{−t_{1}}{a_{11}} & ] \\ ∑ \\ [\frac{−c_{2}t_{2}−...−cntn−1}{d}]+1 \end{matrix}(−1)^{n−1}L (\overline{S_{B}}, t_{2} + a_{21}m, …, t_{n+1} + a_{n+1,1}m)

=^{(1)} (−1)^{n} ∑_{m=−[\frac{c_{2}t_{2}+...+cntn}{d}]}^{−[ \frac{t_{1}−1}{a_{11}} ]−1} L (\overline{S_{B}}, t_{2} + a_{21}m, …, t_{n+1} + a_{n+1,1}m)

= (−1)^{n} \begin{matrix}[ & \frac{c_{2}t_{2}+...+cntn}{d} & ] \\ ∑ \\ m=[ \frac{t_{1}−1}{a_{11}} ]+1 \end{matrix} L (\overline{S_{B}}, t_{2} − a_{21}m, …, t_{n+1} − a_{n+1,1}m)

= (−1)^{n}L (\overline{S_{A}}, t) .

□

4 Some remarks and an example

An obvious generalization of Theorem 3 would be a similar statement for arbitrary rational polytopes (with any number of facets). However, it is not even clear how to phrase conditions on t in the definition of a ’vector-dilated polytope’, since the number of facets/vertices changes for different values of t.

Another variation of the idea of vector-dilating a polytope is to dilate the vertices by certain factors, instead of the facets. This would most certainly require completely different methods as the ones used in this paper.

It is, finally, of interest to compute precise formulas (that is, the coefficients of the quasipolynomials) for L (S_{A}^{∘}, t) and L (\overline{S_{A}}, t), corresponding to the various existing formulas for L (P^{∘}, t) and L (\overline{P}, t).

To illustrate this, we will compute L (\overline{S_{A}}, t) for a two-dimensional rectangular rational triangle, namely,

S_{A} = \{x ∈ ℝ^{2} : \begin{matrix}a_{1}x_{1} & & & ≥ & 1 \\ & & a_{2}x_{2} & ≥ & 1 \\ c_{1}x_{1} & + & c_{2}x_{2} & ≤ & 1 \end{matrix} \} .

Here, a_{1}, a_{2}, c_{1}, c_{2} are positive integers; we may also assume that c_{1} and c_{2} are relatively prime. To derive a formula for L (\overline{S_{A}}, t) we use the methods introduced in [Be]. Similarly as in that paper, we can interpret

L (\overline{S_{A}}, t) = # \{(m_{1}, m_{2}) ∈ ℤ^{2} : \begin{matrix}a_{1}m_{1} & & & ≥ & t_{1} \\ & & a_{2}m_{2} & ≥ & t_{2} \\ c_{1}m_{1} & + & c_{2}m_{2} & ≤ & t_{3} \end{matrix} \}

as the Taylor coefficient of z^{t_{3}} of the function

( ∑_{m_{1}≥[ \frac{t_{1}−1}{a_{1}} ]+1} z^{c_{1}m_{1}} ) ( ∑_{m_{2}≥[ \frac{t_{2}−1}{a_{2}} ]+1} z^{c_{2}m_{2}} ) (∑_{k≥0} z^{k})

= \frac{z^{([^{\frac{t_{1}−1}{a_{1}}} ]+1)c_{1}}}{1 − z^{c_{1}}} \frac{z^{([^{\frac{t_{2}−1}{a_{2}}} ]+1)c_{2}}}{1 − z^{c_{2}}} \frac{1}{1 − z} .

Equivalently,

L (\overline{S_{A}}, t) = Res (\frac{z^{e_{1}+e_{2}−t_{3}−1}}{(1 − z^{c_{1}}) (1 − z^{c_{2}}) (1 − z)}, z = 0) ,  (6)

where we introduced, for ease of notation, e_{j} := ([\frac{t_{j}−1}{a_{j}}] + 1) c_{j} for j = 1, 2. If the

right-hand side of (6) counts the number of lattice points in S_{A}^{(t)}, then the remaining task is computing the other residues of

f(z) := \frac{z^{e_{1}+e_{2}−t_{3}−1}}{(1 − z^{c_{1}}) (1 − z^{c_{2}}) (1 − z)} ,

and use the residue theorem for the sphere ℂ ∪ {∞}. Besides at 0, f has poles at all c_{1}, c_{2}’th roots of unity; note that if we start with a t which satisfies Definition 1 then Res(f(z), z = ∞) = 0.

The residue at z = 1 can be easily calculated as

Res(f(z), z = 1) = Res(e^{z}f(e^{z}), z = 0)

= −\frac{1}{2c_{1}c_{2}} (e_{1} + e_{2} − t_{3})^{2} + \frac{1}{2} (e_{1} + e_{2} − t_{3}) (\frac{1}{c_{1}} + \frac{1}{c_{2}} + \frac{1}{c_{1}c_{2}} )

−\frac{1}{4} (1 + \frac{1}{c_{1}} + \frac{1}{c_{2}} ) − \frac{1}{12} (\frac{c_{1}}{c_{2}} + \frac{c_{2}}{c_{1}} + \frac{1}{c_{1}c_{2}} ) .

It remains to compute the residues at the nontrivial roots of unity. Let λ^{c_{1}} = 1 ≠ λ. Then

Res(f(z), z = λ) = \frac{λ^{e_{2}−t_{3}−1}}{(1 − λ^{c_{2}}) (1 − λ)} Res (\frac{1}{1 − λ^{c_{1}}} , z = λ)

= −\frac{λ^{e_{2}−t_{3}}}{c_{1} (1 − λ^{c_{2}}) (1 − λ)} .

Adding up all the nontrivial c_{1}’th roots of unity, we obtain

∑_{λ^{c_{1}}=1≠λ} Res(f(z), z = λ) = −\frac{1}{c_{1}} ∑_{λ^{c_{1}}=1≠λ} \frac{λ^{e_{2}−t_{3}}}{(1 − λ^{c_{2}}) (1 − λ)} ,

a special case of a Fourier-Dedekind sum, which already occurred in [Be-Di-Ro]. In fact, in the same paper we derived, by means of finite Fourier series,

\frac{1}{c_{1}} ∑_{λ^{c_{1}}=1≠λ} \frac{λ^{t}}{(1 − λ^{c_{2}}) (1 − λ)} = ∑_{k=0}^{c_{1}−1} ((\frac{−c_{2}k − t}{c_{1}})) ((\frac{k}{c_{1}} )) − \frac{1}{4c_{1}} ,

where ((x)) = x − [x] − 1/2 is a sawtooth function (differing slightly from the one appearing in the classical Dedekind sums). The expression on the right is, up to a trivial term, a special case of a Dedekind-Rademacher sum ([Di], [Me], [Ra]). Hence,

∑_{λ^{c_{1}}=1≠λ} Res(f(z), z = λ) = − ∑_{k=0}^{c_{1}−1} ((\frac{t_{3} − e_{2} − c_{2}k}{c_{1}} )) ((\frac{k}{c_{1}} )) + \frac{1}{4c_{1}} ,

and, similarly, for the nontrivial c_{2}’th roots of unity

∑_{μ^{c_{2}}=1≠μ} Res(f(z), z = μ) = − ∑_{k=0}^{c_{2}−1} ((\frac{t_{3} − e_{1} − c_{1}k}{c_{2}} )) ((\frac{k}{c_{2}} )) + \frac{1}{4c_{2}} .

The residue theorem allows us now to rewrite (6) as

L (\overline{S_{A}}, t) = \frac{1}{2c_{1}c_{2}} (e_{1} + e_{2} − t_{3})^{2} − \frac{1}{2} (e_{1} + e_{2} − t_{3}) (\frac{1}{c_{1}} + \frac{1}{c_{2}} + \frac{1}{c_{1}c_{2}} )

+\frac{1}{4} + \frac{1}{12} (\frac{c_{1}}{c_{2}} + \frac{c_{2}}{c_{1}} + \frac{1}{c_{1}c_{2}} ) + ∑_{k=0}^{c_{1}−1} ((\frac{t_{3} − e_{2} − c_{2}k}{c_{1}} )) ((\frac{k}{c_{1}} ))

+ ∑_{k=0}^{c_{2}−1} ((\frac{t_{3} − e_{1} − c_{1}k}{c_{2}} )) ((\frac{k}{c_{2}} )) .

To see the quasipolynomial character better, we substitute back the expressions for e_{1} and e_{2}, and write [x] = x − ((x)) − 1/2 for the greatest integer function. After a somewhat tedious calculation, we obtain

L (\overline{S_{A}}, t) = \frac{c_{1}}{2a_{1}^{2}c_{2}} t_{1}^{2} + \frac{c_{2}}{2a_{2}^{2}c_{1}} t_{2}^{2} + \frac{1}{2c_{1}c_{2}} t_{3}^{2} + \frac{1}{a_{1}a_{2}} t_{1}t_{2} − \frac{1}{a_{1}c_{2}} t_{1}t_{3} − \frac{1}{a_{2}c_{1}} t_{2}t_{3}

+ν_{1}(t) t_{1} + ν_{2}(t) t_{2} + ν_{3}(t) t_{3} + ν_{0}(t) ,

where

ν_{1}(t) = −\frac{c_{1}}{a_{1}^{2}c_{2}} (1 + ((\frac{t_{1} − 1}{a_{1}}))) − \frac{1}{a_{1}} ((\frac{t_{2} − 1}{a_{2}})) − \frac{1}{a_{1}a_{2}} − \frac{1}{2a_{1}c_{2}}

ν_{2}(t) = −\frac{c_{2}}{a_{2}^{2}c_{1}} (1 + ((\frac{t_{2} − 1}{a_{2}}))) − \frac{1}{a_{2}} ((\frac{t_{1} − 1}{a_{1}})) − \frac{1}{a_{1}a_{2}} − \frac{1}{2a_{2}c_{1}}

ν_{3}(t) = \frac{1}{a_{1}c_{2}} + \frac{1}{a_{2}c_{1}} + \frac{1}{2c_{1}c_{2}} + \frac{1}{c_{2}} ((\frac{t_{1} − 1}{a_{1}})) + \frac{1}{c_{1}} ((\frac{t_{2} − 1}{a_{2}}))

ν_{0}(t) = −\frac{1}{4c_{1}} − \frac{1}{4c_{2}} + \frac{1}{a_{1}a_{2}} + \frac{1}{2a_{1}c_{2}} + \frac{1}{2a_{2}c_{1}} + \frac{1}{12c_{1}c_{2}} − \frac{c_{1}}{24c_{2}} − \frac{c_{2}}{24c_{1}}

+\frac{c_{1}}{2a_{1}^{2}c_{2}} + \frac{c_{2}}{2a_{2}^{2}c_{1}} + ((\frac{t_{1} − 1}{a_{1}})) (\frac{1}{a_{2}} + \frac{1}{2c_{2}} + \frac{c_{1}}{a_{1}c_{2}} )

+ ((\frac{t_{2} − 1}{a_{2}})) (\frac{1}{a_{1}} + \frac{1}{2c_{1}} + \frac{c_{2}}{a_{2}c_{1}} ) + \frac{c_{1}}{2c_{2}} ((\frac{t_{1} − 1}{a_{1}}))^{2}

the electronic journal of combinatorics 6 (1999), #R37 9

+\frac{c_{2}}{2c_{1}} ((\frac{t_{2} − 1}{a_{2}}))^{2} + ((\frac{t_{1} − 1}{a_{1}})) ((\frac{t_{2} − 1}{a_{2}}))

+ ∑_{k=0}^{c_{1}−1} ((\frac{t_{3}}{c_{1}} − \frac{t_{2} − 1}{a_{2}c_{1}} + \frac{1}{c_{1}} ((\frac{t_{2} − 1}{a_{2}})) − \frac{1}{2c_{1}} − \frac{c_{2}k}{c_{1}} )) ((\frac{k}{c_{1}} ))

+ ∑_{k=0}^{c_{2}−1} ((\frac{t_{3}}{c_{2}} − \frac{t_{1} − 1}{a_{1}c_{2}} + \frac{1}{c_{2}} ((\frac{t_{1} − 1}{a_{1}})) − \frac{1}{2c_{2}} − \frac{c_{1}k}{c_{2}} )) ((\frac{k}{c_{2}} )) .

As a final remark, we note that this formula enables us to compute the number of lattice points inside any rational polygon: Any two-dimensional polytope can be written as a virtual decomposition of rectangles (which are easy to deal with) and the right-angled triangles discussed above. Moreover, if the polygon has rational vertices, so do all these ’pieces’.

Acknowledgements. I am grateful to Boris Datskovsky, Sinai Robins, and Bob Styer for corrections and helpful suggestions on earlier versions of this paper, and to Tendai Chitewere for invaluable moral support.

References

[Be] M. Beck, Counting lattice points by means of the residue theorem, to appear in: Ramanujan J.

[Be-Di-Ro] M. Beck, R. Diaz, S. Robins, The Frobenius problem, rational polytopes, and Fourier-Dedekind sums, submitted.

[Di] U. Dieter, Das Verhalten der Kleinschen Funktionen log σ_{g,h} (w_{1}, w_{2}) gegenüber Modultransformationen und verallgemeinerte Dedekindsche Summen, J. reine angew. Math. 201 (1959), 37-70.

[Eh] E. Ehrhart, Sur un problème de géométrie diophantienne linéaire II, J. reine angew. Math. 227 (1967), 25-49.

[Ma] I. G. Macdonald, Polynomials associated with finite cell complexes, J. London Math. Soc. 4 (1971), 181-192.

[Mc] P. McMullen, Lattice invariant valuations on rational polytopes, Arch. Math. (Basel) 31, no. 5 (1978/79), 509–516.

[Me] C. Meyer, Über einige Anwendungen Dedekindscher Summen, J. reine angewandte Math. 198 (1957), 143-203.

[Ra] H. Rademacher, Some remarks on certain generalized Dedekind sums, Acta Aritm. 9 (1964), 97-105.

[St] R. Stanley, Enumerative combinatorics, Wadsworth and Brooks/Cole, Monterey, Ca. (1986).