一句话：证明代数数上几乎可解矩阵群的恒等问题与群问题可判定，显著缩小已知不可判定边界。
Tits 择一定理指出，有限生成矩阵群要么包含非交换自由子群 F2，要么是几乎可解的。本文研究几乎可解矩阵群中的两个判定问题：恒等问题（给定有限生成子半群是否包含单位矩阵）与群问题（给定有限生成子半群是否为群）。作者证明，在代数数域 \overline{\mathbb{Q}} 上的几乎可解矩阵群中，这两个问题都是可判定的。该证明扩展了 Bodart、Ciobanu、Metcalfe 与 Shaffrir 关于幂零群的判定性结果，以及 Dong 在 STOC’24 中关于亚交换群的结果。由于在包含 F2 × F2 的矩阵群中这两个问题已知不可判定，本文结果显著缩小了二者之间的可判定性差距。
The Tits alternative states that a finitely generated matrix group either contains a nonabelian free subgroup F2, or it is virtually solvable. This paper considers two decision problems in virtually solvable matrix groups: the Identity Problem (does a given finitely generated subsemigroup contain the identity matrix?), and the Group Problem (is a given finitely generated subsemigroup a group?). We show that both problems are decidable in virtually solvable matrix groups over the field of algebraic numbers $\overline {\mathbb{Q}} $ . Our proof also extends the decidability result for nilpotent groups by Bodart, Ciobanu, Metcalfe and Shaffrir, and the decidability result for metabelian groups by Dong (STOC’24). Since the Identity Problem and the Group Problem are known to be undecidable in matrix groups containing F2 × F2, our result significantly reduces the decidability gap for both decision problems.
DOI 原文 ·
@inproceedings{paperbot8632,
title = {The Identity Problem in virtually solvable matrix groups over algebraic numbers},
author = {Corentin Bodart and Ruiwen Dong},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00026}
}