Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

On the generalized membership problem in relatively hyperbolic groups

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the generalized membership problem—whether a given element belongs to the subgroup generated by other given elements—is decidable for relatively quasi-convex subgroups of finitely presented relatively hyperbolic…

desk verdict A clean synthesis of known results; the main theorem is plausible but the halting guarantee rests on an unproved extracted stronger form of a cited theorem. read the letter →

arxiv 1908.03525 v2 pith:F4OEWMMP submitted 2019-08-09 math.GR

Olga Kharlampovich , Pascal Weil This is my paper · ORCID
classification math.GR MSC 20F1020F6520F67
keywords generalizedmembershipproblemrelativelyhyperbolicgroupsquasi-convexsubgroupspartialalgorithmStallingsgraphsautomaticstructurestoralperipheral
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper takes on the generalized membership problem: given a list of words that generate a subgroup H in a group G and a word representing an element g, decide whether g is in H. The authors establish that, in a finitely presented relatively hyperbolic group whose peripheral subgroups satisfy a list of algorithmic and structural conditions (called (Hyp)), this problem is decidable whenever H is relatively quasi-convex. The proof runs two searches in parallel: one enumerates evidence that g belongs to H, the other searches for a finite-index enlargement of H within the peripheral structure that still excludes g. The theorem guarantees that in the relevant cases one of the two searches halts, and whichever halts decides the question correctly. Since the hypotheses cover toral relatively hyperbolic groups, the result gives a uniform decision procedure for a broad and much-studied class of groups.

What carries the argument

The argument rests on four pieces: the finite labeled graph of a finitely generated subgroup of a free group (the Stallings graph), which lets the membership search enumerate what the relators force; a geodesic automatic structure for G, built from automatic structures on the peripheral subgroups, which provides a computable set of representatives and a route to deciding membership for quasi-convex subgroups; the finite family of maximal infinite parabolic subgroups of a relatively quasi-convex subgroup, which organizes which peripheral directions matter; and a separation theorem from [24] that enlarges H by finite-index subgroups of those parabolic subgroups while excluding a given outside element. The non-membership semi-algorithm combines the last two with an existing partial algorithm that handles relatively quasi-convex subgroups with peripherally finite index.

What would settle it

Find a relatively quasi-convex subgroup H in a finitely presented relatively hyperbolic group satisfying (Hyp) and an element g outside H such that for every finite-index subgroup R of every peripheral conjugate P^x containing the relevant H∩P^x, the group generated by H and R contains g; such an example would refute the extracted separation statement and break the guaranteed halting of the non-membership semi-algorithm.

Watch

Extended reading notes

Core claim

Theorem 5 states that there is a partial algorithm which, on input g,h1,...,hk, halts at least when g is in H or when the subgroup H generated by the hi is relatively quasi-convex and g is not in H, and when it halts it decides whether g is in H. The membership direction is a classical enumeration: start with the labeled graph representing the subgroup generated by the hi in the free group, repeatedly attach loops for relators and fold, and check whether g labels a loop at the base vertex. The non-membership direction is the new content: nondeterministically choose finitely many conjugates of peripheral subgroups, choose finite-index subgroups of each, adjoin them to H, and run a previously known partial algorithm for relatively quasi-convex subgroups with peripherally finite index. A separation theorem from [24] is what guarantees that, for relatively quasi-convex H and g outside H, some such choice keeps g outside while making the enlarged subgroup peripherally finite, so the search halts with a certificate of non-membership.

Load-bearing premise

The load-bearing premise is the separation statement extracted from [24, Theorem 1.7]: for any relatively quasi-convex H and any g outside H, one can enlarge H by finite-index subgroups of finitely many peripheral conjugates so that g remains outside and all parabolic intersections of the enlarged subgroup are finite or finite-index; if that statement fails, the non-membership search may never halt on legitimate inputs.

Editorial extensions

