No Access

MULTIPLICATIVE MEASURES ON FREE GROUPS

ALEXANDRE V. BOROVIK

Department of Mathematics, UMIST, PO Box 88, Manchester M60 1QD, United Kingdom

Supported by the Royal Society Leverhulme Trust Senior Research Fellowship.

Search for more papers by this author

ALEXEI G. MYASNIKOV

Department of Mathematics, The City College of New York, New York, NY 10031, USA

Search for more papers by this author

, and

VLADIMIR N. REMESLENNIKOV

Omsk Branch of Mathematical Institute SB RAS, 13 Pevtsova Street, Omsk 644099, Russia

Supported by EPSRC grant GR/R29451.

Search for more papers by this author

https://doi.org/10.1142/S0218196703001596Cited by:22 (Source: Crossref)

Abstract

We introduce a family of multiplicative distributions {μ_s|s∈(0,1)} on a free group F and study it as a whole. In this approach, the measure of a given set R⊆F is a function μ(R) : s → μ_s(R), rather then just a number. This allows one to evaluate sizes of sets using analytical properties of their measure functions μ(R). We suggest a new hierarchy of subsets R in F with respect to their size, which is based on linear approximations of the function μ(R). This hierarchy is quite sensitive, for example, it allows one to differentiate between sets with the same asymptotic density. Estimates of sizes of various subsets of F are given.

An earlier version of the paper was deposited at arXiv.org/math.GR-0204070.

Keywords:

AMSC: Primary 20P05, Primary 20E05, Secondary 20F10

References

G. N. Arzhantseva, Proc. Amer. Math. Soc. 12, 3205 (2000). Crossref, Web of Science, Google Scholar
L. Bartholdi, Ensign. Math. 45, 83 (1999). Web of Science, Google Scholar
A. V. Borovik and A. G. Myasnikov, Quotient tests and random walks in computational group theory, in preparation . Google Scholar
A. V. Borovik, A. G. Myasnikov and V. N. Remeslennikov, Algorithms for amalgamated products of groups, to appear in Contemporary Math., Amer. Math. Soc . Google Scholar
A. V. Borovik, A. G. Myasnikov and V. Shpilrain, Computational and Statistical Group Theory, Contemporary Math 298 (Amer. Math. Soc., Providence, RI) pp. 21–42. Google Scholar
C. Champetier, Adv. Math. 116, 197 (1995), DOI: 10.1006/aima.1995.1067. Crossref, Web of Science, Google Scholar
N. Chomsky and M. P. Schutzenberger, Computer Programming and Formal Systems, eds. P. Bradford and D. Hirschberg (North-Holland, Amsterdam, 1963) pp. 118–161. Crossref, Google Scholar
J. M. Cohen, J. Funct. Anal. 48, 301 (1982), DOI: 10.1016/0022-1236(82)90090-8. Crossref, Web of Science, Google Scholar
M. J. Dunwoody, Invent. Math. 81, 449 (1985), DOI: 10.1007/BF01388581. Crossref, Web of Science, Google Scholar
D. B. A. Epstein et al. , Word Processing in Groups ( Jones and Bartlett , Boston, London , 1992 ) . Crossref, Google Scholar
P. Flajolet and R. Sedgwick, Analytic combinatorics: Functional equations, rational and algebraic functions, Res. Rep. INRIA RR4103, January 2001 . Google Scholar
C. D. Godsil , Algebraic Combinatorics ( Chapman and Hall , New York , 1993 ) . Google Scholar
R. I. Grigorchuk, Russian Math. Surv. 32, 217 (1977). Google Scholar
R. I. Grigorchuk, Banach Averages on Homogeneous Spaces and Random Walks, Ph.D. Thesis, Moscow State University, 1978 . Google Scholar
R. I. Grigorchuk, Ukrainian Math. J. 31(5), 490 (1978). Google Scholar
R. I. Grigorchuk, Multicomponent Random Systems, eds. R. L. Dobrushin and Ya. G. Sinai (Dekker, New York, 1980) pp. 285–325. Google Scholar
M. Gromov, Inst. Hautes Études Sci. Publ. Math. 53, 53 (1981), DOI: 10.1007/BF02698687. Crossref, Google Scholar
G. H. Hardy , Divergent Series ( Chelsea , 1991 ) . Google Scholar
I. Kapovich and A. G. Myasnikov, J. Algebra 248, 608 (2002), DOI: 10.1006/jabr.2001.9033. Crossref, Web of Science, Google Scholar
J. G. Kemeny , J. L. Snell and A. W. Knapp , Denumerable Markov Chains ( D. van Nostrand , Princeton , 1966 ) . Google Scholar
B. Kitchens , Symbolic Dynamics ( Springer , 1998 ) . Crossref, Google Scholar
D. Kouksov, Proc. Amer. Math. Soc. 126, 2845 (1998), DOI: 10.1090/S0002-9939-98-04741-8. Crossref, Web of Science, Google Scholar
C. F. Miller III , Ann. Math. Stud. 68 ( Princeton University Press , Princeton, NJ , 1971 ) . Google Scholar
D. E. Muller and P. E. Schupp, J. Comp. Syst. Sci. 26, 295 (1983), DOI: 10.1016/0022-0000(83)90003-X. Crossref, Web of Science, Google Scholar
A. D. Myasnikov and A. G. Myasnikov, Groups and Computation III, eds. W. Kantor and A. Seress (de Gruyter, Berlin, 2001) pp. 257–264. Crossref, Google Scholar
Z. Maassarani, J. Phys. A: Math. Gen. 33, 5675 (2000), DOI: 10.1088/0305-4470/33/32/306. Crossref, Google Scholar
E. W. Montrol, Random walks on lattices, Stochastic processes in mathematical physics and engineering, Proc. Symp. Appl. MAth.16 (Amer. Matm. Soc., Providence, RI, 1964) pp. 193–220. Google Scholar
A. Yu. Ol'shanskii, Int. J. Algebra Comput. 2, 1 (1992). Link, Google Scholar
V. J. Rayward-Smith , A First Course in Formal Language Theory ( Blackwell Scientific Publications , Oxford , 1983 ) . Google Scholar
N. J. A. Sloane, On-line Encyclopedia of Integer Sequences , http://www.research.att.com/~njas/sequences/Seis.html . Google Scholar
R. P. Stanley , Enumerative Combinatorics 2 ( Cambridge University Press , 1999 ) . Crossref, Google Scholar
G. Quenell, Contemp. Math. 173, 257 (1994). Crossref, Google Scholar
N. Varopoulos , L. Saloff-Coste and T. Coulhon , Cambridge Tracts in Mathematics 100 ( Cambridge University Press , Cambridge , 1992 ) . Google Scholar
W. Woess, Arch. Math. 41, 363 (1983), DOI: 10.1007/BF01371408. Crossref, Web of Science, Google Scholar