The Brunn-Minkowski inequality for nilpotent groups

16 September, 2011 in expository, math.GR, math.MG | Tags: Brunn-Minkowski inequality, nilpotent groups, Prekopa-Leindler inequality

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,C \subset {\bf R}}$ are non-empty measurable sets with ${A+B \subset C \subset {\bf R}}$ , then

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

Proof: By inner regularity we may assume that ${A,B}$ are compact. The claim then follows since ${C}$ 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.

25 comments

Comments feed for this article

16 September, 2011 at 1:55 pm

Deane

This is pretty cool. A consequence of the Brunn-Minkowski inequality is the isoperimetric inequality, which in turn implies sharp Sobolev inequalities. Can this chain of reasoning be used for a nilpotent Lie group, too?

16 September, 2011 at 2:12 pm

Deane

Oops. I didn’t read the full posting carefully enough. I see that this chain does break down already when trying to use Brunn-Minkowski to prove an isoperimetric inequality. Interesting…

16 September, 2011 at 4:21 pm

Fred Lunnon

Typo: In first para, for “conve bodies” read “convex bodies”

WFL

[Corrected, thanks – T.]

16 September, 2011 at 11:52 pm

Marius Buliga

In Remark 1, when $N \in (0,1)$ , the important term is $O(N^{4})$ and $N^{12}$ is lower order. I mentioned this because in the fictional correspondence between approximate groups and topological groups, large sumsets should be seen (I think) as small balls.

17 September, 2011 at 10:09 am

Terence Tao

I plan to discuss the correspondence between approximate groups and (local) groups in detail in a subsequent post (probably Lecture 5 or 6 in my course notes; it requires a certain amount of preparatory material, most notably the machinery of ultraproducts, to perform properly). But I will just make three remarks for now:

1. When N is small, the set A described above fails to be an approximate group because A.A becomes much larger than A (A has measure about N^{12}, while A.A has measure around N^4). As such, this regime is not related to the structural theory of approximate groups (and is also not close to being an extremal example for the Brunn-Minkowski inequality).

2. When N is large, the topological group associated with the approximate group A is not the Heisenberg group, but rather the Euclidean group R^3. The link is provided by the approximate homomorphism that maps $\begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}$ to $(x/N, y/N, z/N^{10})$ . The point is that this map (which behaves like a homomorphism near A) compresses almost all of the noncommutative structure of the Heisenberg group to nothingness, leaving only the residual Euclidean structure as a degenerate limit of the Heisenberg structure. (One can see this also by observing that iterated sum sets kA of A for small k grow in measure like k^3 rather than k^4, suggesting Euclidean structure at the scale of A, rather than Heisenberg structure.) Again, to formalise these statements properly one has to consider an ultraproduct of approximate groups, rather than a single approximate group; I’ll discuss this more in a future post.

3. When N is comparable to 1, then the appropriate group to associate with A is indeed the Heisenberg group (note that kA now grows like k^4 in this regime).

18 September, 2011 at 2:52 am

Marius Buliga

Thanks for the precise answer. What I wanted to say was that I expect results of the type: “the approximate group A is roughly equivalent with a small ball in the conical group B” (or to a ball in a local conical group B). That is because, probably, at some point you shall identify families of “typical” elements in large(r and larger) sum sets with elements of something having the structure of a local group.

Remarks 2. and 3. , even 1. with some modification, are an illustration of the fact that the operation of the group where the approximate group lies is not very important. Let us vary the Heisenberg group operation, for example by transporting everything by the map you mention at 2. Then, as $N$ becomes larger (there is also a play with $k$ ), the group operation becomes the one of the conical group you are after.

Your remark showed a new thing to me, namely that, how to put it, the “shape” of the approximate group chooses the right dilations in the conical group from the limit, as a principle.

18 September, 2011 at 9:37 am

Terence Tao

Yes, the asymptotic group that models an approximate group depends quite sensitively on the “shape” of that approximate group, which ends up being more important in many ways than the ambient group that the approximate group lives in.

In some cases, the asymptotic group model does not have an easy interpretation as a “conical” limit, because the approximate homomorphisms involved are only locally defined rather than globally defined. To give an example, take the ambient group $G = ({\bf R}, +)$ , and let A be the set

$A = [0,1] \cup [N,N+1] \cup [2N,2N+1] \cup \ldots \cup [N^2-N,N^2-N+1]$

