Pfaffian Degree as Observable Complexity in Class-Two $p$-Groups

1 Introduction

Groups of nilpotency class two and exponent $p$ are controlled by alternating maps

over $\mathbb F_p$. If $p$ is odd, such a map defines a group

with multiplication

Then

Thus pseudo-isometry of alternating maps is the linear-algebraic core of isomorphism for special class-two exponent-$p$ groups. This paper studies the power and limits of bounded-arity observables on such groups. There are two observable hierarchies. The first is the structured support-image hierarchy, or CSI. For

one forms the contraction map

The level-(r) support-image profile records the image subspaces

as $\mathbf x$ varies. The second is the hierarchy of coefficient-free word observables. Given a system of word equations

in (k) variables, one records the number of (k)-tuples in $G_\beta$ satisfying the system. These observables include Hom-counts from finitely generated class-two exponent-$p$ groups. The main discovery of this paper is that, for regular alternating pencils, both hierarchies are governed by a single spectral divisor function. Let

and consider the regular symplectic block

For a direct sum of such blocks

define

This function measures how a test polynomial (h) intersects the spectral elementary divisors of the pencil. The first main theorem states:

The proof is a Smith-normal-form computation. Every level-(r) CSI test produces a matrix (C(t)) with linear entries. Its Smith factors $s_i(t)$ have degree at most (r), and the rank of the test on the block $R_F$ is governed by

The second main theorem extends this to all coefficient-free systems of word equations. After reduction to pure commutator equations and Fourier expansion, each frequency produces a linear alternating polynomial matrix. Since skew-Smith factors occur in pairs, a word observable in (k) variables can only test polynomials of degree at most

Therefore

This gives an exact factor-of-two law. For an irreducible factor (f) of degree (m),

detects (f) exactly at arity (m), whereas word observables require (2m) variables. This is optimal. A companion linearization

gives a CSI witness at arity (m). Its skew-symmetrization

gives two explicit word equations in (2m) variables distinguishing the associated groups. No single word equation ever distinguishes irreducible blocks of the same degree. The conclusion is that Pfaffian degree is observable complexity.

The final consequences are group-theoretic. For every (m), there are

pairwise nonisomorphic directly indecomposable special groups of order

which no word observable in fewer than (2m) variables can distinguish. Since

this is a logarithmic arity lower bound with a matching upper bound inside the word-observable hierarchy. The result should be read as a local-observable lower bound, not as a time lower bound for group isomorphism. Genus-two groups are globally tractable through their pencil structure. Our theorem shows that, even in this globally tractable setting, bounded local invariants cannot see the irreducible Pfaffian factor before its exact degree.

2 Related work and positioning

Class-two exponent-$p$ groups are a central bottleneck in finite group isomorphism. Their isomorphism problem is governed by pseudo-isometry of alternating bilinear maps, or equivalently by isometry of alternating matrix spaces. Several global algorithms and reductions exploit this linear-algebraic structure. Alternating matrix space isometry has been studied as a linear-algebraic analogue of graph isomorphism, and genus-two groups admit efficient isomorphism algorithms using the structure of pencils and their adjoint algebras. More recently, faster algorithms for class-two exponent-$p$ groups and reductions between tensor, group, and polynomial isomorphism problems have clarified the central role of these groups. This paper does not improve those global algorithms. Instead, it gives a sharp lower bound for local observable hierarchies inside a globally tractable family. The closest group-theoretic comparison is Wilson's construction of genus-two $p$-groups with identical proper subgroup and quotient profiles, character tables, and power maps. Our groups belong to the same genus-two universe. The contribution here is different: we give an exact spectral formula for all CSI and coefficient-free word-count observables, prove optimal arity thresholds, produce explicit optimal witnesses, and explain the obstruction through Smith normal form and Pfaffian degree. We also separate our results from Weisfeiler--Leman and full counting-logic lower bounds. We prove indistinguishability for quantifier-free coefficient-free word-counting observables and for Hom profiles from bounded-generator sources. We do not claim a lower bound for full bounded-variable counting logic with quantifier alternation, nor for all WL variants on groups.

3 Regular affine alternating pencils

Throughout, $p$ is an odd prime. Let

be monic of degree

Put

Let

be the linear functional extracting the coefficient of $t^{M-1}$ from the representative of degree $<M$.

Lemma 3.1 (Frobenius pairing).

The pairing

\[ R_F\times R_F\to\mathbb F_p, \qquad (u,v)\mapsto \lambda_F(uv) \]

is nondegenerate.

Set

For

define

Define the alternating pencil

by

Let $B_0,B_1$ be the two scalar coordinate forms. For a finite list

