The average-case complexity of the Word Problem for groups of matrices over~$\mathbb{Q}$ is linear

Abstract

We show that the Word Problem in finitely generated subgroups of ${\text{GL}}_d(\mathbb{Q})$ can be solved in linear average-case complexity, both when the input words are chosen uniformly at random among the words of a given length and when they are chosen uniformly at random among the reduced words of a given length. This is done under the bit-complexity model, which accounts for the fact that large integers are handled (as numerators and denominators of rational numbers). Corollaries include the fact that the Word Problem can be solved in linear average-case complexity for finitely generated nilpotent or polycyclic groups. Our result also generalizes to matrices in ${\text{GL}}_d(R)$, where $R$ is an algebraic number field. And we show that no algorithm can solve this problem in sublinear worst-case or average-case complexity.

20 pages. The proof of the main theorem of the previous version was incorrect. This new version corrects the bug and significantly extends the results: from matrices with integer coefficients to matrices with rational coefficients, and to the situation where inputs are random reduced words. The lower bound results are also new