arXiv:1608.06703v2 [math.GR] 3 Nov 2016

SUB-DOMINANT COGROWTH BEHAVIOUR AND
THE VIABILITY OF DECIDING AMENABILITY
NUMERICALLY
MURRAY ELDER AND CAMERON ROGERS
Abstract. We critically analyse a recent numerical method due
to the first author, Rechnitzer and van Rensburg, which attempts
to detect amenability or non-amenability in a finitely generated
group by numerically estimating its asymptotic cogrowth rate. We
identify two potential sources of error. We then propose a modification of the method that enables it to easily compute surprisingly
accurate estimates for initial terms of the cogrowth sequence.

1. Introduction
Researchers studying the amenability Thompson’s group F will be
familiar with a distrust of experimental methods applied to this problem. Part of this scepticism stems from the fact that (if it is amenable)
F is known to have a very quickly growing Følner function [22]. However, experimental algorithms investigating amenability are rarely based
on Følner’s criteria directly, and to date no identification is made in the
literature of a mechanism by which a quickly growing Følner function
could interfere with a given experimental method.
In this paper we identify such a mechanism for a recent algorithm
proposed by first author, A. Rechnitzer, and E. J. Janse van Rensburg
[9], which was designed to experimentally detect amenability via the
Grigorchuk-Cohen characterisation in terms of the cogrowth function.
We will refer to this as the ERR algorithm in the sequel.
We show that, in the ERR algorithm, estimates of the asymptotic
cogrowth rate are compromised by sub-dominant behaviour in the
reduced-cogrowth function.
Date: March 28, 2018.
2010 Mathematics Subject Classification. 20F69, 20F65, 05A15, 60J20.
Key words and phrases. amenable group; cogrowth function; Følner function;
Kesten’s criterion; return probability; Metropolis algorithm; R. Thompson’s group
F.
Research supported by Australian Research Council grant FT110100178.
1

However, even though sub-dominant behaviour in the cogrowth function may interfere with estimates of the asymptotic growth rate, the
ERR algorithm can still be used to estimate other properties of the
cogrowth function to high levels of accuracy. In particular we are
able re-purpose the algorithm to quickly estimate initial values of the
cogrowth function even for groups for which the determination of the
asymptotic growth rate is not possible (for example groups with unsolvable word problem).
The present work started out as an independent verification by the
second author of the experimental results in [9], as part of his PhD
research. More details can be found in [27].
The article is organised as follows. In Section 2 we give the necessary
background on amenability, random walks and cogrowth, followed by
a summary of previous experimental work on the amenability of F . In
Section 3 a function quantifying the sub-dominant properties of the
reduced-cogrowth function is defined. In Section 4 the ERR algorithm
is summarised, followed by an analysis of two types of pathological
behaviour in Section 5. The first of these is easily handled, while
the second is shown to depend on sub-dominant terms in the reducedcogrowth function. In Section 6 the ERR method is modified to provide
estimates of initial cogrowth values. Using this the first 2000 terms for
the cogrowth function of Thompson’s group F are estimated.
2. Preliminaries
We begin with a definition of terms and a quick survey of experimental work done on estimating amenability.
2.1. Characterisations of amenability. The following characterisation of amenability is due to Grigorchuk [15] and Cohen [8]. A shorter
proof of the equivalence of this criteria with amenability was provided
by Szwarc [28].
Definition 2.1. Let G be a finitely generated non-free group with
symmetric generating set S. Let cn denote the number of freely reduced
words of length n over S which are equal to the identity in G. Then G
is amenable if and only if
lim sup c1/n
= |S| − 1.
n
n→∞

Equivalently, let dn denote the number of words (reduced and unreduced) of length n over S which are equal to the identity. Then G is
2

amenable if and only if
lim sup d1/n
= |S|.
n
n→∞

The function n 7→ cn is called the reduced-cogrowth function for G
with respect to S, and n 7→ dn the cogrowth function.
Kesten’s criteria for amenability is given in terms of the probability
of a random walk on the group returning to its starting point.
Definition 2.2. Let G be a finitely generated group, and let µ be a
symmetric measure on G. The random walk motivated by µ is a Markov
chain on the group starting at the identity where the probability of
moving from x to y is µ(x−1 y). Note the distribution after n steps is
given by the n-fold convolution power of µ, which we denote as µn .
That is, µn (g) is the probability that an n-step walk starting at e ends
at g. By Kesten’s criteria [18] a group is amenable if and only if
lim sup(µn (e))1/n = 1.
n→∞

Pittet and Saloff-Coste proved that the asymptotic decay rate of the
probability of return function is independent of measure chosen, up to
the usual equivalence [24]. For finitely generated groups we can choose
the random walk motivated by the uniform probability measure on a
finite generating set. This random walk is called a simple random walk
and corresponds exactly with a random walk on the Cayley graph. For
this measure the probability of return is given by
dn
(1)
µn (e) =
,
|S|n
where the (reduced and non-reduced) cogrowth terms dn are calculated
with respect to the support of the measure. Thus the cogrowth function
arises from a special case of return probabilities.
Følner’s characterisation of amenability [13] can be phrased in several
ways. Here we give the definition for finitely generated groups.
Definition 2.3. Let G be a group with finite generating set S. For
each finite subset F ⊆ G, we denote by |F | the number of elements in
F . The boundary of a finite set F is defined to be
∂F = {g ∈ G : g ∈
/ F, gs ∈ F for some s ∈ S}.

A finitely generated group G is amenable if and only if there exists a
sequence of finite subsets Fn such that
|∂Fn |
= 0.
lim
n→∞ |Fn |
3

Vershik [29] defined the following function as a way to quantify how
much of the Cayley graph must be considered before sets with a given
isoperimetric profile can be found.
Definition 2.4. The Følner function of a group is


|∂F |
1
f (n) = min |F | :
<
.
|F |
n
Significant literature exists on Følner functions. It is known that
there exists finitely presented amenable groups with Følner functions
n
growing faster than nn ([20] Corollary 6.3) and finitely generated
groups (iterated wreath product of k copies of Z) with Følner functions growing faster than n

n.

..

of height k for arbitrary k [11].

2.2. Experimental work on the amenability of F . Richard Thompson’s group F is the group with presentation
(2)

ha, b | [ab−1 , a−1 ba], [ab−1 , a−2 ba2 ]i

where [x, y] = xyx−1 y −1 denotes the commutator of two elements. See
for example [6] for a more detailed introduction to this group.
Whether or not F is amenable has attracted a large amount of interest, and has so far evaded many different attempts at a proof of both
positive and negative answers.
The following is a short summary of experimental work previously
done on Thompson’s group F .
[5] Burillo, Cleary and Wiest 2007. The authors randomly choose
words and reduce them to a normal form to test if they represent
the identity element. From this they estimate the proportion
of words of length n equal to the identity, as a way to compute
the asymptotic growth rate of the cogrowth function.
[1] Arzhantseva, Guba, Lustig, and Préaux 2008. The authors
study the density or least upper bound for the average vertex degree of any finite subgraph of the Cayley graph; an mgenerated group is amenable if and only if the density of the
corresponding Cayley graph is 2m (considering inverse edges as
distinct). A computer program is run and data is collected on a
range of amenable and non-amenable groups. They find a finite
subset in F with density 2.89577 with respect to the 2 generator
presentation above. (To be amenable one would need to find
sets whose density approaches 4). Subsequent theoretical work
of Belk and Brown gives sets with density approaching 3.5 [2].
4

