Las Vegas algorithms for matrix groups

We consider algorithms in finite groups, given by a list of generators. We give polynomial time Las Vegas algorithms (randomized, with guaranteed correct output) for basic problems for finite matrix groups over the rationals (and over algebraic number fields): testing membership, determining the order, finding a presentation (generators and relations), and finding basic building blocks: center, composition factors, and Sylow subgroups. These results extend previous work on permutation groups into the potentially more significant domain of matrix groups. Such an extension has until recently been considered intractable. In case of matrix groups G of characteristic p, there are two basic types of obstacles to polynomial-time computation: number theoretic (factoring, discrete log) and large Lie-type simple groups of the same characteristic p involved in the group. The number theoretic obstacles are inherent and appear already in handling abelian groups. They can be handled by moderately efficient (subexponential) algorithms. We are able to locate all the nonabelian obstacles in a normal subgroup N and solve all problems listed above for G/N. >

Authors

• Robert Beals
• László Babai

Keywords

• Polynomials
• Computational Intelligence Society
• Testing
• Marine vehicles
• Statistical analysis
• Computer science
• Mathematics
• Complexity theory
• Galois fields
• Packaging
• Las Vegas
• Las Vegas Algorithms
• Group Elements
• Characteristic Zero
• Abelian Group
• Composition Factors
• Finite Group
• Normal Subgroup
• Number Theory
• Permutation Group
• Discrete Logarithm
• Proof Of Theorem
• Random Walk
• Dimensional Vector
• Commutative
• Regulon
• Cycle Length
• Input Size
• Matrix Representation
• Linear Representation
• Power Of 3
• Finite Field
• Nilpotent Groups
• Classical Group
• Recursive Algorithm
• Random Element
• Field In Order
• Prime Number
• Input Length
• Polynomial-time Algorithm