Isomorphism in expanding families of indistinguishable groups

Abstract

For every odd prime $p$ and every integer $n\ge 12$ there is a Heisenberg group of order $p^{5n/4+O(1)}$ that has $p^{n^2/24+O(n)}$ pairwise nonisomorphic quotients of order $p^n$. Yet, these quotients are virtually indistinguishable. They have isomorphic character tables, every conjugacy class of a non-central element has the same size, and every element has order at most $p$. They are also directly and centrally indecomposable and of the same indecomposability type. The recognized portions of their automorphism groups are isomorphic, represented isomorphically on their abelianizations, and of small index in their full automorphism groups. Nevertheless, there is a polynomial-time algorithm to test for isomorphisms between these groups.

28 pages

References in corpus (1)

• Finding central decompositions of p-groups

Cited by in corpus (14)

• A fast isomorphism test for groups of genus 2
• The threshold for subgroup profiles to agree is $\Omega (\log n)$
• Skolem-Noether for nilpotent products
• A spectral theory for transverse tensor operators
• On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract)
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
• Groups acting on tensor products
• Normalizers and permutational isomorphisms in simply-exponential time
• On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
• Polynomial-time isomorphism test of groups that are tame extensions
• Tensor Isomorphism by conjugacy of Lie algebras
• Subgroups of simple groups are as diverse as possible
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
• Enumerating isoclinism classes of semi-extraspecial groups