Skip to content

Research at St Andrews

Minimal and random generation of permutation and matrix groups

Research output: Contribution to journalArticlepeer-review

Abstract

We prove explicit bounds on the numbers of elements needed to generate various types of finite permutation groups and finite completely reducible matrix groups, and present examples to show that they are sharp in all cases. The bounds are linear in the degree of the permutation or matrix group in general, and logarithmic when the group is primitive. They can be combined with results of Lubotzky to produce explicit bounds on the number of random elements required to generate these groups with a specified probability. These results have important applications to computational group theory. Our proofs are inductive and largely theoretical, but we use computer calculations to establish the bounds in a number of specific small cases.
Close

Details

Original languageEnglish
Pages (from-to)195-214
Number of pages20
JournalJournal of Algebra
Volume387
Early online date12 May 2013
DOIs
Publication statusPublished - 1 Aug 2013

    Research areas

  • Finite groups , Generation of groups , Matrix groups , Permutation groups , Probabilistic and symptotic group theory

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  2. The non-commuting, non-generating graph of a nilpotent group

    Cameron, P. J., Freedman, S. D. & Roney-Dougal, C. M., 29 Jan 2021, In: Electronic Journal of Combinatorics. 28, 1, 15 p., P1.16.

    Research output: Contribution to journalArticlepeer-review

  3. Normalisers of primitive permutation groups in quasipolynomial time

    Roney-Dougal, C. M. & Siccha, S., 23 Apr 2020, In: Bulletin of the London Mathematical Society. 52, 2, p. 358-366

    Research output: Contribution to journalArticlepeer-review

  4. Involution centralisers in finite unitary groups of odd characteristic

    Glasby, S., Praeger, C. & Roney-Dougal, C. M., 1 Mar 2020, In: Journal of Algebra. 545, p. 245-299

    Research output: Contribution to journalArticlepeer-review

  5. On random presentations with fixed relator length

    Ashcroft, C. & Roney-Dougal, C. M., 19 Jan 2020, In: Communications in Algebra. Latest Articles, 15 p.

    Research output: Contribution to journalArticlepeer-review

Related by journal

  1. A transversal property for permutation groups motivated by partial transformations

    Araújo, J., Araújo, J. P., Bentz, W., Cameron, P. J. & Spiga, P., 5 Jan 2021, In: Journal of Algebra. 19 p.

    Research output: Contribution to journalArticlepeer-review

  2. Groups generated by derangements

    Bailey, R. A., Cameron, P. J., Giudici, M. & Royle, G. F., 15 Apr 2021, In: Journal of Algebra. 572, p. 245-262

    Research output: Contribution to journalArticlepeer-review

  3. Primitive permutation groups and strongly factorizable transformation semigroups

    Araújo, J., Bentz, W. & Cameron, P. J., 1 Jan 2021, In: Journal of Algebra. 565, p. 513-530

    Research output: Contribution to journalArticlepeer-review

  4. Involution centralisers in finite unitary groups of odd characteristic

    Glasby, S., Praeger, C. & Roney-Dougal, C. M., 1 Mar 2020, In: Journal of Algebra. 545, p. 245-299

    Research output: Contribution to journalArticlepeer-review

  5. The Hall–Paige conjecture, and synchronization for affine and diagonal groups

    Bray, J., Cai, Q., Cameron, P. J., Spiga, P. & Zhang, H., Mar 2020, In: Journal of Algebra. 545, p. 27-42

    Research output: Contribution to journalArticlepeer-review

ID: 5157201

Top