Polynomial-time computation in matrix groups
Eugene M. Luks, Takunari Miyazaki · 1999
This dissertation investigates deterministic polynomial-time computation in matrix groups over finite fields. Of particular interest are matrix-group problems that resemble testing graph isomorphism. The main results are instances where the problems admit polynomial-time solutions and methods that enable such efficiency. A permutation-group problem that generalizes graph-isomorphism testing is the problem of finding stabilizers of sets. For an integer constant d > 0, let Γd denote the class of finite groups all of whose nonabelian composition factors lie in Sd. A result of Luks asserts that in Γ d one can find set-stabilizers in polynomial time. The set-stabilizer problem has important generalizations in matrix groups. Let G be a matrix group on a vector space V over a finite field. The vector-stabilizer problem asks: given v∈V , find the subgroup of G stabilizing v. The subspace-stabilizer problem asks: given W⊂V , find the subgroup of G stabilizing W. A critical foundation for group computation is the ability to perform testing membership of an element in a group. In matrix groups, a polynomial-time method seems unlikely since membership-testing already subsumes the discrete-log problem. Nevertheless, assuming a polynomial bound on the primes in |G| other than the field characteristic, Luks has found polynomial-time solutions for testing membership and also for finding stabilizers of vectors and subspaces in solvable groups. The main theme of this dissertation is the generalization of the solvable-matrix group algorithms to algorithms for matrix groups in Γd . Assuming the same bound on these primes, we establish polynomial-time membership-testing in a broader class than Γd: matrix groups all of whose nonabelian composition factors have polynomially bounded orders. Now assume a polynomial bound on the primes in |G| and the field characteristic. Based on the membership-testing algorithm, we then develop a divide-and-conquer paradigm for finding stabilizers of vectors and subspaces in polynomial time for G∈Gd . This result exploits Babai, Cameron, and Palfy's theorem on the polynomial orders of primitive groups in Γd and Ronyai's algorithm for finding irreducible subspaces.