Let $p\geq 3$ be a prime. Let $\Lambda(n,p)$ be the set of alternating matrices over $\mathbb{F}_p$, where $A\in M(n,p)$ is alternating if for all $v\in\mathbb{F}_p^n$, $v^tAv=0$. Let $\mathbb{A}\in\Lambda(n,q)^m$ be an $m$-tuple of alternating matrices. We say two $m$-tuple of alternating matrices $\mathbb{A}_1$ and $\mathbb{A}_2$ pseudo-isometric, if there exists $T\in \text{GL}(n,p)$ such that $\langle T^t\mathbb{A}_1T\rangle=\langle\mathbb{A}_2\langle$ (as subspaces), where $\langle \mathbb{A} \rangle$ denotes the linear space spanned by alternating matrices in the $m$-tuple $\mathbb{A}$.
Pseudo-isometry testing can be done in $p^{\Theta(n^2)}\text{poly}(n,m,\log p)$. In~[Brooksbank et al., 2019], if one of the two alternating matrix tuples \emph{doesn’t have shrunk subspace}, the isometric testing can be done in time $p^{O(n+m)}$.
Definition. A subspace $U\leq \mathbb{F}_q^n$ is a shrunk subspace of $\mathbb{A}$ if $\dim(U)>\dim(\mathbb{A}(U))$, where $\mathbb{A}(U)=\text{span}{Au:A\in\mathbb{A},~u\in U}$.
Alternating matrix tuples can be converted into $p$-groups of class $2$ and exponent $p$ through the Baer correspondence: Let $\mathbb{A}=(A_1,\cdots,A_m)$ be an $m$-tuple of $n\times n$ alternating matrices over $\mathbb{F}:=\mathbb{F}_p$. Let $\phi:\mathbb{F}^n\times\mathbb{F}^n\to\mathbb{F}^m$ be an alternating bilinear map defined as $\phi(u,v)=(u^tA_1v,\dots,u^tA_mv)^t\in\mathbb{F}^m$ for $u,v\in\mathbb{F}^n$.
Define the $p$-groups of class $2$ and exponent $p$ $P_{\phi}$ as follows: the group elements are pairs of vectors $(u,v)\in\mathbb{F}^n\oplus\mathbb{F}^m$. The group product is defined as $(u_1,v_1)\circ(u_2,v_2)=(u_1+u_2,v_1+v_2+\frac{1}{2}\phi(u_1,u_2))$.
There is also a reverse convention from $p$-groups of class $2$ and exponent $p$ to alternating matrix tuples. The Baer correspondence connect the isomorphism testing of $p$-groups of class $2$ and exponent $p$ with the pseudo-isometry testing of alternating matrix tuples: A polynomial-time algorithm (in the group order) for testing isomorphism for $p$-groups of class $2$ and exponent $p$, known as the bottleneck case of general group isomorphism, is equivalent to a $p^{O(n+m)}$-time algorithm for testing pseudo-isometry for $m$-tuples of $n\times n$ alternating matrix spaces over $\mathbb{F}$.
Problem. What is the corresponding group structure of shrunk subspaces of alternating matrix tuples, through the Baer correspondence?
An answer to this problem helps to identify what group structure prevents a polynomial-time isomorphism testing for $p$-groups of class $2$ and exponent $p$.
Additional Questions?
If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.
