For more details see, e.g., [
ECHLPT]
, Chapter 1.
Definition: A finite state automata on
$n$
strings is a 5tuple
$$(A,(V,E),S,F,l)$$
with
$A$
a finite set (called the alphabet),
$(V,E)$
a finite directed graph (called the state graph),
$S\in V$
(called the start state),
$F\subset V$
(called the final states), and
$l:E\u27f6{\prod}_{i=1}^{n}(A\cup \{\$\left\}\right)$
with
$\$$
some symbol disjoint from
$A$
(
$l$
is called the transition label; “
$\$$
” is a symbol for the end of a word) satisfying the following condition : if
$l\left(e\right)=(\cdot ,...,\$,\cdot ,...)$
with the
$\$$
in the
${k}^{th}$
place, then
$l\left(f\right)$
also has a
$\$$
in the
${k}^{th}$
place for all edges
$f$
so that there is a finite (oriented) path
$$e={e}_{0},{e}_{1},...,{e}_{m}=f$$
Definition: Let
$Z=(A,(V,E),S,F,l)$
be a finite state automata on
$n$
strings.
We define the language
$L\left(Z\right)\subset {\prod}_{i=1}^{n}{A}^{*}$
to be the following. Consider any element
$({w}_{1},...,{w}_{n})\in {\prod}_{i=1}^{n}{A}^{*}$
. Assume that the longest word in this tuple has
$m$
letters. For
$1\le i\le n$
and
$1\le j\le m$
define
${w}_{i}^{j}$
to be the
${j}^{th}$
letter of
${w}_{i}$
if
$j$
is at most the length of
${w}_{i}$
and
$\$$
otherwise. Then
$({w}_{1},...,{w}_{n})\in L\left(Z\right)$
if and only if there is some path
$$S={v}_{1},{e}_{1},{v}_{2},{e}_{2},...,{e}_{m},{v}_{m+1}\in F$$
so that for
$1\le j\le m$
we have
$$l\left({e}_{j}\right)=({w}_{1}^{j},{w}_{2}^{j},...,{w}_{n}^{j})$$
We say that
$L\left(Z\right)$
is a regular language.
Remark. Observe that we are abusing the word “language” in this definition:
only the case
$n=1$
is an actual language. Higher
$n$
correspond to
$n$
tuples of words in a language.
Remark. One should think of this as a machine able to keep track of a finite amount of information.
The following theorem demonstrates the flexibility of regular languages.
Theorem 2.1
([
ECHLPT]
, Corollary 1.4.7) The class of regular languages is closed under all first order predicates (i.e.
$\cup $
,
$\cap $
,
$\neg $
,
$\forall $
, and
$\exists $
).
We will also need the following theorem.
Theorem 2.2
Let
$Z=(A,(V,E),S,F,l)$
be a finite state automata on one string and let
$\phi :A\u27f6{\mathbb{Z}}_{\ge 0}$
be a weighting. Then the generating function
$G\left(L\right(Z\left)\right)$
with the language
$L\left(Z\right)$
weighted by
$\phi $
is a rational function.
Proof: It is a standard fact (see, for instance, [
CDP]
, Theorem 9.1) that
$G\left(L\right(Z\left)\right)$
is rational if
$\phi $
is the constant function
$1$
. To deduce the general case from this, replace each edge
$e$
in
$(V,E)$
by a path of length
$\phi \left(l\right(e\left)\right)$
with each edge in the path labeled by
$l\left(e\right)$
.
$\diamond $
Remark. When we refer to a regular language without specifying how many strings it has, we are referring to a regular language on one string.
3 Partitioning Regular Languages
Fix a regular language
$L$
with weighting
$\phi $
. Consider a partition
$P$
of
$L$
.
By Theorem
2.2 , we know that
$L$
has a rational generating function. In this section we give a sufficient condition for
$L/P$
(see Section 2.2 for the definition of
$L/P$
) to have a rational generating function. Our condition, the falsification by fellow traveler property, allows us to construct a regular sublanguage of
$L$
with exactly one word of minimal length in each set of
$P$
. It is inspired by the property of the same name in [
NS1]
.
Definition: We say that
$L/P$
has a regular minimal cross section if there is some subset
${L}^{\prime}\subset L$
so that
${L}^{\prime}$
is regular and
${L}^{\prime}$
contains exactly one representative of minimal size for each set in
$P$
.
Definition: We say that our partition
$P$
is a semiregular partition if there is a finite set of regular languages
${R}_{h},...,{R}_{k}\subset L\times L$
for
$h\le k$
(called the partial acceptors) so that
$${R}_{h},...,{R}_{k}\subset \left\{\right({w}_{1},{w}_{2})\in L\times L:{w}_{1}={w}_{2}\in L/P\}$$
Definition: We say that a semiregular partition
$P$
with partial acceptors
${R}_{h},...,{R}_{k}$
has the falsification by fellow traveler property if there is some constant
$K$
and some regular sublanguage
${L}^{\prime}$
of
$L$
containing at least one minimal representative of each set in the partition so that if
$w\in {L}^{\prime}$
is not a minimal representative in
$L/P$
then there is some word
${w}^{\prime}\in L$
so that the following are true.

∙
$(w,{w}^{\prime})\in {R}_{i}$
for some
$i$
(and in particular
$w={w}^{\prime}$
in
$L/P$
)

∙
$\left\right{w}^{\prime}\left\right<\left\rightw\left\right$

