The Brunn-Minkowski inequality and nonconvex sets

Imre Z. Ruzsa*

Mathematical Institute of the Hungarian Academy of Sciences Budapest, Pf. 127, H-1364 Hungary. e-mail: ruzsa@math-inst.hu

Abstract. We improve the Brunn-Minkowski inequality for nonconvex sets. Besides the volume of the sets, our estimate depends on the volume of the convex hull of one of the sets. The estimate is asymptotically best possible if this set is fixed and the size of the other tends to infinity.

Keywords. Volume, convexity, convex hull, sumsets.

MSC 1991 classification. Primary 52A40, secondary 28A75, 52A38

1. Introduction

Let A, B be Borel sets in ℝ^{d}; μ will denote the inner Lebesgue measure. The celebrated Brunn-Minkowski inequality asserts that

μ(A + B)^{1/d} ≥ μ(A)^{1/d} + μ(B)^{1/d},  (1.1)

and here equality holds if A and B are homothetic convex sets. If we assume that μ(A + B) > 0 and A, B are both closed or open, then this is the only case of equality.

Our aim is to improve this inequality if the sets are nonconvex, and to measure the degree of nonconvexity we propose to use the measure of the convex hull beside the measure of the set. More exactly, we define the impact function of the set B by

ξ(a) = inf{μ(A + B) : μ(A) = a}.

Thus (1.1) is equivalent to

ξ(a) ≥ (a^{1/d} + μ(B)^{1/d})^{d} ,

and this is the best possible estimate in terms of μ(B) only. We would like to find the best estimate in terms of μ(B) and μ(conv B). We are unable to do this, but at least we can describe the asymptotic behaviour of ξ in terms of these quantities.

* Supported by Hungarian National Foundation for Scientific Research, Grant No. T7582.

Theorem 1.

For every bounded Borel set B ⊂ ℝ^{d} of positive measure we have

lim_{a→∞} ξ(a)^{1/d} − a^{1/d} = μ(conv B)^{1/d}.  (1.2)

We are able to give an estimate for ξ in terms of μ(B) and μ(conv B), but this is probably far from optimal. Note that by considering sets homothetic to conv B we immediately obtain

ξ(a)^{1/d} ≤ a^{1/d} + μ(conv B)^{1/d}.  (1.3)

Theorem 2.

Let μ(B) = b, μ(conv B) = v. We have

ξ(a)^{1/d} ≥ a^{1/d} + v^{1/d} (1 − c(v/b)^{1/2}(v/a)^{1/(2d)})  (1.4)
ξ(a) ≥ a + dv^{1/d}a^{1−1/d} (1 − c(v/b)^{1/2}(v/a)^{1/(2d)})  (1.5)

with a suitable positive constant c depending on d.

Theorem 1 is a consequence of (1.3) and (1.4).

If v > b, we get a nontrivial improvement over the Brunn-Minkowski inequality for a > a_{0}(b, v). It would be desirable to find an improvement also for small values of a.

The exact bound and the structure of the extremal set may be complicated. This is illustrated by the case d = 1, which was solved in [6].

Let B ⊂ ℝ, and write μ(B) = b, μ(conv B) = v (this is the diameter of B). If

a ≥ \frac{v(v − b)}{2b} + \frac{b\{v/b\}(1 − \{v/b\})}{2},  (1.6)

then ξ(a) = a + v. If (1.6) does not hold, then let k be the unique positive integer satisfying

\frac{k(k − 1)}{2} ≤ \frac{a}{b} < \frac{k(k + 1)}{2};

and define δ by

\frac{a}{b} = \frac{k(k − 1)}{2} + δk.

We have

ξ(a) ≥ a + (k + δ)b,

and this bound is attained if B = [0, b] ∪ {v}. A set A such that ξ(a) = μ(A + B) is given by

A = [0, (k − 1 + δ)b] ∪ [v, v + (k − 2 + δ)b] ∪ ... ∪ [(k − 1)v, (k − 1)v + δb].

On the other hand, we have here the simple and quite good lower bound

ξ(a) ≥ min(a + v, (\sqrt{a} + \sqrt{b/2})^{2}).

In particular, for d = 1 the limit relation in (1.2) becomes an equality for a > a_{0}. Now we show via an example that this is not the case if d = 2.

We give an example of a set B ⊂ ℝ^{2} such that

ξ(a)^{1/2} < a^{1/2} + v^{1/2}

will hold for certain arbitrarily large values of a.

Let 0 < c < 1 and let B consist of the square [0, c]×[0, c] and the points (0, 1), (1, 0) and (1, 1). Hence b = c^{2} and v = 1.

