Functional Analysis Proof of Gromov’s Polynomial Growth Theorem

(1)

Functional Analysis Proof of

Gromov’s Polynomial Growth Theorem

Narutaka OZAWA

Research Institute for Mathematical Sciences, Kyoto University

MSJ-SI: Operator Algebras and Mathematical Physics Tohoku University, August 2016

N. Ozawa; A functional analysis proof of Gromov’s polynomial growth theorem. arXiv:1510.04223 A. Erschler and N. Ozawa; in preparation.

Narutaka OZAWA (RIMS) FA Proof of Gromov’s Theorem (Day 1) August 2016 1 / 24

(2)

Introduction

(3)

Growth of a group

G finitely generated group,G =hSi

S finite symmetric (i.e., g ∈S ⇔g⁻¹∈S) generating subset,e ∈S word metric |x|_S := min{n :x∈Sⁿ} anddS(x,y) :=|x⁻¹y|_S Definition

G haspolynomial growth if∃d >0 s.t. lim sup_n|Sⁿ|/n^d <∞.

weak polynomial growthif∃d >0 s.t. lim inf_n|Sⁿ|/n^d <∞.

Note: • independent of the choice ofS

•H≤G finite index⇒H andG have the same growth type

∵ the growth type (|S|ⁿn^d, exponential growth, etc.) is aQI-invariant.

Definition

A mapf : (X,d_X)→(Y,d_Y) is a quasi-isometry(QI) if∃K,L>0 s.t.

1

KdX(x,y)−L≤dY(f(x),f(y))≤KdX(x,y) +L and Y ⊂_Lf(X).

Homework: H ≤_f.i.G and G =hSi,H=hTi ⇒ (G,d_S)'_QI (H,d_T)

⇒ G andH has the same growth type.

(4)

Introduction

Theorem (Milnor 1968)

M complete Riem mfld with non-negative Ricci curvature Then ∀ f.g. subgroup of π₁(M) has PG.

Theorem (Milnor–Wolf 1968)

Virtually nilpotent groups (i.e.∃finite-index nilp subgroups) have PG.

Moreover ∀ f.g. v.solvable group is either v.nilp or exponential growth.

In fact, ∃d ∈Ns.t. |Sⁿ| ∼n^d (Bass–Guivarch).

Theorem (Tits Alternative 1972)

G ≤GL(n,F) f.g. linear grp⇒EitherG v.solv orF2≤G ( exp growth) Corollary: Every f.g. linear group with wPG is v.nilp.

Theorem (Gromov 1981 (van den Dries–Wilkie 1984))

Every f.g. group with wPG is v.nilp.

(5)

Gromov’s Theorem

Theorem (Gromov 1981 (van den Dries–Wilkie 1984))

Every f.g. group with wPG is v.nilp.

A cornerstone result of Geometric Group Theory: a geometric condition yields an algebraic result.

Proof: Geometric.

An ultralimit of (G,_K(n)¹ d_S)^∞_n=1 is a metric group, which can be arranged to be locally compact under the wPG assumption (bounded doubling).

One can apply the solution to Hilbert’s 5th problem by Montgomery, Zippin, and Yamabe, and reduce the problem to a problem on a Lie group.

Other proofs: Kleiner 2007, Analytic “Elementary but Hard”

... Shalom–Tao 2009, Hrushovski 2009, Breuillard–Green–Tao 2011 A new proof (2015): Functional Analytic “Soft and Simple”

(6)

The first (or the last) steps of the proof.

Algebraic parts.

Recall that G is nilpotent if the lower (or upper) central series terminates:

G =G0.G1.· · ·.Gn={e}, where Gi+1= [Gi,G], i.e.,Gi/Gi+1 =Z(G/Gi+1).

(7)

The first (or the last) step of the proof

• Proof is done once we know any infiniteG with wPG virtually surjects ontoZ, i.e, there is a finite index subgrpH≤_f.i.G s.t. HZ.

Proof `a la Milnor–Wolf.

Let G be a f.g. group with wPG of degreed. We want to showG is v.nilp.

WMA ∃q:G Z. ThenN := kerq isf.g. of wPG of degree ≤d −1.

Sketch of the proof: G =ht,s₁, . . . ,s_mi,q(t) = 1 andq(s_i) = 0.

Sl :={t^ks_i^±t^−k :i = 1, . . . ,m,k ∈Z,|k| ≤l} ∪ {e} N=hS

lSli Observe that B_l := (S_l)^l ⊂S^(2l^+1)l has polynomial growth (of deg≤2d).

If∃x ∈S_l+1\(B_l)², thenxB_ltB_l ⊂B_l₊₁ and so|B_l+1| ≥2|B_l|.

∃l₀ s.t. Sl0+1 ⊂(Bl0)² ⊂ hS_l₀i, which implies hS_l₀i=hS

lSli=N.

Moreover, (S_l₀∪ {t^±})²ⁿ⊃F

|k|≤nt^k(S_l₀)ⁿ yields n^dn|(S_l₀)ⁿ|.

Thus, by induction hypothesis, WMAN is nilp andG =hN,ti ∼=NotZ. We claim ∃K ∈Ns.t. the f.i. subgrphN,t^Ki is nilp.

Idea of the proof: Assume for simplicityN is f.g. abelian, N=Z^m×F.

∃K₁ s.t. [F,t^K¹] ={e} Ad_t^K1 ∼A∈GLm(Z) with eigenvalues roots of unity (∵Z^moAZwPG,...) ∃K₂ s.t. A^K² unipotent, K :=K₁K₂.

(8)

The second (or the last) step of the proof

• IfG has a finite-dim (unitary) repn G y^π H with infinite imageπ(G), then∃H ≤_f.i.G s.t. H Z.

This follows from Tits Alternative, but here’s an elementary proof.

Proof by Shalom.

SupposeG has wPG of degreed and G ⊂ U(H), dimH<∞. Note that k1−[g,h]k=kgh−hgk=k(1−g)(1−h)−(1−h)(1−g)k ≤2k1−gkk1−hk.

Take ε >0 small enough. One hash{g ∈G :k1−gk< ε}i ≤_f.i.G. WMA G =hSi,S ⊂ {g ∈G :k1−gk< ε}andG ⊂ U(H) irreducible.

We claim dimH= 1. S’pose not: ∃g₀∈G\C1 s.t.ε0 :=k1−g0k< ε.

· · · ∃s_k ∈S s.t. g_k := [gk−1,s_k]6= 1 g_k ∈/ C1 (∵detg_k = 1 andg_k ≈1) g₀,g₁, . . . are s.t.ε_k :=k1−g_kk<2εε_k−1 and|g_k|_S ≤e^k.

g₀^k⁰g₁^k¹· · ·g_m^k^m,m∈N,|k_i| ≤(10ε)⁻¹, are mutually distinct.

∵ Givenk_l andk_l⁰, put l := min{l :k_l 6=k_l⁰}. Thenkg_l^k^l −g^k

0 l

l k ≥ε_l and kg_l^k₊₁^l⁺¹· · ·g_m^k^m−g^k

0 l+1

l+1 · · ·g^k

0 m0

m k ≤P

k>lε_k·_10ε¹ < ¹₂ε_l.

|Ball_S(_10ε¹ me^m)| ≥(_10ε¹ )^m |Ball_S(n)| (_10ε¹ )¹²^logⁿ=n¹²^log(^10ε¹ ⁾.

(9)

Digest of the first day lecture

S finite symmetric (i.e., g ∈S ⇔g⁻¹∈S) generating subset,e ∈S word metric |x|_S := min{n :x∈Sⁿ} anddS(x,y) :=|x⁻¹y|_S G hasweak polynomial growthif∃d >0 s.t. lim inf_n|Sⁿ|/n^d <∞.

Theorem (Gromov 1981 (van den Dries–Wilkie 1984)) Every f.g. group with wPG is virtually nilpotent.

• Proof is done once we know any infiniteG with wPG virtually surjects ontoZ, i.e, there is a finite index subgrpH≤_f.i.G s.t. q:HZ.

∵ kerq is f.g. and has wPG of degree≤d−1. Induction.

• IfG has a finite-dim (unitary) repn G y^π H with infinite imageπ(G), then∃H ≤_f.i.G s.t. q:H Z.

∵ Tits Alternative or an elementary proof by Shalom.

Day 2:

How to obtain a non-trivial finite-dim repn?

(10)

Reduced Cohomology and

Finite-Dimensional Representation from Random Walks

(11)

Harmonic 1-cocycles

Fix µa fin-supp symm prob measure onG s.t.G =hsuppµi& µ(e)>0.

(π,H) a unitary repn, given (not necessarily fin-dim).

b:G → H 1-cocycle ^def⇔ b(gx) =b(g) +π_gb(x) for∀g,x∈G e.g., 1-coboundary bv(g) =v−πgv, where v ∈ H

µ-harmonic ^def⇔ P

xb(gx)µ(x) =b(g) for∀g ∈G (or justg =e) kb(x)k ≤ |x|_Smax

s∈S kb(s)kand 0 =b(e) =b(x⁻¹) +π_x⁻¹b(x) for ∀x kb(x⁻¹y)k=kb(x⁻¹) +π_x⁻¹b(y)k=kb(x)−b(y)k

b is a 1-cocycle iffρg:v 7→πgv+b(g) is an affine isometric action onH.

b is a coboundary ⇔ ρ has a fixed point ⇔ b is bounded Z¹(G, π) :={1-cocycles} ⊃ {1-coboundaries}=:B¹(G, π), Z¹ is a Hilbert space w.r.t. kbk_L2(µ):= (P

xkb(x)k²µ(x))^1/2. Z¹(G, π) =B¹(G, π)⊕B¹(G, π)^⊥ and

H¹(G, π) :=Z¹(G, π)/B¹(G, π)∼=B¹(G, π)^⊥={harmonic cocycles}.

∵ P

xhb(x),v−πxviµ(x) = 2hP

xb(x)µ(x),vi= 0 ∀v ⇔ harmonic.

(12)

Shalom’s property H

_FD

Theorem H (Mok 95, Korevaar–Schoen 97, Shalom 99) G a f.g. infinite grp of wPG (or amenable or non-(T)) Then, ∃(π,H,b) non-zeroµ-harmonic 1-cocycle.

b(gx) =b(g) +πgb(x) spanb(G) isπ(G)-invariant.

IfK is aπ(G)-invariant subspace, thenPKb is a (harmonic) cocycle.

Observation (Shalom): IfG is v.nilp, then it has propertyHFD.

HFD: Any (π,H) with H¹(G, π)6= 0 has a non-zero finite-dim subrepn.

Equivalently, any harmonic 1-cocycle has a finite-dim summand.

Shalom’s Idea (2004): Prove “wPG ⇒ H_FD” w/o using Gromov’s Thm.

A new proof of Gromov’s Thm.

∵







By Theorem H andH_FD,∃(π,H,b) s.t. π:G → U(H) f.d. repn andb:G → Hnon-zero harmonic cocycle (unbdd).

If|π(G)|=∞, then we are done.

If|π(G)|<∞, then b is an unbdd additive hom from kerπ into H.

We are left to prove Theorem H (^→Day 3) andH_FD for wPG grps.

(13)

Proof of H

_FD

A f.g. group G with wPG has Shalom’s property H_FD:

Any harmonic 1-cocycleb:G → Hwithπ no non-zero f.d. subrepn is zero.

We want to show hb(g),vi= 0 for∀ g ∈S andv ∈ H.

hb(g),vi=P

xhb(gx)−b(x),viµ^∗n(x)

=P

xhb(x),v)i

| {z }

(1)

(g·µ^∗n−µ^∗n)(x)

| {z }

(2)

(♠)

Lemma (1)

Let (π,H) weakly mixing (i.e., no non-zero f.d. subrepn) andb harmonic.

Then, ¹_nP

x|hb(x),vi|²µ^∗n(x)→0.

Note: P

kb(x)k²µ^∗n(x) = P

kb(x⁻¹y)k²µ^∗n−1(x⁻¹)µ(y)

= Pkb(x)−b(y)k²µ^∗n−1(x)µ(y)

= P

kb(x)k²µ^∗n−1(x) +kbk²_L2(µ) = nkbk²_L2(µ).

(14)

Some functional analysis (after Shalom, Chifan–Sinclair)

Lemma (1)

(π,H) weakly mixing andb harmonic ⇒ ¹_nP

x|hb(x),vi|²µ^∗n(x)→0.

Note that|hb(x),vi|²=hb(x)⊗¯b(x),v⊗¯vi_H⊗H¯. P

x(b(x)⊗b(x))µ¯ ^∗n(x) =P

x,y(b(xy)⊗b(xy¯ ))µ^∗n−1(x)µ(y)

=P

x,y(b(x) +π_xb(y))⊗(¯b(x) + ¯π_x¯b(y))µ^∗n−1(x)µ(y)

=P

x(b(x)⊗b(x))µ¯ ^∗n−1(x) +Tⁿ⁻¹w where T :=P

g(π_g ⊗π¯_g)µ(g) andw :=P

y(b(y)⊗b(y))µ(y)¯ ∈ H ⊗H¯

= (1 +T +· · ·+Tⁿ⁻¹)w. T is a self-adjoint contraction onH ⊗H.¯

π w.mixing π(G)⁰∩K(H) =0 no nonzero (π⊗π)(G¯ )-inv vector

∵ UnderH ⊗H ∼¯ =S₂(H), a (π⊗π)(G¯ )-invariant vector corresponds to a Hilbert–Schmidt operator which commutes with π(G).

1 is not an eigenvalue ofT (∵ His strictly convex).

1 n

P

x(b(x)⊗b(x))µ¯ ^∗n(x) = ¹_n(1 +T +· · ·+Tⁿ⁻¹)w →0 by LDCT.

(15)

Entropy (after Erschler–Karlsson) and QED for H

_FD

For p prob measure,H(p) :=−P

xp(x) logp(x)≥0. Shannon entropy p 7→H(p) is concave ∵ (−tlogt)⁰⁰ = (−1/t)<0.

δ(p,q) :=H(^p+q₂ )−¹₂(H(p) +H(q))≥ ¹₈P

x

|p(x)−q(x)|² p(x)+q(x) . Thus for ∀f ≥0 one has

P

xf(x)|p(x)−q(x)| ≤ 8δ(p,q)P

xf(x)²(p(x) +q(x))1/2

. (2)

Why entropy?

• Can estimate♠:=P

xhb(x),v)i(g·µ^∗n−µ^∗n)(x).

• Convenient to the telescoping argument.

H(p) =P

xp(x) log(1/p(x))≤log|suppp| by concavity of log.

H(µ^∗n)≤log|suppµ^∗n|= log|(suppµ)ⁿ| dlogn (w.r.t. lim infn) µ∗ν=P

gµ(g)g·ν andH(µ∗ν)≥P

gµ(g)H(g ·ν) =H(ν).

H(µ∗ν)−H(ν)≥2 min{µ(e), µ(g)}δ(ν,g·ν) for∀g ∈S lim infnnδ(µ^∗n,g·µ^∗n)≤C lim infnn(H(µ^∗n+1)−H(µ^∗n))<∞

|♠|²≤8nδ(µ^∗n,g·µ^∗n)·¹_nP

x|hb(x),v)i|²(g ·µ^∗n+µ^∗n)(x) →

lim inf0.

(16)

Digest of the second day lecture

S finite symmetric (i.e., g ∈S ⇔g⁻¹∈S) generating subset,e ∈S word metric |x|_S := min{n :x∈Sⁿ} anddS(x,y) :=|x⁻¹y|_S G hasweak polynomial growthif∃d >0 s.t. lim inf_n|Sⁿ|/n^d <∞.

Theorem (Gromov 1981 (van den Dries–Wilkie 1984)) Every f.g. group with wPG is virtually nilpotent.

Theorem H (Mok 95, Korevaar–Schoen 97, Shalom 99. To be proved.) G a f.g. infinite grp of wPG (or amenable or non-(T))

Then, ∃(π,H,b) non-zero harmonic 1-cocycle.

A f.g. group G with wPG has Shalom’s property H_FD:

Any non-zero harmonic 1-cocycle has a non-zero finite-dim summand.

∃ non-trivial f.d. cocycle ∃ a virtual surjection toZ Gromov’s Thm.

Day 3:

Proof of Theorem H and further development

(17)

Review on Amenability

(18)

Review on Amenability

Fix µa fin-supp symm prob measure onG s.t.G =hsuppµi.

A group G is amenable if it satisfies the following equivalent conditions.

• (invariant mean) ∃ϕ:`∞(G)→Ca left G-invariant state;

• (approximate invariant mean) ∃ξ_n∈Prob(G) approx G-invariant;

• (Hulanicki) ∃ξ_n∈`2(G) approxG-invariant unit vectors;

• (Kesten) limnµ^∗2n(e)^1/2n=kλ(µ)ⁿδek^1/n=kλ(µ)k= 1.

Here λ:G y`₂G the left reg repn, λ_gδ_x =δ_gx, or λ(µ)ξ=µ∗ξ.

(µ∗ν)(x) := (P

gµ(g)g·ν)(x) =P

gµ(g)ν(g⁻¹x), λ(µ∗ν) =λ(µ)λ(ν).

Q^! ^µ^∗nmay not be approxG-inv in Prob(G) (failure of the Liouville prty), although they are always approxG-inv in`₂(G) after normalization.

Examples of amenable grps include finite grps, abelian grps, subgrps, quotients, extensions, inductive limits, solvable grps, subexp growth grps (∵µ(e)^∗2n≥µ^∗2n(g) for ∀g andµ^∗2n(e)≥ _|supp¹_µ∗2n| = _|(supp¹_µ)2n|).

Grigorchuk (1980/84): ∃an intermediate growth group,

G =hSi with exp(n^0.5) |Sⁿ| exp(n^0.9).

(19)

Existence of harmonic cocycles

(20)

Existence of a harmonic 1-cocycle

Theorem (Mok 95, Korevaar–Schoen 97, Shalom 99)

G a f.g. infinite grp of wPG or more generally amenable (or non-(T)) Then, ∃(π,H,b) non-zeroµ-harmonic 1-cocycle.

Fix a free ultrafilter U on N. limU:`∞(N)→C non-principal character H Hilb space H^U :=`∞(N;H)/{(v_n)n: limUkv_nk= 0} ultrapower h[v_n⁰]_n,[v_n]_ni_HU := limUhv_n⁰,v_ni_H, π_g^U[v_n]_n:= [π_gv_n]_n ultrapower repn

To avoid the parity problem, we will assume µ^∗¹^/² exists.

kλ(µ)ⁿ^/²δek² =µ^∗n(e)→0 but kλ(µ)ⁿ^/²δek²^/ⁿ=µ^∗n(e)¹^/ⁿ→1.

b_n(g) :=λ(µ^∗ⁿ^/²−g ·µ^∗ⁿ^/²)δ_e =µ^∗ⁿ^/²−g·µ^∗ⁿ^/² (omit writingλ).

γ(n) :=kb_nk²_L2(µ)=P

gkb_n(g)k²µ(g) = 2(µ^∗n(e)−µ^∗n+1(e)).

b(g) := [γ(n)⁻¹^/²b_n(g)]_n∈(`₂G)^U b is normalized, i.e.,kbk_L2(µ)= 1.

