{"id":"b770440b-12f0-4a4a-87b0-bc6ce72e4435","arxiv_id":"1908.07294","paper_version":4,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every finitely generated virtually abelian group with any finite weighted generating set, geodesic growth is either polynomial with rational growth series or exponential with holonomic growth series, and the geodesic language is blind multicounter.","lead":"In virtually abelian groups, groups that are only finitely far from an abelian lattice, the number of shortest words for group elements always grows either polynomially or exponentially, never in the intermediate range. The paper proves this and shows the geodesic growth series is holonomic, and rational in the polynomial case, using a new polyhedrally constrained language framework.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 5.14 applies Δ to the empty pattern ε though Definition 5.4 does not make ε a strong pattern; for σ=at in D∞ the prescribed sequence needs undefined Δ(ε,t), so Lemmas 6.4 and 7.2 are not fully defined.","rationale":"After a good-faith reading, the proof is otherwise coherent: the polyhedral language argument, the affine maps Ψπ and Ωπ, the geodesic polyhedral sets Gπ, and the blind multicounter construction all line up, and the main steps are explicitly derived. The reader's identification of Lemma 5.13 as the weakest assumption is apt. The specific defect I find there is not a matter of computational difficulty but of definitional coverage: the very first application of Δ is outside its domain for nonempty words whose first shuffle leaves τ=ε and a nonempty suffix, and such words exist in the simplest nontrivial virtually abelian group. Since Lemma 6.4's bijection and Theorem 7.2's automaton both invoke Algorithm 5.14 without restriction, the central claim is not fully proved as written. The issue is local and easily repaired; it does not suggest the dichotomy is false. Hence I would move the verdict from ACCEPT to CONDITIONAL, pending an explicit convention or patch for the empty-pattern case.","tokens_in":20817,"tokens_out":42930,"duration_ms":487017,"concrete_test":"Run Algorithm 5.14 verbatim on the infinite dihedral group D∞ = <a,t | t^2=1, t a t = a^{-1}> with S={a,t} and σ=at, using Definitions 5.4-5.8 and Lemma 5.13 as written. The first step with τ=ε and w=at produces the intermediate extended word ((e_b,ε),t); the next transition requires Δ(ε,t), so the algorithm is undefined unless ε is admitted as a strong pattern. If the intended convention is that ε is strong, verify that every application in Lemmas 5.13, 6.4, and Theorem 7.2 satisfies the stated hypotheses and correct the definition accordingly; otherwise add an explicit handling of the initial empty pattern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central construction is the finite sequence (3) produced by repeated applications of Δ. Lemma 5.13 has domain StrPatt × W1, and Definition 5.4 distinguishes patterns from strong patterns: for ε the condition that ρ(π) be distinct from the coset representatives in (2) fails because ρ(ε)=1 is listed in (2). Algorithm 5.14 nevertheless starts with ((0,ε),σ) and applies Δ to τ=ε. This is not a vacuous worry. Let G=D∞ with S={a,t}, d=2, σ=at. Then w=at, and Lemma 5.13 with τ=ε, w∉P, α=ε, β=a, δ=t is in the first case with a=0, giving τ'=ε and σ'=t. The next step would need Δ(ε,t), which is outside the stated domain, so the sequence (3) does not exist. The same gap makes the initial edge of pσ in Lemma 6.4 and the simulation in Theorem 7.2 undefined for such words. The second case of Lemma 5.13 also contains an apparent index typo (\"a·k+b\" with an undefined a instead of the final-block coordinate used in the display), which should be corrected. The gap is patchable, by declaring ε a strong pattern or adding an explicit initial case, but as written the main theorems rest on an unstated convention.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21074,"tokens_out":11104,"duration_ms":111685,"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":[{"comment":"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.","section":"Definition 5.4 and Algorithm 5.14"}],"minor_comments":[{"comment":"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|.","section":"Lemma 5.13, second case"},{"comment":"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.","section":"Definition 7.1"},{"comment":"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.","section":"Lemma 3.1"},{"comment":"In the sentence introducing the formal definition, 'bind k-counter automaton' should be 'blind k-counter automaton'.","section":"Definition 7.1"},{"comment":"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.","section":"Definition 6.3"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are plausible, and the gap concerning the empty pattern is readily fixable. The revision should also correct the undefined 'a' in Lemma 5.13 and the closure typo in Definition 7.1. I did not find evidence of circularity or of a deeper obstruction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Big picture: this is a genuine result and the proof idea is sound. The paper proves the full polynomial-vs-exponential dichotomy for geodesic growth of virtually abelian groups, with holonomic growth series (rational in the polynomial case), and shows the geodesic language is blind multicounter. That settles what Bridson et al. left open for these groups, and it is not a repackaging of their results. The machinery—shuffling words into patterned form, polyhedrally constrained languages, the finite graph Γ—is carefully built, and the weight-preserving bijection in Lemma 6.4 is the real core. I believe the main theorems are correct.\n\nThe main soft spot is exactly the one in the stress-test note, and it is real. Definition 5.4 excludes ε from StrPatt, yet Algorithm 5.14 starts from ((0,ε),σ), so the first application of Δ has τ=ε. In D∞ with S={a,t}, σ=at forces the sequence through Δ(ε,t), which is undefined. That is a genuine gap in the written construction; Lemmas 6.4 and 7.2 depend on it. It is patchable—declare ε a strong pattern or handle the initial step separately, and Lemma 5.13's proof actually works for τ=ε if you allow it—but as written it is an unstated convention, and a referee should ask the author to fix it.\n\nTwo smaller items. Lemma 3.1 says holonomic series have only finitely many poles, which is false: algebraic functions like sqrt(1-z) are holonomic and have branch points. The argument only needs the singular set to be finite, so the intended conclusion survives, but the wording should be corrected. And in the second case of Lemma 5.13's proof, the label 'a·k+b' uses an undefined a; from the displayed new vector it should be the index of the new final block. Cosmetic, but confusing.\n\nThe citation pattern looks right: Benson, Massazza, Greibach, and the Bridson et al. context are all used as tools, not as hidden assumptions. There are no fitted parameters. On balance this deserves a serious referee: the result is important inside geometric group theory, and the proof is mostly explicit and checkable. I would send it out; the revision should be minor.\n\nWho it's for: people working on growth series, formal language classifications of geodesics, and holonomic generating functions. I'd cite it.","headline":"Solid and new result; one patchable gap in the base case of the shuffling algorithm and a sloppy Lemma 3.1.","tokens_in":21616,"tokens_out":5973,"would_cite":true,"duration_ms":62704,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20F65","20K35","68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"For virtually abelian groups, geodesic growth is polynomial or exponential, with nothing in between.","keywords":["virtually abelian group","geodesic language","geodesic growth","blind multicounter language","holonomic series","generating function","patterned words","polyhedrally constrained language"],"falsifier":"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.","tokens_in":20572,"feed_emoji":"📈","tokens_out":8921,"duration_ms":86270,"temperature":0.7,"pith_summary":"This paper proves that for any virtually abelian group and any finite weighted generating set—where each generator carries a positive integer weight and a word's weight is the sum of its letters' weights—the count of geodesic words grows either polynomially or exponentially; an intermediate growth rate is impossible. It also proves that the geodesic growth series is holonomic, meaning it satisfies a linear differential equation with rational-function coefficients, and rational in the polynomial case. In parallel, the set of all geodesic words is shown to be a blind multicounter language, that is, it is accepted by a finite-state machine with finitely many counters it can never inspect. The result matters because geodesic growth is a finer invariant than ordinary group growth, and it settles the virtual-abelian case of a known question about intermediate geodesic growth.","feed_headline":"Geodesic growth rate never falls between polynomial and exponential","feed_subtitle":"The counting series is holonomic and rational in polynomial cases; geodesic words form a blind multicounter language.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the polyhedral-set machinery and the proof that standard growth series of finite extensions of Z^n are rational, which the paper adapts to geodesic counting.","marker":"[2]"},{"why":"Poses the question of intermediate geodesic growth and gives the earlier sufficient condition in virtually abelian groups that this paper sharpens into a dichotomy.","marker":"[3]"},{"why":"Provides the theorem that linearly constrained languages have holonomic multivariate generating functions, extended here to polyhedral constraints.","marker":"[19]"},{"why":"Defines blind multicounter automata and supplies the language hierarchy used for Theorem 7.2.","marker":"[13]"},{"why":"Supplies the classical integer-power-series theorem used to rule out intermediate growth once the geodesic growth series is holonomic.","marker":"[4]"},{"why":"Provides the analytic-combinatorics results on rational and holonomic series and coefficient asymptotics used in the growth dichotomy.","marker":"[12]"},{"why":"Shows inverse images of finite-monoid subsets are regular, which lets modular arithmetic constraints be folded into the constrained language construction.","marker":"[22]"}],"fun_headline_variants":["Geodesic growth: polynomial or exponential, no in-between","Dichotomy: geodesic growth is either polynomial or exponential","No intermediate geodesic growth in virtually abelian groups","Blind multicounter geodesics: growth is polynomial or exponential","Virtually abelian geodesic growth never sits between polynomial and exponential"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Geodesic growth: polynomial or exponential, no in-between","Dichotomy: geodesic growth is either polynomial or exponential","No intermediate geodesic growth in virtually abelian groups","Blind multicounter geodesics: growth is polynomial or exponential","Virtually abelian geodesic growth never sits between polynomial and exponential"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000549,"raw_usage":{"total_tokens":2538,"prompt_tokens":775,"completion_tokens":1763,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":391,"completion_tokens_details":{"reasoning_tokens":1677}},"tokens_in":391,"tokens_out":1763,"duration_ms":12995,"temperature":1.0,"reasoning_tokens":1677,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:21:57.448540+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Benson, Growth series of finite extensions of Zn are rational , Invent","cited_arxiv_id":null,"evidence_quote":"Supplies the polyhedral-set machinery and the proof that standard growth series of finite extensions of Z^n are rational, which the paper adapts to geodesic counting."},{"cited_title":"Bridson, José Burillo, Murray Elder, and Zoran Šunić, On groups whose geodesic growth is polynomial, Internat","cited_arxiv_id":null,"evidence_quote":"Poses the question of intermediate geodesic growth and gives the earlier sufficient condition in virtually abelian groups that this paper sharpens into a dichotomy."},{"cited_title":"Massazza, Holonomic functions and their relation to linearly constra ined languages, RAIRO Inform","cited_arxiv_id":null,"evidence_quote":"Provides the theorem that linearly constrained languages have holonomic multivariate generating functions, extended here to polyhedral constraints."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines blind multicounter automata and supplies the language hierarchy used for Theorem 7.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical integer-power-series theorem used to rule out intermediate growth once the geodesic growth series is holonomic."},{"cited_title":"MR2483235","cited_arxiv_id":null,"evidence_quote":"Provides the analytic-combinatorics results on rational and holonomic series and coefficient asymptotics used in the growth dichotomy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows inverse images of finite-monoid subsets are regular, which lets modular arithmetic constraints be folded into the constrained language construction."}],"review_version":1}