BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-227
ENTRY:: January 28, 2008
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Deciding Finiteness for Matrix Groups Over Function Fields
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Beals, Robert
AUTHOR:: Rockmore, Daniel N.
AUTHOR:: Tan, Ki-Seng
DATE:: June 1995
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-227.pdf
ABSTRACT:: 
Let S be any finite subset GLn(F(t)) where F is a field.  In this paper we give algorithms to decide if the group generated by S is finite.  In the case of characteristic zero, slight modifications of earlier work of Babai, Beals and Rockmore [1] give polynomial time deterministic algorithms to solve this problem.  The case of positive characteristic turns out to be more subtle and our algorithms depend on a structure theorem proved here, generalizing a theorem of Weil.  We also present a fairly detailed analysis of the size of finite subgroups in this case and give bounds which depend upon the number of generators.  To this end we also introduce the notion of the diameter of a finitely generated algebra and derive some upper bounds related to this quantity.  In positive characteristic the deterministic algorithms we present are exponential.  A randomized algorithm based on ideas of the Meat-Axe is also given.  While not provably efficient, the success of the Meat-Axe suggests the randomized algorithm will be useful.
END:: ncstrl.dartmouthcs//TR94-227