Posts Tagged ‘Larry Guth’

The travelling salesman problem

March 19, 2012





Trivial observations:


This can be easily improved by a standard divide and concur:


Now the value of this F can be computed recursively:


Otherwise F(S, p_1, p_2) =










Selected highlights of proof:








Keep this in mind.









which is indeed polynomial in N/\varepsilon many operations.







Bonus: I also started to paint on iPad~



A Bosuk-Ulam-kind theorem for simplexes

October 17, 2011











So we started to throw out random ideas.









OK~ perhaps not a useful answer but problem solved!

So far I do not know the answer to the following:





A report of my Princeton generals exam

April 26, 2011





Conan Wu’s generals


Topics: Metric Geometry, Dynamical Systems

Real analysis:

Mather: Construct a first category but full measure set.

(I gave the intersection of decreasing balls around the rationals)



Mather: Does integration by parts work for Lipschitz functions?

(Lip imply absolutely continuous then Lebesgue’s differentiation theorem)




(Prove it’s rapidly decreasing)







We moved on to complex.

Complex analysis:



Guth: State maximal modulus principal.


Gabai: What do the Mobius group preserve?

(Poincare metric)





I think that’s pretty much all for the complex.


Gabai: State Eisenstein’s criteria


Gabai: State Sylow’s theorem



(Again, no computing Galois group…)



Gabai: Prove multiplicative group of a finite field is cyclic.




Gabai: What’s \pi_3(S^2)?

(\mathbb{Z}, via Hopf fibration)


(Poincare duality + universal coefficient)

We then moved on to special topics:

Metric Geometry:

Guth: What’s the systolic inequality?

(the term ‘aspherical’ comes up)

Gabai: What’s aspherical? What if the manifold is unbounded?



(I sketched Gromov’s proof via filling radius)


(My guess is for any 2-chain we should have





(it can be as large as c L_1 L_2)

Dynamical Systems:

Mather: Define Anosov diffeomorphisms.

Mather: Prove the definition is independent of the metric.


Mather: Prove structural stability of Anosov diffeomorphisms.






Mather: When are they actually conjugate to the irrational rotation?




Graph, girth and expanders

April 11, 2011

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

March 22, 2011














Let g be a left-invariant metric on H_3.





Since we have
















Isoperimetric inequality on groups

February 28, 2011

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



\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


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

On Uryson widths

February 21, 2011

This is a note on parts of Gromov’s paper ‘width and related invariants of Riemannian manifolds’ (1988).

For a compact subset C of \mathbb{R}^n, we define the k-codimensional width (or simply k-width) to be the smallest possible number w where there exists a k-dimensional affine subspace P_k \subseteq \mathbb{R}^n s.t. all points of C is no more than w away from P_k.


\displaystyle{W}_k(C) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p\in C} \mbox{dist}(p, P_k)
where \mbox{dist}(p, P_k) is the length of the orthogonal segment from p to P_k.

It’s easy to see that, for any C,

\mathcal{W}_0(C) \geq  \mathcal{W}_1(C) \geq \cdots \geq \mathcal{W}_n(C) = 0.

At the first glance it may seems that \mathcal{W}_0(C) = \frac{\mbox{diam}(C)}{2}. However it is not the case since for example the equilateral triangle of side length 1 in \mathbb{R}^2 has diameter 1 but 0-width \frac{1}{\sqrt{3}}. In fact, by a theorem of Jung, this is indeed the optimum case, i.e. we have:

\frac{1}{2}\mbox{diam}(C) \leq \mathcal{W}_0(C) \leq \sqrt{\frac{n}{2(n+1)}}\mbox{diam}(C)

At this point one might wonder (at least I did), if we want to invent a notion that captures the ‘diameter’ after we ‘forget the longest k-dimensions’, a more direct way seem to be taking the smallest possible number w' where there is an orthogonal projection of C onto a k dimensional subspace P_k where any point p \in P_k has pre-image with diameter \leq w'.


\displaystyle \widetilde{\mathcal{W}_k}(X) = \inf_{P_k \subseteq \mathbb{R}^n} \sup_{p \in P_k} \mbox{diam}(\pi^{-1}_{P_k}(p))

Now we easily have \mbox{diam}(C) = \widetilde{\mathcal{W}_0}(C) \geq  \widetilde{\mathcal{W}_1}(C) \geq \cdots \geq \widetilde{\mathcal{W}_n}(C) = 0.

