Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Journal of Symbolic ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Symbolic Computation
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Journal of Symbolic Computation
Article . 1997
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Symbolic Computation
Article . 1997 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
DBLP
Article . 2021
Data sources: DBLP
versions View all 6 versions
addClaim

Computing Sylow Subgroups in Permutation Groups

Computing Sylow subgroups in permutation groups
Authors: John J. Cannon; Bruce C. Cox; Derek F. Holt;

Computing Sylow Subgroups in Permutation Groups

Abstract

This paper describes practical algorithms for the computation of Sylow subgroups of a permutation group \(G\) as well as for finding group elements that conjugate given Sylow subgroups into each other. For the first problem the following techniques have been in use: 1. Finding the Sylow subgroup in the centralizer of a \(p\)-element of the Sylow subgroups' centre. (\textit{G. Butler} and \textit{J. Cannon} [J. Symb. Comput. 12, No. 4/5, 443-457 (1991; Zbl 0787.20004)]). 2. Reduction to transitive groups with at most one minimal block system and (if imprimitive) the image of the block action being a \(p\)-group, as suggested by \textit{M. D. Atkinson} and \textit{P.M. Neumann} [Congr. Numerantium 79, 55-60 (1990; Zbl 0862.20002)]. 3. Iterative construction of the intersections of the Sylow subgroup with the groups in a composition series. A polynomial time albeit impractical algorithm for this has been designed by \textit{W. M. Kantor} [J. Algorithms 11, No. 4, 523-563 (1990; Zbl 0731.20005)]. The practicality of this has recently been enhanced by \textit{P. Morje} [Groups and computation II. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 257-272 (1997; Zbl 0878.20005)]. The authors improve on strategy 2 by considering further reductions. In the imprimitive case the Sylow subgroup of the kernel of the action on (maximal) blocks is extended by a Frattini-argument construction that requires finding a conjugating element for Sylow subgroups of the kernel. In the primitive case the O'Nan-Scott classification is invoked, referring for the analysis to the authors' preceding paper [J. Symb. Comput. 24, No. 3-4, 285-301 (1997)]. A resulting composed structure of \(G\) is used to reduce the computation to smaller constituents, in the almost simple case strategy 1 is maintained. For the conjugation of Sylow subgroups the same reductions are used, the case of a unique minimal block system and the non-affine primitive cases however is delegated to a backtrack search. The algorithms are given in explicit form that allows immediate implementation in systems like GAP or MAGMA. The authors also mention various implementational tricks that can be used to improve practical performance. The paper closes with example runtimes and a discussion of the algorithms' practical performance. As timings are only given for the authors' new algorithm, it is difficult to assess the improvement in performance. Unfortunately all the wreath product type examples given are full wreath products, which is untypical. The authors conclude that the practical bottleneck of their algorithm is the backtrack that can be invoked when searching a conjugating element; the worst case they list took over 40 hours for computing \(\text{Sylow}(S_{27}\wr S_9,7)\). They expect improvements due to better pruning in the backtrack search.

Related Organizations
Keywords

Algebra and Number Theory, Sylow subgroups, permutation groups, conjugating elements, block actions, Symbolic computation and algebraic computation, algorithms, Subgroups of symmetric groups, Computational Mathematics, Computational methods (permutation groups), Sylow subgroups, Sylow properties, \(\pi\)-groups, \(\pi\)-structure, minimal block systems

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    3
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3
Average
Average
Average
hybrid