A Brunn-Minkowski inequality for the integer lattice

Gardner, R.; Gronchi, P.

doi:10.1090/S0002-9947-01-02763-5

A Brunn-Minkowski inequality for the integer lattice
HTML articles powered by AMS MathViewer

by R. J. Gardner and P. Gronchi PDF

Trans. Amer. Math. Soc. 353 (2001), 3995-4024 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