[10] Elder, Rechnitzer and Wong 2012. Lower bounds on the cogrowth
rates of various groups are obtained by computing the dominant
eigenvalue of the adjacency matrix of truncated Cayley graphs.
These bounds are extrapolated to estimate the cogrowth rate.
As a byproduct the first 22 coefficients of the cogrowth series
are computed exactly.
[17] Haagerup, Haagerup, and Ramirez-Solano 2015. Precise lower
bounds of certain norms of elements in the group ring of F are
computed, and coefficients of the first 48 terms of the cogrowth
series are computed exactly.
[9] Elder, Rechnitzer and van Rensburg 2015. The Metropolis
Monte Carlo method from statistical mechanics is adapted to
estimate the asymptotic growth rate of the cogrowth function
by running random walks on the set of all trivial words in a
group. The results obtained for Thompson’s group F suggest it
to be non-amenable. We describe their method in more detail
in Section 4 below.
Justin Moore [22] (2013) has shown that if F were amenable then
its Følner function would increase faster than a tower of n − 1 twos,
22

..

.

2

This result has been proposed as an obstruction to all computational
methods for approximating amenability; a computationally infeasibly
large portion of the Cayley graph must be considered before sets with
small boundaries can be found. However, in all but one of the experimental algorithms listed above computing Følner sets was not the
principle aim. In order to understand how a bad Følner function affects the performance of these methods, we need to understand the
connection between convergence properties of the respective limits in
the various characterisations of amenability.
3. Quantifying sub-dominant cogrowth behaviour
The Følner function quantifies the rate of convergence of the limit
in Definition 2.3. We consider the following definitions as an attempt
to quantify the rate of convergence of the limits in Definition 2.1.
Definition 3.1. Let G be a finitely generated group with symmetric
generating set S. Let cn be the number of all reduced trivial words of
1/n
length n and let C = lim sup cn . Define


c2k+2
1
2
>C −
R(n) = min k :
c2k
n
5

Definition 3.1 uses only even word lengths (and hence C 2 instead
of C). This is necessary because group presentations with only even
length relators have no odd length trivial words. For this paper we
will only consider the function R for amenable groups, in which case
C = |S| − 1 except when the group is free (infinite cyclic).
A similar definition may be made for the cogrowth function.
Definition 3.2. For G a finitely generated group with symmetric generating set S we may define


d2k+2
1
0
2
R (n) = min k :
>D −
d2k
n
where dn be the number of all (reduced and non-reduced) trivial words
1/n
of length n and D = lim sup cn .
Literature already exists studying the convergence properties of return probabilities, and we suspect that the function R0 is a reformulation of the L2 -isoperimetric function [3].
Example 3.3. For the trivial group with some finite symmetric generating set S we have c0 = 1, ck = |S|(|S| − 1)k−1 for k ≥ 1 so
c2k+2
≥ (|S| − 1)2 and R(n) = 0. Similarly since dk = |S|k we have
c2k
R(n) = R0 (n) = 0.
Aside from the trivial group, it is usually easier to compute R0 (or its
asymptotics) than it is to obtain R. For this reason we first consider R0
functions for various groups, and then prove that for infinite, amenable,
non-free groups R0 and R have the same asymptotic behaviour.
Example 3.4. For any finite group the rate of growth of dn is the
dominant eigenvalue of the adjacency matrix of the Cayley graph, and
some simple analysis shows that R0 (n) is at most logarithmic in n.
Define f - g if there exist constants a, b > 0, such that for x large
enough, f (x) ≤ ag(bx). Then f ∼ g (f and g are asymptotic) if f - g
and g - f .
Table 1 provides a sample of amenable groups for which the asymptotics of R0 (n), the Følner function and probabilities of return are
known [11, 25, 26].
The results for the asymptotics of R0 (n) were derived directly from
the known asymptotics for µn . A discussion of these methods will
appear in [27]. In practice however it proved quicker to guess the
asymptotics and then refine using the following method.
Proposition 3.5. The asymptotic results for R0 (n) in Table 1 are
correct.
6

Example

F(n)

µn (e)

R0 (n)

trivial

∼ constant

∼ constant

∼ constant

Zk

∼ nk

∼ n−k/2

∼n

BS(1, N )

∼ en

∼ e−n

ZoZ

nn

Z o Z o ··· o Z
(d − 1)-fold
wreath
product

nn

..

1/3

∼ n3/2

1/3 (ln n)2/3

∼ ln(n)n3/2

∼ e−n

n
.

∼ e−n

n
(tower
of d − 1 n’s)

d
2
d+2 (ln n) d+2

∼ ln(n)n(d+2)/2

Table 1. Comparing asymptotics of the probabilities of
return, the Følner function F, and R0 for various groups.

Proof. For a given group suppose µn (e) ∼ g(n) where g is a continuous
real valued function, as in Table 1. Then dn ∼ |S|n g(n).
Finding R0 (n) requires solving the equation
d2k+2
1
(3)
= |S|2 −
d2k
n
for k = k(n). This is equivalent to solving


d2k+2
2
1 = n |S| −
d2k
for k.
Suppose f (n) is a function where


d2f (n)+2
2
(4)
L = lim n |S| −
n→∞
d2f (n)
exists and is non-zero.
If L = 1 then


d2f (n)+2
1
2
|S| −
∼
d2f (n)
n
7

and so

d2f (n)+2
1
∼ |S|2 − .
d2f (n)
n
Then k(n) ∼ f (n) satisfies Equation 3. Therefore R0 (n) is asymptotic
to f (n).
If L exists and is non-zero then


d2f (n)+2
L
2
|S| −
∼ .
d2f (n)
n

Then


d2f (Ln)+2
L
1
∼
=
|S| −
d2f (Ln)
Ln
n
0
and so R (n) ∼ f (Ln).
The derivations of candidates for f (n) in each case in Table 1 is
performed in [27]. The results in the table do not include the constant
L since the probabilities of return used as input are only correct up
to scaling. We leave the calculation of Equation 4 for the results from
Table 1 as an exercise.



2

3.1. Converting from cogrowth to reduced-cogrowth. We now
prove an equivalence between the sub-dominant behaviour of the cogrowth
and reduced-cogrowth functions. This allows us to borrow the previously listed results for R0 when discussing R and the ERR method.
The dominant and sub-dominant cogrowth behaviour can be analysed
from the generating functions for these sequences.
Definition 3.6. Let dn denote the number of trivial words of length
n in a finitely generated group. The cogrowth series is defined to be
∞
X
D(z) =
dn z n .
n=0

