NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED
GROUPS

arXiv:1706.07571v1 [] 23 Jun 2017

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN
Abstract. We have developed polynomial-time algorithms to generate terms of the
cogrowth series for groups Z o Z, the lamplighter group, (Z o Z) o Z and the Navas-Brin
group B. We have also given an improved algorithm for the coefficients of Thompson’s
group F, giving 32 terms of the cogrowth series. We develop numerical techniques to
extract the asymptotics of these various cogrowth series. We present improved rigorous
lower bounds on the growth-rate of the cogrowth series for Thompson’s group F using
the method from [18] applied to our extended series. We also generalise their method by
showing that it applies to loops on any locally finite graph. Unfortunately, lower bounds
less than 16 do not help in determining amenability.
Again for Thompson’s group F we prove that, if the group is amenable, there cannot be
a sub-dominant stretched exponential term in the asymptotics1. Yet the numerical data
provides compelling evidence for the presence of such a term. This observation suggests
a potential path to a proof of non-amenability: If the universality class of the cogrowth
sequence can be determined rigorously, it will likely prove non-amenability.
We estimate the asymptotics of the cogrowth coefficients of F to be
cn ∼ c · µn · κn

σ

logδ n

· ng ,

where µ ≈ 15, κ ≈ 1/e, σ ≈ 1/2, δ ≈ 1/2, and g ≈ −1. The growth constant µ must
be 16 for amenability. These two approaches, plus a third based on extrapolating lower
bounds, support the conjecture [7, 18] that the group is not amenable.

1. Introduction
In an attempt to find compelling evidence for the amenability or otherwise of Thompson’s
group F , we have studied, numerically, the co-growth sequence of a number of infinite,
finitely generated amenable groups whose asymptotics are, in most cases, partially or fully
known. We have chosen a number of examples with increasingly complex asymptotics.
Using the experience and insights gained from these examples, we turn to a study of
Thompson’s group F , having first developed an improved algorithm for the generation of
the co-growth sequence, which we evaluate to O(x32 ).
The cogrowth series of a group G with finite, inverse closed, generating set S is
X
CG =
cn xn ,
n≥0

where cn is the number of words w of length 2n over the alphabet S, which satisfy w =G 1
i.e. w is the identity in the group G. There are many equivalent definitions of amenability.
A standard one is that a group G is amenable if it admits a left-invariant finitely additive
1

2

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

probability measure µ. A consequence of the Grigorchuk-Cohen [11, 5] theorem is that G is
amenable if and only if the radius of convergence of CG is 1/|S|2 . In particular, Thompson’s
group F amenable if and only if its cogrowth sequence has exponential growth rate 16.
We have developed new, polynomial-time algorithms to generate coefficients for the
lamplighter group, and for general wreath product groups, Wd = Z od Z. We also give a
polynomial time algorithm for the cogrowth coefficients of the Navas-Brin group, and an
improved algorithm to generate the coefficients of Thompson’s group F, generating the
cogrowth sequences to O(x128 ) and O(x32 ) for B and F respectively.
The amenable group introduced independently by Navas [19] and Brin [4], which we call
the Navas-Brin group B, is a subgroup of Thompson’s group F , and is defined as an infinite
wreath product, with an extra generator which commutes each generator of the infinite
wreath product to the next one. It has 2 generators, so the growth rate of the cogrowth
sequence is 16. It also has a sub-exponential growth term that is very close to exponential,
and so makes the growth rate difficult to estimate accurately with the number of terms at
our disposal.
Using results of Pittet and Sallof-Coste [20, 21], we prove that the cogrowth coefficients
cn of Thompson’s group F satisfy
cn < 16n · λ−n

κ

for any real numbers κ < 1, and λ > 1. That is to say, if Thompson’s group F is amenable,
then its asymptotics cannot contain a stretched-exponential term1. Such a term is present
in the asymptotics of the lamplighter group L and the family of groups Wd . Furthermore,
our numerical study reveals compelling evidence for the presence of such a term in the
asymptotics of the coefficients of F. This is our first strong evidence that Thompson’s
group F is not amenable. Our second piece of evidence is the estimation of the growth
constant. For amenability, the growth constant must be 16. We find that it is very close
to 15.0 (we do not suggest it is exactly 15, but that is certainly a possibility).
Our numerical analysis relies on a number of methods that are well-known in the statistical mechanics and enumerative combinatorics community. Many are reviewed in [13] and
[16]. For studies of the cogrowth asymptotics we primarily rely on the behaviour of the
ratio of successive coefficients, as irrespective of the sub-dominant asymptotics, this ratio
must go to the growth constant in the limit as the order of the coefficients goes to infinity.
One new technique that we make use of in our study of the groups B and F is that of
series extension [15]. In the case of group B, we have 128 exact coefficients, but predict a
further 590 ratios (and terms) with an estimated accuracy of, at worst, 1 part in 5 × 10−7 .
Having these extra (approximate) terms greatly improves the quality of the analysis we
can perform. Similarly, for group F, we use 32 exact terms to predict a further 200 ratios
1We define stretched exponential more broadly than usual. It normally refers to a term of the form e−tβ ,
β

δ

with t > 0 and 0 < β < 1. We allow behaviour such as e−t ·log t , or indeed any appropriate logarithmic
δ
term. We do not have a name for sub-exponential growth of the form e−t/ log t , with δ > 0 (or appropriate
logarithmic function) which is the type of term that must be present in the cogrowth series of the Navas-Brin
group, and indeed in Thompson’s group F if it were amenable.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

3

(and terms) with an estimated accuracy of 1 part in 4 × 10−5 . This level of accuracy is
more than sufficient for the graphical techniques we use to extract the asymptotics.
Another approach to estimating the growth rate was introduced by Haagerup, Haagerup
and Ramirez-Solano in [18] who proved that the cogrowth sequence of Thompson’s group
F is given by the moments of a probability measure. We extend this to prove that this
observation applies to the cogrowth sequence of any Cayley graph. In this way a sequence
of rigorous lower bounds to the growth constant of the cogrowth series can be constructed.
This approach also gives some stronger, non-rigorous, pseudo-bounds. Further details of
this method, and some results, are given in section 4.
The simplest examples of groups we have chosen have asymptotics of the form
cn ∼ c · µn · ng ,
where c is a constant, µ is the growth constant and g is an exponent.
The first example of such a group is Z2 , which is a particularly simple case as both
2
the coefficients and generating function
are exactly known. In fact cn = 2n
n , and the

√

generating function CZ2 = 2K 4 π x , where K is the complete elliptic integral of the first
kind.
The second example is the Heisenberg group, for which the asymptotic form of the
coefficents is known [10] to be cn ∼ 0.5 · 16n · n−2 , corresponding to a generating function
1
CHeisenberg ∼ (1 − 16x) log(1 − 16x).
2
We have calculated 90 terms of the generating function, and show that this is sufficient to
get a very precise asymptotic representation of the coefficients.
The next level of asymptotic complexity arises when there is an additional stretchedexponential term, so that the coefficients of the generating function behave as
σ

cn ∼ c · µn · κn · ng ,
where 0 < κ < 1, and 0 < σ < 1. There is no known simple expression for the corresponding
generating function in such cases2. The lamplighter group L is the wreath product of the
group of order two with the integers, L = Z2 o Z. The growth rate is known, µ = 9, and
from Theorem 3.5 of [21] it follows that σ = 1/3, and from [22] we know that the exponent
1/3
g = 1/6. So for the lamplighter group, cn ∼ c · 9n · κn · n1/6 . Methods to extract the
asymptotics from the coefficients have been developed, and are described in [14]. We give
a polynomial time algorithm to generate the coefficients, and use it to determine the first
201 coefficients, from which we are able to estimate the correct values of the parameters
µ, σ and g.
We next consider wreath products Wd = Z od Z. In that case the exponent of the
stretched-exponential term also includes a fractional power of a logarithm. Coefficients
of the generating function behave as given by Theorem 3.11 in [21], so that
σ

cn ∼ c · µn · κn

logδ n

· ng ,

2See, for example [14] for a discussion of this point, and further examples of such generating functions.

4

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

where 0 < κ < 1, and 0 < σ, δ < 1.
For d = 1, one has µ = 16, σ = 1/3, δ = 2/3 and g is not known. For d = 2, one has,
again by Theorem 3.11 in [21], µ = 36, σ = 1/2 and δ = 1/2. For general d, µ = (2d)2 ,
σ = d/(d + 2), and δ = 2/(d + 2).
Note that this dimensional dependence of the exponent σ of the stretched-exponential
term appears to be a common feature among a broad class of problems. For example, if one
considers the problem of a self-avoiding walk attached to a surface at its origin (or a Dyck
path or a Motzkin path) and pushed toward the surface at its end-point (or its highest
vertex), then, as shown in [1] there is a stretched-exponential term in the asymptotics of
the coefficients, with exponent σ = 1/(1 + df ), where df is the fractal dimension of the
walk/path. Whether this dimensional dependence is in fact a ubiquitous feature of such
stretched-exponential terms remains an open question.
We have studied two examples, W1 = Z o Z and W2 = (Z o Z) o Z, based on the series we
have generated of 276 and 133 terms respectively. We find that the presence of the confluent
logarithmic term in the exponent makes the analysis significantly more difficult, but we
can nevertheless accurately estimate the growth constant µ and less precisely estimate the
sub-dominant growth rate κ and the exponents σ and δ. Our estimates of the exponent g
are not precise enough to be useful.
We then turn to a contrived example, a constructed series with the asymptotics of Wd =
Z od Z, with d = 98. As d increases, the exponent in the stretched-exponential term gets
closer to 1, and so this term behaves more and more like the dominant exponential growth
term µn . We show that estimating the correct growth constant even approximately requires
careful analysis, and appropriate techniques. This serves as a caution, and underlies that
our conclusions regarding the non-amenability of Thompson’s group F assumes the absence
of some unknown functional pathology.
Finally we study two groups whose behaviour is not fully known. The first is the NavasBrin group B. We give a polynomial-time algorithm to generate the coefficients, and in
this way generate the first 128 terms, then use these to estimate the next 590 ratios. This
group has a sub-exponential growth term that is very close to exponential, and so makes the
growth rate difficult to estimate accurately with the number of terms at our disposal. The
second is Thompson’s group F where we have 32 exactly known terms, and 200 estimated
ratios of terms.
The makeup of the paper is as follows. In Section 2 we describe the algorithms developed
for the cogrowth series of the lamplighter group L, W1 , W2 , B and Thompson’s group F.
In Section 3 we discuss the possible asymptotic form of the cogrowth series for Thompson’s
group F, and prove the absence of a stretched-exponential term. In Section 4 we develop
the idea that the cogrowth coefficients can be represented as the sequence of moments of
a probability measure. With this identification we establish rigorous lower-bounds on the
growth constant for Thompson’s group F. In Section 5 we analyse the series expansions
for the cogrowth series of all the groups we have mentioned above, apart from B and F.
Section 6 is devoted to a description of the method of series extension that we employ,
and in Sections 7 and 8 we use this method and the techniques discussed in the previous

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

5

section to analyse the Navas-Brin group B and Thompson’s group F. Section 9 comprises
a discussion and conclusion.
2. Series generation
In this section we describe the algorithms we have used to compute the terms of the
cogrowth sequence of various groups. We start by describing polynomial time algorithms
which we have found and used for the groups L, W1 , W2 , and B. Finally we describe the
algorithm which we have used for Thompson’s group F . The first 50 coefficients for the
group B are given in Table 1, while the coefficients of the cogrowth series of F are given
in Table 2.
2.1. Wreath Products G o Z. Let G be a group with finite generating set S. We will
describe a polynomial time algorithm for computing the cogrowth series of G o Z, with
respect to the generating set {a} ∪ S, where a generates Z, given the corresponding series
for G. In particular, this give a polynomial time algorithm to compute the cogrowth of the
lamplighter group Z2 o Z as well as groups such as Z o Z and (Z o Z) o Z.

