Transactions of the American Mathematical Society

Author(s): R. J. Gardner; P. Gronchi
Journal: Trans. Amer. Math. Soc. 353 (2001), 3995-4024.
MSC (1991): Primary 05B50, 52B20, 52C05, 52C07; Secondary 92C55
Posted: June 6, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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

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

R. J. Gardner
Affiliation: Department of Mathematics, Western Washington University, Bellingham, Washington 98225-9063
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
Email: paolo@iaga.fi.cnr.it

DOI: 10.1090/S0002-9947-01-02763-5
PII: S 0002-9947(01)02763-5
Keywords: Brunn-Minkowski inequality, lattice, lattice polygon, convex lattice polytope, lattice point enumerator, sum set, difference set
Received by editor(s): September 30, 1999
Posted: June 6, 2001
Additional Notes: First author supported in part by U.S. National Science Foundation Grant DMS-9802388
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS