Quadratic Presentational Complexity and Exact Observable Barriers for Class-Two $p$-Groups

1 Introduction

Let (G) be a finite group. A finite system of word equations

defines a numerical invariant

Such invariants include commuting probabilities, higher commuting probabilities, homomorphism counts from finitely presented groups, and many centralizer-type statistics. They are among the most elementary ways to observe a finite group using only its multiplication. This paper studies such observables in the variety

where (p) is an odd prime. Groups in $\mathcal N_{2,p}$ are naturally represented by alternating bilinear maps. If

is alternating over $\mathbb F_p$, then

with multiplication

is a group of class at most $2$ and exponent (p). Conversely, special groups in $\mathcal N_{2,p}$ arise in this way from their commutator maps. The basic observation is that word equations collapse in this variety. Every word in (k) variables has a unique normal form consisting of:

• a linear exponent-sum part in $\mathbb F_p^k$;

• an alternating quadratic commutator part in $\Lambda^2\mathbb F_p^k$. Thus, from the perspective of $\mathcal N_{2,p}$, every word observable is a quadratic observable. We call the resulting theory quadratic presentational complexity. Its basic objects are quadratic presentations

The map (a) records the linear part of the relations, while (b) records the commutator part. The paper has two main parts. The first part develops the general quadratic formalism and proves an exact solution-counting formula. Given an alternating map

the number of solutions of a quadratic presentation in $G_\beta$ is a linear factor times the number of noncentral assignments whose quadratic obstruction lies in a specified linear image. The second part specializes to graphical (p)-groups. Given a graph $\Gamma$, the Baer--Lovasz--Tutte construction associates a class-two exponent-(p) group $G_\Gamma$. This construction is faithful to graph isomorphism: $G_\Gamma\cong G_{\Gamma'}$ if and only if $\Gamma\cong\Gamma'$. For these groups we prove a transfer theorem:

Here $\Omega(S,K)$ is a reflexive graph with vertex set (S), where

and

Thus, on graphical groups, quadratic presentational observables are exactly right homomorphism counts toward alternating-orthogonality targets. This viewpoint gives:

• a canonical semantic normal form for quadratic observables on graphical groups;

• a complexity dichotomy for evaluating a fixed observable;

• a right-profile completeness theorem;

• and an exact arity lower bound using Wilson's examples. The final theorem says that there exist nonisomorphic groups in $\mathcal N_{2,p}$ that cannot be distinguished by any coefficient-free observable in fewer than

variables. The bound is exact. This result shows that arity is a real observational resource. It is not enough to choose more equations or longer equations in too few variables.

2 The variety N2p

Let (p) be an odd prime. Let $\mathcal N_{2,p}$ denote the variety of groups of nilpotency class at most $2$ and exponent (p). For $G\in\mathcal N_{2,p}$,

and every element has order dividing (p). Let $F_k$ be the free group on generators

Let

be the free object in $\mathcal N_{2,p}$ on (k) generators. Equivalently,

where $F_k^{(3)}$ is the third term of the lower central series. Every element of $F_{k,2,p}$ has a unique normal form

where

Thus, as a set and as an $\mathbb F_p$-vector space,

The first summand records the image in the abelianization. The second records the commutator coordinates.

3 Quadratic normal forms for words

Let $w\in F_k$. Its image in $F_{k,2,p}$ has a unique coordinate pair

This pair is the quadratic normal form of (w) in $\mathcal N_{2,p}$. Now let

be alternating bilinear over $\mathbb F_p$, and define

with multiplication

Then

Theorem 3.1 (Quadratic normal form).

For every word $w\in F_k$, there are unique

\[ a(w)\in\mathbb F_p^k, \qquad B(w)\in\Lambda^2\mathbb F_p^k \]

such that, for every alternating map $\beta:V\times V\to W$ and every

\[ g_i=(v_i,z_i)\in G_\beta, \]

one has

\[ w(g_1,\dots,g_k) \left( \sum_i a_i(w)v_i, \sum_i a_i(w)z_i+ \sum_{i<j}B_{ij}(w)\beta(v_i,v_j) \right). \]

Moreover, (a(w)) and (B(w)) are computable in time linear in the length of (w).

4 Quadratic presentations

A quadratic presentation over $\mathbb F_p$ is a quadruple

where (X) and (R) are finite-dimensional $\mathbb F_p$-vector spaces and

are linear maps. The space (X) is the variable space. The space (R) is the relation space. The map (a) records the linear exponent-sum part of the relations, while (b) records the alternating commutator part. Let

be alternating. An assignment of the variables of $\mathcal P$ in $G_\beta$ consists of two linear maps

The assignment satisfies $\mathcal P$ if

and

Let

be the set of satisfying assignments.

Proposition 4.1 (Equivalence with word systems).

Every finite system of word equations in $\mathcal N_{2,p}$ defines a quadratic presentation. Conversely, every quadratic presentation is realized by a finite system of word equations in $\mathcal N_{2,p}$.

5 The counting formula

Let

be a quadratic presentation and let

be alternating. For

define the quadratic obstruction

Let

be the map

Theorem 5.1 (Counting formula).

Let

\[ d=\dim W. \]

Then

\[ |\operatorname{Sol}_{\mathcal P}(\beta)| p^{d(\dim X-\operatorname{rank}a)} \left| \left\{ f:X\to V: f\circ a=0, Q_f\in\operatorname{im}a^* \right\} \right|. \]

6 Graphical (p)-groups

Let

be a finite simple graph. Fix an arbitrary orientation of (E). Define

For $x,y\in V_\Gamma$, define

if the oriented edge (e) is $u\to v$. Let

Changing the orientation of an edge changes the sign of the corresponding basis vector of $W_\Gamma$, so the isomorphism type of $G_\Gamma$ does not depend on the orientation. This is the standard graphical class-two exponent-(p) construction, equivalent to the Baer--Lovasz--Tutte graph-to-group construction. We use the following known fact.

Theorem 6.1 (Faithfulness of the graphical construction).

For finite simple graphs $\Gamma,\Gamma'$,

\[ \Gamma\cong\Gamma' \quad\Longleftrightarrow\quad G_\Gamma\cong G_{\Gamma'}. \]