Let ak be the number of loops of length k in G. For example, if G = Z, then a2k = 2k
k
and a2k+1 = 0 for all k ∈ Z≥0 . Then for each positive integer n, define the generating
function Pn (x) by

∞ 
X
j+n−1
Pn (x) =
aj xj .
n−1
j=0

This is the generating function for n-tuples of words w1 , w2 , . . . , wn ∈ S ∗ such that w1 . . . wn =
1, counted by the length of the word w1 . . . wn .
Given a loop l in G o Z, we define the base loop l0 of l to be the loop in Z made up of
only the terms a and a−1 in l. For each positive integer i, let ci be the number of steps in
the baseloop l0 from ai−1 to ai (which is the same as the number of steps from ai to ai−1 )
and let di be the number of steps from a−i+1 to a−i . Let m and n be maximal such that
cm , dn > 0. Then the length of l0 is equal to
m
n
X
X
2ci +
2dj .
i=1

j=1

l0

Let = a1 a2 . . . a|l0 | and l = w1 a1 w2 . . . a|l0 | w|l0 |+1 , where each wi is a word in (S ∪ S −1 )∗ .
We say that the height of one of the subwords wi is equal to the integer p which satisfies
ap = a1 . . . ai . Then l is a loop if and only if for any height h, concatening all of the words
wi at height h creates a loop in G. Hence the generating function for the sections at height
h is Pr (x) where r is the number of these sections. If h > 0 then r = ch + ch+1 , if h < 0
then r = d−h + d−h+1 and if h = 0 then r = c1 + d1 + 1. Hence, by considering the sections
of l at each height separately, we see that the generating function for loops l with base loop
l0 is equal to
(1)

0

x|l | Pdn (x)Pcm (x)Pc1 +d1 +1 (x)

m−1
Y
i=1

Pci +ci+1 (x)

n−1
Y
j=1

Pdj +dj+1 (x),

6

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

assuming that m, n ≥ 1. Similarly, if m = 0 and n ≥ 1, the generating function is
|l0 |

x Pdn (x)Pd1 +1 (x)

n−1
Y

Pdj +dj+1 (x).

j=1

If n = 0 and m ≥ 1, the generating function is
0

x|l | Pcm (x)Pc1 +1 (x)

m−1
Y

Pci +ci+1 (x).

i=1

Finally, if m = 0 and n = 0, then the generating function is P1 (x). So we now need to sum
this over all possible base loops l0 .
For a given pair of sequences c1 , . . . , cm , d1 , . . . , dn , the number of such base loops is
equal to
(2)


 m−1 
 n−1 

c1 + d1 Y ci + ci+1 − 1 Y dj + dj+1 − 1
.
c1
ci − 1
dj − 1
i=1

j=1

This is because from each vertex i > 0 we can choose the order of the outgoing steps, except
that the last one must be a left step, and there are ci − 1 other left steps and ci+1 right
i+1 −1
steps. Hence there are ci +c
possible orders of the steps leaving any vertex i > 0, and
ci −1

dj +dj+1 −1
similarly
possible orders of the steps leaving any vertex −j for j > 0. Finally,
dj −1

c1 +d1
there are c1
possible orders of the steps leaving the vertex 0. It is easy to see that for
any possible choice of these orders there is exactly one corresponding base loop l0 .
Now using (1) and (7) it follows that for any pair of sequences c1 , . . . , cm , d1 , . . . , dn ,
with m, n ≥ 1, the generating function for the corresponding loops l in G o Z is equal to
(3)
x2c1 +2d1

m−1
n−1
c + d 
c + c

d + d

Y
Y
1
1
i
i+1 − 1
j
j+1 − 1
Pdn Pcm Pc1 +d1 +1
x2ci+1
x2dj+1
Pci +ci+1
Pdj +dj+1 .
c1
ci − 1
dj − 1
i=1
j=1

If m = 0 and n ≥ 1, the generating function is
(4)

x

2d1

Pdn Pd1 +1

n−1
Y

x

2dj+1

j=1



dj + dj+1 − 1
Pdj +dj+1 .
dj − 1

If m ≥ 1 and n = 0 we get a similar generating function, and if m = n = 0 we get P1 (x).
To calculate these we define some new power series Ωd (x) by
Ωd (x) =

X

Pdn

n−1
Y
j=1

x

2dj+1




dj + dj+1 − 1
Pdj +dj+1 (x),
dj − 1

where the sum is over all sequences n, d1 , d2 , . . . , dn with d1 = d. Then it follows immediately from (3) and (4) that the generating function F for the cogrowth series series of G o Z

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

is given by
(5)

F (x) = 

∞
X
c,d=1

7


!


∞
X
2c+2d c + d
2d
Pc+d+1 (x)Ωd (x)Ωc (x) + 2
x
x Pd (x)Ωd (x) + P1 (x).
c
d=1

So now we just need to calculate Ωd (x) for each positive integer d. First, the contribution
to Ωd from the case where n = 1 is Pdn = Pd1 = Pd . The contribution from the case where
n = 1 and d2 = b for some fixed positive integer b is


d+b−1
x2b
Pd+b (x)Ωb (x).
d−1
Hence, we have the equation
(6)

Ωd (x) = Pd (x) +

∞
X
b=1



b+d−1
x
Pb+d (x)Ωb (x).
d−1
2b

Using this equation we can calculate the coefficient of xk in Ωd of x in terms of coefficients
of xj in Ωb (x) where we only need to consider j, b satisfying 2b + j ≤ k (hence j ≤ k − 2).
This takes polynomial time using a simple dynamic program.
2.2. The Navas-Brin group B. In this section we adapt the previous algorithm to calculate the cogrowth series for the Navas-Brin group B. Again this is a polynomial time
algorithm, however the polynomial has higher degree than the one for the previous section.
The group B is defined as the semi-direct product
(. . . o Z o Z o Z o Z o . . .) o Z,
where the copies of Z in the wreath product are generated by . . . , a2 , a1 , a0 , a−1 , a−2 , . . .
and the generator t of the other copy of Z satisfies tai t−1 = ai+1 for each i. Note that
the group B is generated by the two elements t and a = a0 . The group B was described
independently in [19] and on page 638 in [4], where Brin showed that is an amenable
supgroup of Thompson’s group F . In that paper it is the group generated by f and h.
We define the t-height of a word over the generating set {a, t, a−1 , t−1 } to be the sum
of the powers of t. Before counting the total number of loops, we will count the number
of loops where any initial subword has non-negative height. Let G(x, y) be the generating
function for these, where x counts the total length and y counts the number of steps of
the loop which end at height 0. For each positive integer n, let Hn (x, y) be the generating
function for n-tuples w1 , w2 , . . . , wn of words in {a, a−1 , t, t−1 }∗ which each end at height 0
and which have no a or a−1 steps at height 0, such that w1 . . . wn = 1. In this generating
function, x counts the total length of w1 . . . wn and y counts the total number of steps
which end at height 0. Given such a loop l, let the baseloop l0 be the subword consisting
of all a and a−1 steps at t-height 0. Similarly to the previous algorithm, we let ci be the
number of steps in l0 from ai−1 to ai , and di be the number of steps in l0 from a−i+1 to

8

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

a−i . Then the length |l0 | of l0 is equal to
m
X

2ci +

i=1

n
X

2dj .

j=1

As in the previous subsection, for a given pair of sequences c1 , . . . , cm , d1 , . . . , dn , the number of such base loops is equal to
 m−1 
 n−1 


c1 + d1 Y ci + ci+1 − 1 Y dj + dj+1 − 1
(7)
.
c1
ci − 1
dj − 1
i=1

j=1

Let l0 = a1 a2 . . . a|l0 | , where each ai ∈ {a, a−1 }, and let l = w1 a1 w2 . . . a|l0 | w|l0 |+1 be the
decomposition where each step ai is at t-height 0. We say that the a-height of one of the
subwords wi is equal to the integer p which satisfies ap = a1 . . . ai . Then l is a loop if and
only if for any height h, concatenating all of the words wi at a-height h creates a loop.
Note that each word wi must have height 0 and have no a or a−1 steps at height 0. As in
the previous section we define another generating function Λd (x, y) by


n−1
Y
X
2dj+1 2dj+1 dj + dj+1 − 1
Λd (x, y) =
Hdn
x
y
Hdj +dj+1 (x),
dj − 1
j=1

where the sum is over all sequences n, d1 , d2 , . . . , dn with d1 = d. In the same way as in
the previous section we get the following equations, which are essentially the same as (5)
and (6).

G(x, y) =

∞
X
c,d=1
∞
X

+2

2c+2d 2c+2d

x

y



c+d
Hc+d+1 (x, y)Λd (x, y)Λc (x, y)
c

x2d y 2d Hd (x, y)Λd (x, y)

d=1

(8)

(9)

+H1 (x, y).

Λd (x) = Hd (x, y) +

∞
X
b=1

2b 2b

x y




b+d−1
Hb+d (x, y)Λb (x).
d−1

So now to calculate G(x, y), we just need to calculate the generating functions Hn (x, y).
For each k ∈ Z≥0 , let Jk (x) be the generating function for loops in B which have exactly
k steps which end at t-height 0, none of which are a or a−1 steps, and which never go
below height 0. For each such word w, the number of ways of breaking it into n words
w1 , w2 , . . . , wn where each ends at height 0, such that w1 . . . wn = w is equal to


k+n−1
.
n−1

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

9

Therefore, we can calculate each generating function Hn (x, y) in terms of the generating
functions Jk (x) as follows:


∞
X
k k+n−1
(10)
Hn (x, y) =
Jk (x).
y
n−1
k=0

Finally, we will calculate the generating functions Jk (x). Trivially we have J0 (x) = 1.
For k > 0, let l be a loop counted by Jk (x). Then l must contain exactly k steps which end
at height 0, which are not a or a−1 steps. Hence they must all be t−1 steps. Therefore, l
decomposes as
l = tu1 t−1 tu2 t−1 . . . tuk t−1 ,
where each word uk ends at height 0 and never goes below height 0. Moreover, since l
is a loop, we must have u1 . . . uk = 1. Hence the word u = u1 . . . uk is counted by the
generating function G(x, y). Moreover, if u contains m steps which end at height 0, then
there are exactly


m+k−1
k−1
ways to decompose u into subwords u1 , . . . , uk which each end at height 0. Hence we get
the equation


∞
X
2k m + k − 1
(11)
Jk (x) =
x
[y m ]G(x, y).
k−1
m=0

Now using equations (8), (9), (10) and (11) as well as the base case J0 (x) = 1, we can
calculate the coefficients of G(x, y) in polynomial time using a dynamic program. Finally
we need to relate these coefficients to the total number of loops in B. We claim that for
each n, the number of loops bn of length n in B over the generating set {a, t, a−1 , t−1 } is
equal to
∞
X
n m n
[y ][x ]G(x, y).
bn =
m
m=0

The reason for this is that the contribution to both sides of the equation from any set
of n loops which are cyclic permutations of each other is the same. That is, if we take
n loops xi . . . xn x1 . . . xi−1 for 1 ≤ i ≤ n, and m of these are counted by G(x, y), then
they will each contribute xn y m to G(x, y), so altogether these will contribute n to both
sides of the equation. If two or more of these loops are identical, then we must have
x1 . . . xn = (x1 . . . xp )q for some p, q satisfying pq = n. In this case, assuming that q is
maximal, the contribution to each side is n/q instead of n, since we overcounted by a
factor of q.
Using the last equation we can quickly calculate the coefficients of the cogrowth generating function CB (x) using those of G(x, y). In Table 1 we give the first 50 coefficients of
this generating function. In fact we have 128 terms.

10

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN
1
4
28
232
2092
19864
195352
1970896
20275692
211825600
2240855128
23952786400
258287602744
2806152315048
30686462795856
337490492639512
3730522624066540
41422293291178872
461802091590831904
5167329622166765872
58012358366319158872
653272479274904359312
7376993667962247094112
83518163933592420945440
947797532286760923097848
10779770914124700529470264
122856228305621394118000520
1402877847412263986004347872
16048147989560391552043686160
183892883412730524613883088808
2110556326150834244975990231512
24259510831181186885644198829344
279244563297679787781517160899820
3218641495385722409923501191862264
37146337262307758446419466115479416
429227600058421313330040967935014416
4965493663308539362541734301378311648
57506535582014868288482236767840209688
666700108804771886996957763509359246064
7737176908622194648339548498436658811432
89878279784970230837678375953110478795352
1045033044367535197025078407316665177933928
12161645115366917947524997117208173413019632
141653302005285175865456465524239660635389712
1651274058730064356309776255817393993665780288
19264448513399180870635082273788105896265150480
224919270246185854430934219198103161122414157760
2627954546552385827255336138747466100454012242528
30726935577139566309665785537931570627782996384120
359517978960007312327796870699755173605904761839752

Table 1. The first 50 coefficients of the cogrowth series for the Navas-Brin
group B.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

11

2.3. A General Algorithm. Before we describe the algorithm which we use for Thompson’s group F , we will describe a general algorithm which can be applied to any group
admitting certain functions which can be computed very quickly. In the next subsection
we will describe how we apply this algorithm to F . This algorithm could also be applied to
any of the other groups which we have discussed, however it would be much less efficient
than the specific algorithms described previously in this section.
Our algorithm can be seen as a significantly more memory efficient version of the algorithm in [6]. First we describe that algorithm. Given a loop γ = a0 a1 . . . a2n , where each
ai ∈ V (Γ) and a2n = a0 = e, we define the midpoint of γ to be the vertex an . Then γ is
made up of a walk of length n from e to its midpoint followed by a walk of length n from
its midpoint to 1. Hence, the number of loops in Γ of length 2n with midpoint m is the
square of the number of walks of length n from 1 to m.
Using a simple dynamic program, the algorithm calculates the number of walks to each
vertex in B(e, n), the ball of radius n in Γ. Then one sums the squares of these numbers
to calculate the number of loops of length 2n. Note also that for each walk from e to m,
there is a corresponding walk from e to m−1 , so it is only necessary to calculate the number
of walks to either m or m−1 . The problem with this algorithm is that it is necessary to
store a large proportion of the ball of radius n in memory at the same time. As a result
it is essentially impossible to get any more than 24 coefficients of the cogrowth series for
Thompson’s group F using this algorithm. Our algorithm is very similar except that we
only store the ball of radius k in memory, where k ≈ n/2. Importantly, we do this without
significantly increasing the running time of the program.
Let G be a group with inverse closed generating set S. Let Γ(G, S) denote the Cayley
graph of G with respect to the generating set S. We will often refer to this as simply Γ.
We will assume that every loop has even length, however this algorithm could easily be
altered to apply when this is not the case.
Let O be an object in the program which represents an element of G. We require the
following functions to be implemented:
• init(). This returns an object O which represents the identity in G.
• val(O). This returns a value which is uniquely determined by the element of G
which the object O represents. In other words, val(O1 ) = val(O2 ) if and only if O1
and O2 represent the same element of G.
• For each generator λ ∈ S, we have an operation O.doλ . If O initially represents the
element g ∈ G, this changes O to an object which represents gλ.
• For each generator λ ∈ S, we have a function lλ (O), defined by lλ (O) = |gλ| − |g|,
where g is the element of G which O represents. That is, lλ (O) = 1 if applying λ
moves g away from the identity.
The speed of our algorithm depends entirely on the efficiency of these functions. For
Thompson’s group our implementations of these all take constant time. Importantly, we
do not require an inverse of val to be implemented.
Given these functions, the algorithm proceeds as follows:
Step 1: Assign an arbitrary order to the generating set S and set k = d n2 e.

12

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Step 2: Using a simple dynamic program, construct an associative array An−k , implemented as a hash table, with a key value pair (kg , ag ) for each element g ∈ G within the
ball of radius n − k. The key kg is given by val(O) where O is any object which represents
g and the value ag is equal to the number of walks of length n − k in Γ from e to g. We
will write ag = A[kg ]. For a number x which is not a key in An−k , we set A[x] = 0.
Step 3: Construct a tree Tk which contains one vertex vg for each element g of G within
the ball of radius k, such that each vertex vg , apart from ve , is connected to exactly one
vertex vh satisfying |h| = |g| − 1, and g = hλ for some λ ∈ S. If there are multiple possible
choices of h, we choose the element h which minimises λ, according to the order we assigned
in step 1. The edge (h, g) is then labelled with λ. Each vertex vg is also labelled with the
number p(vg ) of paths of length k in Γ from e to g.
Step 4: We now create a function numpaths(O, d) whose input is an object O and a
positive integer d, which, assuming that d = |g|, outputs the number of paths of length n
in Γ from e to g, where g is the group element represented by O. During the calculation
of numpaths the object O may change, but at the end it must represent the same group
element g. Each path of length n from e to g −1 in Γ can be written in a unique way as a
path of length k from e to some vertex h in Γ followed by a path of length n − k from h to
g −1 . For a given h, the number of these paths is equal to p(vh )A[kh−1 g−1 ] = p(vh )A[kgh ].
Hence, the number which we need to return is
X
p(vh )A[kgh ].
h∈G

Note also that the summand is 0 unless |h| ≤ k and |gh| ≤ n − k, so we only need to sum
over values of h which satisfy these two inequalities. To do this we perform a depth first
search of the tree Tk , skipping any sections where we can be sure that there are no vertices
vh such that h satisfies the two inequalities. We start the search at the root vertex ve of Tk
and initialise r = 0 and total = 0. Whenever we move from a vertex vh to vhλ we change
d to d + lλ (O) and then apply the operation O.doλ . That way whenever we are at a vertex
vh , the object O represents gh and d = |gh|. We also increase x by 1 whenever we move
to a child vertex and decrease x by 1 when we backtrack so that we always have x = |h|.
Then we add p(vh )A[kgh ] = p(vh )A[val(O)] to the sum total if and only if d ≤ n − k, since
x = |h| ≤ k for every vertex vh in Tk . Since d decreases by at most 1 when we move to a
child vertex, and x always increases by 1, the value x + d never decreases when we move
to a child vertex. So if x + d > n when we are at a vertex vh , then we do not traverse the
children of vh . At the end of the search we return to the root vertex so that O is back to
its original value and then return the value total.
Step 5: For the last step we just need to add up the value of numpaths for every
vertex g in the ball of radius n such that |g| has the same parity as n. To accomplish this
we perform a depth first search of the tree Tn , which is defined in the same way as Tk .
However, we do not explicitly construct Tn as doing so would use too much memory. In
order to perform the depth first search, we just need a function isedgeλ (O) for each λ ∈ S
which returns 1 if and only if there is an outward edge from vg to vgλ in Tn , where g is
the group element that O represents. This will be the case if and only if |gλ| = |g| + 1

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

13

and |gλµ| = |gλ| + 1 for each µ ∈ S with µ < λ−1 . We test this using the functions lλ ,
doλ and lµ . During the depth first search, we keep track of the distance d = |g|, where g is
the group element represented by O. Now, to calculate the number numloops of loops of
length 2n, we first set numloops = 0, then run the depth first search, and when we visit
each vertex of Tn , add numpaths(O, d)2 to numloops. At the end of this process numloops
is equal to the number of loops of length 2n, so we return numloops and terminate the
algorithm.
The advantage of this algorithm is that it only stores Tk and An−k in memory, rather
than all of Tn . This also allows us to parallelise step 5.

2.4. Thompson’s group F . In this section we describe how the object O, the operation
doλ and the functions val and lλ are implemented for Thompson’s group F . We use the
standard generating set S = {a, b, a−1 , b−1 }, which yields the presentation
F = ha, b|a2 ba−2 = baba−1 b−1 , a3 ba−3 = ba2 ba−2 b−1 i.
For O we use the forest representation given by Belk and Brown in [2]. We simultaneously
store the forest diagram as a graph P as well as a pair of binary strings a, b. A forest
diagram is defined as a pair of sequences of binary trees, with one tree highlighted in each
sequence. A single binary tree with m leaves corresponds to a unique binary string s of
length 2m − 2 with the property that s has an equal number of 1’s and 0’s and the number
of 1’s in any initial substring is at least equal to the number of 0’s in that substring. This
is defined by doing a depth first search of the tree and writing a 1 whenever we move
down an edge from a vertex to its left subtree and writing a 0 whenever we backtrack
along such an edge. Now to convert a sequence of binary trees to a binary string, we first
convert each individual tree to a binary string, insert the string 01 before each such string,
then concatenate the results. We then change the 01 before the string corresponding to
the highlighted tree to 00. This is how the strings a and b are defined. We also store
the numbers pa and pb in O, which define the positions of the 00 before the highlighted
tree in each of a and b. The strings a and b each have length at most 2n, so they can be
represented as 64 bit numbers as long as n ≤ 32. The operation doλ is defined easily for the
effect on the graph P . The effect on the binary strings a and b is a bit more complicated
and requires some bit shifting. The entire length of an element of Thompson’s group F
can be determined by its forest diagram, as shown in [2], so we could use this to determine
lλ by using the graph P and simply subtracting the calculated length |g| from the length
we calculate for |gλ|. In fact we do it more efficiently than this, as the difference |gλ| − |g|
is determined entirely by the highlighted tree and the surrounding trees. Finally, val(O)
simply returns the pair (a, b).
In Table 2 we give the first 32 coefficients of the cogrowth generating function for Thompson’s group F. This is 7 further terms than given in [18].

14

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Coefficients
1
4
28
232
2092
19884
196096
1988452
20612364
217561120
2331456068
25311956784
277937245744
3082543843552
34493827011868
389093033592912
4420986174041164
50566377945667804
581894842848487960
6733830314028209908
78331435477025276852
915607264080561034564
10750847942401254987096
126768974481834814357308
1500753741925909645997904
17833339046478612301547884
212663448005862463186139032
2544535423071442709522261116
30542557512715560857221200908
367718694478039302564802454628
4439941127401928226610731571976
53756708216952135677787623701460
Table 2. Terms in the cogrowth sequence of Thompson’s group F .

3. Possible cogrowth of Thompson’s Group
In this section we will show that if a0 , a1 , . . . is the cogrowth sequence for Thompson’s
group F , then for any real numbers a < 1 and λ > 1, the inequality
a

an < 16n λ−n

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

15

holds for all sufficiently large integers n. As a result, if Thompson’s group is amenable,
then the sequence cannot grow at the rate
a

16n λ−n ,
For any fixed a < 1. This result follows quite readily from results in [21] and [20], however
we will need some definitions before we can see how they apply. Let G be a group with
finite generating set S. Then we define the function φS : Z>0 → R>0 by setting φS (n)
to be the probability that a random walk in (G, S) of length 2n finishes at the origin. In
other words, |S|2n φS (n) is the number of loops of length 2n in the Cayley graph Γ(G, S).
Now, for two different (non-increasing) functions φ1 and φ2 , we say that φ1  φ2 , if there
is some C ∈ R>0 such that φ1 (n) ≤ Cφ2 (n/C), where each φi is extended to the reals by
linear interpolation. Finally we say that φ1 ≈ φ2 if both φ1  φ2 and φ2  φ1 . We recall
Theorem 3.1 from [20]:
Theorem 3.1. Let G be a group with finite, symmetric generating set S and let H be a
subgroup of G and let T be a finite symmetric generating set of H. Then
φS  φT .
The other result we need concerns wreath products with Z. In [21], Pittet and SaloffCoste show (in a remark just below Theorem 8.11) that for a finite generating set T of
Z od Z, we have


