THE MODULAR GROUP AND WORDS IN ITS TWO GENERATORS

arXiv:1512.02596v5 [math.NT] 24 Mar 2017

GIEDRIUS ALKAUSKAS
Abstract. Consider the full modular group PSL2 (Z) with presentation hU, S|U 3 , S 2 i. Motivated by our investigations on quasi-modular forms and the Minkowski question mark function
(so that this paper might be considered as a necessary appendix), we are lead to the following natural question. Some words in the alphabet {U, S} are equal to the unity; for example,
U SU 3 SU 2 is such a word of length 8, and U SU 3 SU SU 3 S 3 U is such a word of length 15. We
consider the following integer sequence. For each n ∈ N0 , let t(n) be the number of words
in alphabet {U, S} that equal the identity in the group. This is the new entry A265434 into
the Online Encyclopedia of Integer Sequences. We investigate the generating function of this
sequence and prove that it is an algebraic function over Q(x) of degree 3. As an interesting
generalization, we formulate the problem of describing all algebraic functions with a Fermat
property.

1. Introduction
1.1. Motivation and results. The topic of this paper is the following two new sequences.
The first one t(n), n ≥ 0, starts from
1, 0, 1, 1, 1, 5, 2, 14, 13, 31, 66, 77, 240, 286, 722, 1226, 2141, 4760, 7268, 16473, . . .

(1)

This is the sequence A265434 in [13]. The second sequence t(n), n ≥ 0, starts from
1, 0, 1, 1, 0, 3, 0, 5, 3, 7, 16, 12, 50, 44, 123, 195, 301, 718, 928, 2244, . . .

They are defined as follows. Let U 3 = I and S 2 = I be two elements of order 3 and 2,
respectively, I being the unity.
that
 Consider
 the the full modular group PSL2 (Z).
 It is known

0 1
0 1
it is freely generated by U =
, element of order 3, and and S =
, element
−1 1
−1 0
of order 2. Let n ∈ N0 , and A be any word in the alphabet U, S of total lenght n:
n
Y
(U ǫj S δj ), ǫj , δj ∈ {0, 1}, ǫj + δj = 1.
A=
j=1

Let t(n) be the number of such words that in the group Γ are equal to the unity. Our method
to calculate the first 20, 0 ≤ n ≤ 19, terms of the sequence (1) was via a brute force calculation.
As the model, let U and S be
my 2 × 2 matrices as above. Let us construct a binary tree,
 given 
1 0
starting from the node I =
. Each node A in this binary tree generates two offspring
0 1
- the right one AU, and the left one AS. For a given n, we then calculate which of the 2n
Date: March 28, 2017.
2010 Mathematics Subject Classification. Primary 05A05, 05A15, 20XX, 14H05.
Key words and phrases. The modular group, combinatorial group theory, free group, unity, generating function, algebraic function, cogrowth rate, return generating function, word problem, pushdown automaton.
The research of the author was supported by the Research Council of Lithuania grant No. MIP-072/2015.
1

2

G. ALKAUSKAS

matrices in the nth generation are equal to ±I. Via this method, a standard home computer
can give few more terms of this sequence.
Further, we call such a word primitive, if
s
Y
(U ǫj S δj ) = I only if s = n.
j=1

Let t(n) be the number of primitive (and nonempty) words of length n. Let us introduce the
generating functions
∞
∞
X
X
n
t(n)x = T (x),
t(n)xn = T(x).
n=0

n=1

Obviously,
1
= T (x).
1 − T(x)
Indeed, we are just considering words broken up into primitive loops, so

2
T (x) = 1 + t(1)x + t(2)x2 + · · · + t(1)x + t(2)x2 + · · · + · · · .

The number of total words of length n is equal to 2n . So, t(n) ≤ 2n , and thus both series
converge at least for |x| < 21 . The Table gives values for this function (and all words) for
0 ≤ n ≤ 8.
Table. Sequences t(n) and t(n). Primitive elements are in bold
n t(n) t(n) Products
0
1
0 I
1
0
0 −
2
1
1 S2
3
1
1 U3
4
1
0 S4
5
5
3 U 3 S 2 , U2 S2 U, US2 U2 , S 2 U 3 , SU3 S
6
2
0 S6, U 6
7
14
5 U 3 S 4 , U2 S4 U, US4 U2 , S 4 U 3 , SU 3 S 3 , S 2 U 2 S 2 U, SU2 S2 US, U 2 S 2 US 2
S 2 US 2 U 2 , SUS2 U2 S, US 2 U 2 S 2 , S 3 U 3 S, S 2 U 3 S 2 , US2 US2 U
8
13
3 S 8 , U 6 S 2 , U 5 S 2 U, U 4 S 2 U 2 , U 3 S 2 U 3 , U 2 S 2 U 4 , US 2 U 5 , S 2 U 6
SU6 S, U 3 SU 3 S, U2 SU3 SU, USU3 SU2 , SU 3 SU 3
The integer q(n, m) counts the number of words that are equal to the unity in the group Γ,
and which contain n copies of U and m copies of S. Note that
q(n, m) = 0 unless n ≡ 0 (mod 3) and m ≡ 0 (mod 2).