of monic polynomials, define

and

Let

Then

This model captures the affine regular part of an alternating pencil with a chosen nondegenerate scalar member. The homogeneous treatment, including spectral factors at infinity, should be obtained by the corresponding binary-form version; we do not need it here.

4 Structured CSI and its rank transform

Let

be an alternating map. For

define

The level-(r) structured support-image profile is the function

It is often easier to use the rank transform. Let

Choose a basis $u_1,\ldots,u_a$ of (U), and define

by

Let

Proposition 4.1 (CSI/rank-transform equivalence).

For fixed (r), the functions

\[ T\mapsto E_r^\beta(T) \]

and

\[ U\mapsto \rho_r^\beta(U) \]

determine one another.

5 Spectral divisor functions

For a list

define the spectral divisor function

by

For $r\ge0$, write

for the restriction of $D_{\mathcal F}$ to polynomials of degree at most (r). The theorem below says that $D_{\mathcal F,\le r}$ is exactly the spectral content of CSI through level (r).

6 Exact CSI spectral tomography

Let

Identify

with the two-dimensional space of linear polynomials

Let

After choosing a basis of (U), represent (U) by an $a\times r$ matrix

whose entries are linear polynomials. Let

be the nonzero Smith factors of $C_U(t)$ over $\mathbb F_p[t]$.

Theorem 6.1 (CSI Smith formula).

For the regular affine pencil $\beta_{\mathcal F}$,

\[ \boxed{ \rho_r^{\beta_{\mathcal F}}(U) =2\sum_{\nu=1}^s \sum_{i=1}^k \left( M_\nu-\deg\gcd(s_i,F_\nu) \right). } \tag{6.1} \]

Equivalently,

\[ \boxed{ \rho_r^{\beta_{\mathcal F}}(U) =2\sum_{i=1}^k \left( M-D_{\mathcal F}(s_i) \right). } \tag{6.2} \]

Theorem 6.2 (Exact CSI tomography).

For regular affine pencils,

\[ \boxed{ \operatorname{CSI}_{\le r}(\beta_{\mathcal F}) \quad\Longleftrightarrow\quad D_{\mathcal F,\le r}. } \]

More explicitly, for two lists $\mathcal F,\mathcal G$ of the same total degree (M),

\[ \operatorname{CSI}_{\le r}(\beta_{\mathcal F}) = \operatorname{CSI}_{\le r}(\beta_{\mathcal G}) \]

in fixed pencil coordinates if and only if

\[ D_{\mathcal F}(h)=D_{\mathcal G}(h) \]

for every polynomial $h$ with

\[ \deg h\le r. \]

7 Recovery of elementary divisors

Suppose the spectral list is written in primary form

where the $p_\alpha$ are distinct monic irreducibles. For $a\ge1$,

Define

Then

Therefore

Corollary 7.1 (Complete regular spectral recovery).

Let

\[ \tau(\mathcal F) \max_{\alpha,j} e_{\alpha,j}\deg p_\alpha. \]

Then

\[ \operatorname{CSI}_{\le \tau(\mathcal F)} \]

recovers the complete primary spectral multiset $\mathcal F$. Moreover, the pairwise CSI separation depth in fixed pencil coordinates is

\[ \boxed{ \delta_{\mathrm{CSI}}(\mathcal F,\mathcal G) \min{\deg h:D_{\mathcal F}(h)\ne D_{\mathcal G}(h)}. } \tag{7.3} \]

That is,

\[ \operatorname{CSI}_{\le r}(\beta_{\mathcal F}) = \operatorname{CSI}_{\le r}(\beta_{\mathcal G}) \]

if and only if

\[ r<\delta_{\mathrm{CSI}}(\mathcal F,\mathcal G). \]

8 Irreducible spectral blocks and CSI threshold

Let

be monic irreducible polynomials of degree $m\ge3$. If

then

for every nonzero $h_0$. Hence

is independent of (f). At level (m), taking

gives

whereas

if $h\ne f$. Thus:

Theorem 8.1 (Exact CSI threshold for irreducible blocks).

For irreducible degree-(m) blocks,

\[ \operatorname{depth}_{\mathrm{CSI}}=m. \]

In fixed pencil coordinates,

\[ \operatorname{CSI}_{\le m-1}(\beta_f) \operatorname{CSI}_{\le m-1}(\beta_h) \]

for all irreducible $f,h$ of degree (m), while

\[ \operatorname{CSI}_{\le m} \]

distinguishes (f) from (h) unless (f=h). Projectively, equality at level (m) holds precisely when (f) and (h) are in the same $PGL_2(p)$-orbit.