Let cn denote the number of reduced trivial words. Then
∞
X
C(z) =
cn z n
n=0

is said to be the reduced-cogrowth series.
D and C are the generating functions for dn and cn respectively, and
are related in the following way. Let |S| = 2p be the size of a symmetric
generating set. Then from [19, 30]


1 − z2
z
D
(5)
C(z) =
1 + (2p − 1)z 2
1 + (2p − 1)z 2
8

and
p
1 − p + p 1 − 4(2p − 1)z 2
(6) D(z) =
C
1 − 4p2 z 2

1−

!
p
1 − 4(2p − 1)z 2
.
2(2p − 1)z

The dominant and sub-dominant growth properties of the cogrowth
functions may be analysed by considering the singularities of these
generating functions. For a detailed study of the relationship between
singularities of generating functions and sub-dominant behaviours of
coefficients see [12].
We now outline an example of how the composition of functions
(as in Equations 5 and 6) effects the growth properties of the series
coefficients.
Example 3.7. Consider

z −p
f (z) = 1 −
.
r
Then (for positive p) f (z) has a singularity at z = r, and this defines
the radius of convergence of f (z) and the asymptotic growth rate of the
series coefficients of the expansion of f (z). It also determines the principle sub-dominant term contributing to the growth of the coefficients.
In this example, the coefficients will grow like np−1 r−n .
We wish to investigate what happens to this growth behaviour when
we compose the function f with a function g. Consider f (g(z)) for some
function g for which g(0) = 0. The singularities of g are inherited by
f (g(z)); if g is analytic everywhere then the only singularities of f (g(z))
will occur when g(z) = r. In this case, the new radius of convergence
will be the minimum |z| such that g(z) = r. Importantly, however,
the principle sub-dominant growth term of the series coefficients will
remain polynomial of degree p − 1.
A variation on this behaviour will occur if there is an r0 for which
g(z) is analytic on the ball of radius r0 , and g(z) = r for some z in
this region. Again, when this occurs, the new radius of convergence is
obtained by solving g(z) = r and the type of the principle sub-dominant
term in the growth of the coefficients remains unchanged.
If there does not exist such an r0 , the principle singularity of g(z)
will dominate the growth properties of the coefficients.
Proposition 3.8. Let G be an infinite amenable group generated by
p elements and their inverses. Then the principle sub-dominant terms
contributing to the growth of dn and cn are asymptotically equivalent,
except when the group is infinite cyclic.
9

Proof. For an amenable group generated by p elements and their inverses the radius of convergence for D(z) is exactly 1/2p. This follows
immediately from Definition 2.1.
Now from Equation 5, the reduced-cogrowth series is obtained by
composing the cogrowth series with
z
p(z) =
1 + (2p − 1)z 2
and then multiplying by
1 − z2
.
q(z) =
1 + (2p − 1)z 2
√
Both of these functions are analytic inside the ball of radius 1/ 2p − 1.
Now


1
1
= ,
(7)
p
2p − 1
2p
the singularity of D(z). Hence, 1/(2p − 1) is a singularity of D(p(z)),
and hence of C(z). Note
√ that if the group is infinite cyclic, then p = 1
and 1/(2p − 1) and 1/ 2p − 1 are equal. In this scenario the radius of
convergence of p(z) is reached at the same moment that p(z) reaches the
radius of convergence of D(z). This means that both p and q contribute
to the principle singularity, and this explains why the reduced and nonreduced cogrowth functions for the infinite cyclic group exhibit such
different behaviour.
√
If p > 1 then 1/(2p − 1) is inside the ball of radius 1/ 2p − 1 (ie,
inside the region of convergence for p and q). Thus, the singularity of
D is reached before z approaches the singularity of p and q.
In this case the substitutions in Equation 5 change the location of
the principle singularity, but do not change the type of the singularity,
or the form of the principle sub-dominant term contributing to the
growth of the series coefficients.


Corollary 3.9. Suppose G is a finitely generated, infinite amenable
group that is not the infinite cyclic group. Then R is asymptotically
equivalent to R0 .
Remark 3.10. An alternate proof of the Grigorchuk/Cohen characterisation of amenability is easily constructed from an analysis of the
singularities of C(z) and D(z). For example, Equation 7 proves the
first result from Definition 2.1. This argument also picks up that
the infinite cyclic group presents a special case. Though amenable,
lim supn→∞ cn 6= |S| − 1. For this group we have R(n) ∼ 0 while
R0 (n) ∼ n.
10

3.2. Sub-dominant behaviour in the cogrowth of F . The groups
BS(1, N ) limit to Z o Z in the space of marked groups. This implies
that the growth of the function R0 and hence R for BS(1, N ) increases
with N . This is consistent with Table 1, since these results do not
include scaling constants. This leads to the following result.
Proposition 3.11. If Thompson’s group F is amenable, its R function
grows faster than the R function for any BS(1, N ). In particular, it is
asymptotically super-polynomial.
Proof. By the convergence of BS(1, N ) to Z o Z in the space of marked
groups we have that, for any N , the function R0 for BS(1, N ) grows
slower than the corresponding function for Z o Z. In [24] it is proved
that, for finitely generated groups, the probability of return cannot
asymptotically exceed the probability of return of any finitely generated
subgroup. This implies that, for finitely generated amenable groups,
the R0 function of the group must grow faster than the R0 function
of any finitely generated subgroup. Since there is a subgroup of F
isomorphic to Z o Z, R0 (n) for F must grow faster than R0 (n) for Z o Z
and hence BS(1, N ).
Since F contains every finite depth iterated wreath products of Z
([16] Corollary 20), the probability of return for F decays faster than
e−n

d
2
d+2 (ln n) d+2

for any d. Taking the limit as d approaches infinity of the corresponding
values for R0 and then doing the conversion from R0 to R gives the final
result.

Note that if F is non-amenable, then even though it still contains
these subgroups, they do not affect the R0 function. In this scenario
it is still true that the return probability for F decays faster than the
interated wreath product, because F would have exponentially decaying return probability. For non-amenable groups the return probability
does not identify the principle sub-dominant term in dn , and hence does
not correlate directly with R0 .
4. The ERR algorithm
We start by summarising the original work by the first author, Rechnitzer and van Rensburg. Only the details directly pertinent to the
present paper are discussed here, for a more detailed analysis of the
random walk algorithm and a derivation of the stationary distribution
we refer the reader to [9]. For the sake of brevity the random walk
11

performed by the algorithm will be referred to as the ERR random
walk.
Recall that a group presentation, denoted hS | Ri, consists of a set
S of formal symbols (the generators) and a set R of words written in
S ±1 (the relators) and corresponds to the quotient of the free group
on S by the normal closure of the relators R. In our paper, as in
[9], all groups will be finitely presented: both S and R will be finite.
Furthermore, the implementation of the algorithm assumes both S and
R to be symmetric, that is, S = S −1 and R = R−1 . In addition,
for convenience R is enlarged to be closed under cyclic permutation.
Recall that cn counts the number of reduced words in S of length n
which represent the identity in the group (that is, belong to the normal
closure of R in the free group).

