×

The many aspects of counting lattice points in polytopes. (English) Zbl 1093.52006

This well-written survey discusses applications of lattice-point enumeration problems in convex rational polytopes. Any such counting problem can be formulated in terms of the function \[ \phi_A(b) = \# \left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\} , \] for some integral \(d \times n\) matrix \(A\) and \(b \in {\mathbb Z}^d\). The author surveys some specific applications, such as knapsack problems, integral network flows, transportation polytopes and contingency tables, magic squares, Gelfand-Tsetlin patterns, and Hilbert series of monomial algebras. The paper gives the main structure theorem about \(\phi_A(b)\), namely that this function is a piecewise-defined quasipolynomial [B. Sturmfels, J. Comb. Theory, Ser. A 72, No. 2, 302–309 (1995; Zbl 0837.11055)]. A fundamental specialization of this counting function is given by \(\phi_A(tb)\) for a fixed \(b\); hence \(t\) becomes an integral parameter which can be thought of as a dilation factor of the polytope \(\left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\}\). If this polytope has integral vertices, Ehrhart’s theorem asserts that \(\phi_A(tb)\) is a polynomial in \(t\) whose leading term is the volume of \(P\) [E. Ehrhart, C. R. Acad. Sci., Paris 254, 616–618 (1962; Zbl 0100.27601)]. The author finishes with a description of Barvinok’s algorithm, which computes the lattice-point count for a rational polytope in fixed dimension in polynomial time. The paper concludes with some alternative algorithmic approaches and a brief discussion of lattice-point problems for regions other than convex polytopes.

MSC:

52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
11P21 Lattice points in specified regions
11H06 Lattices and convex bodies (number-theoretic aspects)
05A15 Exact enumeration problems, generating functions

Software:

LattE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal, K., Lenstra, A.K., Lenstra, H.W. Jr.: Hard equality constrained integer knapsacks. In: W.J. Cook and A.S. Schulz (eds.), Integer Programming and Combinatorial Optimization: 9th International IPCO Conference, Lecture Notes in Computer Science, vol. 2337, Springer-Verlag, pp. 350–366, 2002 · Zbl 1049.90042
[2] Adleman, L., Manders, K.: NP-complete decision problems for quadratic polynomials. In: Proceedings of the Eighth annual ACM symposium on theory of computing, Hershey, PA 1976, 23–29, ACM, New York, 1976 · Zbl 0381.68044
[3] Ahmed, M., De Loera, J., Hemmecke, R.: Polyhedral cones of magic cubes and square. In: New Directions in Combinatorial Geometry, The Goodman-Pollack festschrift (eds. Aronov et al.), Springer Verlag, pp. 25–41, 2003 · Zbl 1077.52506
[4] Andrews, G., Ekhad, S., Zeilberger, D.: A short proof of Jacobi’s formula for the number of representations of an integer as a sum of four squares. Am. Math. Mon. 100, 274–276 (1993) · Zbl 0769.11020
[5] Balcioglu, A., Wood, R.: Enumerating Near-Min s-t Cuts. In: Woodruff, D.L. (ed.) Network Interdiction and Stochastic Integer Programming, vol. 22, series operations research/computer science interfaces, Kluwer, Boston 2002 · Zbl 1099.90078
[6] Baldoni-Silva, W., De Loera, J., Vergne, M.: Counting integral flows on Networks. Found. Comput. Math. 4, 277–314 (2004) · Zbl 1083.68640
[7] Barvinok, A.I.: A course in Convexity. Graduate studies in Mathematics, vol. 54, Am. Math. Soc., Providence RI, 2002 · Zbl 1014.52001
[8] Barvinok, A.I.: Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math of Operations Research 19, 769–779 (1994) · Zbl 0821.90085
[9] Barvinok, A.I., Pommersheim, J.: An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–1997), pp. 91–147, Math. Sci. Res. Inst. Publ. 38, Cambridge Univ. Press, Cambridge, 1999 · Zbl 0940.05004
[10] Barvinok, A.I., Woods, K.: Short rational generating functions for lattice point problems. J. Am. Math. Soc. 16, 957–979 (2003) · Zbl 1017.05008
[11] Beck, M.: Counting lattice points by means of the residue theorem. Ramanujan J. 4 (3), 299–310 (2000) · Zbl 0988.11045
[12] Beck, M., De Loera, J.A., Develin, M., Pfeifle, J., Stanley, R.: Coefficients and roots of Ehrhart polynomials to appear in Cont. Math. (Proceedings of the Summer Research Conference on Integer Points in Polyhedra, July 13–July 17, Snowbird Utah, 2003) · Zbl 1153.52300
[13] Beck, M., Pixton, D.: The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom. 30 (4), 623–637 (2003) · Zbl 1065.52007
[14] Betke, U., McMullen, P.: Lattice points in lattice polytopes. Monatsh. Math. 99, 253–265 (1985) · Zbl 0565.52007
[15] Blakley, G.R.: Combinatorial remarks on partitions of a multipartite number. Duke Math. J. 31, 335–340 (1964) · Zbl 0122.01404
[16] Berenstein, A., Zelevinsky, A.: Tensor product multiplicities, canonical bases and totally positive varieties. Invent. Math. 143, 77–128 (2001) · Zbl 1061.17006
[17] Billey, S., Guillemin, V., Rassart, E.: A vector partition function for the multiplicities of \(\mathfrak{sl}_{k}\mathbb{C}\) . J. Algebra 278, 251–293 (2004) · Zbl 1116.17005
[18] Brion, M.: Points entiers dans les polyèdres convexes. Ann. Sci. École Norm. Sup. 21, 653–663 (1988) · Zbl 0667.52011
[19] Brion, M., Vergne, M.: Residue formulae, vector partition functions and lattice points in rational polytopes. J. Am. Math. Soc. 10, 797–833 (1997) · Zbl 0926.52016
[20] Clauss, P., Loechner, V.: Parametric Analysis of Polyhedral Iteration Spaces. J. VLSI Signal Process. 19, 179–194 (1998)
[21] De Loera, J.A., McAllister, T.B.: Vertices of Gelfand-Tsetlin polytopes. Discrete Comput. Geom. 32, 459–470 (2004) · Zbl 1057.05077
[22] De Loera, J.A., Haws, D., Hemmecke, R., Huggins, P., Sturmfels, B., Yoshida, R.: Short rational functions for toric algebra and applications. J. Symb. Comput. 38, 959–973 (2004) · Zbl 1137.13316
[23] De Loera, J. A., Haws, D., Hemmecke, R., Huggins, P., Tauzer, J., Yoshida, R.: A User’s Guide for LattE, software package LattE and manual are available at http://www.math.ucdavis.edu/atte/ 2003
[24] De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R.: Effective lattice point counting in rational convex polytopes. J. Symb. Comput. 38, 1273–1302 (2004) · Zbl 1137.52303
[25] Diaconis, P., Gangolli, A.: Rectangular arrays with fixed margins. In: Discrete probability and algorithms (Minneapolis, MN, 1993), pp. 15–41, IMA Vol. Math. Appl., 72, Springer, New York, 1995 · Zbl 0839.05005
[26] Diaz, R., Robins, S.: The Ehrhart Polynomial of a Lattice Polytope. Ann. Math. 145, 503–518 (1997) · Zbl 0874.52009
[27] Dyer, M., Mount, D., Kannan, R., Mount, J.: Sampling contingency tables. Random Structures and Algorithms 10, 487–506 (1997) · Zbl 0884.62065
[28] Ehrhart, E.: Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux. J. Reine Angew. Math. 226, 1–29 (1967)
[29] Ehrhart, E.: Polynômes arithmétiques et méthode des polyèdres en combinatoire, International Series of Numerical Mathematics, Vol. 35, Birkhäuser Verlag, Basel, 1977
[30] Fienberg, S.E., Makov, U.E., Meyer, M.M., Steele, R.J.: Computing the exact conditional distribution for a multi-way contingency table conditional on its marginal totals. In: Data Analysis From Statistical Foundations, pp. 145–166, Nova Science Publishers, A.K.Md.E. Saleh, Huntington, NY, 2001
[31] Fulton, W., Harris, J.: Representation Theory: A first course. Graduate texts in Mathematics, vol 129, Springer, New York, 1991 · Zbl 0744.22001
[32] Garey, M.R., Johnson, S.J.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979 · Zbl 0411.68039
[33] Ghosh, S., Martonosi, M., Malik, S.: Cache miss equations: a compiler framework for analyzing and tuning memory behavior. ACM Trans. Program. Lang. Syst. 21, 703–746 (1999)
[34] Guy, R.K.: Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240–241, 1994 · Zbl 0805.11001
[35] Hibi, T.: A lower bound theorem for Ehrhart polynomials of convex polytopes. Advances in Math. 105, 162–165 (1994) · Zbl 0807.52011
[36] Huxley, M.N.: Area, lattice points, and exponential sums. Oxford Univ. Press. Oxford, 1996 · Zbl 0861.11002
[37] Jacobi, C.: Gesammelte Werke, Berlin 1881–1891. Reprinted by Chelsea, New York, 1969
[38] Jerrum, M., Sinclair, A.: The Markov Chain Monte Carlo Method: An approach to approximate Counting and integration. In: Hochbaum, D. (ed.) Approximation Algorithms, PWS Publishing Company, Boston, 1997
[39] Jones, J.P.: Universal diophantine equations. J. Symb. Log. 47 (3), 403–410 (1982) · Zbl 0472.03034
[40] Kantor, J.M., Khovanskii, A.: Une application du Théorème de Riemann-Roch combinatoire au polynôme d’Ehrhart des polytopes entier. C. R. Acad. Sci. Paris, Series I 317, 501–507 (1993)
[41] Knutson, A., Tao, T.: The honeycomb model of GLn(\(\mathbb{C}\)) tensor products I: Proof of the Saturation Conjecture. J. Am. Math. Soc. 12, 1055–1090 (1999) · Zbl 0944.05097
[42] Knutson, A., Tao, T., Woodward, C.: The honeycomb model of GLn(\(\mathbb{C}\)) tensor products II: Puzzles determine facets of the Littlewood-Richardson cone. J. Am. Math. Soc. 17, 19–48 (2004) · Zbl 1043.05111
[43] Lasserre, J.B., Zeron, E.S.: On counting integral points in a convex rational polytope. Math. Oper. Res. 28, 853–870 (2003) · Zbl 1082.52009
[44] Lisonek, P.: Denumerants and their approximations. J. Combinat. Math. Combinat. Comput. 18, 225–232 (1995) · Zbl 0833.68086
[45] Loechner, V., Meister, B., Clauss, P.: Precise data locality optimization of nested loops. J. Supercomput. 21, 37–76 (2002) · Zbl 0991.68017
[46] Lóvász, L., Plummer, M.: Matching Theory. North-Holland mathematics studies, Elsevier, 1986
[47] Macdonald, I.G.: Polynomials associated with finite cell-complexes. J. Lond. Math. Soc. 4 (2), 181–192 (1971) · Zbl 0216.45205
[48] Miller, E., Sturmfels, B.: Combinatorial Commutative Algebra, Graduate texts in Mathematics, Vol. 227, Springer, New York, 2004
[49] McAllister, T.B., Woods, K.: The minimum period of the Ehrhart quasi-polynomial of a rational polytope. J. Combinat. Theory Series A, to appear · Zbl 1063.52006
[50] Morelli, R.: Pick’s theorem and the Todd class of a toric variety. Adv. Math. 100, 183–231 (1993) · Zbl 0797.14018
[51] Moura, L.: Polyhedral methods in design theory. In: Computational and Constructive Design Theory, pp. 227–254, W.D. Wallis (ed.) Math. Appl. 368, Kluwer, 1996 · Zbl 0847.90118
[52] Pemantle, R., Wilson, M.: Asymptotics of multivariate sequences, part I: smooth points of the singular variety. J. Comb. Theory, Series A 97, 129–161 (2001) · Zbl 1005.05007
[53] Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience, 1986 · Zbl 0665.90063
[54] Szenes, A., Vergne, M.: Residue formulae for vector partitions and Euler-Maclaurin sums. Adv. Appl. Math. 30, 295–342 (2003) · Zbl 1067.52014
[55] Stanley, R.P.: Decompositions of rational convex polytopes. In: Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). Ann. Discrete Math. 6, 333–342 (1980) · Zbl 0812.52012
[56] Stanley, R.P.: Two poset polytopes. Discrete Comput. Geom. 1, 9–23 (1986) · Zbl 0595.52008
[57] Stanley, R.P.: Enumerative Combinatorics, Volume I. Cambridge, 1997
[58] Sturmfels, B.: On Vector Partition functions. J. Combin. Theory Ser. A 72, 302–309 (1995) · Zbl 0837.11055
[59] Welsh, D.J.A.: Approximate counting. In: Bailey, R.A. (ed.) Surveys in Combinatorics, Cambridge Univ. Press, Cambridge, 1997 · Zbl 0880.68102
[60] Ziegler, G.M.: Lectures on Polytopes. Springer-Verlag, New York, 1995 · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.