Black box exceptional groups of Lie type.

DOI10.1090/S0002-9947-2013-05822-9MaRDI QIDQ2847127zbMATH OpenOpenAlexWikidataFDO

Authors Kay Magaard, William M. Kantor

Publication date 4 September 2013

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.3000

zbMATH Keywords

black box groupsconstructive recognitionexceptional groups of Lie typeexceptional simple groupsfinite linear groupsLas Vegas algorithms

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to group theory (20-04) Simple groups: alternating groups and groups of Lie type (20D06) Linear algebraic groups over finite fields (20G40) Probabilistic methods in group theory (20P05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: If a black box group is known to be isomorphic to an exceptional simple group of Lie type of (twisted) rank $>1$, other than any ${}^2{F}_4(q)$, over a field of known size, a Las Vegas algorithm is given to produce a constructive isomorphism. In view of its timing, this algorithm yields an upgrade of all known nearly linear time Monte Carlo permutation group algorithms to Las Vegas algorithms when the input group has no composition factor isomorphic to any group ${}^2{F}_4(q)$ or ${}^2{G}_2(q)$.

Review text

This paper takes a further step in the development of computational algorithms for the recognition and investigation of finite simple groups and linear groups definable over finite fields. In the case considered in this paper, the given group \(G\) is assumed to be a perfect central extension of an exceptional simple group \(H\) of Lie type, of (twisted) rank greater than \(1\) over a finite field of known order \(q\), other than \(^2F_4(q)\). Also the group is a `black-box' group, not given in any particular representation.NEWLINENEWLINE The authors describe a Las Vegas algorithm that recognises the group \(G/Z(G)\), and gives a constructive isomorphism between it and the identified exceptional simple group \(H\), as well as a corresponding epimorphism from the universal cover \(\widehat H\) (of \(H\)) onto \(G\).NEWLINENEWLINE The approach involves finding a long root element and then building a subgroup isomorphic to \(\mathrm{SL}(3,q)\), and also a subgroup \(\mathrm{Spin}^-_8(q)\) when the Lie rank is greater than 2. Pieces of these groups are used to obtain the centraliser of a subgroup isomorphic to \(\mathrm{SL}(2,q)\) generated by long root groups. Then (in contrast to approach for classical groups) the algorithm finds all of the root groups corresponding to a root system, and verifies the standard commutator relations that define these groups. The corresponding presentation guarantees the Las Vegas nature of the algorithm.NEWLINENEWLINE The algorithm does not run in polynomial time in the input, as the complexity (resulting from two of the main steps) involves \(q\), but the authors propose some possible variants which might lead to more effective implementations.

Recommendations

• Black box exceptional groups of Lie type. II.
• Black box groups.
• Black-box recognition of finite simple groups of Lie type by statistics of element orders
• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• Recognition of finite exceptional groups of Lie type.

Cites work

• A black-box group algorithm for recognizing finite symmetric and alternating groups, I
• A Recognition Algorithm for Special Linear Groups
• An algorithm for Lang's theorem.
• An improved method for generating the centralizer of an involution
• Black box classical groups.
• Black-box recognition of finite simple groups of Lie type by statistics of element orders
• Computing Chevalley bases in small characteristics
• Computing in groups of Lie type
• Constructive membership in black-box groups
• Constructive recognition of \(\text{SL}_3(q)\).
• Constructive recognition of classical groups in their natural representation.
• Constructive recognition of 𝑃𝑆𝐿(2,𝑞)
• Fast constructive recognition of black box orthogonal groups.
• Fast constructive recognition of black box symplectic groups.
• Fast Constructive Recognition of Black-Box Unitary Groups
• Fast recognition of classical groups over large fields
• Finding the characteristic of a group of Lie type
• Generating random elements in finite groups.
• Generating random elements of a finite group
• Generators, relations and coverings of algebraic groups. II
• scientific article; zbMATH DE number 3135133 (Why is no real title available?)
• scientific article; zbMATH DE number 3904833 (Why is no real title available?)
• scientific article; zbMATH DE number 1187223 (Why is no real title available?)
• scientific article; zbMATH DE number 3479126 (Why is no real title available?)
• scientific article; zbMATH DE number 1283936 (Why is no real title available?)
• scientific article; zbMATH DE number 1284153 (Why is no real title available?)
• scientific article; zbMATH DE number 1004932 (Why is no real title available?)
• scientific article; zbMATH DE number 1111401 (Why is no real title available?)
• scientific article; zbMATH DE number 3439117 (Why is no real title available?)
• scientific article; zbMATH DE number 1836313 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 3392741 (Why is no real title available?)
• Large element orders and the characteristic of Lie-type simple groups.
• Linear Groups with Orders Having Certain Large Prime Divisors
• On constructive recognition of a black box \(\text{PSL}(d,q)\).
• Presentations of finite simple groups: a computational approach.
• Presentations of finite simple groups: a quantitative approach.
• Prime power graphs for groups of Lie type
• Primitive permutation groups of odd degree, and an application to finite projective planes
• Recognising simplicity of black-box groups by constructing involutions and their centralisers.
• Recognising the Suzuki groups in their natural representations.
• Short presentations for finite groups
• Simple groups in computational group theory
• Subgroups generated by root elements in groups of Lie type
• Subgroups of Classical Groups Generated by Long Root Elements
• Subgroups of Maximal Rank in Finite Exceptional Groups of Lie Type
• The 2-Transitive Permutation Representations of the Finite Chevalley Groups
• The computational matrix group project.
• The geometry of root subgroups in exceptional groups. I
• The maximal subgroups of the Chevalley groups \(G_ 2(q)\) with q odd, the Ree groups \(2G_ 2(q)\), and their automorphism groups
• The maximal subgroups of the Steinberg triality groups \(3D_ 4(q)\) and their automorphism groups
• The Maximal Tori in The Finite Chevalley Groups of Type E₆E₇And E₈
• The semisimple conjugacy classes and the generic class number of the finite simple groups of lie type E₈

Cited in

(13)

• Prime power graphs for groups of Lie type
• Constructive recognition of \(\text{SL}_3(q)\).
• Black box classical groups.
• Recognition of finite exceptional groups of Lie type.
• New approaches in black box group theory.
• THE ANDREWS–CURTIS CONJECTURE AND BLACK BOX GROUPS
• Minimum circuit size, graph isomorphism, and related problems
• Black box exceptional groups of Lie type. II.
• Black-box recognition of finite simple groups of Lie type by statistics of element orders
• A practical model for computation with matrix groups.
• Black box groups.
• On the semidirect discrete logarithm problem in finite groups
• An algorithm for Lang's theorem.

This page was built for publication: Black box exceptional groups of Lie type.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2847127)