The Rationality of Sol-Manifolds

Thomas A. Putman

March 30, 2005

Abstract
Let Γ   be the fundamental group of a manifold modeled on three dimensional Sol geometry. We prove that Γ   has a finite index subgroup G   which has a rational growth series with respect to a natural generating set. We do this by enumerating G   by a regular language. However, in contrast to most earlier proofs of this sort our regular language is not a language of words in the generating set, but rather reflects a different geometric structure in G   .

1 Introduction

Let Γ   be a group with a finite generating set S   . For g ∈ Γ   , let | | g | |   be equal to the length of the shortest word in S ∪ S − 1   representing g   , and for g 1 , g 2 ∈ Γ   set d ( g 1 , g 2 ) = | | g 1 − 1 g 2 | |   . This is known as the word metric on Γ   . The growth of the size of balls in this metric constitutes a central object of study in geometric group theory (see [Ha] , Chapters 6-7 for a survey).
To study the growth of Γ   , it is natural to define the growth series of Γ   to be the power series G ( Γ ) = ∑ k = 0 ∞ c k z k   where c k = | { g ∈ Γ : | | g | | = k } |   . In many cases, it turns out that G ( Γ )   is a rational function. The first nontrivial example of this is in [Bo] , where an exercise outlines a proof that all Coxeter groups have rational growth with respect to a Coxeter generating set. Perhaps the most remarkable theorem of this type is in Cannon's paper [Ca] , which proves that all word hyperbolic groups have rational growth with respect to any generating set ([Ca] only proves this for fundamental groups of compact hyperbolic manifolds, but it contains all the ideas necessary for the extension to word hyperbolic groups – see [CDP] for a complete account).
In this paper we study the growth series of the fundamental groups Γ   of torus bundles over the circle with Anosov monodromy. In other words, Γ = Z 2 ∖ M Z   with M ∈ S L 2 ( Z )   a matrix with two distinct real eigenvalues. These are the fundamental groups of 3-manifolds modeled on Sol geometry. Our main theorem is the following.
Theorem 1.1 (Main Theorem) Let Γ   be the fundamental group of a Sol manifold. Then there exists a finite index subgroup G   generated by a finite set S   so that G   has rational growth with respect to S   . In other words, Γ   is virtually rational.
This theorem is part of two different streams of research. On the one hand, there have been many papers investigating the growth series for lattices in Thurston's eight 3-dimensional model geometries (see [Be1] , [Be2] , [Ca] , [NS1] , [Sh1] , [Sh2] , and [We] ). After Theorem  1.1 , the only remaining geometry for which there is not some general theorem is S L 2 ~   , although some progress has been made on this case by Shapiro ([Sh2] ).
On the other hand, there has also been significant research on the growth series of finitely generated solvable groups. Kharlampovich has produced a 3-step solvable group which has an unsolvable word problem([Kh] ). Since all groups with rational growth series have a solvable word problem (the rational growth series allows one to calculate the size of balls in the Cayley graph, which one can then construct using a brute force enumeration), it follows that Kharlampovich's example does not have rational growth with respect to any set of generators.
One can therefore hope for general results only for 1 and 2-step solvable groups. The 1-step solvable groups are the finitely generated abelian groups.
Benson has proven that more generally all finitely generated virtually abelian groups have rational growth with respect to any set of generators ([Be1] ). The 2-step solvable groups are divided into the nilpotent and non-nilpotent groups.
A fundamental set of examples of 2-step nilpotent groups are the lattices in Nil geometry. These correspond to groups of the form Z 2 ∖ M Z   with M ∈ S L 2 ( Z )   a matrix with two different complex eigenvalues, which necessarily must lie on the unit circle. Benson, Shapiro, and Weber ([Be2] , [Sh1] , and [We] ) have shown that lattices in Nil geometry have rational growth with respect to a certain generating set. This has been generalized by Stoll ([Sto] ), who showed that all 2-step nilpotent groups with infinite cyclic derived subgroup have rational growth with respect to some generating set. He also showed that many such groups (those with “Heisenberg rank at least 2   ”) have transcendental growth with respect to some other generating set. This demonstrates that, in contrast to most natural group properties studied by geometric group theorists, rational growth can depend strongly on the choice of generating set.
The non-nilpotent solvable case is divided into the polycyclic and the non-polycyclic cases. A fundamental set of examples of 2-step solvable non-polycyclic groups are the solvable Baumslag-Solitar groups B S ( 1 , n )   . Brazil has shown that these have rational growth with respect to the standard set of generators ([Bz] ).
A fundamental set of examples of 2-step solvable polycyclic groups are the torsion-free abelian-by-cyclic groups. These are groups of the form Z n ∖ M Z   with M ∈ S L n ( Z )   . Theorem  1.1 combined with the result of Benson, Shapiro, and Weber referred to in the previous paragraph cover the case n=2, with ours being the “generic” case since our eigenvalues do not lie on the unit circle.
The strategy of our proof is as follows. We first show that there is a bijective, “size-preserving” correspondence between elements of our group and elements of a quotient of the ring of integral Laurent polynomials in one variable (where we give a certain natural measure of the “size” of a Laurent polynomial which takes into account both the size of the coefficients and the degree). We then enumerate this ring by a regular language, which by well known results is enough to assure that it has a rational growth series.
Philosophically, the appearance of the theory of regular languages is no accident. In fact, the following theorem demonstrates that at least in a weak sense regular languages are a “universal” method for proving that objects have rational growth.
Theorem 1.2 Let X   be a set and | | ⋅ | | : X ⟶ Z ≥ 0   a function (in the language of Section  2.2 , X   is a sized set). Form the generating function G ( X ) = ∑ k = 0 ∞ c k z k   where c k = | { x ∈ X : | | x | | = k } |   . Assume that there is exactly one element g ∈ X   so that | | g | | = 0   . Then G ( X )   is rational if and only if there exists a regular language L   and a length preserving bijection φ : L ⟶ X   .
Since this theorem functions as propaganda for our point of view but is not used in our proof, we relegate its proof to an appendix. A psychological obstacle to applying this theorem is that words in a group form a natural language, and hence it is easy to assume that if a regular language enumerates a group then it must be a sublanguage of the natural language. The language we construct is definitely not a sublanguage of the natural language, and in fact we doubt that it is possible to construct such a sublanguage (as evidence, it is known that lattices in Sol are not asynchronously automatic ([Br] )). In fact, Neumann and Shapiro have produced an example of a group which has rational growth with respect to any generating set (in fact, it is virtually abelian), but for which for every generating set there exists no regular language of words in the group which contains a unique geodesic for every group element ([NS2] ). Thus non-standard languages like the one we construct are inevitable in proofs that certain groups have rational growth.
Remark. Though in theory our methods are entirely constructive, in practice the finite state automata we build are so huge that it is impractical to calculate any examples.
History and Comments. In his unpublished thesis ([Gr] ), Grayson claimed to prove Theorem  1.1 whenever the trace of the monodromy is even. However, his proof is insufficient (see the remarks in Section  4 for a more detailed discussion).
Our methods are rather different from his methods. He attempts to write down a complicated recurrence relation between balls of different radii. As indicated above, we instead use the theory of finite state automata. We do, however, use some of his ideas. In particular, he introduced the notions of types and heights described Section  4 (though he does not distinguish between the reduced and unreduced types), and the elegant proof of Theorem  4.1 is due to him.
Acknowledgments. I would like to thank my advisor Benson Farb for introducing me to this problem and for offering many corrections to previous versions of this paper. I would also like to thank Chris Hruska for several useful conversations and for helping me to make sense of Grayson's work.