φT (n) ≈ exp −nd/(d+2) (log n)2/(d+2) .
Now, since Z od Z is a subgroup of Thompson’s group F , we must have


φS (n)  φT (n) ≈ exp −nd/(d+2) (log n)2/(d+2) ,
where S is the standard generating set of F . Hence, for any positive integer d, there is a
positive real number C such that


φS (n) ≤ C exp −(n/C)d/(d+2) (log(n/C))2/(d+2) .
Now we are ready to prove our theorem.
Theorem 3.2. Let an be the number of loops of length 2n in the standard Cayley graph
for Thompson’s group. Then for any real numbers a < 1 and λ > 1, the inequality
a

an < 16n λ−n
holds for all sufficiently large integers n.

d
> a. Then there is some C ∈ R>0 such
Proof. Let d be a positive integer such that d+2
that


φS (n) ≤ C exp −(n/C)d/(d+2) log(n/C)2/(d+2)

16

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

for all n ∈ Z>0 . For n sufficiently large, we have log(n/C) > 0, so




C exp −(n/C)d/(d+2) log(n/C)2/(d+2) <C exp −(n/C)d/(d+2)


= exp log(C) − C −d/(d+2) nd/(d+2) ,
Hence, for all n sufficiently large we have
φS (n) < exp(−nα ).
Therefore,
an = 16n φS (n) < 16n exp(−nα )

Note that the same result holds if we replace Thompson’s group F with the Navas-Brin
group B, since it also contains every wreath product Z od Z as a subgroup.
4. Moments
In [18], Haagerup, Haagerup and Ramirez-Solano prove that the cogrowth sequence
a0 , a1 , . . . for Thomson’s group F is the sequence of moments of some probability measure
µ on [0, ∞), in other words, the sequence is a Stieltjes moment sequence. In fact, their
proof applies to the cogrowth series of any (locally finite) Cayley graph Γ. In this section,
we generalise the result further, to any locally finite graph. First we give some background
on the Stieltjes and Hamburger moment problems.
4.1. Stieltjes and Hamburger moment sequences. In the following, for the sequence
(n)
a = a0 , a1 , . . ., and n ≥ 0, we define the matrix H∞ (a) by


an an+1 an+2 . . .
an+1 an+2 an+3 . . .


(n)
H∞
(a) = an+2 an+3 an+4 . . .


..
..
..
..
.
.
.
.
Theorem 4.1. (Stieltjes [23], GantmakherKrein [9] ) For a sequence a = a0 , a1 , . . ., the
following are equivalent:
• There exists a positive measure µ on [0, ∞) such that
Z
an = xn dµ(x).
(0)

(1)

• The matrices H∞ (a) and H∞ (a) are both positive semidefinite.
• There exists a sequence of real numbers α0 , α1 , . . . ≥ 0 such that the gnerating
function A(t) for the sequence a0 , a1 , . . . satisfies
∞
X
α0
A(t) =
an t n =
α1 t
1−
n=0
α2 t
1−
1 − ...

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

17

A sequence which satisfies the conditions of the theorem above is called a Stieltjes
moment sequence.
Theorem 4.2. For a sequence a = a0 , a1 , . . ., the following are equivalent:
• There exists a positive measure µ on (−∞, ∞) such that
Z
an = xn dµ(x).
(0)

• The matrix H∞ (a) is positive semidefinite.
A sequence which satisfies the conditions of the theorem above is called a Hamburger
moment sequence. From either definition of Hamburger moment sequence, it follows immediately that any Stieltjes moment sequence is a Hamburger moment sequence. Carleman’s
condition states that the measure µ is unique if
∞
X

−

1

a2n2n = +∞,

n=0

This is certainly true when the sequence grows at most exponentially, as is the case for all
of our examples. For Stieltjes moment sequences, the following weaker condition implies
that the measure µ is unique:
∞
X
− 1
an 2n = +∞.
n=0

For a Hamburger moment sequence a, which grows at most exponentially, the radius of
convergence of A(t) = a0 + a1 t + a2 t2 + . . . is equal to
1
.
|µ|
In particular, this means that if a is a Stieltjes moment sequence, the exponential growth
rate of the sequence is equal to the minimum value in the support of µ.
One benefit of proving that a sequence a is a Stieltjes moment sequence is that it allows
us to compute good lower bounds for the exponential growth rate of the sequence using
only finitely many terms. This method was described in [18], but we repeat the description
here, using the continued fraction form of a. We consider the generating function
∞
X

α0
.
α1 t
1−
n=0
α2 t
1−
1 − ...
Using the terms a0 , . . . , an , we calculate the terms α0 , . . . , αn . It is easy to see that A(t)
is nondecreasing in each αj . Hence, the minimum possible value An (t) is achieved by
setting αn+1 , αn+2 , . . . to 0. Therefore, the radius of convergence tc of A(t) is bounded
above by the radius of convergence tn of An (t). Therefore, bn = 1/tn is a lower bound
for the exponential growth rate of a. It is easy to check that the sequence b1 , b2 , . . . is
A(t) =

an tn =

18

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

nondecreasing, and bnn > an /a0 . It follows that this sequence of lower bounds converges to
the exponential growth rate of a.
If we assume further that the sequences α0 , α2 , α4 , . . . and α1 , α3 , . . . are non-decreasing,
as seems to be true for many of the cases we consider, we can get stronger lower bounds
for the growth rate by setting αn+1 , αn+3 , . . . to αn−1 and αn+2 , αn+4 , . . . to αn . For this
√
√
sequence the exponential growth rate of corresponding sequence a is ( αn + αn−1 )2 .
4.2. Applications of moments to the cogrowth series. Here we describe how to
compute lower bounds for the growth rate of the cogrowth sequence of Thompson’s group
F.
Theorem 4.3. Let Γ be a locally finite graph with a fixed base vertex v0 . For each n ∈ Z≥0 ,
let tn be the number of loops of length n in Γ which start and end at v0 . Then there exists
a probability measure µ on R such that for each n ∈ Z≥0 , the nth moment of µ is given by
Z ∞
xn dµ = tn .
−∞

In other words, t0 , t1 , . . . is a Hamburger moment sequence.
Proof. The sequence t = t0 , t1 , . . . is a Hamburger
matrix

t0 t1 t2
t1 t2 t3

(0)
H∞
(t) = t2 t3 t4

.. .. ..
. . .

moment sequence if and only if the

...
. . .

. . .

..
.

is positive semidefinite. To prove this, we will show that this is the matrix representation
of a positive definite bilinear form.
Let M be the inner product space over R defined by the orthonormal basis {bv |v ∈ V (Γ)}.
For each n ∈ Z we let xn ∈ M be the element defined by
X
xn =
pv bv ,
v∈V (Γ)

where pv is the number of paths of length n in Γ from v0 to v. Then it is easy to see that
for any non-negative integers m and n, the value hxn , xm i is equal to the number tm+n of
paths of length m + n in Γ from v0 to itself. Now let X be the subspace of M spanned by
{x0 , x1 , . . .}. Then A is the matrix representation of the inner product h, i, restricted to X,
(0)
with respect to the spanning set {x0 , x1 , . . .}. Therefore, H∞ (t) is positive semidefinite.
(0)
Note that if {x0 , x1 , . . .} are linearly independent, then H∞ (t) is positive definite.

Theorem 4.4. Let C ∈ Z>0 and let Γ be a graph with a fixed base vertex v0 , such that
each vertex in Γ has degree at most C. For each n ∈ Z≥0 , let tn be the number of loops of
length n in Γ which start and end at v0 . There exists a probability measure µ on R>0 such
that for each n ∈ Z≥0 , the nth moment of µ is equal to t2n . In other words, t0 , t2 , t4 , . . . is
a Stieltjes moment sequence.
Moreover, µ is unique and its support is contained in the interval [0, C 2 ].

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

Proof. In order to show that the sequence s = t0 , t2 , t4 , . . . is a
it suffices to prove that the two matrices



t0 t2 . . .
t2
t2 t4 . . .
t4
(0)
(1)
H∞ (s) = 
 and H∞ (s) = 
.. .. . .
..
.
. .
.
are positive semidefinite. From the previous theorem,

t0 t1 t2
t1 t2 t3

(0)
H∞
(t) = t2 t3 t4

.. .. ..
. . .

19

Stieltjes moment sequence,

t4 . . .
t6 . . .

.. . .
.
.

we know that the matrix

...
. . .

. . .

..
.
(0)

is positive semidefinite. Hence any principal submatrix of H∞ (t) (using the same rows
(0)
(1)
and columns) is also positive semidefinite. Since both the matrices H∞ (s) and H∞ (s)
(0)
are such principal submatrices of H∞ (t), each of these matrices is positive semidefinite.
Therefore, the sequence t0 , t2 , t4 , . . . is a Stieltjes moment sequence. Now, since each vertex
of the graph has degree at most C, the number of paths of length n is at most C n . Hence
we have the inequality
Z
∞

xn dµ = t2n ≤ C 2n .

0

Therefore, the support of µ must be contained in the interval [0, C 2 ]. This also implies
that µ is unique.

In particular, if we let G be a finitely generated group, with inverse closed generating
set S, and Γ be the corresponding Cayley graph, then the even terms of the cogrowth
sequence for Γ form a Stieltjes moment sequence. Moreover, each vertex has degree |S| so
the support of the corresponding measure µ is contained in the interval [0, |S|]. As described
in the previous subsection, we can compute lower bounds bn for the exponential growth rate
of any such sequence. Turning our attention to Thompson’s group, using 31 terms of the
cogrowth sequence, we have computed the corresponding terms α0 , α1 , . . . , α31 . Using these
we have computed the rigorous lower bound b31 ≈ 13.269 for the exponential growth rate
of the cogrowth sequence of Thompson’s group. If we assume that the sequences α0 , α2 , . . .
√
√
and α1 , α3 , . . . are increasing, we get the stronger lower bound ( α30 + α31 )2 ≈ 13.706.
In Section 8 below we extrapolate the sequence of bounds {bn } to estimate the growth
constant µ, and find µ ≈ 15.0.
5. Series Analysis
We have series for six groups, which we will consider in order. Firstly, the group Z2 ,
then the Heisenberg group, the lamplighter group L = Z2 o Z, the two groups Z o Z and
(Z o Z) o Z, the Navas-Brin group B [19, 4] and finally Thompson’s group F . We will analyse
each of these in turn.

20

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

In all cases our initial analysis is based on the behaviour of the ratio of successive terms,
with other methods deployed as appropriate. In the simplest situation we consider, which
is when the asymptotic form of the coefficients is cn ∼ c · µn · ng , one has that the ratio of
successive coefficients is asymptotically linear when plotted against 1/n, as

 
g
1
cn
=µ 1+ +o
.
(12)
rn =
cn−1
n
n

It is therefore natural to plot the ratios rn against 1/n. If the correction term o n1 can be
ignored3, such a plot will be linear, with gradient µ · g, and intercept µ at 1/n = 0. If the
growth constant µ is known, or can be guessed, better estimates of the exponent g can be
made by extrapolating the sequence
gn = (rn /µ − 1) · n = g + o(1).
More complicated asymptotic forms for the coefficients can give rise to different expressions for the ratios, as we show below.
5.1. The group Z2 . For the group Z2 , the coefficients of the cogrowth series are known
2
exactly, cn = 2n
n , and so the ratio of successive terms is


