Paperlane

no. 5 · Friday 30 October 2026

On the complexity of epimorphism testing with virtually abelian targets

Murray Elder, Jerry Shen and Armin Weiß

math.GR · v2 · 27 pp

Abstract

Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to the direct product of an abelian and a finite group, or to a virtually cyclic group, is decidable. Here we prove that these problems are $\mathsf{NP}$-complete. In addition, we show that testing epimorphism is $\mathsf{NP}$-complete when the target is is the semi-direct product of a finitely generated free-abelian group and a finite group which factors through $\{\pm\text{Id}\}$, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known.

comments
27 pages. Sections 7-9 of previous version of this paper split into a separate article arxiv:TBA
fields
Group Theory
pdf ↗ page arXiv:2501.05283 ↗