1.1 Outline

In Section 2, we review some preliminary material on Sol manifolds, regular languages, etc. Next, in Section 3 we discuss a technical condition on partitions of regular languages which implies rational growth. This condition, the falsification by fellow traveler property, is inspired by but different from the condition of the same name defined by Neumann-Shapiro in [NS1] . We then discuss a geometric decomposition of our Sol group in Section 4. This geometric decomposition leads to the quotient ring of integral Laurent polynomials described above. In Section 5 we construct a language which enumerates the ring, and we prove that it satisfies the falsification by fellow traveler property. This proves Theorem  1.1 . We then discuss some open questions, and finally prove Theorem  1.2 in the appendix.

2 Preliminaries

2.1 Sol Manifolds

As discussed in [Th] , Sol manifolds are torus bundles over the circle with Anosov monodromy M   , that is M ∈ S L 2 ( Z )   and M   has two distinct real eigenvalues. Equivalently, | t r a c e ( M ) | > 2   . Let M   be such a matrix, and let a   and b   be generators for Z 2   . Hence, M a   and M b   are well defined. Abusing notation in the obvious way, we say that the torus bundle with monodromy M   is the group with the presentation Γ = < a , b , t | [ a , b ] = 1 , t − 1 a t = M a , t − 1 b t = M b >   Observe that G = < a , t >   is a finite index subgroup of Γ   . If M = ( a b c d )   , then G   corresponds to the torus bundle with fiber generated by a   and M a   .
It is easy to see that G   is isomorphic to the torus bundle with monodromy ( 1 − 1 0 trace ( M ) )   . We shall prove that G   has rational growth with respect to the generating set { a , t }   .
Assumption. To simplify our formulas, we will assume that t r a c e ( M ) > 0   .
The other case is completely analogous.