1
cn
1
rn =
= 16 1 − + 2 .
cn−1
n 4n
A plot of the ratios against 1/n is shown in Figure 1, based on the first 50 coefficients.
It is clearly going to the expected limit of 16. The exponent g should be −1, and we plot
estimators gn against 1/n in Figure 2, which is also clearly going to the expected limit −1.
This corresponds to a logarithmic singularity of the generating function,
CZ2 (x) ∼ c · log(1 − 16x).
For this simple example one can do much better by using the package gfun, available
in Maple, and asking for the underlying ordinary differential equation for the generating
function, given the first 20 or so coefficients. In this way one immediately obtains the result
for the generating function
 √ 
X
4 x
n
cn x = 2K
,
CZ2 (x) =
π
where K is the complete elliptic integral of the first kind.
5.2. The Heisenberg group. We have calculated 90 terms of the generating function,
and show that this is sufficient to obtain a very precise asymptotic representation of the
coefficients. The leading order asymptotics of the coefficients is known [10] to be cn ∼
16n /(2n2 ), corresponding to a generating function
1
CHeisenberg ∼ (1 − 16x) log(1 − 16x).
2
We have analysed this series in the same way as described above for the group Z2 .
3In the simplest cases, such as the present one, the correction term will be O

1
n2



.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

21

Figure 1. Plot of Z2 ratios against 1/n.

Figure 2. Estimators of exponent g for Z2
vs. 1/n.

Figure 3. Plot of Heisenberg group ratios
against 1/n.

Figure 4. Estimators of exponent g for
the Heisenberg group vs. 1/n.

A plot of the ratios against 1/n is shown in Figure 3. It is clearly going to the expected
limit of 16. The exponent g should be −2, and we plot estimators gn against 1/n in Figure
4, which are also clearly going to the expected limit −2.

22

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

In order to obtain higher-order asymptotic terms, we subtract the known leading-order
term from the coefficients, forming the sequence
c(1) (n) = cn − 16n /(2n2 ).
A ratio analysis of this sequence strongly suggests that c(1) (n) ∼ const/n, implying that
cn ∼ 16n /(2n2 )+const./n3 . Such behaviour is consistent with a simple algebraic singularity
of the generating function. Accordingly, we attempted a linear fit to the assumed form
cn /16n = 1/(2n2 ) + k1 /n3 + k2 /n4 + k3 /n5 . We did this by solving the linear system given
by setting n = m − 1, n = m, n = m + 1 in the preceding equation, and solving for
k1 , k2 , k3 , with m ranging from 20 to the maximum possible value 89. We obtain an
m-dependent sequence of estimates of the amplitudes k1 , k2 , k3 , which we extrapolated
against appropriate powers of 1/m.
In this way we estimate k1 = 0.93341, k2 = 1.530, and k3 = 3.30, where we expect errors
in these estimates to be confined to the last quoted digit.
To summarise, we find the asymptotics of the coefficients of the cogrowth series of the
Heisenberg group to be
 

1
0.93341 1.530 3.30
1
n
.
+
+
+ 5 +O
cn = 16
2
3
4
2n
n
n
n
n6
5.3. The lamplighter group. The lamplighter group L is the wreath product of the
group of order two with the integers, L = Z2 o Z. From [22] we know that for this group,
(13)

cn ∼ c · 9n · κn

1/3

· n1/6 .
1/3

So in this example we see the presence of a stretched-exponential term, κn , which
makes the analysis more difficult. As remarked above, we have generated 201 terms of
the cogrowth series, and show how these terms can be used to estimate the asymptotic
behaviour of the coefficients.
If the coefficients of a series include a stretched-exponential term, so that
σ

an ∼ c · µn · κn · ng ,
with 0 < σ, κ < 1, then the ratio of successive terms behaves as


σ log κ g
an
rn =
∼ µ 1 + 1−σ + + · · · .
an−1
n
n
Experimentally, the presence of such a stretched-exponential term is signalled by the fact
that the ratio plots against 1/n exhibit curvature, and that this curvature can be eliminated,
or at least substantially reduced, by plotting the ratios against 1/n1−σ , where σ is roughly
estimated by choosing its value so as to maximise linearity. This theory is developed in
greater detail, along with several examples, in [14].
Because of the presence of two terms in the ratio plots, one of order O(nσ−1 ) the other
of order O(1/n), there is some competition between these two terms, which can make it

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

23

difficult to estimate the value of σ just from the linearity of the ratio plots. So we first
eliminate the O(1/n) term by calculating the modified ratios
 

1
σ 2 log κ
(1)
.
(14)
rn = n · rn − (n − 1) · rn−1 = µ 1 + 1−σ + o
n
n
In Figure 5 we show the modified ratios plotted against 1/n2/3 , which is seen to be linear,
and extrapolating to the known
√ growth constant of 9. While not shown, we also plotted
the modified ratios against 1/ n and against 1/n3/4 . These were visibly convex upward
and concave downward, respectively. One would conclude that 1/2 < σ < 3/4, and bearing
in mind that in all known such behaviour, σ is a simple rational fraction (arguably simply
related to dimensionality), one would conjecture that κ = 2/3. However, we can also
estimate the value of σ by other means.

Figure 5. Modified lamplighter group ratios vs. n−2/3 .
(1)

If we assume µ = 9, then from (14) it follows that a plot of ln = log |1 − rn /µ| against
log(n) should be linear with gradient σ − 1. This plot (not shown) is indeed visually linear.
To calculate the gradient, which will vary slightly with n, we calculate the local gradient
(ln − ln−1 )/(log(n) − log(n − 1)), and show this plotted against 1/n4/3 in Figure 6. This
plot is clearly going to a limit very close to −2/3, as expected.
One can also find estimators for the exponent σ without assuming or knowing the value
of the growth constant µ. Taking the ratio of the modified ratios eliminates the growth
constant µ, so that
(1)

rn(2) =

rn

(1)

rn−1

=1−

σ 2 (1 − σ) log κ
+ o(nσ−2 ).
n2−σ

24

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure 6. Estimates of σ − 1 vs. n−4/3 .

Figure 7. Estimates of σ − 2 vs. n−2/3 .

(2)

So a plot of log |rn − 1| against log n should be linear with gradient σ − 2. As above,
we don’t show this uninteresting linear plot, but instead show the local gradient, plotted
against 1/n2/3 , in Figure 7, which appears to be going to a value around −1.67, consistent
with the known exact value −5/3.
Assuming the values µ = 9, and σ = 1/3, we estimate the remaining parameters in
the asymptotic expression by direct fitting to the logarithm of the coefficients. From
1/3
cn ∼ c · 9n · κn · ng we get
log cn − n · log 9 ∼ n1/3 · log κ + g · log n + log c.
As in the preceding analysis of the Heisenberg group coefficients, we fit successive triples
of coefficients to get estimates of the three unknowns, log κ, g and log c. The results are
shown in Figures 8, 9, and 10 respectively.
From these plots, we estimate log κ ≈ −2.78, g ≈ 0.17, and log c ≈ −0.6. If we use the
fact that we know that the exponent g = 1/6, we can get refined estimates of the remaining
parameters, giving log κ ≈ −2.775, and log c ≈ −0.55, so that κ ≈ 0.0623, and c ≈ 0.58.
As far as we are aware, these two constants have not previously been estimated.
5.4. Analysis of group Z o Z. As discussed in the introduction, for the groups Z od Z,
there is an additional logarithmic factor associated with the stretched-exponential term.
For d = 1 the group Z o Z has coefficients that behave as
an ∼ const · µn · κn

σ

logδ n

· ng , with σ = 1/3 and δ = 2/3.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

25

Figure 9. Estimates of
Figure 8. Estimates of log κ exponent g vs. 1/n. The Figure 10. Estimates
vs. 1/n.
log c vs. n−2/3 .
exact value is 1/6.

of

It follows that the ratio of successive coefficients behaves as
(15)

an
σ · log κ · logδ n δ · log κ · logδ−1 n g
rn =
∼µ 1+
+
+ + ···
an−1
n1−σ
n1−σ
n

!
.

We have generated series to order x276 for this group. A simple ratio plot against 1/n is
strongly concave downwards. Plotting the ratios against 1/n2/3 gives a plot which is√much
closer to linear, but still displays a slight concavity. A simple ratio plot against 1/ n by
contrast, displays slight convexity.
As we noted in our analysis of the lamplighter group, the term g/n in eqn. (15) also
makes a contribution (as does the logarithmic term logδ n), so a clearer picture emerges if
this term is eliminated, which we do by forming the modified ratios (14), which behave in
this case as



log κ  2/3
−1/3
−4/3
−5/3+
(1)
n − 2 log
n + o(n
) .
(16)
rn = µ 1 + 2/3 log n + 4 log
9n
√
Plots of the modified ratios are shown in Figures 11, 12, and 13, against 1/ n, 1/n2/3
and 1/n3/4 respectively. It is clear that the plot against 1/n2/3 is the closest to linear,
corresponding to κ = 1/3. However, there is still some downward concavity, due to the associated logarithmic terms.
 To see this even more clearly, weshow in Figure 14 a plot of the
modified ratios against log2/3 n + 4 log−1/3 n − 2 log−4/3 n /n2/3 , which is the expected
asymptotic behaviour, see (16). This is indistinguishable from linearity.
To date we haven’t tried to estimate µ, known to be exactly 16. One way to do this is
from the modified ratio plots shown above. All are seen to be tracking towards a value
very close to 16.
It is also possible to estimate the exponent σ directly from the ratios, even without
knowing the dominant exponential growth constant µ. One first forms the ratio of successive

26

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure
11. Modified ratios for Z o Z vs.
√
1/ n.

Figure 12. Modified ratios for Z o Z vs.
n−2/3 .

Figure 13. Modified ratios for Z o Z vs.
n−3/4 .

Figure
14. Modified ratios for Zo Z vs.

2/3
log n + 4 log−1/3 n − 2 log−4/3 n n−2/3 .

ratios, so that
(17)

rrn(1)

=

rn
rn−1

log κ · logδ n
= 1+
n2−σ




δ(2σ − 1) δ(δ − 1)
g
σ(σ − 1) +
+
− 2 + o(1/n2 ).
2
log n
n
log n

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

27

As we did above with the ratios, we eliminate the O(1/n2 ) term by constructing a
modified ratio-of-ratios,
(1)

(18)

rrn(2) =

(1)

n2 rrn − (n − 1)2 rrn−1
c log δ n
= 1 + 2−σ (1 + O(1/ log n)) ,
2n − 1
n

where the constant c = (σ 2 (σ − 1) log κ)/2.
(2)
Then a plot of log |rrn − 1| against log n should be close to linear, as the logarithmic
term will vary very slowly over the range of n-values at our disposal, with gradient σ − 2.
Such a plot (not shown) is visually linear, but in order to calculate the gradient we find
(2)
(2)
the (local) gradient of the segment joining rrn and rrn−1 , which should approach the
“correct” value as n increases. This is shown, plotted against 1/n in Figure 15. It appears
to be going to a limit around −1.62 to − 1.61, which would imply σ ≈ 0.38 or 0.39, rather
than the known value of 1/3.

Figure 15. Estimators of exponent σ − 2 vs. 1/n.
However, if we assume we know that δ = 2/3, and include the confluent logarithmic
term log2/3 n in the exponent of the stretched-exponential term, plotting instead
!
(2)
rn − 1
log
log2/3 n
against log n, the plot is again visually linear. However the corresponding plot of the local
gradient, shown in Figure 16, is clearly going to a limit around −5/3, consistent with the
known value σ = 1/3.

28

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure 16. Estimators of exponent σ − 2
vs. 1/n, assuming a confluent logarithmic
term.

Figure 17. Estimates of log κ vs. 1/n.