This is a theorem of He and Qiao for the Baer--Lovasz--Tutte construction.

7 From quadratic presentations to alternating targets

Let

be a quadratic presentation. An assignment of the noncentral parts of the variables in $G_\Gamma$ is a linear map

For each vertex $u\in U$, define

The equation

is equivalent to

for every (u). Therefore the allowed spins lie in

The commutator part defines an alternating map

by

Let

be the map induced by $\widetilde q_\mathcal P$. Define

Now define a reflexive graph

with vertex set $S_\mathcal P$ and adjacency

Since $s\wedge s=0$, every vertex has a loop.

8 Protocol-to-target transfer

Theorem 8.1 (Transfer theorem).

For every finite graph $\Gamma$,

\[ |\operatorname{Sol} {\mathcal P}(G \Gamma)| p^{\dim S_\mathcal P\cdot |E(\Gamma)|} \operatorname{hom} \bigl( \Gamma,\Omega(S_\mathcal P,K_\mathcal P) \bigr). \]

9 Realization of all alternating-orthogonality targets

Let (S) be a finite-dimensional $\mathbb F_p$-vector space and let

Define

as before:

Proposition 9.1 (Realization).

For every pair ((S,K)), there exists a quadratic presentation $\mathcal P$ such that

\[ (S_\mathcal P,K_\mathcal P)\cong(S,K). \]

10 The contraction-kernel core

The target $\Omega(S,K)$ may contain many twin vertices. Its semantic content as a graph homomorphism target is captured by a weighted twin-free core. For $s\in S$, define

This is precisely the neighborhood of (s) in $\Omega(S,K)$. Define an equivalence relation on (S) by

Let

For $L\in\mathcal K(S,K)$, define its multiplicity

We define a weighted reflexive graph

as follows:

• the vertex set is $\mathcal K(S,K)$;

• the vertex weight of $L$ is $\mu(L)$;

• vertices (L) and (M) are adjacent if, for some equivalently every $s,t\in S$ with $K_s=L$ and $K_t=M$, one has

Lemma 10.1 (Well-defined adjacency).

The adjacency relation on $\operatorname{Core}(S,K$) is well-defined.

Proposition 10.2 (Weighted-core identity).

For every finite graph $\Gamma$,

\[ \operatorname{hom}(\Gamma,\Omega(S,K)) \sum_{\phi:\Gamma\to\operatorname{Core}(S,K)} \prod_{u\in V(\Gamma)}\mu(\phi(u)). \]

11 Semantic equivalence of quadratic presentations

Two quadratic presentations may have different variable and relation spaces but produce identical observables on all graphical groups. The weighted core gives the exact criterion.