kP

xb(x)µ(x)k²= limUγ(n)⁻¹kµ^∗ⁿ^/²−µ^∗ⁿ^/²⁺¹k²= limU γ(n)−γ(n+1)

2γ(n) =

Lem0.

Hence b is a normalized µ-harmonic 1-cocycle into (`₂G)^U.

(21)

Existence of a harmonic 1-cocycle: Proof continues

Recall that G is amenable iff

P

gµ(g)kµ^∗ⁿ^/²−g·µ^∗ⁿ^/²k²

2kµ^∗ⁿ^/²k² = ^µ^∗n^(e)−µ_µ∗n(e)^∗n+1^(e) →0.

Lemma (A refinement of Avez’s Lemma)

For γ(n) = 2(µ^∗n(e)−µ^∗n+1(e)), one has limn→∞ γ(n+1) γ(n) = 1.

Proof. Recall that ∃µ^∗¹^/², µ^∗n(e)→0, and µ^∗n(e)^1/n→1.

γ(n) = 2hλ(µ)ⁿ(1−λ(µ))δe, δeidecreasing (∵λ(µ) =λ(µ^∗¹^/²)² ≥0).

δ(n) :=γ(2n) +γ(2n+ 1) = 2(µ^∗2n(e)−µ^∗2(n+1)(e)) also decreasing.

δ(n+ 1)²= (P

ghµ^∗n−g·µ^∗n, µ^∗n+2−g·µ^∗n+2iµ^∗2(g))² ≤δ(n)δ(n+ 2).

δ(n+ 1)/δ(n)≤δ(n+ 2)/δ(n+ 1)% ∃δ≤1.

Thus γ(n)≤Cδⁿ^/² and so 2µ^∗n(e) =P∞

k=nγ(k)≤C⁰δⁿ^/² δ= 1.

limnγ(n+ 1)/γ(n) = 1.

Thus b(g) := [γ(n)⁻¹^/²(µⁿ^/²−g ·µ^∗ⁿ^/²)]n∈(`2G)^U is a nor. µ-harm. coc.