Assuming the values µ = 16, and σ = 1/3 and κ = 2/3, we can estimate the remaining
parameters in the asymptotic expression by direct fitting to the logarithm of the coefficients.
2/3
1/3
From cn ∼ c · 16n · κn log n · ng we get
log cn − n · log 16 ∼ n1/3 · log2/3 n · log κ + g · log n + log c.
As in the preceding analysis of the lamplighter group coefficients, we fit successive triples
of coefficients to get n−dependant estimates of the three unknowns, log κ, g and log c. The
results are shown in Figures 17, 18, and 19 respectively.
From these plots, we estimate log κ ≈ −1.64, but it is difficult to estimate g. It appears
to be quite small, close to zero, and could even be negative. It is even more difficult to
extrapolate the plot for log c, though one might conclude the bound log c ≥ −2. These
estimates correspond to κ ≈ 0.194, g ≈ 0, and c > 0.13. As far as we are aware, these three
constants have not previously been studied.
In anticipation of our analysis of Thompson’s group F, where the growth constant µ
is not known, we attempt to estimate both the exponents σ and δ without knowing the
value of µ. Forming the ratios (15) eliminates the constant c in the asymptotic form of the
coefficients, and the ratio of ratios (17) eliminates µ. If we now form the sequence
(1)

(19)

tn =

rrn − 1
(1)

rrn−1 − 1

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

Figure 18. Estimates of exponent g vs.
n−1/3 .

29

Figure 19. Estimates of log c vs. n−1/3 .

this eliminates the base κ of the stretched-exponential term, and in fact
n(tn − 1) ∼ σ − 2 +

δ
.
n log n

So plotting n(tn − 1) against 1/(n log n) should give an estimate of σ − 2. To estimate δ,
we form the sequence
n log2 n(n(tn − 1) − (n − 1)(tn−1 − 1)) ∼ −δ + O(1/ log n).
We show these plots in Figures 20 and 21 respectively. The estimate of σ − 2 appears to
be going to a limit of around -1.6 or below, c.f. the known exact value of −5/3, while the
estimate of δ is harder to estimate, but the plot is certainly consistent with the known
value 2/3. As can be seen, this exponent is difficult to estimate without many more terms
than we currently have.
5.5. Analysis of group (Z o Z) o Z. For this group we have 132 terms in the cogrowth
series, just less than half the number we have for Z o Z, so the results are not quite as
precise. We analysed this series the same way as for the group Z o Z. For this group it is
known that the coefficients grow exponentially, and that the dominant term is 36n . The
1/2
1/2
sub-dominant term is κn log n , which again follows from Theorem 3.11 in [21]. Again,
there is presumably a sub-sub dominant term ng .
In this case we have for the ratio of successive terms:
!
an
log κ log1/2 n
log κ
g
(20)
rn =
∼µ 1+
+
+ + ··· .
an−1
2n1/2
2n1/2 log1/2 n n

30

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure 20. Estimates of σ − 2 vs.
1/(n log n)

Figure 21. Estimates of exponent −δ vs.
1/ log n.

We eliminate the O(1/n) term by forming the modified ratios (14) which behave as

(21)

rn(1)



log κ p
−1/2
−3/2
−3/2+
log n + 2 log
n − log
n + o(n
) .
=µ 1+ √
4 n


First, we remark that extrapolating the ratios against 1/n gives a plot with considerable
curvature (not shown). We plotted the modified ratios, defined above, against 1/nσ for
several values of σ. We show the results for σ = 1/2 and σ = 1/3 in Figures 22 and 23
respectively. Surprisingly, the latter is closer to linear, however it extrapolates to a value
of µ rather larger than the actual value, µ = 36. However if we include the effect of the
logarithmic
term in the exponent, and plot (see equation (21)) the modified ratios against
q
log n
n ,

the modified ratio plot, shown in Figure 24, is indistinguishable from linearity and
extrapolates to the correct value of µ.
Repeating the analysis of the previous section, we attempted to estimate the exponent σ
(2)
without assuming the value of the growth constant µ. A plot of log |rrn − 1| (18) against
log n should be close to linear, (as the logarithmic term will vary only slowly over the range
of n-values at our disposal), with gradient σ − 2. Such a plot (not shown) is visually linear,
but in order to calculate the gradient we find the (local) gradient of the segment joining
(2)
(2)
rrn and rrn−1 , which should approach the “correct” value as n increases. This is shown,
plotted against 1/n in Figure 25. It appears to be going to a limit below −1.42 which
would imply σ < 0.58, compared to the known value of 1/2.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

31

√
Figure 22. Modified ratios for (Z o Z) o Z vs. 1/ n.

Figure 23. Modified ratios for (Z o Z) o Z
vs. n−1/3 .

Figure
p 24. Modified ratios for (Z o Z) o Z
vs. log n/n.

However, if we assume we know that δ = 1/2, and include the confluent logarithmic
term log1/2 n in the exponent of the stretched-exponential term, plotting instead
!
(2)
rn − 1
log
log1/2 n

32

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure 25. Estimators of exponent σ − 2
vs. 1/n.

Figure 26. Estimators of exponent σ − 2
vs. 1/n, assuming a confluent logarithmic
term.

against log n, the plot is again visually linear. Moreover the corresponding plot of the local
gradient, shown in Figure 26, is going to a limit around −3/2, consistent with the known
value σ = 1/2.
Assuming the values µ = 16, σ = 1/2 and κ = 1/2, we can estimate the remaining
parameters in the asymptotic expression by direct fitting to the logarithm of the coefficients.
1/2
1/2
From cn ∼ c · 36n · κn log n · ng we get
log cn − n · log 36 ∼ n1/2 · log1/2 n · log κ + g · log n + log c.
As in the preceding analysis of Z o Z, we fit successive triples of coefficients to get estimates
of the three unknowns, log κ, g and log c. The results for the first two are shown in Figures
27 and 28 respectively. From this, and further analysis with an additonal term in the
assumed asymptotic form, we estimate log κ ≈ −2.3 and g ≈ 3.3.
Again repeating the analysis of the previous section, we tried to estimate σ and δ directly
without knowing µ or κ. Plotting n(tn − 1) (19) against 1/(n log n) should give an estimate
of σ − 2, and plotting the sequence n log2 n(n(tn − 1) − (n − 1)(tn−1 − 1)) against 1/ log n
should give estimates of −δ. We show these plots in Figures 29 and 30 respectively. The
estimate of σ − 2 appears to be going to a limit of below -1.39 or so, c.f. the known exact
value of −1.5, while it is not possible to estimate δ from this plot, but it is not inconsistent
with the known value 1/2.
5.6. The group Z od Z. In the previous sections we have considered the analysis of the
groups Z od Z for d = 1 and d = 2. We have shown how the stretched-exponential term
slows the rate of convergence of the ratios, but that appropriate analysis can still reveal

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

33

√
Figure 27. Estimates of log κ vs. 1/ n.

Figure
28. Estimates of exponent g vs.
√
1/ n.

Figure 29. Estimates of σ −2 for (ZoZ)oZ
vs. 1/(n log n)

Figure 30. Estimates of exponent δ for
(Z o Z) o Z vs. 1/ log n.

much asymptotic information. However as d increases, it becomes increasingly difficult to
extract the asymptotics from a hundred or so terms of the cogrowth series. To see this, we

34

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

consider the case d = 98. Then we know the asymptotic form of the coefficients is
σ

cn ∼ c · µn · κn

logδ n

· ng ,

where σ = 49/50 and δ = 1/50 [21].
While we could have generated 100 or so terms of this series from the algorithms described above, it will be more instructive to generate a test series with the given asymptotic
behaviour, as then we can generate thousands of terms essentially immediately.
δ
σ
So we have generated coefficients defined by cn = c · µn · κn log n · ng with c = 1, µ = 4,
κ = 0.7, g = 0.5, σ = 49/50 and δ = 1/50. The ratio of successive terms must go to 4.0,
the value of the growth constant4. Using 128 terms of this test series, we show a plot of
the ratios against 1/n in Figure 31. It is not possible to assert that, as n → ∞ the ratios
will go to 4.0. In Figure 32 we show the same plot with 1280 terms. While this curve
is steeply increasing, it is still not possible to assert that the limiting value is 4.0. Using
10000 terms, and plotting the ratios against 1/n1/50 (not shown), we finally see evidence
that the extrapolated limit is around 3.8 or 3.9.

Figure 31. The first 128 ratios for Z o98 Z
vs. 1/n.

Figure 32. The first 1280 ratios for Z o98 Z
vs. 1/n.

For this series the asymptotic form of the ratios is


49 log κ
0.5
rn = µ 1 +
+
+ o(1/n) ,
n
50 · n1/50
so we might expect more informative results if we eliminate the term O(1/n), which we
can do by forming the modified ratios. These are shown, plotted against 1/n1/50 in Figures
4The growth constant is actually 4(d + 1)2 , but for this exercise the actual value is irrelevant, so we have

chosen a much smaller value.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

35

33 and 34, based on the first 128 terms and the first 10000 terms. Extrapolating these to
n → ∞ again gives a limit around 3.9.

Figure 33. The first 128 modified ratios
for Z o98 Z vs. n−1/50 .

Figure 34. The first 10000 modified ratios
for Z o98 Z vs. n−1/50 .

It is possible to estimate the exponent σ without knowing µ, as we showed in previous
examples above. In particular, using the method based on equation (17), and described
immediately below that equation, we show in Figure 35 a plot of estimators of σ −2 against
1/n, based on a 10000 term series, and it is persuasively going to the known value −1.02.
Unfortunately, for no interesting problem is it realistic to get 10000 terms, so this example, and the next, must remain as a cautionary tale, to the extent that there can and
do exist groups whose cogrowth series exhibit asymptotic behaviour that is difficult to estimate by numerical methods of the type we have considered. Another example of similar
difficulty is given by the Navas-Brin group B, discussed in the next section.
6. Series extension
In this section we develop one further tool that will be extremely useful in our analysis
of the series for Thompson’s group F, where we have only 32 terms, rather than a hundred
or more as in the examples we have been considering. It will also be very helpful in our
analysis of the Navas-Brin group B, discussed in the next section.
Recall that our analysis of the more complex asymptotic forms that include stretchedexponential terms is based on ratios of successive terms, whereas for simpler groups, with
simpler asymptotics, we used the method of differential approximants (DAs). It is obviously
highly desirable to have further terms (in particular, further ratios), for all series with nonsimple asymptotics, and particularly in those cases where we have comparatively short

36

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

Figure 35. Estimators of σ − 2 for Z o98 Z against 1/n for n ≤ 10000.

series, such as the 32 term series we have for Thompson’s group F. In order to obtain further
ratios (or terms), we use the method of differential approximants to predict subsequent
ratios/terms. The detailed description as to how this is done is given in [15].
We will give two demonstrations of the effectiveness of this method. In the first, we take
the first 32 terms of the series for Z o Z discussed above, (we have more than 200 terms for
this series), and use these to predict the next 89 ratios, from 5th order DAs. As well as
the mean ratio, we calculate the standard deviation. We show, in Table 3, a comparison
between the actual error in the predicted ratios and the standard deviation of the estimated
ratios. It can be seen that the true error lies between 1 and 1.5 standard deviations, which
provides some confidence that the predicted ratios are accurate to within an error of 1.5
standard deviations.
For the series simulating the coefficients of the group Zo98 Z, we showed the importance of
long series to reveal the asymptotic behaviour with some precision. In this second example,
we take the first 100 terms of this series, and use them to predict the next 315 ratios. That
is, we estimate cn /cn−1 for n = 101 · · · 415.
To see how precisely these ratios can be predicted, we plot the difference between the
actual ratios and those calculated by 4th order differential approximants in Figure 36.
It can be seen that the error is less than 2 parts in 1020 for all n < 416. Just to make
this perfectly clear, given 100 coefficients, we have predicted the next 315 ratios with an
accuracy of some 20 significant digits.
In a similar fashion, using 4th order DAs, we were able to get 200 extra ratios for the
32-term series for Thompson group F. The maximum error (as estimated by 1.5 s.d. of the

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

Figure 36. Absolute error in predicted ratios of Z o98 Z for 100 < n < 416.
k
1
5
10
20
30
40
50
60
70
80
89

37

Figure 37. The first 128 modified ratios
of the Navas-Brin group B vs. 1/n.

Actual error 1 standard deviation
2.69 × 10−17
2.02 × 10−17
−13
1.14 × 10
7.85 × 10−14
−11
3.37 × 10
2.08 × 10−11
2.22 × 10−8
1.23 × 10−8
−7
9.63 × 10
5.39 × 10−7
−5
1.22 × 10
6.88 × 10−6
−5
7.59 × 10
4.73 × 10−5
3.13 × 10−4
2.23 × 10−4
−4
9.39 × 10
8.11 × 10−4
−3
2.44 × 10
2.44 × 10−3
−3
4.63 × 10
5.38 × 10−3

Table 3. Actual error in coefficient O(z 31+k ) and 1 standard deviation
from the mean of the estimated coefficient.

DAs) is 1 part in 4 × 10−5 , which is graphically imperceptible. In the Appendix we give
the (predicted) next 200 ratios, and their standard deviations.
7. Analysis of the Navas-Brin group B.
This is an amenable group introduced independently by Navas [19] and Brin [4], so we
call it the Navas-Brin group B, and is defined in subsection 2.2. It has 2 generators, so