9 Word observables and QCO

We now pass from CSI to word equations. Let

be a coefficient-free system of words in (k) variables in the variety

of class-two exponent-$p$ groups. Every word has a normal form

where

is its linear exponent vector and

is its commutator matrix. Let

be the matrix with rows $\alpha_j$. Put

After choosing a basis of $\ker A$ and projecting central equations to $\operatorname{coker}A$, the system becomes (t) pure commutator equations in (n) variables:

where

The central coordinates lift with multiplicity

Proposition 9.1 (QCO reduction).

For every alternating map $\beta: \Lambda^2V\to W$ with $\dim W=2$,

\[ |\operatorname{Sol}_{\Sigma}(G_\beta)| =p^{2n}N_{\mathbf D'}(\beta), \tag{9.2} \]

where $N_{\mathbf D'}(\beta)$ is the number of solutions of the pure commutator system (9.1) in $V^n$.

A finite Boolean combination of word equations and disequations is a finite integer linear combination of counts of systems of equations, by inclusion--exclusion. Thus the same analysis applies to quantifier-free Boolean word observables.

10 Fourier--Smith formula for word counts

Fix a nontrivial additive character

Let

Write

Define the linear alternating polynomial matrix

Because $C_{\boldsymbol\lambda}(t)$ is alternating over the PID $\mathbb F_p[t]$, its nonzero Smith factors occur in pairs. We write the skew-Smith factors as

meaning that the ordinary Smith form contains

as its nonzero factors.

Theorem 10.1 (Fourier--Smith word-count formula).

For the regular affine pencil $\beta_{\mathcal F}$,

\[ \boxed{ |\operatorname{Sol}_{\Sigma}(G_{\mathcal F})| =p^{2n-2t} \sum_{\boldsymbol\lambda\in(W^*)^t} p^{ 2nM -2\displaystyle\sum_{i=1}^{u(\boldsymbol\lambda)} \left( M-D_{\mathcal F} (s_{\boldsymbol\lambda,i}) \right) }. } \tag{10.2} \]

11 The degree budget for alternating matrices

Let $C(t)\in\operatorname{Alt}_n(\mathbb F_p[t])$ have entries of degree at most (1). Suppose its rational rank is (2u). Let its skew-Smith factors be

Then

Indeed, the determinantal divisor of order (2u) is

It divides every nonzero $2u\times2u$ minor. Such a minor has degree at most (2u), because every entry is linear. Hence

In particular, every individual skew-Smith factor satisfies

12 Word-spectrum factorization

Theorem 12.1 (Word observables factor through truncated spectral data).

Let $\beta_{\mathcal F}$ and $\beta_{\mathcal G}$ be regular affine pencils with the same total spectral degree (M). Suppose

\[ D_{\mathcal F}(h)=D_{\mathcal G}(h) \]

for every polynomial $h$ with

\[ \deg h\le \left\lfloor\frac k2\right\rfloor. \]

Then every coefficient-free word observable in at most (k) variables has the same count on

\[ G_{\mathcal F} \quad\text{and}\quad G_{\mathcal G}. \]

The same holds for quantifier-free Boolean combinations of word equations and disequations in at most (k) variables.

Corollary 12.2 (Quantifier-free counting word logic).

Let $f,h$ be irreducible of degree (m). If (k<2m), then every coefficient-free quantifier-free formula in the group language with at most (k) free variables has the same number of satisfying assignments in $G_f$ and $G_h$.

13 Hom profiles and subgroup occurrence profiles

Let $H\in\mathcal N_{2,p}$ be generated by at most (k) elements. A presentation of (H) in the variety $\mathcal N_{2,p}$ uses (k) generators and some system of word equations. Therefore Theorem 12.1 immediately gives:

Corollary 13.1 (Hom-profile lower bound).

Under the hypotheses of Theorem 12.1,

\[ |\operatorname{Hom}(H,G_{\mathcal F})| =|\operatorname{Hom}(H,G_{\mathcal G})| \]

for every $H\in\mathcal N_{2,p}$ generated by at most (k) elements. Now fix $K\in\mathcal N_{2,p}$. Every homomorphism

\[ K\to G \]

has kernel $N\trianglelefteq K$ and induces an injection

\[ K/N\hookrightarrow G. \]

Thus

\[ |\operatorname{Hom}(K,G)| \sum_{N\trianglelefteq K} |\operatorname{Inj}(K/N,G)|. \tag{13.1} \]

This triangular relation over the normal-subgroup lattice recovers injection counts from Hom counts of quotients.

Corollary 13.2 (Bounded-generator subgroup profiles).

Let $f,h$ be irreducible of degree (m). If $K\in\mathcal N_{2,p}$ is generated by fewer than (2m) elements, then

\[ |\operatorname{Inj}(K,G_f)| =|\operatorname{Inj}(K,G_h)|. \]

Consequently,

\[ \#\{L\le G_f:L\cong K\} =\#\{L\le G_h:L\cong K\}. \]

14 Irreducible blocks and the factor-of-two law

Let $f,h\in\mathbb F_p[t]$ be monic irreducibles of degree (m). If

then

for every nonzero (a). Therefore

Theorem 14.1 (Complete word-observable blindness below (2m)).

If

\[ k<2m, \]

then every coefficient-free word observable in (k) variables has the same count on

\[ G_f \quad\text{and}\quad G_h. \]

Equivalently,

\[ G_f\equiv_{2m-1}^{\mathrm{word}}G_h. \]

In particular,

\[ |\operatorname{Hom}(H,G_f)| =|\operatorname{Hom}(H,G_h)| \]

for every $H\in\mathcal N_{2,p}$ generated by fewer than (2m) elements.

15 An optimal two-equation word witness

We now construct a distinguishing word observable in exactly (2m) variables. Let

be the companion linearization of (f). Define the skew-linearization

Write

with

Introduce variables

Define two pure commutator words

Let

Theorem 15.1 (Optimal word witness).

If (h) is not $PGL_2(p)$-equivalent to (f), then

\[ Z_f(G_f)>Z_f(G_h). \]

More precisely,

\[ Z_f(G_f)-Z_f(G_h) =p^{4m-4} (p-1) |\operatorname{Stab}_{PGL_2(p)}(f)| \left( p^{2m^2+2m}-p^{2m^2} \right). \tag{15.3} \]

16 One equation never distinguishes

Theorem 16.1 (Two equations are necessary).

Let $f,h\in\mathbb F_p[t]$ be monic irreducibles of the same degree $m\ge2$. No single coefficient-free word equation distinguishes

\[ G_f \quad\text{from}\quad G_h, \]

regardless of the number of variables.

17 The factor-of-two law

Define

to be the least (r) such that $\operatorname{CSI}_{\le r}$ distinguishes $\beta_f$ from $\beta_h$, up to projective pencil equivalence. Define

to be the least (k) such that a coefficient-free word system in (k) variables has different solution count on $G_f$ and $G_h$.

Theorem 17.1 (Exact factor-of-two law).

If $f,h$ are irreducible of degree (m) and are not $PGL_2(p)$-equivalent, then

\[ \boxed{ \operatorname{depth}_{\mathrm{CSI}}(f,h)=m, } \]

and

\[ \boxed{ \operatorname{depth}_{\mathrm{word}}(G_f,G_h)=2m. } \]

Moreover, (2m) variables suffice with two equations, and one equation never suffices.

Since

we obtain

18 Direct indecomposability and large fibres

For irreducible (f), the associated group $G_f$ is special and directly indecomposable.

Proposition 18.1.

The group $G_f$ is a directly indecomposable special class-two exponent-$p$ group of order

\[ p^{2m+2}. \]

The number of monic irreducible polynomials of degree (m) is

Every $PGL_2(p)$-orbit has size at most

Thus there are at least

pairwise nonisomorphic groups $G_f$ of order $p^{2m+2}$ in the same $\operatorname{CSI}_{\le m-1}$-fibre and in the same word-observable fibre below (2m) variables. In terms of

this fibre has size

19 Classical character and conjugacy data

The irreducible blocks also collapse many classical invariants.

Proposition 19.1.

Let (f) be irreducible of degree (m). For every nonzero $v\in V_f$, the map

\[ u\mapsto \beta_f(v,u) \]

is surjective onto $W=\mathbb F_p^2$.

Corollary 19.2 (Classical invariants).

For irreducible $f,h$ of the same degree (m), the groups $G_f,G_h$ have: the same conjugacy class size distribution; the same irreducible character degrees; the same character table form, up to relabelling of the center and its dual; the same power maps.

20 Hom-profile hierarchy

Let

mean that

for every $K\in\mathcal N_{2,p}$ generated by at most (k) elements.

Corollary 20.1.

If $f,h$ are irreducible of degree (m), then

\[ G_f\equiv_{2m-1}^{\mathrm{Hom}}G_h. \]

If $f,h$ are not projectively equivalent, then

\[ G_f\not\equiv_{2m}^{\mathrm{Hom}}G_h. \]

21 Local observable lower bounds

The preceding results may be summarized as a lower bound for local invariant-refinement procedures. Consider any invariant procedure whose decisions factor through any finite combination of: CSI, rank-support, flag, or star data of arity $<m$; coefficient-free word-system counts in $<2m$ variables; Hom counts from $<2m$-generated sources; quantifier-free coefficient-free counting word formulas in $<2m$ variables; subgroup occurrence counts for $<2m$-generated subgroups. Then the procedure is constant on a fibre of size

inside the directly indecomposable special groups of order (G). This is not a lower bound for all algorithms. It is an observable-complexity lower bound for a broad class of local and counting invariants.

22 Relation to Wilson's genus-two groups

The groups $G_f$ lie in the genus-two family of groups associated with quotients of the Heisenberg group over $\mathbb F_{p^m}$. Wilson showed that this family contains many directly and centrally indecomposable groups of order $p^{2m+2}$ with identical proper subgroup and quotient profiles, character tables, and power maps. The present results are complementary. Wilson's theorem gives a strong subgroup/quotient-profile obstruction. Here we give a spectral explanation of bounded-arity word and support-image invisibility: Every CSI level (r) sees exactly spectral divisor data of degree $\le r$. Every word observable in (k) variables sees exactly spectral divisor data of degree $\le\lfloor k/2\rfloor$. The irreducible Pfaffian degree (m) is invisible below CSI arity (m) and word arity (2m). A concrete two-equation witness at (2m) variables distinguishes the groups optimally. One equation never distinguishes. Thus the contribution is not merely another family of hard examples; it is an exact spectral formula explaining the observable barrier.

23 Algorithmic interpretation

The results are not time lower bounds for group isomorphism. In fact, genus-two $p$-groups admit efficient algorithms using global pencil structure. The theorem instead separates global isomorphism methods from bounded-local-observable methods. For regular pencils, a minimal CSI certificate of nonisomorphism between $\mathcal F$ and $\mathcal G$ is obtained by finding a polynomial (h) of least degree such that

The companion linearization $L_h(t)$ is then an optimal CSI witness. For irreducible (f), the skew-linearization $K_f(t)$ gives an optimal word-count witness with two equations in (2m) variables. Thus the theory gives explicit, checkable nonisomorphism certificates whose arity is provably minimal inside the corresponding observable hierarchy.

24 Main theorem package

We collect the main statements.

Theorem 24.1 (Pfaffian degree as observable complexity).

Let $p$ be odd. Let

\[ \mathcal F=(F_1,\ldots,F_s) \]

be a regular affine spectral pencil and define

\[ D_{\mathcal F}(h)=\sum_\nu\deg\gcd(h,F_\nu). \]

Then: $\operatorname{CSI}_{\le r}(\beta_{\mathcal F})$ determines and is determined by $D_{\mathcal F,\le r}$. Every coefficient-free word observable in (k) variables factors through $D_{\mathcal F,\le\lfloor k/2\rfloor}$. If $f,h$ are irreducible of degree (m), then all CSI observables below arity (m) and all word observables below (2m) variables are blind to the difference between $G_f$ and $G_h$. If $f,h$ are not projectively equivalent, then CSI at arity (m) and two explicit word equations in (2m) variables distinguish them. One word equation never distinguishes irreducible degree-(m) blocks. The associated directly indecomposable special groups have order $p^{2m+2}$, so the exact word-observable threshold is

\[ 2m=\log_p|G_f|-2. \]

A single lower-level observable fibre contains

\[ |G_f|^{1/2-o(1)} \]

nonisomorphic directly indecomposable special groups. Hom profiles from $<2m$-generated sources, quantifier-free word-counting profiles in $<2m$ variables, and subgroup occurrence profiles for $<2m$-generated subgroups are all blind on this fibre.

25 Further directions

25.1 Beyond affine regular pencils

The affine regular model assumes a chosen nondegenerate scalar member. A homogeneous treatment should include spectral factors at infinity. The same Smith/gcd mechanism should extend after replacing (t) by homogeneous binary forms.

25.2 Higher derived rank

For $\dim W>2$, the corresponding spectral data are no longer elementary divisors of a pencil but Pfaffian systems. A higher-dimensional analogue would likely involve determinantal ideals and multivariate Smith-like invariants.

25.3 Logical observables

The present paper proves lower bounds for coefficient-free quantifier-free word-count observables. Extending the factorization theorem to bounded-variable counting logic fragments with quantifier alternation would require a separate translation from formulas to spectral divisor data.

25.4 Zeta functions and subgroup growth

Pfaffian geometry appears in local zeta functions of class-two groups. It would be interesting to determine whether truncations of the spectral divisor function $D_{\mathcal F}$ control corresponding truncations of subgroup or normal zeta functions.