For an integer n ≥ 1 put

A_{n} = [0, n] × [0, n] ∪ ⋃_{j=0}^{n}[j, j + c] × [n, n + c] ∪ ⋃_{j=0}^{n−1}[n, n + c] × [j, j + c].

Thus A_{n} consists of a square of side n and 2n + 1 small squares of side c, hence

μ(A_{n}) = n^{2} + (2n + 1)b.

We can easily see that A_{n} + B = A_{n+1}. Hence by considering the set A = A_{n} we see that for a number a of the form a = n^{2} + (2n + 1)b we have

ξ(a) ≤ μ(A_{n+1}) = (n + 1)^{2} + (2n + 3)b < (\sqrt{a} + 1)^{2}.

A more detailed calculation leads to

ξ(a)^{1/2} ≤ a^{1/2} + 1 − ca^{−1}

(for these special values of a).

2. Plünnecke’s method

For iterated sumsets we introduce the notation

Bk = B + B + .. + B, k summands,

to distinguish it from

kB = {kx : x ∈ B}.

For convex sets these coincide.

Plünnecke [3] developed a method to connect the impacts of B and Bk. He considered sets of integers, and density rather than measure. I simplified his argument [4,5] and applied it to study cardinality problems for finite sets [7,9]. In [8] I studied sets of lattice points in several dimensions. The results and proofs are very similar to those of this paper. To apply this method, however, first we need to extend it from cardinalities to measures. With other possible applications in mind, we shall do this more generally than we need for the present application.

Using Plünnecke’s method, I proved the following result [4].

Lemma 2.1.

Let A, B_{1}, ..., B_{k} be nonempty finite subsets of a commutative group. Write α_{i} = |A + B_{i}|/|A|. There is a nonempty subset A′ ⊂ A such that

|A′ + B_{1} + ... + B_{k}| ≤ α_{1}...α_{k}|A′|.

Let G be a locally compact commutative group, written additively, with Haar measure μ. (For a not necessarily measurable set X we interpret μ(X) as the inner measure of X.) By a lattice we mean a discrete subgroup of G. We say that G is well-gridded, if for every neighbourhood U of 0 there is a lattice L such that L + U = G. (Examples are ℝ^{d}, a finite-dimensional torus, their product.)

Theorem 3.

Let G be a well-gridded locally compact commutative group, A, B_{1}, ..., B_{k} ⊂ G measurable sets. Assume that A is relatively compact, each B_{i} is compact and μ(A) > 0. Write α_{i} = μ(A + B_{i})/μ(A). For every ε > 0 there is a compact subset A′ ⊂ A such that μ(A′) > 0 and

μ(A′ + B_{1} + ... + B_{k}) ≤ (1 + ε)α_{1}...α_{k}μ(A′).

We say that a set Q ⊂ G is a fundamental cell for a lattice L if every g ∈ G has a unique decomposition as g = x + y, x ∈ L, y ∈ Q.

We shall repeatedly use the following property of fundamental cells, which is an immediate consequence of the definition. For any X ⊂ G the smallest set Y ⊂ L such that X ⊂ Y + Q is given by Y = (X − Q) ∩ L.

Lemma 2.2.

Let L be a lattice and V a measurable relatively compact set such that L + V = G. There is a measurable fundamental cell contained in V.

Proof. Since V is relatively compact, the set S = (V − V) ∩ L is finite. Hence we can find finitely many characters γ_{1}, ..., γ_{k} such that for all s ∈ S there is a j with γ_{j}(s) ≠ 1.

Now for x ∈ V let

f(x) = (\frac{log γ_{1}(x)}{i}, ..., \frac{log γ_{k}(x)}{i}) ∈ [−π, π)^{k}

and put

Q = {x ∈ V : there is no y ∈ V with y − x ∈ L, f(x) < f(y)}

where < means the lexicographical ordering. It follows immediately from the definition that Q is a fundamental cell.

To show that Q is measurable, observe that

Q = V \ ⋃_{s∈S} W_{s},

where

\begin{aligned}W_{s} & = \{v ∈ V : v + s ∈ V, f(x + s) < f(x)\} \\ & = V ∩ (V − s) ∩ \{x ∈ G : f(x + s) < f(x)\}. \end{aligned}

Here the third set is obviously a Borel set.

Proof of the Theorem. Assume first that A is also compact; then so is A + B_{i}. Select a δ > 0 (it will be specified in terms of ε later) and take a symmetric open neighbourhood U of 0 such that

μ(A + U) < (1 + δ)μ(A), μ(A + B_{i} + U) < (1 + δ)μ(A + B_{i})

