Sylow's theorem in polynomial time (Q1063109): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Created claim: DBLP publication ID (P1635): journals/jcss/Kantor85, #quickstatements; #temporary_batch_1731505720702
 
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0022-0000(85)90052-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2047131975 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3895642 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5662096 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Sylow 2-subgroups of the finite classical groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3848237 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3941595 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3253828 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Singer-Zyklen in klassischen Gruppen / rank
 
Normal rank
Property / cites work
 
Property / cites work: Permutation representations of the finite classical groups of small degree or rank / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-time algorithms for finding elements of prime order and sylow subgroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial-time versions of Sylow's theorem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time / rank
 
Normal rank
Property / cites work
 
Property / cites work: A polynomial bound for the orders of primitive solvable groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4190797 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sylow p-Subgroups of the Classical Groups Over Finite Fields with Characteristic Prime to p / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5512231 / rank
 
Normal rank
Property / DBLP publication ID
 
Property / DBLP publication ID: journals/jcss/Kantor85 / rank
 
Normal rank

Latest revision as of 14:59, 13 November 2024

scientific article
Language Label Description Also known as
English
Sylow's theorem in polynomial time
scientific article

    Statements

    Sylow's theorem in polynomial time (English)
    0 references
    0 references
    1985
    0 references
    The main theorem of the paper states that there are polynomial-time algorithms which, when given a subgroup G of the symmetric group \(S_ n\) and a prime p, solve the following problems: (i) given a p-subgroup P of G, find a Sylow p-subgroup of G containing P; and (ii) given Sylow p- subgroups \(P_ 1\), \(P_ 2\) of G, find \(g\in G\) conjugating \(P_ 1\) to \(P_ 2\). (G and its subgroups are specified in terms of generating permutations.) The result is mainly of theoretical interest as the running time of the algorithms is \(O(n^ 9)\). The proof makes use of the classification of finite simple groups. To solve the problems for a simple group \(G\leq S_ n\), \(| G| >n^ 8\), the ''natural'' permutation representation of G is constructed in polynomial time: if \(G\simeq A_ m\) then an m-element set and the action of G on it; if G is isomorphic to a classical group then a vector space V \((| V| <n^ 2)\), a form on V if G is symplectic, orthogonal, or unitary, and the action of G on the set of 1-spaces of V. Having a solution for simple groups, the algorithms consist of several reductional procedures. For solvable groups the algorithms can be simplified and extended to finding Hall \(\pi\)-subgroups and finding conjugating elements for Hall \(\pi\)- subgroups; these algorithms are given in the Appendix.
    0 references
    polynomial-time algorithms
    0 references
    symmetric group
    0 references
    Sylow p-subgroups
    0 references
    classification of finite simple groups
    0 references
    permutation representation
    0 references
    solvable groups
    0 references
    Hall \(\pi \) -subgroups
    0 references

    Identifiers