Hartnick, Tobias; Talambutsa, Alexey Relations between counting functions on free groups and free monoids. (English) Zbl 1451.20005 Groups Geom. Dyn. 12, No. 4, 1485-1521 (2018). Summary: We study counting functions on the free groups \(F_n\) and free monoids \(M_n\) for \(n \geq 2\), which we introduce for combinatorial approach to famous Brooks quasimorphisms on free groups. Two counting functions are considered equivalent if they differ by a bounded function. We find the complete set of linear relations between equivalence classes of counting functions and apply this result to construct an explicit basis for the vector space of such equivalence classes. Moreover, we provide a simple graphical algorithm to determine whether two given counting functions are equivalent. In particular, this yields an algorithm to decide whether two linear combinations of Brooks quasimorphisms on \(F_n\) represent the same class in bounded cohomology. Cited in 2 Documents MSC: 20E05 Free nonabelian groups 20M05 Free semigroups, generators and relations, word problems 20J06 Cohomology of groups 05A15 Exact enumeration problems, generating functions 20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) 20F28 Automorphism groups of groups Keywords:bounded cohomology; free groups; counting function; counting quasimorphism; Brooks quasimorphism PDFBibTeX XMLCite \textit{T. Hartnick} and \textit{A. Talambutsa}, Groups Geom. Dyn. 12, No. 4, 1485--1521 (2018; Zbl 1451.20005) Full Text: DOI arXiv