We also introduce

X

A is unity

P

x

ǫj

y

P

δj

=

∞
X

q(n, m)xn y m = Q(x, y).

n,m=0

Obviously, T (x) = Q(x, x). The series T (x) can be interpreted as a return generating function
for a certain directed graph (see the Subsection 1.2 and Figure 1), and thus this function belongs to a hugely diverse and abundant family of functions with the following two features. All

THE MODULAR GROUP AND WORDS

3

of them share the property that their Taylor coefficients grow exponentially, and all are related
to the graph theory and enumeration ([3], 5.6).
The main result of this paper is the following
Theorem. The function Q(x, y) is an algebraic 3rd degree function over Q(x, y), satisfying
(y 6 − x6 + 6y 2 x3 − 3y 4 + 2x3 + 3y 2 − 1)Q3 + (x3 y 2 − y 4 + x3 + 2y 2 − 1)Q2 + (x3 − y 2 + 1)Q + 1 = 0.

In particular, the function T (x) is an algebraic 3rd degree function over Q(x), satisfying
(6x5 − 3x4 + 2x3 + 3x2 − 1)T 3 + (x5 − x4 + x3 + 2x2 − 1)T 2 + (x3 − x2 + 1)T + 1 = 0.
Thus,
∞
X
t(n)
n=0

2n

14
6√
=
+
17,
13 13

∞
X
t(n)
n=0

2n

·

1
2n+1

= 0.5443390725+.

The last number can be interpreted as probability that a randomly chosen word is a unity,
with a convention that each length n is given a weight 2−(n+1) , and then probability is equally
distributed among all words of length n.
Two proofs of this result are given. The first one is longer, but uses only elementary combinatorics and considerations from the scratch. The second one is shorter, is included due to
a suggestion and very clear guidance by the referee, and is a standard proof in the area of
geometric and combinatoric group theory.
We finish this Subsection with the following
Proposition 1. For any prime p > 3, t(p) ≡ 0 (mod p).
Proof. Indeed, if AB = I in the group Γ, then BA = I as well. So, any cyclic permutation of
the word which is a unity is a unity again. So, words of length p > 3 which are equal to the unity
split into groups each containing exactly p words. Indeed, otherwise all these permutations are
equal. But U p 6= I and S p 6= I - a contradiction.

1.2. Context, previous results. In [1] we investigate the relation of modular forms to the
Minkowski question mark function, introducing the notion of mean-modular forms. In particular, the analytic continuation of a certain bivariate analytic function G(κ, z) (an extension
of the Stieltjes transform of the Minkowski question mark function) requires us to know the
analytic formula for Q(x, y) as a bivariate function; whence the principal motivation for the
current paper. In fact, the result of Theorem is new, but it is an exercise for people in the
field. The much more ambitious program of integrating the world of Minkowski question mark
function and the world of modular forms for PSL2 (Z) justifies the current paper as a necessary
appendix to [1].
As just mentioned, this particular question is new, though many intricately related problems were investigated and solved before, and the topic itself is of big importance in the
theory of groups (growth and cogrowth rates), graphs (return and first-return paths), and
non-commutative probability.

4

G. ALKAUSKAS

As a particular example of his more general results, Kuksov [6] considers the cogrowth rate
of the product Z/(2) ⋆ Z/(3), which is the same modular group. The question of investigating
cogrowth rates amounts to the following. Count the number of reduced words in the alphabet
{U, U −1 , S, S −1 } that are equal to the unity. Reduced means that S and S −1 , and also U and
U −1 never follow immediately one after another. It is obvious then that the total number of
reduced words of length n is 4 · 3n−1 : the first letter can be anything, after that the choice is
restricted. The generating function of this sequence (cogrowth series) turns out to be


