The average-case complexity of the Word Problem for groups of matrices over $\mathbb{Z}$ is linear
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912588328075264 |
|---|---|
| author | Bassino, Frédérique Nicaud, Cyril Weil, Pascal |
| author_facet | Bassino, Frédérique Nicaud, Cyril Weil, Pascal |
| contents | We show that the Word Problem in finitely generated subgroups of $\textsf{GL}_d(\mathbb{Z})$ can be solved in linear average-case complexity. This is done under the bit-complexity model, which accounts for the fact that large integers are handled, and under the assumption that the input words are chosen uniformly at random among the words of a given length. Our result generalizes to matrices in $\textsf{GL}_d(R)$, where $R$ is a subring of $\mathbb{C}$, of finite rank over $\mathbb{Z}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00948 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The average-case complexity of the Word Problem for groups of matrices over $\mathbb{Z}$ is linear Bassino, Frédérique Nicaud, Cyril Weil, Pascal Group Theory 20F10, 68Q25, 68W40 We show that the Word Problem in finitely generated subgroups of $\textsf{GL}_d(\mathbb{Z})$ can be solved in linear average-case complexity. This is done under the bit-complexity model, which accounts for the fact that large integers are handled, and under the assumption that the input words are chosen uniformly at random among the words of a given length. Our result generalizes to matrices in $\textsf{GL}_d(R)$, where $R$ is a subring of $\mathbb{C}$, of finite rank over $\mathbb{Z}$. |
| title | The average-case complexity of the Word Problem for groups of matrices over $\mathbb{Z}$ is linear |
| topic | Group Theory 20F10, 68Q25, 68W40 |
| url | https://arxiv.org/abs/2506.00948 |