Graph, girth and expanders

Conan2 Comments

In the book “Elementary number theory, group theory and Ramanujan graphs“, Sarnak et. al. gave an elementary construction of expander graphs. We decided to go through the construction in the small seminar and I am recently assigned to give a talk about the girth estimate of such graphs.

Given graph (finite and undirected) G, we will denote the set of vertices by V(G) and the set of edges E(G) \subseteq V(G)^2. The graph is assumed to be equipped with the standard metric where each edge has length 1.

The Cheeger constant (or isoperimetric constant of a graph, see this pervious post) is defined to be:

\displaystyle h(G) = \inf_{S\subseteq V_G} \frac{|\partial S|}{\min\{|S|, |S^c|\}}

Here the notation \partial S denote the set of edges connecting an element in S to an element outside of S.

Note that this is indeed like our usual isoperimetric inequalities since it’s the smallest possible ratio between size of the boundary and size of the set it encloses. In other words, this calculates the most efficient way of using small boundary to enclose areas as large as possible.

It’s of interest to find graphs with large Cheeger constant (since small Cheeger constant is easy to make: take two large graphs and connect them with a single edge).

It’s also intuitive that as the number of edges going out from each vertice become large, the Cheeger constant will become large. Hence it make sense to restrict ourselves to graphs where there are exactly k edges shearing each vertex, those are called k-regular graphs.

If you play around a little bit, you will find that it’s not easy to build large k-regular graphs with Cheeger constant larger than a fixed number, say, 1/10.

Definition: A sequence of k-regular graphs (G_i) where |V_{G_i}| \rightarrow \infty is said to be an expander family if there exists constant c>0 where h(G_i) \geq c for all i.

By random methods due to Erdos, we can prove that expander families exist. However an explicit construction is much harder.

Definition: The girth of G is the smallest non-trivial cycle contained in G. (Doesn’t this smell like systole? :-P)

In the case of trees, since it does not contain any non-trivial cycle, define the girth to be infinity.

The book constructs for us, given pair p, q of primes where p is large (but fixed) and q \geq p^8, a graph (p+1)-regular graphX^{p,q} with

\displaystyle h(X^{p,q}) \geq \frac{1}{2}(p+1 - p^{5/6 + \varepsilon} - p^{1/6-\varepsilon})

where 0 < \varepsilon < 1/6.

Note that the bound is strictly positive and independent of q. Giving us for each p, (X^{p,q}) as q runs through primes larger than p^8 is a (p+1)-regular expander family.

In fact, this constructs for us an infinite family of expander families: a (k+1)-regular one for each prime k and the uniform bound on Cheeger constant gets larger as k becomes larger.

One of the crucial step in proving this is to bound the girth of the graph X^{p,q}, i.e. they showed that g(X^{p,q}) \geq 2 \log_p(q) and if the quadratic reciprocity (\frac{p}{q}) = -1 then g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4). This is what I am going to do in this post.

Let \mathbb H ( \mathbb Z) be the set of quaternions with \mathbb Z coefficient, i.e.

\mathbb H ( \mathbb Z) = \{ a+bi+cj+dk \ | \ a,b,c,d \in \mathbb Z \}

Fix odd prime p, let

\Lambda' = \{ \alpha \in \mathbb H(\mathbb Z) \ | \ \alpha \equiv 1 (mod 2) \}

\cup \ \{\alpha \in \mathbb H(\mathbb Z) \ | \ N(\alpha) = p^n \ \mbox{and} \ \alpha \equiv i+j+k (mod 2) \}

where the norm N on \mathbb H(\mathbb Z) is the usual N(a+bi+cj+dk) = a^2 + b^2 +c^2+d^2.

\Lambda' consists of points with only odd first coordinate or points lying on spheres of radius \sqrt{p^n} and having only even first coordinate. One can easily check \Lambda' is closed under multiplication.

Define equivalence relation \sim on \Lambda' by

\alpha \sim \beta if there exists m, n \in \mathbb{N} s.t. p^m \alpha = \pm p^n \beta.

Let \Lambda = \Lambda' / \sim, let Q: \Lambda' \rightarrow \Lambda be the quotient map.

Since we know \alpha_1 \sim \alpha_2, \beta_1 \sim \beta_2 \Rightarrow \alpha_1\beta_1 \sim \alpha_2\beta_2, \Lambda carries an induced multiplication with unit.