p
(x + 1) 9x5 − 3x4 + 8x3 − x2 + x − (6x2 − x + 2) R(x)
v(x) =
,
2(3x − 1)(3x2 + 1)(3x2 + 3x + 1)(3x2 − x + 1)
where R(x) = 81x8 − 54x7 + 9x6 − 18x5 − 8x4 − 6x3 + x2 − 2x + 1.
The cogrowth rate (the inverse of the radius of convergence of the Taylor series for this function
at the origin) turns out to be 2.9249+ < 3. The function v(x) is quadratic algebraic function,
as opposed to cubic algebraic function T (x) in our case. The Taylor coefficients of v(x) are
1, 0, 2, 2, 6, 24, 44, 136, 298, 914, 2462, 6464, . . .
For example, there are 6 reduced words of length 4:
SSSS, S −1 S −1 S −1 S −1 , U −1 SSU, USSU −1 , U −1 S −1 S −1 U, US −1 S −1 U −1 .
Also, Proposition 1 does not have an analogoue in this case.
In a related direction, Quenell in [9] investigates the return generating function of Cayley
graphs for the free products of finite groups. This is related to the thesis of McLaughlin [8]
(see also [2]). In particular, in case of the modular group the return generating function counts
words in {U, U −1 , S, S −1 } of total length n that are equal to the unity (words are not necessarily reduced). The total number of all words of spell length n is 4n . In this context, the
function T (x) can be interpreted as a return generated function for a directed Cayley graph for
Z/(2) ⋆ Z/(3), where each 2-cycle and 3-cycle has a particular direction chosen in advance; see
Figure 1.
Franz Lehner has pointed out that the question in consideration is a special case of a “free
convolution” and can be obtained via Voiculescu-Woess transform [7, 10, 11, 12]. This technique
is implemented as a package and it is part of the library of FriCAS. So, the current paper can
be thought as a purely combinatoric demonstration of the result, with emphasis on a bivariate
function Q(x, y) rather than a univariate T (x) = Q(x, y).
1.3. Algebraic functions with a Fermat property. Before passing to the proof of the main
result, we will formulate one interesting problem, which is motivated by Proposition 1.
Consider the following rational function
∞

∞

X
X
x2
P (x) =
=
s(n)xn =
(2n−1 − 1)xn .
(1 − 2x)(1 − x) n=2
n=2
Thus, we have s(p) ≡ 0 (mod p) for p > 2 prime.

THE MODULAR GROUP AND WORDS

5

Figure 1. First few generations of a directed Cayley graph for Z/(2) ⋆ Z/(3).
Next, let


∞
∞ 

X
X
1
2n
2
n
J(x) = √
− 2 xn .
=
s(n)x =
−
n
1 − 4x 1 − x n=0
n=0

This also gives s(p) ≡ 0 (mod p) for p ≥ 2 prime.
Finally, as is implied by Proposition 1, we have the same (for p > 3) conclusion for a degree
3 algebraic function T (x) = 1 + x2 + O(x3 ), which satisfies
(6x5 − 3x4 + 2x3 + 3x2 − 1)T 3 + (x5 − x4 + x3 + 2x2 − 1)T 2 + (x3 − x2 + 1)T + 1 = 0.
∞
P
Let R(x) =
s(n)xn ∈ Z[[x]] be an algebraic function over Q(x), unramified at x = 0.
n=0

Suppose, s(p) ≡ 0 (mod p) for all sufficiently large prime numbers p. We call such a function
R(x) an algebraic function with a Fermat property. Thus, we formulate
Problem 1. Characterize all algebraic functions with a Fermat property in general, and in any
particular algebraic function field Q(x, U), where U is unramified at x = 0.
We can multiply the function R(x) by an integer to get the congruence valid for all primes.
All algebraic functions with a Fermat property form an abelian group P
F . Since the set of all
n
algebraic functions over Q is countable, F is also
countable. If U(x) = ∞
n=0 a(n)x ∈ Z[[x]] is
P
∞
n
∂
′
an algebraic function, then U (x) := xU (x) = n=0 na(n)x ∈ F . Indeed, first it is obvious
that U ∂ ∈ Z[[x]]. And second, if G(Y, x) ∈ Z[Y, x] and G(U, x) = 0, then
U′ = −

Gx (U, x)
GY (U, x)

6

G. ALKAUSKAS

