The word problem and growth of groups
<|reference_start|>The word problem and growth of groups: Let $\mathrm{WP}_G$ denote the word problem in a finitely generated group $G$. We consider the complexity of $\mathrm{WP}_G$ with respect to standard deterministic Turing machines. Let $\mathrm{DTIME}_k(t(n))$ be the complexity class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_1(n\log n)$ if and only if $G$ is virtually nilpotent. We relate the complexity of the word problem and the growth of groups by showing that $\mathrm{WP}_G\not\in \mathrm{DTIME}_1(o(n\log\gamma(n)))$, where $\gamma(n)$ is the growth function of $G$. We prove that $\mathrm{WP}_G\in\mathrm{DTIME}_k(n)$ for strongly contracting automaton groups, $\mathrm{WP}_G\in\mathrm{DTIME}_k(n\log n)$ for groups generated by bounded automata, and $\mathrm{WP}_G\in\mathrm{DTIME}_k(n(\log n)^d)$ for groups generated by polynomial automata. In particular, for the Grigorchuk group, $\mathrm{WP}_G\not\in\mathrm{DTIME}_1(n^{1.7674})$ and $\mathrm{WP}_G\in\mathrm{DTIME}_1(n^2)$.<|reference_end|>
@article{bondarenko2024the,
    title={The word problem and growth of groups},
    author={Ievgen Bondarenko},
    journal={arXiv preprint arXiv:2403.11148},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.11148},
    primaryClass={math.GR cs.FL}
}