In elementary number theory, we know that the equation a^2+b^2+c^2+d^2 = p has exactly 8(p+1) integer solutions. Hence the sphere of radius p in \mathbb H(\mathbb Z) contain 8(p+1) points.

In each 4-tuple (a,b,c,d) exactly one is of a different parity from the rest, depending on whether p\equiv1 or 3 (mod 4). Restricting to solutions where the first coordinate is non-negative, having different parity from the rest (in case the first coordinate is 0, we pick one of the two solutions \alpha, -\alpha to be canonical), this way we obtain exactly p+1 solutions.

Let S'_p = \{ \alpha_1, \bar{\alpha_1}, \cdots, \alpha_k, \bar{\alpha_k}, \beta_1, \cdots, \beta_l \} be this set of p+1 points on the sphere. Note that the \betas represent the solutions where the first coordinate is exactly 0.

Check that S'_p generates \Lambda'.

We have \alpha_i \bar{\alpha_i} = p and -\beta_j^2 = p. By definition S'_p \subseteq \Lambda' and Q is injective on S'_p. Let S_p = Q(S'_p).

Consider the Cayley graph \mathcal G (\Lambda, S_p), this is a (p+1)-regular graph. Since S_p generares \Lambda, \mathcal G (\Lambda, S_p) is connected.

Claim: \mathcal G (\Lambda, S_p) is a tree.

Suppose not, let (v_0, v_1, \cdots, v_k=v_0) a non-trivial cycle. k \geq 2. Since \mathcal G is a Cayley graph, we may assume v_0 = e.

Hence v_1 = \gamma_1, \ v_2 = \gamma_1\gamma_2, \cdots, v_k = \gamma_1 \cdots \gamma_k, for some \gamma_1, \cdots, \gamma_k \in S_p.

Since v_{i-1} \neq v_{i+1} for all 1\leq i \leq k-1, the word \gamma_1, \cdots, \gamma_k cannot contain either \alpha_i\bar{\alpha_i} or \beta_i^2, hence cannot be further reduced.

\gamma_1, \cdots, \gamma_k = e in \Lambda means for some m, n we have

\pm p^n \gamma_1, \cdots, \gamma_k = p^m.

Since every word in \Lambda' with norm N(\alpha) = p^k must have a unique factorization \alpha = \pm p^r w_m where w_m is a reduces word of length m in S'_p and 2r+m = k.

Contradiction. Establishes the claim.

Now we reduce the group \mathbb H (\mathbb Z) mod q:

\pi_q: \mathbb H (\mathbb Z) \rightarrow \mathbb H (\mathbb{F}_q)

