You are currently browsing the tag archive for the ‘Prekopa-Leindler inequality’ tag.

One of the fundamental inequalities in convex geometry is the Brunn-Minkowski inequality, which asserts that if {A, B} are two non-empty bounded open subsets of {{\bf R}^d}, then

\displaystyle  \mu(A+B)^{1/d} \geq \mu(A)^{1/d} + \mu(B)^{1/d}, \ \ \ \ \ (1)

where

\displaystyle  A+B := \{a+b: a \in A, b \in B \}

is the sumset of {A} and {B}, and {\mu} denotes Lebesgue measure. The estimate is sharp, as can be seen by considering the case when {A, B} are convex bodies that are dilates of each other, thus {A = \lambda B := \{ \lambda b: b \in B \}} for some {\lambda>0}, since in this case one has {\mu(A) = \lambda^d \mu(B)}, {A+B = (\lambda+1)B}, and {\mu(A+B) = (\lambda+1)^d \mu(B)}.

The Brunn-Minkowski inequality has many applications in convex geometry. To give just one example, if we assume that {A} has a smooth boundary {\partial A}, and set {B} equal to a small ball {B = B(0,\epsilon)}, then {\mu(B)^{1/d} = \epsilon \mu(B(0,1))^{1/d}}, and in the limit {\epsilon \rightarrow 0} one has

\displaystyle  \mu(A+B) = \mu(A) + \epsilon |\partial A| + o(\epsilon)

where {|\partial A|} is the surface measure of {A}; applying the Brunn-Minkowski inequality and performing a Taylor expansion, one soon arrives at the isoperimetric inequality

\displaystyle  |\partial A| \geq d \mu(A)^{1-1/d} \mu(B(0,1))^{1/d}.

Thus one can view the isoperimetric inequality as an infinitesimal limit of the Brunn-Minkowski inequality.

There are many proofs known of the Brunn-Minkowski inequality. Firstly, the inequality is trivial in one dimension:

Lemma 1 (One-dimensional Brunn-Minkowski) If {A, B \subset {\bf R}} are non-empty measurable sets, then

\displaystyle  \mu(A+B) \geq \mu(A)+\mu(B).

Proof: By inner regularity we may assume that {A,B} are compact. The claim then follows since {A+B} contains the sets {\sup(A)+B} and {A+\inf(B)}, which meet only at a single point {\sup(A)+\inf(B)}. \Box

For the higher dimensional case, the inequality can be established from the Prékopa-Leindler inequality:

Theorem 2 (Prékopa-Leindler inequality in {{\bf R}^d}) Let {0 < \theta < 1}, and let {f, g, h: {\bf R}^d \rightarrow {\bf R}} be non-negative measurable functions obeying the inequality

\displaystyle  h(x+y) \geq f(x)^{1-\theta} g(y)^\theta \ \ \ \ \ (2)

for all {x,y \in {\bf R}^d}. Then we have

\displaystyle  \int_{{\bf R}^d} h \geq \frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}} (\int_{{\bf R}^d} f)^{1-\theta} (\int_{{\bf R}^d} g)^\theta. \ \ \ \ \ (3)

This inequality is usually stated using {h((1-\theta)x + \theta y)} instead of {h(x+y)} in order to eliminate the ungainly factor {\frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}}}. However, we formulate the inequality in this fashion in order to avoid any reference to the dilation maps {x \mapsto \lambda x}; the reason for this will become clearer later.

The Prékopa-Leindler inequality quickly implies the Brunn-Minkowski inequality. Indeed, if we apply it to the indicator functions {f := 1_A, g := 1_B, h := 1_{A+B}} (which certainly obey (2)), then (3) gives

\displaystyle  \mu(A+B)^{1/d} \geq \frac{1}{(1-\theta)^{1-\theta} \theta^{\theta}} \mu(A)^{\frac{1-\theta}{d}} \mu(B)^{\frac{\theta}{d}}

for any {0 < \theta < 1}. We can now optimise in {\theta}; the optimal value turns out to be

\displaystyle  \theta := \frac{\mu(B)^{1/d}}{\mu(A)^{1/d}+\mu(B)^{1/d}}

which yields (1).

To prove the Prékopa-Leindler inequality, we first observe that the inequality tensorises in the sense that if it is true in dimensions {d_1} and {d_2}, then it is automatically true in dimension {d_1+d_2}. Indeed, if {f, g, h: {\bf R}^{d_1} \times {\bf R}^{d_2} \rightarrow {\bf R}^+} are measurable functions obeying (2) in dimension {d_1+d_2}, then for any {x_1, y_1 \in {\bf R}^{d_1}}, the functions {f(x_1,\cdot), g(y_1,\cdot), h(x_1+y_1,\cdot): {\bf R}^{d_2} \rightarrow {\bf R}^+} obey (2) in dimension {d_2}. Applying the Prékopa-Leindler inequality in dimension {d_2}, we conclude that

\displaystyle  H(x_1+y_1) \geq \frac{1}{(1-\theta)^{d_2(1-\theta)} \theta^{d_2\theta}} F(x_1)^{1-\theta} G(y_1)^\theta

for all {x_1,y_1 \in {\bf R}^{d_1}}, where {F(x_1) := \int_{{\bf R}^{d_2}} f(x_1,x_2)\ dx_2} and similarly for {G, H}. But then if we apply the Prékopa-Leindler inequality again, this time in dimension {d_1} and to the functions {F}, {G}, and {(1-\theta)^{d_2(1-\theta)} \theta^{d_2\theta} H}, and then use the Fubini-Tonelli theorem, we obtain (3).

From tensorisation, we see that to prove the Prékopa-Leindler inequality it suffices to do so in the one-dimensional case. We can derive this from Lemma 1 by reversing the “Prékopa-Leindler implies Brunn-Minkowski” argument given earlier, as follows. We can normalise {f,g} to have sup norm {1}. If (2) holds (in one dimension), then the super-level sets {\{f>\lambda\}, \{g>\lambda\}, \{h>\lambda\}} are related by the set-theoretic inclusion

\displaystyle  \{ h > \lambda \} \supset \{ f > \lambda \} + \{ g > \lambda \}

and thus by Lemma 1

\displaystyle  \mu(\{ h > \lambda \}) \geq \mu(\{ f > \lambda \}) + \mu(\{ g > \lambda \})

whenever {\lambda \leq 1}. On the other hand, from the Fubini-Tonelli theorem one has the distributional identity

\displaystyle  \int_{\bf R} h = \int_0^\infty \mu(\{h > \lambda\})\ d\lambda

(and similarly for {f,g}, but with {\lambda} restricted to {(0,1)}), and thus

\displaystyle  \int_{\bf R} h \geq \int_{\bf R} f + \int_{\bf R} g.

The claim then follows from the weighted arithmetic mean-geometric mean inequality {(1-\theta) x + \theta y \geq x^{1-\theta} y^\theta}.

In this post, I wanted to record the simple observation (which appears in this paper of Leonardi and Mansou in the case of the Heisenberg group, but may have also been stated elsewhere in the literature) that the above argument carries through without much difficulty to the nilpotent setting, to give a nilpotent Brunn-Minkowski inequality:

Theorem 3 (Nilpotent Brunn-Minkowski) Let {G} be a connected, simply connected nilpotent Lie group of (topological) dimension {d}, and let {A, B} be bounded open subsets of {G}. Let {\mu} be a Haar measure on {G} (note that nilpotent groups are unimodular, so there is no distinction between left and right Haar measure). Then

\displaystyle  \mu(A \cdot B)^{1/d} \geq \mu(A)^{1/d} + \mu(B)^{1/d}. \ \ \ \ \ (4)

Here of course {A \cdot B := \{ ab: a \in A, b \in B \}} is the product set of {A} and {B}.

Indeed, by repeating the previous arguments, the nilpotent Brunn-Minkowski inequality will follow from

Theorem 4 (Nilpotent Prékopa-Leindler inequality) Let {G} be a connected, simply connected nilpotent Lie group of topological dimension {d} with a Haar measure {\mu}. Let {0 < \theta < 1}, and let {f, g, h: G \rightarrow {\bf R}} be non-negative measurable functions obeying the inequality

\displaystyle  h(xy) \geq f(x)^{1-\theta} g(y)^\theta \ \ \ \ \ (5)

for all {x,y \in G}. Then we have

\displaystyle  \int_G h\ d\mu \geq \frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}} (\int_G f\ d\mu)^{1-\theta} (\int_G g\ d\mu)^\theta. \ \ \ \ \ (6)

To prove the nilpotent Prékopa-Leindler inequality, the key observation is that this inequality not only tensorises; it splits with respect to short exact sequences. Indeed, suppose one has a short exact sequence

\displaystyle  0 \rightarrow K \rightarrow G \rightarrow H \rightarrow 0

of connected, simply connected nilpotent Lie groups. The adjoint action of the connected group {G} on {K} acts nilpotently on the Lie algebra of {K} and is thus unimodular. Because of this, we can split a Haar measure {\mu_G} on {G} into Haar measures {\mu_K, \mu_H} on {K, H} respectively so that we have the Fubini-Tonelli formula

\displaystyle  \int_G f(g)\ d\mu_G(g) = \int_H F(h)\ d\mu_H(h)

for any measurable {f: G \rightarrow {\bf R}^+}, where {F(h)} is defined by the formula

\displaystyle F(h) := \int_K f(kg) d\mu_K(k) = \int_K f(gk)\ d\mu_K(k)

