Соотношения и быстрые алгоритмы для считающих функций на свободных группах и свободных моноидах

Квазиморфизмом на группе $G$ называется отображение $f$ из $G$ в множество действительных чисел, такое что для всех $x$, $y$ из $G$ значения $|f(xy)-f(x)-f(y)|$ ограничены сверху некоторой константой. Гомоморфизмы и ограниченные функции образуют линейное подпространство в пространстве всех квазиморфизмов, а факторизация по ним изоморфна ядру канонического гомоморфизма из группы ограниченных когомологий $H_b^2 (G,R)$ в группу когомологий $H^2 (G,R)$. Считающие квазиморфизмы на свободной неабелевой группе $F$ возникли в работе Р. Брукса 1980 года с целью установить, что для неё группа $H_b^2(F,R)$ имеет бесконечную размерность. Позже, с помощью аналогичных конструкций, эта задача была решена для фундаментальных групп двумерных ориентируемых поверхностей и всех гиперболических групп в работах Григорчука и Фудживары–Эпштейна.
Однако вопрос о соотношениях между всеми квазиморфизмами Брукса в факторизованном пространстве $H_b^2 (F,R)$ оставался открытым даже для свободной группы. Были известны бесконечные серии естественных комбинаторных соотношений так называемых левых и правых разложений, но не было известно, покрывают ли они всё множество соотношений. Этот вопрос был положительно решён в работе [1]. С помощью установленных результатов были также найдены достаточно простые базисы для линейного пространства Брукса, порождённого в $H_b^2 (F,R)$ считающими квазиморфизмами.
Считающие квазиморфизмы Брукса представляют интерес также по той причине, что на них можно явным комбинаторным образом определить действие группы автоморфизмов свободной группы $\operatorname{Aut}(F)$. Однако, поскольку между квазиморфизмами Брукса есть соотношения, то многие естественные вопросы о действии $\operatorname{Aut}(F)$ приводят к тому, что требуется эффективно решать проблему равенства в пространстве Брукса. Ранее, для решения этой проблемы был известен только экспоненциальный по сложности алгоритм. Базируясь на комбинаторном описании базовых соотношений из работы [1], в новой работе [2] был предложен новый быстрый алгоритм для решения проблемы равенства в пространстве Брукса. Этот алгоритм имеет линейную сложность для случая целочисленных коэффициентов и сложность $N\log(N)$ для рациональных коэффициентов.

Список литературы

1. T. Hartnick, A. Talambutsa, “Relations between counting functions on free groups and free monoids”, Groups, Geometry and Dynamics, 12:4 (2018), 1485–1521    
2. А. Таламбуца, Т. Хартник, “Быстрые алгоритмы для считающих функций на свободных группах и свободных моноидах”, Математический сборник, 214:10 (2023), 116–162