Source-linked AI summary
Algorithms for Finite Group Epimorphism Testing
Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
TL;DR
The paper asks which structured finite-group classes admit efficient Group Epimorphism testing from Cayley tables, where comparatively little is known. It exploits group structure and representation-theoretic reductions to obtain polynomial-time tests for several classes, while identifying scope boundaries in more general Fitting-free settings.
Problem
For finite groups given by Cayley tables, the computational complexity of GpEpi is comparatively little known despite extensive study of related isomorphism problems.
Method
The paper exploits normal Hall subgroups, complements, representation theory, and reductions to related algorithmic problems for structured group classes.
Results
The paper gives deterministic polynomial-time GpEpi algorithms for Coprime(Ab, Cyc), Coprime(Q ElemAb, ElemAb), and groups whose composition factors are all non-Abelian simple.
Takeaways & Limitations
These results establish efficient epimorphism testing across several structured classes previously associated with polynomial-time isomorphism algorithms.
Takeaways & Limitations
The paper does not solve GpEpi for arbitrary Fitting-free groups, and some socle-series cases create too many subspace choices for polynomial-time brute force.
Abstract
from arXiv · showhide
The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.
1 Introduction
The paper studies the complexity of Group Epimorphism testing for finite groups given by Cayley tables, targeting structured classes where polynomial-time isomorphism testing is known. It gives deterministic polynomial-time algorithms for several such classes and connects one case to a representation-theoretic problem.
- Problem: GpEpi asks whether one finite group has a surjective homomorphism onto another, but its Cayley-table complexity is comparatively understudied.The paper focuses on worst-case algorithms and structured group classes.
- Algorithmic framework: For Coprime(Ab, Cyc), the algorithm combines algebraic structure with representation-theoretic results and maximum matching in bipartite graphs.The proof first identifies suitable normal Hall subgroups and cyclic complements before testing for an epimorphism.
- Main results: The paper develops polynomial-time GpEpi algorithms for Coprime(Ab, Cyc), Coprime(Q ElemAb, ElemAb), and groups with no Abelian composition factors.It also treats restricted Fitting-free settings with limited multiplicity of Abelian chief factors.
- Representation-theoretic reduction: For Coprime(ElemAb, ElemAb), GpEpi is polynomial-time many-one equivalent to SInducedRepEpivalent.This representation problem asks whether a surjective group map and compatible surjective linear map exist between two representations.
- Representation-theoretic reduction: When the elementary Abelian groups have rank d, SInducedRepEpivalent reduces to CodeIso for d-dimensional codes in F^m.Here m is the maximum of the two representation dimensions.
2 Preliminaries
The preliminaries establish the paper’s group-theoretic, representation-theoretic, module-theoretic, and coding terminology. They also define the structural decompositions and computational problem used later.
- Group theory: A semidirect product G = N ⋊τ H consists of a normal subgroup N, a complement H, and an induced action τ : H →Aut(N).For normal Hall subgroups, Schur–Zassenhaus guarantees a complement, and all complements are conjugate.
- Socle and chief series: Chief factors arise from unrefinable normal series and each has the form T^n for a finite simple group T.The socle series can be refined into a chief series by inserting preimages of minimal normal subgroups.
- Code Isomorphism: Code Isomorphism asks whether two generating matrices differ by an invertible row transformation and a permutation of columns.
- Representation theory: A representation is a homomorphism from a group into a general linear group, with irreducibility determined by its invariant subspaces.
- Representation theory: Two representations are equivalent when an invertible linear map intertwines the action of every group element.
- Representation theory: For an elementary Abelian normal subgroup, the conjugation action of its complement is represented by matrices over a finite field.
3 Condition for epimorphism testing
For semidirect products with normal Hall subgroups, epimorphism testing reduces exactly to compatible epimorphisms on the normal subgroups and complements. The compatibility condition ensures that the component maps respect the respective group actions.
- Reduction theorem: Epimorphism testing between G1 = N1 ⋊τ H1 and G2 = N2 ⋊γ H2 requires epimorphisms on both normal Hall subgroups and complements.
- Reduction theorem: The component epimorphisms must intertwine the actions τ and γ for every element of H1.
- Forward direction: Given an epimorphism G1 → G2, its kernel decomposes as L ⋊τ K with L in N1 and K in H1.
- Forward direction: The induced action of K on N1/L is trivial, so the action descends to H1/K acting on N1/L.
- Reverse direction: Conversely, compatible component epimorphisms define f(n,h) = (ρ(n), ϕ(h)), an epimorphism from G1 to G2.
4 Efficient epimorphism testing of Coprime(Ab, Cyc)
For groups with Abelian normal Hall subgroups and cyclic complements, the paper gives a polynomial-time epimorphism algorithm. It reduces the problem to quotient construction, module decomposition, module matching, and polynomial-time conjugacy tests.
- Module structure: The subgroup L is a direct sum of maximal indecomposable H1-submodules of N1.
- Module structure: Indecomposable H-modules and their decompositions can be computed in polynomial time when H is cyclic and acts coprimely on an Abelian group.The decomposition algorithm recursively finds direct-summand submodules and complements.
- Algorithm setup: The algorithm first verifies the target class and finds suitable normal Hall subgroups and cyclic complements with the necessary order inequalities.These structural objects and conditions can be checked in polynomial time.
- Quotient construction: The unique subgroup K ◁H1 with |H1/K| = |H2| determines the complement quotient required for a candidate epimorphism.The algorithm computes K and the subgroup L generated by the differences vτ(k) −v.
- Quotient construction: When |N1/L| = |N2|, epimorphism testing reduces to isomorphism testing between N1/L ⋊τ H1/K and N2 ⋊γ H2.A computed isomorphism lifts to an epimorphism from G1 to G2.
- Module matching: The algorithm represents the remaining module-matching choices by a bipartite graph whose edges encode compatible quotient-module isomorphisms.An edge is supported by an elementary-Abelian module isomorphism and an exponent inequality.
- Module matching: Testing the required elementary-Abelian module isomorphisms reduces to matrix conjugacy in GL(Fp, d), solvable deterministically in polynomial time.
5 Efficient epimorphism testing of Coprime(Q ElemAb, ElemAb)
This section reduces epimorphism testing for groups with quas elementary Abelian normal Hall subgroups and elementary Abelian complements to representation-theoretic conditions, then to Code Isomorphism.
- Structural reduction: The algorithm decomposes each group into a normal Hall subgroup and complement, then tests epimorphisms between these parts.For the relevant classes, the normal subgroups are elementary Abelian p-groups and complements are elementary Abelian q-groups.
- Representation test: Representations are decomposed into irreducible constituents, and an epimorphism exists exactly when every target constituent appears in the source with sufficient multiplicity.Lemma 3 gives the necessary-and-sufficient multiplicity condition for epivalence.
- Representation test: The constituent-matching condition is tested by finding a suitable linear transformation between the representation parameters.The method expresses the condition through matrices and a surjective linear map between complement spaces.
- Algorithmic consequence: The resulting matrix condition is an instance of Code Isomorphism, yielding a polynomial-time algorithm for the elementary-Abelian setting.Babai’s singly exponential-time Code Isomorphism algorithm is polynomial here because the relevant code parameters are logarithmic in the Cayley-table input size.
- Extension: The same framework extends from elementary Abelian normal Hall subgroups to products of such subgroups by using block-diagonal matrices.The extension reduces the problem to solving M1P = ϕM2 for block-diagonal representation matrices.
6 Efficient epimorphism testing in groups with limited Abelian composition factors
This section develops polynomial-time epimorphism testing when the target has no Abelian composition factors and extends the result to targets paired with groups of bounded Abelian width.
- Groups with limited Abelian composition factors: Theorem 5’s procedure first rejects targets with Abelian composition factors, computes a chief series of the source, and tests the resulting candidate quotients.The final isomorphism test is polynomial-time because the target is Fitting-free.
- Groups with limited Abelian composition factors: The algorithm enumerates subsets of chief factors of the source as possible kernels, checking quotient order, kernel validity, and isomorphism with the target.The chief series has length at most log |G1|, so the number of subsets is bounded by 2^log |G1| ≤ |G1|.
- Remaining obstacle: Repeated isomorphic Abelian minimal normal subgroups create p^Θ(k^2) candidate normal subgroups, making brute-force enumeration non-polynomial when k = Θ(log |G|).This obstacle can occur at any layer of the socle series.
- Abelian width: The paper defines Abelian width as the maximum multiplicity of an Abelian minimal normal subgroup across the socle series.The width is always O(log |G|), although it can be much smaller than the dimension of a chief factor.
- Bounded-width extension: When the source has Abelian width O(log |G1|) and the target is Fitting-free, the candidate enumeration becomes polynomial-time.The algorithm enumerates copies T^j rather than individual chief factors, with at most k p^Θ(k^2) choices under the bounded-width assumption.
7 Conclusion and open problems
The conclusion identifies unresolved complexity questions for GpEpi and lists further group classes where polynomial-time testing remains open.
- Open complexity questions: Whether GpEpi is in P remains open, and a positive answer would imply that GpI is in P.The paper therefore focuses on classes where polynomial-time isomorphism testing is already known.
- Open complexity questions: The paper leaves open whether GpEpi belongs to coAM and asks for the complexity of the counting problem #GpEpi.These are stated as separate basic complexity questions.
- Candidate classes: Further targets include Fitting-free groups, groups with constant-size or constantly generated targets, and groups whose quotients have bounded genus.The list also includes groups with Abelian Sylow towers or tame towers.
- Candidate classes: The paper specifically asks about groups with central elementary Abelian radicals whose quotient is a direct product of non-Abelian simple groups.This is listed as another class for future epimorphism testing.
- Fitting-free targets: For Fitting-free targets, an epimorphism G → H exists exactly when an epimorphism G/Rad(G) → H exists.The remaining difficulty concerns target socles arising from chief factors at different layers of the source’s socle series.
A Deferred proofs
The deferred proof establishes that the subgroup generated by the action differences is the direct sum of maximal indecomposable modules.
- Module decomposition: The proof writes N1 as a direct sum of indecomposable H1-submodules and defines the action-difference subgroups on each component.For each Vi, the construction uses V′i = {vτ(k) − v : v ∈ Vi, k ∈ K}.
- Component analysis: It suffices to show that each nonzero component V′i has the required form, using the restricted submodule structure of indecomposable coprime modules.The proof invokes that the only submodules of Vi are powers of the prime ideal filtration.
- Coprime case: In the coprime case, every action element has order dividing both |N1| and |H1|, forcing the action to be trivial.The proof concludes with τ(k) = ι and hence V′i = Vi.
- Conclusion: The proof closes by combining the component identities to establish the observation.The conclusion is stated as completion of the proof of Observation 1.