Geodesic
Efficient computations with counting functions on free groups and free monoids
Sbornik. Mathematics, Tome 214 (2023) no. 10, pp. 1458-1499 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We present efficient algorithms to decide whether two given counting functions on nonabelian free groups or monoids are at bounded distance from each other and to decide whether two given counting quasimorphisms on nonabelian free groups are cohomologous. We work in the multi-tape Turing machine model with nonconstant-time arithmetic operations. In the case of integer coefficients we construct an algorithm of linear time complexity (assuming that the rank is at least $3$ in the monoid case). In the case of rational coefficients we prove that the time complexity is $O(N\log N)$, where $N$ denotes the size of the input, that is, it is the same as in addition of rational numbers (implemented using the Harvey-van der Hoeven algorithm for integer multiplication). These algorithms are based on our previous work which characterizes bounded counting functions. Bibliography: 20 titles.
Keywords: free monoid, free group, counting function, bounded cohomology.
Mots-clés : quasimorphism 
@article{SM_2023_214_10_a5,
     author = {A. L. Talambutsa and T. Hartnick},
     title = {Efficient computations with counting functions on free groups and free monoids},
     journal = {Sbornik. Mathematics},
     pages = {1458--1499},
     year = {2023},
     volume = {214},
     number = {10},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2023_214_10_a5/}
}
TY  - JOUR
AU  - A. L. Talambutsa
AU  - T. Hartnick
TI  - Efficient computations with counting functions on free groups and free monoids
JO  - Sbornik. Mathematics
PY  - 2023
SP  - 1458
EP  - 1499
VL  - 214
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/SM_2023_214_10_a5/
LA  - en
ID  - SM_2023_214_10_a5
ER  - 
%0 Journal Article
%A A. L. Talambutsa
%A T. Hartnick
%T Efficient computations with counting functions on free groups and free monoids
%J Sbornik. Mathematics
%D 2023
%P 1458-1499
%V 214
%N 10
%U http://geodesic.mathdoc.fr/item/SM_2023_214_10_a5/
%G en
%F SM_2023_214_10_a5
A. L. Talambutsa; T. Hartnick. Efficient computations with counting functions on free groups and free monoids. Sbornik. Mathematics, Tome 214 (2023) no. 10, pp. 1458-1499. http://geodesic.mathdoc.fr/item/SM_2023_214_10_a5/

[1] R. Brooks, “Some remarks on bounded cohomology”, Riemann surfaces and related topics: Proceedings of the 1978 Stony Brook conference (State Univ. New York, Stony Brook, NY 1978), Ann. of Math. Stud., 97, Princeton Univ. Press, Princeton, NJ, 1981, 53–63 | DOI | MR | Zbl

[2] D. Calegari, scl, MSJ Mem., 20, Math. Soc. Japan, Tokyo, 2009, xii+209 pp. | DOI | MR | Zbl

[3] S. Cook, On the minimum computation time of functions, Ph.D. thesis, Harvard Univ., Cambridge, MA, 1966

[4] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001, xxii+1180 pp. | MR | Zbl

[5] R. Frigerio, Bounded cohomology of discrete groups, Math. Surveys Monogr., 227, Amer. Math. Soc., Providence, RI, 2017, xvi+193 pp. | DOI | MR | Zbl

[6] R. I. Grigorchuk, “Some results on bounded cohomology”, Combinatorial and geometric group theory (Edinburgh 1993), London Math. Soc. Lecture Notes Ser., 204, Cambridge Univ. Press, Cambridge, 1995, 111–163 | DOI | MR | Zbl

[7] T. Hartnick and P. Schweitzer, “On quasioutomorphism groups of free groups and their transitivity properties”, J. Algebra, 450 (2016), 242–281 | DOI | MR | Zbl

[8] T. Hartnick and A. Sisto, “Bounded cohomology and virtually free hyperbolically embedded subgroups”, Groups Geom. Dyn., 13:2 (2019), 677–694 | DOI | MR | Zbl

[9] T. Hartnick and A. Talambutsa, “Relations between counting functions on free groups and free monoids”, Groups Geom. Dyn., 12:4 (2018), 1485–1521 | DOI | MR | Zbl

[10] A. Hase, Dynamics of $\operatorname{Out}(F_n)$ on the second bounded cohomology of $F_n$, arXiv: 1805.00366

[11] D. Harvey and J. van der Hoeven, “Integer multiplication in time $O(n\log n)$”, Ann. of Math. (2), 193:2 (2021), 563–617 | DOI | MR | Zbl

[12] J. E. Hopcroft, R. Motwani and J. D. Ullman, Introduction to automata theory, languages, and computation, 3rd ed., Pearson Education, Inc., Boston, MA, 2006, xvii+535 pp. | MR | Zbl

[13] P. Kiyashko, Bases for counting functions on free monoids and groups, arXiv: 2306.15520

[14] I. Krasikov and Y. Roditty, “On a reconstruction problem for sequences”, J. Combin. Theory Ser. A, 77:2 (1997), 344–348 | DOI | MR | Zbl

[15] V. I. Levenstein, “Efficient reconstruction of sequences from their subsequences and supersequences”, J. Combin. Theory Ser. A, 93:2 (2001), 310–332 | DOI | MR | Zbl

[16] M. Lothaire, Combinatorics on words, Cambridge Math. Lib., 2nd ed., Cambridge Univ. Press, Cambridge, 1997, xviii+238 pp. | DOI | MR | Zbl

[17] D. Osin, “Acylindrically hyperbolic groups”, Trans. Amer. Math. Soc., 368:2 (2016), 851–888 | DOI | MR | Zbl

[18] M. V. Sapir, Combinatorial algebra: syntax and semantics, With contributions by V. S. Guba, M. V. Volkov, Springer Monogr. Math., Springer, Cham, 2014, xvi+355 pp. | DOI | MR | Zbl

[19] A. Schonhage and V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing (Arch. Elektron. Rechnen), 7 (1971), 281–292 | DOI | MR | Zbl

[20] A. L. Toom, “The complexity of a scheme of functional elements realizing the multiplication of integers”, Soviet Math. Dokl., 4 (1963), 714–716 | MR | Zbl