Isoperimetric inequality on groups

Conan5 Comments

Back in high school, we have all learned and loved the isoperimetric inequality: “If one wants to enclose a region of area \pi on the plane, one needs a rope of length at least 2 \pi.” or equivalently, given U \subseteq \mathbb{R}^2 bounded open, we always have

\ell(\partial U) \geq 2 \sqrt{\pi} \sqrt{\mbox{Area}(U)}

Of course this generalizes to \mathbb{R}^n:

Theorem: Given any open set U \subseteq \mathbb{R}^n, we have

\mbox{vol}_{n-1}\partial (U) \geq n\cdot \omega_n^{1/n} \mbox{vol}_n(U)^{\frac{n-1}{n}}

Here \omega_n is the volume of the unit n-ball. Note that the inequality is sharp for balls in \mathbb{R}^n.

One nature question to ask should be: for which other kind of spaces do we have such an inequality. i.e. when can we lower bound the volume of the boundary by in terms of the volume of the open set? If such inequality exists, how does the lower bound depend on the volume of the set?

I recently learned to produce such bounds on groups:
Let G be a discrete group, fix a set of generators and let C_G be its Cayley graph, equipped with the word metric d.

Let N(R) = |B_R(e)| be the cardinality of the ball of radius R around the identity.

For any set U \subseteq G, we define \partial U = \{g \in G \ | \ d(g, U) = 1 \} i.e. points that’s not in U but there is an edge in the Cayley graph connecting it to some point in U.

Theorem:For any group with the property that N(R) \geq c_n R^n, then for any set U \subseteq G with |U| \leq \frac{1}{2}|G|,

|\partial U| \geq c_n |U|^{\frac{n-1}{n}}.

i.e. If the volume of balls grow (w.r.t. radius) as fast as what we have in \mathbb{R}^n, then we can lower bound the size of boundary any open set in terms of its volume just like what we have in \mathbb{R}^n.

Proof: We make use of the fact that right multiplications by elements of the group are isometries on Cayley graph.

Let R = (\frac{2}{c_n}|U|)^\frac{1}{n}, so we have |B_R(e)| \geq 2|U|.

For each element g \in B_R(e), we look at how many elements of U went outside of U i.e. | Ug \backslash U|. (Here the idea being the size of the boundary can be lower bounded in terms of the length of the translation vector and the volume shifted outside the set. Hence we are interested in finding an element that’s not too far away from the identity but shifts a large volume of U outside of U.)

The average value of |Ug \backslash U| as g varies in the ball B_R(e) is:

\displaystyle \frac{1}{|B_R(e)|} \sum_{g\in B_R(e)} |Ug \backslash U|

The sum part is counting the elements of U that’s translated outside U by g then sum over all g \in B_R(e), this is same as first fixing any u \in U, count how many g sends u outside U, and sum over all u \in U ( In fact this is just Fubini, where we exchange the order of two summations ). “how mant g \in B_R(e) sends u outside of U” is merely |uB_R(e) \backslash U|.

Hence the average is

\displaystyle \frac{1}{|B_R(e)|} \sum_{u\in U}|uB_R(e) \backslash U|.

But we know |B_R(e)| \geq 2 \cdot |U|, hence |uB_R(e) \backslash U| is at least \frac{1}{2}|B_R(e)|.

Hence

\displaystyle \frac{1}{|B_R(e)|} \sum_{u\in U}|uB_R(e) \backslash U|

\geq \frac{1}{|B_R(e)|} \cdot |U| \cdot \frac{1}{2} |B_R(e)| = \frac{1}{2} |U|

Now we can pick some g \in B_R(e) where |Ug \backslash U| \geq \frac{1}{2}|U| (at least as large as average).

Since g has norm at most R, we can find a word g_1 g_2 \cdots g_k = g, \ k \leq R.

For any ug \in (Ug \backslash U), since u \in U and ug \notin U, there must be some 1\leq i\leq k s.t. u(g_1\cdots g_{i-1}) \in U and u(g_1\cdots g_i) \notin U.

Hence u g_1 \cdots g_i \in \partial U, ug \in \partial U \cdot g_{i+1} \cdots g_k.

We deduce that \displaystyle Ug \backslash U \subseteq \partial U \cup \partial U g_k \cup \cdots \cup \partial U g_2 \cdots g_k i.e. a union of k copies of \partial U.

Hence R |\partial U| \geq k |\partial U| \geq |Ug \backslash U| \geq \frac{1}{2}|U|

|\partial U| \geq \frac{|U|}{2R}

