On a Discrete Brunn--Minkowski Type Inequality

María A. Hernández Cifre, David Iglesias, Jesús Yepes Nicolás

SIAM Journal on Discrete Mathematics · 2018 · 19 citations · 6 references

Concepts

Abstract

The Brunn--Minkowski inequality states that the volume of compact sets $K,L\subset\mathbb{R}^n$ satisfies $\mathrm{vol}(K+L)^{1/n}\geq\mathrm{vol}(K)^{1/n}+\mathrm{vol}(L)^{1/n}$. In this paper we obtain two discrete analogs of it for the cardinality of finite subsets of the integer lattice ${\mathbb{Z}}^n$. On one hand we prove that if $A,B\subset{\mathbb{Z}}^n$ are finite, then $\bigl|\bar{A}+B\bigr|^{1/n}\geq |A|^{1/n}+|B|^{1/n}$, where $\bar{A}$ is an extension of $A$ which is constructed by adding some new integer points in a particular way; on the other hand, removing points of $A$, say, an equivalent inequality of the form $|A+B|^{1/n}\geq\bigl|{\mathrm{r}}(A)\bigr|^{1/n}+|B|^{1/n}$ can be obtained, where $r(A)$ is the reduced set of $A$. Both inequalities are sharp, and it can be seen that the number of additional points in $\bar{A}$ cannot be too large and depends only on $A$. Finally we also prove that the classical Brunn--Minkowski inequality for compact sets can be obtained as a consequence of these new discrete versions.

References

6