If this is right

  • For every relatively quasi-convex subgroup H of a finitely presented relatively hyperbolic group satisfying (Hyp), the generalized membership problem is decidable: the algorithm halts and outputs the correct yes/no answer.
  • The hypotheses are satisfied in particular by toral relatively hyperbolic groups, so the result applies to that whole class.
  • When the algorithm halts it produces an explicit certificate: either a sequence of relator-rewritings and foldings exhibiting g as an element of H, or an enlarged subgroup of peripherally finite index that contains H but not g.
  • The non-membership search is a uniform enumeration over finitely many peripheral conjugates and finite-index subgroups, so the theorem yields a single partial algorithm for all finitely presented groups in the class, rather than a group-by-group construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same two-search template should transfer to other group classes equipped with an automatic structure and a separation property for quasi-convex subgroups; the proof does not use anything peculiar to relative hyperbolicity beyond those ingredients.
  • Because the theorem only guarantees halting in the quasi-convex case, a natural next step is to seek complexity bounds: the paper notes the algorithm has no recursive time bound, so asking whether toral relatively hyperbolic groups admit a primitive recursive or polynomial version is a concrete open problem.
  • If the extracted separation statement from [24] could be made effective (computing the finite-index subgroups instead of guessing them), the non-deterministic enumeration in Step (2) would become deterministic and the practical behavior of the algorithm would improve considerably.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proves that the generalized membership problem (given generators h_1,...,h_k for a subgroup H of a finitely presented relatively hyperbolic group G and a word g, decide whether g lies in H) has a partial algorithm that halts on all instances with g in H, and also on all instances where H is relatively quasi-convex and g is not in H. The main result, Theorem 5, is obtained by running concurrently a positive semi-algorithm (Stallings-graph enumeration of the subgroup generated by H and the relators) and a negative semi-algorithm that nondeterministically enlarges H by finite-index subgroups of the relevant peripheral subgroups until the enlarged subgroup has peripherally finite index and excludes g, at which point a previously established partial algorithm from [22] decides membership. The paper relies on hypotheses (Hyp) on the peripheral structure: bi-automatic structures and slenderness/LERF assumptions, recursive enumerability of finite-index subgroups, and decidability of membership in peripheral subgroups. These hypotheses hold in particular for toral relatively hyperbolic groups.

Significance. If the result is correct, it establishes decidability of the generalized membership problem for relatively quasi-convex subgroups of finitely presented relatively hyperbolic groups under rather mild peripheral hypotheses, covering toral relatively hyperbolic groups. This is a valuable contribution, as it combines the Stallings-graph approach of [22] with the peripheral-separation technique of Manning and Mart\'inez-Pedroza to produce a clean two-sided partial decision procedure. The paper is concise and clearly written, and it explicitly identifies which ingredients come from prior work. The main correctness risk is the use of a strengthened form of [24, Theorem 1.7] extracted from the proof rather than proved or quoted verbatim; this step is load-bearing for the halting guarantee of the negative semi-algorithm. Apart from this, the argument is a transparent deduction from published results.

