Skip to content
DraconiticResearch
Search Sources API
186,086 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2

  • Joshua A. Grochow
  • Gábor Ivanyos
  • Youming Qiao
  • Xiaorui Sun
Open at sourcePDFDOICite

Abstract

The finite group isomorphism problem asks whether two finite groups of order N are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time Nlog N + O(1). Despite intensive study, the current best known algorithm has a running time of N(1 / 4 + o(1))log N (Rosenbaum, '13). p-groups of class $2$ have been recognized as the major bottleneck for faster group isomorphism. Recent progress has led to No(log N)-time algorithms for p-groups of class $2$ where p is odd (Sun, STOC '23; Ivanyos--Mendoza--Qiao--Sun--Zhang, FOCS '24; Grochow--Qiao--Stange--Sun, STOC '25). However, the case of p=2, which represents the majority of p-groups of class 2 assuming a well-known conjecture in group enumeration, remained elusive, with essentially no progress until now. In this paper, we present an algorithm for testing the isomorphism of two 2-groups of Frattini class 2 of order N in time NO((log N)1/2). To our knowledge, this is the first No(log N)-time isomorphism algorithm for a class of $2$-groups that constitutes logarithmically almost all $2$-groups, in the sense that limN → ∞ (log(# 2−groups of Frattini class 2 and order ≤ N))/(log(# 2−groups of order ≤ N)) = 1. As our main tool, we present the first non-trivial algorithms for the quadratic form space/tuple isometry problems over 𝔽2. These algorithms rely on combinations of combinatorial and algebraic ideas, including finite matrix group algorithms developed by Luks (FOCS '92). As far as we know, this is the first time that matrix group algorithms are used to make progress on the worst-case complexity of p-group isomorphism.

Related

  1. A note on isomorphism types of complete discretely valued fields of mixed characteristic
    Pranav Velavan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
    Nader H. Bshouty
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  3. Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
    Gabriel Rioux, Joanna Marks, Riccardo Passeggeri +1
    arXivPreprintarXiv licenceFull textOptimisation & controlStatisticsarXiv
  4. Faster quantum linear system solver beyond the condition number
    Alexander M. Dalzell, Jianqiang Li, Yuan Su
    arXivPreprintCC BY-SA 4.0Full textNumerical analysis & scientific computingQuantum physics & quantum informationarXiv
  5. Ivanov's finite-index Frattini conjecture for subgroups of mapping class groups
    Renaud Detcherry, Efstratia Kalfagianni
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{grochow2026beyond,
  title = {{Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2}},
  author = {Joshua A. Grochow and Gábor Ivanyos and Youming Qiao and Xiaorui Sun},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.00874},
  eprint = {2610.00874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.00874},
}
RIS
TY  - UNPB
TI  - Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
AU  - Joshua A. Grochow
AU  - Gábor Ivanyos
AU  - Youming Qiao
AU  - Xiaorui Sun
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.00874
UR  - https://arxiv.org/abs/2610.00874
AB  - The finite group isomorphism problem asks whether two finite groups of order N are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time N^log N + O(1). Despite intensive study, the current best known algorithm has a running time of N^(1 / 4 + o(1))log N (Rosenbaum, '13). p-groups of class $2$ have been recognized as the major bottleneck for faster group isomorphism. Recent progress has led to N^o(log N)-time algorithms for p-groups of class $2$ where p is odd (Sun, STOC '23; Ivanyos--Mendoza--Qiao--Sun--Zhang, FOCS '24; Grochow--Qiao--Stange--Sun, STOC '25). However, the case of p=2, which represents the majority of p-groups of class 2 assuming a well-known conjecture in group enumeration, remained elusive, with essentially no progress until now. In this paper, we present an algorithm for testing the isomorphism of two 2-groups of Frattini class 2 of order N in time N^O((log N)^1/2). To our knowledge, this is the first N^o(log N)-time isomorphism algorithm for a class of $2$-groups that constitutes logarithmically almost all $2$-groups, in the sense that lim_N → ∞ (log(# 2−groups of Frattini class 2 and order ≤ N))/(log(# 2−groups of order ≤ N)) = 1. As our main tool, we present the first non-trivial algorithms for the quadratic form space/tuple isometry problems over 𝔽_2. These algorithms rely on combinations of combinatorial and algebraic ideas, including finite matrix group algorithms developed by Luks (FOCS '92). As far as we know, this is the first time that matrix group algorithms are used to make progress on the worst-case complexity of p-group isomorphism.
ER  -