belongs to the same algebraic function field Q(x, U). Let D (from “Differential”) P
be the union of
n
all such possible U ∂ . Then D is a subgroup of F . So is Z[x]. Finally, let U(x) = ∞
n=0 a(n)x ∈
Z[[x]] is again an algebraic function, unramified and without a pole at x = 0, and let for an
integer M ≥ 2, U (M ) (x) = U(xM ). Let P (from “Power”) be the group whose elements are
s
X
(M )
Uj j , Mj ≥ 2.
j=1

Then P is also a subgroup of F . Of course, any two of the subgroups D, Z[x] and P have
a non-trivial pairwise intersection. Let also for any U, algebraic over Q(x) and unramified at
x = 0, FU = F ∩ Q(x, U), DU = D ∩ Q(x, U), PU = P ∩ Q(x, U) (We identify any algebraic
function with its Laurent expansion at x = 0). We may refine Problem 1 as follows.
Problem 2. Find the structure of abelian groups
F /(D + Z[x] + P ),


AU = FU / DU + Z[x] ,

PU = FU / DU + Z[x] + PU



for any U algebraic over Q(x) and unramified at x = 0. In particular, for example, what is the
group P∅ (that is, we talk only about Q(x))?
In fact, for a function J(x) we have an even stronger property s(p) ≡ 0 (mod p2 ). We may
call it an algebraic function with a strong Fermat (or Wieferich) property, and ask similar
questions.
2. The first proof
Let us introduce the function q̂(n, m). This is defined similarly as q(n, m). Namely, we count
the number of words in U, S which are equal to unity in Γ, which have n copies of U and m
copies of S, but which do not contain S 2 (two S ′ s in a row). Let
∞
X
b y).
q̂(3n, 2m)x3n y 2m = Q(x,
n,m≥0

Proposition 2. We have an identity


X
3n + k
.
q(3n, 2m) =
q̂(3n, 2m − 2k) ·
k
k≥0

This implies


1
x
,
y
·
.
2
1−y
1 − y2
Proof. Indeed, consider any word which has 3n copies of U and 2m copies of S. Now, replace
each occurring segment S 2ℓ+j , ℓ ≥ 0, j ∈ {0, 1}, with S j . We get a word which lies in the set
which defines q̂(3n, 2m − 2k) for some k ∈ N0 . In the other direction, consider the latter word.
Suppose, we have k spare copies of S 2 . We can plug k copies of S 2 into such a word, to get a
word which defines q(3n, 2m). As can be seen, we can confine in plugging to the left of each
occurrence of U, plus to the right of the rightmost U. This gives 3n + 1 possible places to plug
in. We want to distribute k copies of S 2 . This gives the formula in Proposition.


b
Q(x, y) = Q

Let us divide the words which define the quantity q̂(n, m) into 7 disjoint subsets. B stands
for any non-empty word. Let n, m ≥ 0. Here everywhere “—” stands for the phrase “be the
number of such words that are of the form...”.

THE MODULAR GROUP AND WORDS

a)
b)
c)
d)
e)
f)
g)

7

a(n, m) — SUBUS.
b(n, m) — either U α SBSU β , α, β > 0 and α + β ≡ 0 (mod 3), or U γ , γ ≡ 0 (mod 3).
c(n, m) — U α SBS, or SBSU α , α > 0, α ≡ 0 (mod 3).
d(n, m) — U α SBSU β , α, β > 0, and α + β ≡ 2 (mod 3).
e(n, m) — U α SBSU β , α, β > 0, and α + β ≡ 1 (mod 3).
f (n, m) — either SBSU α , or U α SBS, α ≡ 1 (mod 3).
g(n, m) — either SBSU α , or U α SBS, α ≡ 2 (mod 3).

Let us also introduce two subsets which define d and f , respectively, as follows:
d) d(n, m) — USBSU,
f) f(n, m) — SBSU.

Example 1. We have: q̂(6, 2) = 5. Words which corespond to a, b, c are, respectively, {SU 6 S},
{U 2 SU 3 SU, U SU 3 SU 2 }, {SU 3 SU 3 , U 3 SU 3 S}. All sets beyond “c” are empty.
✷
Example 2. We have: q̂(9, 4) = 20. Words which correspond to a(9, 4) = 7, b(9, 4) = 5, c(9, 4) = 3,
d(9, 4) = 1, e(9, 4) = 0, f (9, 4) = 2, g(9, 4) = 2, are, respectively:
a : {SU SU 3 SU 5 S, SU SU 6 SU 2 S, SU 2 SU 3 SU 4 S, SU 2 SU 6 SU S, SU 3 SU 3 SU 3 S, SU 4 SU 3 SU 2 S,
SU 5 SU 3 SU S},
b : {U SU SU 3 SU 2 SU 2 , U SU 2 SU 3 SU SU 2 , U 2 SU SU 3 SU 2 SU, U 2 SU 2 SU 3 SU SU, SU SU 3 SU 2 SU 3 },
c : {SU 2 SU 3 SU SU 3 , U 3 SU SU 3 SU 2 S, U 3 SU 2 SU 3 SU S},
d : {U SU 3 SU SU 3 SU },
e : ∅,
f : {SU 3 SU 2 SU 3 SU, U SU 3 SU 2 SU 3 S},
g : {SU 3 SU SU 3 SU 2 , U 2 SU 3 SU SU 3 S}.
✷

