A Brunn-Minkowski inequality for the integer lattice
HTML articles powered by AMS MathViewer
- by R. J. Gardner and P. Gronchi
- Trans. Amer. Math. Soc. 353 (2001), 3995-4024
- DOI: https://doi.org/10.1090/S0002-9947-01-02763-5
- Published electronically: June 6, 2001
- PDF | Request permission
Abstract:
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
- Ilya J. Bakelman, Convex analysis and nonlinear geometric elliptic equations, Springer-Verlag, Berlin, 1994. With an obituary for the author by William Rundell; Edited by Steven D. Taliaferro. MR 1305147, DOI 10.1007/978-3-642-69881-1
- S. L. Bezrukov, Isoperimetric problems in discrete spaces, Extremal problems for finite sets (Visegrád, 1991) Bolyai Soc. Math. Stud., vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 59–91. MR 1319157
- Béla Bollobás and Imre Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991), no. 1, 47–62. MR 1082842, DOI 10.1016/0097-3165(91)90021-8
- Béla Bollobás and Imre Leader, Sums in the grid, Discrete Math. 162 (1996), no. 1-3, 31–48. MR 1425777, DOI 10.1016/S0012-365X(96)00303-2
- T. Bonnesen and W. Fenchel, Theory of convex bodies, BCS Associates, Moscow, ID, 1987. Translated from the German and edited by L. Boron, C. Christenson and B. Smith. MR 920366
- Christer Borell, Capacitary inequalities of the Brunn-Minkowski type, Math. Ann. 263 (1983), no. 2, 179–184. MR 698001, DOI 10.1007/BF01456879
- S. Campi, A. Colesanti, and P. Gronchi, Shaking compact sets, Contributions to Algebra and Geometry 42 (2001), 123–136.
- Max H. M. Costa and Thomas M. Cover, On the similarity of the entropy power inequality and the Brunn-Minkowski inequality, IEEE Trans. Inform. Theory 30 (1984), no. 6, 837–839. MR 782217, DOI 10.1109/TIT.1984.1056983
- Amir Dembo, Thomas M. Cover, and Joy A. Thomas, Information-theoretic inequalities, IEEE Trans. Inform. Theory 37 (1991), no. 6, 1501–1518. MR 1134291, DOI 10.1109/18.104312
- P. Erdös, P. M. Gruber, and J. Hammer, Lattice points, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 39, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989. MR 1003606
- Günter Ewald, Combinatorial convexity and algebraic geometry, Graduate Texts in Mathematics, vol. 168, Springer-Verlag, New York, 1996. MR 1418400, DOI 10.1007/978-1-4612-4044-0
- Richard J. Gardner, Geometric tomography, Encyclopedia of Mathematics and its Applications, vol. 58, Cambridge University Press, Cambridge, 1995. MR 1356221
- R. J. Gardner and Peter Gritzmann, Discrete tomography: determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997), no. 6, 2271–2295. MR 1376547, DOI 10.1090/S0002-9947-97-01741-8
- Andrew Granville and Friedrich Roesler, The set of differences of a given set, Amer. Math. Monthly 106 (1999), no. 4, 338–344. MR 1682377, DOI 10.2307/2589556
- Peter Gritzmann and Jörg M. Wills, Lattice points, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 765–797. MR 1242996
- M. Gromov, Convex sets and Kähler manifolds, Advances in differential geometry and topology, World Sci. Publ., Teaneck, NJ, 1990, pp. 1–38. MR 1095529
- Gabor T. Herman and Attila Kuba (eds.), Discrete tomography, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 1999. Foundations, algorithms, and applications. MR 1722457, DOI 10.1007/978-1-4612-1568-4
- David Jerison, A Minkowski problem for electrostatic capacity, Acta Math. 176 (1996), no. 1, 1–47. MR 1395668, DOI 10.1007/BF02547334
- Jeff Kahn and Nathan Linial, Balancing extensions via Brunn-Minkowski, Combinatorica 11 (1991), no. 4, 363–368. MR 1137768, DOI 10.1007/BF01275670
- D. J. Kleitman, Extremal hypergraph problems, Surveys in combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979) London Math. Soc. Lecture Note Ser., vol. 38, Cambridge Univ. Press, Cambridge-New York, 1979, pp. 44–65. MR 561306
- Melvyn B. Nathanson, Additive number theory, Graduate Texts in Mathematics, vol. 165, Springer-Verlag, New York, 1996. Inverse problems and the geometry of sumsets. MR 1477155, DOI 10.1007/978-1-4757-3845-2
- Andrei Okounkov, Brunn-Minkowski inequality for multiplicities, Invent. Math. 125 (1996), no. 3, 405–411. MR 1400312, DOI 10.1007/s002220050081
- Gilles Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275, DOI 10.1017/CBO9780511662454
- J. Rosenblatt and P. D. Seymour, The structure of homometric sets, SIAM J. Alg. Disc. Meth. 3 (1982), 343–350.
- Imre Z. Ruzsa, Sum of sets in several dimensions, Combinatorica 14 (1994), no. 4, 485–490. MR 1312875, DOI 10.1007/BF01302969
- I. Z. Ruzsa, Sets of sums and commutative graphs, Studia Sci. Math. Hungar. 30 (1995), no. 1-2, 127–148. MR 1341572
- Imre Z. Ruzsa, Sums of finite sets, Number theory (New York, 1991–1995) Springer, New York, 1996, pp. 281–293. MR 1420216, DOI 10.1007/978-1-4612-2418-1_{2}1
- Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR 1216521, DOI 10.1017/CBO9780511526282
- Y. Stanchescu, On finite difference sets, Acta Math. Hungar. 79 (1998), no. 1-2, 123–138. MR 1611960, DOI 10.1023/A:1006513923148
- Yonutz Stanchescu, On the simplest inverse problem for sums of sets in several dimensions, Combinatorica 18 (1998), no. 1, 139–149. MR 1645670, DOI 10.1007/PL00009808
- Roger Webster, Convexity, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1443208
Bibliographic Information
- R. J. Gardner
- Affiliation: Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063
- MR Author ID: 195745
- Email: gardner@baker.math.wwu.edu
- P. Gronchi
- Affiliation: Istituto di Analisi Globale ed Applicazioni, Consiglio Nazionale delle Ricerche, Via S. Marta 13/A, 50139 Firenze, Italy
- MR Author ID: 340283
- Email: paolo@iaga.fi.cnr.it
- 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
- © Copyright 2001 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 353 (2001), 3995-4024
- MSC (1991): Primary 05B50, 52B20, 52C05, 52C07; Secondary 92C55
- DOI: https://doi.org/10.1090/S0002-9947-01-02763-5
- MathSciNet review: 1837217