PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Joshua A. Grochow, Gábor Ivanyos, Youming Qiao, Xiaorui Sun

arXiv:2610.00874v1cs.DSmath.GR

TL;DR

Worst-case group isomorphism testing remains at |G|^{O(log |G|)}, with 2-groups of Frattini class 2 among the hardest cases. This paper reduces their isomorphism testing to quadratic-form isometry problems and gives an algorithm running in |G|^{O((log |G|)^{1/2})}.

  • Problem

    Worst-case group isomorphism testing is not known to beat |G|^{O(log |G|)}, and 2-groups of Frattini class 2 are identified as some of its hardest cases.

    Source: §1 · p. 3

  • Method

    The paper translates group isomorphism into quadratic-form space isometry, reduces that problem to tuple isometry, and solves the tuple problem using special-case algorithms.

    Source: §1.2.2 · p. 8, §1.2.3 · p. 9

  • Results

    |G|^{O((log |G|)^{1/2})} time suffices to test isomorphism of 2-groups of Frattini class 2.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The reduction connects the group-level algorithm to a quadratic-form tuple isometry algorithm with running time 2^{O((m+n)^{1.5})}.

    Source: §1.2.2 · p. 8

    Extending the approach to nilpotency class 2 requires handling quadratic forms over non-fields such as Z/2^kZ, and significant additional work is expected.

    Source: §1.1 · p. 6

Abstract