Note that a(n, m) and other 8 functions are potentially non-zero only for n = 3k, m = 2l for
k ≥ 0, l ≥ 0.
The first step to derive our main result is the following
Proposition 3. We have the following recurrences:
a(3n, 2m) = b(3n, 2m − 2) + d(3n, 2m − 2) + e(3n, 2m − 2),
X
b(3n, 2m) =
(3k − 1)a(3n − 3k, 2m) for m ≥ 1, b(3n, 0) = 1 for n > 0,
k≥1

c(3n, 2m) = 2

X
k≥1

d(3n, 2m) =

X
k≥0

e(3n, 2m) =

X
k≥1

f (3n, 2m) = 2

(3k + 1)d(n − 3k, 2m),
3kf(n − 3k, 2m),

X
k≥0

g(3n, 2m) = 2

a(3n − 3k, 2m),

X
k≥0

f(n − 3k, 2m),
d(n − 3k, 2m).

8

G. ALKAUSKAS

These hold for n, m ≥ 0 assuming that all these functions vanish if one of the arguments is
negative.
Proof. All these equalities are straighforward. Only the formula for e needs an explanation.
Indeed, we note that (as already used in the proof of Proposition 1) if AB = I in the group Γ,
then BA = I. So, if U 2 BU 2 = I, this gives BU = I.

Let
A(x, y) =

X

a(3n, 2m)x3n y 2m

n,m≥0

be the generating function of the coefficients a(3n, 2m), and similarly we define other bivariate
functions B, C, D, E, F, G, D and F. The identities of Proposition 3 now read as
A = y 2B + y 2D + y 2 E,
C=

2x3
A,
1 − x3

D=

This gives

A =
b is then
Our function Q

2x3 + 1
D,
(1 − x3 )2

x3
x3 (x3 + 2)
+
A,
1 − x3
(1 − x3 )2
3x3
2
E=
F, F =
F,
3
2
(1 − x )
1 − x3

B=

G=

2
D.
1 − x3

y 2 x3 (x3 + 2)
y 2 (2x3 + 1)
3y 2x3
y 2x3
+
A
+
D
+
F.
1 − x3
(1 − x3 )2
(1 − x3 )2
(1 − x3 )2

