Random Quotients of the Modular Group are Rigid
by
Paul E. Schupp
University of Illinois
Coauthors: Ilya Kapovich

We porve that quotients of the modular group, by any finite number

of additional relators, generically satisfy a very strong Mostow-type

rigidity. The associated geometric structure of such a quotient

is its Cayley graph on standard generators, a and b, of the modular

group with the word metric. Generically, two quotients are isomorphic

if and only if their associated Cayley graphs are isometric. Indeed,

one can at most interchange the edge label b and b^(-1).

As a consequence, although the isomorphism problem remains

unsolvable for quotients of the modular group, it generic-case

complexity is strongly polynomial time. Random quotients are

"essentially incompressible". This means that the shortest

possible finite presentation of such quotients are uniformly "almost"

as long as the given presentation. Also, one can calculate

the exact asymptotics as n goes to infinity of the number of isomorphism classes of quotients

with m relators all of length n.

Date received: February 28, 2006