Volume 15 (2019)
Article 19 pp. 1-25
The Threshold for Subgroup Profiles to Agree is Logarithmic
Received: December 20, 2016
Revised: October 19, 2019
Published: December 21, 2019
Revised: October 19, 2019
Published: December 21, 2019
Keywords: group isomorphism, profiles, $p$-groups
Categories: complexity theory, lower bounds, group isomorphism, graph isomorphism, profiles, $p$-groups
ACM Classification: F.2.2
AMS Classification: 68Q17, 20D15, 20F69, 68Q25
Abstract: [Plain Text Version]
For primes $p> 2$ and $e> 3$ there are at least $p^{e-3}/e$ groups of order $p^{2e+2}$ that have equal multisets of isomorphism types of proper subgroups and proper quotient groups, isomorphic character tables, and power maps. This obstructs recent speculation concerning a path towards efficient isomorphism tests for general finite groups. These groups have a special-purpose deterministic polynomial-time isomorphism test.
Licensed under a Creative Commons Attribution License (CC-BY)