That is,
b y) =
Q(x,

(2)

b = 1 + A + B + C + D + E + G.
Q
2x3 + 1
3
x3 + 2
1
+
A+
D+
F.
1 − x3 (1 − x3 )2
(1 − x3 )2
(1 − x3 )2

(3)

Example 3. The sets which define “d” through “g” are non-empty starting only from the length 13
(that is, where 3n + 2m = 13). Thus, if we use the above recurences only minding the sets “a”, “b”
and “c” (that is, assuming that D = 0 and F = 0), we obtain
A(x, y) ≫

y 2 x3 (1 − x3 )
.
(1 − x3 )2 − y 2 x3 (x3 + 2)

By the sign ≫ we mean that the inequality ≥ holds for Taylor coeffiencts of corresponding functions
on the left and on the right. This gives
b y) ≫ 1 + A + B + C ≫
Q(x,

1 − x3 − y 2 x3
,
(1 − x3 )2 − y 2 x3 (x3 + 2)

and consequently

 x
1
(x − 1)(x + 1)(x6 + x5 − 3x4 + x3 + 3x2 − 1)
b
,
x
·
≫
.
T (x) = Q
1 − x2
1 − x2
1 − 5x2 − 2x3 + 10x4 + 2x5 − 9x6 + 2x7 + 5x8 − 2x9 − x10

And indeed, minding the values given by (1), MAPLE confirms that the first disrepancy occurs only
for n = 13. Namely, 286 > 281, and the five missing words are precisely those given by Example 2 in
the sets “d” through “g”. For n = 14 there are no words in the sets beyond “c”, so the above is in fact
the equality 722 = 722. The Galois group of the splitting field of the polynomial in the denominator

THE MODULAR GROUP AND WORDS

9

is equal to S10 . This polynomial has the unique root θ of the smallest absolute value, it is real and
positive: θ = 0.5394737936+ , θ −1 = 1.853658161+ . So, this single observation gives the lower bound
t(n) > C(1.853658161)n
for a certain C > 0. In fact, our main Theorem implies that for the function t(n) we have the sharper
bound
t(n) > C(1.971480194)n ,
where φ−1 = 1.971480194+ , φ being the smallest (in absolute value) root of x7 − 20x5 + 12x4 − 8x3 −
12x2 + 4 = 0, the factor of the discriminant of the cubic polynomial in the Theorem.
✷

b we need to express D and F in terms of A. In
To prove the formula for A, and hence for Q,
order to accomplish this, we introduce the notion of a primitive a-word. This, by definition, is
the word which belongs to the subset which defines the function “a” (an a−word ), but which
cannot be written as
A1 U α1 A2 U α2 · · · U αs−1 As ,

s ≥ 2,

αi ≥ 1,

(4)

where each Ai is an a−word.
Thus, let us continue our classification given by a) through f), and introduce
a) a(n, m) — number of primitive a-words, which have n copies of U and m copies of S.
Example 4. In the Example 2 above, six of the a−words are primitive, only SU 3 SU 3 SU 3 S is not. ✷

Proposition 4. We have the recurrence
a(3n, 2m) = a(3n, 2m) +

∞
X

X

k=1

+


∞ 
X
3k − 1
k=1

+

1


∞ 
X
3k − 1
k=1

2

X

a(3n1 , 2m1 )a(3n2 , 2m2 )

3n1 +3n2 =3n−3k
2m1 +2m2 =2m

a(3n1 , 2m1 )a(3n2 , 2m2 )a(3n3 , 2m3 )

3n1 +3n2 +3n3 =3n−3k
2m1 +2m2 +2m3 =2m

X

a(3n1 , 2m1 )a(3n2 , 2m2 )a(3n3 , 2m3 )a(3n4 , 2m4 )

3n1 +3n2 +3n3 +3n4 =3n−3k
2m1 +2m2 +2m3 +2m4 =2m

+ ··· .
Proof. We note that each a−word is either primitive, or can be written in the form (4), where
each Ai is a primitive a−word. This claim
 follows by induction. Now we are left to count,
which gives the above formula. Here 3k−1
stands for a number of ways the number 3k can be
s
written as a sum of s + 1 positive integers.

Let
W (x, y) =

X

n,m≥0

a(3n, 2m)x3n y 2m .

10

G. ALKAUSKAS

The identity in Proposition 4 can be written as

∞
∞ X
X
X
x3 W 2 (1 + W )2
3k − 1 3k s+2
x W
=W+
x3k W 2 (1 + W )3k−1 = W +
A=W +
.
3 (1 + W )3
s
1
−
x
k=1
k=1 s≥0
Analogously we derive recurrences for d and f in terms of a, which lead to the identities
D=

x3 W 2
,
1 − x3 (1 + W )3

F=

x3 W 2 (1 + W )
.
1 − x3 (1 + W )3

Plugging all these three identities for A, D and F into (2), we readily obtain that W is an
algebraic function:
W =

W 2 x3 (1 + W )2
W 2 x3 y 2 (5x3 + 1 + 3x3 W )
y 2 x3 (1 − x3 )
−
+
.
(1 − x3 )2 − y 2 x3 (x3 + 2) 1 − x3 (1 + W )3 [1 − x3 (1 + W )3 ][(1 − x3 )2 − y 2 x3 (x3 + 2)]

MAPLE simplifies this to a very elegant form

W = x3 (W + 1)2 (W + y 2 ).

(5)

So, W is a third degree algebraic function over Q(x, y), and thus so is Q. The exact form of
the cubic equation can be easily calculated with MAPLE, but we rather concentrate on T (x),
since, first, the equation for Q with the help of method in Section 3 can be easily calculated
by hand, and second, the cubic equation for W is very convenient to calculate fast the Taylor
coefficients of T recurrently. Let
 x

Z(x) = W
,x .
1 − x2
Then the equation for Z reads as
Z=

x3 (Z + 1)2 (Z + x2 )
.
(1 − x2 )3

