A characterization of wreath products where knapsack is decidable

arXiv2101.06132MaRDI QIDQ6358356FDOQ6358356

Authors: Pascal Bergsträßer, Moses Ganardi, Georg Zetzsche 

Publication date: 15 January 2021

Abstract: The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group $G$ and takes as input group elements $g_1,ldots,g_n,ginG$ and asks whether there are $x_1,ldots,x_{n}ge0$ with $g_1^{x_1}cdots{g}_n^{x_n}=g$. We study the knapsack problem for wreath products $GwrH$ of groups $G$ and $H$. Our main result is a characterization of those wreath products $GwrH$ for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors $G$ and $H$. To this end, we introduce two decision problems, the intersection knapsack problem and its restriction, the positive intersection knapsack problem. Moreover, we apply our main result to $H_3(mathbbZ)$, the discrete Heisenberg group, and to Baumslag-Solitar groups $mathsfBS(1,q)$ for $qge1$. First, we show that the knapsack problem is undecidable for $Gwr{H}_3(mathbbZ)$ for any $Ge1$. This implies that for $Ge1$ and for infinite and virtually nilpotent groups $H$, the knapsack problem for $GwrH$ is decidable if and only if $H$ is virtually abelian and solvability of systems of exponent equations is decidable for $G$. Second, we show that the knapsack problem is decidable for $GwrmathsfBS(1,q)$ if and only if solvability of systems of exponent equations is decidable for $G$.

This page was built for publication: A characterization of wreath products where knapsack is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358356)