One can check that \pi_q(\Lambda') = \mathbb H (\mathbb{F}_q)^\times.

Let Z_q = \{ \alpha \in \mathbb H (\mathbb{F}_q)^\times \ | \ \alpha = \bar{\alpha} \}, Z_q < \mathbb H (\mathbb{F}_q)^\times is a central subgroup.

For \alpha, beta \in \Lambda', \alpha \sim \beta \Rightarrow \pi_q(\alpha)^{-1}\pi_q(\beta) \in Z_q. Which means we have well defined homomorphism

\Pi_q: \Lambda \rightarrow \mathbb H (\mathbb{F}_q)^\times / Z_p.

Let T_{p,q} = \Pi_q(S_p), if q > 2\sqrt{q} we have \Pi_q is injective on S_p and hence $latex | T_{p,q} | = p+1.

Now we are ready to define our expanding family:

X^{p,q} = \mathcal{G}( \Pi_q(\Lambda), T_{p,q}).

Since S_p generates \Lambda, T_{p,q} generates \Pi_q(\Lambda). Hence X^{p,q} is (p+1)-regular and connected.

Theorem 1: g(X^{p,q}) \geq 2 \log_p(q)

Let (e, v_1, \cdots, v_k=e) be a cycle in X^{p,q}, there is t_1, \cdots, t_k \in T_{p,q} such that v_i = t_1 t_2 \cdots t_k for 1 \leq i \leq k.

Let \gamma_i = \Pi_q^{-1}(t_i), \ \gamma_i \in S_p, \alpha = a_0 + a_1 i+a_2 j +a_3 k = \gamma_1 \cdots \gamma_k \in \Lambda. Note that from the above arguement we know \alpha is a reduced word, hence \alpha \neq e_{\Lambda}. In particular, this implies a_1, a_2, a_3 cannot all be 0.

Also, since \alpha is reduced, \displaystyle N(\alpha) = \Pi_{i=1}^k N(\gamma_i) = p^k.

By Lemma, since \Pi_q(\alpha) = 1, \alpha \in \mbox{ker}(\Pi_q) hence q divide a_1, a_2, a_3, we conclude

N(\alpha) = a_0^2 + a_1^2 +a_2^2 +a_3^2 \geq q^2

We deduce p^k \geq q^2 hence k \geq \log_p(q) for all cycle. i.e. g(X^{p,q}) \geq \log_p(q).

Theorem 2: If q does not divide p and p is not a square mod q (i.e. (\frac{p}{q}) = -1), then g(X^{p,q}) \geq 4 \log_p(q) - \log_p(4).

For any cycle of length k as above, we have N(\alpha) = p^k \equiv a_0^2 (\mbox{mod} \ q), i.e. (\frac{p^k}{q}) = 1.

Since (\frac{p^k}{q}) = ((\frac{p}{q})^k, we have (-1)^k = 1, \ k is even. Let k = 2l.

Note that p^k \equiv a_0^2 (\mbox{mod} \ q^2), we also have

p^{2l} \equiv a_0^2 (\mbox{mod} \ q^2)

Hence p^l \equiv a_0 (\mbox{mod} \ q^2).

Since a_0^2 \leq p^{2l}, |a_0| \leq p^l.

If 2l < 4 \log_p(q) - \log_p(4) we will have p^l < q^2/2. Then |p^l\pm a_0| \leq 2|p^l| < q^2.

But we know that p^l \equiv a_0 (\mbox{mod} \ q^2), one of p^l\pm a_0 must be divisible by q^2, hence 0.

Conclude p^l = \pm a_0, N(\alpha) = p^k = a_0^2, hence a_1=a_2=a_3=0. Contradiction.

The Carnot-Carathéodory metric

Conan7 Comments

I remember looking at Gromov’s notes “Carnot-Carathéodory spaces seen from within” a long time ago and didn’t get anywhere. Recently I encountered it again through professor Guth. This time, with his effort in explaining, I did get some ideas. This thing is indeed pretty cool~ So I decided to write an elementary introduction about it here. We will construct a such metric in \mathbb{R}^3.

In general, if we have a Riemannian manifold, the Riemannian distance between two given points p, q is defined as

\inf_\Gamma(p,q) \int_0^1||\gamma'(t)||dt

where \Gamma is the collection of all differentiable curves \gamma connecting the two points.

However, if we have a lower dimensional sub-bundle E(M) of the tangent bundle (depending continuously on the base point). We may attempt to define the metric

d(p,q) = \inf_{\Gamma'} \int_0^1||\gamma'(t)||dt

where \Gamma' is the collection of curves connecting p, q with \gamma'(t) \in E(M) for all t. (i.e. we are only allowed to go along directions in the sub-bundle.

Now if we attempt to do this in \mathbb{R}^3, the first thing we may try is let the sub-bundle be the say, xy-plane at all points. It’s easy to realize that now we are ‘stuck’ in the same height: any two points with different z coordinate will have no curve connecting them (hence the distance is infinite). The resulting metric space is real number many discrete copies of \mathbb{R}^2. Of course that’s no longer homeomorphic to \mathbb{R}^3.

Hence for the metric to be finite, we have to require accessibility of the sub-bundle: Any point is connected to any other point by a curve with derivatives in the E(M).

For the metric to be equivalent to our original Riemannian metric (meaning generate the same topology), we need E(M) to be locally accessible: Any point less than \delta away from the original point p can be connected to p by a curve of length < \varepsilon going along E(M).

At the first glance the existence of a (non-trivial) such metric may not seem obvious. Let’s construct one on \mathbb{R}^3 that generates the same topology:

To start, we first identify our \mathbb{R}^3 with the 3 \times 3 real entry Heisenberg group H^3 (all 3 \times 3 upper triangular matrices with “1”s on the diagonal). i.e. we have homeomorphism

h(x,y,z) \mapsto \left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right)

Let g be a left-invariant metric on H_3.

In the Lie algebra T_e(H_3) (tangent space of the identity element), the elements X = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) , Y = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right) and Z = \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) form a basis.

