×

Speed of random walks, isoperimetry and compression of finitely generated groups. (English) Zbl 07310598

Summary: We give a solution to the inverse problem (given a prescribed function, find a corresponding group) for large classes of speed, entropy, isoperimetric profile, return probability and \(L_p\)-compression functions of finitely generated groups. For smaller classes, we give solutions among solvable groups of exponential volume growth. As corollaries, we prove a recent conjecture of Amir on joint evaluation of speed and entropy exponents and we obtain a new proof of the existence of uncountably many pairwise non-quasi-isometric solvable groups, originally due to Cornulier and Tessera. We also obtain a formula relating the \(L_p\)-compression exponent of a group and its wreath product with the cyclic group for \(p\) in \([1,2]\).

MSC:

20F69 Asymptotic properties of groups
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
46B85 Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
20E22 Extensions, wreath products, and other compositions of groups
20F05 Generators, relations, and presentations of groups
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Grigorchuk, R. I., Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Math.. Izvestiya: Mathematics, 25, 259-300 (1985) · Zbl 0583.20023 · doi:10.1070/IM1985v025n02ABEH001281
[2] Albiac, Fernando; Kalton, Nigel J., Topics in {B}anach Space Theory, Grad. Texts in Math., 233, xii+373 pp. (2006) · Zbl 1094.46002 · doi:10.1007/0-387-28142-8
[3] Aldous, D.; Fill, J. A., Reversible {M}arkov chains and random walks on graphs (2002)
[4] Amir, Gideon, On the joint behaviour of speed and entropy of random walks on groups, Groups Geom. Dyn.. Groups, Geometry, and Dynamics, 11, 455-467 (2017) · Zbl 1368.20021 · doi:10.4171/GGD/403
[5] Amir, Gideon; Vir\'{a}g, B\'{a}lint, Speed exponents of random walks on groups, Int. Math. Res. Not. IMRN. International Mathematics Research Notices. IMRN, 2567-2598 (2017) · Zbl 1405.60007 · doi:10.1093/imrn/rnv378
[6] Arzhantseva, Goulnara; Dru\c{t}u, Cornelia; Sapir, Mark, Compression functions of uniform embeddings of groups into {H}ilbert and {B}anach spaces, J. Reine Angew. Math.. Journal f\"{u}r die Reine und Angewandte Mathematik. [Crelle’s Journal], 633, 213-235 (2009) · Zbl 1258.20032 · doi:10.1515/CRELLE.2009.066
[7] Arzhantseva, G. N.; Guba, V. S.; Sapir, M. V., Metrics on diagram groups and uniform embeddings in a {H}ilbert space, Comment. Math. Helv.. Commentarii Mathematici Helvetici. A Journal of the Swiss Mathematical Society, 81, 911-929 (2006) · Zbl 1166.20031 · doi:10.4171/CMH/80
[8] Austin, Tim, Amenable groups with very poor compression into {L}ebesgue spaces, Duke Math. J.. Duke Mathematical Journal, 159, 187-222 (2011) · Zbl 1226.43001 · doi:10.1215/00127094-1415860
[9] Austin, Tim; Naor, Assaf; Peres, Yuval, The wreath product of {\( \Bbb Z\)} with {\( \Bbb Z\)} has {H}ilbert compression exponent {\( \frac{2}{3} \)}, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 137, 85-90 (2009) · Zbl 1226.20032 · doi:10.1090/S0002-9939-08-09501-4
[10] Avez, A., Harmonic functions on groups. Differential Geometry and Relativity, Math. Phys. Appl. Math., 3, 27-32 (1976) · Zbl 0345.31004 · doi:10.1007/978-94-010-1508-0_4
[11] Bader, Uri; Furman, Alex; Gelander, Tsachik; Monod, Nicolas, Property ({\(T\)}) and rigidity for actions on {B}anach spaces, Acta Math.. Acta Mathematica, 198, 57-105 (2007) · Zbl 1162.22005 · doi:10.1007/s11511-007-0013-0
[12] Ball, K., Markov chains, {R}iesz transforms and {L}ipschitz maps, Geom. Funct. Anal.. Geometric and Functional Analysis, 2, 137-172 (1992) · Zbl 0788.46050 · doi:10.1007/BF01896971
[13] Bartholdi, Laurent; Erschler, Anna, Groups of given intermediate word growth, Ann. Inst. Fourier (Grenoble). Universit\'{e} de Grenoble. Annales de l’Institut Fourier, 64, 2003-2036 (2014) · Zbl 1317.20043 · doi:10.5802/aif.2902
[14] Bartholdi, Laurent; Erschler, Anna, Distortion of imbeddings of groups of intermediate growth into metric spaces, Proc. Amer. Math. Soc.. Proceedings of the Amer. Math. Soc., 145, 1943-1952 (2017) · Zbl 1431.20027 · doi:10.1090/proc/13453
[15] Baumslag, Gilbert, On finitely presented metabelian groups, Bull. Amer. Math. Soc.. Bulletin of the Amer. Math. Soc., 78, 279 pp. (1972) · Zbl 0253.20052 · doi:10.1090/S0002-9904-1972-12958-6
[16] Bekka, Bachir; de la Harpe, Pierre; Valette, Alain, Kazhdan’s Property ({T}), New Math. Monogr., 11, xiv+472 pp. (2008) · Zbl 1146.22009 · doi:10.1017/CBO9780511542749
[17] Bell, G. C.; Dranishnikov, A. N., A {H}urewicz-type theorem for asymptotic dimension and applications to geometric group theory, Trans. Amer. Math. Soc.. Transactions of the Amer. Math. Soc., 358, 4749-4764 (2006) · Zbl 1117.20032 · doi:10.1090/S0002-9947-06-04088-8
[18] Bendikov, Alexander; Pittet, Christophe; Sauer, Roman, Spectral distribution and {\(L^2\)}-isoperimetric profile of {L}aplace operators on groups, Math. Ann.. Mathematische Annalen, 354, 43-72 (2012) · Zbl 1268.43001 · doi:10.1007/s00208-011-0724-6
[19] Bobkov, S. G.; Houdr\'{e}, C., Isoperimetric constants for product probability measures, Ann. Probab.. The Annals of Probability, 25, 184-205 (1997) · Zbl 0878.60013 · doi:10.1214/aop/1024404284
[20] Brieussel, J\'{e}r\'{e}mie, Behaviors of entropy on finitely generated groups, Ann. Probab.. The Annals of Probability, 41, 4116-4161 (2013) · Zbl 1280.05123 · doi:10.1214/12-AOP761
[21] Brieussel, J\'{e}r\'{e}mie, Growth behaviors in the range {\(e^{r^\alpha}\)}, Afr. Mat.. Afrika Matematika, 25, 1143-1163 (2014) · Zbl 1337.20041 · doi:10.1007/s13370-013-0182-2
[22] Caputo, Pietro; Faggionato, Alessandra; Gaudilli\`ere, Alexandre, Recurrence and transience for long range reversible random walks on a random point process, Electron. J. Probab.. Electronic Journal of Probability, 14, 2580-2616 (2009) · Zbl 1191.60120 · doi:10.1214/EJP.v14-721
[23] Chen, Zhen-Qing; Kumagai, Takashi, Heat kernel estimates for jump processes of mixed types on metric measure spaces, Probab. Theory Related Fields. Probability Theory and Related Fields, 140, 277-317 (2008) · Zbl 1131.60076 · doi:10.1007/s00440-007-0070-5
[24] Cornulier, Yves; Stalder, Yves; Valette, Alain, Proper actions of wreath products and generalizations, Trans. Amer. Math. Soc.. Transactions of the Amer. Math. Soc., 364, 3159-3184 (2012) · Zbl 1283.20049 · doi:10.1090/S0002-9947-2012-05475-4
[25] Cornulier, Yves; Tessera, Romain, Dehn function and asymptotic cones of {A}bels’ group, J. Topol.. Journal of Topology, 6, 982-1008 (2013) · Zbl 1311.20034 · doi:10.1112/jtopol/jtt019
[26] de Cornulier, Yves; Tessera, Romain; Valette, Alain, Isometric group actions on {H}ilbert spaces: growth of cocycles, Geom. Funct. Anal.. Geometric and Functional Analysis, 17, 770-792 (2007) · Zbl 1129.22004 · doi:10.1007/s00039-007-0604-0
[27] Coulhon, Thierry, Ultracontractivity and {N}ash type inequalities, J. Funct. Anal.. Journal of Functional Analysis, 141, 510-539 (1996) · Zbl 0887.58009 · doi:10.1006/jfan.1996.0140
[28] Coulhon, Thierry; Grigor{\cprime}yan, Alexander, On-diagonal lower bounds for heat kernels and {M}arkov chains, Duke Math. J.. Duke Mathematical Journal, 89, 133-199 (1997) · Zbl 0920.58064 · doi:10.1215/S0012-7094-97-08908-0
[29] Coulhon, Thierry; Saloff-Coste, Laurent, Isop\'{e}rim\'{e}trie pour les groupes et les vari\'{e}t\'{e}s, Rev. Mat. Iberoamericana. Revista Matem\'{a}tica Iberoamericana, 9, 293-314 (1993) · Zbl 0782.53066 · doi:10.4171/RMI/138
[30] Coulhon, Thierry; Saloff-Coste, Laurent, Vari\'{e}t\'{e}s riemanniennes isom\'{e}triques \`a l’infini, Rev. Mat. Iberoamericana. Revista Matem\'{a}tica Iberoamericana, 11, 687-726 (1995) · Zbl 0845.58054 · doi:10.4171/RMI/190
[31] Derriennic, Yves, Lois “z\'{e}ro ou deux” pour les processus de {M}arkov. {A}pplications aux marches al\'{e}atoires, Ann. Inst. H. Poincar\'{e} Sect. B (N.S.), 12, 111-129 (1976) · Zbl 0353.60075
[32] Diaconis, P.; Saloff-Coste, L., Nash inequalities for finite {M}arkov chains, J. Theoret. Probab.. Journal of Theoretical Probability, 9, 459-510 (1996) · Zbl 0870.60064 · doi:10.1007/BF02214660
[33] Dvoretzky, A.; Erd\"{o}s, P., Some problems on random walk in space. Proceedings of the {S}econd {B}erkeley {S}ymposium on {M}athematical {S}tatistics and {P}robability, 1950, 353-367 (1951) · Zbl 0044.14001
[34] Enflo, Per, On the nonexistence of uniform homeomorphisms between {\(L\sb{p} \)}-spaces, Ark. Mat.. Arkiv f\"{o}r Matematik, 8, 103-105 (1969) · Zbl 0196.14002 · doi:10.1007/BF02589549
[35] Erschler, Anna, On drift and entropy growth for random walks on groups, Ann. Probab.. The Annals of Probability, 31, 1193-1204 (2003) · Zbl 1043.60005 · doi:10.1214/aop/1055425775
[36] Erschler, Anna, Piecewise automatic groups, Duke Math. J.. Duke Mathematical Journal, 134, 591-613 (2006) · Zbl 1159.20019 · doi:10.1215/S0012-7094-06-13435-X
[37] Erschler, Anna, Poisson-{F}urstenberg boundaries, large-scale geometry and growth of groups. Proceedings of the {I}nternational {C}ongress of {M}athematicians. {V}olume {II}, 681-704 (2010) · Zbl 1258.60009 · doi:10.1142/9789814324359_0069
[38] Ershov, Mikhail; Jaikin-Zapirain, Andrei, Property ({T}) for noncommutative universal lattices, Invent. Math.. Inventiones Mathematicae, 179, 303-347 (2010) · Zbl 1205.22003 · doi:10.1007/s00222-009-0218-2
[39] Eskin, Alex; Fisher, David; Whyte, Kevin, Coarse differentiation of quasi-isometries {I}: {S}paces not quasi-isometric to {C}ayley graphs, Ann. of Math. (2). Annals of Mathematics. Second Series, 176, 221-260 (2012) · Zbl 1264.22005 · doi:10.4007/annals.2012.176.1.3
[40] Eskin, Alex; Fisher, David; Whyte, Kevin, Coarse differentiation of quasi-isometries {II}: {R}igidity for {S}ol and lamplighter groups, Ann. of Math. (2). Annals of Mathematics. Second Series, 177, 869-910 (2013) · Zbl 1398.22012 · doi:10.4007/annals.2013.177.3.2
[41] Farb, Benson; Mosher, Lee, A rigidity theorem for the solvable {B}aumslag-{S}olitar groups, Invent. Math.. Inventiones Mathematicae, 131, 419-451 (1998) · Zbl 0937.22003 · doi:10.1007/s002220050210
[42] Farb, Benson; Mosher, Lee, Quasi-isometric rigidity for the solvable {B}aumslag-{S}olitar groups. {II}, Invent. Math.. Inventiones Mathematicae, 137, 613-649 (1999) · Zbl 0931.20035 · doi:10.1007/s002220050337
[43] Farb, Benson; Mosher, Lee, Problems on the geometry of finitely generated solvable groups. Crystallographic {G}roups and their {G}eneralizations ({K}ortrijk, 1999), Contemp. Math., 262, 121-134 (2000) · Zbl 0983.20038 · doi:10.1090/conm/262/04170
[44] Gournay, Antoine, The {L}iouville property and {H}ilbertian compression, Ann. Inst. Fourier (Grenoble). Universit\'{e} de Grenoble. Annales de l’Institut Fourier, 66, 2435-2454 (2016) · Zbl 1397.20062 · doi:10.5802/aif.3067
[45] Grigorchuk, Rostislav I.; Nowak, Piotr W., Diameters, distortion, and eigenvalues, European J. Combin.. European Journal of Combinatorics, 33, 1574-1587 (2012) · Zbl 1246.05046 · doi:10.1016/j.ejc.2012.03.019
[46] available on author’s webpage, Asymptotic invariants of infinite groups. Geometric {G}roup {T}heory, {V}ol. 2, London Math. Soc. Lecture Note Ser., 182, 1-295 (1993)
[47] Gromov, Mikhael, Groups of polynomial growth and expanding maps, Inst. Hautes \'{E}tudes Sci. Publ. Math.. Institut des Hautes \'{E}tudes Scientifiques. Publications Math\'{e}matiques, 53-73 (1981) · Zbl 0474.20018 · doi:10.1007/BF02698687
[48] Guentner, Erik; Kaminker, Jerome, Exactness and uniform embeddability of discrete groups, J. London Math. Soc. (2). Journal of the London Mathematical Society. Second Series, 70, 703-718 (2004) · Zbl 1082.46049 · doi:10.1112/S0024610704005897
[49] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.). Amer. Math. Soc.. Bulletin. New Series, 43, 439-561 (2006) · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[50] Jolissaint, Pierre-Nicolas; Valette, Alain, {\(L^p\)}-distortion and {\(p\)}-spectral gap of finite graphs, Bull. Lond. Math. Soc.. Bulletin of the London Mathematical Society, 46, 329-341 (2014) · Zbl 1297.46021 · doi:10.1112/blms/bdt096
[51] Ka\u{\i}manovich, V. A.; Vershik, A. M., Random walks on discrete groups: boundary and entropy, Ann. Probab.. The Annals of Probability, 11, 457-490 (1983) · Zbl 0641.60009 · doi:10.1214/aop/1176993497
[52] Kasparov, Gennadi; Yu, Guoliang, The coarse geometric {N}ovikov conjecture and uniform convexity, Adv. Math.. Advances in Mathematics, 206, 1-56 (2006) · Zbl 1102.19003 · doi:10.1016/j.aim.2005.08.004
[53] Kassabov, Martin; Pak, Igor, Groups of oscillating intermediate growth, Ann. of Math. (2). Annals of Mathematics. Second Series, 177, 1113-1145 (2013) · Zbl 1283.20027 · doi:10.4007/annals.2013.177.3.7
[54] Kesten, Harry, Full {B}anach mean values on countable groups, Math. Scand.. Mathematica Scandinavica, 7, 146-156 (1959) · Zbl 0092.26704 · doi:10.7146/math.scand.a-10568
[55] Lafforgue, Vincent, Un renforcement de la propri\'{e}t\'{e} ({T}), Duke Math. J.. Duke Mathematical Journal, 143, 559-602 (2008) · Zbl 1158.46049 · doi:10.1215/00127094-2008-029
[56] Lawler, Gregory F.; Sokal, Alan D., Bounds on the {\(L^2\)} spectrum for {M}arkov chains and {M}arkov processes: a generalization of {C}heeger’s inequality, Trans. Amer. Math. Soc.. Transactions of the Amer. Math. Soc., 309, 557-580 (1988) · Zbl 0716.60073 · doi:10.2307/2000925
[57] Lee, James R.; Peres, Yuval, Harmonic maps on amenable groups and a diffusive lower bound for random walks, Ann. Probab.. The Annals of Probability, 41, 3392-3419 (2013) · Zbl 1284.05250 · doi:10.1214/12-AOP779
[58] Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L., Markov chains and mixing times, xviii+371 pp. (2009) · Zbl 1160.60001 · doi:10.1090/mbk/058
[59] Linial, Nathan; Magen, Avner; Naor, A., Girth and {E}uclidean distortion, Geom. Funct. Anal.. Geometric and Functional Analysis, 12, 380-394 (2002) · Zbl 0991.05037 · doi:10.1007/s00039-002-8251-y
[60] Linial, Nathan; London, Eran; Rabinovich, Yuri, The geometry of graphs and some of its algorithmic applications, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 15, 215-245 (1995) · Zbl 0827.05021 · doi:10.1007/BF01200757
[61] Linial, Nathan; Magen, Avner, Least-distortion {E}uclidean embeddings of graphs: products of cycles and expanders, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 79, 157-171 (2000) · Zbl 1026.05032 · doi:10.1006/jctb.2000.1953
[62] Lyons, Russell; Peres, Yuval, Probability on Trees and Networks, Cambridge Ser. Stat. Prob. Math., 42, xv+699 pp. (2016) · Zbl 1376.05002 · doi:10.1017/9781316672815
[63] Matou\v{s}ek, Ji\v{r}\'{\i}, On embedding expanders into {\(l_p\)} spaces, Israel J. Math.. Israel Journal of Mathematics, 102, 189-197 (1997) · Zbl 0947.46007 · doi:10.1007/BF02773799
[64] Mazur, S., Une remarque sur l’hom{\'e}omorphie des champs fonctionnels, Studia Mathematica, 1, 83-85 (1929) · doi:10.4064/sm-1-1-83-85
[65] Mendel, Manor; Naor, Assaf, Metric cotype, Ann. of Math. (2). Annals of Mathematics. Second Series, 168, 247-298 (2008) · Zbl 1187.46014 · doi:10.4007/annals.2008.168.247
[66] Mimura, Masato, Sphere equivalence, {B}anach expanders, and extrapolation, Int. Math. Res. Not. IMRN. International Mathematics Research Notices. IMRN, 4372-4391 (2015) · Zbl 1334.46020 · doi:10.1093/imrn/rnu075
[67] Naor, Assaf; Peres, Yuval, Embeddings of discrete groups and the speed of random walks, Int. Math. Res. Not. IMRN. International Mathematics Research Notices. IMRN, 076-34 (2008) · Zbl 1163.46007 · doi:10.1093/imrn/rnn076
[68] Naor, Assaf; Peres, Yuval, {\(L_p\)} compression, traveling salesmen, and stable walks, Duke Math. J.. Duke Mathematical Journal, 157, 53-108 (2011) · Zbl 1268.20044 · doi:10.1215/00127094-2011-002
[69] Naor, Assaf; Peres, Yuval; Schramm, Oded; Sheffield, Scott, Markov chains in smooth {B}anach spaces and {G}romov-hyperbolic metric spaces, Duke Math. J.. Duke Mathematical Journal, 134, 165-197 (2006) · Zbl 1108.46012 · doi:10.1215/S0012-7094-06-13415-4
[70] Naor, Assaf; Silberman, Lior, Poincar\'{e} inequalities, embeddings, and wild groups, Compos. Math.. Compositio Mathematica, 147, 1546-1572 (2011) · Zbl 1267.20057 · doi:10.1112/S0010437X11005343
[71] Newman, Ilan; Rabinovich, Yuri, A lower bound on the distortion of embedding planar metrics into {E}uclidean space, Discrete Comput. Geom.. Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, 29, 77-81 (2003) · Zbl 1050.68154 · doi:10.1007/s00454-002-2813-5
[72] Olshanskii, Alexander Yu.; Osin, Denis V., A quasi-isometric embedding theorem for groups, Duke Math. J.. Duke Mathematical Journal, 162, 1621-1648 (2013) · Zbl 1331.20054 · doi:10.1215/00127094-2266251
[73] Peres, Yuval; Revelle, David, Mixing times for random walks on finite lamplighter groups, Electron. J. Probab.. Electronic Journal of Probability, 9, 825-845 (2004) · Zbl 1064.60095 · doi:10.1214/EJP.v9-198
[74] Pittet, C.; Saloff-Coste, L., On random walks on wreath products, Ann. Probab.. The Annals of Probability, 30, 948-977 (2002) · Zbl 1021.60004 · doi:10.1214/aop/1023481013
[75] Pittet, C.; Saloff-Coste, L., On the stability of the behavior of random walks on groups, J. Geom. Anal.. The Journal of Geometric Analysis, 10, 713-737 (2000) · Zbl 0985.60043 · doi:10.1007/BF02921994
[76] Rao, M. M., Random and Vector Measures, Ser. Multivariate Anal., 9, xiv+538 pp. (2012) · Zbl 1283.60007 · doi:10.1142/8678
[77] Saloff-Coste, Laurent, Lectures on finite {M}arkov chains. Lectures on Probability Theory and Statistics, Lecture Notes in Math., 1665, 301-413 (1997) · Zbl 0885.60061 · doi:10.1007/BFb0092621
[78] Saloff-Coste, Laurent; Zheng, Tianyi, Random walks and isoperimetric profiles under moment conditions, Ann. Probab.. The Annals of Probability, 44, 4133-4183 (2016) · Zbl 1378.60019 · doi:10.1214/15-AOP1070
[79] Tessera, Romain, Asymptotic isoperimetry on groups and uniform embeddings into {B}anach spaces, Comment. Math. Helv.. Commentarii Mathematici Helvetici. A Journal of the Swiss Mathematical Society, 86, 499-535 (2011) · Zbl 1274.43009 · doi:10.4171/CMH/232
[80] Tessera, Romain, Isoperimetric profile and random walks on locally compact solvable groups, Rev. Mat. Iberoam.. Revista Matem\'{a}tica Iberoamericana, 29, 715-737 (2013) · Zbl 1267.43004 · doi:10.4171/RMI/736
[81] Yu, Guoliang, The coarse {B}aum-{C}onnes conjecture for spaces which admit a uniform embedding into {H}ilbert space, Invent. Math.. Inventiones Mathematicae, 139, 201-240 (2000) · Zbl 0956.19004 · doi:10.1007/s002229900032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.