∙
For any
$j$
, let
$s$
and
${s}^{\prime}$
be initial segments of
$w$
and
${w}^{\prime}$
of length
$\text{max(}j\text{,}0\text{)}$
and
$\text{max(}ji\text{,}0\text{)}$
, respectively. Then
$\left\right\lefts\right\left{s}^{\prime}\right\left\right\le K$
(we say that
$w$
and
${w}^{\prime}$
$K$
fellow travel with respect to
$i$
).
We also require that if
$w,{w}^{\prime}\in {L}^{\prime}$
are both minimal representatives of the same element of
$L/P$
then there is some
$i$
so that
$(w,{w}^{\prime})\in {R}_{i}$
.
Remark. We need this slightly clumsy definition of
$K$
fellow traveling because (as will become clear later) to get things to “line up” while testing for equality we will have to first read a few letters from one word before starting to read the second.
Lemma 3.1
Let
$P$
be a semiregular partition with partial acceptors
${R}_{h},...,{R}_{k}$
of a regular language
$L$
and let
$K$
be any number. Fix some
$h\le i\le k$
. Then the following language is regular.
$$\begin{array}{cc}{L}^{\prime}=\{& ({w}_{1},{w}_{2})\in L\times L:({w}_{1},{w}_{2})\in {R}_{i},\left\right{w}_{1}\left\right>\left\right{w}_{2}\left\right,\end{array}$$  
$$\begin{array}{cc}& \text{and}{w}_{1}\text{and}{w}_{2}\text{Kfellow travel with respect to}i\text{}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
Proof: Observe that
${L}^{\prime}$
is the intersection of
${R}_{i}$
and the language
$$\begin{array}{cc}{L}^{\prime \prime}=\{& ({w}_{1},{w}_{2})\in ({A}^{*}{)}^{2}:\left{w}_{1}\right>\left{w}_{2}\right,\text{and}{w}_{1}\text{and}\end{array}$$  
$$\begin{array}{cc}& {w}_{2}\text{Kfellow travel (with respect to}i\text{)}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
By Theorem 2.1 it is thus enough to show that
${L}^{\prime \prime}$
is regular.
${L}^{\prime \prime}$
is accepted by a finite state automata which has “memory” to store
$i$
letters in the alphabet, which are initially set to some dummy letter which we think of having size
$0$
, plus one additional integer (called the “difference”) bounded by
$K$
. We read
${w}_{1}$
and
${w}_{2}$
in from left to right. We place the letter from
${w}_{2}$
into the end of our queue and remove the first letter from it. We then subtract the size of the letter from the queue from the size of the letter from
${w}_{1}$
, and add the result to the difference. If the absolute value of the difference ever exceeds
$K$
, then we fail. Otherwise, we accept the pair of words if after reading both words the difference is positive, and we reject it if the difference is nonpositive.
$\diamond $
Theorem 3.2
Let
$P$
be a semiregular partition with partial acceptors
${R}_{h},...,{R}_{k}$
of a regular language
$L$
so that
$P$
has the falsification by fellow traveler property.
Then
$L/P$
has a regular minimal cross section.
Proof: Let
${L}^{\prime}$
be the regular sublanguage of
$L$
and
$K$
be the constant given by the definition of the falsification by fellow traveler property. By Lemma 3.1
$$\begin{array}{cc}{L}_{i}=\{& ({w}_{1},{w}_{2})\in L\times L:({w}_{1},{w}_{2})\in {R}_{i},\left\right{w}_{1}\left\right>\left\right{w}_{2}\left\right,\end{array}$$  
$$\begin{array}{cc}& \text{and}{w}_{1}\text{and}{w}_{2}\text{Kfellow travel}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
is a regular language for each
$i$
. Hence by Theorem 2.1
$$\begin{array}{cc}{L}^{\prime \prime}=\{& w\in {L}^{\prime}:\text{there does not exist any}{w}^{\prime}\in L\text{so that}\end{array}$$  
$$\begin{array}{cc}& (w,{w}^{\prime})\in {L}_{1}\cup ...\cup {L}_{k}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
is a regular language. This language is composed of minimal representatives in
${L}^{\prime}/P$
. It contains at least one representative of each element. By a remark on page 57 of [
ECHLPT]
, the language
$$\begin{array}{cc}S=\{& ({w}_{1},{w}_{2})\in L\times L:\text{}{w}_{1}\text{is shortlex less than}{w}_{2}\text{}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
is regular (see page 56 of [
ECHLPT]
for the definition of the shortlex ordering.
For our purposes its only important property is that it is a total ordering on the set of words). By Theorem
2.1 the language
$$\begin{array}{cc}T=\{& ({w}_{1},{w}_{2})\in L\times L:\text{For some}h\le i\le k\text{}({w}_{1},{w}_{2})\in {R}_{i}\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
is a regular language. We conclude from Theorem 2.1 that
$$\begin{array}{cc}{L}^{\prime \prime \prime}=\{w\in {L}^{\prime \prime}:\text{for all}{w}^{\prime}\text{if}(w,{w}^{\prime})\in T\text{then}(w,{w}^{\prime})\in D\text{}\}& \end{array}$$  
$$\begin{array}{}\end{array}$$  
is regular. By the definition of the falsification by fellow traveler property,
${L}^{\prime \prime \prime}$
contains a unique representative of minimal length for each element of
${L}^{\prime}/P$
; i.e. it is a regular minimal cross section of
$L/P$
.
$\diamond $
Theorem 2.2 thus implies the following.
Corollary 3.3
Let
$P$
be a semiregular partition of a regular language
$L$
so that
$P$
has the falsification by fellow traveler property. Then
$L/P$
has rational growth.
4 Types and Heights
Fix a torus bundle
$\Gamma $
with monodromy
$M$
. Recall that we are examining the finite index subgroup
$G=<a,t>$
.
4.1 Definitions
Consider a word
$w$
in the generators of
$G$
. By conjugating all the
$t$
's to the right, we see that
$w$
is equal in the free group on
$a$
and
$t$
to a word of the following form.
$$w={(}^{n}{\prod}_{i=1}{t}^{{k}_{i}}{a}^{\pm 1}{t}^{{k}_{i}}){t}^{h}$$
We call
$h$
the height of
$w$
, which we will henceforth denote
$h\left(w\right)$
. Since (continuing our earlier abuse of notation) conjugation by
$t$
acts upon
$a$
by multiplication by
$M$
, each term
${t}^{{k}_{i}}{a}^{\pm 1}{t}^{{k}_{i}}$
is equal to
$\pm {M}^{{k}_{i}}a$
. We denote by
$type\left(w\right)$
the expression
$$type\left(w\right)={\sum}_{k={N}^{\prime}}^{N}{c}_{k}{M}^{k}a$$
which is obtained by collecting together equal powers of
$M$
. Here the
${c}_{k}$
are integers. Abusing notation, we regard this as a formal Laurent polynomial with coefficients
${c}_{k}$
and “variable”
$Ma$
. We call this polynomial the unreduced type of
$w$
. Let
$\overline{type}\left(w\right)$
the vector obtained by replacing
$M$
by the monodromy matrix and
$a$
by the vector
$(1,0)$
. We call this the reduced type of
$w$
.
Geometrically, we have decomposed
$G$
into a stack of copies of
${\mathbb{Z}}^{2}$
. The height of an element is layer it sits in. The reduced type of an element is the projection from that element to the height
$0$
layer. Observe that
${w}_{1}$
and
${w}_{2}$
are equal in
$G$
if and only if
$h\left({w}_{1}\right)=h\left({w}_{2}\right)$
and
$\overline{type}\left({w}_{1}\right)=\overline{type}\left({w}_{2}\right)$
, but there definitely exist words which are equal in
$G$
but have different unreduced types.
4.2 Appearance of Types
We now determine the length of the shortest word with a specified unreduced type and height.
Theorem 4.1
Let
$${\sum}_{k={N}^{\prime}}^{N}{c}_{k}{M}^{k}a$$
with
${c}_{{N}^{\prime}}$
and
${c}_{N}$
nonzero be an unreduced type and let
$h$
be a height. Then the shortest word with this unreduced type and level has length
$$l=\lefth\right+2{N}^{\prime}+2\mathit{m}\mathit{a}\mathit{x}(Nh,0)+{\sum}_{k={N}^{\prime}}^{N}\left{c}_{k}\right$$
Figure 1
:
$a{t}^{1}{a}^{1}{t}^{6}a{t}^{7}{a}^{1}{t}^{4}{a}^{2}{t}^{4}a{t}^{2}$
shortens to
${t}^{2}{a}^{1}t{a}^{1}ta{t}^{2}{a}^{2}{t}^{3}a{t}^{1}a{t}^{2}$
Proof: Without loss of generality assume
$h\ge 0$
. Consider any word
$w$
with the desired height and unreduced type. We first demonstrate that
$w$
is equal in
$G$
to a word of the desired length. Consider the following path in
${\mathbb{R}}^{2}$
. Start at
$(0,0)$
. As
$w$
is read from left to right, go one unit up for each
$t$
, one unit down for each
${t}^{1}$
, and one unit to the right for each
${a}^{\pm 1}$
. This path ends at the point
$\left({\sum}_{k={N}^{\prime}}^{N}\right{c}_{k},h)$
. See Figure 1 .
Going from
$(x,y)$
to
$(x+1,y)$
upon reading
$l$
is equivalent to adding
${t}^{y}l{t}^{y}={M}^{y}l$
to the unreduced type. Hence we may commute conjugates of
${a}^{\pm 1}$
around so that the terms of the unreduced type occur from the smallest power of
$M$
to the largest. See Figure 1 .
Observe that the resulting word has the desired length : the xcoordinate of the path moves
${\sum}_{k={N}^{\prime}}^{N}\left{c}_{k}\right$
units, and the ycoordinate first goes down
${N}^{\prime}$
units, then up
${N}^{\prime}$
units, then up
$h$
units, then up
$\mathit{m}\mathit{a}\mathit{x}(nh,0)$
, and finally down
$\mathit{m}\mathit{a}\mathit{x}(nh,0)$
units. Since any word yielding the desired unreduced type and height must correspond to a similar path, the indicated length is minimal.
$\diamond $
Remark. The minimallength word with a specified height and unreduced type need not be unique.
Remark. After proving a version of Theorem 4.1 , Grayson attempts to set up a complicated system of recurrence relations between various subsets of the group. He expresses the growth function as a power series whose coefficients are themselves power series. He demonstrates that there is a sort of linear recurrence relation between these (power series) coefficients. He then claims that this is enough to prove that the growth series is rational. However, absent a proof that (say) the first coefficient is in fact a rational function this is insufficient.
Let
$T=trace\left(M\right)$
. Since
$M$
is Anosov, it has two distinct real eigenvalues.
Let
$\lambda >\frac{1}{\lambda}$
be the eigenvalues with eigenvectors
$v$
and
${v}^{\prime}$
. Let
$\alpha ,{\alpha}^{\prime}\in \mathbb{R}$
be such that
$$(1,0)=\alpha v+{\alpha}^{\prime}{v}^{\prime}$$
Theorem 4.2
Let
${w}_{1}$
and
${w}_{2}$
be words in the generators of
$G$
with
$$type\left({w}_{1}\right)={\sum}_{k={N}^{\prime}}^{N}{c}_{k}{M}^{k}a$$
$$type\left({w}_{2}\right)={\sum}_{k={N}^{\prime}}^{N}{c}_{k}^{\prime}{M}^{k}a$$
(note that we have made our ranges of summation equal by inserting appropriate zero coefficients). Then
${w}_{1}={w}_{2}$
in
$G$
if and only if
$h\left({w}_{1}\right)=h\left({w}_{2}\right)$
and
$1TMa+{M}^{2}a$
divides the Laurent polynomial
$$type\left({w}_{1}\right)type\left({w}_{2}\right)={\sum}_{k={N}^{\prime}}^{N}({c}_{k}{c}_{k}^{\prime}){M}^{k}a$$
Proof: Observe that with respect to the basis
$\{v,{v}^{\prime}\}$
we have
$$\overline{type}\left({w}_{1}\right)=(\alpha {\sum}_{k={N}^{\prime}}^{N}{c}_{k}{\lambda}^{k},{\alpha}^{\prime}{\sum}_{k={N}^{\prime}}^{N}{c}_{k}{{\lambda}^{\prime}}^{k})$$
$$\overline{type}\left({w}_{2}\right)=(\alpha {\sum}_{k={N}^{\prime}}^{N}{c}_{k}^{\prime}{\lambda}^{k},{\alpha}^{\prime}{\sum}_{k={N}^{\prime}}^{N}{c}_{k}^{\prime}{{\lambda}^{\prime}}^{k})$$
Since
$M$
is a
$2\times 2$
matrix with irrational eigenvalues,
$\lambda $
and
${\lambda}^{\prime}$
have the same minimal polynomial as
$M$
; i.e.
$1Tz+{z}^{2}$
, whence the theorem.
$\diamond $
Consider the set
$$X=\mathbb{Z}\times \mathbb{Z}[z,{z}^{1}]$$
Define a size function on
$X$
by
$$\left\right(h,{\sum}_{k={N}^{\prime}}^{N}{c}_{k}{z}^{k}:=1+h+2{N}^{\prime}+2\mathit{m}\mathit{a}\mathit{x}(Nh,0)+{\sum}_{k={N}^{\prime}}^{N}{c}_{k}$$
Define a partition
$P$
on
$X$
by the following equivalence relation.
$$({h}_{1},{f}_{1})\sim ({h}_{2},{f}_{2})\u27fa[{h}_{1}={h}_{2}\text{and}1Tz+{z}^{2}\text{divides}{f}_{1}{f}_{2}]$$
We can now state the following important corollary to the above calculations.
Corollary 4.3
$G$
is isomorphic to
$X/P$
as a sized set.
Remark. Recall that the definition of size isomorphism we are using allows size functions to differ by a constant. The extra “
$1$
” in the size function on
$X$
will simplify the arguments below.
5 The Language
By Corollary 3.3 , to prove Theorem 1.1 it is enough to produce a regular language
$L$
with a semiregular partition
${P}^{\prime}$
with the falsification by fellow traveler property so that
$L/{P}^{\prime}$
is isomorphic to
$X/P$
. We first prove a number of finiteness results about
$X$
, then we define our language
$L$
, and finally we define our partition
${P}^{\prime}$
and show that it has the necessary properties.
5.1 Finiteness Lemmas
We first prove two lemmas which allow us to bound the coefficients in
$X$
we need to enumerate and to bound the information we need to keep track of to compare elements of
$X$
modulo
$P$
. This is necessary to apply the theory of finite state automata. Recall our standing assumption that
$T>0$
.
Lemma 5.1
Let
$w$
be a word in the generators of
$G$
of minimal length. Then the unreduced type of
$w$
has coefficients
${c}_{k}$
with
$\left{c}_{k}\right<5T$
.
Proof: Assume that
$w$
has minimal length and that
$$type\left(w\right)={\sum}_{k={N}^{\prime}}^{N}{c}_{k}{M}^{k}a$$
Theorem 4.2 tells us that we can, for each
$k$
, add or subtract
${M}^{k1}aT{M}^{k}a+{M}^{k+1}a$
without changing the group element represented by
$type\left(w\right)$
. Now, if
$\left{c}_{k}\right\ge 5T$
, add or subtract
$5{M}^{k1}a5T{M}^{k}a+5{M}^{k+1}a$
in such a way as to decrease
$\left{c}_{k}\right$
. Examining the above formula for the length of an element representing an unreduced type, we see that we have subtracted
$5T$
from the length of our representative and added at most
$2+2+5+5=14$
to its length.
Since
$T\ge 3$
, we conclude that
$w$
did not have minimal length, a contradiction.
$\diamond $
Lemma 5.2
For every integer
$A$
, there exists some integer
${B}_{A}$
so that the following holds. For
$i=1,2$
let
${f}_{i}={\sum}_{k={N}^{\prime}}^{N}{c}_{k,i}{z}^{k}$
with
$\left{c}_{k,i}\right\le A$
. Assume that
$1Tz+{z}^{2}$
divides
${f}_{1}{f}_{2}$
. Then the coefficients of
$({f}_{1}{f}_{2})/(1Tz+{z}^{2})$
are bounded by
${B}_{A}$
.
Proof: Since
$T\ge 3$
, the largest coefficient which is left when we expand out
$(1Tz+{z}^{2})g\left(z\right)$
is at least as large as the largest coefficient of
$g$
. Hence we may set
${B}_{A}=2A$
$\diamond $
5.2 The Language
Fix a natural number
$n\ge 1$
. Let
$${A}_{n}=\{n,...,n\}\times \{1,1,2\}$$
be an alphabet with weighting
$$\phi (t,a)=\leftt\right+\lefta\right$$
Consider the language
${L}_{n}$
on
${A}_{n}$
whose words are of the following form :
$$(\cdot ,2)...(\cdot ,2)(\cdot ,\pm 1)...(\cdot ,\pm 1)(\cdot ,2)...(\cdot ,2)$$
We require that there be at least one letter of the form
$(\cdot ,\pm 1)$
in each word, and that the second entry in all the middle terms of a word have the same sign.
This language is clearly regular. Define a map
$\phi :{L}_{n}\u27f6X$
by
$$\begin{array}{cc}& \phi {(}^{{n}_{1}}{\prod}_{k=0}({t}_{k},2{)}^{{n}_{2}}{\prod}_{k=0}({v}_{k},\pm 1{)}^{{n}_{3}}{\prod}_{k=0}({x}_{k},2))\end{array}$$  
$$\begin{array}{cc}& =(\pm {n}_{2},{\sum}_{k=0}^{{n}_{1}}{t}_{k}{z}^{k{n}_{1}1}+{\sum}_{k=0}^{{n}_{2}}{v}_{k}{z}^{k}+{\sum}_{k=0}^{{n}_{3}}{x}_{k}{z}^{{n}_{2}+1+k})\end{array}$$  
$$\begin{array}{}\end{array}$$  
where the sign of the first term is the same as the sign of the second part of all the middle terms. This is clearly a sizepreserving injection from
${L}_{n}$
into
$X$
.
Hence the partition
$P$
of
$X$
induces a partition
${P}_{n}$
of
${L}_{n}$
. Lemma 5.1 implies that for
$n\ge 5T$
the induced map
$\phi :{L}_{n}/{P}_{n}\u27f6X/P$
is an isomorphism.
5.3 The Partial Acceptors
Fix an integer
$i$
. Define a language
$$\begin{array}{cc}{R}_{i}=\{& ({w}_{1},{w}_{2})\in {L}_{n}\times {L}_{n}:{w}_{1}={w}_{2}\text{in}{L}_{n}/{P}_{n}\end{array}$$  
$$\begin{array}{cc}& \text{and}\phi \left({w}_{1}\right)=(h,{\sum}_{k={N}_{1}^{\prime}}^{{N}_{1}}{c}_{k}{z}^{k})\text{,}\phi \left({w}_{2}\right)=(h,{\sum}_{k={N}_{2}^{\prime}}^{{N}_{2}}{d}_{k}{z}^{k})\end{array}$$  
$$\begin{array}{cc}& \text{with}{N}_{1}^{\prime}{N}_{2}^{\prime}=i\}\end{array}$$  
$$\begin{array}{}\end{array}$$  
Theorem 5.3
${R}_{i}$
is a regular language.
Proof: We build an automata accepting
${R}_{i}$
. Without loss of generality
$i\ge 0$
. We imitate the usual polynomial long division algorithm to divide the difference between the Laurent polynomials determined by
${w}_{1}$
and
${w}_{2}$
by
$1Tz+{z}^{2}$
.
Let
${B}_{n}$
be the constant from Lemma 5.2 . Our automata will keep track of
$i$
items (each an element of
${A}_{n}$
) plus an additional 2 numbers of size bounded by
$(T+1){B}_{n}$
. The
$i$
pieces of memory will keep track of elements read from the second tape, and will be initialized to
$(0,2)$
. The other 2 numbers will be referred to as the “correction terms”, and will be initialized to 0.
We read the two tapes from left to right. At each step, we get two elements
$(t,a)$
and
$({t}^{\prime},{a}^{\prime})$
. Place the
$({t}^{\prime},{a}^{\prime})$
at the end of our
$k$
pieces of memory and remove the element
$({t}^{\prime \prime},{a}^{\prime \prime})$
from the beginning. Let
$c$
be the first “correction term”. The next coefficient of the quotient is then
$t{t}^{\prime \prime}+c$
. If this is larger than
${B}_{n}$
, then we fail. Otherwise, we shift the other correction term to the first position and add
$T(t{t}^{\prime \prime}+c)$
to it and place
$t{t}^{\prime \prime}+c$
in the second correction slot. We succeed if we get to the end of the words and our “correction terms” are both equal to zero (hence zero remainder) and the “middle terms” of our two strings line up (in other words, the heights are equal).
$\diamond $
5.4
$K$
Fellow Traveler Property
Theorem 1.1 now follows from Corollary 3.3 and the following theorem.
Again recall our standing assumption that
$T>0$
.
Theorem 5.4
For sufficiently large
$m$
,
$n$
, and
$K$
we have that
${P}_{n}$
is a semiregular partition with partial acceptors
${R}_{m},...,{R}_{m}$
of
${L}_{n}$
with the
$K$
fellow traveler property.
Proof: By Lemma 5.1 , the sublanguage
${L}_{5T}$
contains at least one minimallength representative of each class in the partition. Consider any word
$w\in {L}_{5T}$
. We need to pick
$n$
,
$m$
, and
$K$
large enough so that the following two things are true.

1.
If
$w$
is of minimal length, then for any other
${w}^{\prime}\in {L}_{5T}$
of minimal length we have that
$(w,{w}^{\prime})\in {R}_{i}$
for some
$m\le i\le m$
.

2.
If
$w$
is not of minimal length, then there is some
${w}^{\prime \prime}\in {L}_{n}$
so that
$\left\right{w}^{\prime}\left\right<\left\rightw\left\right$
,
$(w,{w}^{\prime \prime})\in {R}_{i}$
for some
$m\le i\le m$
, and
$w$
and
${w}^{\prime \prime}$
$K$
fellow travel with respect to
$i$
.
We will need two lemmas. During the proofs of these lemmas we will need the following notation/technique. Let
$w$
and
${w}^{\prime}$
be two words which represent the same element in
$L/P$
, and let
$$\phi \left(w\right)={\sum}_{k={N}_{1}^{\prime}}^{{N}_{1}}{c}_{k}{M}^{k}a$$
$$\phi \left({w}^{\prime}\right)={\sum}_{k={N}_{2}^{\prime}}^{{N}_{2}}{d}_{k}{M}^{k}a$$
$$\sum ({c}_{k}{d}_{k}){z}^{k}=(1Tz+{z}^{2})\sum {e}_{k}{z}^{k}$$
Arrange the coefficients in a table such as Table 1. The bottom row is equal to the top row plus the middle rows. We will often speak of modifying the middle rows. This corresponds to changing the difference between
$w$
and
${w}^{\prime}$
.
The new
${w}^{\prime}$
we get by adding our new middle rows to the top row will represent a different element which is equal to
$w$
in
$L/P$
.
${c}_{{N}_{1}^{\prime}}$

${c}_{{N}_{1}^{\prime}+1}$

${c}_{{N}_{1}^{\prime}+2}$

${c}_{{N}_{1}^{\prime}+3}$

${c}_{{N}_{1}^{\prime}+4}$

${c}_{{N}_{1}^{\prime}+5}$

...

${e}_{{N}_{1}^{\prime}}$

T
${e}_{{N}_{1}^{\prime}}$

${e}_{{N}_{1}^{\prime}}$






${e}_{{N}_{1}^{\prime}+1}$

$T{e}_{{N}_{1}^{\prime}+1}$

${e}_{{N}_{1}^{\prime}+1}$






${e}_{{N}_{1}^{\prime}+2}$

$T{e}_{{N}_{1}^{\prime}+2}$

${e}_{{N}_{1}^{\prime}+2}$






${e}_{{N}_{1}^{\prime}+3}$

$T{e}_{{N}_{1}^{\prime}+3}$

${e}_{{N}_{1}^{\prime}+3}$


. . .

. . .

. . .

. . .

. . .

. . .


${d}_{{N}_{1}^{\prime}}$

${d}_{{N}_{1}^{\prime}+1}$

${d}_{{N}_{1}^{\prime}+2}$

${d}_{{N}_{1}^{\prime}+3}$

${d}_{{N}_{1}^{\prime}+4}$

${d}_{{N}_{1}^{\prime}+5}$

...



Table 1
: The top and bottom rows list the coefficients of the types of two elements of
$X$
which are equivalent mod
$P$
. The difference between these types is divisible by
$1Tz+{z}^{2}$
. Each middle row corresponds to one coefficient of the quotient. Hence the bottom row is equal to the top row plus the middle rows.
Lemma 5.5
Let
$w,{w}^{\prime}\in {L}_{5T}$
be so that
$w={w}^{\prime}$
in
$L/P$
and let
${c}_{k}$
,
${N}_{1}$
,
${N}_{1}^{\prime}$
,
${d}_{k}$
,
${N}_{2}$
,
${N}_{2}^{\prime}$
, and
${e}_{k}$
be associated to
$w$
and
${w}^{\prime}$
as above. Assume that
${N}_{1}^{\prime}{N}_{2}^{\prime}>(T+2)B$
. Then there is some
${w}^{\prime \prime}\in {L}_{5T+(T+1)B}$
so that
$\left\right{w}^{\prime \prime}\left\right<\left\rightw\left\right$
and
$(w,{w}^{\prime \prime})\in {R}_{i}$
for some
$(T+4)B\le i\le (T+4)B$
.
Proof: We will assume that
${N}_{1}^{\prime}>{N}_{2}^{\prime}$
; the other case has a similar proof.
Arrange the coefficients as in Table 1. Observe that in this case we have at least the first
$(T+2)B$
coefficients on the bottom row equal to zero. Remove all but the first
$(T+2)B$
“center” terms
${e}_{k}$
. This changes
${w}^{\prime}$
to another word in the same equivalence class. Observe that the first
$(T+2)B$
terms on the bottom are equal to zero, the next term differs from the corresponding
${c}_{k}$
term by at most
$(T+1)B$
, the next term differs from the corresponding
${c}_{k}$
term by at most
$B$
, and the rest are identical to the
${c}_{k}$
terms. Changing the first
$(B+2)T$
terms to zero decreases the size of
$w$
by at least
$2(T+2)B$
. The changes in the next two terms increase it by at most
$(T+2)B$
. Hence we have
$\left\right{w}^{\prime \prime}\left\right<\left\rightw\left\right$
. The other claims about
${w}^{\prime \prime}$
are clear.
$\diamond $
Lemma 5.6
Let
$w\in {L}_{5T}$
and
${w}^{\prime}\in {L}_{5T+(T+1)B}$
be so that
$(w,{w}^{\prime})\in {R}_{i}$
for some
$(T+4)B\le i\le (T+4)B$
and let
${c}_{k}$
,
${N}_{1}$
,
${N}_{1}^{\prime}$
,
${d}_{k}$
,
${N}_{2}$
,
${N}_{2}^{\prime}$
, and
${e}_{k}$
be associated to
$w$
and
${w}^{\prime}$
as above. Then there exists some
${w}^{\prime \prime}\in {L}_{5T+3(T+1)B}$
so that
$(w,{w}^{\prime \prime})\in {R}_{j}$
for some
$(T+4)B\le j\le (T+4)B$
and
$w$
and
${w}^{\prime \prime}$
$K$
fellow travel with respect to
$j$
for
$K=(T+2)B$
.
Proof: We will assume without loss of generality that
${N}_{1}^{\prime}\ge {N}_{2}^{\prime}$
Assume that
$w$
and
${w}^{\prime}$
do not
$K$
fellow travel. There are two cases.
We again will assume that
${N}_{1}^{\prime}>{N}_{2}^{\prime}$
. First, assume that there is some subword
${w}_{1}$
of
$w$
and corresponding subword
${w}_{2}$
of
${w}^{\prime}$
so that
$$\left\right{w}_{2}\left\right>\left\right{w}_{1}\left\right+(T+2)B$$
Assume that these are the largest such subwords, and that
${w}_{1}$
has length (not norm) equal to
$c$
. We again make use of Table 1. Remove the first
$c$
of the
${e}_{k}$
terms. This modifies
${w}^{\prime}$
so that the first
$c$
terms are now equal to the
${c}_{k}$
's, the next term is changed by at most
$(T+1)B$
, the next by at most
$B$
, and the rest are left unchanged. It is clear that we still have
$\left\right{w}^{\prime}\left\right<\left\rightw\left\right$
, but now we have for all corresponding initial segments
${w}_{1}$
and
${w}_{2}$
that
$$\left\right{w}_{2}\left\right\le \left\right{w}_{1}\left\right+(T+2)B$$
This reduces us to the next case.
In this case we have some initial segment
${w}_{1}$
of
$w$
and corresponding initial segment
${w}_{2}$
of
${w}^{\prime}$
so that
$$\left\right{w}_{1}\left\right>\left\right{w}_{2}\left\right+(T+2)B$$
Let these be the first such segments. Assume that the length of
${w}_{1}$
equals
$c$
.
Referring again to Table 1, throw away all
${e}_{k}$
after
$c$
. It is easy to see that the resulting
${w}^{\prime}$
has the desired properties. This completes the proof.
$\diamond $
We can now prove the two items indicated above. Set
$m=(T+4)B$
,
$n=5T+3(T+1)B$
, and
$K=(T+2)B$
. Claim 1 is an immediate corollary of Lemma 5.5 ; if
$w$
and
${w}^{\prime}$
are not read by an appropriate
${R}_{i}$
then they are not minimal. To prove claim 2, let
$w\in {L}_{5T}$
be some nonminimal representative in
$L/P$
, and let
${w}^{\prime}\in {L}_{5T}$
be a minimal representative. Lemma 5.5 allows us to modify
${w}^{\prime}$
so that
$w$
and
${w}^{\prime}$
are read by an appropriate
${R}_{i}$
. Finally, Lemma 5.6 allows us to modify
${w}^{\prime}$
so that it
$K$
fellow travels with
$w$
, as desired.
$\diamond $
6 Some Questions
As we remarked in the introduction, using the methods of this paper to actually compute growth series would be a long and unpleasant task. However, sometimes the growth series of groups are not only rational but also display interesting arithmetic and combinatorial patterns (see, for instance, [
FP]
). The following therefore might be an interesting combinatorial problem.
Question 1: Explicitly compute the growth series of some Sol groups, for instance the group with monodromy
$\left(\begin{array}{cc}2& 1\\ 1& 1\\ \end{array}\right)$
.
The 3dimensional Sol groups are the fundamental groups of 2 dimensional torus bundles over a circle whose monodromy has has no eigenvalues on the unit circle. By considering
$n$
dimensional torus bundles over a circle with the same restriction on the monodromy, we get the
$n+1$
dimensional Sol groups.
It seems difficult to generalize our methods to these groups. This suggests the following question.
Question 2: Do the higherdimensional Sol groups have rational growth functions?
The fact that we were only able to find a finite index subgroup with rational growth suggests the following question.
Question 3: Does there exist any group
$G$
which has irrational growth with respect to all sets of generators but which contains a finite index subgroup
${G}^{\prime}$
which has rational growth with respect to some set of generators?
The following more general question also seems interesting.
Question 4: Consider the property of having rational growth with respect to some set of generators. How does this property behave under commensuration?
under quasiisometry?
Remark. Observe that
$\stackrel{~}{S{L}_{2}}$
and
${\mathbb{H}}^{2}\times \mathbb{R}$
are quasiisometric, and hence the fundamental groups of manifolds modeled on these geometries are quasiisometric.
An easy consequence of Cannon's work (see [
Ca]
) is that the fundamental groups of manifolds modeled on
${\mathbb{H}}^{2}\times \mathbb{R}$
are rational with respect to any generating set.
The work of Shapiro suggests that this is probably false for manifolds modeled on
$\stackrel{~}{S{L}_{2}}$
(see [
Sh2]
), so the property of being rational with respect to all generating sets is likely not wellbehaved under quasiisometry. The question of whether the fundamental group of any
$\stackrel{~}{S{L}_{2}}$
manifold has rational growth with respect to some generating set is still open.
Finally, Theorem 1.2 suggests that in some sense finite state automata should be a “universal” method for detecting rational generating functions. However, the regular language in our proof does not consist of words in the generators of the group, but rather reflects another structure. Neumann and Shapiro have produced virtually abelian groups so that for every generating set there exists no regular language of words in the group containing a unique geodesic for every group element ([NS2] ). However, Benson proved that virtually abelian groups have rational growth with respect to any set of generators ([Be1] ). This suggests that like in the case of Sol groups there must be another structure which guarantees rationality. The following would be very interesting.
Question 5: For a virtually abelian group
$G$
, find a regular language
$L$
which is isomorphic to
$G$
as a sized set.
7 Appendix : Proof of Theorem 1.2
The reverse implication is [
CDP]
, Theorem 9.1. We now prove the forward implication. We will use the following classical characterization of rational generating functions; see, e.g., [
Sta]
, Theorem 4.1.1.
Theorem 7.1
Let
${\sum}_{k=0}^{\infty}{a}_{k}{z}^{k}$
be a rational function. There then exists some natural number
$l>1$
and constants
${c}_{1},...,{c}_{l}$
so that for
$k>l$
we have
$${a}_{k}={c}_{1}{a}_{k1}+{c}_{2}{a}_{k2}+...+{c}_{l}{a}_{kl}$$
Let
${a}_{k}=\left\right\{x\in X:\left\rightx\left\right=k\left\}\right$
. By assumption
$G\left(z\right)={\sum}_{k=0}^{\infty}{a}_{k}{z}^{k}$
is rational, and our goal is to produce a regular language
$L$
so that
$G\left(L\right)=G\left(z\right)$
.
Let
${c}_{1},...,{c}_{l}$
be the constants given by Theorem 7.1 . Let
$A$
be the following alphabet.
$$\{{I}_{i}^{j}:1\le j\le l1,1\le i\le {a}_{j}\}\cup \{{C}_{i}^{j}:1\le j\le l,1\le i\le {c}_{j}\parallel $$
Finally, let
$L$
be the following language. Each word begins with
$a$
of the
${I}_{b}^{a}$
for some fixed
$a$
and
$b$
. After that, it is composed of any combination of the
${C}_{i}^{j}$
with the restriction that the letter
${C}_{i}^{j}$
must occur in blocks of size
$j$
. For instance, the letter
${C}_{3}^{5}$
must occur in blocks of the form
${C}_{3}^{5}{C}_{3}^{5}{C}_{3}^{5}{C}_{3}^{5}{C}_{3}^{5}$
. This language is clearly regular, and an easy induction demonstrates that it has the desired generating function.
References

Benson, M., Growth series of finite extensions of
${Z}^{n}$
are rational, Invent. Math. 73 (1983), no. 2, 251–269.

Benson, M., On the rational growth of virtually nilpotent groups, in Combinatorial Group Theory and Topology, Ed. by S. M. Gersten and John R. Stallings, Annals of Mathematics Studies, No. 111, Princeton University Press, 1987, 185196.

Bourbaki N., Groupes et algébres de Lie, Chapitres 4,5 et 6, Paris : Hermann, 1968.

Brady, Noel, Sol geometry groups are not asynchronously automatic, Proc. London Math. Soc. (3), 83 (2001), no. 1, 93119.

Brazil, Marcus., Growth functions for some nonautomatic BaumslagSolitar groups, Trans. Amer. Math. Soc. 342 (1994), no. 1, 137154.

Cannon, James W., The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata 16 (1984), no. 2, 123–148.

Coornaert, M., Delzant, T., Papadopoulos, A., Géométrie et théorie des groupes, Berlin : Springer Verlag, 1990.

de la Harpe, Pierre Topics in geometric group theory, Chicago : University of Chicago Press, 2000.

Epstein, D., Cannon, J. W., Holt, D. F., Levy, S. V. F., Paterson, M. S., Thurston, W. P., Word Processing in Groups, Boston : Jones and Bartlett Publishers, 1992.

Floyd, William J. and Steven P. Plotnick, Growth functions on Fuchsian groups and the Euler characteristic. Invent. Math. 88 (1987), no. 1, 129.

Grayson, M. A. Geometry and Growth in Three Dimensions, unpublished thesis, Princeton University, 1983.

Kharlampovich, O. G. A finitely presented solvable group with unsolvable word problem. (Russian), Izv. Akad. Nauk SSSR Ser. Math. 45 (1981), no. 4, 852873, 928.

Neumann, Walter D., and Michael Shapiro, Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. math. 120, 259287 (1995)

Neumann, Walter D., and Michael Shapiro. Regular geodesic normal forms in virtually abelian groups. Bull. Austral. Math. Soc., 55 (1997) 3, 517519.

Shapiro, Michael, A geometric approach to the almost convexity and growth of some nilpotent groups., Math. Ann., 285 (1989), 601624.

Shapiro, Michael, Growth of a
$PS{L}_{2}R$
manifold group. Math. Nachr. 167, (1994), 279312.

Stanley, Richard P., Enumerative combinatorics, vol I. Wadsworth and Brooks, Monterey, CA, 1986.

Stoll, Michael, Rational and transcendental growth series for the higher Heisenberg groups, Invent. Math. 126 (1996), no. 1, 85–109.

Thurston, William P., Threedimensional geometry and topology. Vol. 1. Princeton University Press, Princeton, NJ, 1997

Weber, Bernhard, Zur Rationalität polynomialer Wachstumsfunktionen, Bonner Mathematische Schriften 197, 1989.
Dept. of Mathematics, University of Chicago 5734 University Ave. Chicago, Il 60637 Email: andyp@math.uchicago.edu