arxiv: 2605.12793 · v1 · submitted 2026-05-12 · 🧮 math.CO · math.GR

Recognition: 2 theorem links

· Lean Theorem

On groups with D-finite cogrowth series

Mudit Aggarwal , Murray Elder , Andrew Rechnitzer

Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:50 UTC · model grok-4.3

classification 🧮 math.CO math.GR MSC 20F0505A15

keywords cogrowth seriesD-finite functionsSchreier graphtree widthgenerating functionsfinitely presented groupsconstant term extraction

0 comments

The pith

An infinite family of groups has D-finite non-algebraic cogrowth series.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that for one infinite family of finitely presented groups, the cogrowth series with respect to a finite generating set equals the constant term of an algebraic function. This forces the series to be D-finite, satisfying a linear differential equation with polynomial coefficients, while remaining non-algebraic. The argument proceeds by fixing a subgroup whose Schreier graph has finite tree width, then splitting every path into a coset sequence and a walk on the graph so that the two parts can be counted by separate generating functions whose joint solution yields the constant-term expression. The same decomposition produces D-finite non-algebraic series for several additional groups that share the same structural feature.

Core claim

For a particular infinite family of presentations, the cogrowth series can be determined as the constant term of an algebraic function, which shows that it is D-finite and, with more work, not algebraic. The proof exploits the fact that for a particular choice of subgroup, the corresponding Schreier graph has finite tree width, and by considering paths in the cosets and the Schreier graph separately, a system of generating functions which count paths is constructed. The asymptotics of this system establish that the groups have D-finite but non-algebraic cogrowth series. The method also applies to additional examples with similar structure, again yielding D-finite non-algebraic series.

What carries the argument

System of algebraic generating functions obtained by decomposing walks into independent coset traversals and walks on a finite-tree-width Schreier graph of a fixed subgroup, then extracting the constant term.

If this is right

The cogrowth series satisfies a linear differential equation with polynomial coefficients.
The series is not algebraic.
Several additional groups with analogous subgroup structure likewise possess D-finite non-algebraic cogrowth series.
The examples supply concrete support for the conjecture that algebraic cogrowth series occur only for virtually free groups.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The finite-tree-width condition on the Schreier graph could be used as a search criterion to locate further families with D-finite cogrowth.
If the conjecture holds, the algebraic versus D-finite distinction would give a combinatorial characterisation of virtually free groups among those with finite generating sets.
The decomposition technique may extend to other series, such as growth series or random-walk return probabilities, whenever a suitable finite-tree-width Schreier graph exists.

Load-bearing premise

The chosen subgroup admits a Schreier graph of finite tree width so that path counting separates cleanly into coset and graph components.

What would settle it

Explicit computation of the first several hundred coefficients of the cogrowth series for any single group in the family, followed by a check that the sequence fails to satisfy the linear recurrence implied by D-finiteness.

Figures

Figures reproduced from arXiv: 2605.12793 by Andrew Rechnitzer, Mudit Aggarwal, Murray Elder.

**Figure 1.** Figure 1: The Schreier graph of G3 = ⟨a, b, c | a 2 = b 2 = c 2 ⟩; vertex v corresponds to the coset ⟨∆⟩v with the edges drawn by two arcs. To avoid overuse of subscripts, we have chosen generators a, b, c rather than a1, a2, a3. 2.1 Walks in the k-regular tree The problem of counting words in Gk which are equivalent to the identity will be closely related to the problem of counting walks in the k-tree that start an… view at source ↗

