Multiplicative measures on free groups. (English) Zbl 1061.20066
A family of multiplicative distributions on a free group \(F\) is introduced. This allows one to evalute sizes of sets using analytical properties of their measure functions. Estimates of sizes of various subsets of \(F\) are presented.
This paper is motivated by needs of practical computations in finitely generated discrete infinite groups. The practical complexity of algorithmic problems for such groups can be based on the tools developed in the paper.
This paper is motivated by needs of practical computations in finitely generated discrete infinite groups. The practical complexity of algorithmic problems for such groups can be based on the tools developed in the paper.
Reviewer: V. A. Roman’kov (Omsk)
MSC:
| 20P05 | Probabilistic methods in group theory |
| 20E05 | Free nonabelian groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F69 | Asymptotic properties of groups |
| 43A05 | Measures on groups and semigroups, etc. |
| 60G50 | Sums of independent random variables; random walks |
Keywords:
free groups; random walks; growth functions; generating functions; regular sets; amenable groups; asymptotic densitiesReferences:
| [1] | Arzhantseva G. N., Proc. Amer. Math. Soc. 12 pp 3205– |
| [2] | Bartholdi L., Ensign. Math. 45 pp 83– |
| [3] | 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. |
| [4] | DOI: 10.1006/aima.1995.1067 · Zbl 0847.20030 · doi:10.1006/aima.1995.1067 |
| [5] | DOI: 10.1016/S0049-237X(08)72023-8 · doi:10.1016/S0049-237X(08)72023-8 |
| [6] | DOI: 10.1016/0022-1236(82)90090-8 · Zbl 0499.20023 · doi:10.1016/0022-1236(82)90090-8 |
| [7] | DOI: 10.1007/BF01388581 · Zbl 0572.20025 · doi:10.1007/BF01388581 |
| [8] | Epstein D. B. A., Word Processing in Groups (1992) |
| [9] | Godsil C. D., Algebraic Combinatorics (1993) · Zbl 0784.05001 |
| [10] | Grigorchuk R. I., Russian Math. Surv. 32 pp 217– |
| [11] | Grigorchuk R. I., Ukrainian Math. J. 31 pp 490– |
| [12] | R. I. Grigorchuk, Multicomponent Random Systems, eds. R. L. Dobrushin and Ya. G. Sinai (Dekker, New York, 1980) pp. 285–325. |
| [13] | DOI: 10.1007/BF02698687 · Zbl 0474.20018 · doi:10.1007/BF02698687 |
| [14] | Hardy G. H., Divergent Series (1991) · Zbl 0897.01044 |
| [15] | DOI: 10.1006/jabr.2001.9033 · Zbl 1001.20015 · doi:10.1006/jabr.2001.9033 |
| [16] | Kemeny J. G., Denumerable Markov Chains (1966) · Zbl 0178.53306 |
| [17] | DOI: 10.1007/978-3-642-58822-8 · doi:10.1007/978-3-642-58822-8 |
| [18] | DOI: 10.1090/S0002-9939-98-04741-8 · Zbl 0909.20020 · doi:10.1090/S0002-9939-98-04741-8 |
| [19] | Miller C. F., Ann. Math. Stud. 68 (1971) |
| [20] | DOI: 10.1016/0022-0000(83)90003-X · Zbl 0537.20011 · doi:10.1016/0022-0000(83)90003-X |
| [21] | A. D. Myasnikov and A. G. Myasnikov, Groups and Computation III, eds. W. Kantor and A. Seress (de Gruyter, Berlin, 2001) pp. 257–264. |
| [22] | DOI: 10.1088/0305-4470/33/32/306 · Zbl 0980.82007 · doi:10.1088/0305-4470/33/32/306 |
| [23] | DOI: 10.1142/S0218196792000025 · Zbl 0779.20016 · doi:10.1142/S0218196792000025 |
| [24] | Rayward-Smith V. J., A First Course in Formal Language Theory (1983) |
| [25] | DOI: 10.1017/CBO9780511609589 · doi:10.1017/CBO9780511609589 |
| [26] | DOI: 10.1090/conm/173/01830 · doi:10.1090/conm/173/01830 |
| [27] | Varopoulos N., Cambridge Tracts in Mathematics 100 (1992) |
| [28] | DOI: 10.1007/BF01371408 · Zbl 0522.20043 · doi:10.1007/BF01371408 |
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.
