Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-12-01T00:02:45.622Z Has data issue: false hasContentIssue false
  • English
  • Français

Ehrhart Polynomials and Successive Minima

Part of: Polytopes and polyhedra Discrete geometry

Published online by Cambridge University Press:  21 December 2009

Martin Henk ,
Achill Schürmann  and
Jörg M. Wills
Martin Henk
Affiliation:
Universität Magdeburg, IAG, Universitätsplatz 2, D-39106 Magdeburg, Germany. E-Mail: [email protected]
Achill Schürmann
Affiliation:
Universität Magdeburg, Institut für Algebra und Geometrie, Universitätsplatz 2, D-39106 Magdeburg, Germany. E-mail: [email protected]
Jörg M. Wills
Affiliation:
Universität Siegen, Mathematisches Institut, ENC, D-57068 Siegen, Germany. E-mail: [email protected]
Get access

Abstract

The Ehrhart polynomials for the class of 0-symmetric convex lattice polytopes in Euclidean n-space ℝn are investigated. It turns out that the roots of the Ehrhart polynomial and Minkowski's successive minima of such polytopes are closely related by their geometric and arithmetic means. It is also shown that the roots of the Ehrhart polynomials of lattice n-polytopes with or without interior lattice points differ essentially. Furthermore, the structure of the roots in the planar case is studied. Here it turns out that their distribution reflects basic properties of lattice polygons.

MSC classification