(6)

We are left to verify the cubic equation given in the formulation of the Theorem. Plugging
known values into (3) and using Proposition 2, we obtain
(1 − x2 )2 (1 + Z)
.
(7)
1 − 3x2 − x3 + 3x4 − x6 − 3x3 Z − 3x3 Z 2 − x3 Z 3
Now, plug this value of T (x) into the cubic equation given by the Theorem. Then factor the
numerator. MAPLE confirms that one of the two multipliers is indeed Z(1 − x2 )3 − x3 (Z +
1)2 (Z + x2 ), so the equation for T (x) is verified. In fact, this equation was discovered by Robert
Israel by finding a 3rd degree algabraic function whose first 42 Taylor coefficients coincide with
t(n), 0 ≤ n ≤ 41. Our theoretical result thus double-checks this fact.
T (x) =

The equalities (6) and (7) give a polynomial-time method to calculate coefficients t(n). Indeed, let us start from Z1 (x) = x5 (the first primitive a−word is SU 3 S), and let us define
polynomials ZN (x) ∈ Z[x] recurrently by
ZN +1 =

x3 (ZN + 1)2 (ZN + x2 )
(mod x3N +6 ).
(1 − x2 )3

Thus, ZN is of degree 3N + 2, ZN +1 ≡ ZN (mod x3N +3 ). After reaching enough terms, plug
this into (7). This agrees perfectly with (1), which was calculated by a direct count. Robert
Israel calculated 2000 terms of the sequence t(n).

THE MODULAR GROUP AND WORDS

11

3. The short proof using PDA
The following alternative proof was proposed by the referee. We reproduce it almost verbatim, since the ideas are clear and self-explanatory. The PDA stands for a pushdown automaton.
Both proofs give exactly the same algebraic equation for the function Q.
The group Γ = PSL2 (Z) is virtually free, so in the framework of geometric and combinatoric
group theory it is known that the word problem (the set of all words in generators and inverses
that are equal 1) is an unambiguous context-free language. However, for our purposes in [1]
we need the regular language of all positive words {U, S}∗ to obtain the language of words
counted by the generating functions T and Q. It follows immediatelly from the ChomskySchützenberger enumeration theorem that the functions T and Q are algebraic.
To obtain the explicit formulae, we can explicitly construct a PDA accepting the language,
then follow standard methods to obtain generating functions from the PDA.
The language is very simple: a word equals 1 if some sequence of applications of the rules
S 2 → 1, U 3 → 1 to factors of the input word reduces it to the empty word. This can be done
using a PDA which has just one state, and a pushdown stack which uses the alphabet {0, 1, 2, 3}
where 0 is the bottom-of-stack marker, 1 means a single U, 2 means U 2 , and 3 means S. So
that the model of a PDA can be used that accepts on empty stack. Let us introduce a symbol
$, and consider the language L$ = {w$ | w ∈ {U, S}∗ , w =Γ 1}.
Here are the transitions:
1)
2)
3)
4)
5)
6)
7)
8)
9)

U, 0 → 10
U, 1 → 2
U, 2 → ǫ
U, 3 → 13
S, 0 → 30
S, 1 → 31
S, 2 → 32
S, 3 → ǫ
$, 0 → ǫ

This is indeed self-explanatory. For example, take the item 4). This means U is the next
letter, and 3 is on the top of the stack (that is, S). Since US does not reduce, replace 3 with
13. On the other hand, consider the item 3). It stands for a move that now we get a factor U 3 ,
which is removed.
The idea is that one reads a word in U, S and puts it into normal form on the fly, reducing U 3 ,
S whenever they appear as one moves right. The normal form of the prefix of the input word
is written (in code) on the stack. Accept if at the end the stack is empty (the normal form is 1).
2

Now we follow [4] to convert the deterministic PDA into an unambiguous context free grammar. Let Ni stand for the nonterminal Nq,i,q (since there exists only one state). Start symbol
is N0 . We get
1) N0 → UN1 N0

12

G. ALKAUSKAS

2)
3)
4)
5)
6)
7)
8)
9)

N1
N2
N3
N0
N1
N2
N3
N0

→ UN2
→U
→ UN1 N3
→ SN3 N0
→ SN3 N1
→ SN3 N2
→S
→$

Next, following the method of Chomsky-Schützenberger we obtain the following system of
equations for the generating function directly from the grammar:

f = xf1 f0 + yf3f0 + z,


 0
