Corentin Bodart - Membership problems in nilpotent groups

gcc:13954 - journal of Groups, complexity, cryptology, April 25, 2025, Volume 17, Issue 1 - https://doi.org/10.46298/jgcc.2025.17.1.13954
Membership problems in nilpotent groupsArticle

Authors: Corentin Bodart

    We study both the Submonoid Membership problem and the Rational Subset Membership problem in finitely generated nilpotent groups. We give two reductions with important applications. First, Submonoid Membership in any nilpotent group can be reduced to Rational Subset Membership in smaller groups. As a corollary, we prove the existence of a group with decidable Submonoid Membership and undecidable Rational Subset Membership, confirming a conjecture of Lohrey and Steinberg. Second, the Rational Subset Membership problem in $H_3(\mathbb Z)$ can be reduced to the Knapsack problem in the same group, and is therefore decidable. Combining both results, we deduce that the filiform $3$-step nilpotent group has decidable Submonoid Membership.


    Volume: Volume 17, Issue 1
    Published on: April 25, 2025
    Accepted on: April 23, 2025
    Submitted on: July 18, 2024
    Keywords: Mathematics - Group Theory,Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 111 times.
    This article's PDF has been downloaded 43 times.