REVIEW 1 major objections 5 minor 25 references
Geodesic growth in virtually abelian groups
T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For virtually abelian groups, geodesic growth is polynomial or exponential, with nothing in between.
desk verdict Solid and new result; one patchable gap in the base case of the shuffling algorithm and a sloppy Lemma 3.1. 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 load-bearing object is word shuffling: an algorithm that turns any word over the generating set into a patterned word $(v,\pi)$, where $\pi$ is a short word over a finite set whose prefix coset representatives are all distinct, and the vector $v$ records counts of short subgroup words. The map $\Delta$ performs each step by replacing a bounded-length prefix with a strictly shorter word while preserving both the represented group element and its weight, so the process terminates in finitely many steps. This same mechanism drives both main results: it defines the weight-preserving bijection from words to paths in a finite weighted graph, and it can be executed inside a blind multicounter automaton while the counters check polyhedral membership of $v$.
What would settle it
Run the paper's shuffling algorithm on all short words of an explicit small virtually abelian group, such as the infinite dihedral group with a weighted generating set. If any word fails to reach a patterned word with the same group element and weight while strictly shortening the suffix at each step, Lemma 5.13 is false and the dichotomy collapses. A complementary check: find a virtually abelian generating set whose geodesic growth series is holonomic with integer coefficients but not rational; the classical theorem used in Corollary 3.4.1 would force the unit circle to be a natural boundary, which the holonomicity lemma forbids.
Extended reading notes
Core claim
The central discovery is that geodesic counting in a virtually abelian group reduces, for every finite weighted monoid generating set, to counting paths in a finite weighted labelled graph whose accumulated label vectors lie in polyhedral sets. A weight-preserving bijection sends every word to such a path through an explicit word-shuffling procedure that reorganizes the word into a patterned word: a short prefix pattern whose prefix coset representatives are pairwise distinct, together with counts of short subgroup words. Geodesics correspond exactly to paths whose accumulated label vector sits in a polyhedral set, and the languages that result are polyhedrally constrained, so their multivariate generating functions are holonomic by an extension of a known theorem on constrained languages. Substituting weighted variables produces a holonomic geodesic growth series; a classical theorem on integer-coefficient power series then forces either rationality (polynomial growth) or exponential growth, with no intermediate case. The same shuffling procedure is simulated inside a blind multicounter automaton, so the geodesic language itself is blind multicounter.
Load-bearing premise
Everything rests on Lemma 5.13's claim: every word over the generating set can be shuffled by finitely many prefix replacements that keep the same group element and weight and strictly shorten the remaining suffix, ending in a patterned word.
Editorial extensions
If this is right
- No virtually abelian group has intermediate geodesic growth for any finite weighted generating set.
- In the polynomial case the geodesic growth series is rational, so geodesic counts are eventually exact polynomials in $n$.
- In the exponential case the geodesic growth series is holonomic, so the coefficient sequence obeys a linear recurrence with polynomial coefficients.
- The geodesic language of any virtually abelian group sits in the blind multicounter class, a level of the formal-language hierarchy strictly inside context-sensitive languages.
Reading between the lines
- The same bounded-prefix shuffling strategy should be tested on other groups with a finite-index abelian normal subgroup and a well-behaved normal form; any class admitting such a shuffling would inherit a holonomic geodesic growth series and the same polynomial-or-exponential dichotomy.
- The polyhedral-constraint lemma is likely reusable beyond geodesics, for any counting problem over virtually abelian groups that can be encoded by Parikh vectors in polyhedral sets.
- The proof does not compute the minimal number of counters needed to recognize the geodesic language; a concrete next question is whether this number is determined by the rank of the abelian subgroup and the coherence of the generating set.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies geodesic growth in finitely generated virtually abelian groups with respect to finite weighted monoid generating sets. Its main results are Theorem 6.5, asserting that the geodesic growth series is holonomic and that the growth is either polynomial with rational series or exponential, and Theorem 7.2, asserting that the language of geodesics is blind multicounter. The proof works by introducing a 'shuffling' algorithm that rewrites every word into a canonical patterned word with the same group element and the same weight, characterizing via a polyhedral set Gπ exactly which patterned words are geodesics, and then transferring holonomicity from a class of polyhedrally constrained languages. The same shuffling construction is simulated by a blind multicounter automaton. The exposition is careful, and most closure arguments are given in detail.
Significance. If correct, the paper gives a complete answer for virtually abelian groups to the question of intermediate geodesic growth, and it extends Benson's rationality theorem to the geodesic setting in a natural way. The paper's strengths are its explicit weight-preserving bijection, the polyhedral characterization of geodesic patterned words, and the relatively self-contained treatment of the holonomic and multicounter machinery. The central gap identified below is localized and easily patchable; I see no reason to doubt the main theorems.
major comments (1)
- [Definition 5.4 and Algorithm 5.14] The initial step of Algorithm 5.14 is not defined. Definition 5.4 declares a word π∈P* a strong pattern only when ρ(π) is distinct from the representatives in (2); for π=ε this condition fails because ρ(ε)=1 is itself listed in (2). Yet Algorithm 5.14 starts from ((0,ε),σ), and Lemma 6.4 and Theorem 7.2 both use Δ(ε,w). In the concrete case G=D∞ with S={a,t} and d=2, the word σ=at gives, by the first case of Lemma 5.13, Δ(ε,at)=(b,ε,t); the next step would require Δ(ε,t), which is outside the stated domain StrPatt×W1. Thus the finite sequence (3) does not exist as written, and the weight-preserving bijection of Lemma 6.4 and the initial configuration of the multicounter machine in Theorem 7.2 are undefined for such words. This is patchable, for example by explicitly adding ε to StrPatt or by adding a separate initial case, but it must be fixed before the main theorems are fully proved.
minor comments (5)
- [Lemma 5.13, second case] In the displayed definition Δ(τ,w)=(a·k+b, τ', δ), the symbol a is undefined in the second case; the intended coordinate is k·m+b, where m=|Y|.
- [Definition 7.1] The text says ⊢* is the 'transitive symmetric closure' of ⊢, but acceptance is defined by reachability, which is the reflexive transitive closure; the symmetric closure would allow backwards transitions and would not describe the intended machine.
- [Lemma 3.1] The statement that a holonomic series 'can have only finitely many poles' is imprecise; the proof establishes analytic continuation outside the finite singular set of the coefficient functions, which is the property actually used in Corollary 3.4.1.
- [Definition 7.1] In the sentence introducing the formal definition, 'bind k-counter automaton' should be 'blind k-counter automaton'.
- [Definition 6.3] Edges labelled by ∅, which arise in the w∈P case of Lemma 5.13, are not counted in α(p); since e_{τ,∅}=0 is defined in Definition 5.11, this is harmless, but it should be stated explicitly.
Circularity Check
No circularity found: the main theorem is derived from a self-contained weight-preserving bijection and external closure results, not from its own conclusion.
full rationale
The derivation is self-contained. Theorem 6.5 is obtained by constructing a finite graph Γ whose paths are in weight-preserving bijection with S* (Lemma 6.4), then carving out the geodesic paths using the polyhedral sets Gπ of Lemma 5.16, whose defining criterion is an independent 'no shorter patterned word' condition and not an assumption of the theorem. Holonomicity of the resulting polyhedrally constrained languages comes from Proposition 4.3, which uses Massazza's external theorem and standard closure properties; the polynomial/exponential dichotomy is then drawn from general results (Fekete's lemma, Pólya–Carlson, Lemma 3.3). No fitted parameter is renamed as a prediction, no load-bearing step is justified only by a self-citation, and no uniqueness theorem is imported from the author's prior work. The reviewer-noted issue that ε is not formally a strong pattern, so Algorithm 5.14's initial application of Δ is not covered by Lemma 5.13's stated domain, is a definability or correctness gap in the shuffle construction rather than a circular reduction of the theorem to its inputs; it does not change the circularity verdict.
Assumptions & free parameters
assumptions (8)
- domain assumption Every finitely generated virtually abelian group contains a finite-index normal subgroup isomorphic to Z^n for some n.
- standard math The class of polyhedral sets is closed under Cartesian product, finite union, intersection, difference, and integer affine transforms (Benson, Propositions 13.1, 13.7, 13.8).
- standard math Massazza's theorem: the multivariate generating function of a linearly constrained language is holonomic.
- standard math Holonomic functions are closed under addition, multiplication, and composition with algebraic functions (Lipshitz, Proposition 2.3).
- standard math A power series with integer coefficients that is analytic in the open unit disk is either rational or has the unit circle as a natural boundary (Pólya-Carlson).
- standard math Fekete's lemma gives the limit αS = lim_{n→∞} γS(n)^{1/n} for submultiplicative positive sequences.
- standard math The class of unambiguous context-free languages is closed under intersection with regular languages, and inverse images of subsets of finite monoids under monoid homomorphisms are regular.
- standard math Linear ODEs with rational coefficients have unique analytic solutions in simply connected regions away from the poles of the coefficients (Wasow).
Cite this review
Pith. "Pith review of Geodesic growth in virtually abelian groups." pith.science (2026). https://pith.science/paper/J22SNUYB
@misc{pith2026190807294,
author = {Pith},
title = {Pith review of: Geodesic growth in virtually abelian groups},
year = {2026},
howpublished = {\url{https://pith.science/paper/J22SNUYB}},
note = {Machine review of arXiv:1908.07294}
}
read the original abstract
We show that the geodesic growth function of any finitely generated virtually abelian group is either polynomial or exponential; and that the geodesic growth series is holonomic, and rational in the polynomial growth case. In addition, we show that the language of geodesics is blind multicounter.
Figures
Reference graph
Works this paper leans on
-
[1]
Laurent Bartholdi, Rostislav Grigorchuk, and Volodymy r Nekrashevych, From fractal groups to fractal sets , Fractals in Graz 2001, 2003, pp. 25–118. MR2091700
work page 2001
-
[2]
Benson, Growth series of finite extensions of Zn are rational , Invent
M. Benson, Growth series of finite extensions of Zn are rational , Invent. Math. 73 (1983), no. 2, 251–269. MR714092
work page 1983
-
[3]
Martin R. Bridson, José Burillo, Murray Elder, and Zoran Šunić, On groups whose geodesic growth is polynomial, Internat. J. Algebra Comput. 22 (2012), no. 5, 1250048,
work page 2012
-
[4]
Fritz Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten , Math. Z. 9 (1921), no. 1-2, 1–13. MR1544447
work page 1921
-
[5]
Sean Cleary, Murray Elder, and Jennifer Taback, Cone types and geodesic languages for lamplighter groups and Thompson ’s group F , J. Algebra 303 (2006), no. 2, 476–
work page 2006
-
[6]
Pierre de la Harpe, Topics in geometric group theory , Chicago Lectures in Mathemat- ics, University of Chicago Press, Chicago, IL, 2000. MR1786 869
work page 2000
-
[7]
Murray Elder, Regular geodesic languages and the falsification by fellow t raveler prop- erty, Algebr. Geom. Topol. 5 (2005), 129–134. MR2135549
work page 2005
-
[8]
Murray Elder, Mark Kambites, and Gretchen Ostheimer, On groups and counter automata, Internat. J. Algebra Comput. 18 (2008), no. 8, 1345–1364. MR2483126
work page 2008
Show all 25 references
-
[9]
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvi o V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups , Jones and Bartlett Publishers, Boston, MA, 1992. MR1161694
1992
-
[10]
Alex Evetts, Rational growth in virtually abelian groups , Illinois J. Math. 63 (2019), no. 4, 513–549. MR4032813
2019
-
[11]
Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten , Math
M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten , Math. Z. 17 (1923), no. 1, 228–249. MR1544613
1923
-
[12]
MR2483235
Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge Univer- sity Press, Cambridge, 2009. MR2483235
2009
-
[13]
S. A. Greibach, Remarks on blind and partially blind one-way multicounter m achines, Theoret. Comput. Sci. 7 (1978), no. 3, 311–324. MR513714
1978
-
[14]
R. I. Grigorchuk, On the Milnor problem of group growth , Dokl. Akad. Nauk SSSR 271 (1983), no. 1, 30–33. MR712546
1983
-
[15]
Gromov, Hyperbolic groups, Essays in group theory, 1987, pp
M. Gromov, Hyperbolic groups, Essays in group theory, 1987, pp. 75–263. MR919829
1987
-
[16]
Hautes Études Sci
Mikhael Gromov, Groups of polynomial growth and expanding maps , Inst. Hautes Études Sci. Publ. Math. 53 (1981), no. 1, 53–73. MR623534
1981
-
[17]
Lipshitz, D-finite power series , J
L. Lipshitz, D-finite power series , J. Algebra 122 (1989), no. 2, 353–373. MR999079
1989
-
[18]
395, Cambridge University Press, Cambridge, 2012
A vinoam Mann, How groups grow, London Mathematical Society Lecture Note Series, vol. 395, Cambridge University Press, Cambridge, 2012. MR2 894945
2012
-
[19]
Massazza, Holonomic functions and their relation to linearly constra ined languages, RAIRO Inform
P. Massazza, Holonomic functions and their relation to linearly constra ined languages, RAIRO Inform. Théor. Appl. 27 (1993), no. 2, 149–161. MR1217683
1993
-
[20]
Muller and Paul E
David E. Muller and Paul E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26 (1983), no. 3, 295–310. MR710250
1983
-
[21]
117, American Mathematical Society, Providen ce, RI, 2005
Volodymyr Nekrashevych, Self-similar groups , Mathematical Surveys and Mono- graphs, vol. 117, American Mathematical Society, Providen ce, RI, 2005. MR2162164
2005
-
[22]
M. O. Rabin and D. Scott, Finite automata and their decision problems , IBM J. Res. Develop. 3 (1959), 114–125. MR103795
1959
-
[23]
Michael Shapiro, A note on context-sensitive languages and word problems , Internat. J. Algebra Comput. 4 (1994), no. 4, 493–497. MR1313124 GEODESIC GROWTH IN VIRTUALLY ABELIAN GROUPS 23
1994
-
[24]
, Pascal’s triangles in abelian and hyperbolic groups , J. Austral. Math. Soc. Ser. A 63 (1997), no. 2, 281–288. MR1475566
1997
-
[25]
XIV, Interscience Publisher s John Wiley & Sons, Inc., New York-London-Sydney, 1965
Wolfgang Wasow, Asymptotic expansions for ordinary differential equations , Pure and Applied Mathematics, Vol. XIV, Interscience Publisher s John Wiley & Sons, Inc., New York-London-Sydney, 1965. MR0203188 University of Technology Sydney, Australia URL: https://alexbishop.githu...
1965
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.