On the average-case bit complexity of the Word Problem for groups of matrices over ℤ \mathbb{Z}
Frédérique Bassino, [email protected], Cyril Nicaud, [email protected], Pascal Weil, [email protected] · 2025
Read On the average-case bit complexity of the Word Problem for groups of matrices over ℤ \mathbb{Z} by Frédérique Bassino, [email protected], Cyril Nicaud, [email protected], Pascal Weil, [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00948.txt.
Description
Frederique Bassino and co-authors show in 2025 that a classic group task on matrix groups over the rationals takes linear time on the mean case. The head gives that form of the claim. The task asks if a word in group steps equals the plain unit.
Time is counted in bits, since big whole numbers swell as counts grow. The linear claim holds for both raw words and cut down words picked at chance. It then flows to nilpotent and chain like groups for free. No method can beat linear time here, in worst or mean case, the team also shows.
Catalog record
| CREATOR | Frédérique Bassino, [email protected], Cyril Nicaud, [email protected], Pascal Weil, [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00948