However, the disadvantage of this notion is, for example, there is no reason for a semicircle arc to have 1-width 0 but a three-quarters circular arc having positive 1-width.

Since we are measuring how far is the set from being linear, taking convex hull should not make the set ‘wider’ \widetilde{\mathcal{W}_k}, unlike \widetilde{\mathcal{W}_k} is not invariant under taking convex hulls. Note that for convex sets we do have

\frac{1}{2}\widetilde{\mathcal{W}_k}(C) \leq \mathcal{W}_k(C) \leq \sqrt{\frac{n-k}{2(n-k+1)}}\widetilde{\mathcal{W}_k}(C)

\mathcal{W}_k(C) = 0 iff C is contained in a k-plane.

We now generalize this notion to general metric spaces:

Definition: The Uryson k-width of a compact metric space M is the smallest number w where there exists k dimensional topological space X and a continuous map \pi: M \rightarrow X where any point x \in X has pre-image with diameter \leq w.

i.e. \displaystyle UW_k(M) = \inf \{ \ \sup_{x \in X} \mbox{diam}(\pi^{-1}(x)) \ |

\dim{X} = k, \pi:M \rightarrow X \ \mbox{is continuous} \}

Note: Here dimension is the usual covering dimension for topological spaces: i.e. a topological space X is n dimensional if any finite cover of X has a finite refinement s.t. no point of X is contained in more than n_1 sets in the cover and n is the smallest number with this property.

For compact subsets C of \mathbb{R}^n with induced metric, we obviously we have UW_k(C) \leq \widetilde{\mathcal{W}_k}(C) since the pair (P_k, \pi_{p_k}) is clearly among the pairs we are minimizing over.

Speaking of topological dimensions, one of the classical results is the following:

Lebesgue’s lemma: Let M=[0,1]^n be the solid n-dimensional cube, then for any topological space X with \dim(X)<n and any continuous map p: M \rightarrow X, we have image of at least one pair of opposite (n-1)-faces intersect.

Since the conclusion is purely topological, this applies equally well to rectangles. i.e. for M = [0, L_1] \times [0, L_2] \times \cdots \times [0, L_n], L_1 \geq L_2 \geq \cdots \geq L_n, we have UW_{n-1}(M) \geq L_n; furthermore, UW_k(M) \geq L_{k+1} for all k.

(If the later statement does not hold, we write M as M_1 \times M_2, M_1 being the product of the first (k+1) coordinates. Now UW_k(M) \geq UW_k(M_1) \geq L_{k+1}).

In light of the earlier post about minimax inequality, we should note that if we restrict X to be a homeomorphic copy of \mathbb{R}^k then the notion is the same as the minimax length of fibres. In particular as proved in the post the minimax length of the unit disc to \mathbb{R} is 2.

Exercise: Check that for the unit 2-disk, UW_1(D^2) = \sqrt{3}, i.e. the optimum is obtained by contracting the disc onto a triod.

Hence it can indeed be strictly smaller than merely taking \mathbb{R}^k as the targeting space, even for simply connected sets. This gives a better measurement of ‘width’ in the sense that, for example, the \varepsilon neighborhood of a tree will have 1-width about 2 \varepsilon.

Intergal geometry and the minimax inequality in a nutshell

February 7, 2011









This is indeed easy to prove:



g: z \mapsto -z

be the antipodal map on S^1.


Then we have

f \circ g (L_1) \subseteq L_1.





Establishes the claim.





















We therefore deduce


Establishes the theorem.













On length and volume

November 29, 2010















Define f = \pi_x \circ \phi.




Establishes the theorem.


Moving to the torus


Note that










(to be continued)

Systoles and the generalized Geroch conjecture

October 25, 2010

Almost a year ago, I said here that I would write a sequence of posts on some simple facts and observations related to the systolic inequality but got distracted and didn’t manage to do much of that…

I was reminded last week as I heard professor Guth’s talk on systoles for the 4th time (Yes, the same talk! –in Toronto, Northwestern, India and here at the IAS). It’s interesting that I’m often thinking about different things each time I hear the same talk. This one is about the generalized Geroch conjecture.

Geroch conjecture: \mathbb{T}^n (the n-torus) does not admit a metric of positive scalar curvature.

The conjecture is proved by Schoen and Yau (1979).