Secondary: 52C07: Lattices and convex bodies in $n$ dimensions 52B20: Lattice polytopes (including relations with commutative algebra and algebraic geometry)
Type
Research Article
Information
Mathematika , Volume 52 , Issue 1-2 , December 2005 , pp. 1 - 16
Copyright
Copyright © University College London 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Bambah, R. P., Woods, A. C., and Zassenhaus, H., Three proofs of Minkowski's second inequality in the geometry of numbers. J. Austral. Math. Soc. 5 (1965), 453–462.CrossRefGoogle Scholar
2Barvinok, A., Computing the Ehrhart polynomial of a convex lattice polytope. Discrete Comput. Geom. 12 (1994), 35–48.CrossRefGoogle Scholar
3Barvinok, A., A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19 (1994), 769–779.CrossRefGoogle Scholar
4Barvinok, A. and Pommersheim, J. E., An algorithmic theory of lattice points in polyhedra. New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–1997, Math. Sci. Res. Inst. Publ., 38 (1994), 91–147.Google Scholar
5Beck, M., De Loera, J., Develin, M., Pfeifle, J., and Stanley, R. P., Coefficients and roots of Ehrhart polynomials. Contemp. Math. 374 (2005), 15–36.CrossRefGoogle Scholar
6Beck, M. and Pixton, D., The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom. 30 (2003), 623–637.CrossRefGoogle Scholar
7Beck, M. and Robins, S., Computing the continuous discretely: Integer-point enumeration in polyhedra. Springer (to appear), Preprint at http://math.sfsu.edu/beck/papers/ccd.html.CrossRefGoogle Scholar
8Betke, U. and Gritzmann, P., An application of valuation theory to two problems of discrete geometry. Discrete Math. 58 (1986), 81–85.CrossRefGoogle Scholar
9Betke, U., Henk, M., and Wills, J. M., Successive-minima-type inequalities. Discrete Comput. Geom. 9 (1993), 165–175.CrossRefGoogle Scholar
10Betke, U. and Kneser, M., Zerlegungen und Bewertungen von Gitterpolytopen. J. Reine Angew. Math. 358 (1985), 202–208.Google Scholar
11Betke, U. and McMullen, P., Lattice points in lattice polytopes. Monatsh. Math. 99 (1985), 253–265.CrossRefGoogle Scholar
12Bump, D., Choi, K.-K., Kurlberg, P., and Vaaler, J., A local Riemann hypothesis, I. Math. Z. 233 (2000), 1–19.CrossRefGoogle Scholar
13Davenport, H., Minkowski's inequality for the minima associated with a convex body. Quarterly J. Math. 10 (1939), 119–121.CrossRefGoogle Scholar
14De Loera, J., Haws, D., Hemmecke, R., and Huggins, P., A user's guide for latte v1.1, software package latte, 2004, available at http://www.math.ucdavis.edu/~latte.Google Scholar
15De Loera, J., Hemmecke, R., Tauzer, J., and Yoshida, R., Effective lattice point counting in rational convex polytopes. J. Symb. Comput. 38 (2004), 1273–1302.CrossRefGoogle Scholar
16Diaz, R. and Robins, S., The Ehrhart polynomial of a lattice polytope. Ann. Math. 145 (1997), 503–518. Erratum in 146 (1997), 237.CrossRefGoogle Scholar
17Ehrhart, E., Sur les polyedres rationnels homothétiques à n dimensions. C. R. Acad. Sci., Paris, Sér. A. 254 (1962), 616–618.Google Scholar
18Ehrhart, E., Sur un problème de gèomètrie diophantienne linéaire. J. Reine Angew. Math. 227 (1967), 25–49.Google Scholar
19Ehrhart, E., Sur la loi de rèciprocitè des polyèdres rationnels. C. R. Acad. Sci., Paris, Sèr. A 266 (1968), 695–697.Google Scholar
20Gritzmann, P. and Wills, J. M., Lattice points. In Handbook of Convex Geometry (Gruber, P.M. and Wills, J.M., eds.), vol. B, North-Holland (Amsterdam, 1993).Google Scholar
21Gruber, P. M. and Lekkerkerker, C. G., Geometry of Numbers (2nd ed.), vol. 37, North-Holland Publishing Co. (Amsterdam, 1987).CrossRefGoogle Scholar
22Grünbaum, B., Convex Polytopes (2nd ed. Prepared by Kaibel, V., Klee, V. and Ziegler, G. M.). Springer (New York, 2003).CrossRefGoogle Scholar
23Henk, M., Inequalities between successive minima and intrinsic volumes of a convex body. Monatsh. Math. 110 (1990), 279–282.CrossRefGoogle Scholar
24Henk, M., Successive minima and lattice points. Rend. Circ. Mat. Palermo (2) Suppl., (2002), no. 70, part I, 377–384.Google Scholar
25Hibi, T., Algebraic Combinatorics on Convex Polytopes. Carslaw Publications (Glebe, Australia, 1992).Google Scholar
26Hibi, T., Dual polytopes of rational convex polytopes. Combinatorica 12 (1992), 237–240.CrossRefGoogle Scholar
27Lagarias, J. C., Point lattices. Handbook of Combinatorics (Graham, R. L., Grötschel, M., and Lovász, L., eds.), vol. A, North-Holland (Amsterdam, 1995).Google Scholar
28Lagarias, J. C. and Ziegler, G. M., Bounds for lattice polytopes containing a fixed number of interior points in a sublattice. Canad. J. Math. 43 (1991), 1022–1035.CrossRefGoogle Scholar
29Liu, F., Ehrhart polynomials of cyclic polytopes. J. Comb. Theory Ser. A 111 (2005), 111–127.CrossRefGoogle Scholar
30Liu, F., Ehrhart polynomials of lattice-face polytopes. http://arxiv.org/abs/math.co/0512616.Google Scholar
31Minkowski, H., Geometrie der Zahlen, Teubner (Leipzig-Berlin, 1896). (Reprinted: Johnson, New York, 1968.)Google Scholar
32Mordell, L. J., Lattice points in tetrahedron and generalized Dedekind sums. J. Indian Math. Soc. (N.S.) 15 (1951), 41–46.Google Scholar
33Mustata, M. and Payne, S., Ehrhart polynomials and stringy Betti numbers. http://arxiv.org/abs/math.AG/0505054.Google Scholar
34Pick, G. A., Geometrisches zur Zahlenlehre. Sitzungsber. Lotus Prag 19 (1899), 311–319.Google Scholar
35Pommersheim, J. E., Toric varieties, lattice points and Dedekind sums. Math. Ann. 295 (1993), 1–24.CrossRefGoogle Scholar
36Reeve, J. E., On the volume of lattice polyhedra. Proc. London Math. Soc. 7 (1957), no. 3, 378–395.CrossRefGoogle Scholar
37Rodriguez-Villegas, F., On the zeros of certain polynomials. Proc. Amer. Math. Soc. 130 (2002), 2251–2254.CrossRefGoogle Scholar
38Schneider, R., Convex bodies: The Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press (Cambridge, 1993).CrossRefGoogle Scholar
39Scott, P. R., On convex lattice polygons. Bull. Austral. Math. Soc. 15 (1976), 395–399.CrossRefGoogle Scholar
40Siegel, C. L., Lectures on the Geometry of Numbers, Springer-Verlag (Berlin, 1989).CrossRefGoogle Scholar
41Stanley, R. P., Decompositions of rational convex polytopes. Ann. Discrete Math. 6 (1980), 333–342.CrossRefGoogle Scholar
42Stanley, R. P., Enumerative combinatorics. vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press (Cambridge, 1997) (corrected reprint of the 1986 original).CrossRefGoogle Scholar
43Weyl, H., On geometry of numbers. Proc. London Math. Soc. (2) 47 (1942), 268–289.CrossRefGoogle Scholar
44Wills, J. M., Kugellagerungen und Konvexgeometrie. Jahresber. Deutsch. Math.-Verein. 92 (1990), 21–46.Google Scholar
45Wills, J. M., Minkowski's successive minima and the zeros of a convexity-function. Monatsch. Math. 109 (1990), 157–164.CrossRefGoogle Scholar
46Wills, J. M., On an analog to Minkowski's lattice point theorem. In The Geometric Vein: The Coxeter Festschrift (Davis, C., Grünbaum, B., and Sherk, F. A., eds.), Springer (New York, 1982), 285–288.Google Scholar