for all i. Take another symmetric open neighbourhood V such that

V 4 ⊂ U.

Let L be such a lattice that L + V = G, and let Q ⊂ V be a measurable fundamental cell of L. Write q = μ(Q).

Let S = (A − Q) ∩ L. This set satisfies A ⊂ S + Q, hence

q|S| = μ(S + Q) ≥ μ(A),

6 I. Z. Ruzsa but also

q|S| = μ(S + Q) ≤ μ(A + Q − Q) ≤ μ(A + V 2) ≤ μ(A + U) ≤ (1 + δ)μ(A). Thus

μ((S + Q)\A) ≤ δμ(A).  (2.1)

Write

S_{1} = \{s ∈ S : μ((s + Q) ∩ A) > (1 − \sqrt{δ})q, S_{2} = S\S_{1}.

We have

μ((S + Q)\A) ≥ μ((S_{2} + Q)\A) ≥ \sqrt{δ}q|S_{2}|

hence by (2.1)

q|S_{2}| ≤ \sqrt{δ}μ(A).

and so

q|S_{1}| ≥ (1 − \sqrt{δ})μ(A).  (2.2)

Define now

T_{i} = (B_{i} + Q − Q) ∩ L.

These sets satisfy

B_{i} + Q ⊂ T_{i} + Q,

hence

B_{1} + ... + B_{k} + Q ⊂ B_{1} + .. + B_{k−1} + T_{k} + Q ⊂ ... ⊂ T_{1} + ... + T_{k} + Q.  (2.3)

We apply Lemma 2.1 for the sets S_{1} and T_{i}. To do this, we need to estimate the numbers

β_{i} = |S_{1} + T_{i}|/|S_{1}|.

We have

q|S_{1} + T_{i}| = μ(S_{1} + T_{i} + Q) ≤ μ(S + T_{i} + Q)
≤ μ(A − Q + B_{i} + Q − Q + Q) ≤ μ(A + B_{i} + V 4)
≤ μ(A + B_{i} + U) ≤ (1 + δ)μ(A + B_{i}).

Taking into account (2.3) we see that

β_{i} ≤ \frac{1 + δ}{1 − \sqrt{δ}} α_{i}.

Now Lemma 2.1 gives us a nonempty set S′ ⊂ S_{1} such that

|S′ + T_{1} + ... + T_{k}| ≤ β_{1}...β_{k}|S′| ≤ (\frac{1 + δ}{1 − \sqrt{δ}} )^{k} α_{1}...α_{k}|S′|.  (2.4)

We put A′ = (S′ + Q) ∩ A. We have

μ(A′) = ∑_{s∈S′} μ((s + Q) ∩ A) ≥ (1 − \sqrt{δ})q|S′|.  (2.5)

Furthermore,

A′ + B_{1} + ... + B_{k} ⊂ S′ + Q + B_{1} + ... + B_{k} ⊂ S′ + Q + T_{1} + ... + T_{k}

by (2.3), consequently

μ(A′ + B_{1} + ... + B_{k}) ≤ μ(S′ + Q + T_{1} + ... + T_{k}) = q|S′ + T_{1} + ... + T_{k}|.

Combining this with (2.4) and (2.5) we obtain

\frac{μ(A′ + B_{1} + ... + B_{k})}{μ(A′)} ≤ \frac{(1 + δ)^{k}}{(1 − \sqrt{δ})^{k+1}} α_{1}...α_{k} < (1 + ε)α_{1}...α_{k}

if δ is chosen suitably.

If A is noncompact, we can obtain the desired result by applying the compact case for compact subsets of A.

3. Brunn-Minkowski and multiple sums

We use the classical Brunn-Minkowski inequality and the result of the previous section to estimate μ(A + B) in terms of μ(A) and μ(Bk).

Theorem 4.

Let A, B ⊂ ℝ^{d} be Borel sets, μ(B) > 0, k a positive integer. We have

μ(A + B)^{k/d} ≥ μ(A)^{k/d} + μ(A)^{(k−1)/d}μ(Bk)^{1/d}.  (3.1)

Proof. We may assume that μ(A) > 0, otherwise the statement is obvious. Assume initially also that B is compact. Choose an ε > 0. We apply Theorem 3 with B_{j} = B. This gives us a set A′ ⊂ A such that μ(A′) > 0 and

μ(A′ + Bk) ≤ (1 + ε) (\frac{μ(A + B)}{μ(A)})^{k} μ(A′).

On the other hand we have

μ(A′ + Bk)^{1/d} ≥ μ(A′)^{1/d} + μ(Bk)^{1/d}

by the Brunn-Minkowski inequality. Comparing these inequalities we obtain

μ(A′)^{1/d} + μ(Bk)^{1/d} ≤ (1 + ε) (\frac{μ(A + B)}{μ(A)})^{k/d} μ(A′)^{1/d}.

This can be rearranged as

(1 + ε)μ(A + B)^{k/d} ≥ μ(A)^{k/d} (1 + \frac{μ(Bk)}{μ(A′)})^{1/d} ≥ μ(A)^{k/d} (1 + \frac{μ(Bk)}{μ(A)})^{1/d}

since A′ ⊂ A. Since this holds for every ε > 0, we conclude that (3.1) holds.

Suppose now that B is bounded but not compact, Let A^{∗} denote the set of those points where A has density 1; we know that μ(A^{∗}) = μ(A) (even μ((A^{∗}\A)∪(A\A^{∗})) = 0 ). Let \overline{B} denote the closure of B. We claim that

μ((A^{∗} + \overline{B})\(A + B)) = 0.  (3.2)

Indeed, take any u ∈ A^{∗} +\overline{B}. We have u = a+b, a ∈ A^{∗}, b ∈ \overline{B}, and there is a sequence b_{i} → b, b_{i} ∈ B. Let R_{t} denote the ball of radius t centered at the origin. For every ε > 0 we can find δ > 0 so that

μ((a + R_{t}) ∩ A) > (1 − ε)μ(R_{t}) for 0 < t < δ.

Hence

μ((a + b_{i} + R_{t}) ∩ (A + B)) ≥ μ((a + b_{i} + R_{t}) ∩ (A + b_{i})) ≥ (1 − ε)μ(R_{t})

for all i. As i → ∞, we conclude that

μ((u + R_{t}) ∩ (A + B)) ≥ (1 − ε)μ(R_{t}),

thus A + B has density 1 at u. Therefore the set in (3.2) has density 0 at all its points, so its measure must be 0.

(3.2) implies that μ(A + B) ≥ μ(A^{∗} + \overline{B}). Applying (3.1) for the sets A^{∗} and \overline{B} we conclude its validity for A and B.

Finally, if B is not bounded, then μ(A + B) = ∞, thus (3.1) holds obviously.

4. Estimating the measure of a multiple sum

To apply Theorem 4 we need to estimate μ(Bk) in terms of μ(B) and μ(conv B).

Lemma 4.1.

Let B ⊂ ℝ^{d} be any set, C = conv B. For q > d we have

Cq = Cd + B(q − d).

This is a special case of the Shapley-Folkman theorem; see [1, Appendix 1].

Theorem 5.

Let B be a bounded Borel set of positive measure in ℝ^{d}, C = conv B. With

r = c_{1}μ(C)/μ(B),

where c_{1} depends on d, for k > r we have

μ(Bk) ≥ (k − r)^{d}μ(C).

Proof. Write μ(B) = b, μ(C) = v. Assume initially that B is compact and 0 ∈ B. Select b_{1}, ..., b_{d} ∈ B so that the volume of the simplex

R = {∑ λ_{i}b_{i} : λ_{i} ≥ 0, ∑ λ_{i} ≤ 1}

is maximal, say μ(R) = w. Since R ⊂ C, we have w ≤ v.

We claim that the parallelotope

P = {∑ λ_{i}b_{i} : |λ_{i}| ≤ 1}

contains B. Indeed, every b ∈ B has a unique representation as b = ∑ λ_{i}b_{i}. If we had |λ_{i}| > 0 for some i, then replacing b_{i} by b we would get a larger simplex than R. Observe that μ(P) = 2^{d}d!w.

Let L be the lattice generated by 2b_{1}, ..., 2b_{d}. A fundamental cell of L is

P′ = {∑ λ_{i}b_{i} : −1 < λ_{i} ≤ 1} .

Let G = ℝ^{d}/L, ψ : ℝ^{d} → G the natural homomorphism, B′ = ψ(B). Since B ⊂ P, we have μ(B′) = μ(B). By Macbeath’s theorem [2] we have

μ(B′m) ≥ min(mμ(B′), μ(G)).

Hence for

m = [1 + \frac{2^{d}d!w}{b} ]  (4.1)

we have B′m = G. This means that every x ∈ ℝ^{d} can be expressed in the form

x = v_{1} + ... + v_{m} + s_{1}b_{1} + ... + s_{d}b_{d}, v_{i} ∈ B, s_{i} ∈ ℤ.

Consider this expression for an x ∈ P. By developing x and each v_{i} in base b_{1}, ..., b_{d} and comparing the coefficient of b_{i} we see that |s_{i}| ≤ m + 1. Hence

x + (m + 1)(b_{1} + ... + b_{d}) = v_{1} + ... + v_{m} + (s_{1} + m + 1)b_{1} + ... + (s_{d} + m + 1)b_{d}.

Here the coefficients are nonnegative and their sum is at most d(2m + 2). Taking into account that 0 ∈ B, with

z = (m + 1)(b_{1} + ... + b_{d}), n = m + d(2m + 2)

we have x + z ∈ Bn. Since this is true for every x ∈ P, we have

C ⊂ P ⊂ Bn − z.

Hence for q > d we have, by virtue of Lemma 4.1 and the previous inclusion,

Cq = B(q − d) + Cd ⊂ B(q − d) + Bnd − dz = B(q + (n − 1)d) − dz.

If we apply this for q = k −(n−1)d and compare the volumes of the left and right sides, we obtain

μ(Bk) ≥ μ(Cq) = q^{d}μ(C) = (k − (n − 1)d)^{d}μ(C).

The application is justified if q > d, that is, for k > dn.

To complete the proof we have only to observe that the estimate

dn ≤ r = c_{1}w/b

follows from the definition of n and estimate (4.1) for m. A possible choice of c_{1} is d(2d + 1)(2 + 2^{d}d!).

Now the assumption 0 ∈ B can be dropped since the result is translation invariant. If B is not compact, then for every ε > 0 we can find a compact B′ ⊂ B such that μ(B′) > μ(B)−ε and μ(conv B′) > μ(conv B)−ε. Applying the result for these subsets B′ we obtain the theorem for general B.

5. Estimating the impact

Here we prove Theorem 2.

Lemma 5.1.

For x, y ≥ 0 and α ≥ 0 we have

(x + y)^{α} ≥ x^{α} + αyx^{α−1} − \frac{α}{2}y^{2}x^{α−2}.

Proof. Exercise (or see [8, Lemma 12.1]).

Proof of Theorem 2.

On substituting Theorem 5 into (3.1) we obtain

ξ(a)^{k/d} ≥ a^{k/d} + a^{(k−1)/d}(k − r)v,

valid for k > r. Lemma 5.1 with α = 1/k yields

ξ(a)^{1/d} ≥ a^{1/d} + (1 − \frac{r}{k} )v^{1/d} − \frac{(k − r)^{2}}{2k} v^{2/d}a^{−1/d} = a^{1/d} + v^{1/d}(1 − s)

with

s = \frac{r}{k} + \frac{(k − r)^{2}}{2k} (v/a)^{1/d}.

To make s small we choose

k = [r + \sqrt{r(a/v)^{1/d}}] .

This choice satisfies k > r if a > v, and it leads to

s ≤ 2\sqrt{r(v/a)^{1/d}}.

Taking into account that r ≤ c_{1}v/b, we obtain that

s ≤ c\sqrt{(v/b)(v/a)^{1/d}},

the value used in (1.4). If a ≤ v, then (assuming that c ≥ 1) (1.4) is weaker than the obvious estimate ξ(a) ≥ a. This concludes the proof of (1.4).

(1.5) follows from (1.4) and the binomial theorem.

Acknowledgement. I am grateful to Prof. M. Laczkovich for pointing out the argument used in the proof of Theorem 4 for noncompact sets.

References

[1] Ekeland, I., Temam, R., Convex analysis and variational problems, North Holland, Amsterdam 1976.

[2] Macbeath, A. M., On measure of sum sets II., Proc. Cambridge Phil. Soc. 49(1953), 40–43.

[3] Plünnecke, H., Eine zahlentheoretische Anwendung der Graphentheorie, J. Reine Angew. Math. 243(1970), 171–183.

[4] Ruzsa, I. Z., An application of graph theory to additive number theory, Scientia, Ser. A 3(1989), 97–109.

[5] Ruzsa, I. Z., Addendum to: An application of graph theory to additive number theory, Scientia, Ser. A 4(1990/91), 93–94.

[6] Ruzsa, I. Z., Diameter of sets and measure of sumsets, Monats. Math. 112(1991), 323–328.

[7] Ruzsa, I. Z., Arithmetical progressions and the number of sums, Periodica Math. Hung 25(1992), 105–111.

[8] Ruzsa, I. Z., Sets of sums and commutative graphs, Proc. of the workshop in combinatorics, Bielefeld 1991; Studia Sci. Math. Hungar. 30(1995), 127–148.

[9] Ruzsa, I. Z., Sums of finite sets, Number Theory, Proc. Conf., New York 1989, to appear. Printed 1999.2.28.