f1 = xf2 + yf3 f1 ,
(8)
f2 = x + yf3f2 ,


 f = xf f + y.
3
1 3

That is, we replace U and S with x and y, respectively, and add the corresponding terms. If
(f0 , f1 , f1 , f3 ) is the solution, then Q(x, y) = fz0 . Note that the variable z appears only in the
extression for f0 only as a linear factor z.
Solving easily by hand the last three equations of (8) gives the cubic equation for f3 = K:
y 2K 3 − (2y + y 3)K 2 + (1 + 2y 2 − x3 )K − y = 0.

(9)

Plugging everything into the first equation of (8), we get
Q(x, y) =

K
.
y(1 − K 2 )

(10)

Let K1 , K2 and K3 be three distinct roots of (9), and let σ1 = K1 + K2 + K3 , σ2 = K1 K2 +
K1 K3 + K2 K3 , σ3 = K1 K2 K3 be the standard symmetric polynomials. Then
σ1 =

2 + y2
,
y

σ2 =

1 + 2y 2 − x3
,
y2

1
σ3 = .
y

Let Qi , 1 ≤ i ≤ 3, are obtained from (10) by plugging Ki instead of K. We get

X 1
X
1
1
1
yσ2
+
+
= y
−y
Ki =
− yσ1 = y 2 − x3 − 1,
Q1 Q2 Q3
Ki
σ3
2
1
1
y σ1
(σ1 σ2 − 3σ3 )
1
+
+
=
+ y 2 σ2 − y 2
= x3 y 2 − y 4 + x3 + 2y 2 − 1,
Q1 Q2 Q2 Q3 Q1 Q3
σ3
σ3
1
y3
σ 2 − 2σ2
σ 2 − 2σ1 σ3
=
− y 3 σ3 − y 3 1
+ y3 2
Q1 Q2 Q3
σ3
σ3
σ3
6
6
2 3
4
3
2
= x − y − 6y x + 3y − 2x − 3y + 1.

We thus get the cubic equation for
formulated in the Theorem.

1
,
Q

and the reciprocal of it is the equation for Q, exactly as

THE MODULAR GROUP AND WORDS

13

Acknowledgements. I would like to thank Wadim Zudilin, Murray Elder and Franz Lehner
for sending me references and pointing out that these results are a small part of the much
richer field in the theory of groups and graphs. I sincerely thank Roland Bacher, and also
Robert Israel and activists of OEIS for helping with MAPLE and the sequence t(n) itself. I
thank Audrius Alkauskas for a picture. I especially thank the anonymous referee: all the text
in Section 3, up to the system (8), is almost verbatim taken from the referee’s report.
References
[1] G. Alkauskas, The Minkowski ?(x) function, a class of singular measures, quasi-modular and meanmodular forms. http://arxiv.org/abs/1209.4588.
[2] L. Bartholdi, Counting paths in graphs, Enseign. Math. (2) 45 (1-2) (1999), 83–131.
[3] S.R. Finch, Mathematical constants, Encyclopedia of Mathematics and its Applications, 94. Cambridge
University Press, Cambridge (2003).
[4] J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages, and computation, AddisonWesley Series in Computer Science. Addison-Wesley Publishing Co., Reading, Mass. (1979).
[5] D. G. Kouksov, On rationality of the cogrowth series, Proc. Amer. Math. Soc. 126 (10) (1998), 2845–2847.
[6] D. Kuksov, Cogrowth series of free products of finite and free groups, Glasgow Math. J. 41 (1) (1999),
19–31.
[7] F. Lehner, On the computation of spectra in free probability, J. Funct. Anal. 183 (2) (2001), 451–471.
[8] J. C. McLaughlin, “Random walks and convolution operators on free products”, Doctoral dissertation,
New York University, 1986.
[9] G. Quenell, Combinatorics of free product graphs, Contemp. Math. 173 (1994), 257–281.
[10] D. Voiculescu, Addition of certain noncommuting random variables, J. Funct. Anal. 66 (3) (1986),
323–346.
[11] W. Woess, Nearest neighbour random walks on free products of discrete groups. Boll. Un. Mat. Ital. B
(6) 5 (3) (1986), 961–982.
[12] W. Woess, Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138. Cambridge University Press, Cambridge, 2000.
[13] The Online Encyclopedia of Integer Sequences, Sequence A265434.
Vilnius University, Department of Mathematics and Informatics, Naugarduko 24, LT-03225
Vilnius, Lithuania
E-mail address: giedrius.alkauskas@mif.vu.lt