for any coset representative {g \in G} of {h} (the choice of {g} is not important, thanks to unimodularity of the conjugation action). It is then not difficult to repeat the proof of tensorisation (relying heavily on the unimodularity of conjugation) to conclude that the nilpotent Prékopa-Leindler inequality for {H} and {K} implies the Prékopa-Leindler inequality for {G}; we leave this as an exercise to the interested reader.

Now if {G} is a connected simply connected Lie group, then the abeliansation {G/[G,G]} is connected and simply connected and thus isomorphic to a vector space. This implies that {[G,G]} is a retract of {G} and is thus also connected and simply connected. From this and an induction of the step of the nilpotent group, we see that the nilpotent Prékopa-Leindler inequality follows from the abelian case, which we have already established in Theorem 2.

Remark 1 Some connected, simply connected nilpotent groups {G} (and specifically, the Carnot groups) can be equipped with a one-parameter family of dilations {x \mapsto \lambda \cdot x}, which are a family of automorphisms on {G}, which dilate the Haar measure by the formula

\displaystyle  \mu( \lambda \cdot x ) = \lambda^D \mu(x)

for an integer {D}, called the homogeneous dimension of {G}, which is typically larger than the topological dimension. For instance, in the case of the Heisenberg group

\displaystyle  G := \begin{pmatrix} 1 & {\bf R} & {\bf R} \\ 0 & 1 & {\bf R} \\ 0 & 0 & 1 \end{pmatrix},

which has topological dimension {d=3}, the natural family of dilations is given by

\displaystyle  \lambda: \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix} \mapsto \begin{pmatrix} 1 & \lambda x & \lambda^2 z \\ 0 & 1 & \lambda y \\ 0 & 0 & 1 \end{pmatrix}

with homogeneous dimension {D=4}. Because the two notions {d, D} of dimension are usually distinct in the nilpotent case, it is no longer helpful to try to use these dilations to simplify the proof of the Brunn-Minkowski inequality, in contrast to the Euclidean case. This is why we avoided using dilations in the preceding discussion. It is natural to wonder whether one could replace {d} by {D} in (4), but it can be easily shown that the exponent {d} is best possible (an observation that essentially appeared first in this paper of Monti). Indeed, working in the Heisenberg group for sake of concreteness, consider the set

\displaystyle  A := \{ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}: |x|, |y| \leq N, |z| \leq N^{10} \}

for some large parameter {N}. This set has measure {N^{12}} using the standard Haar measure on {G}. The product set {A \cdot A} is contained in

\displaystyle  A := \{ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}: |x|, |y| \leq 2N, |z| \leq 2N^{10} + O(N^2) \}

and thus has measure at most {8N^{12} + O(N^4)}. This already shows that the exponent in (4) cannot be improved beyond {d=3}; note that the homogeneous dimension {D=4} is making its presence known in the {O(N^4)} term in the measure of {A \cdot A}, but this is a lower order term only.

It is somewhat unfortunate that the nilpotent Brunn-Minkowski inequality is adapted to the topological dimension rather than the homogeneous one, because it means that some of the applications of the inequality (such as the application to isoperimetric inequalities mentioned at the start of the post) break down. (Indeed, the topic of isoperimetric inequalities for the Heisenberg group is a subtle one, with many naive formulations of the inequality being false. See the paper of Monti for more discussion.)

Remark 2 The inequality can be extended to non-simply-connected connected nilpotent groups {G}, if {d} is now set to the dimension of the largest simply connected quotient of {G}. It seems to me that this is the best one can do in general; for instance, if {G} is a torus, then the inequality fails for any {d>0}, as can be seen by setting {A=B=G}.

Remark 3 Specialising the nilpotent Brunn-Minkowski inequality to the case {A=B}, we conclude that

\displaystyle  \mu(A \cdot A) \geq 2^d \mu(A).

This inequality actually has a much simpler proof (attributed to Tsachik Gelander in this paper of Hrushovski, as pointed out to me by Emmanuel Breuillard): one can show that for a connected, simply connected Lie group {G}, the exponential map {\exp: {\mathfrak g} \rightarrow G} is a measure-preserving homeomorphism, for some choice of Haar measure {\mu_{{\mathfrak g}}} on {{\mathfrak g}}, so it suffices to show that

\displaystyle  \mu_{{\mathfrak g}}(\log(A \cdot A)) \geq 2^d \mu_{{\mathfrak g}}(\log A).

But {A \cdot A} contains all the squares {\{a^2: a \in A \}} of {A}, so {\log(A \cdot A)} contains the isotropic dilation {2 \cdot \log A}, and the claim follows. Note that if we set {A} to be a small ball around the origin, we can modify this argument to give another demonstration of why the topological dimension {d} cannot be replaced with any larger exponent in (4).

One may tentatively conjecture that the inequality {\mu(A \cdot A) \geq 2^d \mu(A)} in fact holds in all unimodular connected, simply connected Lie groups {G}, and all bounded open subsets {A} of {G}; I do not know if this bound is always true, however.

Archives

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 3,823 other followers