**Figure 2.** Figure 2: The Schreier graph of G2 = ⟨a, b | a 3 = b 4 ⟩; vertex p corresponds to the coset ⟨∆⟩p. Consider the Schreier graph of Gk with respect to the generating set {a1, . . . , ak and subgroup ⟨∆⟩. As before, since cosets are in bijection with suffixes as in the previous corollary, we may assume vertices are labelled by suffixes. An example of G2 = ⟨a, b | a 3 = b 4 ⟩ is shown in [PITH_FULL_IMAGE:figures/full_fi… view at source ↗

**Figure 3.** Figure 3: By keeping track of these facet traversals, as the winding number, we keep track of the [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

**Figure 4.** Figure 4: Building our system from two different facets. The dashed line represents where we “cut” [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗

**Figure 5.** Figure 5: Building blocks for this Schreier coset graph and system of walks for [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗

**Figure 6.** Figure 6: Walk decomposition and switching the winding number contribution of a particular loop. [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗

**Figure 7.** Figure 7: Example of attachment with our walks. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗

**Figure 8.** Figure 8: Construction of new walks in the popularity argument. [PITH_FULL_IMAGE:figures/full_fig_p036_8.png] view at source ↗

**Figure 9.** Figure 9: The Schreier graphs of the cosets of the subgroup [PITH_FULL_IMAGE:figures/full_fig_p042_9.png] view at source ↗

**Figure 10.** Figure 10: The Schreier graph of B3 with respect to the presentation ⟨a, x | axa = x 2 ⟩ and ∆ = x 3 . The coset ⟨∆⟩ is indicated by the black vertex. Theorem 8.2. The cogrowth series for B3 with respect to the generating set {a, x} is D-finite but not algebraic. The proof is quite similar to the results above, but requires us to keep track of more tedious details. In particular, we show that the cogrowth series is … view at source ↗

**Figure 11.** Figure 11: The Schreier graph of the group ⟨a, x | axa = x 2 ⟩; The coset ⟨∆⟩ is indicated by the black vertex. B.1 Counting returns on the Schreier graph (no q’s) We start by first counting returns on the Schreier graph without considering the exponent of ∆. Consider the central triangle shown in [PITH_FULL_IMAGE:figures/full_fig_p051_11.png] view at source ↗

**Figure 12.** Figure 12: The central triangle of the Schreier graph. [PITH_FULL_IMAGE:figures/full_fig_p051_12.png] view at source ↗

**Figure 13.** Figure 13: The graph with one “branch” removed. • G01(z) be the generating function of paths in this graph that start at 0 and end at 1, and • G02(z) be the generating function of paths in this graph that start at 0 and end at 2. The generating functions G10 and G20 are defined analogously. We also need to define some “primitive loops”. Let • L00(z) be the generating function of walks of positive length that start a… view at source ↗

**Figure 14.** Figure 14: Graph with labelled vertices used to prove the recursive decomposition of paths for the [PITH_FULL_IMAGE:figures/full_fig_p054_14.png] view at source ↗

**Figure 15.** Figure 15: The central triangle of the Schreier graph with the cosets [PITH_FULL_IMAGE:figures/full_fig_p056_15.png] view at source ↗

read the original abstract

The cogrowth series of a group with respect to a finite generating set is an important combinatorial quantity that seems very difficult to compute exactly, as evidenced by the scarcity of known examples. In this paper, we give a particular infinite family of presentations for which the cogrowth series can be determined as the constant term of an algebraic function, which shows that it is D-finite and, with more work, not algebraic. Our proof exploits the fact that for a particular choice of subgroup, the corresponding Schreier graph has finite tree width, and by considering paths in the cosets and the Schreier graph separately, we are able to construct a system of generating functions which count paths. We find the asymptotics of this system to conclude that the groups have D-finite but non-algebraic cogrowth series. We also apply our method to some additional examples which have some similarities with the infinite family above, and again show they have D-finite but non-algebraic cogrowth series. These examples lend some support to the conjecture that if a group has an algebraic cogrowth series, then it must be virtually-free, and adds to the small collection of known examples of groups having D-finite cogrowth series for at least one finite generating set.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives an explicit infinite family of groups whose cogrowth series are D-finite but non-algebraic, obtained by splitting paths on a finite-treewidth Schreier graph.

read the letter

This paper gives an explicit infinite family of groups whose cogrowth series are D-finite but non-algebraic. They pick a subgroup so the Schreier graph has finite treewidth, split walks into coset-representative steps and steps on the graph, and obtain a finite system of algebraic generating functions whose constant term is the cogrowth series. Asymptotics of the system then rule out algebraicity. The same construction works for a few additional examples that share the structure. The infinite family is the clear addition; earlier examples were mostly isolated cases, so having infinitely many at once is useful. The method itself is standard transfer-matrix counting once the treewidth is fixed, which keeps the argument direct. The equations close without obvious self-reference or fitted parameters. The main point to check is whether the transition rules between coset lifts and graph edges are captured exactly in the system; a mismatch there would affect both the D-finiteness and the asymptotic claim. The paper supplies enough of the setup that a referee can verify small cases by direct computation or enumeration. The asymptotics follow ordinary singularity analysis and do not rest on unstated estimates. This is for combinatorial group theorists who track exact growth series and the conjecture that algebraic cogrowth forces virtual freeness. Readers already familiar with the few known D-finite examples will see how these new ones fit and can use the family for further checks. The work is concrete and checkable enough to deserve a serious referee. I would send it to peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript constructs an infinite family of group presentations such that the cogrowth series with respect to a finite generating set equals the constant term of an algebraic generating function. This establishes D-finiteness of the series; a subsequent singularity analysis shows the series is not algebraic. The argument proceeds by selecting a subgroup whose Schreier graph has finite treewidth, then building a finite system of algebraic equations for generating functions that separately track walks on coset representatives and on the Schreier graph.

Significance. If the construction is correct, the paper supplies the first explicit infinite family of non-virtually-free groups whose cogrowth series are known to be D-finite but non-algebraic. The finite-treewidth technique for producing an algebraic system is reusable and strengthens the evidence for the conjecture that algebraic cogrowth series occur only for virtually free groups. The work also enlarges the small list of groups with provably D-finite cogrowth series.

major comments (2)

[§3] §3 (Construction of the generating-function system): the transition rules that lift generators across coset representatives and the finite-state automaton for the Schreier graph are described only at the level of diagrams; the explicit algebraic equations relating the generating functions F_i(t) are not written out. Without these equations it is impossible to confirm that the constant-term extraction recovers the cogrowth series exactly or that the system is closed under the chosen subgroup generators.
[§4] §4 (Asymptotic analysis): the claim that the dominant singularity is a branch point of square-root type (hence the series is non-algebraic) rests on the radius of convergence of the algebraic system being strictly less than 1 and on the absence of other singularities on the circle of convergence. The manuscript does not compute the explicit radius or verify the non-interference condition between the coset and Schreier-graph components; a mismatch here would invalidate both the D-finiteness and non-algebraicity conclusions.

minor comments (2)

[§3] Notation for the finite set of states in the treewidth automaton is introduced only in a figure caption; a numbered definition in the text would improve readability.
[§5] The additional examples in §5 are stated to be “similar” to the main family, but the precise subgroup and generating-set choices are not tabulated; a short table would clarify the scope of the method.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate the revisions we plan to make.

read point-by-point responses

Referee: [§3] §3 (Construction of the generating-function system): the transition rules that lift generators across coset representatives and the finite-state automaton for the Schreier graph are described only at the level of diagrams; the explicit algebraic equations relating the generating functions F_i(t) are not written out. Without these equations it is impossible to confirm that the constant-term extraction recovers the cogrowth series exactly or that the system is closed under the chosen subgroup generators.

Authors: We agree that including the explicit equations would improve clarity and verifiability. In the revised manuscript we will write out the full closed system of algebraic equations for the generating functions F_i(t), obtained directly from the transition rules on coset representatives and the finite-state automaton for the Schreier graph. The finite treewidth guarantees that only finitely many states appear, so the system is closed; the constant-term extraction then recovers the cogrowth series by construction. revision: yes
Referee: [§4] §4 (Asymptotic analysis): the claim that the dominant singularity is a branch point of square-root type (hence the series is non-algebraic) rests on the radius of convergence of the algebraic system being strictly less than 1 and on the absence of other singularities on the circle of convergence. The manuscript does not compute the explicit radius or verify the non-interference condition between the coset and Schreier-graph components; a mismatch here would invalidate both the D-finiteness and non-algebraicity conclusions.

Authors: The radius of convergence is shown to be strictly less than 1 by a growth-rate comparison: the finite-treewidth Schreier graph produces a strictly smaller exponential growth rate than the free group on the same generators, which is already known to be 1. The separation into independent coset and graph components ensures that the dominant singularity arises solely from the square-root branch point in the algebraic system for the graph walks; no other singularities lie on the circle of convergence by the analytic properties of the finite-state system. We will add a clarifying paragraph in §4 spelling out this separation argument and the growth-rate bound. An explicit numerical value for the radius is not needed for the proof and would require solving a high-degree polynomial system, but we can note its computability in principle. revision: partial

Circularity Check

0 steps flagged

No circularity: derivation constructs explicit algebraic system from finite-treewidth Schreier graph using standard path-counting techniques.

full rationale

The paper derives the cogrowth series explicitly as the constant term of an algebraic function by separating walks into coset representatives and segments on a Schreier graph of finite treewidth, then building a finite system of generating functions whose solution yields the series. Finite treewidth is an external graph-theoretic property that guarantees finitely many states; the equations are constructed directly from the group presentation and chosen subgroup without fitting parameters to the target series or reducing the result to a self-referential definition. No load-bearing self-citations or imported uniqueness theorems appear in the central argument. The construction provides independent combinatorial content that can be verified against the graph structure.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the domain assumption that finite treewidth of the Schreier graph permits a solvable system of algebraic generating functions whose constant term is the cogrowth series, together with standard closure properties of D-finite functions under the operations used.

axioms (2)

domain assumption Finite treewidth of the chosen Schreier graph allows separation of coset and graph paths into a solvable generating-function system
Invoked to construct the system that yields the constant-term expression for the cogrowth series.
standard math Constant term of an algebraic function is D-finite
Standard fact in combinatorial enumeration used to conclude D-finiteness.

pith-pipeline@v0.9.0 · 5523 in / 1401 out tokens · 80296 ms · 2026-05-14T19:50:50.061621+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

by considering paths in the cosets and the Schreier graph separately, we are able to construct a system of generating functions which count paths
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the Schreier graph has finite tree width

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references

[1]

Scaling limits of permutation classes with a finite specification: A dichotomy

Fr´ ed´ erique Bassino, Mathilde Bouvel, Valentin F´ eray, Lucas Gerin, Micka¨ el Maazoun, and Adeline Pierrot. Scaling limits of permutation classes with a finite specification: A dichotomy. Adv. Math., 405:108513, 2022

2022
[2]

Cogrowth series for free products of finite groups

Jason Bell, Haggai Liu, and Marni Mishna. Cogrowth series for free products of finite groups. Internat. J. Algebra Comput., 33(02):237–260, 2023. 43

2023
[3]

On the complexity of the cogrowth sequence.J

Jason Bell and Marni Mishna. On the complexity of the cogrowth sequence.J. Comb. Algebra, 4(1):73–85, 2020

2020
[4]

Submaps of maps

Edward A Bender, Zhi-Cheng Gao, and L Bruce Richmond. Submaps of maps. I. General 0–1 laws.J. Combin. Theory Ser. B, 55(1):104–117, 1992

1992
[5]

On groups whose cogrowth series is the diagonal of a rational series.Internat

Alex Bishop. On groups whose cogrowth series is the diagonal of a rational series.Internat. J. Algebra Comput., 34(8):1209–1224, 2024

2024
[6]

A virtually nilpotent group whose green series is not D-finite.Internat

Corentin Bodart. A virtually nilpotent group whose green series is not D-finite.Internat. J. Algebra Comput., 0(0):1–11, 0
[7]

Asymptotic laws for random knot diagrams.J

Harrison Chapman. Asymptotic laws for random knot diagrams.J. Phys. A, 50(22):225001, May 2017

2017
[8]

Chomsky and M

N. Chomsky and M. P. Sch¨ utzenberger. The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963

1963
[9]

Joel M. Cohen. Cogrowth and amenability of discrete groups.J. Funct. Anal., 48(3):301–309, 1982

1982
[10]

Finitely generated subgroups of free groups as formal languages and their cogrowth.J

Arman Darbinyan, Rostislav Grigorchuk, and Asif Shaikh. Finitely generated subgroups of free groups as formal languages and their cogrowth.J. Groups Complex. Cryptol., 13(2):Paper No. 1, 30, 2021

2021
[11]

de Bruijn and P

N.G. de Bruijn and P. Erd¨ os. Some linear and some quadratic recursion formulas II.Indag. Math., 55:152–163, 1952

1952
[12]

Systems of functional equations.Random Structures Algorithms, 10(1-2):103– 124, 1997

Michael Drmota. Systems of functional equations.Random Structures Algorithms, 10(1-2):103– 124, 1997

1997
[13]

Math- ematics and Statistics

Michael Drmota.Random Trees: An Interplay between Combinatorics and Probability. Math- ematics and Statistics. Springer Vienna, 2009

2009
[14]

Dunwoody

Martin J. Dunwoody. The accessibility of finitely presented groups.Invent. Math., 81(3):449– 457, 1985

1985
[15]

Janse van Rensburg, and Thomas Wong

Murray Elder, Andrew Rechnitzer, Esaias J. Janse van Rensburg, and Thomas Wong. The cogrowth series for BS(N, N) is D-finite.Internat. J. Algebra Comput., 24(2):171–187, 2014

2014
[16]

On the cogrowth of Thompson’s group F.Groups Complex

Murray Elder, Andrew Rechnitzer, and Thomas Wong. On the cogrowth of Thompson’s group F.Groups Complex. Cryptol., 4(2):301–320, 2012

2012
[17]

Flajolet and R

P. Flajolet and R. Sedgewick.Analytic combinatorics. Cambridge Univ. Press, 2009

2009
[18]

Words in linear groups, random walks, automata and P- recursiveness.J

Scott Garrabrant and Igor Pak. Words in linear groups, random walks, automata and P- recursiveness.J. Comb. Algebra, 1(2):127–144, 2017

2017
[19]

S´ ebastien Gou¨ ezel and Steven P. Lalley. Random walks on co-compact Fuchsian groups.Ann. Sci. ´Ec. Norm. Sup´ er. (4), 46(1):129–173 (2013), 2013

2013
[20]

Local limit theorem for symmetric random walks in Gromov-hyperbolic groups.J

S´ ebastien Gou¨ ezel. Local limit theorem for symmetric random walks in Gromov-hyperbolic groups.J. Amer. Math. Soc., 27(3):893–928, 2014. 44

2014
[21]

Grigorchuk, J.-F

R. Grigorchuk, J.-F. Quint, and A. Shaikh. Multivariate growth and cogrowth.Carpathian Math. Publ., 17(1):82–109, 2025

2025
[22]

R. I. Grigorchuk. Symmetrical random walks on discrete groups. InMulticomponent random systems, volume 6 ofAdv. Probab. Related Topics, pages 285–325. Dekker, New York, 1980

1980
[23]

Hammersley, G.M

J.M. Hammersley, G.M. Torrie, and S.G. Whittington. Self-avoiding walks interacting with a surface.J. Phys. A, 15(2):539, 1982

1982
[24]

Humphries

Stephen P. Humphries. Generalised cogrowth series, random walks, and the group determinant. Math. Proc. Cambridge Philos. Soc., 165(3):445–465, 2018

2018
[25]

R. Jungen. Sur les s´ eries de taylor n’ayant que des singularit´ es alg´ ebrico-logarithmiques sur leur cercle der convergence.Comment. Math. Helv., 3:266–306, 1931

1931
[26]

On the number of self-avoiding walks.J

Harry Kesten. On the number of self-avoiding walks.J. Math. Physics, 4(7):960–969, 07 1963

1963
[27]

On rationality of the cogrowth series.Proc

Dmitri Kouksov. On rationality of the cogrowth series.Proc. Amer. Math. Soc., 126(10):2845– 2847, 1998

1998
[28]

Cogrowth series of free products of finite and free groups.Glasg

Dmitri Kuksov. Cogrowth series of free products of finite and free groups.Glasg. Math. J., 41(1):19–31, 1999

1999
[29]

Lipshitz

L. Lipshitz. The diagonal of aD-finite power series isD-finite.J. Algebra, 113(2):373–378, 1988

1988
[30]

Two notes on Rankin’s book on the modular group.J

Roger Lyndon. Two notes on Rankin’s book on the modular group.J. Aust. Math. Soc., 16(4):454–457, 1973

1973
[31]

Lyndon and Paul E

Roger C. Lyndon and Paul E. Schupp.Combinatorial group theory. Springer-Verlag, Berlin,
[32]

Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89
[33]

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:295–310, 1983

1983
[34]

Algebraic and arithmetic properties of the cogrowth sequence of nilpotent groups, 2022

Igor Pak and David Soukup. Algebraic and arithmetic properties of the cogrowth sequence of nilpotent groups, 2022

2022
[35]

Guttmann

Andrew Elvey Price and Anthony J. Guttmann. Numerical studies of Thompson’s groupF and related groups.Internat. J. Algebra Comput., 29(2):179–243, 2019

2019
[36]

Ross.Stochastic Processes

S.M. Ross.Stochastic Processes. Wiley series in probability and mathematical statistics. Wiley, 1995

1995
[37]

R. P. Stanley. Differentiably finite power series.European J. Combin, 1(2):175–188, 1980

1980
[38]

R. P. Stanley.Enumerative combinatorics. Volume 2, volume 62 ofCambridge Stud. Adv. Math.Cambridge Univ. Press, Cambridge, 1999

1999
[39]

R. P. Stanley.Enumerative combinatorics. Volume 1, volume 49 ofCambridge Stud. Adv. Math.Cambridge Univ. Press, Cambridge, second edition, 2012

2012
[40]

The writhe of a self-avoiding polygon.J

E J Jance van Rensburg, E Orlandini, D W Sumners, M C Tesi, and S G Whittington. The writhe of a self-avoiding polygon.J. Phys. A, 26(19):L981, Oct 1993. 45

1993
[41]

branches

Wolfgang Woess.Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Math. Cambridge Univ. Press, 2000. A Explicit asymptotics for some examples In this appendix, we discuss some explicit asymptotic results for small values of our parameters. A.1B 3 with trefoil knot presentation Consider the following presentation of the trefoil group ⟨c, d|c 3...

2000