Efficient computations with counting functions on free groups and free monoids

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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(NlogN), 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.

About the authors

Alexey Leonidovich Talambutsa

Steklov Mathematical Institute of Russian Academy of Sciences

Author for correspondence.
Email: altal@mi-ras.ru
Candidate of physico-mathematical sciences, no status

Tobias Hartnick

Karlsruhe Institute of Technology

Email: tobias.hartnick@kit.de

References

  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
  2. D. Calegari, scl, MSJ Mem., 20, Math. Soc. Japan, Tokyo, 2009, xii+209 pp.
  3. S. Cook, On the minimum computation time of functions, Ph.D. thesis, Harvard Univ., Cambridge, MA, 1966
  4. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, Алгоритмы: построение и анализ, Вильямс, М., 2011, 1296 с.
  5. R. Frigerio, Bounded cohomology of discrete groups, Math. Surveys Monogr., 227, Amer. Math. Soc., Providence, RI, 2017, xvi+193 pp.
  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
  7. T. Hartnick, P. Schweitzer, “On quasioutomorphism groups of free groups and their transitivity properties”, J. Algebra, 450 (2016), 242–281
  8. T. Hartnick, A. Sisto, “Bounded cohomology and virtually free hyperbolically embedded subgroups”, Groups Geom. Dyn., 13:2 (2019), 677–694
  9. T. Hartnick, A. Talambutsa, “Relations between counting functions on free groups and free monoids”, Groups Geom. Dyn., 12:4 (2018), 1485–1521
  10. A. Hase, Dynamics of $operatorname{Out}(F_n)$ on the second bounded cohomology of $F_n$
  11. D. Harvey, J. van der Hoeven, “Integer multiplication in time $O(nlog n)$”, Ann. of Math. (2), 193:2 (2021), 563–617
  12. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to automata theory, languages, and computation, 3rd ed., Pearson Education, Inc., Boston, MA, 2006, xvii+535 pp.
  13. P. Kiyashko, Bases for counting functions on free monoids and groups
  14. I. Krasikov, Y. Roditty, “On a reconstruction problem for sequences”, J. Combin. Theory Ser. A, 77:2 (1997), 344–348
  15. V. I. Levenstein, “Efficient reconstruction of sequences from their subsequences and supersequences”, J. Combin. Theory Ser. A, 93:2 (2001), 310–332
  16. M. Lothaire, Combinatorics on words, Cambridge Math. Lib., 2nd ed., Cambridge Univ. Press, Cambridge, 1997, xviii+238 pp.
  17. D. Osin, “Acylindrically hyperbolic groups”, Trans. Amer. Math. Soc., 368:2 (2016), 851–888
  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.
  19. A. Schonhage, V. Strassen, “Schnelle Multiplikation grosser Zahlen”, Computing (Arch. Elektron. Rechnen), 7 (1971), 281–292
  20. А. Л. Тоом, “О сложности схемы из функциональных элементов, реализующей умножение целых чисел”, Докл. АН СССР, 150:3 (1963), 496–498

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Таламбуца А.L., Хартник Т.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).