At each point, we take the two dimensional sub-bundle E(H_3) of the tangent bundle generated by infinitesimal left translations by X, Y. Since the metric g is left invariant, we are free to restrict the metric to E(M) i.e. we have ||X_p|| = ||Y_p|| = 1 for each p \in M.

The interesting thing about H_3 is that all points are accessible from the origin via curves everywhere tangent to E(H_3). In other words, any points can be obtained by left translating any other point by multiples of elements X and Y.

The “unit grid” in \mathbb{R}^3 under this sub-Riemannian metric looks something like:

Since we have

\left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) = \left( \begin{array}{ccc} 1 & x+1 & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right) ,

the original x-direction stay the same, i.e. a bunch of horizontal lines connecting the original yz planes orthogonally.

However, if we look at a translation by Y, we have

\left( \begin{array}{ccc} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right) = \left( \begin{array}{ccc} 1 & x & z+x \\ 0 & 1 & y+1 \\ 0 & 0 & 1 \end{array} \right)

i.e. a unit length Y-vector not only add a 1 to the y-direction but also adds a height x to z, hence the grid of unit Y vectors in the above three yz planes look like:

We can now try to see the rough shape of balls by only allowing ourselves to go along the unit grid formed by X and Y lines constructed above. This corresponds to accessing all matrices with integer entry by words in X and Y.

The first question to ask is perhaps how to go from (0,0,0) to (0,0,1). –since going along the z axis is disabled. Observe that going through the following loop works:

We conclude that d_C((0,0,0), (0,0,1)) \leq 4 in fact up to a constant going along such loop gives the actual distance.

At this point one might feel that going along z axis in the C-C metric is always takes longer than the ordinary distance. Giving it a bit more thought, we will find this is NOT the case: Imagine what happens if we want to go from (0,0,0) to (0,0,10000)?