Since |B_R(e)| \geq c_n R^n, we have R \leq c_n |B_R(e)|^{\frac{1}{n}}. R = (\frac{2}{c_n}|U|)^\frac{1}{n} = c_n |U|^\frac{1}{n}, hence we have

|\partial U| \geq c_n |U|^\frac{n-1}{n}

Establishes the claim.

Remark: The same argument carries through as long as we have a lower bound on the volume of balls, not necessarily polynomial. For example, on expander graphs, the volume of balls grow exponentially: B_R(e) \geq c \cdot e^R, then trancing through the argument we get bound

|\partial U| \geq c \cdot \frac{|U|}{\log{|U|}}

Which is a very strong isoperimetric inequality. However in fact the sharp bound for expanders is |\partial U| \geq c \cdot |U|. But to get that one needs to use more information of the expander than merely the volume of balls.

On the same vein, we can also prove a version on Lie groups:

Theorem:Let G be a Lie group, g be a left invariant metric on G. If \mbox{vol}_n(B_R) \geq c_n R^n then for any open set U with no more than half of the volume of G,

\mbox{vol}_{n-1}(\partial U) \geq c_n \mbox{vol}_n(U)^\frac{n-1}{n}.

Note that to satisfy the condition \mbox{vol}_n(B_R) \geq c_n R^n, our Lie group must be at least n-dimensional since if not the condition would fail for small balls. n might be strictly larger than the dimension of the manifold depending on how ‘neigatively curved’ the manifold is in large scale.

Sketch of proof: As above, take a ball twice the size of the set U around the identity, say it’s B_R(e). Now we consider all left translates of the set U by element in B_R(e). In average an element shifts at least half of U outside of U. Pick element g where \mbox{vol}(gU \backslash U) is above average.

Let \gamma: [0, ||g||] be a unit speed geodesic connecting e to g. Consider the union of left translates of \partial U by elements in \gamma([0, ||g||]), this must contain all of gU \backslash U since for any gu \notin U the segment \gamma([0,||g||]) \cdot u must cross the boundary of U, i.e. there is c \in [0,||g||] where \gamma(c) u \in \partial U, hence

g\cdot u = \gamma(||g||) \cdot u = \gamma(||g||-c)\gamma(c) u \in \gamma(||g||-c) \cdot \partial U

But since the geodesic has derivative 1, the n-dimensional volume of the union of those translates is at most \mbox{vol}_{n-1}(\partial U) \cdot ||g||.

We have \mbox{vol}_{n-1}(\partial U) \cdot R \geq \mbox{vol}_n(gU \backslash U) \geq \mbox{vol}_n(U)/2

Now since we have growth condition

2\mbox{vol}_n(U) = \mbox{vol}_n(B_R) \geq c_n R^n

i.e. R \leq c_n \mbox{vol}_n(U)^\frac{1}{n}.

Conbine the two inequalities we obtain

\mbox{vol}_{n-1}(\partial U) \geq c_n \mbox{vol}_n(U)^\frac{n-1}{n}.

Establishes the theorem.

Remark: In general, this argument produces a lower bound on the size of the boundary in terms of the volume of the set as long as:
1. There is a way to ‘continuously translate’ the set by elements in the space.
2. We have a lower bound on the growth of balls in terms of radius.

The key observation is that the translated set minus the original set is always contained in a ‘flattened cylinder’ of the boundary in direction of the translate, which then has volume controlled by the boundary size and the length of the translating element. Because of this, the constant is almost never strict as the difference (translate subtract original) can never be the whole cylinder (in case of a ball, this difference is a bit more than half of the cylinder).

5 thoughts on “Isoperimetric inequality on groups”

    • For the argument I think one only need the volume of U is no more than 1/2 the volume of the whole Lie group. (Otherwise there is no ball with twice the volume) So you are right, I should put a condition (in fact on both cases) that the size of the open set cannot be more than 1/2 the total size of the space. ^_^ thanks

      However, it does make sense to only consider those sets since the boundary of the complement is essentially the boundary of the set, so of course one should bound the size of the boundary by the smaller set it encloses.

      To the second question, even manifolds with constant negative curvature can have thin Margulis tubes, hence forming an open set with boundary only cutting through the tubes will give large volume with arbitrarily small boundary. perhaps, after lifting to the universal cover something would hold.

      Like

      Reply

  4. Hi Conan,
    thanks for the very nice post! Do you know who is(are) the author(s) of the very nice “probabilistic” argument giving the isoperimetric inequality on Cayley graphs? Or simply a bibliographic reference for it?

    Like

    Reply

Leave a comment