4.1. The ERR random walk. The ERR random walk is not a random walk on the Cayley graph of a group, but instead a random walk
on the set of trivial words for the group presentation. This makes the
algorithm extremely easy to implement, since it does not require an
easily computable normal form or even a solution to the word problem. The walk begins at the empty word, and constructs new trivial
words from the current trivial word using one of two moves:
• (conjugation by x ∈ S). In this move an element is chosen from
S according to a predetermined probability distribution. The
current word is conjugated by the chosen generator and then
freely reduced to produce the new candidate word.
• (insertion of a relator). In this move a relator is chosen from
R according to a predetermined distribution and inserted into
the current word at a position chosen uniformly at random . In
order to maintain the detailed balance criteria (from which the
stationary distribution is derived) it is necessary to allow only
those insertions which can be immediately reversed by inserting
the inverse of the relator at the same position. To this end the a
notion of left insertion is introduced; after relators are inserted
free reduction is done on only the left hand side of the relator.
If after this the word is not freely reduced the move is rejected.
Transition probabilities are defined which determine whether or not
the trivial word created with these moves is accepted as the new state.
These probabilities involve parameters α ∈ R and β ∈ (0, 1) which may
be adjusted to control the distribution of the walk.
Let the current word be w and the candidate word be w0 .
12

• If w0 was obtained from w via a conjugation it is accepted as
the new current state with probability
( 
)
1+α
|w0 | + 1
0
min 1,
β |w |−|w| .
|w| + 1

• If w0 was obtained from w via an insertion it is accepted as the
new state with probability

  0
α
|w | + 1
|w0 |−|w|
.
min 1,
β
|w| + 1
If w0 is not accepted the new state remains as w.
These probabilities are chosen so that the distribution on the set of
all trivial words given by
(|u| + 1)1+α β |u|
,
Z
(where Z is a normalizing constant) can be proved to be the unique stationary distribution of the Markov chain, and the limiting distribution
of the random walk.
The following result is then given.
π (u) =

Proposition 4.1 ([9]). As β approaches
1
βc =
lim supn→∞ (cn )1/n
the expected value of the word lengths visited approaches infinity.
This result leads to the following method for estimating the value of
βc . For each presentation, random walks are run with different values
of β. Average word length is plotted against β. The results obtained
for Thompson’s group F are reproduced in Figure 1. The values for β
at which the data points diverge gives an indication of βc , and hence
the amenability or otherwise of the group.
Random walks were run on presentations for a selection of amenable
and non-amenable groups, including Baumslag-Solitar groups, some
free product examples whose cogrowth series are known [21], the genus
2 hyperbolic surface group, a finitely presented group related to the
basilica group, and Thompson’s group F .
The data in Figure 1 appears to show fairly convincingly that the
location of βc is a long way from the value of 31 expected were the group
amenable.
It is noted in [9] that a long random walk may be split into shorter
segments, and the variation in average word lengths of the segments
gives an estimation of the error in the estimated expected word length.
13

60

hni

40

20

0
0.25

0.3

0.35

0.4

β

Figure 1. The results from [9] of the ERR algorithm
applied to the standard presentation of Thompson’s
group F . Each data point plots the average word length
of an ERR random walk against the paramater β used.
Remark 4.2. In the original work reported in [9], the algorithm was
coded in c++, words were stored as linked lists, the GNU Scientific
Library was used to generate pseudo-random numbers, and parallel
tempering was used to speed up the convergence of the random walk.
For independent verification the second author coded the algorithm in
python, kept words as strings, used the python package random, and
no tempering was used. Results obtained were consistent with those
in [9]. The experimental analysis and modifications described in this
paper use the python version of the second author.
5. Investigating Pathological Behaviour
The theory underpinning the ERR random walk is complete — the
random walk is certain to converge to the stationary distribution. This
does not preclude, however, convergence happening at a computationally indetectible rate. Since there are finitely presented groups with
unsolvable word problem, there is no chance of deriving bounds on
the rates of convergence of the walk in any generality. In the process
of independently verifying the results in [9], however, we were able to
identify two properties of group presentations which appear to slow the
rate of convergence. The first of these is unconnected with the Følner
14

function, and does not pose any problem to the implementation of the
ERR algorithm to Thompson’s group F . It does, however, refute the
claim in ([9] Section 3.7) that the method can be successfully applied
to infinite presentations.
5.1. Walking on the wrong group. It is easy to see from the probabilistic selection criteria used by the ERR random walk that moves
which increase the word length by a large amount are rejected with high
probability. This poses a problem for group presentations containing
long relators since insertion moves that attempt to insert a long relator
will be accepted much less often than moves which attempt to insert a
shorter relation.
The following example makes this explicit.
Lemma 5.1. All presentations of the form
a, b | abab−1 a−1 b−1 , an b−n−1

describe the trivial group.

Proof. Since an = bn+1 we have an ba = bn+1 ba = bbn+1 a = ban+1
babn+1 .
Since aba = bab we have ai ba = ai−1 bab so an ba = an−1 bab
n−2
a bab2 = · · · = babn .
Putting these results together gives babn = babn+1 and hence b
trivial. The result follows.

=
=
is


By increasing n we can make the second relator arbitrarily large
without affecting the group represented by the presentation, or the
group elements represented by the generators. This implies that ERR
random walks for each of these presentations should converge to the
same stationary distribution.
Changing the presentation, however, does change the number of steps
in the ERR random walk needed to reach certain trivial words (such
as the word ‘a’).
ERR random walks were performed on these presentations for n =
1, 2, . . . , 19. As well as recording the average word length of words
visited, the number of accepted insertions of each relator was recorded.
Table 2 shows the sharp decline in the number of accepted insertions of the second relator as n increases. Indeed, for n > 14 there
were no instances in which the longer relator was successfully inserted.
Unsurprisingly, walks for large n did not converge to the same distribution as those where n was small, and for large n the data did not
accurately predict the asymptotic growth rate of the cogrowth function. For these n the ERR random walk was actually taking place
15

n

number of
steps

number of
number of
accepted
accepted
insertions of
insertions for
small relator
big relator
8
1
2.0 × 10
2977228
7022772
2
3.6 × 108
4420185
5579815
8
3
6.1 × 10
6323376
3676624
4
9.0 × 108
8016495
1983505
9
5
1.2 × 10
9088706
911294
9
6
1.4 × 10
9621402
378598
7
1.5 × 109
9850251
149749
9
8
1.7 × 10
9943619
56381
9
1.8 × 109
9977803
22197
9
10
1.9 × 10
9991680
8320
9
11
2.1 × 10
9997122
2878
12
2.2 × 109
9998720
1280
9
13
2.2 × 10
9999585
415
14
2.3 × 109
9999938
62
9
15
2.4 × 10
10000000
0
9
16
2.6 × 10
10000000
0
17
2.7 × 109
10000000
0
9
18
2.8 × 10
10000000
0
19
2.9 × 109
10000000
0
Table 2. The ERR algorithm applied to the trivial
group with presentation ha, b | aba = bab, an = bn+1 i for
various n. As n increases, the longer relator is successfully inserted less frequently.

