{"id":"ffed8b54-b115-44aa-a3d6-e79c56195477","arxiv_id":"2507.13203","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A single family of finite extensions of lamplighter groups separates uniform from non-uniform subgroup membership, pairs rational growth with an undecidable word problem, and pairs a context-free conjugacy geodesic language with an undecidable conjugacy problem.","lead":"This paper builds finitely generated groups that are tiny twists on lamplighter groups, and shows they solve three open problems in group theory. The results produce new and unexpected combinations of decidable and undecidable algorithmic problems for groups.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The third main theorem depends on Proposition A.1's sufficiency direction and on the exactness of the Theorem A.4 grammar; both are only sketched or referred to Mercier, so a single counterexample there would invalidate the context-free ConjGeo claim.","rationale":"The reader's verdict is CONDITIONAL, and the weakest assumption identified there is the same one I regard as load-bearing: the sufficiency direction of Proposition A.1 and the completeness/unambiguity of the Theorem A.4 grammar. My independent reading of the appendix confirms that the proof is only a sketch. The grammar rules are not actual context-free productions because of the unbounded 'distinct Xi' condition, and no construction is given that turns them into a finite unambiguous CFG. The unique-leftmost-derivation claim is stated without proof. The chain from Proposition A.1 to Theorem A.4 to Lemma 4.5 to Theorem 4.1 is therefore the least secure part of the paper. The first two main results, by contrast, have substantially more complete proofs: Theorem 1 rests on Romanovskii's theorem and a clear two-case argument, and Theorem 2 uses the explicit isometric preimage of the standard lamplighter generating set. I also noticed a notation issue in Section 3.2: the paper defines growth series with cumulative coefficients beta(n), but Proposition 3.2's formula 1+x^2+2(Gamma_L-1) is a statement about exact-length generating functions. This is fixable (the cumulative series is Gamma/(1-x), so rationality is preserved) and therefore not my central objection. The deciding issue remains the appendix: without a complete proof or an explicit machine-checked grammar, the third bullet of Theorem 4.1 should be regarded as conditional. Since this is exactly the reader's stated concern, I recommend keeping the CONDITIONAL verdict.","tokens_in":15648,"tokens_out":28124,"duration_ms":346474,"concrete_test":"Independently compute ground-truth ConjGeo for all elements of C2 wr F2 with word length at most 7: enumerate the finite ball, compute each element's minimal length in its conjugacy class by BFS, and record the set of geodesic words representing elements that are length-minimal in their class. Then implement Proposition A.1's conditions (1)-(4) and check, for every element in that ball, that the conditions are equivalent to being in ground-truth ConjGeo; any element satisfying (1)-(4) that is not length-minimal would refute the sufficiency direction. Separately, implement the grammar of Theorem A.4 by expanding the 'distinct Xi' schemata into explicit finite productions, parse the same ball, and check that the generated language agrees exactly with ground-truth ConjGeo and that each word has exactly one leftmost derivation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim most at risk is the third bullet of Theorem 4.1: ConjGeo(G(F2,I),S) is unambiguously context-free while the Word Problem is decidable and the Conjugacy Problem is undecidable. That bullet rests on Lemma 4.5 and on Theorem A.4, which asserts that ConjGeo(C2 wr Fr,T) is unambiguously context-free. Theorem A.4 is not actually proved as a context-free grammar. Its productions, such as Es <- s X1...Xl s^{-1} with 'the Xi are distinct elements', are rule schemata with unbounded l and a distinctness constraint; as written these are not production rules of a context-free grammar, and no finite unambiguous CFG construction is supplied. Even if that schema can be expanded into a genuine finite CFG, the claim that every conjugacy geodesic has a unique leftmost derivation is asserted without proof. More fundamentally, the characterization of conjugacy geodesics in Proposition A.1 is used in its sufficiency direction: conditions (1)-(4) are said to imply length-minimality only because 'all the reductions made in [27, section 3] ... actually preserve the length'. That direction is precisely what lets the grammar generate only genuine conjugacy geodesics. If it is false, or if the grammar overgenerates or undergenerates relative to it, then ConjGeo may fail to be context-free or unambiguous, and the third main result does not follow. This is an internal proof gap, not a disagreement with consensus: the author's own text marks the grammar argument as an observation and delegates the key converse to an unpublished preprint.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies central extensions G(H,I) of lamplighter groups C2≀H, where the extension datum is a symmetric subset I⊂H. The main results are: (1) for a suitable recursive I⊂Z, the group GI has decidable Subgroup Membership but undecidable Uniform Subgroup Membership; (2) for a suitable recursive I⊂Z, GI can have undecidable Word Problem while its growth series with respect to a natural generating set is rational; and (3) for a suitable recursive I⊂F2, the group G(F2,I) has decidable Word Problem, undecidable Conjugacy Problem, and unambiguously context-free language of conjugacy geodesics. The paper also discusses residual finiteness, the co-Word Problem, and the Isomorphism Problem inside this class. Theorems 1 and 2 are supported by concrete Turing reductions and explicit computations, but the third theorem relies heavily on an appendix that characterizes conjugacy geodesics in C2≀Fr and asserts that ConjGeo(C2≀Fr,T) is unambiguously context-free.","tokens_in":15873,"tokens_out":23052,"duration_ms":277781,"significance":"If the main claims hold, the paper answers open questions of Duchin and Shapiro (growth series vs. undecidable Word Problem) and of Ciobanu, Hermiller, Holt and Rees (low-complexity ConjGeo with undecidable Conjugacy Problem), and it introduces a flexible family of central extensions of lamplighter groups as a toolkit for constructing groups with prescribed algorithmic properties. Theorems 1 and 2 are, in my reading, established: the reductions via Romanovskii's theorem, Lemma 2.3, and the isometry argument in Proposition 3.2 are convincing and largely self-contained. The paper is well written and carefully credits prior work, including Genevois's construction and Mercier's preprint. The main weakness is that the third theorem's ConjGeo claim is not proved at the required level of detail in Appendix A, and Lemma 4.5 as stated contains a language-theoretic error that needs correction. These are substantial but local issues, and in my view they are fixable within the manuscript's framework.","major_comments":[{"comment":"The displayed equality ConjGeo(G,S) = τ^{-1}(ConjGeo(Q,T)) ∪ (F\\{1}) is not correct as written. If τ is the erasing homomorphism S*→T* that sends every element of F to the empty word, then in the example G=G(Z,∅), Q=C2≀Z, T={a,t±}, S={a,az,t±,t±z,z}, the word w=za satisfies τ(w)=a∈ConjGeo(C2≀Z,T), so w belongs to the right-hand side. But the element \\bar w=za is the generator az, which has S-length 1, while w has length 2, so w is not a conjugacy geodesic. The proof also states the equivalence 'w is a conjugacy geodesic iff ... τ(w) is a conjugacy geodesic' without the necessary length condition ℓ(w)=ℓ(τ(w)). The correct statement is that a word using no letters from F is a conjugacy geodesic exactly when its image under the non-erasing restriction S\\F→T lies in ConjGeo(Q,T), together with the empty word and the length-one words for the non-identity elements of F; equivalently, one must add the condition ℓ(w)=ℓ(τ(w)). Since this lemma is the bridge from the quotient language to ConjGeo(G,S) in Theorem 4.1, the proof needs to be corrected accordingly.","section":"§4.2, Lemma 4.5"},{"comment":"The sufficiency direction of Proposition A.1 is load-bearing for Theorem A.4 and is not proved. The sentence 'all the reductions made in [27,§3] to go from g satisfying (1-4) to a conjugacy geodesic actually preserve the length' is an appeal to an unpublished preprint and does not by itself establish that every element satisfying conditions (1)–(4) is length-minimal in its conjugacy class. Since the grammar in Theorem A.4 is supposed to generate exactly the language of conjugacy geodesics, this direction is essential. Please supply a complete proof, or state and prove the relevant result from Mercier's preprint in sufficient detail that the length-preservation claim can be checked.","section":"§A.1, Proposition A.1"},{"comment":"Theorem A.4 is the central technical support for the third bullet of Theorem 4.1, but its proof is only the assertion 'We claim ...'. First, the rule schemata such as Es ← s X1...Xℓ s^{-1} with 'the Xi are distinct elements' should be expanded into a genuine finite context-free grammar; this is in fact possible because the available variable set {a}∪{Ev | v∈B±} is finite, so the constraints on distinctness and on ℓ merely enumerate finitely many productions, but the text should say so explicitly. More importantly, there is no argument that the language generated by all the rules is exactly ConjGeo(C2≀Fr,T), and no argument for the claimed uniqueness of leftmost derivations. Given that the correctness of the grammar also depends on the unproved sufficiency direction of Proposition A.1, this is a substantial gap that must be closed before the third main theorem can be considered established.","section":"§A.4, Theorem A.4"}],"minor_comments":[{"comment":"In the definition of conjugacy, 'there exists c∈G such that g = cgc^{-1}' should read 'g = chc^{-1}'.","section":"§0.3"},{"comment":"The phrase 'halts after m steps' should be 'halts after exactly m steps', and m=0 should be excluded (or the definition arranged so that 0∉I), to avoid ambiguity about what 'after 0 steps' means.","section":"§2, Lemma 2.3"},{"comment":"The converse direction of Proposition 3.4 (if I is recursive then the growth series is computable) is only implicit; since I recursive gives decidable Word Problem by Theorem 1.4, one can enumerate all words up to length n and remove duplicates, but this should be stated explicitly.","section":"§3, Proposition 3.4"},{"comment":"The 'if' direction of Theorem 1.4 is described in words ('now we just have to move the factors around') and would benefit from a more formal normal-form argument; as written this is a decidability proof and the commutator bookkeeping is not fully spelled out.","section":"§1, Theorem 1.4"},{"comment":"In the final paragraph of Theorem A.4, the claim refers to 'ConjGeo(C2 ≀ F2, T)' while the theorem statement is for C2≀Fr; this should be fixed to Fr.","section":"§A, Theorem A.4"},{"comment":"The paper relies essentially on Mercier's arXiv preprint [27]; since it is not peer-reviewed, the reliance should be stated explicitly, and if the preprint has since been published or revised, that information should be included.","section":"§A, reference [27]"}],"recommendation":"major_revision","confidential_remarks":"The first two main theorems appear sound and are valuable. The third theorem is plausible but the appendix is not sufficient as written: both Proposition A.1's sufficiency direction and Theorem A.4's grammar correctness/unambiguity need full proofs, and Lemma 4.5 contains a language-theoretic overgeneration error that must be corrected. These issues are local and fixable, so I recommend major revision rather than rejection. The editor may also wish to verify the availability and reliability of Mercier's preprint [27], since the paper's main new claim depends on it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Bodart's paper. It is a genuinely strong contribution: the same family of central extensions of lamplighter groups resolves three open questions, and each resolution is transparent. The subgroup membership dichotomy—whether z lies in the finitely generated subgroup—combined with the undecidable divisibility set I is a neat way to separate uniform from non-uniform membership. The growth series result using Genevois's isometry is clean and the formula checks out. The conjugacy problem reduction via Lemma 4.2 is also convincing, and the extra results on residual finiteness and co-word problem are welcome. The paper credits Genevois properly and has no circularity problems.\n\nThe soft spot is the appendix, and it is load-bearing for the third bullet of Theorem 4.1. Proposition A.1's sufficiency direction is not proved; it is delegated to Mercier's preprint with a one-line assertion that the reductions in [27, §3] preserve length. That is not enough for a result this central. The grammar in Theorem A.4 is also presented as a schema with 'distinct Xi' and no proof of unambiguity. The stress-test worry about 'unbounded l' is less serious than it sounds: because the Xi are drawn from a finite set of variables, distinctness bounds the length, so the schema can be expanded to an ordinary finite context-free grammar. But the author should say that explicitly. The bigger issue is that the unique-leftmost-derivation claim is asserted without proof. If the sufficiency direction fails, the grammar could overgenerate, so this needs a real proof or a precise reference that actually contains one.\n\nAs it stands, Theorems 1 and 2 deserve acceptance; Theorem 4.1 is very plausible but incomplete. This is exactly the kind of paper that should get serious refereeing, not a desk rejection. Send it to a referee with instructions that the appendix must be completed: either a full proof of A.4 and of the sufficiency direction of A.1, or a precise quotation from Mercier with proof. I would be willing to see the revised version.","headline":"Strong paper, three open questions answered; Theorems 1 and 2 are solid, but Theorem 4.1's appendix needs real proof before the third bullet is fully established.","tokens_in":703,"tokens_out":960,"would_cite":true,"duration_ms":90430,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20F10","20F65","20E22"],"pacs":[],"model":"deepseek-v4-flash","headline":"One family of lamplighter extensions yields three never-before-seen combinations of algorithmic properties.","keywords":["lamplighter groups","central extensions","subgroup membership problem","uniform subgroup membership","word problem","conjugacy problem","growth series","conjugacy geodesics"],"falsifier":"Enumerate all elements of $C_2\\wr F_2$ of length at most 8 for a fixed free basis, compute the true minimal length in each conjugacy class, and check whether every word accepted by the grammar of Theorem A.4 (equivalently, every element satisfying conditions (1)--(4) of Proposition A.1) is one of those minimal representatives; a single accepted word that is not minimal would refute the context-free claim of Theorem 4.1.","tokens_in":15334,"feed_emoji":"🔦","tokens_out":13736,"duration_ms":135089,"temperature":0.7,"pith_summary":"This paper studies a family of groups obtained from lamplighter groups $C_2 \\wr H$ by adding one central element $z$ of order 2 and declaring that $[a,a^h]=z$ exactly when $h$ lies in a chosen subset $I \\subset H$. The central claim is that this single family, by varying $H$ and $I$, realizes three combinations of algorithmic properties that were previously unknown: decidable membership in any fixed finitely generated subgroup with no uniform algorithm for membership across all such subgroups; rational volume growth series together with an undecidable word problem; and a decidable word problem with an undecidable conjugacy problem while the language of conjugacy geodesics (minimal-length representatives of conjugacy classes) is unambiguously context-free. If correct, these examples settle two open questions in the literature about how far such properties can be separated. The paper also characterizes residual finiteness and isomorphism within the family, and argues that the construction should be a standard tool for building groups with prescribed algorithmic behavior.","feed_headline":"One lamplighter construction splits three group decision problems","feed_subtitle":"The same family of central extensions separates subgroup membership, word, growth, and conjugacy problems in new ways.","key_machinery":"The central object is the commutator-twisted lamplighter extension $G(H,I)$. Its nilpotent kernel is an explicit 2-step nilpotent group $N(H,I)\\cong(\\bigoplus_H \\mathbb{F}_2)\\times \\mathbb{F}_2$ with product $(u,m)(v,n)=(u+v,\\,m+n+\\omega_I(u,v))$, where $\\omega_I(u,v)=\\sum_{g<h}\\chi_I(g^{-1}h)u_g v_h \\pmod 2$. This normal form turns each algorithmic question into a parity or membership question controlled by $I$: membership of $z$ in a subgroup becomes a divisibility condition, conjugacy of $x$ with $xz$ becomes a parity condition on $g^{-1}\\mathrm{supp}(x)\\cap I$, and the growth series is computed by the observation that, for the generating set $S=\\{a,az,t^\\pm,t^\\pm z\\}$, the projection to $C_2\\wr\\mathbb{Z}$ preserves word length outside $\\{1,z\\}$. The same split, an explicit nilpotent kernel sitting over a lamplighter quotient, lets the paper pull undecidability from $I$ into the group while inheriting the context-free geodesic language of $C_2\\wr F_2$.","core_discovery":"Starting from a group $H$ and a symmetric subset $I\\subset H$ with $1\\notin I$, the paper defines $G(H,I)=\\langle a,H,z \\mid a^2=z^2=[a,z]=[h,z]=1,\\ [a,a^h]=z \\text{ if } h\\in I,\\ 1 \\text{ otherwise}\\rangle$, a central extension $1\\to \\langle z\\rangle \\to G(H,I) \\to C_2\\wr H \\to 1$. The discovery is that this small twist of the lamplighter presentation is flexible enough to separate algorithmic problems that had resisted separation. Specifically, the paper constructs a recursive $I\\subset \\mathbb{Z}$ for which $G_I$ has decidable Subgroup Membership but undecidable Uniform Subgroup Membership; a non-recursive $I$ for which $G_I$ has undecidable word problem yet rational volume growth series with respect to a natural generating set; and a recursive $I\\subset F_2$ for which $G(F_2,I)$ has decidable word problem, undecidable conjugacy problem, and an unambiguously context-free conjugacy-geodesic language. The subset $I$ acts as a switch: it controls where the extra commutator $z$ appears, and hence where undecidable instances hide, while the lamplighter quotient keeps the geometry and the geodesic language tractable.","pith_inferences":["A natural next test, raised by the paper as Question 2.7, is whether a sufficiently irregular recursive $I$ makes Uniform Subgroup Membership decidable in $G_I$ while the Knapsack problem is undecidable; that would separate yet another pair of algorithmic problems inside the same family.","Because the rational growth of Theorem 2 comes from an isometry to a direct product, the generating-set trick may transfer to other central extensions with rational-growth quotients, producing more groups with rational growth series and undecidable word problem.","The context-free part of Theorem 4.1 rests on the sufficiency direction of a quoted characterization of conjugacy geodesics in $C_2\\wr F_r$; a direct verification of that direction for short elements would remove the main residual doubt, and a mismatch would isolate exactly which part of the grammar construction fails."],"forward_implications":["The classical observation that recursively presented groups with undecidable word problem have non-computable growth series cannot be extended to all finitely generated groups, since $G_I$ has rational growth series and undecidable word problem.","Subgroup Membership and Uniform Subgroup Membership are genuinely different problems: within $G_I$, every fixed finitely generated subgroup has decidable membership, yet no algorithm can take a pair of generators and decide whether $z$ lies in the subgroup.","A conjugacy-geodesic language as low as context-free does not imply a decidable conjugacy problem; the group $G(F_2,I)$ has an unambiguously context-free conjugacy-geodesic language and undecidable conjugacy problem.","Within the family, residual finiteness is equivalent to $H$ being residually finite and $I$ being a union of cosets of a finite-index subgroup, and $G(H,I)\\simeq G(H,J)$ exactly when some automorphism of $H$ carries $I$ to $J$, under the unit-conjecture hypothesis."],"supporting_citations":[{"why":"Supplies the theorem that finitely generated metabelian groups have decidable uniform subgroup membership, used to decide membership in the lamplighter quotient in Theorem 1.","marker":"[30]"},{"why":"Supplies the closed-form rational growth series of $C_2\\wr\\mathbb{Z}$ used in Proposition 3.2 to compute the growth series of $G_I$.","marker":"[23]"},{"why":"Observes that $G_I$ with the chosen generating set is isometric to $C_2\\times(C_2\\wr\\mathbb{Z})$, the fact that makes the growth series rational.","marker":"[18]"},{"why":"Provides the characterization of conjugacy geodesics in $C_2\\wr F_r$ quoted as Proposition A.1, from which the unambiguous context-free grammar of Theorem A.4 is built.","marker":"[27]"}],"fun_headline_variants":["One lamplighter family splits three group decision problems","Lamplighter switch: one subset splits multiple group problems","Central extension of lamplighter answers three open problems","Lamplighter twist yields unique decidable-undecidable combos","Finite lamplighter extensions separate subgroup, word, conjugacy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the quoted characterization of shortest representatives of conjugacy classes in $C_2\\wr F_r$ is correct in the sufficiency direction, because the context-free grammar of Theorem A.4 is built on it and would accept non-geodesic words if that direction failed.","fun_headline_variants_meta":{"raw":{"variants":["One lamplighter family splits three group decision problems","Lamplighter switch: one subset splits multiple group problems","Central extension of lamplighter answers three open problems","Lamplighter twist yields unique decidable-undecidable combos","Finite lamplighter extensions separate subgroup, word, conjugacy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000939,"raw_usage":{"total_tokens":4003,"prompt_tokens":923,"completion_tokens":3080,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":539,"completion_tokens_details":{"reasoning_tokens":2997}},"tokens_in":539,"tokens_out":3080,"duration_ms":26384,"temperature":1.0,"reasoning_tokens":2997,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:32:38.800015+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all elements of $C_2\\wr F_2$ of length at most 8 for a fixed free basis, compute the true minimal length in each conjugacy class, and check whether every word accepted by the grammar of Theorem A.4 (equivalently, every element satisfying conditions (1)--(4) of Proposition A.1) is one of those minimal representatives; a single accepted word that is not minimal would refute the context-free claim of Theorem 4.1.","supporting_citations":[{"cited_title":"Some algorithmic problems for solvable groups","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that finitely generated metabelian groups have decidable uniform subgroup membership, used to decide membership in the lamplighter quotient in Theorem 1."},{"cited_title":"Rational growth of wreath products","cited_arxiv_id":null,"evidence_quote":"Supplies the closed-form rational growth series of $C_2\\wr\\mathbb{Z}$ used in Proposition 3.2 to compute the growth series of $G_I$."},{"cited_title":"Infinitely many finitely generated groups having the same Cayley graph","cited_arxiv_id":null,"evidence_quote":"Observes that $G_I$ with the chosen generating set is isometric to $C_2\\times(C_2\\wr\\mathbb{Z})$, the fact that makes the growth series rational."},{"cited_title":"Conjugacy growth series of some wreath products","cited_arxiv_id":"1610.07868","evidence_quote":"Provides the characterization of conjugacy geodesics in $C_2\\wr F_r$ quoted as Proposition A.1, from which the unambiguous context-free grammar of Theorem A.4 is built."}],"review_version":1}