Эффективный алгоритм для решения проблемы распознавания равенства в пространстве классов квазиморфизмов свободной группы

Действительнозначная функция $f$, определенная на данной группе $G$, называется квазиморфизмом этой группы, если существует такая константа $C\ge 0$, что для любых $x,y\in G$ выполнено неравенство $|f(xy)-f(x)-f(y)|<C$. Квазиморфизмы $f,g$ данной группы считаются элементами одного класса, если функция $|f-g|$ ограничена некоторой константой на всей группе $G$.
В 1980 году Р.Брукс построил бесконечномерное подпространство в линейном пространстве всех классов квазиморфизмов свободной группы. Известно, что классы Брукса являются линейно зависимыми, и в работе Калегари -Уолкера 2011 года был предложен экспоненциальный по времени алгоритм, который проверяет равенство нулю линейной суммы классов.
В докладе будет описан алгоритм, который решает данную задачу за линейное время в случае, когда сумма дана с целыми коэффициентами и за квадратичное время, если коэффициенты рациональные.