on ha, b | abab−1 a−1 b−1 i, which is a presentation for the 3-stand braid
group, which is non-amenable.
Note that, given enough time, the longer relator would be successfully sampled, and that an infinite random walk is still guaranteed to
converge to the theoretical distribution for the trivial group. Such convergence, however, may take a computationally infeasible amount of
time.
Claim 5.2. The presence of long relators in the input presentation
slows the rate at which an ERR random walk converges to the stationary
distribution. Therefore, the ERR method cannot be reliably extended to
accept infinite presentations.
16

This result is not surprising. In [4] an infinitely presented amenable
group is given for which any truncated presentation (removing all but
a finite number of relators) is non-amenable. The ERR method could
not expect to succeed on this group even if long relators were sampled
often; since the ERR random walk can only be run for a finite time there
can never be a representative sampling of an infinite set of relators, so
ERR would incorrectly conclude this group is non-amenable.
The pathological presentations of the trivial group studied here form
a sequence of presentations for amenable (trivial) groups which approach a non-amenable group in the space of marked groups. The failure of the ERR method to predict amenability for these groups suggests
that one does not need particularly elaborate or large presentations to
produce pathological behaviour.
However, we remark that this behaviour is easily monitored. In addition to counting the number of attempted moves of the walk, one
should record the relative number of successful insertions of each relator. In the case of Thompson’s group F the two relators have similar
lengths, and in our experiments both were sampled with comparable
frequency.
Further analysis of this phenomena appears [27].
5.2. Sub-dominant behaviour in cogrowth. Recall that the solvable Baumslag-Solitar groups BS(1, n) = ha, t | tat−1 a−n i are the only
two generator, single-relator, amenable groups [7]; for each of these
groups βc = 1/3. In [9] walks were run on BS(1, 1) = Z2 , BS(1, 2)
and BS(1, 3) and for these groups the random walk behaved as predicted with divergence occurring at the moment when β exceeded βc .
It may be surprising then to see the output of some ERR walks run
BS(1, 7) shown in Figure 2.
It is clear that, for this group, the divergence for β > βc predicted
by the theory is not occurring. This is further seen in Figure 3, which
shows the progression over time of one of the random walks used to
generate Figure 2. The results in Figure 3 show the word lengths visited
for ten ERR random walks (superimposed) performed on BS(1, 7),
with α = 3 and β = 0.34. Since the group has only a single relator,
which was successfully inserted into the word 10000 times, it is not
an error of the type identified in Subsection 5.1. The ERR method
relies on the divergence of the average word length to identify βc , so
application of the method in this case will not accurately identify the
amenability of BS(1, 7).
Divergence of the ERR random walk (when β > βc ) relies on the
abundance of long trivial words. For most presentations, at all points
17

<n>

80

x
60

x

40

x
x

20

x
x

x

x

x

x

x

x

x

x

x

x
x

x

0.30

x

x

0.31

x

x

0.32

x

x

0.33

x

x
0.34

x

x
0.35

x
0.36

β

Figure 2. A graph (as in [9]), of average word length
of ERR random walks plotted against the parameter β.
The orange points come from walks where α = 3, and the
blue points come from walks where α = 0. The vertical
line at 1/3 marks the expected asymptote.
in an ERR walk there are always more moves which lengthen the word
than shorten it, but the probabilistic selection criteria ensures balance.
More specifically, the parameter β imposes a probabilistic barrier which
increases exponentially with attempted increase in word length. When
β > βc this exponential cap is insufficient, and the word length diverges.
Recall that for a given word length n the function R(n) quantifies
how many reduced-trivial words there are of length similar to n. The
results in Table 1 imply that, for many groups, large word lengths
must be reached before the asymptotic growth rate is reflected by a
local abundance of longer trivial words. We have noted in Section 3.2
that the convergence properties of BS(1, N ) in the space of marked
groups requires R(n) to grow more quickly as N increases. We now
show that the growth rate of R(n) is sufficient to cause the pathological
behaviour noted above.
To this end we postulate a hypothetical cogrowth function for which
we can explicitly identify and control R(n).
Example 5.3. Suppose that for some group on two generators and
q > 0, p ∈ (0, 1), the reduced-cogrowth is known to be exactly
p

cn = 3n−qn .
18

Word Length

150

100

50

1 × 1011

2 × 1011

3 × 1011

4 × 1011

5 × 1011

6 × 1011

7 × 1011

Number of Steps

Figure 3. The distribution of ERR random walks on
BS(1, 7) with α = 3 and β = 0.34. This is a plot of word
length against number of steps taken. The data represents ten ERR random walks overlaid on top of each
other. As can be seen, none of the walks diverged. Each
dot represents the average word length over 10000 accepted relator insertions. There is no divergence at this
β value, even though the group is amenable.
1/n

Then lim supn→∞ cn = 3 and so the group is amenable. It may easily
be verfied by the methods outlined in Proposition 3.5 that
1

R(n) = (9 log(3)qp2p n) 1−p .
1
Note that as p approaches 1, the exponent 1−p
approaches infinity. This
increases both the degree of the polynomial in n, and the coefficient
1
(9 log(3)qp2p ) 1−p .
Even though we do not know a group presentation with precisely
this cogrowth function, by varying p and q this hypothetical example
models the groups listed in Table 1.
Figure 4 shows the effect of increasing the parameter p on the ERR
random walk distribution. Note that this figure is not the output of
any computer simulation, rather it models the distributions for an ERR
random walk on an amenable group with the hypothetical cogrowth
function, for α = 0, β = 0.335 and q = 1. Recall that for β < βc the
theoretical distribution of word lengths visited by the ERR random

19

p

Figure 4. Graphs of cn (n + 1)0.335n for cn = 3n−n .
walk is
cn (n + 1)α+1 β n
Z
where Z is a normalizing constant. For β > βc the distribution cannot
be normalised. In this case the function cn (n+1)α+1 β n still contains information about the behaviour of the walk. If the random walk reaches
a word of length x then the relative heights of cn (n + 1)α+1 β n either
side of x describe the relative probabilities of increasing or decreasing
the word length in the next move.
From Figure 4 we see that, for p = 0.3, the slope of cn (n + 1)α+1 β n
is always positive, so at all word lengths probabilities are uniformly
in favour of increasing the word length. However, as p increases (and
the growth rate for R(n) increases) a ‘hump’ appears at short word
lengths. A random walk for such a group would tend to get stuck in
the ‘hump’. Indeed, for p = 0.39 the distribution looks much less like
a walk diverging towards infinite word lengths and much more like the
distributions for BS(1, 7) used to produce Figure 2, where the average
word length in the ERR walk remained finite.
Pr(@n) =

