Papers
In this note, we provide examples of groups with transcendental spectral radius. We provide two constructions:
The first one provides finitely presented examples, and relies on links between decidability of the Word Problem and semi-computability of the spectral radius.
The second provides examples with decidable Word Problem, and relies on small-cancellation and the Rapid Decay property.
The Identity Problem in virtually solvable matrix groups over algebraic numbers, joint w/ Ruiwen Dong, arXiv link
The Tits alternative states that a finitely generated matrix group either contains a nonabelian free subgroup , or it is virtually solvable. This paper considers two decision problems in virtually solvable matrix groups: the Identity Problem (does a given finitely generated subsemigroup contain the identity matrix?), and the Group Problem (is a given finitely generated subsemigroup a group?). We show that both problems are decidable in virtually solvable matrix groups over the field of algebraic numbers. Our proof extends the decidability result for nilpotent groups by Bodart, Ciobanu, Metcalfe and Shaffrir, and for metabelian groups by Dong (STOC'24). Since the Identity Problem and the Group Problem are known to be undecidable in matrix groups containing F2×F2, our result significantly reduces the decidability gap for both decision problems.
We study both the Submonoid Membership problem (SMP) and the Rational Subset Membership problem (RSMP) in finitely generated nilpotent groups. We give two reductions with important applications:
The SMP in any nilpotent group can be reduced to the RSMP in smaller groups. As a corollary, we prove the existence of a group with decidable SMP and undecidable RSMP, answering a question of Lohrey and Steinberg.
The Rational Subset Membership problem in H_3(Z) can be reduced to the Knapsack problem in the same group, and is therefore decidable.
Combining both results, we deduce that the filiform 3-step nilpotent group has decidable Submonoid Membership.
We give a criterion on pairs (G,S) - where G is a virtually s-step nilpotent group and S is a finite generating set - saying whether the geodesic growth is exponential or strictly sub-exponential. Whenever s=1,2, this goes further and we prove the geodesic growth is either exponential or polynomial. For s≥3 however, intermediate growth is possible. We provide an example of virtually 3-step nilpotent group with geodesic growth asymptotic to exp(n^{3/5} log(n)). This is the first known example of group with intermediate geodesic growth. Along the way, we prove results on the geometry of virtually nilpotent groups of independent interest, including asymptotics with error terms for their volume growth.
Dead ends and rationality of complete growth series, joint w/ Pierre Bagnoud, latest version, arXiv link
We are interested in the NG-rationality and NG-algebraicity of the complete growth series of finitely generated groups. It is shown that dead ends of arbitrarily large depths form an obstruction to NG-rationality. In the case of the 3-dimensional Heisenberg group H_3(Z), we prove that the complete series is not NG-algebraic for any generating set. Dead ends are also used to show that complete growth series of higher Heisenberg groups are not NG-rational for specific generating sets. Using a more general version of this obstruction, we prove that complete growth series of some lamplighter groups are not NG-rational either. This work provides the first examples of groups exhibiting a difference between rationality of standard growth series, and rationality of complete growth series.
We provide new examples of groups without rational cross-sections (also called regular normal forms), using connections with bounded generation and rational orders on groups. Our examples contain a finitely presented HNN extension of the first Grigorchuk group. This last group is the first example of finitely presented group with solvable word problem and without rational cross-sections. It is also not autostackable, and has no left-regular complete rewriting system.