Q^! The 1-cocycleb may depend on the choice of an ultrafilter U. Is it possible to tell whenb is f.d. or has a f.d. summand?

(22)

Further applications: Motivations

Theorem (Shalom 2004)

H_FD is a QI-invariant among f.g. amenable groups.

Some motivation: Virtual nilpotency is a QI invariant by Gromov’s Thm.

Conjecture (Gromov ?): Virtual polycyclicity is a QI invariant.

Malcev–Mostow Theorem: G is v.polycyc iff it is virtually isomorphic to a (uniform) lattice in a simply connected solvable Lie group.

Theorem (Shalom 2004)

Some groups have property H_FD, e.g., L(F) :=Z n(L

ZF), BS(1,p) :={a,t :tat⁻¹ =a^p}, polycyclic grps,. . . and many groups don’t, e.g.,

L(Z) :=Z n(L

ZZ), infinite amenable + no virtual surjection ontoZ,. . . Grigorchuk’s Gap Conjecture: Any f.g. group of super-polynomial growth

has growth rate at least exp(√ n).

Is it true: Every infinite sub-exp(√

n) group has a virtual surjection ontoZ?

(23)

Further applications of harmonic cocycle methods

Xn Random Walk associated with (G, µ), i.e.,X_n: Q

(G, µ)^N3(s_k)^∞_k₌₁7→s₁· · ·s_n∈G. Theorem (Erschler–Oz.)