The distributions in Figure 4 exhibit a mechanism which can explain anomalous behaviour previously observed. When R(n) increases
quickly the ERR random walk may adhere to the behaviour predicted
by the theory and simultaneously give anomalous results about the
asymptotics of the cogrowth function. In this sense if [9] contains incorrect answers it is because the original ERR algorithm as it was
20

initially proposed asks the wrong question. The ERR walk does not
measure asymptotic properties of the cogrowth function; it provides
information about the cogrowth function only for word lengths visited
by the walk. This observation forms the basis of Section 6.
Note that increasing the parameter α pushes the algorithm towards
longer word lengths. Thus, any pathological behaviour caused by the
growth of R(n) could theoretically be overcome by increasing α. If
R(n) is known, then it may be used to calculate how large words have
to get before divergence occurs. A method to do this is outlined by the
following example.
Suppose that ERR random walks are run on a two generator group
with β = 0.34 (as in Figure 3). If we eliminate the α term of the
stationary distribution (which, being polynomial, becomes insignificant
for long word lengths) the divergence properties are controlled by the
contest between 0.34n and cn . That is, divergence will occur when
c2n+2 /c2n > 1/0.342 = 3 − 1/17; the word length at which divergence
will occur is R(17). If this value is known α may be increased until the
walk visits words of this length. This process, however, requires specific
information about R(n) including all scaling constants. It is hard to
imagine a group for which the sub-dominant cogrowth behaviour was
known to this level of precision, but dominant cogrowth behaviour (and
hence the amenability question for the group) was still unknown.
5.3. Reliability of the ERR results for Thompson’s group F .
In Proposition 3.11 we saw that the R function for F grows faster than
that of any iterated wreath product of Z’s, and certainly faster than
that of any BS(1, N ) group. Since the ERR method fails to predict
the amenability of these groups for N as low as 7, and this behaviour is
consistent with the pathological behaviour caused by R, we conclude
that the data encoded in Figure 1 does not imply the non-amenability
of F , and so the conclusion of the paper [9] that F appears to be
non-amenable based on this data is unreliable.
6. Appropriation of the ERR algorithm
The original implementation of the ERR random walk uses only
the mean length of words visited in an attempt to estimate asymptotic
behaviour of the cogrowth function. In this section we show that, using
the full distribution of word lengths visited, it is possible to estimate
specific values of the cogrowth function.
When doing a long random walk, the probability of arriving at a
word of length n can be estimated by multiplying the number of words
21

of that length by the asymptotic probability that the walk ends at a
word of this length, π(n). That is,
(n + 1)α β n
.
Z
The proportion of the time that the walks spends at words of length
n, however, gives us another estimate of Pr(@n). If we let Wn be the
number of times the walk visits a word of length n then we have that
Wn
Pr(@n) ≈
,
Y
where Y is equal to the length of the walk. From this we obtain
Pr(@n) ≈ cn π(n) = cn

Wn
(n + 1)α β n
≈ cn
.
Y
Z
For two different values, n and m, we obtain the result
Wm
cm (m + 1)α β m
,
≈
Wn
cn (n + 1)α β n
Thus,

α
Wm n + 1
(8)
cm ≈ cn
β n−m .
Wn m + 1
Equation 8 provides a method of estimating the value of cm using
some known or previously estimated value of cn and the distribution
of word lengths visited from an ERR random walk. Let’s try a quick
implementation of this for Thompson’s group F , where the first 48
cogrowth terms of which are known [17].
We ran an ERR random walk of length exceeding 1012 steps on the
standard presentation (Equation 2) f or α = 3 and β = 0.3. The
frequency of word length visited is shown in Table 3.
We used Equation 8 and the data in Table 3 to estimate c10 from
c0 , and then this estimate was used to estimate c12 . (Note that the
shortest non-empty trivial words are of length 10. Since the relators
in the standard presentation of F are even in length there are no odd
length relators.) Using the data and the previous estimate for cn−2 ,
estimates were made of the first 48 terms, and these compared to the
correct value in Table 4.
This implementation of Equation 8 may be refined in several ways.
Firstly, in many groups we have exact initial values of cn for more than
the trivial result c0 = 1. In this case these initial values can be used to
estimate subsequent terms. In this paper we are primarily concerned
with testing the efficacy of this method for determining cogrowth, and
so do not make use of such data.
22

n
0
10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48

Wn
32547326274
56273373521
31613690578
26477475739
13576713156
9684082360
5444250723
3360907182
1905434239
1121735814
638093341
367320461
208025510
118432982
65983874
37210588
20642387
11332618
6243538
3421761
1863477

Table 3. Data collected from an ERR random walk of
length Y = 1.8 × 1011 with α = 3 and β = 0.3 on the
standard presentation for Thompson’s group F .

Secondly, in the above implementation the only cogrowth value used
to estimate cn was cn−2 . Instead, estimates for cn may be made from
ck for any k < n. These estimates may then be averaged to form an
estimate for cn . Note, however, that if only one ERR random walk is
used, and each of the ck is itself estimated from previous values of the
same distribution there may be issues with interdependence.
This leads naturally to the following refinement — to obtain several
independent estimates for a given cogrowth value several ERR random
walks can be run with different values for the parameters α and β.
6.1. The ERR-R algorithm. The ERR-R algorithm accepts as input
a group presentation and the cogrowth value with c0 = 1. As above,
recursive application of Equation 8 is used to produce estimates for
longer word lengths. However, in each step previous estimates for a
23

n

exact

estimate

10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48

20
64
336
1160
5896
24652
117628
531136
2559552
12142320
59416808
290915560
1449601452
7269071976
36877764000
1.8848 × 1011
9.7200 × 1011
5.0490 × 1012
2.6423 × 1013
1.3920 × 1014

19.9988
63.9928
335.969
1160.23
5893.13
24667.2
117588
530650
2551340
12116600
59353400
290848000
1453990000
7206930000
36583500000
1.8461 × 1011
9.3078 × 1011
4.7504 × 1012
2.4308 × 1013
1.245 × 1014

percentage
error
.006
.01
.01
.02
.05
.06
.03
.09
.3
.2
.1
.02
.3
.8
.8
2
4
6
8
10

Table 4. Estimate of the first 48 terms of the cogrowth
function for Thompson’s group F , constructed from an
ERR random walk of Y = 1.8 × 1011 steps with α = 3
and β = 0.3. Exact values from [17].

range of cn are used to produce new estimates. A detailed analysis of
the error incurred with each application of Equation 8 is performed in
Section 6.5. All error bounds which appear in subsequent graphs are
constructed using these techniques.
Unsurprisingly, the errror analysis in Section 6.5 predicts that the
largest errors are incurred when data is used from the tails of random
walk distributions. Ideally then, a separate random walk should be run
for each cn , with parameters α and β chosen so that the sampled word
lengths occupy the peaks of the distribution. If many estimates are to
be made this is computationally infeasible. Instead we performed ERR
random walks using a range of α and β values, which can be chosen so
that all word lengths of interest are visited often.
24