2.2 Sized Sets and Languages

In the course of our proof, we will construct a series of objects whose growth reflects the growth series of G   . The “size functions” on these objects come from very different sources. The following formalism provides a language with which to compare these objects.
Definition: A sized set is a set X   together with a function | | ⋅ | | : X ⟶ Z ≥ 0   .
A sized set X   has an associated generating function G ( X ) = ∑ k = 0 ∞ c k z k   with c k = | { x ∈ X : | | x | | = k } |   .
Definition: Let X   be a sized set and P   be a partition of X   . In other words, P   is a set of pairwise disjoint subsets of X   so that ⋃ A ∈ P A = X   We define X / P   to be the sized set whose elements are elements of P   and whose size function is | | A | | = min { | | a | | : a ∈ A }  
Definition: Let ( X 1 , | | ⋅ | | 1 )   and ( X 2 , | | ⋅ | | 2 )   be sized sets. A bijection φ : X 1 ⟶ X 2   is a sized set isomorphism if there exists some constant c   so that for all x ∈ X 1   we have | | x | | 1 = | | φ ( x ) | | 2 + c   .
Remark. We allow the constant c   in the definition because we are really interested in the generating functions for sized sets. Adding a constant to the norm corresponds to multiplying the generating function by some power of z   .
This will simplify our arguments.
Definition: Let A   be a finite set, which we will call the alphabet. A language L   over A   is a subset of A *   , the set of finite sequences of elements of A   . Elements of L   are called words.
Languages can be considered sized sets in the following way. Let L   be a language over A   . Consider some φ : A ⟶ Z ≥ 0   , which we will call the weighting. For a 1 a 2 . . . a k ∈ L   , define | | a 1 a 2 . . . a k | | = ∑ i = 1 k φ ( a i )  
Example: Let G   be a group with a finite set of generators S   . Let L   be the language of all words in S   with weighting 1   for each generator. Finally, let P   be the partition which identifies two words if they represent the same element in G   . The series G ( L / P )   is then the usual growth series for G   .

2.3 Regular Languages

We quickly review the theory of finite state automata and regular languages.
For more details see, e.g., [ECHLPT] , Chapter 1.
Definition: A finite state automata on n   strings is a 5-tuple ( 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 ∈ V   (called the start state), F ⊂ V   (called the final states), and l : E ⟶ ∏ i = 1 n ( A ∪ { $ } )   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 ( e ) = ( ⋅ , . . . , $ , ⋅ , . . . )   with the $   in the k t h   place, then l ( f )   also has a $   in the k t h   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 ( Z ) ⊂ ∏ i = 1 n A *   to be the following. Consider any element ( w 1 , . . . , w n ) ∈ ∏ i = 1 n A *   . Assume that the longest word in this tuple has m   letters. For 1 ≤ i ≤ n   and 1 ≤ j ≤ m   define w i j   to be the j t h   letter of w i   if j   is at most the length of w i   and $   otherwise. Then ( w 1 , . . . , w n ) ∈ L ( Z )   if and only if there is some path S = v 1 , e 1 , v 2 , e 2 , . . . , e m , v m + 1 ∈ F   so that for 1 ≤ j ≤ m   we have l ( e j ) = ( w 1 j , w 2 j , . . . , w n j )   We say that L ( Z )   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. ∪   , ∩   , ¬   , ∀   , and ∃   ).
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 φ : A ⟶ Z ≥ 0   be a weighting. Then the generating function G ( L ( Z ) )   with the language L ( Z )   weighted by φ   is a rational function.
Proof: It is a standard fact (see, for instance, [CDP] , Theorem 9.1) that G ( L ( Z ) )   is rational if φ   is the constant function 1   . To deduce the general case from this, replace each edge e   in ( V , E )   by a path of length φ ( l ( e ) )   with each edge in the path labeled by l ( e )   . ⋄  
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 φ   . 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 ′ ⊂ L   so that L ′   is regular and L ′   contains exactly one representative of minimal size for each set in P   .
Definition: We say that our partition P   is a semi-regular partition if there is a finite set of regular languages R h , . . . , R k ⊂ L × L   for h ≤ k   (called the partial acceptors) so that R h , . . . , R k ⊂ { ( w 1 , w 2 ) ∈ L × L : w 1 = w 2 ∈ L / P }  
Definition: We say that a semi-regular 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 ′   of L   containing at least one minimal representative of each set in the partition so that if w ∈ L ′   is not a minimal representative in L / P   then there is some word w ′ ∈ L   so that the following are true.
  • ∙ ( w , w ′ ) ∈ R i   for some i   (and in particular w = w ′   in L / P   )
  • ∙ | | w ′ | | < | | w | |  
  • ∙ For any j   , let s   and s ′   be initial segments of w   and w ′   of length max( j , 0 )   and max( j − i , 0 )   , respectively. Then | | | s | | − | | s ′ | | | ≤ K   (we say that w   and w ′   K   -fellow travel with respect to i   ).
We also require that if w , w ′ ∈ L ′   are both minimal representatives of the same element of L / P   then there is some i   so that ( w , w ′ ) ∈ 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 semi-regular partition with partial acceptors R h , . . . , R k   of a regular language L   and let K   be any number. Fix some h ≤ i ≤ k   . Then the following language is regular.
L ′ = { ( w 1 , w 2 ) ∈ L × L : ( w 1 , w 2 ) ∈ R i , | | w 1 | | > | | w 2 | | ,
and w 1 and w 2 K-fellow travel with respect to i }
Proof: Observe that L ′   is the intersection of R i   and the language
L ′ ′ = { ( w 1 , w 2 ) ∈ ( A * ) 2 : | | w 1 | | > | | w 2 | | , and w 1 and
w 2 K-fellow travel (with respect to i ) }
By Theorem  2.1 it is thus enough to show that L ′ ′   is regular. L ′ ′   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. ⋄  
Theorem 3.2 Let P   be a semi-regular 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 ′   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 
L i = { ( w 1 , w 2 ) ∈ L × L : ( w 1 , w 2 ) ∈ R i , | | w 1 | | > | | w 2 | | ,
and w 1 and w 2 K-fellow travel }
is a regular language for each i   . Hence by Theorem  2.1 
L ′ ′ = { w ∈ L ′ : there does not exist any w ′ ∈ L so that
( w , w ′ ) ∈ L 1 ∪ . . . ∪ L k }
is a regular language. This language is composed of minimal representatives in L ′ / P   . It contains at least one representative of each element. By a remark on page 57 of [ECHLPT] , the language
S = { ( w 1 , w 2 ) ∈ L × L : w 1 is short-lex less than w 2 }
is regular (see page 56 of [ECHLPT] for the definition of the short-lex 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
T = { ( w 1 , w 2 ) ∈ L × L : For some h ≤ i ≤ k ( w 1 , w 2 ) ∈ R i }
is a regular language. We conclude from Theorem  2.1 that
L ′ ′ ′ = { w ∈ L ′ ′ : for all w ′ if ( w , w ′ ) ∈ T then ( w , w ′ ) ∈ D }
is regular. By the definition of the falsification by fellow traveler property, L ′ ′ ′   contains a unique representative of minimal length for each element of L ′ / P   ; i.e. it is a regular minimal cross section of L / P   . ⋄  
Theorem  2.2 thus implies the following.
Corollary 3.3 Let P   be a semi-regular 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 Γ   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 ∏ i = 1 t − k i a ± 1 t k i ) t h   We call h   the height of w   , which we will henceforth denote h ( w )   . Since (continuing our earlier abuse of notation) conjugation by t   acts upon a   by multiplication by M   , each term t − k i a ± 1 t k i   is equal to ± M k i a   . We denote by t y p e ( w )   the expression t y p e ( w ) = ∑ k = − N ′ 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” M a   . We call this polynomial the unreduced type of w   . Let t y p e ¯ ( w )   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 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 ( w 1 ) = h ( w 2 )   and t y p e ¯ ( w 1 ) = t y p e ¯ ( w 2 )   , 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 ∑ k = − N ′ N c k M k a   with c − N ′   and c N   non-zero be an unreduced type and let h   be a height. Then the shortest word with this unreduced type and level has length l = | h | + 2 N ′ + 2 m a x ( N − | h | , 0 ) + ∑ k = − N ′ N | c k |  

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 t a t 2 a 2 t 3 a t 1 a t − 2  

Proof: Without loss of generality assume h ≥ 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 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 ± 1   . This path ends at the point ( ∑ k = − N ′ N | 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 ± 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 x-coordinate of the path moves ∑ k = − N ′ N | c k |   units, and the y-coordinate first goes down N ′   units, then up N ′   units, then up h   units, then up m a x ( n − | h | , 0 )   , and finally down m a x ( n − | h | , 0 )   units. Since any word yielding the desired unreduced type and height must correspond to a similar path, the indicated length is minimal.
⋄  
Remark. The minimal-length 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 = t r a c e ( M )   . Since M   is Anosov, it has two distinct real eigenvalues.
Let λ > 1 λ   be the eigenvalues with eigenvectors v   and v ′   . Let α , α ′ ∈ R   be such that ( 1 , 0 ) = α v + α ′ v ′  
Theorem 4.2 Let w 1   and w 2   be words in the generators of G   with t y p e ( w 1 ) = ∑ k = − N ′ N c k M k a   t y p e ( w 2 ) = ∑ k = − N ′ N c k ′ 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 ( w 1 ) = h ( w 2 )   and 1 − T M a + M 2 a   divides the Laurent polynomial t y p e ( w 1 ) − t y p e ( w 2 ) = ∑ k = − N ′ N ( c k − c k ′ ) M k a  
Proof: Observe that with respect to the basis { v , v ′ }   we have t y p e ¯ ( w 1 ) = ( α ∑ k = − N ′ N c k λ k , α ′ ∑ k = − N ′ N c k λ ′ k )   t y p e ¯ ( w 2 ) = ( α ∑ k = − N ′ N c k ′ λ k , α ′ ∑ k = − N ′ N c k ′ λ ′ k )   Since M   is a 2 × 2   matrix with irrational eigenvalues, λ   and λ ′   have the same minimal polynomial as M   ; i.e. 1 − T z + z 2   , whence the theorem. ⋄  
Consider the set X = Z × Z [ z , z − 1 ]   Define a size function on X   by | | ( h , ∑ k = − N ′ N c k z k | | : = 1 + | h | + 2 N ′ + 2 m a x ( N − h , 0 ) + ∑ k = − N ′ N | c k |   Define a partition P   on X   by the following equivalence relation.
( h 1 , f 1 ) ∼ ( h 2 , f 2 ) ⟺ [ h 1 = h 2 and 1 − T z + z 2 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 semi-regular partition P ′   with the falsification by fellow traveler property so that L / P ′   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 ′   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 | c k | < 5 T   .
Proof: Assume that w   has minimal length and that t y p e ( w ) = ∑ k = − N ′ N c k M k a   Theorem  4.2 tells us that we can, for each k   , add or subtract M k − 1 a − T M k a + M k + 1 a   without changing the group element represented by t y p e ( w )   . Now, if | c k | ≥ 5 T   , add or subtract 5 M k − 1 a − 5 T M k a + 5 M k + 1 a   in such a way as to decrease | c k |   . Examining the above formula for the length of an element representing an unreduced type, we see that we have subtracted 5 T   from the length of our representative and added at most 2 + 2 + 5 + 5 = 14   to its length.
Since T ≥ 3   , we conclude that w   did not have minimal length, a contradiction.
⋄  
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 = ∑ k = − N ′ N c k , i z k   with | c k , i | ≤ A   . Assume that 1 − T z + z 2   divides f 1 − f 2   . Then the coefficients of ( f 1 − f 2 ) / ( 1 − T z + z 2 )   are bounded by B A   .
Proof: Since T ≥ 3   , the largest coefficient which is left when we expand out ( 1 − T z + z 2 ) g ( z )   is at least as large as the largest coefficient of g   . Hence we may set B A = 2 A   ⋄  

5.2 The Language

Fix a natural number n ≥ 1   . Let A n = { − n , . . . , n } × { − 1 , 1 , 2 }   be an alphabet with weighting φ ( t , a ) = | t | + | a |   Consider the language L n   on A n   whose words are of the following form :
( ⋅ , 2 ) . . . ( ⋅ , 2 ) ( ⋅ , ± 1 ) . . . ( ⋅ , ± 1 ) ( ⋅ , 2 ) . . . ( ⋅ , 2 )   We require that there be at least one letter of the form ( ⋅ , ± 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 φ : L n ⟶ X   by
φ ( n 1 ∏ k = 0 ( t k , 2 ) n 2 ∏ k = 0 ( v k , ± 1 ) n 3 ∏ k = 0 ( x k , 2 ) )
= ( ± n 2 , ∑ k = 0 n 1 t k z k − n 1 − 1 + ∑ k = 0 n 2 v k z k + ∑ k = 0 n 3 x k z n 2 + 1 + k )
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 size-preserving 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 ≥ 5 T   the induced map φ : L n / P n ⟶ X / P   is an isomorphism.

5.3 The Partial Acceptors

Fix an integer i   . Define a language
R i = { ( w 1 , w 2 ) ∈ L n × L n : w 1 = w 2 in L n / P n
and φ ( w 1 ) = ( h , ∑ k = − N 1 ′ N 1 c k z k ) , φ ( w 2 ) = ( h , ∑ k = − N 2 ′ N 2 d k z k )
with N 1 ′ − N 2 ′ = i }
Theorem 5.3 R i   is a regular language.
Proof: We build an automata accepting R i   . Without loss of generality i ≥ 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 1 − T z + 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 ′ , a ′ )   . Place the ( t ′ , a ′ )   at the end of our k   pieces of memory and remove the element ( t ′ ′ , a ′ ′ )   from the beginning. Let c   be the first “correction term”. The next coefficient of the quotient is then t − t ′ ′ + 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 ′ ′ + c )   to it and place t − t ′ ′ + 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). ⋄  

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 5 T   contains at least one minimal-length representative of each class in the partition. Consider any word w ∈ L 5 T   . 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 ′ ∈ L 5 T   of minimal length we have that ( w , w ′ ) ∈ R i   for some − m ≤ i ≤ m   .
  • 2. If w   is not of minimal length, then there is some w ′ ′ ∈ L n   so that | | w ′ | | < | | w | |   , ( w , w ′ ′ ) ∈ R i   for some − m ≤ i ≤ m   , and w   and w ′ ′   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 ′   be two words which represent the same element in L / P   , and let φ ( w ) = ∑ k = − N 1 ′ N 1 c k M k a   φ ( w ′ ) = ∑ k = − N 2 ′ N 2 d k M k a   ∑ ( c k − d k ) z k = ( 1 − T z + z 2 ) ∑ 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 ′   .
The new w ′   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 ′   c − N 1 ′ + 1   c − N 1 ′ + 2   c − N 1 ′ + 3   c − N 1 ′ + 4   c − N 1 ′ + 5   ...
e − N 1 ′   -T e − N 1 ′   e − N 1 ′  
e − N 1 ′ + 1   − T e − N 1 ′ + 1   e − N 1 ′ + 1  
e − N 1 ′ + 2   − T e − N 1 ′ + 2   e − N 1 ′ + 2  
e − N 1 ′ + 3   − T e − N 1 ′ + 3   e − N 1 ′ + 3  
. . . . . . . . . . . . . . . . . .
d − N 1 ′   d − N 1 ′ + 1   d − N 1 ′ + 2   d − N 1 ′ + 3   d − N 1 ′ + 4   d − N 1 ′ + 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 1 − T z + 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 ′ ∈ L 5 T   be so that w = w ′   in L / P   and let c k   , N 1   , N 1 ′   , d k   , N 2   , N 2 ′   , and e k   be associated to w   and w ′   as above. Assume that | N 1 ′ − N 2 ′ | > ( T + 2 ) B   . Then there is some w ′ ′ ∈ L 5 T + ( T + 1 ) B   so that | | w ′ ′ | | < | | w | |   and ( w , w ′ ′ ) ∈ R i   for some − ( T + 4 ) B ≤ i ≤ ( T + 4 ) B   .
Proof: We will assume that N 1 ′ > N 2 ′   ; 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 ′   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 | | w ′ ′ | | < | | w | |   . The other claims about w ′ ′   are clear. ⋄  
Lemma 5.6 Let w ∈ L 5 T   and w ′ ∈ L 5 T + ( T + 1 ) B   be so that ( w , w ′ ) ∈ R i   for some − ( T + 4 ) B ≤ i ≤ ( T + 4 ) B   and let c k   , N 1   , N 1 ′   , d k   , N 2   , N 2 ′   , and e k   be associated to w   and w ′   as above. Then there exists some w ′ ′ ∈ L 5 T + 3 ( T + 1 ) B   so that ( w , w ′ ′ ) ∈ R j   for some − ( T + 4 ) B ≤ j ≤ ( T + 4 ) B   and w   and w ′ ′   K   -fellow travel with respect to j   for K = ( T + 2 ) B   .
Proof: We will assume without loss of generality that N 1 ′ ≥ N 2 ′   Assume that w   and w ′   do not K   -fellow travel. There are two cases.
We again will assume that N 1 ′ > N 2 ′   . First, assume that there is some subword w 1   of w   and corresponding subword w 2   of w ′   so that | | w 2 | | > | | w 1 | | + ( 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 ′   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 | | w ′ | | < | | w | |   , but now we have for all corresponding initial segments w 1   and w 2   that | | w 2 | | ≤ | | w 1 | | + ( 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 ′   so that | | w 1 | | > | | w 2 | | + ( 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 ′   has the desired properties. This completes the proof. ⋄  
We can now prove the two items indicated above. Set m = ( T + 4 ) B   , n = 5 T + 3 ( T + 1 ) B   , and K = ( T + 2 ) B   . Claim 1 is an immediate corollary of Lemma  5.5 ; if w   and w ′   are not read by an appropriate R i   then they are not minimal. To prove claim 2, let w ∈ L 5 T   be some non-minimal representative in L / P   , and let w ′ ∈ L 5 T   be a minimal representative. Lemma  5.5 allows us to modify w ′   so that w   and w ′   are read by an appropriate R i   . Finally, Lemma  5.6 allows us to modify w ′   so that it K   -fellow travels with w   , as desired. ⋄  

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 ( 2 1 1 1 )   .
The 3-dimensional 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 higher-dimensional 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 ′   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 quasi-isometry?
Remark. Observe that S L 2 ~   and H 2 × R   are quasi-isometric, and hence the fundamental groups of manifolds modeled on these geometries are quasi-isometric.
An easy consequence of Cannon's work (see [Ca] ) is that the fundamental groups of manifolds modeled on H 2 × R   are rational with respect to any generating set.
The work of Shapiro suggests that this is probably false for manifolds modeled on S L 2 ~   (see [Sh2] ), so the property of being rational with respect to all generating sets is likely not well-behaved under quasi-isometry. The question of whether the fundamental group of any 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 ∑ k = 0 ∞ 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 k − 1 + c 2 a k − 2 + . . . + c l a k − l  
Let a k = | { x ∈ X : | | x | | = k } |   . By assumption G ( z ) = ∑ k = 0 ∞ a k z k   is rational, and our goal is to produce a regular language L   so that G ( L ) = G ( z )   .
Let c 1 , . . . , c l   be the constants given by Theorem  7.1 . Let A   be the following alphabet.
{ I i j : 1 ≤ j ≤ l − 1 , 1 ≤ i ≤ a j } ∪ { C i j : 1 ≤ j ≤ l , 1 ≤ i ≤ c j ∥   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

  1. Benson, M., Growth series of finite extensions of Z n   are rational, Invent. Math. 73 (1983), no. 2, 251–269.
  2. 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, 185-196.
  3. Bourbaki N., Groupes et algébres de Lie, Chapitres 4,5 et 6, Paris : Hermann, 1968.
  4. Brady, Noel, Sol geometry groups are not asynchronously automatic, Proc. London Math. Soc. (3), 83 (2001), no. 1, 93-119.
  5. Brazil, Marcus., Growth functions for some nonautomatic Baumslag-Solitar groups, Trans. Amer. Math. Soc. 342 (1994), no. 1, 137-154.
  6. Cannon, James W., The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata 16 (1984), no. 2, 123–148.
  7. Coornaert, M., Delzant, T., Papadopoulos, A., Géométrie et théorie des groupes, Berlin : Springer Verlag, 1990.
  8. de la Harpe, Pierre Topics in geometric group theory, Chicago : University of Chicago Press, 2000.
  9. 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.
  10. Floyd, William J. and Steven P. Plotnick, Growth functions on Fuchsian groups and the Euler characteristic. Invent. Math. 88 (1987), no. 1, 1-29.
  11. Grayson, M. A. Geometry and Growth in Three Dimensions, unpublished thesis, Princeton University, 1983.
  12. Kharlampovich, O. G. A finitely presented solvable group with unsolvable word problem. (Russian), Izv. Akad. Nauk SSSR Ser. Math. 45 (1981), no. 4, 852-873, 928.
  13. Neumann, Walter D., and Michael Shapiro, Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. math. 120, 259-287 (1995)
  14. Neumann, Walter D., and Michael Shapiro. Regular geodesic normal forms in virtually abelian groups. Bull. Austral. Math. Soc., 55 (1997) 3, 517-519.
  15. Shapiro, Michael, A geometric approach to the almost convexity and growth of some nilpotent groups., Math. Ann., 285 (1989), 601-624.
  16. Shapiro, Michael, Growth of a P S L 2 R   manifold group. Math. Nachr. 167, (1994), 279-312.
  17. Stanley, Richard P., Enumerative combinatorics, vol I. Wadsworth and Brooks, Monterey, CA, 1986.
  18. Stoll, Michael, Rational and transcendental growth series for the higher Heisenberg groups, Invent. Math. 126 (1996), no. 1, 85–109.
  19. Thurston, William P., Three-dimensional geometry and topology. Vol. 1. Princeton University Press, Princeton, NJ, 1997
  20. Weber, Bernhard, Zur Rationalität polynomialer Wachstumsfunktionen, Bonner Mathematische Schriften 197, 1989.

Dept. of Mathematics, University of Chicago 5734 University Ave. Chicago, Il 60637 E-mail: andyp@math.uchicago.edu