which is the union of N equally spaced unit intervals, with the spacing between intervals being comparable to N, where N is a large integer. (Actually, this is not quite an approximate group because, by definition, such groups are supposed to be symmetric around the origin, but one can easily modify the above example to be symmetric by a suitable translation.) In this case, the asymptotic group that models A is actually ${\bf R}^2$ , and the approximate homomorphism that links A (as well as iterated sumsets $kA=A+\ldots+A$ for small k) to this asymptotic group is given by the map $\phi: aN + b \mapsto (\frac{a}{N}, b)$ for a an integer of size O(N), and b a real of size O(1). Note that in this example kA grows quadratically in k for small k (though it eventually reverts to linear growth for $k \gg N$ ), which is consistent with the two-dimensionality of the asymptotic group. Thus we see here that due to the disconnected nature of A, the asymptotic group model ends up having larger dimension than the ambient group, making it difficult to interpret the former as a conical limit of the latter. So conical limits are certainly one type of example of asymptotic group model of an approximate group, but it turns out that they are not fully representative of this concept.

(Note also that in this case the approximate homomorphism $\phi$ is only locally defined in some portions of ${\bf R}$ , but not globally defined on all of ${\bf R}$ . This hints at the fact that the category of local groups is a slightly more natural category to study approximate groups than the category of global groups. Indeed, one can view ${\bf R}^2$ as emerging as a Gromov-Hausdorff limit of certain “local dilations” of ${\bf R}$ if one wishes, and so one can in some sense recover a rather strange, local interpretation of “conical limit” with which to try to understand the concept of an asymptotic group model.)

18 September, 2011 at 11:53 pm

Marius Buliga

Nice example, the one with $\mathbb{R}^{2}$ , which is a conical group, but I look forward for your future posts to understand exactly how “shape” chooses the right dilations (or where I am wrong, quite possibly).

Concerning the matter of local groups versus conical groups, for me all structures, groups and dilations included, are local and only by chance they become global. By definition a (local) conical group is a left distributive uniform idempotent right quasigroup (aka “linear dilation structure”) see arXiv:1005.5031 and references. The (family of) operation(s) of the quasigroup (indexed by a commutative group with an absolute) are the dilations, which generate the (local) group operation by a precise recipe.

In this (maybe strange) language, the solution of the Hilbert’ 5th problem is that a topological, locally compact, local group admits a a left invariant, linear dilation structure such that the tangent space at identity (in the sense of dilation structures) has the algebraic structure of a commutative conical group. There are many other interesting, or relevant dilation structures, beside this one. Many more “analyses” than the well-known one, say.

19 September, 2011 at 8:29 am

Terence Tao

There are examples in which the asymptotic model group does not have a dilation structure. For instance, if we modify the previous example by setting $G = ({\bf R},+)$ and

$A = [0,1] \cup [10,11] \cup [20,21] \cup \ldots \cup [10 N - 10, 10N-9]$

then the model group is now a cylinder ${\bf R} \times {\bf R}/{\bf Z}$ , with the approximate homomorphism mapping $10a+b$ to $(\frac{a}{N}, \frac{b}{10})$ for $a = O(N)$ and $0 \leq b < 10$ . Here, A is approximately mapped onto the rectangle $[0,1] \times [0,\frac{1}{10}]$ . Note that the dilates kA exhibit quadratic growth up to k=10, and then linear growth for larger values of k.

On the other hand, the slightly larger set 10A can be safely modeled by ${\bf R}$ . One of the theorems we will show later is that if A is an approximate group in an arbitrary ambient group, then for some sufficiently large k, kA can be modeled by a connected, simply connected Lie group, which can be taken to be nilpotent if A was discrete. These groups however need not have a dilation structure. For instance, if one picks a Lie group at random, say G = SL_2(R), and lets A be the unit ball in G (wrt some metric, say a smooth Riemannian left-invariant one), then A is an approximate group which is its own model; the growth of iterates A^k of A is not controlled by any Lie group that is more "primitive" than SL_2(R), and this group has no obvious dilation structure.

17 September, 2011 at 12:25 am

Florian

Something is wrong in (3) or its conclusion: you take (3) to the power 1/d to get the estimate for $\mu(A+B)^{1/d}$, but you don’t take $\mu(A)$ and $\mu(B)$ to the power 1/d.

[Corrected, thanks – T.]