major comments (3)
  1. [Section 2, boxed statement [MMP]] The halting guarantee of the non-membership semi-algorithm rests entirely on the asserted extraction of a stronger form of [24, Theorem 1.7] from the proof on p. 319 of [24], and the manuscript provides no proof of this extracted statement. If the extraction is incorrect (for instance, if the finite-index subgroups R_i cannot always be chosen so that K = <H, R_i> has peripherally finite index and does not contain g), then the non-membership semi-algorithm may run forever on precisely the instances where H is relatively quasi-convex and g is not in H, so Theorem 5 would not deliver the claimed decidability. The authors should either prove the strengthened statement as a lemma in this note, or quote the exact theorem from [24] and give a rigorous derivation of the precise consequences used in the algorithm.
  2. [Section 2, paragraph following Step (3)] The summary states that [MMP] shows that the constructed H1 is relatively quasi-convex and has peripherally finite index, but the boxed [MMP] statement only asserts that K = <H, R_i> has peripherally finite index and excludes g; it does not mention relative quasi-convexity. Since the partial algorithm of [KhMW] (cited as [22, Thm 7.5]) is applied only to subgroups that are relatively quasi-convex and have peripherally finite index, the missing relative quasi-convexity of H1 is a gap in the application. The manuscript needs an explicit argument or a precise reference for why the constructed K is relatively quasi-convex, for instance via Hruska's characterization of relatively quasi-convex subgroups in terms of finite generation and finitely generated peripheral intersections.
  3. [Section 2, Step (2)] The nondeterministic choice in Step (2) guesses a tuple (x_1,...,x_ell) but ell itself is not fixed in advance: the number of maximal infinite parabolic subgroups in the collection guaranteed by [H] is not known to the algorithm. The description should clarify that the nondeterministic algorithm also guesses ell (or, equivalently, that the deterministic simulation dovetails over all ell and all choices), so that the enumeration is exhaustive over the relevant finite-index subgroups of the peripheral conjugates.
minor comments (4)
  1. [Abstract] In the first sentence of the abstract, 'decidability o f' contains a spacing typo; it should read 'decidability of'.
  2. [Section 2, boxed statements [H] and [MMP]] The notation P^{x_i}_i is confusing because the subscript i on P_i denotes the choice of peripheral group while the superscript x_i denotes conjugation; consider writing P_i^{x_i} in the displayed statements and stating once that conjugation by an element x is denoted by P^x, to avoid reading P^{x_i}_i as a power.
  3. [Remark 4] Remark 4 states without further comment that (Hyp) is satisfied when the peripheral structure consists of finitely generated abelian groups; a one-sentence justification that (H3) and (H4) hold for such groups (for example, by Smith normal form for membership and by enumerating finite-index subgroups through torsion-free quotients) would make the remark self-contained.
  4. [Step (3)] In the description of the negative semi-algorithm, the phrase 'Run the partial algorithm [KhMW] to decide whether g is in H1' should specify that if this algorithm halts, it returns the correct membership answer for H1, but that for wrong nondeterministic guesses it may never halt; this is implicit in the nondeterministic framework but stating it explicitly would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof reduces the generalized membership problem in G to independent external theorems on relatively hyperbolic groups and to the authors' prior published work, without restating the target result as an input.

full rationale

The derivation in Theorem 5 is not circular. The semi-algorithm for certifying g in H is the classical relator-gluing enumeration on Stallings graphs: it halts exactly when g is in H and does not presuppose the theorem. The non-membership semi-algorithm reduces the given instance to guessing finite-index subgroups R_i of peripheral subgroups; the existence of such R_i with g not in K and K peripherally finite index is imported from Manning and Martinez-Pedroza [24, Theorem 1.7], with the paper explicitly noting that the statement is extracted from the proof at [24, p. 319], and the finite list of maximal parabolic subgroups comes from Hruska [16, Theorem 9.1]. These are external results, not the theorem being proved. The authors' own prior work [22] is used for the partial Stallings-graph algorithm and for the implication that relatively quasi-convex plus peripherally finite index implies L-quasi-convex; this self-citation is load-bearing, but it is published, independently vetted mathematics and it does not depend on the present theorem, so it does not create circularity. Hypothesis (H4), solvability of the generalized membership problem in each peripheral subgroup, is an input assumption about proper subgroups of G, not a disguised version of the conclusion about G. The only legitimate concern is the strengthened [MMP] statement: the paper acknowledges that [24, Theorem 1.7] is more concise and that the stronger form is extracted from the proof. If that extraction were incorrect, the non-membership semi-algorithm might fail to halt. That is a correctness and verification risk about a cited proof, not a circular dependence, because the paper does not define the existence of the R_i in terms of the target decidability claim. No specific reduction of a claimed prediction to an input by construction can be exhibited, so the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The proof is a synthesis of published theorems in geometric group theory. The axioms listed are the external results (unproved in this note) that the central claim rests on. No free parameters are fitted and no new entities are introduced.