1/n

Figure 5. Estimates for cn for the groups BS(1, N ),
N = 2 . . . 7. As N increases the curves takes longer to
approach the asymptote.
When estimating cm , one estimate was made from each random walk
distribution and from each cn , m − 100 < n < m. To avoid using the
tails of distributions only data points which were greater than 10% of
the max height were used.
Using Equation 9 each estimate was assigned a weight equal to the
inverse of the estimated error. The final value for cm was taken as the
weighted average of the estimates, and the error in cm was taken to be
the weighted average of the individual error estimates.
Random walk data was obtained as before using the python code of
the second author as described in Remark 4.2.
6.2. Application to the examples in Section 5. Applying the
ERR-R algorithm can be used to analyse in more detail the pathological behaviours analysed in this paper. Unsurprisingly, for the presentations of the trivial group given in 5.1 which ignore the long relator, the ERR-R estimates for cogrowth values align closely with the
three strand braid group. For BS(1, N ) we can use estimates of initial cogrowth to analyse how R increases with N . This is shown, for
example in Figure 5 which exhibits the behaviour predicted by the convergence to Z o Z in the space of marked groups. Further analysis of
these presentations will appear in [27].
25

Figure 6. Upper and lower bounds for the n-th root
of the cogrowth function for the fundamental group of a
surface of genus 2 as calculated from ERR random walks.
The horizontal lines (indistinguishable at this scale) identify the known upper and lower bounds. Note that after
12000 recursive applications of Equation 8 the error in
the n-th root is still only approximately 0.01.
6.3. Application to surface group. The fundamental group of a
surface of genus 2 has presentation ha, b, c, d | [a, b][c, d]i. The cogrowth
of this group has received a lot of attention, and good upper and lower
bounds are known for the asymptotic rate of growth [14, 23].
ERR random walks were run on this surface group with α = 3, 30, 300
and β = 0.281, 0.286, 0.291, . . . , 0.351. Estimates were made for cn as
1/n
well as the error ∆cn . The resultant upper and lower bounds for cn
are shown in Figure 6.
6.4. Application to Thompson’s group F . We now apply the more
sophisticated implementation of the method to F . Recall that we can
compare the first 48 values with exact values obtained by Haagerup et
al.. Our method allows us to go much further than this though, which
we do.
ERR random walks were run on F with α = 3, 13, 23, 33, 53, 63 and
β = 0.28, 0.29, . . . 0.37. Collection of experimental data is ongoing.
1/n
Table 5 shows comparisons between estimates for cn and the actual
26

n

exact

estimate

10
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48

20
64
336
1160
5896
24652
117628
531136
2559552
12142320
59416808
290915560
1449601452
7269071976
36877764000
1.8848 × 1011
9.7200 × 1011
5.0490 × 1012
2.6423 × 1013
1.3920 × 1014

19.9996
63.9981
335.999
1159.96
5895.98
24653.1
117625
531098
2558950
12138200
59408300
290861000
1449260000
7268550000
36876700000
1.88491 × 1011
9.7205 × 1011
5.05097 × 1012
2.64353 × 1013
1.39246 × 1014

error (%)
0.002
0.003
0.0002
0.003
0.0003
0.005
0.003
0.007
0.02
0.03
0.01
0.02
0.02
0.007
0.003
0.003
0.005
0.04
0.05
0.03

predicted
error (%)
.03
0.06
0.07
0.1
0.1
0.1
0.2
0.2
0.2
0.3
0.3
0.3
0.3
0.4
0.5
0.5
0.5
0.6
0.6
0.7

Table 5. Estimate of the first 48 terms of the cogrowth
function for Thompson’s group F , constructed from 60
ERR random walks. Exact values from [17].

values, for n ≤ 48, as well as the estimates for the error obtained from
the experimental data.
Remark 6.1. Table 5 shows a marked increase in the degree of accuracy of the estimates over those of Table 4. This suggests the method
of using multiple distributions and weighted averages is effective. Note
that there are approximately 1012 trivial words of length 48 so the walks
could not possibly have visited each one. The sample of words visited
by the walk seem to reflect the space as a whole reasonably accurately.
1/n

Figure 7 shows our estimates for upper and lower bounds of cn
n ≤ 2000.
27

for

cn 1/n

3.0

2.5

2.0

1.5

1.0

0.5

0

500

1000

1500

2000

n

1/n

Figure 7. Estimates of cn for Thompsons group F for
n ≤ 2000, using the ERR-R method. The figure includes
upper and lower bounds, but at this scale the estimated
error is to small for the bounds to be distinguished.
6.5. Error analysis. Here we identify a method by which error in
cogrowth estimates my be estimated. We stress that this is a statistical
measurement of error, rather than theoretical.
Recall Equation 8. Suppose that cn is known up to ±∆cn , and that
the error in the measurements Wm and Wn are ±∆Wm and ±∆Wn
respectively. Then, from elementary calculus, the error in cm is given
by

(9)


α
Wm n + 1
∆cm ≈
β n−m ∆cn
Wn m + 1

α
cn
n+1
+
β n−m ∆Wm
Wn m + 1

α
Wm n + 1
+ cn 2
β n−m ∆Wn
Wn m + 1

α


Wm n + 1
∆cn ∆Wm ∆Wn
n−m
=c (n)
β
+
+
Wn m + 1
cn
Wm
Wn


∆cn ∆Wm ∆Wn
≈cm
+
+
.
cn
Wm
Wn
28

Hence the proportional error in the estimate of cm is approximately
equal to the sum of the proportional errors in cn , Wm and Wn . It is clear
from this that if Equation 8 is used recursively (building new estimates
based on previously estimated cogrowth values) the proportional error
in cn is certain to increase. Note, the factor controlling the rate of
growth in the proportional error of estimates is the proportional error
in ∆Wn . If this is constant as n increases the proportional error in cn
will grow linearly with n.
To calculate useful error margins for cn it is necessary to quantify
∆Wn . Here we employ the same method used in the ERR paper; walks
are split into M segments and the number of times the walk visits words
of length n is recorded for each segment. Let xi,n denote the number
of times the walk visited words of length n in the ith segment. Then
Wn is taken to be the average of xi,n for i = 1 . . . M and the error in
Wn is calculated from the statistical variance of these values,
r
(10)

∆Wn =

Var{xi,n }1≤i≤M
.
M −1

Example 6.2. Equations 9 and 10 were used to produce the estimates
of the error in the estimates contained in Table 5. Note that the estimated error is much larger then the actual error.
6.6. Error in the n-th root of cn . We have noted that recursive
uses of Equation 8 will result in an increasing proportional error in cn .
However, it is the n-th root of cn which reflects the amenability of a
1/n
group. Let γn = cn and ∆γn denote the error of the estimate for γn .
Once again from elementary calculus we obtain that for a given n
1 n1 −1
cn ∆cn
n
1 1 ∆cn
= cnn
n
cn
1 ∆cn
= γn
n cn
∆γn
1 ∆cn
and so
≈
.
γn
n cn
∆γn ≈