Now, scalar curvature can be seen as a limit of volume of balls:

Definition: The scalar curvature of M at p is

\displaystyle \mbox{Sc}(p) = c_n \lim_{r\rightarrow 0} \frac{\mbox{Vol}_E (B(\bar{0},r)) - \mbox{Vol}_g(B(p,r))}{r^{n+2}}

where \mbox{Vol}_E is the Euclidian volume and c_n is a positive constant only depending on the dimension n.

Note that since our manifold does not have any cone points,


must vanish. Further more, the Riemannian structure on M forces the r^{n+1} term to vanish.

Since for this context we only care about is whether the scalar curvature is larger or smaller than 0, we can be even more simple-minded: M has positive scalar curvature at p all small enough balls around p has smaller volume than their Euclidean cousins (with a difference of order propositional to r^{n+2}). In light of this definition, we have:

Restatement of the Geroch conjecture: For all g on \mathbb{T}^n, there exists some point p s.t. \mbox{Sc}(p) \leq 0.

This is to say, small enough balls around some point $p$ are not small enough for it to have positive scalar curvature. What if instead we look at balls of a fixed radius instead of those infinitesimal balls? This naturally leads to

Generalized Geroch conjecture: For any (\mathbb{T}^n, g), for all r, there exists p s.t. \mbox{Vol}_g(B(p, r)) \geq \mbox{Vol}_E(B(\bar{0}, r)).

(For those r larger than the injectivity radius, we lift M to its universal cover so that all homotopically non-trival loops are ‘unfolded’)

Let’s take a look at the 2-torus to get a feel of the conjecture:

The flat torus, of course, has 0 r-scalar curvature at all points.

For the regular rotational torus, we take the ball around the saddle point of the gradient flow, the ball look like a saddle, as shown below.

To see that this has area larger than the analogous Euclidean ball, we can cut it along radial rays into thin triangles, each triangle can be ‘almost flattened’ to a Euclidean triangle, but we have a more triangles than in the Euclidean case.

What if we try to make the surface spherical for most of the area and having those negative scalar curvature points taking up a very small potion. One of my first attempts would be to connect a few spheres with cylinders:

We have a few parameters here: the number of balls n, the width of the connecting cylinders w, the length of the connecting cylinders l and the radius of each sphere R.

If cylinders are too long (longer than 2r), then we can just take the ball in the middle of the cylinder, the volume when lifted to universal cover would be equal to Euclidean.

If the width of cylinders are much smaller than r, then the ball around a point in the gluing line would have volume almost a full spherical ball plus a half Euclidean ball, which would obviously be larger than a full Euclidean ball.

Hence the more interesting case is to have very short, wide tubes and as a consequence, have many balls forming a loop. In this case, the ‘worst’ ball would be centered at the middle of the tube, it intersects the two spheres connected by the tube in something a bit larger than a spherical half-ball.

I haven’t figured out an estimate yet. i.e. can the advantage taken from the fact that spherical ball are smaller than Euclidean balls cancel out the ‘a bit larger than half’? I think that would be interesting to work out.

Finally, let’s say what does this has to do with systoles:

Theorem: Generalized Geroch conjecture \Rightarrow \mbox{Sys}(\mathbb{T}^n, g) \leq \frac{2}{\omega_n^{\frac{1}{n}}} \mbox{Vol}_g(\mathbb{T}^n)^{\frac{1}{n}} (which is the systolic inequality with a constant better than what we have so far)

Proof: Suppose not,

\mbox{Sys}(\mathbb{T}^n, g) > 2 (\frac{\mbox{Vol}_g(\mathbb{T}^n)}{\omega_n})^{\frac{1}{n}}

Let r = (\frac{\mbox{Vol}_g(\mathbb{T}^n)}{\omega_n})^{\frac{1}{n}}, by the generalized Geroch conjecture we have some B(p, r) larger than the Euclidean ball. i.e.

\mbox{Vol}_g(B(p, r))>\omega_n r^n = \omega_n \frac{\mbox{Vol}_g(\mathbb{T}^n)}{\omega_n} = \mbox{Vol}_g(\mathbb{T}^n)

Since the systole is at least 2r, hence B(p, r) cannot contain any homotopically non-trival loop i.e. it does not “warp around” and get unfolded when passing to the universal cover. Hence volume of a ball with radius r cannot be larger than the volume of the whole manifold. Contradiction