Geodesic Languages and Co-Word Problems over Groups

Publication Type:
Issue Date:
Full metadata record
In 1968, Milnor asked if a finitely-generated group could have volume growth that is neither exponential nor polynomial (so-called ‘intermediate’), and if there is an algebraic classification of groups with polynomial volume growth. We consider the analogous questions for geodesic growth. We show that no virtually abelian group can have intermediate geodesic growth. In particular, we completely characterise the geodesic growth for every virtually abelian group. We show that the geodesic growth is either polynomial of an integer degree with rational geodesic growth series, or exponential with holonomic geodesic growth series. In addition, we show that the language of geodesics is blind multicounter. These results hold for each finite weighted monoid generating set of any virtually abelian group. A direct consequence of Gromov’s classification of polynomial volume growth is that if a group has polynomial geodesic growth with respect to some finite generating set, then it is virtually nilpotent. Until now, the only known examples with polynomial geodesic growth were all virtually abelian. We furnish the first example of a virtually 2-step nilpotent group having polynomial geodesic growth with respect to a certain finite generating set. Holt and Röver proved that finitely-generated bounded automata groups have indexed co-word problems. We sharpen this result to show that their co-word problem is ET0L. We do so using an equivalent machine model known as a cspd automaton. This extends a result of Ciobanu, Elder and Ferov who showed this for the first Grigorchuk group by explicitly constructing an ET0L grammar.
Please use this identifier to cite or link to this item: