Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A Brunn-Minkowski inequality for the integer lattice

Authors: R. J. Gardner and P. Gronchi
Journal: Trans. Amer. Math. Soc. 353 (2001), 3995-4024
MSC (1991): Primary 05B50, 52B20, 52C05, 52C07; Secondary 92C55
Published electronically: June 6, 2001
MathSciNet review: 1837217
Full-text PDF

Abstract | References | Similar Articles | Additional Information


A close discrete analog of the classical Brunn-Minkowksi inequality that holds for finite subsets of the integer lattice is obtained. This is applied to obtain strong new lower bounds for the cardinality of the sum of two finite sets, one of which has full dimension, and, in fact, a method for computing the exact lower bound in this situation, given the dimension of the lattice and the cardinalities of the two sets. These bounds in turn imply corresponding new bounds for the lattice point enumerator of the Minkowski sum of two convex lattice polytopes. A Rogers-Shephard type inequality for the lattice point enumerator in the plane is also proved.

References [Enhancements On Off] (What's this?)

  • 1. I. J. Bakelman, Convex Analysis and Nonlinear Geometric Elliptic Equations, Springer, Berlin, 1994. MR 95k:35063
  • 2. S. L. Bezrukov, Isoperimetric problems in discrete spaces, Extremal Problems for Finite Sets, Visegrád, Hungary (1991), Bolyai Society Mathematical Studies 3 (Budapest), János Bolyai Math. Soc., 1994, pp. 59-91. MR 96c:05181
  • 3. B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Comb. Theory A 56 (1991), 47-62. MR 92h:05133
  • 4. -, Sums in the grid, Discrete Math. 162 (1996), 31-48. MR 97h:05179
  • 5. T. Bonnesen and W. Fenchel, Theory of Convex Bodies, BCS Associates, Moscow, Idaho, U.S.A., 1987. German original: Springer, Berlin, 1934. MR 88j:52001
  • 6. C. Borell, Capacitary inequalities of the Brunn-Minkowski type, Math. Ann. 263 (1983), 179-184. MR 84e:31005
  • 7. S. Campi, A. Colesanti, and P. Gronchi, Shaking compact sets, Contributions to Algebra and Geometry 42 (2001), 123-136.
  • 8. M. H. M. Costa and T. Cover, On the similarity of the entropy power inequality and the Brunn-Minkowksi inequality, IEEE Trans. Information Theory 30 (1984), 837-839. MR 86d:26029
  • 9. A. Dembo, T. M. Cover, and J. A. Thomas, Information theoretic inequalities, IEEE Trans. Information Theory 37 (1991), 1501-1518. MR 92h:94005
  • 10. P. Erdös, P. M. Gruber, and J. Hammer, Lattice Points, Longman Scientific and Technical, and John Wiley, Bath and New York, 1989. MR 90g:11081
  • 11. G. Ewald, Combinatorial Convexity and Algebraic Geometry, Springer-Verlag, New York, 1996. MR 97i:52012
  • 12. R. J. Gardner, Geometric Tomography, Cambridge University Press, New York, 1995. MR 96j:52006
  • 13. R. J. Gardner and P. Gritzmann, Discrete tomography: Determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997), 2271-2295. MR 97h:52021
  • 14. A. Granville and F. Roesler, The set of differences of a given set, Amer. Math. Monthly 106 (1999), 338-344. MR 2000f:05080
  • 15. P. Gritzmann and J. M. Wills, Lattice points, Handbook of Convexity, ed. by P. M. Gruber and J. M. Wills (Amsterdam), North-Holland, 1993, pp. 765-797. MR 94k:52026
  • 16. M. Gromov, Convex sets and Kähler manifolds, Advances in Differential Geometry and Topology (Teaneck, NJ), World Scientific Publishing, 1990, pp. 1-38. MR 92d:52018
  • 17. G. T. Herman and A. Kuba (eds.), Discrete Tomography: Foundations, Algorithms and Application, Birkhäuser, Boston, 1999. MR 2000h:92015
  • 18. D. Jerison, A Minkowski problem for electrostatic capacity, Acta Math. 176 (1996), 1-47. MR 97e:31003
  • 19. J. Kahn and N. Linial, Balancing extensions via Brunn-Minkowski, Combinatorica 11 (1991), 363-368. MR 93e:52017
  • 20. D. L. Kleitman, Extremal hypergraph problems, Surveys in Combinatorics, ed. by B. Bollobás (Cambridge), Cambridge University Press, 1979, pp. 44-65. MR 81d:05061
  • 21. M. B. Nathanson, Additive Number Theory - Inverse Problems and the Geometry of Sumsets, Springer-Verlag, New York, 1996. MR 98f:11011
  • 22. A. Okounkov, Brunn-Minkowski inequality for multiplicities, Invent. Math. 125 (1996), 405-411. MR 99a:58074
  • 23. G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press, Cambridge, 1989. MR 91d:52005
  • 24. J. Rosenblatt and P. D. Seymour, The structure of homometric sets, SIAM J. Alg. Disc. Meth. 3 (1982), 343-350.
  • 25. I. Z. Ruzsa, Sum of sets in several dimensions, Combinatorica 14 (1994), 485-490. MR 95m:11018
  • 26. -, Sets of sums and commutative graphs, Studia Sci. Math. Hungar. 30 (1995), 127-148. MR 96i:11013
  • 27. -, Sums of finite sets, Number Theory, New York Seminar 1991-5 (New York), Springer, 1996, pp. 281-293. MR 97i:11019
  • 28. R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press, Cambridge, 1993. MR 94d:52007
  • 29. Y. Stanchescu, On finite difference sets, Acta Math. Hungar. 79 (1998), 123-138. MR 99c:05034
  • 30. -, On the simplest inverse problem for sums of sets in several dimensions, Combinatorica 18 (1998), 139-149. MR 2000a:05052
  • 31. R. Webster, Convexity, Oxford University Press, Oxford, 1994. MR 98h:52001

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05B50, 52B20, 52C05, 52C07, 92C55

Retrieve articles in all journals with MSC (1991): 05B50, 52B20, 52C05, 52C07, 92C55

Additional Information

R. J. Gardner
Affiliation: Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063

P. Gronchi
Affiliation: Istituto di Analisi Globale ed Applicazioni, Consiglio Nazionale delle Ricerche, Via S. Marta 13/A, 50139 Firenze, Italy

Keywords: Brunn-Minkowski inequality, lattice, lattice polygon, convex lattice polytope, lattice point enumerator, sum set, difference set
Received by editor(s): September 30, 1999
Published electronically: June 6, 2001
Additional Notes: First author supported in part by U.S. National Science Foundation Grant DMS-9802388
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society