from arXiv · show

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 \to \infty} \frac{\log(\text{\# 2-groups of Frattini class 2 and order } \leq N)}{\log(\text{\# 2-groups of order} \leq N)} = 1$. As our main tool, we present the first non-trivial algorithms for the quadratic form space/tuple isometry problems over $\mathbb{F}_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.

1 Introduction

The section presents an isomorphism algorithm for 2-groups of Frattini class 2, reducing the problem to quadratic-form space and tuple isometry. It describes a tuple-isometry approach based on block diagonalization and separate tests for frequent and infrequent blocks, with candidate generation to handle isometries that do not preserve the original split.

1.1 The significance of 2-groups of Frattini class 2

  • Frattini class 2 groups have a central elementary-abelian subgroup with elementary-abelian quotient, and their number matches that of 2-groups on the logarithmic scale.The paper identifies this family as a starting point for 2-group isomorphism testing; recent |G|^o(log |G|) results for odd p do not apply to p = 2.Source: §1 · p. 3

1 Introduction

  • |G|^O((log |G|)^1/2) time suffices to test isomorphism of 2-groups of Frattini class 2.The stated result is for the Cayley table model; the algorithms also work for matrix and permutation group inputs.Source: §1 · p. 4

1.2 Our techniques

  • The overall approach reduces group isomorphism to quadratic-form space isometry, then reduces that problem to quadratic-form tuple isometry.The tuple problem is the key subroutine for obtaining the stated group-isomorphism algorithm.Source: §1 · p. 4

1 Introduction

  • The paper also solves quadratic-form space isometry over F2 in 2^O((m+n)^1.5) time.It tests whether an invertible change of variables maps the span of one sequence of forms to the span of another.Source: §1 · p. 4

1.1 The significance of 2-groups of Frattini class 2

  • In characteristic 2, alternating-matrix spaces may have dimension O((log |G|)^2), and the odd-characteristic lifting method can fail because it requires division by 2.The authors also note that symmetric matrices correspond to linear functions on quadratic forms, motivating their focus on quadratic-form spaces.Source: §1.1 · p. 5

1.2.1 Reduce isomorphism testing of 2-groups of Frattini class 2 to quadratic form space isometry.

  • Higman's criterion translates Frattini class 2 group isomorphism into a GL(n,2)-orbit problem, which the paper completes by passing to the dual action on quadratic forms.The GL(n,2) action on symmetric matrices is equivalent to its natural action on quadratic forms over F2.Source: §1.2.1 · pp. 7–8

1.2.2 Reduce quadratic form space isometry to quadratic form tuple isometry.

  • The space-to-tuple reduction constructs equivalent instances with n′ = O(n + m), whose tuple isometry can be solved in 2^O((n+m)^1.5) time.This yields the stated bound for quadratic-form space isometry; the general quadratic-form tuple problem is also covered by Theorem 1.3.Source: §1 · p. 4, §1.2.2 · p. 8

1.2.3 An algorithm for quadratic form tuple isometry.

  • The tuple algorithm uses new congruent block-diagonalization theory, combinatorial methods for frequent blocks, and matrix-group algorithms for infrequent blocks.For infrequent blocks, it bounds the index of a normal 2-subgroup; the authors identify this as the first use of finite matrix-group algorithms to advance worst-case p-group isomorphism complexity.Source: §1.1 · pp. 5–6, §1.2.3 · p. 8
  • Every alternating matrix tuple can be congruently block-diagonalized so each block corresponds to one or two minimum left-right blocks, which are transposes when there are two.This structural result is Theorem 5.1.Source: §1.2.3 · p. 9
  • With ∆ = 1/2, the general problem reduces to frequent- and infrequent-block cases, solvable in 2^O(n^(1+∆))·poly(m) and 2^O(n^(2−∆))·poly(m) time, respectively.Blocks are classified by whether their minimum left-right blocks appear more than n^(1−∆) times.Source: §1.2.3 · p. 9
  • For frequent blocks, the algorithm enumerates a significantly smaller set of qualifying congruent tuples using local operations that preserve block structure and connect all qualifying tuples.The frequent-block property bounds minimum left-right block dimensions by n^∆, yielding roughly 2^O(n^(1+∆)) possible block-diagonalized partial derivative tuples under additional conditions.Source: §1.2.3 · p. 9
  • For infrequent blocks, polynomial-time left-right equivalence testing either rejects the tuples or yields a group with a computable normal 2-subgroup of index at most 2^(n^(2−∆)), enabling a search using.The algorithm tests coset representatives and searches within the normal 2-subgroup; exhausting them without success certifies non-isometry.Source: §1.2.3 · p. 10
  • The full algorithm reduces isometry testing to roughly 2^O(n^(1+∆)) special-case instances by generating congruent block-diagonalized candidates, so a candidate can align the frequent and infrequent parts even when an isometry does not preserve the original split.The original split need not be preserved by an isometry, so the candidate set must include a tuple whose corresponding parts match those of the other input.Source: §1.2.3 · p. 10

2 Preliminaries

The preliminaries set notation and assumptions, then introduce matrix-tuple block diagonalization and tensor isomorphism. They also state a tensor-isomorphism reduction to restricted instances that remains applicable over F2.

2 Preliminaries

  • The preliminaries assume Cayley-table group inputs and define matrix tuples as ordered sequences of matrices, alongside notation for quadratic forms and change of variables.A tuple is assumed non-degenerate unless otherwise specified.Source: §2 · pp. 10–11, §2.1 · p. 11

2.1 Left-right block diagonalization of matrix tuples

  • The Left-Right Canonical Form Algorithm decomposes a matrix tuple into minimum left-right blocks and outputs the associated spaces V_B and K_B.The cited results used for this algorithm hold over F2.Source: §2.1 · pp. 11–12

2.2 Tensor isomorphism

  • Tensor isomorphism asks whether two alternating 3-tensors are related by invertible changes in their first and shared last dimensions.The restricted problem imposes structural zero conditions on the tensors.Source: §2.2 · p. 12
  • Over F2, the tensor-isomorphism reduction produces restricted instances and preserves the correspondence between solutions of the original and reduced problems.The reduction applies even though the cited tensor-isomorphism algorithms do not work over F2.Source: §2.2 · p. 13

3 Reduce Frattini class 2 group isomorphism to quadratic form space isometry

The paper reduces isomorphism testing for 2-groups of Frattini class 2 to isometry of spaces of quadratic forms over F2. The reduction uses the induced symmetric-matrix action and dual spaces to keep the output dimension tied to the Frattini subgroup.

3 Reduce Frattini class 2 group isomorphism to quadratic form space isometry

  • Quadratic form space isometry asks whether an invertible change of variables carries one span of quadratic forms onto another.The forms are homogeneous degree-2 polynomials over F2.Source: §3 · p. 13
  • For p=2, the induced automorphism action on the Frattini subgroup is equivalent to GL(n,2)’s congruence action on symmetric matrices.The symmetric matrices split into diagonal and alternating parts, reflecting the distinct behavior of squares and commutators.Source: §3 · pp. 14–15
  • A polynomial-time procedure maps two 2-groups of Frattini class 2 to quadratic-form sequences whose spans are isometric exactly when the groups are isomorphic.The sequence length is dim(Φ(G)), and the number of variables is dim(G/Φ(G)).Source: §3 · p. 16
  • The reduction computes each group’s kernel in a relatively free group, views the kernels as symmetric-matrix spaces, and takes their duals as quadratic-form spaces.Bases of the dual spaces supply the quadratic-form sequences used by the algorithm.Source: §3 · p. 16
  • Using the symmetric-matrix spaces directly can require quadratically larger dimensions than dim(Φ(G)), potentially negating gains from a faster isometry algorithm.The dual quadratic-form spaces instead have the same dimension as Φ(G).Source: §3 · pp. 16–17

4 Reduce quadratic form space isometry to quadratic form tuple isometry

This section reduces quadratic form space isometry through restricted and non-degenerate restricted isometry to quadratic form tuple isometry, using derivative-based structure and the Quadratic Form Tuple Construction. It also presents an algorithm for tuple isometry and uses the reduction to obtain Theorem 1.2.

4.1 The partial derivative matrix of a quadratic form

  • Under an invertible change S, the partial derivative matrix transforms as D(fS)=S^T Df S, and the derivative matrix of a sum is the sum of the matrices.These properties are established for quadratic forms over F2.Source: §4.1 · p. 18
  • If S=I+S′ satisfies the stated orthogonality condition against the columns of Df, then the transformed form has the same partial derivative matrix Df.The condition in the passage is (Df)i · S′[i,j]=0 for every i,j.Source: §4.1 · p. 18

4.2 Reduce quadratic form space isometry to non-degenerate restricted quadratic form space isometry

  • Quadratic form space isometry reduces to restricted instances in time p^O((m+n)n^0.5 log p), with max{m−α0−α1, n−β0−β1} ≤ n^0.5.The reduction produces p^O((m+n)n^0.5 log p) restricted instances.Source: §4.2 · p. 19
  • A degenerate vector is supported in the first β0 coordinates, irrelevant to the first α0+α1 forms, and annihilated by the remaining forms’ partial derivative matrices.The degeneracy-identification algorithm computes the span of these vectors and returns transformed forms and its dimension.Source: §4.2 · pp. 21–22
  • The restricted-problem reduction identifies degenerate coordinates, checks their dimensions and specified square terms, then tests induced forms on the remaining variables.It invokes the non-degenerate restricted algorithm with the adjusted parameter β0−df.Source: §4.2 · p. 22
  • 2^O((m−α0−α1)·n) instances suffice to reduce restricted quadratic form space isometry to non-degenerate restricted instances of length m in n′ variables.The output parameters β′0 and β1 are required to satisfy further conditions, which are not specified in the supplied passage.Source: §4.2 · p. 23
  • The restricted quadratic form space algorithm accepts exactly when its non-degenerate restricted instance accepts.The proof establishes both that a yes result for the non-degenerate step gives a yes result overall and that an overall yes result implies the original restricted instance is yes.Source: §4.2 · p. 23

4.3 Reduce non-degenerate restricted quadratic form space isometry to quadratic form tuple isometry

  • A non-degenerate restricted quadratic form space is encoded as a tuple of quadratic forms on the same variables.The construction takes the forms and parameters α0, α1, β0, β1 as input.Source: §4.3 · p. 24
  • Under the stated conditions, derivative-kernel spaces are closed under projections onto designated blocks, and intersections of spaces with this property retain it.Lemma 4.11 gives the projection property for spaces defined by derivative kernels or intersections; Lemma 4.12 shows that tuple isometries map the specified kernel spaces and intersections to their counterparts.Source: §4.3 · pp. 24, 26
  • The constructed tuple has 2(α0 + α1 + β0 + β1) + 3 variables.The stated construction output is a quadratic form tuple on this number of variables.Source: §4.3 · p. 25
  • Every non-zero vector has a non-zero partial derivative under at least one form in the constructed tuple.The proof uses the non-degeneracy of the input with respect to the parameters and the construction’s seven coordinate subspaces.Source: §4.3 · p. 26
  • The construction recovers each of seven coordinate subspaces Ei as a derivative-kernel-defined space If,i.These spaces are defined using kernels of selected tuple-form partial derivative matrices, and Lemma 4.14 identifies them with Ei.Source: §4.3 · pp. 26–27
  • Any isometry between tuples constructed from two inputs preserves each of the seven coordinate subspaces Ei.This follows from the construction’s identification of Ei with If,i and the stated preservation property for constructed tuples.Source: §4.3 · pp. 27–28
  • For tuples built by the construction, tuple isometry captures non-degenerate restricted quadratic form space isometry under the stated shared parameters.Lemma 4.16 establishes corresponding properties in both directions for the constructed tuples.Source: §4.3 · pp. 28–29
  • The constructed tuples satisfy the (m − α0 − α1)-non-zero-square-term condition under the specified invertible transforms.Lemma 4.18 requires the tuples to use the same construction parameters and the columns of U to lie in E1 through E7.Source: §4.3 · p. 29
  • Theorem 4.19 gives an algorithm for deciding isometry of tuples produced by the Quadratic Form Tuple Construction process.The inputs come from two sequences of quadratic forms with the same parameters as the non-degenerate restricted quadratic form space isometry problem.Source: §4.3 · p. 30
  • Together, Theorems 4.6, 4.9, and 4.19 establish the correctness of Theorem 1.2.The running-time analysis likewise combines Theorems 4.6 and 4.9 with Theorem 4.19.Source: §4.3 · p. 30
  • The reduction bounds the remaining tuple-isometry instances by m − α0 − α1 ≤ n^0.5 and uses Theorem 4.19 to bound overall running time.The supplied passage does not include the resulting time bound.Source: §4.3 · p. 30
  • The quadratic form tuple isometry algorithm constructs partial derivative tensors, applies tensor isomorphism reduction, then tests resulting restricted quadratic form space instances.It outputs yes if any restricted quadratic form space instance outputs yes.Source: §4.3 · p. 30
  • The algorithm's correctness follows by ruling out all restricted instances when no tuple isometry exists and obtaining a yes instance when tuple isometry exists.The proof links a tuple isometry to tensor isomorphism and then to a restricted quadratic form space isometry instance.Source: §4.3 · p. 31

5 Congruent block diagonalization of alternating matrix tuple

The section develops a block diagonalization for alternating matrix tuples over F2 under congruence, building it from minimum left-right blocks. It also gives a polynomial-time algorithm to construct a standard congruent block diagonalization from representative blocks.

5 Congruent block diagonalization of alternating matrix tuple

  • Theorem 5.1 shows how to obtain congruent blocks from a minimum left-right block, with the resulting block either XT AX or the congruence transform on [X Y].The latter case applies when XT AX is not itself a minimum left-right block.Source: §5 · p. 31
  • Every alternating matrix tuple has a congruence block diagonalization whose blocks satisfy one of two conditions based on minimum left-right blocks.The two forms are XT AX, or the congruence transform on [X Y] when XT AY is a minimum left-right block.Source: §5 · p. 33
  • After invertible changes within blocks, any standard congruent block diagonalization can be arranged into diagonal blocks determined by representative blocks and their multiplicities.A representative block may pair with its transpose when it is not left-right equivalent to its transpose.Source: §5 · p. 34
  • The Standard Congruent Block Diagonalization Algorithm constructs the specified diagonalization in time polynomial in n and m.It takes an alternating matrix tuple and representative blocks as input.Source: §5 · p. 35

6 Frequent block quadratic form tuple isometry

This section gives an algorithm for quadratic form tuple isometry when minimum left-right blocks are frequent and satisfy the stated square-term condition. It enumerates standard congruent block diagonalized tuples and connects them by local operations.

6 Frequent block quadratic form tuple isometry

  • The algorithm assumes every minimum left-right block has at most r rows and columns, and both tuples satisfy the ρ-non-zero-square-term condition.The square-term condition is required with respect to any standard congruent block diagonalization of the derivative tuple.Source: §6 · p. 35
  • 2^{O(n·(ρ+r))} · poly(m) time suffices to solve Problem 6.1 under its stated assumptions.The running-time bound follows from at most 2^{O(n·(ρ+r))} enumerated tuples and at most n^2 · 2^{O(r^2)} local operations per tuple.Source: §6 · pp. 35, 38
  • There are at most 2^{O(n·(ρ+r))} possible standard congruent block diagonalized quadratic form tuples under the lemma's hypotheses.The bound applies when every minimum left-right block has at most r rows and columns and the tuple satisfies the ρ-non-zero-square-term condition.Source: §6 · p. 36
  • It enumerates standard congruent block diagonalized tuples for f1, applies local operations until the set stabilizes, and accepts if it contains f2's corresponding tuple.The algorithm first checks left-right equivalence of the partial derivative tuples.Source: §6 · pp. 36–37

7 Infrequent block quadratic form tuple isometry

For the infrequent-block case, the section reduces quadratic form tuple isometry to searching a matrix group whose unipotent normal subgroup supports polynomial-time vector transport. The resulting algorithm has running time 2^{nD} · poly(m,n) under Problem 7.1's assumptions.

7 Infrequent block quadratic form tuple isometry

  • The method assumes each minimum block occurs at most D times in a minimum left-right block diagonalization and that neither derivative tuple has a nonzero vector in its kernel.These are conditions of Problem 7.1.Source: §7 · p. 39
  • 2^{nD} · poly(m,n) time suffices to solve Problem 7.1 under its stated conditions.The algorithm searches representatives of the quotient by the radical subgroup, whose size is at most 2^{nD}.Source: §7 · pp. 39, 43
  • The algorithm reduces the isometry search to a group G with an efficiently computable unipotent normal subgroup R of index at most 2^{nD}.For each quotient representative, it tests for an element of R mapping the transformed tuple to the target.Source: §7 · p. 39
  • Vector transport for a unipotent matrix group over F2 is solvable in polynomial time, enabling the subgroup search used by the algorithm.The paper applies this result to the action of R on quadratic form tuples.Source: §7 · pp. 40–41

8 Quadratic form tuple isometry algorithm

This section presents a quadratic-form tuple isometry algorithm under a non-zero-square-term condition, using representative blocks constructed in polynomial time from the partial derivative matrix tuple. The algorithm runs in time 2^{O(n^{1.5}+nρ)}.

8 Quadratic form tuple isometry algorithm

  • Theorem 8.2 solves Problem 8.1 in time 2^{O(n^{1.5}+nρ)} for tuples satisfying the ρ-non-zero-square-term condition.The condition applies with respect to any standard congruent block diagonalization of Df1 using the representative blocks.Source: §8 · p. 44
  • The algorithm first compares left-right canonical forms, then chooses frequent-block, infrequent-block, or mixed-block processing according to r.When 0 < r < ℓ, it builds candidate tuples by modifying blocks and tests the infrequent and frequent cases on complementary variable sets.Source: §8 · p. 47
  • Lemma 8.6 establishes that the Non-Zero-Square-Term Condition Quadratic Form Tuple Isometry Algorithm correctly solves Problem 8.1.Its proof shows both that a yes output certifies isometry and that isometric inputs yield a candidate tuple reaching the required isometry test.Source: §8 · pp. 47–48
  • For the Non-Zero-Square-Term Condition Quadratic Form Tuple Isometry Algorithm, Lemma 8.7 gives a running time of 2^{O(n(nΔ+ρ)+n^(2−Δ))} · poly(m).Source: §8 · p. 49
  • The Representative Blocks Algorithm runs in polynomial time and ensures the tuple satisfies the (m − α0 − α1)-non-zero-square-term condition for any standard congruent block diagonalization of Df.It outputs representative blocks B1, …, Bℓ for Df.Source: §8 · p. 50
  • Theorem 4.19 first obtains representative blocks, then runs tuple isometry; its constructed tuples have length poly(n, m) over O(n + m) variables and satisfy the required condition, enabling Theorem 8.2.Both f and g satisfy the condition for any matrix tuple that is a standard congruent block diagonalization of Df with respect to the representative blocks.Source: §8 · p. 50

A Minimum congruent block diagonalization of alternating matrix tuples

The section gives an explicit alternating matrix tuple over F2 with nonunique minimum congruent block diagonalizations. Two decompositions yield minimum blocks, but their second blocks are not congruent.

A Minimum congruent block diagonalization of alternating matrix tuples

Loading 2610.00874v1…