38

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

the growth rate of the cogrowth sequence is 16. We gave a polynomial-time algorithm to
generate the coefficients above, and have used this to generate 128 terms of the co-growth
series. We then used the method of series extension, described above, to give a further 590
ratios, the last of which we expect to be accurate to 1 part in 5 × 10−7 , while all earlier
ratios will have a lower associated error. We first show a plot of the modified ratios (14)
against 1/n in Figure 37. Even if we knew nothing about the asymptotics of this group,
the curvature of this plot provides strong evidence for a sub-exponential term, and we have
proved that it cannot be a regular stretched-exponential term.
That is to say, the asymptotics for this series must grow more slowly than
σ

cn ∼ c · µn · κn · ng ,
where µ = 16, 0 < σ < 1, and 0 < κ < 1. Possible behaviour might be
cn ∼ c · µn · κn/ log n · ng ,
corresponding to a numerical value σ = 1, which of course hides the logarithmic component.
In that case the ratios will be


constant g
cn
+ + ··· .
∼µ 1+
rn =
cn−1
log n
n
Note that we do not insist the the first correction term is O(1/ log n), it could be a power
of a logarithm, or some other weakly decreasing function, but it cannot have a power-law
increase. For our purposes it suffices to take this term to be O(1/ log n). We show the
modified ratios (this gets rid of the O(1/n) term in the asymptotics) in Figures 38 and 39
which are the same plot, but the first uses only the 128 exact coefficients, while the second
uses the exact plus predicted ratios. From the first plot, it is clear that it would be an
article of faith that the locus is going to 16 as n → ∞. By contrast, the second plot makes
this conclusion far more plausible.
We next try and estimate the exponent σ, which should be 1, without assuming µ =
16. We use the method described below equation (17). With the 128 known terms, the
estimators of σ−2 are shown in Figure 40 and show no evidence of approaching the expected
value of −1. If however we use twice as many terms, so using the next 128 predicted ratios,
we get the plot shown in Figure 41, which is plausibly approaching −1.
This highlights the value of numerically predicting further terms wherever possible.
8. Analysis of Thompson’s group F
For Thompson’s group F it is known that the series grows exponentially like µn . If
µ = 16, the group is amenable. If it is amenable, there cannot be a sub-dominant term of
σ
the form κn with 0 < σ < 1, because the group contains the wreath products ZoZoZo· · ·oZ
as subgroups. This is a consequence of Theorem 1.3 in [20] and results in [21], and is proved
as Theorem 3.2 in Section 3.
We first study the modified ratios, defined by (14). The modified ratio plot against
1/n is shown in figure 42 and displays considerable curvature. By contrast, the same data
plotted against n−1/5 , and shown in figure 43 shows curvature in the opposite direction.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

39

Figure 38. The first 128 modified ratios
for the Navas-Brin group B vs. 1/ log n.

Figure 39. The first 718 modified ratios
for the Navas-Brin group B vs. 1/ log n.

Figure 40. Estimates of σ − 2 from 128
terms of the Navas-Brin group B.

Figure 41. Estimates of σ − 2 from 256
terms of the Navas-Brin group B.

This is strong evidence for the presence of a conventional stretched-exponential term of the
sort we have seen in our study of the lamplighter group and the family Wd . As mentioned
above, the presence of such a term is incompatible with amenability. This is our first piece

40

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

of evidence that the group is not amenable. Note too that this is quite different to the
behaviour observed for the coefficients of the Navas-Brin group B.

Figure 42. Modified ratios vs.
Thompson’s group F.

1/n for

Figure 43. Modified ratios vs. n−1/5 for
Thompson’s group F.

In our subsequent analysis, we use both the exact coefficients and the extrapolated
coefficients. While all extrapolated terms can be used in calculating the ratios, once one
calculates first and second differences, errors are amplified, and so fewer terms can be used.
That is why we quote the number of terms used for different calculations, as it is only to the
quoted order that we are confident that the calculated quantities are accurate to graphical
accuracy.
To estimate the exponents in the stretched-exponential term we use the procedure described in Section 5.4, given by eqn. (19) and subsequent equations. This procedure allows
for the presence of a confluent power of a logarithm, so that the stretched-exponential
δ
σ
term is κn log n . In this way, based on a series of length 80, we show plots of estimators of
2 − σ and −δ in Figures 44 and 45, plotted against 1/n. Extrapolating these, we estimate
σ ≈ 1/2, and δ ≈ 1/2. Recall that this is exactly the stretched-exponential behaviour of
(Z o Z) o Z.
√
Reverting to the modified ratios, briefly discussed above, we plot these against 1/ n in
figure 46, using 186 terms. One observes that the plot still p
displays a little curvature, but
in Figure 47 the plot of these same modified ratios against log n/n, is essentially linear.
This is the appropriate power to extrapolate against, given our estimates of the stretchedexponential exponents. Extrapolating this to n → ∞ we estimate the limit, which gives
the growth constant, to be 14.8 − 15.1. This is well away from 16, which would be required
for amenability.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

41

Figure 44. Estimators of σ−2 for Thompson’s group F vs. 1/n.

Figure 45. Estimators of −δ for Thompson’s group F vs. 1/n.

Figure 46. The first 186 modified
ratios
√
for Thompson’s group F vs. 1/ n.

Figure 47. The first 186 modified
ratios
p
for Thompson’s group F vs. log n/n.

One simple test for amenability uses the fact that the ratio of successive coefficients
asymptotes to the growth constant µ. For the lamplighter group, this ratio behaves as



c
1
(L)
rn = 9 1 + 2/3 + o
.
n
n2/3

42

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

For Z o Z one has
rn(2)

c · log2/3 n
+o
= 16 1 +
n2/3

log2/3 n
n2/3

!!
,

and for the triple wreath product, W2 , the corresponding result is
√
√


c log n
log n
(3)
+o
,
rn = 36 1 +
n1/2
n1/2
while for Thompson’s group F all we know is
rn = µ (1 + lower order terms) ,
where we suspect that the correction term is similar to that of the triple wreath product
of Z.
So, a simple test for amenability is to look at the three quotients
9rn
rn
4rn
, (2) , and
.
(L)
(3)
16rn
rn
9rn
If Thompson’s group F is amenable, these
p quotients should all go to 1. In Figures 48, 49,
50 we show these ratios plotted against log n/n, which is the appropriate power, though
this choice is not critical. The ratios do not appear to be going to 1 in any of the three
cases. For all cases we have used 200 ratios. To do this, we used the extended ratios
for Thompson’s group F and also extended the ratios for W2 from the known 132 ratios.
Indeed, all three cases are consistent with a limit around 0.93 ± 0.02, corresponding to
µ = 14.9 ± 0.3. This is entirely consistent with our previous estimate of µ ≈ 15.0.

Figure
48. Quotient
of Thompson group and
lamplighter group ratios
using 200 terms.

Figure 49. Quotient of
Thompson group and Z o Z
ratios using 200 terms.

Figure 50. Quotient of
Thompson group and (Z o
Z) o Z ratios using 200
terms.

Finally, we take the approach of extrapolating the lower bounds produced in Section 4.
√
Note that the sequence of bounds {bn } are bounds on µ. We have no expectation as to

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

43

how this sequence should approach its limit, so we first plot the bounds against 1/n in
figure 51. Some curvature is seen, which, as we have shown above, is evidence that the
locus behaves as


c2
c1
+ ··· .
bn ∼ b∞ 1 + α +
n
n
(1)
We remove the term O(1/n) in this case by forming the sequence bn = (n · bn − (n − 2) ·
bn−2 )/2 where we have shifted n by 2 to remove the effect of a small odd-even oscillation
√
(1)
if one shifts only by 1. We found that plotting bn against 1/ n gave a visually linear
plot, and this is shown in figure 52. Linearly extrapolating the last two entries gives the
estimate b∞ ≈ 3.875, so that µ ≈ 15.02, in agreement with previous estimates above.

Figure 51. Plot of bounds bn for Thompson’s group F against 1/n.

(1)

Figure 52. Plot of modified bounds
√ bn
for Thompson’s group F against 1/ n.

9. Conclusion
We have have given polynomial-time algorithms to generate terms of the cogrowth series
for several groups. In particular, we have given the first series for the Navas-Brin group B.
We have also given an improved algorithm for the coefficients of Thompson’s group F, giving
32 terms of the cogrowth series, extending previous enumerations by 7 terms. We analysed
these various series to develop numerical techniques to extract the asymptotics, and gave
improved asymptotics for the Heisenberg group. We gave an improved lower bound on the
growth-rate of the cogrowth series for Thompson’s group F, µ ≥ 13.2693 using the method
in [18]. We generalised their method, showing that the cogrowth sequences for all these
groups can be represented as the moments of a distribution. Extrapolation of the sequence
of bounds suggests the limit is around 15.0, which is incompatible with amenability.

44

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

For Thompson’s group F we proved that, if the group is amenable, there cannot be a
sub-dominant stretched exponential term in the asymptotics. The numerical data however
provides compelling evidence for the presence of such a term. This observation suggests a
potential path to a proof of non-amenability.
We have extended the sequence of 32 terms for group F by a further 200 terms (or, as
appropriate, 200 ratios of successive terms), which we demonstrate are sufficiently accurate
for the graphical approaches to analysis that we have taken.
A numerical study of the cogrowth sequence cn gives
σ

cn ∼ c · µn · κn

logδ n

· ng ,