Theorem 11.1 (Semantic equivalence theorem).

Let $\mathcal P$ and $\mathcal P'$ be quadratic presentations with associated pairs

\[ (S,K), \qquad (S',K'). \]

The following are equivalent:

• for every finite graph $\Gamma$,

-

and the weighted reflexive graphs

are isomorphic.

12 Quadratic right-profile completeness

Let

For a graph $\Gamma$, define its quadratic right profile by

Theorem 12.1 (Quadratic right-profile completeness).

For finite graphs $\Gamma,\Gamma'$, the following are equivalent:

• $\Gamma\cong\Gamma'$;

• $G_\Gamma\cong G_{\Gamma'}$;

• all coefficient-free quadratic presentation counts agree on $G_\Gamma$ and $G_{\Gamma'}$;

• $\Gamma$ and $\Gamma'$ have the same number of edges and

13 Complexity dichotomy

For a fixed graph (H), the problem

is the $\#H$-Coloring problem. Dyer and Greenhill proved a dichotomy for this problem. In the case where $H$ is connected and reflexive, the problem is polynomial-time computable precisely when $H$ is a complete reflexive graph; otherwise it is $\#P$-complete. Every target

is reflexive. It is also connected, because $0\in S$ is adjacent to every vertex.

Theorem 13.1 (QPC dichotomy on graphical groups).

Let $\mathcal P$ be a fixed quadratic presentation with associated pair

\[ (S,K). \]

The problem

\[ \Gamma\longmapsto |\operatorname{Sol}_{\mathcal P}(G_\Gamma)| \]

is polynomial-time computable if

\[ K=\Lambda^2S, \]

and is ($\#P$)-complete otherwise.

Example 13.2 (Commuting pairs).

The observable

\[ [x_1,x_2]=1 \]

has

\[ S=\mathbb F_p^2 \]

and

\[ K=0\le\Lambda^2S. \]

Thus

\[ s\sim t \iff s\wedge t=0, \]

i.e. (s,t) are linearly dependent. The target is not complete. Therefore exact counting of commuting pairs in $G_\Gamma$, with $\Gamma$ as input, is ($\#P$)-complete.

14 Relation to left and right homomorphism profiles

The theory above is a right-profile theory. Lovasz's classical theorem says that the full left profile

determines $\Gamma$. Restrictions of left profiles, for example to bounded-treewidth sources, are closely related to Weisfeiler--Leman equivalence and counting logics. By contrast, QPC on graphical groups produces restricted right profiles:

The expressive behavior of restricted right profiles is different from that of restricted left profiles. In particular, known results of Atserias--Kolaitis--Wu show that several equivalences captured by restrictions of left profiles, including fixed-variable counting logic equivalence, cannot in general be captured by restricting the right profile to a fixed class of targets. Accordingly, we do not interpret QPC as another form of Weisfeiler--Leman refinement. It is a different observational hierarchy, based on finite alternating-orthogonality targets.

15 Coefficient-free observables and arity

We now turn from graphical groups to arbitrary finite groups in $\mathcal N_{2,p}$. A coefficient-free observable in (k) variables is a Boolean combination of word equations and disequations in variables

with no named constants from the ambient group. For such an observable $\Phi$, write

for the number of satisfying (k)-tuples in (G). For finite groups (G,H), define

to be the least (k) such that there exists a coefficient-free observable $\Phi$ in (k) variables with

If no such (k) exists, set

For finite groups, $\operatorname{qvar}(G,H$) is finite whenever $G\not\cong H$.

16 Locality through generated subgroups

Lemma 16.1 (Generated-subgroup decomposition).

Let $\Phi$ be a coefficient-free observable in (k) variables. For every finite group (G),

\[ Z_\Phi(G) \sum_{L\le G}\tau_\Phi(L), \]

where

\[ \tau_\Phi(L) \#\left\{ (l_1,\dots,l_k)\in L^k: \langle l_1,\dots,l_k\rangle=L, L\models \Phi(l_1,\dots,l_k) \right\}. \]

Moreover, $\tau_\Phi(L$) depends only on the isomorphism type of (L).

Corollary 16.2.

Suppose (G) and (H) have the same multiset of isomorphism types of proper subgroups, counted with multiplicity. If

\[ k<\min{d(G),d(H)}, \]

then every coefficient-free observable in (k) variables has the same number of solutions in (G) and (H).

17 A general arity upper bound

We now prove a complementary upper bound using Hom/Inj inversion.

Lemma 17.1 (Hom-count separation by a quotient).

Let (G,H) be finite groups of the same order with

\[ G\not\cong H. \]

Then there exists a normal subgroup

\[ N\trianglelefteq G \]

such that

\[ |\operatorname{Hom}(G/N,G)| \ne |\operatorname{Hom}(G/N,H)|. \]

Corollary 17.2 (General arity upper bound).

If $G,H\in\mathcal N_{2,p}$ are finite, nonisomorphic, and have the same order, then

\[ \operatorname{qvar}(G,H) \le \min{d(G),d(H)}. \]

18 Wilson groups and the exact arity barrier

We use the following theorem of Wilson.

Theorem 18.1 (Wilson's subgroup-profile examples).

For primes

\[ p>2 \]

and integers

\[ e>3, \]

there exists a family $\mathcal W_{p,e}$ of at least

\[ \frac{p^{e-3}}{e} \]

pairwise nonisomorphic (p)-groups such that every $G\in\mathcal W_{p,e}$ satisfies:

• $|G|=p^{2e+2}$;

• (d(G)=2e);

• all groups in $\mathcal W_{p,e}$ have the same multiset of isomorphism types of proper subgroups;

• all groups in $\mathcal W_{p,e}$ have the same multiset of isomorphism types of proper quotients. These groups lie in the class of (p)-groups considered by Wilson's logarithmic subgroup-profile construction. We now obtain the exact arity barrier.

Theorem 18.2 (Exact observable arity barrier).

Let (G,H) be two nonisomorphic groups in $\mathcal W_{p,e}$. Then

\[ \operatorname{qvar}(G,H)=2e. \]

Equivalently,

\[ \operatorname{qvar}(G,H)=\log_p|G|-2. \]

Moreover, for every

\[ k<2e, \]

all groups in $\mathcal W_{p,e}$ have identical values for every coefficient-free observable in (k) variables.

19 Interpretation of the arity barrier

Theorem 18.2 shows that arity is a genuine resource for coefficient-free observables. It is not enough to use:

• more relators;

• longer relators;

• more complicated Boolean combinations; if the number of variables is below the generator rank. For the Wilson families, every such observable is trapped inside proper subgroups, and the proper subgroup profiles are identical. Thus the subgroup-profile obstruction is not merely an obstruction to a particular algorithm or heuristic. It obstructs the entire coefficient-free observable hierarchy below the generator rank.

20 Main conclusions

The paper establishes the following principles.

20.1 Quadratic collapse

In $\mathcal N_{2,p}$, every word observable is quadratic.

20.2 Right-profile semantics

On graphical (p)-groups, every quadratic observable is exactly a right homomorphism count toward an alternating-orthogonality target.

20.3 Canonical semantic core

Every such target has a weighted twin-free core determined by the contraction kernels

Two observables have the same values on all graphical groups if and only if their weighted cores agree.

20.4 Complexity dichotomy

Every fixed nondegenerate observable gives a ($\#P$)-complete counting problem on input graphs.

20.5 Exact arity barrier

There exist nonisomorphic groups in $\mathcal N_{2,p}$ requiring exactly

variables to distinguish by any coefficient-free observable.

21 Further directions

21.1 Budget beyond arity

Theorem 18.2 measures variables. It does not measure:

• number of relators;

• sparsity;

• circuit size;

• observable width. A refined theory should study trade-offs between these resources.

21.2 Restricted target families

The full family

is complete for graphical groups. It remains to understand which subfamilies retain significant distinguishing power. Natural candidates include:

• symplectic targets;

• low-codimension kernels (K);

• targets of bounded contraction-kernel diversity;

• targets arising from small-rank commutator systems.

21.3 Canonization

This paper studies counting observables, not canonical forms. A natural next goal is to turn right-profile or quadratic-presentational data into canonical decompositions for alternating maps

21.4 Relation to proof complexity

Reducing QPC counts modulo (p) gives polynomial functions in the structure constants of the alternating map. This suggests a connection with low-degree invariant theory and proof complexity for tensor isomorphism.

Declaration of generative AI and AI-assisted technologies in the writing process

During the preparation of this work, ChatGPT, by OpenAI, was used to assist with mathematical drafting, formalization, review, and editing. This work is shared as a preliminary AI-assisted mathematical note. The mathematical content may have been only partially reviewed and may contain errors; it should not be treated as peer-reviewed or as a fully verified manuscript.