On Isomorphism Testing of Groups with Normal Hall Subgroups
On Isomorphism Testing of Groups with Normal Hall Subgroups
复制标题
关于具有正规霍尔子群的群的同构检验
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Bangsheng Tang
中科院分区：
文献类型：
--
作者：
Youming Qiao;Jayalal Sarma;Bangsheng Tang
群G的正规霍尔子群N是其序素和其索引的正规子群。Schur-Zassenhaus定理指出，每一个正规Hall子群都有一个补子群，补子群是一组协集代表H， H也构成g的一个子群。本文给出了一个框架来检验至少有一个正规Hall子群的群的同构，当群以乘法表形式给出时。为了建立框架，我们首先观察了Schur-Zassenhaus定理的一个构造性证明，并给出了半直积的关联作用、正规部和补部的同构检验的充分必要条件。然后我们重点讨论正规子群是阿贝尔的情况。利用有限群表示理论的基本事实和Le Gall （STACS 2009）的技术，我们首先得到了当补具有有限个数的生成器时的有效同构检验算法。对于补子群为初等阿贝尔时，不一定有有限个数的生成器，我们将其简化为广义码同构问题，得到了一个多项式时间同构检验算法，该问题是关于两个线性子空间在坐标置换前是否相同的问题。后者的解决方案可以通过对Babai等人（SODA 2011）最近开发的代码同构问题的单指数（在坐标数上）时间算法的温和扩展来获得。在得到上述约简的过程中，我们研究了有限群表示理论中的以下计算问题：给定群H / $ mathbb{Z}_p^d $, p a '的两个表示ρ和τ，判断是否存在自同构：H→H，使得引生表示ρ？= ρ◦？和τ在时间poly（|H|, pd）中是等效的。
A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009), we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al. (SODA 2011). Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ρ and τ of a group H over $ mathbb{Z}_p^d $, p a prime, determine if there exists an automorphism : H → H, such that the induced representation ρ? = ρ ◦ ? and τ are equivalent, in time poly(|H|, pd).