19 September, 2011 at 11:42 pm

Marius Buliga

Re: “if A is an approximate group in an arbitrary ambient group, then for some sufficiently large k, kA can be modeled by a connected, simply connected Lie group, which can be taken to be nilpotent if A was discrete.” I look forward to see the proof! I bet that such a group has an action by a commutative group (like $(\mathbb{Z}, +)$ or $(\mathbb{R}, +)$ by automorphisms, which is contracting in some sense.
This is compatible with your two examples from previous comments (for $k$ large).

Or maybe is just lack of imagination on my side. The trick of dilation structures should be just the tip of an aisberg. It already covers manifolds, symmetric spaces, riemannian and sub-riemannian structures, some p-adic (and tree-like) structures, BUT all these objects are already constructed. Your work, coming from the finite towards the infinite objects, could show how these and many other such objects appear in the limit, that is why I am fascinated by your “finitary” program.

Re: the group $SL_{2}(\mathbb{R})$ , it is a Lie group, therefore it has a trivial dilation structure, given by transport on the group of the multiplication by positive scalars on the algebra (the solution of H5 problem), but indeed, it is not clear if it is of any relevance for the problem at hand.

Looks maybe as a king of degenerate situation: take a group $G$ and a “full” set inside $A = G$ , then $A$ is its own model.

What about taking the subset $A$ , seen in the algebra (pick 3 generators and see $A$ as a subset of $\mathbb{R}^{3}) to have the form$ latex [-1,1]^{\alpha}\times [-1,1]^{\alpha} \times [-1,1]^{\beta}$, with $\beta = \alpha^{m}$ , then what happens as $\alpha$ is small(er and smaller)? Are there also three regimes w.r.t. to the choice of $m$ ?

20 September, 2011 at 9:15 am

Terence Tao

I think nilpotent-with-dilation (i.e. Carnot) type structures appear for discrete approximate groups when one looks at the asymptotic limit of kA either at very coarse scales $k \to \infty$ , or also at very fine scales $k \to 0$ , but when working at medium scales $k \sim 1$ (which is the case of interest to additive combinatorics) one only sees nilpotent structure and not the dilations.

(Here one has to define $kA$ for fractional k in a suitable sense. The precise definition is complicated, but as a first approximation, one can think of $\frac{1}{n} A$ as those elements $g$ such that $g,\ldots,g^n$ all lie in $A$ . Note that this gives Euclidean (or more precisely, Lie algebra) structure in the limit rather than Carnot structure, in contrast to Pansu’s theorem. Thus, the behaviour of kA exhibits three regimes: Euclidean/Lie algebra structure at fine scales, Lie group structure at medium scales, and Carnot group structure at large scales.)

For instance, take a 3-step nilpotent Lie algebra ${\mathfrak g}$ that has rational structure coefficients wrt some Mal’cev basis $e_{1,1},\ldots,e_{1,r_1}, e_{2,1},\ldots,e_{2,r_2}, e_{3,1},\ldots,e_{3,r_3}$ but is not homogeneous (thus, for instance, a Lie bracket $[e_{1,i}, e_{1,j}]$ of the 1-step generators may involve both the 2-step generators $e_{2,k}$ and the 3-step generators $e_{3,k}$ , in contrast to a Carnot group when only the 2-step generators are involved. One can exponentiate this to obtain a connected simply connected 3-step nilpotent group G. Inside this group G, one can build a discrete approximate group A consisting of all elements of the form

$e_{1,1}^{a_{1,1}} \ldots e_{3,r_3}^{a_{3,r_3}}$

where each $a_{i,j}$ is an integer multiple of $N^{-i}$ of magnitude at most 1. (Technically, this is not quite an approximate group because A is not perfectly symmetric, but it is close enough to being one for the purpose of this discussion.) In the limit $N \to \infty$ , this group A is modeled by a “unit cube” in G, which is defined similarly to A except that the $a_{i,j}$ now range in the continuous interval [-1,1] rather than a discretisation thereof. Because we are not taking an asymptotic limit to very fine scales or very coarse scales, we don’t get to take a Pansu-like scaling limit to pass from the nilpotent group G to its associated Carnot group (or to its Lie algebra, depending on which way one is taking the scaling.)

This distinction in behaviour is part of a broader distinction between single-scale analysis and asymptotic analysis, which I discuss at https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/

Broadly speaking, the objects obtained in asymptotic analysis tends to be more symmetric and invariant than their single-scale counterparts, and as such, the former does not fully capture the behaviour of the latter, although it often describes the “main term” or the “principal behaviour” in some sense.

20 September, 2011 at 11:10 am

Marius Buliga

Re: “when one looks at the asymptotic limit of kA either at very coarse scales , or also at very fine scales , but when working at medium scales (which is the case of interest to additive combinatorics) one only sees nilpotent structure and not the dilations.” Very interesting, I have to think and come back later. However, only two comments:

1. Your proof of the Brunn-Minkowski inequality shows that: (a) as expected, (the Haar) measure is related to the counting measure (is like counting an infinity of elements) and (b) as you say at the end of your Remark 1., the inequality does not feel the metric dimension, so it says to me that the measure itself is not fine enough, it is “commutative” somewhere deep inside. As a kind of consequence, this is an argument for counting not being geometrical enough, at asymptotic scales at least.

2. Let’s suppose that in the asymptotic regime, indeed, appears a conical group structure (Carnot or other, like 2-adic (??)). Then, you have the so much discussed dilations, take one (of nontrivial coefficient). In some sense, there is a “finitary” version of it, accept you have it. Surely, from a combinatorial point of view, it should be very complex (maybe there is no algorithm to define it, only in some specific classes of examples). Why? Because it simplifies very much the addition of “big” elements (apply the dilation and get much smaller elements; add them and then apply the inverse dilation to the result and then proceed to refine this almost exact result). That is why I would be very very interested (I try this anyway) to find out if there is any way to prove the existence (maybe non-constructively) of the finitary shadow of the dilations. I know it goes against the effort of giving quantitative proofs, but it brings geometry into the matter.

21 September, 2011 at 9:01 am

Marius Buliga

Re: “(Here one has to define kA for fractional k in a suitable sense. The precise definition is complicated, but as a first approximation, one can think of \frac{1}{n} A as those elements g such that g,\ldots,g^n all lie in A. Note that this gives Euclidean (or more precisely, Lie algebra) structure in the limit rather than Carnot structure, in contrast to Pansu’s theorem.”

Trivial example:

Take $G= \mathbb{Z}^{3}$ with the Heisenberg group operation $(a,b,c) \cdot (a',b',c') = (a+a',b+b',c+c'+ab'-a'b)$ and $A(N) = \left\{(a,b,c) \in G \mbox{ : } \mid a \mid \leq N , \mid b \mid \leq N , \mid c \mid \leq N^{2} \right\}$ . The set $A(N)$ is an approximate group and, by your definition, for $n \in \mathbb{N}^{*}$, that $\frac{1}{n} A(N) = \left\{ (a,b,c) \in G \mbox{ : } \mid a \mid \leq \frac{N}{n}, \mid b \mid \leq \frac{N}{n} , \mid c \mid \leq \frac{N^{2}}{n} \right\}$, which is far from $A(\frac{N}{n})$ . That is why, in the limit “this gives Euclidean …”.

Define $n \cdot (a,b,c) =(n a, n b, n^{2} c)$, then $n \cdot A(\frac{N}{n}) = A(N)$. This is the “true” self-similarity in this case. As you see, the definition of it is not easy to write, in the sense that if I give you an element $y$ of $n A(N) \subset A(nN)$ , written as a word with $n$ letters from $A$ , it is far from obvious to tell how to produce the element $x$ of $A(N)$ such that $n \cdot x$ is closest to $y$ .

24 September, 2011 at 2:40 am

Marius Buliga

Excuses for the typos in latex, I can’t see the final look of the comment before submitting.

Shortly said, what I believe is that the result of Breuillard and Green
arXiv:0906.3598, saying that approximate groups in Carnot groups are controlled by nilboxes, is true (in some asymptotic regimes maybe) in a more general situation, i.e. without supposing that the ambient group is nilpotent or even without any ambient group hypothesis (other than the ones which can be turned into hypotheses on the approximate group itself).

My hope is that it is possible to prove this from the start, without invoking a Gromov theorem & Hilbert 5 problem (in order to construct the ambient somehow). One way would be to prove that there are some families of dilations (i.e. some “homomorphisms” of “nilboxes”) and only in the end prove by abstract nonsense that in some limit the “nilboxes” have to be really nilboxes and so on.

Or, there is another thing maybe, turn the reasoning upside up and use Breuillard-Green like result to prove that any approximate group which is roughly equivalent with a nilbox has some dilations (in a rough sense), then quantify the complexity of such objects by estimating how much the use of said dilations simplify the word problem.

I have a strong feeling that your program on H5 problem and approximate groups is close to these ideas.

20 September, 2011 at 8:37 am

sjt

Do “connected” and “simply connected” mean the same thing for Lie groups as they do for general topological spaces? (I ask because if so, saying both is redundant, violating some Gricean maxim or other.)

20 September, 2011 at 8:57 am

Terence Tao

I think there may be competing definitions in the literature; in some texts, a Lie group is simply connected iff every closed loop is contractible, whereas in other texts, one also imposes connectedness. Thus, for instance, a discrete group could be considered a simply connected Lie group in some of the literature. So it is common to add “connected” to “simply connected” for emphasis. (Conversely, one could call a disconnected Lie group with all closed loops contractable a “Lie group with simply connected identity component”, again to avoid ambiguity.)

22 September, 2011 at 1:32 pm

sjt

I see. Thanks for explaining.

20 September, 2011 at 11:42 am

Twelfth Linkfest

[…] Terence Tao: The inverse function theorem for everywhere differentiable maps, The Brunn-Minkowski inequality for nilpotent groups […]

25 September, 2011 at 8:22 am

Jeff

One of the seemingly unexplored encodings of 3x+1 sequences is via irregular convex polygons. One can take sequences convergent to the number 1 and let the number of odds in such sequences denote the vertices, while letting the running sum of evens denote the lengths of the edges. From there all of the obvious questions arise i.e., what subset of irregular polygons map to the 3x+1 sequences? Do all such sequences close under the encoding? Comparison of extremal values and statistics should be done. One may want to know under what conditions the minimal area enclosed of such a 5-gon is smaller than a 4-gon from such a set of irregular n-gons. Where is creativity when you need it most?

28 September, 2011 at 10:50 am

fren

Nilpotent Prékopa-Leindler inequality, wow :) Leindler was my professor in two functional analysis courses

16 November, 2011 at 12:54 am

Dan

It seems that in the last step of the proof (in dimension one) of the Prekopa Leindler inequality
the Holder inequality CANNOT be used since it is in the reverse order.
It seems you prove something slightly weaker than the inequality wanted.
in fact $\int \mu(f>\lambda)^{1-\theta}\mu(g>\lambda)^{\theta}d\lambda <(\int f)^{1-\theta}(\int g)^{\theta} d\lambda$ .

16 November, 2011 at 8:43 am

Terence Tao

Ah, I had accidentally swapped the last two steps of the argument. It should be fixed now.

24 April, 2013 at 8:02 am

Anonymous

If in equation (2) we take h=0, g=0 and f=1, then the arithmetic version of Prekopa-Leindler inequality at the end of the proof of Theorem 2, right above Theorem 3, seems not correct.

[Corrected, thanks – there was a missing step in the proof in which one normalised f and g to have sup norm 1. -T.]

10 March, 2017 at 12:07 pm

Anonymous

In lemma 1 , the sum of two measurable subsets of R need not be measurable

[Fair enough; I’ve reworded the lemma. -T.]

	Author Spotlight: A… on Lewis Carroll logic puzzl…
	Aubrey Wiederin on Generalisations of the limit…
	Discotech on 275A, Notes 4: The central lim…
	Why -1/12? – M… on The Euler-Maclaurin formula, B…
	WrongAdvice on Career advice
	Sergei Ofitserov on PCMI lecture notes on random m…
	Stefan Kohl on Long gaps between primes
	FIELDS MEDAL 2018 on Avila, Bhargava, Hairer, …
	Writing 101 \| Snowdr… on On writing
	TheoryFest Day 3: Pl… on A symmetric formulation of the…
	Anonymous on 245A, Notes 1: Lebesgue m…
	Anonymous on 245A, Notes 1: Lebesgue m…
	Terence Tao on 275A, Notes 2: Product measure…
	Terence Tao on Computing convolutions of…
	Terence Tao on 254B, Notes 1: Equidistributio…

The Brunn-Minkowski inequality for nilpotent groups

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

25 comments

Leave a Reply Cancel reply

For commenters

The Brunn-Minkowski inequality for nilpotent groups

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

25 comments

Leave a Reply Cancel reply

For commenters