(11)

n
n
Thus, if ∆c
increases at most linearly, ∆γ
can be expected to remain
cn
γn
constant.
The values for cn grow exponentially, so a linearly increasing proportional error in cn corresponds with a massive increase in the absolute

29

error in cn . In contrast, γn approaches a constant, so the proportional
error depends linearly on the absolute error. Thus it is not surprising that our experimental results show that even when the error in
cogrowth estimates grows large, the error in the n-th root grows very
slowly.
7. Conclusion
Several ideas emerge from this study. Firstly, researchers performing experimental mathematics to determine the amenability of a group
need to take care that their algorithm is not susceptible to interference
from sub-dominant behaviours. For the reduced-cogrowth function the
sub-dominant behaviour is identified by R. Amenability is an asymptotic property, and the interference of sub-dominant behaviours on experimental algorithms can be subtle and nuanced. In particular, we
have shown that, if Thompson’s group F is amenable, its function R
grows faster than any polynomial. This implies that the prediction of
non-amenability of F in [9] is unreliable.
We have also shown that, despite potential inaccuracies in estimates
of asymptotics, the ERR-R method can produce accurate results for
initial cogrowth values. These are interesting in their own right. Indeed, if Thompson’s group is not amenable, then its R function need
not be super-polynomial and results from experimental methods might
well inform the construction of conjectures regarding cogrowth.
In this context the original benefits of the ERR algorithm still stand:
it requires no group theoretic computational software, no solution to
the word problem, and remains a computationally inexpensive way to
quickly gain insight into the cogrowth function of a finitely presented
group.
Acknowledgements
The authors wish to thank Andrew Rechnitzer and Andrew ElveyPrice for helpful feedback on this work.
References
[1] G. N. Arzhantseva, V. S. Guba, M. Lustig, and J. Préaux. Testing Cayley
graph densities. Ann. Math. Blaise Pascal, 15(2):233–286, 2008.
[2] J. M. Belk and K. S. Brown. Forest diagrams for elements of Thompson’s group
F . Internat. J. Algebra Comput., 15(5-6):815–850, 2005.
[3] A. Bendikov, C. Pittet, and R. Sauer. Spectral distribution and L2 isoperimetric profile of Laplace operators on groups. Math. Ann., 354(1):43–72,
2012.
30

[4] M. G. Benli, R. I. Grigorchuk, and P. de la Harpe. Amenable groups without
finitely presented amenable covers. Bull. Math. Sci., 3(1):73–131, 2013.
[5] J. Burillo, S. Cleary, and B. Wiest. Computational explorations in Thompson’s
group F . In Geometric group theory, Trends Math., pages 21–35. Birkhäuser,
Basel, 2007.
[6] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on Richard
Thompson’s groups. Enseign. Math. (2), 42(3-4):215–256, 1996.
[7] T. G. Ceccherini-Silberstein and R. I. Grigorchuk. Amenability and growth of
one-relator groups. Enseign. Math. (2), 43(3-4):337–354, 1997.
[8] J. M. Cohen. Cogrowth and amenability of discrete groups. J. Funct. Anal.,
48(3):301–309, 1982.
[9] M. Elder, A. Rechnitzer, and E. J. Janse van Rensburg. Random sampling of
trivial words in finitely presented groups. Exp. Math., 24(4):391–409, 2015.
[10] M. Elder, A. Rechnitzer, and T. Wong. On the cogrowth of Thompson’s group
F . Groups Complex. Cryptol., 4(2):301–320, 2012.
[11] A. Erschler. On isoperimetric profiles of finitely generated groups. Geom. Dedicata, 100:157–171, 2003.
[12] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University
Press, 2009.
[13] E. Følner. On groups with full Banach mean value. Math. Scand., 3:243–254,
1955.
[14] S. Gouëzel. A numerical lower bound for the spectral radius of random walks
on surface groups. Combin. Probab. Comput., 24(6):838–856, 2015.
[15] R. I. Grigorchuk. Symmetrical random walks on discrete groups. In Multicomponent random systems, volume 6 of Adv. Probab. Related Topics, pages
285–325. Dekker, New York, 1980.
[16] V. S. Guba and M. V. Sapir. On subgroups of the R. Thompson group F and
other diagram groups. Mat. Sb., 190(8):3–60, 1999.
[17] S. Haagerup, U. Haagerup, and M. Ramirez-Solano. A computational approach
to the Thompson group F . Internat. J. Algebra Comput., 25(3):381–432, 2015.
[18] H. Kesten. Symmetric random walks on groups. Trans. Amer. Math. Soc.,
92:336–354, 1959.
[19] D. Kouksov. On rationality of the cogrowth series. Proc. Amer. Math. Soc.,
126(10):2845–2847, 1998.
[20] P. H. Kropholler and A. Martino. Graph-wreath products and finiteness conditions. J. Pure Appl. Algebra, 220(1):422–434, 2016.
[21] D. Kuksov. Cogrowth series of free products of finite and free groups. Glasg.
Math. J., 41(1):19–31, 1999.
[22] J. T. Moore. Fast growth in the Følner function for Thompson’s group F .
Groups Geom. Dyn., 7(3):633–651, 2013.
[23] T. Nagnibeda. An upper bound for the spectral radius of a random walk on
surface groups. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov.
(POMI), 240(Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 2):154–165,
293–294, 1997.
[24] C. Pittet and L. Saloff-Coste. On the stability of the behavior of random walks
on groups. J. Geom. Anal., 10(4):713–737, 2000.
[25] C. Pittet and L. Saloff-Coste. On random walks on wreath products. Ann.
Probab., 30(2):948–977, 2002.
31

[26] C. Pittet and L. Saloff-Coste. Random walks on finite rank solvable groups. J.
Eur. Math. Soc. (JEMS), 5(4):313–342, 2003.
[27] C. Rogers. On the interconnectedness, via random walks, of cogrowth rates and
the Følner function. PhD thesis, The University of Newcastle, 2016.
[28] R. Szwarc. A short proof of the Grigorchuk-Cohen cogrowth theorem. Proc.
Amer. Math. Soc., 106(3):663–665, 1989.
[29] A. M. Vershik. Amenability and approximation of infinite groups. Selecta Math.
Soviet., 2(4):311–330, 1982. Selected translations.
[30] W. Woess. Cogrowth of groups and simple random walks. Arch. Math. (Basel),
41(4):363–370, 1983.
School of Mathematical and Physical Sciences, The University of
Newcastle, Callaghan NSW 2308, Australia
E-mail address: Murray.Elder@newcastle.edu.au
School of Mathematical and Physical Sciences, The University of
Newcastle, Callaghan NSW 2308, Australia
E-mail address: Cameron.Rogers@uon.edu.au

32