One way to do this is to go along X for 100 steps, then along Y for 100 steps (at this point each step in Y will raise 100 in z-coordinate, then Y^{-100} X^{-100}. This gives d_C((0,0,0), (0,0,10000)) \leq 400.

To illustrate, let’s first see the loop from (0,0,0) to (0,0,4):

The loop has length 8. (A lot shorter compare to length 4 for going 1 unit in z-direction)

i.e. for large Z, it’s much more efficient to travel in the C-C metric. d_C( (0,0,0), (0,0,N^2)) = 4N

In fact, we can see the ball of radius N is roughly an rectangle with dimension R \times R \times R^2 (meaning bounded from both inside and outside with a constant factor). Hence the volume of balls grow like R^4.

Balls are very “flat” when they are small and very “long” when they are large.

Slides for my little Anosov talk

Conan7 Comments

As promised~ have fun!

*Actually I’m a strong supporter of the idea that all talks should be done on blackboards…However, this time since the talk is only 25 minutes long and it takes me 5 minutes to draw a product Cantor set, I had to use slides…

Hence I made fake blackboard slides…

A survey on ergodicity of Anosov diffeomorphisms

Conan3 Comments

This is in part a preparation for my 25-minutes talk in a workshop here at Princeton next week. (Never given a short talk before…I’m super nervous about this >.<) In this little survey post I wish to list some background and historical results which might appear in the talk.

Let me post the (tentative) abstract first:

——————————————————

Title: Volume preserving extensions and ergodicity of Anosov diffeomorphisms

Abstract: Given a C^1 self-diffeomorphism of a compact subset in \mathbb{R}^n, from Whitney’s extension theorem we know exactly when does it C^1 extend to \mathbb{R}^n. How about volume preserving extensions?

It is a classical result that any volume preserving Anosov di ffeomorphism of regularity C^{1+\varepsilon} is ergodic. The question is open for C^1. In 1975 Rufus Bowen constructed an (non-volume-preserving) Anosov map on the 2-torus with an invariant positive measured Cantor set. Various attempts have been made to make the construction volume preserving.

By studying the above extension problem we conclude, in particular the Bowen-type mapping on positive measured Cantor sets can never be volume preservingly extended to the torus. This is joint work with Charles Pugh and Amie Wilkinson.

——————————————————

A diffeomorphism f: M \rightarrow M is said to be Anosov if there is a splitting of the tangent space TM = E^u \oplus E^s that’s invariant under Df, vectors in E^u are uniformly expanding and vectors in E^s are uniformly contracting.

In his thesis, Anosov gave an argument that proves:

Theorem: (Anosov ’67) Any volume preserving Anosov diffeomorphism on compact manifolds with regularity C^2 or higher on is ergodic.

This result is later generalized to Anosov diffeo with regularity C^{1+\varepsilon}. i.e. C^1 with an \varepsilon-holder condition on the derivative.

It is a curious open question whether this is true for maps that’s strictly C^1.

The methods for proving ergodicity for maps with higher regularity, which relies on the stable and unstable foliation being absolutely continuous, certainly does not carry through to the C^1 case:

In 1975, Rufus Bowen gave the first example of an Anosov map that’s only C^1, with non-absolutely continuous stable and unstable foliations. In fact his example is a modification of the classical Smale’s horseshoe on the two-torus, non-volume-preserving but has an invariant Cantor set of positive Lebesgue measure.

A simple observation is that the Bowen map is in fact volume preserving on the Cantor set. Ever since then, it’s been of interest to extend Bowen’s example to the complement of the Cantor set in order to obtain an volume preserving Anosov diffeo that’s not ergodic.

In 1980, Robinson and Young extended the Bowen example to a C^1 Anosov diffeomorphism that preserves a measure that’s absolutely continuous with respect to the Lebesgue measure.

In a recent paper, Artur Avila showed:

Theorem: (Avila ’10) C^\infty volume preserving diffeomorphisms are C^1 dense in C^1 volume preserving diffeomorphisms.

Together with other fact about Anosov diffeomorphisms, this implies the generic C^1 volume preserving diffeomorphism is ergodic. Making the question of whether such example exists even more curious.

In light of this problem, we study the much more elementary question:

Question: Given a compact set K \subseteq \mathbb{R}^2 and a self-map f: K \rightarrow K, when can the map f be extended to an area-preserving C^1 diffeomorphism F: \mathbb{R}^2 \rightarrow \mathbb{R}^2?

Of course, a necessary condition for such extension to exist is that f extends to a C^1 diffeomorphism F (perhaps not volume preserving) and that DF has determent 1 on K. Whitney’s extension theorem gives a necessary and sufficient criteria for this.

Hence the unknown part of our question is just:

Question: Given K \subseteq \mathbb{R}^2, F \in \mbox{Diff}^1(\mathbb{R}^2) s.t. \det(DF_p) = 1 for all p \in K. When is there a G \in \mbox{Diff}^1_\omega(\mathbb{R}^2) with G|_K = F|_K?

There are trivial restrictions on K i.e. if K separates \mathbb{R}^2 and F switches complementary components with different volume, then F|_K can never have volume preserving extension.

A positive result along the line would be the following slight modification of Moser’s theorem:

Theorem: Any C^{r+1} diffeomorphism on S^1 can be extended to a C^r area-preserving diffeomorphism on the unit disc D.

For more details see this pervious post.

Applying methods of generating functions and Whitney’s extension theorem, as in this paper, in fact we can get rid of the loss of one derivative. i.e.

Theorem: (Bonatti, Crovisier, Wilkinson ’08) Any C^1 diffeo on the circle can be extended to a volume-preserving C^1 diffeo on the disc.

With the above theorem, shall we expect the condition of switching complementary components of same volume to be also sufficient?

No. As seen in the pervious post, restricting to the case that F only permute complementary components with the same volume is not enough. In the example, K does not separate the plane, f: K \rightarrow K can be C^1 extended, the extension preserves volume on K, and yet it’s impossible to find an extension preserving the volume on the complement of K.

The problem here is that there are ‘almost enclosed regions’ with different volume that are being switched. One might hope this is true at least for Cantor sets (such as in the Bowen case), however this is still not the case.

Theorem: For any positively measured product Cantor set C = C_1 \times C_2, the Horseshoe map h: C \rightarrow C does not extend to a Holder continuous map preserving area on the torus.

Hence in particular we get that no volume preserving extension of the Bowen map can be possible. (not even Holder continuous)

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).