assumptions (8)
  • domain assumption Equivalence of definitions of relative hyperbolicity (Gromov, Farb, Bowditch, Drutu-Sapir, Osin).
    Section 2, first paragraph: 'There are several definitions... These definitions turn out to be equivalent (see Bumagin, Dahmani, Hruska)'. The proof uses standard properties of relatively hyperbolic groups under any equivalent definition.
  • domain assumption [H] Hruska Theorem 9.1: a relatively quasi-convex subgroup H has finitely many maximal infinite parabolic subgroups up to H-conjugacy.
    Boxed [H] in Section 2. Used so the non-membership semi-algorithm only needs to guess a finite tuple of parabolic subgroups.
  • domain assumption [MMP] Stronger version of Manning-Martinez-Pedroza Theorem 1.7 extracted from its proof (p. 319): for RQC H and g not in H, there exist finite-index R_i <= P_i^{x_i} with K=<H,R_i> peripherally finite index and g not in K.
    Boxed [MMP] in Section 2. Load-bearing for the g-not-in-H semi-algorithm; the authors explicitly note it is extracted from the proof.
  • domain assumption [AC] Antolin-Ciobanu Corollary 1.9, Lemma 5.3, Theorem 7.5: construct a geodesic automatic structure for G on X containing the peripheral structures.
    Boxed [AC] in Section 2. Provides the automatic structure required to run the KhMW partial algorithm.
  • domain assumption [KhMW] Kharlampovich-Miasnikov-Weil Theorem 7.5: a relatively quasi-convex subgroup with peripherally finite index is L-quasi-convex.
    Boxed [KhMW] in Section 2. Converts the enlarged subgroup H1 into one for which the membership partial algorithm halts. This is the authors' own prior work.
  • domain assumption Osin's Theorems 4.13 and 4.16: peripherally finite and peripherally finite index relatively quasi-convex subgroups are finitely generated.
    Section 2, paragraph on peripheral finiteness: 'Such subgroups are always finitely generated (Osin... Kharlampovich et al...)'. Needed so H1 has a finite generating set for the algorithm.
  • domain assumption Classical partial algorithm for the word problem in a finitely presented group: systematic exploration of R-rewritings.
    Section 2, first bullet of the g-in-H semi-algorithm description. Standard.
  • standard math Sipser Theorem 3.16: a non-deterministic partial algorithm can be converted to a deterministic one by systematic enumeration.
    End of Section 2: 'Such a non-deterministic algorithm can be turned into a deterministic one by standard methods (see, e.g., [35, Thm 3.16]).'

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the generalized membership problem in relatively hyperbolic groups." pith.science (2026). https://pith.science/paper/F4OEWMMP

@misc{pith2026190803525,
  author       = {Pith},
  title        = {Pith review of: On the generalized membership problem in relatively hyperbolic groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F4OEWMMP}},
  note         = {Machine review of arXiv:1908.03525}
}
read the original abstract

The aim of this short note is to provide a proof of the decidability of the generalized membership problem for relatively quasi-convex subgroups of finitely presented relatively hyperbolic groups, under some reasonably mild conditions on the peripheral structure of these groups. These hypotheses are satisfied, in particular, by toral relatively hyperbolic groups.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Algorithms detecting stability and Morseness for finitely generated groups

    math.GR 2019-08 conditional novelty 6.0 of 10

    A set of algorithms detects stability and Morseness of finitely generated subgroups in mapping class groups, right-angled Artin groups, toral relatively hyperbolic groups, and limit groups.

Reference graph

Works this paper leans on

38 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [22]

    Kharlampovich, A

    O. Kharlampovich, A. Miasnikov, and P. Weil. Stallings graphs for q uasi- convex subgroups. J. Algebra, 488:442–483, 2017

    work page 2017

  2. [24]

    J. F. Manning and E. Mart ´ ınez-Pedroza. Separation of relatively quasicon- vex subgroups. Pacific J. Math. , 244(2):309–334, 2010

    work page 2010

  3. [1]

    Antol ´ ın and L

    Y. Antol ´ ın and L. Ciobanu. Finite generating sets of relatively hy perbolic groups and applications to geodesic languages. Trans. Amer. Math. Soc. , 368(11):7965–8010, 2016

    work page 2016

  4. [2]

    G. N. Arzhantseva. Generic properties of finitely presented gr oups and Howson’s theorem. Comm. Algebra, 26(11):3783–3792, 1998

    work page 1998

  5. [3]

    G. N. Arzhantseva. A property of subgroups of infinite index in a free group. Proc. Amer. Math. Soc. , 128(11):3205–3210, 2000

    work page 2000

  6. [4]

    G. N. Arzhantseva and A. Y. Ol’shanski ˘ ı. Generality of the class of groups in which subgroups with a lesser number of generators are free. Mat. Za- metki, 59(4):489–496, 638, 1996. 7

    work page 1996

  7. [5]

    Birget, S

    J.-C. Birget, S. Margolis, J. Meakin, and P. Weil. PSPACE-complete prob- lems for subgroups of free groups and inverse finite automata. Theoret. Comput. Sci. , 242(1-2):247–281, 2000

    work page 2000

  8. [6]

    B. H. Bowditch. Relatively hyperbolic groups. Internat. J. Algebra Com- put., 22(3):1250016, 66, 2012

    work page 2012

