REVIEW 3 major objections 6 minor 32 references
On finite extensions of lamplighter groups
T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read One family of lamplighter extensions yields three never-before-seen combinations of algorithmic properties.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§4.2, Lemma 4.5] 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.
- [§A.1, Proposition A.1] 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.
- [§A.4, Theorem A.4] 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.
minor comments (6)
- [§0.3] In the definition of conjugacy, 'there exists c∈G such that g = cgc^{-1}' should read 'g = chc^{-1}'.
- [§2, Lemma 2.3] 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.
- [§3, Proposition 3.4] 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.
- [§1, Theorem 1.4] 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.
- [§A, Theorem A.4] 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.
- [§A, reference [27]] 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.
Circularity Check
No significant circularity: the main results are derived from explicit constructions and external benchmarks, not from their own conclusions.
full rationale
The derivation chain is self-contained against external benchmarks. The family G(H,I) is defined by a presentation involving I, but none of the theorems assumes the property it proves: Theorem 1 reduces Uniform Subgroup Membership undecidability to the halting problem via Lemma 2.3, and uses Romanovskii's theorem for the decidable half; Theorem 2 obtains rational growth by the explicit metric identity ||g||_S = ||tau(g)||_T for S = tau^{-1}(T) and combines it with Theorem 1.4's characterization of the Word Problem; Theorem 4.1's undecidable Conjugacy Problem is reduced to Lemma 4.3, while the ConjGeo statement is transferred from the quotient C2 wr F2 by Lemma 4.5 and the appendix's grammar analysis. The only load-bearing external imports (Mercier's characterization of conjugacy geodesics, Johnson's growth computation, Romanovskii's metabelian membership theorem, Sale's conjugacy search result) are independent of the present paper and are cited as such, not self-citations. Proposition A.1's sufficiency direction and the finite-grammar status of Theorem A.4 are asserted rather than fully formalized, and those are correctness or completeness risks rather than instances of circularity: the paper does not define ConjGeo in terms of the grammar, nor does it fit parameters to the claims it then 'predicts'. No fitted input is renamed as a prediction, and no load-bearing conclusion reduces to an author's own prior result.
Assumptions & free parameters
assumptions (6)
- standard math Romanovskii's theorem: finitely generated metabelian groups have decidable Uniform Subgroup Membership.
- standard math Johnson's formula for the rational growth series of C2 ≀ Z with standard generators.
- domain assumption Mercier's characterization of conjugacy geodesics in C2 ≀ Fr, as restated in Proposition A.1.
- standard math Sale's solution of the Conjugacy Search Problem in C2 ≀ Z.
- standard math Semi-linearity of Knapsack solution sets in co-context-free groups.
- standard math C2 ≀ Z embeds in Thompson's group V, and embeddability in V implies context-free co-Word Problem.
Cite this review
Pith. "Pith review of On finite extensions of lamplighter groups." pith.science (2026). https://pith.science/paper/4YW7CGWY
@misc{pith2026250713203,
author = {Pith},
title = {Pith review of: On finite extensions of lamplighter groups},
year = {2026},
howpublished = {\url{https://pith.science/paper/4YW7CGWY}},
note = {Machine review of arXiv:2507.13203}
}
read the original abstract
We study a family of groups consisting of the simplest extensions of lamplighter groups. We use these groups to answer multiple open questions in combinatorial group theory, providing groups that exhibit various combinations of properties: 1) Decidable Subgroup Membership and undecidable Uniform Subgroup Membership Problem, 2) Rational volume growth series and undecidable Word Problem and 3) Recursive (even context-free) language of conjugacy geodesics, decidable Word Problem, and undecidable Conjugacy Problem. We also consider the co-Word Problem, residual finiteness and the Isomorphism Problem within this class.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Finite generating sets of relatively hy- perbolic groups and applications to geodesic languages
Yago Antolin and Laura Ciobanu. “Finite generating sets of relatively hy- perbolic groups and applications to geodesic languages”. In: Transactions of the American Mathematical Society 368.11 (2016), pp. 7965–8010
work page 2016
-
[2]
Orbit decidability and the conjugacy problem for some extensions of groups
Oleg Bogopolski, Armando Martino, and Enric Ventura. “Orbit decidability and the conjugacy problem for some extensions of groups”. In: Transactions of the American Mathematical Society 362.4 (2010), pp. 2003–2036
work page 2010
-
[3]
James W. Cannon. The Growth of the Closed Surface Groups and the Com- pact Hyperbolic Coxeter Groups . 1980
work page 1980
-
[4]
The combinatorial structure of cocompact discrete hy- perbolic groups
James W. Cannon. “The combinatorial structure of cocompact discrete hy- perbolic groups”. In: Geometriae Dedicata 16.2 (1984), pp. 123–148. 25
work page 1984
-
[5]
Conditional Non-Soficity of p-adic Deligne Extensions: on a Theorem of Gohla and Thom
Michael Chapman, Yotam Dikstein, and Alexander Lubotzky. Conditional Non-Soficity of p-adic Deligne Extensions: on a Theorem of Gohla and Thom. https://arxiv.org/abs/2410.02913. 2024
arXiv 2024
-
[6]
Turbo” Ho, and Mark Pengitore. “Rational growth in torus bundle groups of odd trace
Seongjun Choi, Meng-Che “Turbo” Ho, and Mark Pengitore. “Rational growth in torus bundle groups of odd trace”. In: Proceedings of the Ed- inburgh Mathematical Society 65.4 (2022), pp. 1080–1132
work page 2022
-
[7]
Conjugacy geodesics and growth in dihedral Artin groups
Laura Ciobanu and Gemma Crowe. “Conjugacy geodesics and growth in dihedral Artin groups”. In: New York Journal of Mathematics 31 (2025), pp. 465–507
work page 2025
-
[8]
Conjugacy growth series and lan- guages in groups
Laura Ciobanu and Susan Hermiller. “Conjugacy growth series and lan- guages in groups”. In: Transactions of the American Mathematical Society 366.5 (2014), pp. 2803–2825
work page 2014
Show all 32 references
-
[9]
Conjugacy languages in groups
Laura Ciobanu, Susan Hermiller, Derek Holt, and Sarah Rees. “Conjugacy languages in groups”. In: Israel Journal of Mathematics 211 (2016), pp. 311– 347
2016
-
[10]
The degree of commutativity and lamplighter groups
Charles G. Cox. “The degree of commutativity and lamplighter groups”. In: International Journal of Algebra and Computation 28.07 (2018), pp. 1163– 1173
2018
-
[11]
Conjugacy languages in virtual graph products
Gemma Crowe. “Conjugacy languages in virtual graph products”. In: Jour- nal of Algebra 634 (2023), pp. 873–910
2023
-
[12]
Subgroup distortion in wreath products of cyclic groups
Tara C. Davis and Alexander Yu. Olshanskii. “Subgroup distortion in wreath products of cyclic groups”. In: Journal of Pure and Applied Algebra 215.12 (2011), pp. 2987–3004
2011
-
[13]
Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
Ruiwen Dong. Submonoid Membership in n-dimensional lamplighter groups and S-unit equations. (ICALP 2025). 2025
2025
-
[14]
The Heisenberg group is pan-rational
Moon Duchin and Michael Shapiro. “The Heisenberg group is pan-rational”. In: Advances in Mathematics 346 (2019), pp. 219–263
2019
-
[15]
Not residually finite groups of intermediate growth, com- mensurability and non-geometricity
Anna Erschler. “Not residually finite groups of intermediate growth, com- mensurability and non-geometricity”. In: Journal of Algebra 272.1 (2004), pp. 154–172
2004
-
[16]
No quasi-isometric rigid- ity for proper actions on CAT(0) cube complexes
Francesco Fournier-Facio and Anthony Genevois. “No quasi-isometric rigid- ity for proper actions on CAT(0) cube complexes”. In: Proceedings of the American Mathematical Society 151.12 (2023), pp. 5097–5109
2023
-
[17]
Knap- sack Problems for Wreath Products
Moses Ganardi, Daniel K¨ onig, Markus Lohrey, and Georg Zetzsche. “Knap- sack Problems for Wreath Products”. In: STACS 2018 . Vol. 96. Leibniz International Proceedings in Informatics (LIPIcs). 2018, 32:1–32:13
2018
-
[18]
Infinitely many finitely generated groups having the same Cayley graph
Anthony Genevois. Infinitely many finitely generated groups having the same Cayley graph. MathOverflow. https://mathoverflow.net/q/394830
-
[19]
Gray and Carl-Fredrik Nyberg-Brodda
Robert D. Gray and Carl-Fredrik Nyberg-Brodda. Membership problems in braid groups and Artin groups . 2024. 26
2024
-
[20]
On problems related to growth, entropy, and spectrum in group theory
Rostislav Grigorchuk and Pierre De La Harpe. “On problems related to growth, entropy, and spectrum in group theory”. In: Journal of dynamical and control systems 3 (1997), pp. 51–89
1997
-
[21]
Residual Properties of Infinite Soluble Groups
Karl W. Gruenberg. “Residual Properties of Infinite Soluble Groups”. In: Proceedings of the London Mathematical Society s3-7.1 (1957), pp. 29–62
1957
-
[22]
Finiteness Conditions for Soluble Groups
Philip Hall. “Finiteness Conditions for Soluble Groups”. In: Proceedings of the London Mathematical Society s3-4.1 (1954), pp. 419–436
1954
-
[23]
Rational growth of wreath products
David L. Johnson. “Rational growth of wreath products”. In: Groups St Andrews 1989. Ed. by C. M. Campbell and E. F. Robertson. Vol. 2. London Mathematical Society Lecture Note Series. 1991, pp. 309–315
1989
-
[24]
Knapsack and sub- set sum problems in nilpotent, polycyclic, and co-context-free groups
Daniel K¨ onig, Markus Lohrey, and Georg Zetzsche. “Knapsack and sub- set sum problems in nilpotent, polycyclic, and co-context-free groups”. In: Algebra and computer science . AMS, 2016, pp. 129–144
2016
-
[25]
Rational subsets and submonoids of wreath products
Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. “Rational subsets and submonoids of wreath products”. In: Information and Computation 243 (2015). 40th International Colloquium on Automata, Languages and Pro- gramming (ICALP 2013), pp. 191–204
2015
-
[26]
The Conjugacy Problem in Wreath Products and Free Metabelian Groups
Jane Matthews. “The Conjugacy Problem in Wreath Products and Free Metabelian Groups”. In: Transactions of the American Mathematical Society 121.2 (1966), pp. 329–339
1966
-
[27]
Conjugacy growth series of some wreath products
Valentin Mercier. Conjugacy growth series of some wreath products . https: //arxiv.org/abs/1610.07868. 2016
2016 arXiv
-
[28]
The entrance problem for direct unions of groups
K. A. Mikhailova. “The entrance problem for direct unions of groups”. In: Doklady Akademii Nauk SSSR 119 (1958), pp. 1103–1105
1958
-
[29]
The rationality of Sol-manifolds
Andrew Putman. “The rationality of Sol-manifolds”. In: Journal of Algebra 304.1 (2006), pp. 190–215
2006
-
[30]
Some algorithmic problems for solvable groups
Nikolay S. Romanovskii. “Some algorithmic problems for solvable groups”. In: Algebra and Logic 13.1 (1974), pp. 13–16
1974
-
[31]
Geometry of the conjugacy problem in lamplighter groups
Andrew Sale. “Geometry of the conjugacy problem in lamplighter groups”. In: Algebra and computer science . AMS, 2016, pp. 171–183
2016
-
[32]
Rational and transcendental growth series for the higher Heisenberg groups
Michael Stoll. “Rational and transcendental growth series for the higher Heisenberg groups”. In: Inventiones mathematicae 126 (1996), pp. 85–109. Mathematical Institute, University of Oxford, UK E-mail address: corentin.bodart@maths.ox.ac.uk URL: https://sites.google.com/coren...
1996
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.