where µ ≈ 15, κ ≈ 1/e, σ ≈ 1/2, δ ≈ 1/2, and g ≈ −1. The growth constant µ must be 16
for amenability. This estimate of the growth constant is the same as that obtained from
the extrapolated bounds. These three approaches to the study of amenabilty lead us to
the strong belief that Thompson’s group F is not amenable.
The difficulties we encountered in analysing Z o98 Z and the Navas-Brin group B does
imply that there do exist groups whose cogrowth series are difficult to analyse. Nevertheless, in both those cases we were able to extract the correct asymptotics. Furthermore, the
cogrowth series for Thompson’s group F did not behave like either of these two “difficult”
groups, and indeed appeared to have a stretched exponential term with exponent values
that were readily estimable. While we cannot rule out the presence of some previously
unsuspected pathology in the asymptotic form, we believe that we have presented strong
evidence for the belief that Thompson’s group F is not amenable
10. Appendix
Here are the (predicted) next 200 ratios for Thompson’s group F . That is, the first
ratio here is the coefficient of z 32 divided by the coefficient of z 31 . One standard deviation is 1.6 × 10−21 for the first ratio, 8.4 × 10−16 for the tenth ratio in this list, then
2.2 × 10−13 , 3.8 × 10−11 , 8.3 × 10−10 , 7.5 × 10−9 , 3.1 × 10−8 , 3.5 × 10−7 , 1.2 × 10−6 , 5.3 ×
10−6 , 3.3 × 10−5 , 9.0 × 10−5 , 1.3 × 10−4 , for the twentieth, thirtieth, fourtieth, fiftieth,
seventieth, ninetieth and hunderd and tenthth, hundred and thirtieth, hundred and fiftieth,
hundred and seventy-fifth and two hundredth ratios, respectively.

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS
12.139382519134640546100910550116506
12.227584513675824849745149961326117
12.306364858371755791208652657890394
12.377372393555580912478863352420963
12.441869014094574198504147444796094
12.500840543278316369259845344418039
12.555070835196117213101528584412301
12.605192754131413602669204643768679
12.651724136967118435759923721500215
12.695093725180061251425934047225685
12.735660229810914461533323666877360
12.773726591097905739200796016562265
12.809550810208112073629601806420114
12.843354291696056209817237940576090
12.875328347113943574400714300355914
12.905639332151085077301331779253254
12.934432723922797241056261010730083
12.961836439248190289410424756818502
12.987963464694516602362349323441444
13.012914070454692135046857458367114
13.036777659579423368614400305996310
13.059634066593784780607389266957567
13.081555222866179498657087709047136
13.102605564520384538741633073251136
13.122843467661052218534876988958406
13.142322234451185942341571946995161
13.161089481701929123360329350075889
13.179189107961895176661932566775513
13.196660991623399487925223492990383
13.213542543992015500848473483969209
13.229866114857320555465055797943269
13.245661794080940364573430988057957
13.260959939896671980546840767426691
13.275786005549024172548265823401768
13.290161972217217703156676577608563
13.304113073325880062519253728849004
13.317658188282116335265357329472658
13.330818453996063928243407490059108
13.343606937084326659382677923429016
13.356041865699128533066777923821716
13.368138079655518061737105379768840
13.379909230285796422796584282677189
13.391391013985309598551994527199420
13.402540990852287889254736126437580
13.413411407143425386912606665853825
13.424062672750839568072161252780645
13.434394074827496721484051571897707
13.444482843412927251038029918715121
13.454316759036914691255964338022543
13.463903116875215568913679808238264
13.473213802552343969176414720413487
13.482346421441562120101495301037430
13.491179584354353752611550171676095
13.499895368095523512785232116864023
13.508333602964302346321586079889387
13.516654351365134683610700727371316
13.525000203908312007517604856476096
13.532917871456062697723758553984577
13.540554273647847830847507251037425
13.548063007209007082860967768914526
13.555319528240038802193441194513629
13.562641374331046546303564833879801
13.569777875695742862069575716786180
13.576510610487748479571836167835301
13.584419560999735066923148194498099
13.590831265318841752277570171711095
13.596998211959713327539754998388164

12.169952350800835818835333877031972
12.254800541517346423861272221078461
12.330828666879163731631451465102197
12.399541172868336566805611620482939
12.462097792906309126366784632966479
12.519410149156226556638850314986873
12.572206972475257876321270606856264
12.621079365262119276409607772782102
12.666512975937091192133384667614540
12.708911355958942268539084708497350
12.748613234321123627064424451294341
12.785905507056272163479082083260714
12.821033151370240355220794516217934
12.854206894770548244369354384398327
12.885609214745162856554802222623966
12.915399101706732471897030527017181
12.943715839380256116094239676192280
12.970682107319771206377319240620875
12.996406405676872159827925022024219
13.020985259779764800684267751152161
13.044504679013068113321447729698093
13.067041693422999439936815568787524
13.088665732145507263332155324286416
13.109439117936998695729698444879843
13.129418244175823190427250023546405
13.148654712658935599802876138058446
13.167195007769142327138772890144629
13.185080837993801098011934614407469
13.202352151456208348963284966653968
13.219044110867187297414288617379158
13.235188321357468124261384585429120
13.250815166741899371063964386311321
13.265952758167346821144011231194731
13.280627056720430964223829034834261
13.294858653114477361638435828704210
13.308670446314943572746000301996392
13.322086115777917425146418299128619
13.335121539230967797838900373066820
13.347786320277756923575569080786819
13.360110874363270214471235529540315
13.372097273034426235102779701961991
13.383762909644345312962700551534152
13.395144666969365978147066024081715
13.406196253710405879515140382321201
13.416988156570367066227724319777381
13.427535999385894978339537743097391
13.437779418859588380431049420003005
13.447782268650965022269207427038709
13.457544856354882926610701767183908
13.467042454042638170007261022024409
13.476302647287223508754966768268084
13.485293318045282335887952362450478
13.494084747058831414056697557041621
13.502701722883121030342927584362952
13.511107842566379075799459233305947
13.519431847277609941232036080607544
13.527641315577516333811095751023520
13.535493461803957879581733368101521
13.543084323366200838300039176315332
13.550504412576211288095020257342519
13.557762668158072770433170818766971
13.564958044304722734009028672257896
13.572043884450805383578987603438786
13.578837748814414710933467280925295
13.586612599432547359359203779080153
13.592959911744010496809257658001969
13.599059952154497874738089781219857

12.199326127345853916009149880943422
12.281040527431431456883217428846113
12.354482413853570301131793493786704
12.421027974747801610713466511114207
12.481745360450139667192011174605863
12.537479148348791828180725386201064
12.588907920692053314139061768312908
12.636584558849435543137582196072181
12.680965096098118923436248549296051
12.722429798828036178804146087289492
12.761298847540600696316471357098745
12.797844188914176808112395397996995
12.832298623805456848288841282862554
12.864862864837654839427475941273709
12.895711085169493589386718357886965
12.924995323677800300649200885376963
12.952849018349319276368496909220240
12.979389881806587929393146535001536
13.004722173676474514325001997839461
13.028938801180381908385125175110548
13.052122569524550318903068986491322
13.074347966865955839456185038291272
13.095681797656212049861838152969811
13.116184350936469838871049112592397
13.135910414942072482775413880736439
13.154910018341609905494554223902216
13.173227515058212755159290331997399
13.190904563910270596599158822879997
13.207979050670762502542808795553103
13.224484921862603128812749940479344
13.240453522986667992419868738673504
13.255914147651533345355162750305551
13.270895130906341393601998277628536
13.285419125190171039873138415974114
13.299508767603123209430266638744025
13.313185140342015149024233508130128
13.326471695739198888194127423197993
13.339384163779883682357243658284554
13.351930748190988263794674502771721
13.364142777237566574247813605863778
13.376020835131593723786616298972917
13.387582311376027194727073026599142
13.398865377039202234681959848510147
13.409819665483104102788219559926390
13.420539883769483957581690933051480
13.430979699159296367928654845659964
13.441136013513055381428134566110019
13.451072044972393249466607491105591
13.460737144623883340126835494564910
13.470155360061132928954773338423225
13.479337389227819997111748990692973
13.488249148435842618350149753783486
13.497011084300140602722763616549800
13.505547791585498408392624616902183
13.513936036377083173562688008219201
13.522232264247358404187723455476999
13.530300873952004160088528545275672
13.538046382601181802194312557622836
13.545599058351387123157120673148797
13.552923260697021481475229482726246
13.560302341521164494357743132135167
13.567252292374466826596567631465810
13.574288148599622255870938533612831
13.581263278311749328511560181131020
13.588785775454742632035040598882148
13.594915982519419341022644469998104

45

46

ANDREW ELVEY PRICE AND ANTHONY J GUTTMANN

11. Acknowledgements
We wish to thank Andrew Rechnitzer for many stimulating discussions on this topic, and
Murray Elder for helpful comments on the manuscript. AJG wishes to thank Nathan Clisby
for his vastly superior version of the program to use differential approximants to predict
further terms and ratios. AEP wishes to thank ACEMS for financial support through a
PhD top-up scholarship.
References
[1] N Beaton, A J Guttmann, I Jensen and G Lawler, Compressed self-avoiding walks, bridges and polygons, J. Phys A: Math. Theor. 48 454001 (27pp) (2015).
[2] J Belk and K S Brown, Forest diagrams for elements of Thompson’s group F , Int. J. Alg. Comp. 15
815-850 (2005).
[3] S Blake Fordham, Minimal length elements of Thompsons group F. Geom. Dedicata 99 179-220 (2003).
[4] M G Brin, Elementary amenable subgroups of R. Thompson’s group F, Intl. J. Alg. and Comp. 15
619-642 (2005).
[5] J M Cohen, Cogrowth and amenability of discrete groups, J. Funct. Anal, 48 301-309 (1982).
[6] M Elder, E Fusy and A R Rechnitzer, Counting elements and geodesics in Thompson’s group F , J.
Alg. 324 102-121 (2010).
[7] M Elder, A Rechnitzer and E J Janse van Rensburg, Random Sampling of Trivial Words in Finitely
Presented Groups, Expr Math 24 391-409 (2015).
[8] M Elder, A R Rechnitzer and T Wong, On the cogrowth of Thompson’s group F , Groups - Complexity
- Cryptology, 4 301-320 (2012).
[9] F Gantmakher and M Krein, Sur les matrices completement non-négatives et oscillatoires, Compositio
Mathematica 4 445-476 (1937).
[10] D Gretete, Random walks on a discrete Heisenberg group, Rend. Circ. Mat. Palermo 60 329-335 (2011).
[11] R I Grigorchuk, Symmetric random walks on discrete groups, in Multicomponent random systems (eds.
R L Dobrushin and Ya. G Sinai), Nauka, Moscow (1978).
[12] V S Guba, On the properties of the Cayley graph of Richard Thompson’s group F, Internat. J. Alg.
Comp. 14 (56) 677-702, International Conference on Semigroups and Groups in honor of the 65th
birthday of Prof. John Rhodes (2004).
[13] A J Guttmann, in Phase Transitions and Critical Phenomena, vol 13, eds. C Domb and J Lebowitz,
Academic Press, London and New York, (1989).
[14] A J Guttmann, Analysis of series expansions for non-algebraic singularities, J. Phys A: Math. Theor.
48 045209 (33pp) (2015).
[15] A J Guttmann, Series extension: Predicting approximate series coefficients from a finite number of
exact coefficients, J. Phys A: Math. Theor. 49 415002 (27pp) (2016).
[16] A J Guttmann and I Jensen, Series Analysis. Chapter 8 of Polygons, Polyominoes and Polycubes
Lecture Notes in Physics 775, ed. A J Guttmann, Springer, (Heidelberg), (2009).
[17] A J Guttmann and G S Joyce, A new method of series analysis in lattice statistics, J Phys A, 5 L81–
84, (1972).
[18] S Haagerup, U Haagerup and M Ramirez-Solano, A computational approach to the Thompson group
F , Int. J. Alg. and Comp. 25 381-432 (2015).
[19] A Navas, Quelques groupes moyennables de difféomorphismes de l’intervalle, Bol. Soc. Mat. Mexicana
10 219-244 (2004).
[20] C. Pittet and L Saloff-Coste, On the stability of the behavior of random walks on groups, J. Geom.
Anal. 10 No 4 713-737 (2000).
[21] C. Pittet and L Saloff-Coste, On random walks on wreath products, Ann. of Probab. 30 No.2 948-977
(2002).

NUMERICAL STUDIES OF THOMPSON’S GROUP F AND RELATED GROUPS

47

[22] D Revelle, Heat kernel asymptotics on the lamplighter group, Elect. Comm. in Probab. 8 142-154
(2003).
[23] T-J Stieltjes, Recherches sur les fractions continues, Annales de la Faculté des sciences de Toulouse:
Mathématiques. 8 No. 4. J1-J122 (1894).

