A celebrated theorem of Gromov reads:
Theorem 1 Every finitely generated group of polynomial growth is virtually nilpotent.
The original proof of Gromov’s theorem was quite non-elementary, using an infinitary limit and exploiting the work surrounding the solution to Hilbert’s fifth problem. More recently, Kleiner provided a proof which was more elementary (based in large part on an earlier paper of Colding and Minicozzi), though still not entirely so, relying in part on (a weak form of the) Tits alternative and also on an ultrafilter argument of Korevaar-Schoen and Mok. I discuss Kleiner’s argument more in this previous blog post.
Recently, Yehuda Shalom and I established a quantitative version of Gromov’s theorem by making every component of Kleiner’s argument finitary. Technically, this provides a fully elementary proof of Gromov’s theorem (we do use one infinitary limit to simplify the argument a little bit, but this is not truly necessary); however, because we were trying to quantify as much of the result as possible, the argument became quite lengthy.
In this note I want to record a short version of the argument of Yehuda and myself which is not quantitative, but gives a self-contained and largely elementary proof of Gromov’s theorem. The argument is not too far from the Kleiner argument, but has a number of simplifications at various places. In a number of places, there was a choice to take between a short argument that was “inefficient” in the sense that it did not lead to a good quantitative bound, and a lengthier argument which led to better quantitative bounds. I have opted for the former in all such cases.
Yehuda and I plan to write a short paper containing this argument as well as some additional material, but due to some interest in this particular proof, we are detailing it here on this blog in advance of our paper.
Note: this post will assume familiarity with the basic terminology of group theory, and will move somewhat quickly through the technical details.
— 1. Overview of argument —
The argument requires four separate ingredients. The first is the existence of non-trivial Lipschitz harmonic functions :
Theorem 2 (Existence of non-trivial Lipschitz harmonic functions) Let be an infinite group generated by a finite symmetric set . Then there exists a non-constant function which is harmonic in the sense that
for all , and Lipschitz in the sense that
for all and , and some .
The second is that there are not too many such harmonic functions:
Theorem 3 (Kleiner’s theorem) Let be a group of polynomial growth generated by a finite symmetric set of generators. Then the vector space of Lipschitz harmonic functions is finite-dimensional.
The third ingredient is that Gromov’s theorem is true in the compact linear Lie group case:
Theorem 4 (Gromov’s theorem in the compact Lie case) Let be a finitely generated subgroup of a compact linear Lie group of polynomial growth. Then is virtually abelian.
The final ingredient is that Gromov’s theorem is inductively true once one can locate an infinite cyclic quotient:
Theorem 5 (Gromov’s theorem with an cyclic quotient) Let be a finitely generated group which has polynomial growth of exponent at most (i.e. the volume of a ball grows like for any fixed set of generators ). Suppose inductively that Gromov’s theorem is already known for groups of polynomial growth of exponent at most , and suppose that contains a finite index subgroup which can be mapped homomorphically onto an infinite cyclic group. Then is virtually nilpotent.
We prove these four facts in later sections. For now, let us see how they combine to establish Gromov’s theorem in full generality.
We assume that has polynomial growth of order , and assume inductively that Gromov’s theorem has already been established for growth of order or less. We fix a symmetric set of generators.
We may assume that is infinite otherwise we are already done. So by Theorem 2, the space of (complex) Lipschitz harmonic functions consists of more than just the constants . In particular, setting , we have a non-trivial short exact sequence
The left translation action of preserves the space of Lipschitz harmonic functions, and is thus an action of on . Since preserves constants, it is also an action of on . Now, on , the homogeneous Lipschitz norm is a genuine norm, and is preserved by the action of . Since all norms are equivalent on a finite-dimensional space, we can place an arbitrary Euclidean structure on and conclude that this structure is preserved up to constants by . So, the image of the action of on is precompact, and thus its closure is a compact Lie group. By Theorem 4, this image is virtually abelian. If it is infinite, then we thus see that a finite index subgroup of has an infinite abelian image, and thus has a surjective homomorphism onto the integers, and we are done by Theorem 5. So we may assume that this image is finite; thus there is a finite index subgroup of that is trivial on . The action of on then collapses to the form for some linear functional (in fact annihilates and so comes from ). Note that is then an additive representation of . If the image of this representation is infinite, then we are again done by Theorem 5, so we may assume that it is finite; thus there is a finite index subgroup of that is trivial on . In other words, all Lipschitz harmonic functions are -invariant, and thus take only finitely many values. But looking at the maximum such value and using harmonicity (i.e. using the maximum principle) we conclude that all Lipschitz harmonic functions are constant, a contradiction.
— 2. Building a Lipschitz harmonic function —
Now we prove Theorem 2. We introduce the function
where is the Kronecker delta function. The property of a function being harmonic is then simply that , using the discrete convolution structure on the group.
To build such a function, we consider the functions
where is the convolution of copies of . This sequence of functions is “asymptotically harmonic” in the sense that
but
(we allow implied constants to depend on ).
There are now two cases. The first case is the non-amenable case, when we have
for some , some , and infinitely many ; informally, this means that the averaged iterated convolutions are not getting smoother as . By the duality of and , we see that for each such we can find with such that
But Young’s inequality, has norm of at most , and
Using the sequential Banach-Alaoglu theorem we may take a subsequence limit and obtain a non-trivial bounded harmonic function. Since bounded functions are automatically Lipschitz, the claim follows.
The second case is the amenable case, when we have
as for each . Setting , one soon verifies that
and
In particular
From this and the spectral theorem, we see that the positive-definite Laplacian operator defined by the formula
has non-trivial spectrum at the origin. On the other hand, as is infinite, there are no non-trivial harmonic functions in (as can be seen from the maximum principle), and so the spectrum at the origin is not coming from a zero eigenfunction. From this and the spectral theorem (taking spectral projections to for small ), one can find a sequence of functions such that
but
as .
A summation by parts gives the Dirichlet energy identity
and thus
and also there exists such that
for infinitely many . By the self-duality of , we may thus find a sequence with such that
for infinitely many . From Young’s inequality we also see that
(so is uniformly Lipschitz) and
as , thus is asymptotically harmonic. Using the Arzelá-Ascoli theorem to take another subsequence limit (after first subtracting a constant to normalise to be zero at the identity, so that becomes locally bounded by the uniform Lispchitz property) we obtain the required non-trivial Lipschitz harmonic function.
Remark 1 In the case of groups of polynomial growth, one can verify that one is always in the “amenable” case. In the non-amenable case, the theory of Poisson boundaries gives a plentiful supply of bounded Lipschitz harmonic functions (in fact, there is an infinite-dimensional space of such).
— 3. Kleiner’s theorem —
We now prove Theorem 3. Our proof will basically repeat those in Kleiner’s original paper. For simplicity, let us assume a stronger condition than polynomial growth, namely bounded doubling
for some fixed constant and all . In general, polynomial growth does not obviously imply bounded doubling at all scales, but there is a simple pigeonhole argument that gives bounded doubling on most scales, and this turns out to be enough to run the argument below. But in order not to deal with the (minor) technicalities arising from exceptional scales in which bounded doubling fails, I will assume bounded doubling at all scales. The full proof in the general case can, of course, be found in Kleiner’s paper (which in turn was based upon an earlier argument of Colding and Minicozzi).
Let be a small parameter. The key lemma is
Lemma 6 (Elliptic regularity) Cover by balls of radius . Suppose that a harmonic function has mean zero on every such ball. Then one has
Let’s see how this lemma establishes the theorem. Consider some Lipschitz harmonic functions , which we normalise to all vanish at the identity. Let be the space spanned by . For each , the inner product gives a quadratic form on . Using this quadratic form, we can build a Gram matrix determinant
From the Lipschitz nature of the harmonic functions, we have a bound of the form
as . On the other hand, we also have the monotonicity property
Now by bounded doubling, we can cover by balls of radius . By Lemma 6, the space of functions in which have mean zero on each such ball is such that is bounded (as a quadratic form) by times on this space. Furthermore, by linear algebra, this space has codimension in . Using this, we obtain the improved bound
For small enough and large enough, the rate of growth is strictly less than . Iterating this estimate by doubling off to infinity, and comparing against (1), we conclude in the limit that
for all , and so cannot be linearly independent. This implies that the space of Lipschitz harmonic functions has dimension at most , and the claim follows.
It remains to prove the lemma. Fix the harmonic function .
There are two basic ingredients here. The first is the reverse Poincaré inequality
where
This claim (which heavily exploits the harmonicity of ) is proven by writing as , multiplying by a suitable cutoff function adapted to and equalling one on , and summing by parts; we omit the standard details. (The above inequality is in the general spirit of the philosophy that functions that are harmonic on a ball, should be smooth that ball.)
The second claim is the Poincaré inequality
which does not require harmonicity. To prove this claim, observe that the left-hand side can be bounded by
But by expanding each as a word of length most and using the triangle inequality in and Cauchy-Schwarz, we have
and the claim follows.
If has mean zero on , the Poincaré inequality implies that
To prove the lemma, we first use bounded doubling to refine the family of balls so that the triples have bounded overlap. Applying (2) for each such ball and summing we obtain the claim.
— 4. The compact Lie case —
Now we prove Theorem 4. It is a classical fact that all compact linear Lie groups are isomorphic to a subgroup of a unitary group ; indeed, if one takes the standard inner product on and averages it by the Haar measure of , one obtains an inner product which is -invariant, and so can be embedded inside the unitary group associated to this group. Thus it suffices to prove the claim when .
A key observation is that if two unitary elements are close to the identity, then their commutator is even closer to the identity. Indeed, since multiplication on the left or right by unitary elements does not affect the operator norm, we have
and so by the triangle inequality
We now need to exploit (3) to prove Theorem 4. As a warm-up, we first prove the following slightly easier classical result:
Theorem 7 (Jordan’s theorem) Let be a finite subgroup of . Then contains an abelian subgroup of index (i.e. at most , where depends only on ).
And indeed, the proof of the two results are very similar. Let us first prove Jordan’s theorem. We do this by induction on , the case being trivial. Suppose first that contains a central element which is not a multiple of the identity. Then, by definition, is contained in the centraliser of , which by the spectral theorem is isomorphic to a product of smaller unitary groups. Projecting to each of these factor groups and applying the induction hypothesis, we obtain the claim.
Thus we may assume that contains no central elements other than multiples of the identity. Now pick a small (one could take in fact) and consider the subgroup of generated by those elements of that are within of the identity (in the operator norm). By considering a maximal -net of we see that has index at most in . By arguing as before, we may assume that has no central elements other than multiples of the identity.
If consists only of multiples of the identity, then we are done. If not, take an element of that is not a multiple of the identity, and which is as close as possible to the identity (here is where we use that is finite). By (3), we see that if is sufficiently small depending on , and if is one of the generators of , then lies in and is closer to the identity than , and is thus a multiple of the identity. On the other hand, has determinant . Given that it is so close to the identity, it must therefore be the identity (if is small enough). In other words, is central in , and is thus a multiple of the identity. But this contradicts the hypothesis that there are no central elements other than multiples of the identity, and we are done.
The proof of Theorem 4 is analogous. Again, we pick a small , and define as before. If has a central element that is not a multiple of the identity, then we can again argue via induction, so suppose that there are no such elements.
Being finitely generated, it is not difficult to show that can be generated by a finite set of generators within distance of the identity. Now pick an element which is not a multiple of the identity, and is at a distance from the identity for some . We look at all the commutators where . By (3), they are all at distance from the identity, and have determinant . If they are all constant multiples of the identity, then by arguing as before we see that is central in , a contradiction, so we can find an element for some which is a distance from the origin and is not a multiple of the identity. Continuing this, we can construct , etc., where each is a distance from the identity, and is a commutator of with a generator.
Because of the lacunary nature of the distances of , we easily see that the words with are distinct for some small . On the other hand, all of these words lie in the ball of radius generated by . This contradicts the polynomial growth hypothesis for taken small enough and large enough.
Remark 2 Theorem 4 can be deduced as a corollary of Gromov’s theorem, though we do not do so here as this would be circular. Indeed, it is not hard to see that the image of a torsion-free nilpotent group in a unitary group must be abelian.
— 5. The case of an infinite abelian quotient —
Now we prove Theorem 5 (which was already observed in Gromov’s original paper, and also closely related to earlier work of Milnor and of Wolf).
Since is finitely generated and has polynomial growth of order , the finite index subgroup is also finitely generated of growth . By hypothesis, there is a non-trivial homomorphism . Using the Euclidean algorithm, one can move the generators of around so that all but one of them, say , lie in the kernel of ; we thus see that this kernel must then be generated by and their conjugates by powers of .
Let be the set of for and , and let be the words of length at most generated by elements of . Observe that if at least one of the elements in is not contained in , then is at least twice as big as . Because of polynomial growth, this implies that for some , which implies that is generated by .
Observe that the ball of radius generated by and is at least times as large as the ball of radius generated by . Since has growth , we conclude that has growth at most , and is thus virtually nilpotent by hypothesis.
We have just seen that the kernel contains a nilpotent subgroup of some finite index ; it is thus finitely generated. We can take to be a normal subgroup of . From Lagrange’s theorem, we see that the group generated by the powers with is then contained in and is therefore nilpotent. is clearly a characteristic subgroup of , and is thus normal in . The group is nilpotent and finitely generated with every element being of order , and is thus finite; thus is finite index in . Since it is characteristic, it is in particular invariant under conjugation by . If one lets be the group generated by and , we see that is a finite index subgroup of . (Note that as is not annihilated by , it will have infinite torsion even after quotienting out by .) In particular, it has polynomial growth.
To conclude, we need to show that is virtually nilpotent. It will suffice to show that the conjugation action of on acts unipotently on for some finite . We can induct on the step of the nilpotent group , assuming that the claim has already been proven for the quotient group (where is the centre of ), which has one lower step on . Thus it suffices to prove unipotence on just the center , which is a finitely generated abelian group and thus isomorphic to some for some finite group . By Lagrange’s theorem, the action on becomes trivial after raising to a suitable power, so we only need to consider the action on . In this case the conjugation action can be viewed as a matrix in . Because has polynomial growth, the powers of for cannot grow exponentially (as otherwise the number of subsums of for and would grow exponentially in , contradicting the polynomial growth hypothesis); in other words, all the eigenvalues of have unit magnitude. On the other hand, these eigenvalues consist of Galois conjugacy classes of algebraic integers. But Kronecker’s theorem asserts that the only algebraic integers whose Galois conjugates all have unit magnitude are the roots of unity (Proof: the algebraic integers have bounded degree and uniformly bounded Galois conjugates, hence their minimal polynomial has bounded integer coefficients, and thus repeat itself). We conclude that all the eigenvalues of are roots of unity, i.e. some power of is unipotent, and the claim follows.
36 comments
Comments feed for this article
19 February, 2010 at 6:56 am
DrDolittle
The statement of theorem 5 would be more legible, I think, if you replaced “infinite abelian group” by .
In the proof of theorem 5, I don’t see why should generate the kernel – for example, again is in the kernel.
19 February, 2010 at 7:23 am
Ben Green
Terry,
Thanks for this. I think this proof can definitely be given in a graduate course now, and I intend to do so myself next academic year.
Best
Ben
19 February, 2010 at 7:44 am
pavel zorin
Dear Mr. Tao,
a couple of comments regarding the proof of the existence of a Lipschitz harmonic function:
In the non-amenable case: g_n should be H_n and in the last paragraph, there is no need to appeal to the discreteness of G.
In the amenable case, I don’t quite see how does one arrive at ||F_n-F_n*δ_s||_{ℓ²}=O(n^{-½}): a direct calculation gives a bound in terms of ||f_n-f_n*δ_s||_{ℓ¹}, which has unknown decay (but is sufficient to conclude).
If I understand it right, at the end of the proof one chooses a convergent subsequence of H_n*G_n. How does one ensure ∞-boundedness of this sequence? The sequence G_n must go to infinity if ≡1.
regards, pavel
19 February, 2010 at 7:46 am
pavel zorin
that is, (G_n, ΔG_n)≡1. (always forget that the “less” and “greater” signs are reserved symbols)
19 February, 2010 at 8:51 am
Terence Tao
Thanks for the corrections!
19 February, 2010 at 10:21 am
pavel zorin
Two more things: in the Dirichlet energy identity, there seems to be a 1/2 missing on the right.
Then, I don’t see which topology you would choose to apply Arzelà-Ascoli.
Instead, one could use the uniform Lipschitz condition to get pointwise boundedness and then select a pointwise convergent subsequence. The value of the Laplacian in a point is a continuous function of a finite amount of values of its argument and thus passes to the limit.
19 February, 2010 at 11:42 am
Terence Tao
Thanks again for the correction.
I’m applying Arzela-Ascoli (for sigma-compact domains, and in the topology of locally uniform convergence) for the discrete group G. Of course, the proof of Arzela-Ascoli in this case is exactly as you describe, plus one application of diagonalisation. (I tend to lump all arguments that involve the Arzela-Ascoli diagonalisation trick under the category of Arzela-Ascoli type arguments, as a convenient shorthand.)
20 February, 2010 at 9:00 pm
Boris Solomyak
Terry,
This is great timing, since Steffen Rohde and I are just now covering Gromov’s theorem in a graduate course in Seattle. I have a minor question:
isn’t it the case that the Poincare inequality in this blog should be “reverse Poncare” and vice versa?
Thanks!
[Corrected, thanks – T.]
21 February, 2010 at 10:07 am
David Speyer
Some dumb questions about the amenable growth case in Theorem 2:
(1) I don’t understand the statement that, since has nontrivial spectrum at the origin, there is a sequence with and .
Suppose was a self-adjoint idempotent, such as . Then .
(2) In a possibly related issue, I don’t understand where you use that is infinite.
21 February, 2010 at 10:15 am
Terence Tao
Ah, thanks! Yes, the two issues are related. I forgot to mention that when G is infinite, there are no non-trivial harmonic functions in (from the maximum principle), and so has no eigenfunction at zero; the spectrum at zero must then be coming from something other than pure point spectrum at the origin (e.g. continuous spectrum, or a sequence of eigenvalues tending to zero but not actually zero). Now what one can do is take the functions and spectrally project them to a small interval near the origin, which upon normalisation will give the desired thanks to the spectral theorem. (The absence of a zero eigenfunction is needed to ensure that we do not divide by zero when performing the normalisation.) I’ve changed the text accordingly.
19 July, 2010 at 2:18 am
Gábor Pete
Dear Terry,
I seem to see a mistake in the penultimate paragraph. I’m probably wrong, because I see the same issue in Tits’ appendix to Gromov and in the Drutu-Kapovich lecture notes, but could you please help?
Why would the subgroup of G generated by N’ and e_m be the semidirect product given by conjugation by e_m? For instance, in the short exact sequence {0} –> {0,2} –> {0,1,2,3} –> {0,1} —> {0} of additive cyclic groups, {0,2} and 1 generate {0,1,2,3}, but conjugation by 1 is the trivial action on {0,2}, hence the semidirect product is a direct product \Z_2\times\Z_2, which is not the same as \Z_4.
If I were right, then the last paragraph, about the conjugations, would not apply.
Embarrassingly, I realized I didn’t understand this point during a lecture I was giving…
Thanks!
19 July, 2010 at 8:34 am
Terence Tao
Because we are in the infinite quotient case, has infinite order even after quotienting by N’ (recall that annihilates N’ but not ), so the torsion obstruction indicated by your example does not arise. (To put it in fancier language, the base group here is (as opposed to {0,1} in your example), which has a trivial first group cohomology.) I’ve modified the text to clarify this.
19 July, 2010 at 11:24 am
Gábor Pete
Thanks! This was really dumb…
15 January, 2011 at 8:16 am
A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups « What’s new
[…] result can be compared with Jordan’s theorem (discussed earlier on this blog) that every finite subgroup of is virtually abelian (with a uniform bound on the index of the […]
23 January, 2011 at 7:13 am
The Peter-Weyl theorem, and non-abelian Fourier analysis on compact groups « What’s new
[…] in Gromov’s proof of his theorem on groups of polynomial growth (discussed previously on this blog), and in a more recent paper of Hrushovski on approximate groups (also discussed previously). It is […]
2 July, 2011 at 3:34 pm
Anonymous
I wonder if someone can provide an explicit reference to the
paper of the above Theorem 7 (Jordan’s theorem) — a theorem number, page number, or something like that. If i am not mistaken, it should be in Jordan’s paper: Mémoire sur les équations différentielles
linéaires à intégrale algébrique, J. reine angew. Math. 84 (1878), 89–215?
In any case i enjoyed the above prove!
Paulo
2 July, 2011 at 4:28 pm
Anonymous
Embarrassingly, i have found it now: Page 91.
27 August, 2011 at 11:35 am
254A, Notes 0 – Hilbert’s fifth problem and related topics « What’s new
[…] on harmonic functions of polynomial growth. (This latter proof is discussed in these previous blog posts.) The proof we will give in these notes is more recent, based on an . We remark that the strategy […]
10 November, 2012 at 2:16 am
Felix V.
Dear Prof. Tao,
I have been working my way through your elementary proof of Gromov’s theorem and understood most of it, but I am currently stuck on the last paragraph of your proof of Theorem 5 (the case of an infinite abelian quotient).
But first a few remarks:
1) In the fourth paragraph of the proof of theorem 5, you claim that “the ball of radius R generated by is at least times as large as the ball of radius R/2 generated by “.
I think you have to replace by , as then and thus are pairwise disjoint subsets of each of cardinality , so that your claim follows. At the very least, you will have to replace by .
2) In the fifth paragraph of that proof you claim that the group generated by the powers would be contained in by Lagrange’s theorem.
This is only true if is a normal subgroup, as can be seen by the example , and , where , but .
This is no problem, as every subgroup of finite index contains a subgroup such that is normal in and , so that you can assume that is a normal subgroup.
Now to my question regarding the last paragraph of that proof:
Why does the polynomial growth of imply the (at most) polynomial growth of the entries of ?
The only thing that I can deduce from the polynomial growth assumption is that since , you can bound the number of elements(!) in by a polynomial in , where denotes the (closed) ball of radius with respect to .
But what I would need to show the polynomial growth of the elements of would be a bound on the exponents of the generators in an expression for instead of just a bound on the number of elements.
Could you give me a hint here?
Best regards, and thanks in advance for your help,
Felix V.
11 November, 2012 at 8:22 am
Terence Tao
Thanks for the corrections, which are now implemented! Regarding your final question, I should have written “cannot grow exponentially” rather than “can only grow polynomially”. If the exhibit exponential growth, then the for and will be lacunary enough that the number of all possible subsums of these vectors will grow exponentially in N. On the other hand, all these subsums are contained in a ball of radius , contradicting polynomial growth.
Here we use the fact from the Jordan normal form that powers of a matrix either grow at most polynomially, or grow exponentially; there is no possibility of a intermediate growth rate. (In contrast, there are nontrivial examples of finitely generated groups of intermediate growth, most notably the Grigorchuk groups.)
14 November, 2012 at 4:47 am
Felix V.
Dear Prof. Tao,
thank you very much for clarifying my problem.
I have one more question regarding the same paragraph of the proof of Theorem 5. That question may have a very simple solution which I don’t see, as my knowledge of group theory is limited:
You claim that it is sufficient to show that the conjugation-action of some power of on is unipotent.
My interpretation of unipotency in this case (I only knew that term in connection with matrices) is that for some and the -fold iteration of is trivial, i.e. for all , where the commutator is of length . Your proof actually shows (if I am not mistaken) that all(!) powers of act unipotently (with the same ).
One furthermore knows that is nilpotent, i.e., for some , all commutators of length vanish. But I do not see why this already implies the nilpotency of the semidirect product (I guess that this is what you want to show, as this group has finite index in ).
My idea would be to show that all commutators of a suitable length vanish, but I run into problems, when the commutator “alternates” between and elements of (or also different powers of ), i.e., something like .
Could you help me with this?
Furthermore I am not sure that your proof that all algebraic integers whose Galois-conjugacy class is a subset of the unit circle are roots of unity is correct. According to http://math.stackexchange.com/questions/4323/are-all-algebraic-integers-with-absolute-value-1-roots-of-unity, the statement does not hold if only (i.e. there are Galois conjugates outside of the unit circle) and your proof seems to work even in that case.
Best regards and many thanks again,
Felix V.
14 November, 2012 at 9:16 am
Terence Tao
Thanks again for the corrections! I have now put in a correct proof of Kronecker’s theorem instead of the incorrect one sketched previously.
Regarding how to establish nilpotence of when acts unipotently, observe that the action of preserves each member of the lower central series of N’ (as these are characteristic subgroups of N’), while conjugation by an element of N’ moves from one element of the lower central series to the next. Thus, no matter how one alternates between commutation by or commutation by an element of N’, one either marches up the lower central series and eventually becomes trivial, or else one has a long string of commutation by and so one becomes trivial by unipotence.
21 November, 2012 at 12:32 am
Felix V.
Dear Prof. Tao,
thank You very much, that helped a lot.
Best regards,
Felix V.
20 June, 2013 at 1:21 pm
Three Theorems About Growth | Gödel's Lost Letter and P=NP
[…] All three theorems—more precisely, the proofs of these theorems—require one to overcome a technical hurdle. This is indeed the reason I decided to talk about these results. I was reading a chapter of Terence Tao’s beautiful book titled “Compactness and Contradiction” where he gives an outline of the proof of Gromov’s theorem. Tao is brilliant at explaining things, and you can see this also on-line here. […]
25 July, 2013 at 7:03 am
Kleiner’s space of harmonic functions | Ehsaan's Blog
[…] T. Tao’s blog. […]
6 December, 2014 at 1:12 pm
lingnaodai11
Reblogged this on lingnaodai and commented:
I hope to ask Kleiner to be my advisor.. I hope to understand more of his work, and of group theory of course.
12 September, 2015 at 9:53 am
A Polynomial Growth Puzzle | Gödel's Lost Letter and P=NP
[…] recalled a post by Terence Tao on Mikhail Gromov’s theorem characterizing finitely-generated groups of […]
7 December, 2015 at 3:29 am
Anonymous
In the definition of Lipschitz, shouldn’t be ? Thank you very much.
[Corrected, thanks -T.]
7 December, 2015 at 4:22 am
Anonymous
In the proof of Theorem 2, in the non-amenable case, there is “Since bounded functions are automatically Lipschitz, and the claim follows.” which doesn’t seem very good English to me. I would remove the “and”.
[Corrected, thanks – T.]
7 July, 2017 at 9:20 am
Anonymous
Regarding bounded doubling: What do you mean by “bounded doubling on most scales”? What is the pigeonhole argument showing this? (if you tell me what “most scales” means, maybe I can take this as an exercise). Thanks!
7 July, 2017 at 4:51 pm
Terence Tao
One can show for instance that in a group of polynomial growth, for any there exists such that one has the doubling property for a set of radii of logarithmic density at least . Or, if one restricts to radii that are powers of two, the same claim is true for a set of exponents of natural density at least .
(Here I am using the pigeonhole principle in the broad sense, to also encompass other basic results (such as Markov’s inequality) on how a function must deviate around its average.)
18 October, 2018 at 9:51 pm
Wolfgang Woess
Here is a question which bothers me since quite a while, and which I discussed very briefly with Terry Tao at a Conference in Cortona in June:
For a complete proof of Varopoulos’ classification of the recurrent groups (= finitely generated groups carrying a recurrent random walk), one only needs the following special cases of Gromov’s theorem:
(1) A group which does not grow at most quadratically must grow at least cubically,
(2) A group which grows at most quadratically is virtually Z or Z^2.
“At most quadratically” can be replaced by ” liminf V(n)/n^2 is finite “,
where V(n) is the growth function.
Are there simpler proofs for (1) and/or (2) than the general one ?
As a matter of fact, all the rest of Varopoulos theorem can be presented to 3rd year students.
Regards, Wolfgang
24 October, 2018 at 9:34 am
Terence Tao
This is basically asking whether there is a shortcut to prove Gromov’s theorem for subcubic growth. This is roughly analogous (though easier than) trying obtain a Freiman type theorem for sets of doubling constant strictly less than . While there is a lot of work on Freiman type theorems with very small doubling constant (e.g. strictly less than ), I unfortunately don’t know of any way to treat sets of doubling less than 8 that don’t generalise to handle the case of arbitrary doubling. This doesn’t directly rule out a corresponding shortcut for subcubic Gromov, since one has more structure in that setting (whereas Freiman’s theorem deals with the doubling constant for arbitrary sets, the sets in Gromov’s theorem are balls, and this structure can be exploited).
Though, perhaps one way forward would be to somehow show directly that groups of subcubic growth are virtually abelian, at which point one it is easy to see that the rank is at most two. Given that non-virtually-abelian groups have at least quartic growth (as the Heisenberg group example illustrates), there is a little bit of room here to allow for some slightly inefficient arguments to proceed. Still seems tricky though.
6 April, 2022 at 4:06 am
Lee Mosher
I have a question about the interval . Why shouldn’t one use instead? Isn’t it possible that for small enough the spectrum intersects in just ? I was thinking on the other hand that is a positive operator, but I cannot see why.
By the way I’m presenting the proof of the polynomial growth theorem in my class this semester, drawing from your blog and its sources (papers of Gromov, Kleiner, you and Shalom, and learning some functional analysis). Back in the early mid 80’s sometime, attending Thurston’s class, he gave me the assignment of presenting Gromov’s paper. I must confess, I never did the assignment.
7 April, 2022 at 10:54 am
Terence Tao
is indeed positive semi-definite, since .
3 June, 2022 at 6:50 pm
gr.group theory - Lipschitz harmonic functions on graphs? Answer - Lord Web
[…] I am not familiar with this sort of subject at all but I am aware of Tao and Yahuda’s result that such functions do exist on Cayley graphs of finitely generated (with $S$ empty) with finite […]