Polynomial-time isomorphism test of groups that are tame extensions (Extended abstract)

Grochow, JA; Qiao, Y

Polynomial-time isomorphism test of groups that are tame extensions (Extended abstract)

Grochow, JA Qiao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, 9472 pp. 578 - 589
Issue Date:: 2015-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (332.28 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Grochow, JA	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.date.issued	2015-01-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, 9472 pp. 578 - 589	en_US
dc.identifier.isbn	9783662489703	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/130882
dc.description.abstract	© Springer-Verlag Berlin Heidelberg 2015. We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) imply that GpI reduces to the following: given groups G,H with characteristic subgroups of the same type and isomorphic to ℤdp , and given the coset of isomorphisms Iso(G/ℤdp ,H/ℤdp), compute Iso(G,H) in time poly(\|G\|). Babai&Qiao (STACS 2012) solved this problem when a Sylow p-subgroup of G/ℤdp is trivial. In this paper, we solve the preceding problem in the so-called “tame” case, i. e., when a Sylow p-subgroup of G/ℤdp is cyclic, dihedral, semi-dihedral, or generalized quaternion. These cases correspond exactly to the group algebra (Formula presented.) being of tame type, as in the celebrated tame-wild dichotomy in representation theory. We then solve new cases of GpI in polynomial time. Our result relies crucially on the divide-and-conquer strategy proposed earlier by the authors (CCC 2014), which splits GpI into two problems, one on group actions (representations), and one on group cohomology. Based on this strategy, we combine permutation group and representation algorithms with new mathematical results, including bounds on the number of indecomposable representations of groups in the tame case, and on the size of their cohomology groups. Finally, we note that when a group extension is not tame, the preceding bounds do not hold. This suggests a precise sense in which the tame-wild dichotomy from representation theory may also be a key barrier to cross to put GpI into P.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-662-48971-049	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Polynomial-time isomorphism test of groups that are tame extensions (Extended abstract)	en_US
dc.type	Conference Proceeding
utslib.citation.volume	9472	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	9472	en_US

Abstract:

© Springer-Verlag Berlin Heidelberg 2015. We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) imply that GpI reduces to the following: given groups G,H with characteristic subgroups of the same type and isomorphic to ℤdp , and given the coset of isomorphisms Iso(G/ℤdp ,H/ℤdp), compute Iso(G,H) in time poly(|G|). Babai&Qiao (STACS 2012) solved this problem when a Sylow p-subgroup of G/ℤdp is trivial. In this paper, we solve the preceding problem in the so-called “tame” case, i. e., when a Sylow p-subgroup of G/ℤdp is cyclic, dihedral, semi-dihedral, or generalized quaternion. These cases correspond exactly to the group algebra (Formula presented.) being of tame type, as in the celebrated tame-wild dichotomy in representation theory. We then solve new cases of GpI in polynomial time. Our result relies crucially on the divide-and-conquer strategy proposed earlier by the authors (CCC 2014), which splits GpI into two problems, one on group actions (representations), and one on group cohomology. Based on this strategy, we combine permutation group and representation algorithms with new mathematical results, including bounds on the number of indecomposable representations of groups in the tame case, and on the size of their cohomology groups. Finally, we note that when a group extension is not tame, the preceding bounds do not hold. This suggests a precise sense in which the tame-wild dichotomy from representation theory may also be a key barrier to cross to put GpI into P.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/130882