On the complexity of the cogrowth sequence (Q2181189)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7201622
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of the cogrowth sequence |
scientific article; zbMATH DE number 7201622 |
Statements
On the complexity of the cogrowth sequence (English)
0 references
18 May 2020
0 references
Summary: Given a finitely generated group with generating set \(S\), we study the cogrowth sequence, which is the number of words of length \(n\) over the alphabet \(S\) that are equal to one. This is related to the probability of return for walks in a Cayley graph with steps from \(S\). We prove that the cogrowth sequence is not \(P\)-recursive when \(G\) is an amenable group of superpolynomial growth, answering a question of \textit{S. Garrabrant} and \textit{I. Pak} [J. Comb. Algebra 1, No. 2, 127--144 (2017; Zbl 1422.20009)].
0 references
cogrowth
0 references
\(D\)-finite power series
0 references
amenability
0 references
\(P\)-recursive sequences
0 references
0 references
0.8528472185134888
0 references
0.8463875651359558
0 references
0.8004894852638245
0 references
0.7997329235076904
0 references
0.7766173481941223
0 references