Show all 38 references
  1. [7]

    I. Bumagin. On definitions of relatively hyperbolic groups. In Geometric methods in group theory , volume 372 of Contemp. Math. , pages 189–196. Amer. Math. Soc., Providence, RI, 2005

    2005

  2. [8]

    J.-Y. Cai, W. H. Fuchs, D. Kozen, and Z. Liu. Efficient average-ca se algo- rithms for the modular group. In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) , pages 143–152. IEEE Comput. Soc. Press, Los Alamitos, CA, 1994

    1994

  3. [9]

    F. Dahmani. Les groupes relativement hyperboliques et leurs bords . Pr´ epublication de l’Institut de Recherche Math´ ematique Avanc´ ee, 2003/13. Universit´ e Louis Pasteur, Strasbourg, 2003

    2003

  4. [10]

    Delgado and E

    J. Delgado and E. Ventura. Algorithmic problems for free-abelia n times free groups. J. Algebra, 391:256–283, 2013

    2013

  5. [11]

    Drut ¸u and M

    C. Drut ¸u and M. Sapir. Tree-graded spaces and asymptotic cones of groups. Topology, 44(5):959–1058, 2005. With an appendix by D. Osin and M.Sapir

    2005

  6. [12]

    B. Farb. Relatively hyperbolic groups. Geom. Funct. Anal. , 8(5):810–840, 1998

    1998

  7. [13]

    S. M. Gersten and H. B. Short. Rational subgroups of biautom atic groups. Ann. of Math. (2) , 134(1):125–158, 1991

    1991

  8. [14]

    M. Gromov. Hyperbolic groups. In Essays in group theory , volume 8 of Math. Sci. Res. Inst. Publ. , pages 75–263. Springer, New York, 1987

    1987

  9. [15]

    Gurevich and P

    Y. Gurevich and P. Schupp. Membership problem for the modular group. SIAM J. Comput. , 37(2):425–459, 2007

    2007

  10. [16]

    G. C. Hruska. Relative hyperbolicity and relative quasiconvexity for count- able groups. Algebr. Geom. Topol. , 10(3):1807–1856, 2010

    2010

  11. [17]

    G. C. Hruska and D. T. Wise. Packing subgroups in relatively hype rbolic groups. Geom. Topol., 13(4):1945–1988, 2009

    1945

  12. [18]

    Kapovich

    I. Kapovich. Detecting quasiconvexity: algorithmic aspects. I n Geometric and computational perspectives on infinite groups (Minneap olis, MN and New Brunswick, NJ, 1994) , volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. , pages 91–99. Amer. Math. Soc., Providence...

    1994

  13. [19]

    Kapovich and A

    I. Kapovich and A. Myasnikov. Stallings foldings and subgroups o f free groups. J. Algebra, 248(2):608–668, 2002

    2002

  14. [20]

    Kapovich and P

    I. Kapovich and P. Schupp. Genericity, the Arzhantseva-Ol’shanskii method and the isomorphism problem for one-relator groups. Math. Ann., 331(1):1– 19, 2005. 8

    2005

  15. [21]

    Kapovich, R

    I. Kapovich, R. Weidmann, and A. Myasnikov. Foldings, graphs o f groups and the membership problem. International Journal of Algebra and Com- putation, 15(1):95–128, 2005

    2005

  16. [23]

    H. Kim. Algorithms detecting stability and Morseness for finitely g enerated groups. arXiv:1908.04460, 2019

    1908 arXiv

  17. [25]

    Markus-Epstein

    L. Markus-Epstein. Stallings foldings and subgroups of amalgam s of finite groups. Internat. J. Algebra Comput. , 17(8):1493–1535, 2007

    2007

  18. [26]

    J. P. McCammond and D. T. Wise. Coherence, local quasiconvex ity, and the perimeter of 2-complexes. Geom. Funct. Anal. , 15(4):859–927, 2005

    2005

  19. [27]

    Miasnikov, E

    A. Miasnikov, E. Ventura, and P. Weil. Algebraic extensions in fre e groups. In Geometric group theory , Trends Math., pages 225–253. Birkh¨ auser, Basel, 2007

    2007

  20. [28]

    K. A. Mihailova. The occurrence problem for direct products of groups. Math. USSR Sbornik , 70:241–251, 1966. English translation

    1966

  21. [29]

    D. V. Osin. Relatively hyperbolic groups: intrinsic geometry, alge - braic properties, and algorithmic problems. Mem. Amer. Math. Soc. , 179(843):vi+100, 2006

    2006

  22. [30]

    E. Rips. Subgroups of small cancellation groups. Bull. London Math. Soc. , 14(1):45–47, 1982

    1982

  23. [31]

    A. Roig, E. Ventura, and P. Weil. On the complexity of the Whitehe ad min- imization problem. Internat. J. Algebra Comput. , 17(8):1611–1634, 2007

    2007

  24. [32]

    P. E. Schupp. Coxeter groups, 2-completion, perimeter redu ction and sub- group separability. Geom. Dedicata, 96:179–198, 2003

    2003

  25. [33]

    H. Short. Quasiconvexity and a theorem of Howson’s. In Group theory from a geometrical viewpoint (Trieste, 1990) , pages 168–176. World Sci. Publ., River Edge, NJ, 1991

    1990

  26. [34]

    P. V. Silva, X. Soler-Escriv` a, and E. Ventura. Finite automata for Schreier graphs of virtually free groups. J. Group Theory , 19(1):25–54, 2016

    2016

  27. [35]

    M. Sipser. Introduction to the theory of computation, second edition . Thom- son Course Technology, 2006

    2006

  28. [36]

    J. R. Stallings. Topology of finite graphs. Invent. Math. , 71(3):551–565, 1983

    1983

  29. [37]

    N. W. M. Touikan. A fast algorithm for Stallings’ folding process. Internat. J. Algebra Comput. , 16(6):1031–1045, 2006

    2006

  30. [38]

    H. Tran. On strongly quasiconvex subgroups. Geom. Topol., 23(3):1173– 1235, 2019. 9

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.