Let b be a normalized µ-harmonic 1-cocycle. Then, β := lim

n→∞

1 2

X

x

kb(x)k² n −1

2

µ^∗n(x) = lim

n→∞

1 2E

kb(X_n)k² n −1

2

exists. Moreover,β >0 iffb has a non-zero f.d. summand (of dim≤1/β).

Corollary (Erschler–Oz.)

IfG does not have propertyH_FD, then

• lim infnkµ^∗n−µ^∗(1+δ)nk₁ = 2 for everyδ >0.

• lim sup_nP(|X_n|_S ≤c√

n) = 0 for somec >0.

Proof.

IfG failsHFD, then ∃ a normalizedµ-harmonic w.mixing 1-cocycle b.

By Theorem, n^−1/2kb(X_n)k →1 in probability.

(24)

Further applications of harmonic cocycle methods

IfG does not have propertyH_FD, then

• lim inf_nkµ^∗n−µ^∗(1+δ)nk₁ = 2 for everyδ >0.

• lim sup_nP(|X_n|_S ≤c√

n) = 0 for somec >0.

This gives a simple proof of property HFD for many (all?) known cases.

E.g.,L(Z/2Z) =Z n(L

ZZ/2Z) has property H_FD.

∵

µ:= ¹₂(µ0+µ1), µ_i standard nbhd RW on Z(resp.Z/2Z).

Y_n the standard nbhd RW on Z. Then P(|Y_n| ≤c√

n for all n)>0.

Recall that G is amenable iff

P

gµ(g)kµ^∗ⁿ^/²−g·µ^∗ⁿ^/²k²

2kµ^∗ⁿ^/²k² = ^µ^∗n^(e)−µ_µ∗n(e)^∗n+1^(e) →0.

Let G be a f.g. amenable grp without virtual surjection onto Z.

(E.g. Grigorchuk’s grps, Matui–Juschenko–Monod, . . . .) Assume ∃µ^∗¹^/².

Then, lim

m→∞ lim

n→∞

X

g

µ^∗m(g)

µ^∗n(g)−µ^∗n+m(e) µ^∗n(e)−µ^∗n+m(e)

= 0.