{"id":"4e0b340c-f490-4a0a-a6f0-909f33da201b","arxiv_id":"1908.03525","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For finitely presented relatively hyperbolic groups with well-behaved peripheral subgroups, the generalized membership problem is decidable for relatively quasi-convex subgroups.","lead":"This paper proves that a generalized membership question, deciding whether a group element lies in a described subgroup, is decidable in relatively hyperbolic groups whose peripheral subgroups satisfy four conditions. It combines known results into a partial algorithm that halts on the important cases and answers correctly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The non-membership semi-algorithm depends on a stronger [MMP] statement extracted from a proof in [24, p.319] that is neither proved nor matched to the published theorem; if the extraction is wrong, the algorithm need not halt for relatively quasi-convex H with g notin H.","rationale":"The reader's weakest assumption identifies exactly the dependency I would isolate: the non-membership semi-algorithm is logically valid only if the extracted [MMP] statement is true in full. The rest of the proof is a plausible assembly of known results: the membership semi-algorithm is a standard Stallings-graph/rewriting search; [AC] and [KhMW] are cited with specific references; and the non-deterministic enumeration in Step (2) is a standard dove-tailing argument. The hypotheses (H1)-(H4) are explicit and, for toral relatively hyperbolic groups, are satisfied. No internal inconsistency or obvious gap appears elsewhere. The one place where the proof is not self-contained is the assertion that Manning-Martinez-Pedroza's proof yields the stronger conclusion stated in [MMP], in particular the containment K_i ≤ R_i, the peripherally finite index of K, and the non-membership g notin K. Because the halting guarantee of the non-membership side depends on each of these clauses, the extracted statement is load-bearing. The appropriate response is not rejection but conditional acceptance pending verification or a self-contained proof of the extracted statement. Since the reader already recommended CONDITIONAL and I find no additional concern that changes that verdict, UNCHANGED is the correct adjustment.","tokens_in":119,"tokens_out":4554,"duration_ms":234334,"concrete_test":"Independently re-derive the extracted [MMP] statement from [24, Theorem 1.7] and its proof at [24, p.319], checking in particular that the construction yields: (1) finite-index subgroups R_i of P_i^{x_i} containing K_i; (2) K = <H,R_1,...,R_ell> has peripherally finite index; and (3) g notin K. If any of these three clauses is not present in the proof, or requires an additional hypothesis not listed in [MMP] (such as a stronger separation condition), then Theorem 5's non-membership semi-algorithm lacks a proven halting guarantee, and the paper should supply the missing argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The halting guarantee of the non-membership semi-algorithm rests on [MMP]: for relatively quasi-convex H and g notin H, there must exist finite-index subgroups R_i of the corresponding P_i^{x_i}, with K_i ≤ R_i, such that K = <H,R_i> has peripherally finite index and g notin K. The paper explicitly acknowledges that [24, Theorem 1.7] is 'a little more concise' than this and that the statement is extracted from the proof at [24, p.319]. This extracted statement is doing two essential jobs. First, peripherally finite index is what lets the authors invoke [KhMW] to conclude that H1 is L-quasi-convex and hence that the Stallings-graph partial algorithm halts. Second, g notin K is what makes the output of Step 3 a genuine certificate that g notin H. If the proof of Theorem 1.7 only yields finite-index subgroups of some other subgroup, or yields a K that contains g, or does not guarantee that every infinite K ∩ P^y has finite index in P^y, then the non-membership semi-algorithm can run forever on the very instances the theorem claims it decides. The argument in the note provides no independent derivation of this stronger form and simply asserts that it follows from the published proof. Since the main theorem is a decidability claim, an unverified black-box strengthening of a cited theorem is a genuine correctness risk rather than a question of expository preference.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8254,"tokens_out":9361,"duration_ms":91585,"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":[{"comment":"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.","section":"Section 2, boxed statement [MMP]"},{"comment":"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.","section":"Section 2, paragraph following Step (3)"},{"comment":"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.","section":"Section 2, Step (2)"}],"minor_comments":[{"comment":"In the first sentence of the abstract, 'decidability o f' contains a spacing typo; it should read 'decidability of'.","section":"Abstract"},{"comment":"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.","section":"Section 2, boxed statements [H] and [MMP]"},{"comment":"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.","section":"Remark 4"},{"comment":"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.","section":"Step (3)"}],"recommendation":"major_revision","confidential_remarks":"The core concern is the unproved strengthening of [24, Theorem 1.7] stated in the boxed [MMP]. This is exactly the kind of load-bearing extraction that a referee cannot verify without the full text of [24] at hand, and the manuscript itself flags that the published theorem is 'a little more concise'. The fix is local — either include a proof of the strengthened statement or replace it with a careful derivation from the published theorem — so the result is plausibly correct and suitable for publication after revision. I would also ask the editor to ensure that the reference to [22] is precisely to the published paper and that the hypotheses of Theorem 5 are stated in a way that a reader can verify without reading [22] in full."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know this short note proves a natural decidability theorem by assembling already-published machinery. Theorem 5 says that under hypotheses (Hyp), a partial algorithm decides the generalized membership problem for relatively quasi-convex subgroups of a finitely presented relatively hyperbolic group; the toral case follows. That is a genuinely useful statement to have in one place.\n\nWhat is new is the packaging, not the core technique. The proof combines the authors' own Stallings graph work [22] with Antolín–Ciobanu's automatic structures and a separation result of Manning–Martínez-Pedroza. The paper is clearly written and the hypotheses are clean. The authors also acknowledge exactly where they are using a slightly stronger version of a cited theorem, which is good practice.\n\nThe soft spot is that stronger version itself. The non-membership semi-algorithm halts only if the extracted [MMP] statement is true: for relatively quasi-convex H and g not in H, there exist finite-index subgroups of the appropriate peripheral subgroups so that the group K generated by H and those subgroups has peripherally finite index and excludes g. The published Theorem 1.7 is more concise, and the authors say their version is extracted from the proof on page 319, without reproducing the extraction. This is not a cosmetic issue; if the extraction is wrong, the algorithm can fail to halt on valid inputs. I do not think the paper should be rejected, because the published theorem is real and the stronger form is likely true, but the proof as written has a genuine gap. A referee should ask the authors to supply a self-contained proof of the extracted statement, or at least give a detailed derivation.\n\nThe citation of their own [22] is appropriate and not a concern. The impracticality of the algorithm is acknowledged and not a defect. The novelty is modest, but that is acceptable for a note whose service is synthesis.\n\nThis paper is for researchers in algorithmic group theory. It deserves a serious referee, not a desk reject, but the referee should push on [MMP]. I would send it back conditional on the gap being filled.\n\nBest.","headline":"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.","tokens_in":8742,"tokens_out":3381,"would_cite":true,"duration_ms":34464,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20F10","20F65","20F67"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["generalized membership problem","relatively hyperbolic groups","relatively quasi-convex subgroups","partial algorithm","Stallings graphs","automatic structures","toral relatively hyperbolic groups","peripheral subgroups"],"falsifier":"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.","tokens_in":7738,"feed_emoji":"🧩","tokens_out":8819,"duration_ms":87945,"temperature":0.7,"pith_summary":"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.","feed_headline":"Membership decidable for relatively quasi-convex subgroups","feed_subtitle":"One algorithm settles membership for relatively quasi-convex subgroups, including toral relatively hyperbolic groups.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the structure theory of relatively quasi-convex subgroups, including the finite family of maximal infinite parabolic subgroups and the equivalence of the various definitions used.","marker":"[16]"},{"why":"Provides the separation theorem from which the paper extracts the stronger statement—the load-bearing step—that a finite-index enlargement of peripheral subgroups can keep an outside element outside while making the enlarged subgroup peripherally finite.","marker":"[24]"},{"why":"Constructs the geodesic automatic structure for relatively hyperbolic groups from automatic structures on peripheral subgroups, giving the language of representatives used in the non-membership search.","marker":"[1]"},{"why":"Supplies the partial algorithm that computes a Stallings graph and solves membership for relatively quasi-convex subgroups with peripherally finite index, used as the inner test in the non-membership semi-algorithm.","marker":"[22]"},{"why":"Establishes the basic properties of relatively hyperbolic groups, including finite generation results for peripherally finite subgroups, used to justify the hypotheses.","marker":"[29]"},{"why":"Introduces the labeled graph construction for finitely generated subgroups of free groups that underlies the membership enumeration.","marker":"[36]"}],"fun_headline_variants":["Algorithm decides membership in relatively hyperbolic groups","Decidability of membership for quasi-convex subgroups","Membership problem solved for toral relatively hyperbolic groups","Generalized membership decidable in relatively hyperbolic groups","New algorithm for membership in relatively hyperbolic groups"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Algorithm decides membership in relatively hyperbolic groups","Decidability of membership for quasi-convex subgroups","Membership problem solved for toral relatively hyperbolic groups","Generalized membership decidable in relatively hyperbolic groups","New algorithm for membership in relatively hyperbolic groups"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2558,"prompt_tokens":781,"completion_tokens":1777,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":397,"completion_tokens_details":{"reasoning_tokens":1707}},"tokens_in":397,"tokens_out":1777,"duration_ms":11140,"temperature":1.0,"reasoning_tokens":1707,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:10:54.595238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the structure theory of relatively quasi-convex subgroups, including the finite family of maximal infinite parabolic subgroups and the equivalence of the various definitions used."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the separation theorem from which the paper extracts the stronger statement—the load-bearing step—that a finite-index enlargement of peripheral subgroups can keep an outside element outside while making the enlarged subgroup peripherally finite."},{"cited_title":"Antol ´ ın and L","cited_arxiv_id":null,"evidence_quote":"Constructs the geodesic automatic structure for relatively hyperbolic groups from automatic structures on peripheral subgroups, giving the language of representatives used in the non-membership search."},{"cited_title":"Kharlampovich, A","cited_arxiv_id":null,"evidence_quote":"Supplies the partial algorithm that computes a Stallings graph and solves membership for relatively quasi-convex subgroups with peripherally finite index, used as the inner test in the non-membership semi-algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the basic properties of relatively hyperbolic groups, including finite generation results for peripherally finite subgroups, used to justify the hypotheses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the labeled graph construction for finitely generated subgroups of free groups that underlies the membership enumeration."}],"review_version":1}