Certifying Numerical Decompositions of Compact Group Representations

We present a performant and rigorous algorithm for certifying that a matrix is close to being a projection onto an irreducible subspace of a given group representation. This addresses a problem arising when one seeks solutions to semi-definite programs (SDPs) with a group symmetry. Indeed, in this context, the dimension of the SDP can be significantly reduced if the irreducible representations of the group action are explicitly known. Rigorous numerical algorithms for decomposing a given group representation into irreps are known, but fairly expensive. To avoid this performance problem, existing software packages -- e.g. RepLAB, which motivated the present work -- use randomized heuristics. While these seem to work well in practice, the problem of to which extent the results can be trusted arises. Here, we provide rigorous guarantees applicable to finite and compact groups, as well as a software implementation that can interface with RepLAB. Under natural assumptions, a commonly used previous method due to Babai and Friedl runs in time O(n^5) for n-dimensional representations. In our approach, the complexity of running both the heuristic decomposition and the certification step is O(max{n^3 log n, D d^2 log d}), where d is the maximum dimension of an irreducible subrepresentation, and D is the time required to multiply elements of the group. A reference implementation interfacing with RepLAB is provided.

Rank-deficient representations in the Theta correspondence over finite fields arise from quantum codes

Let V be a symplectic vector space and let $mu$ be the oscillator representation of Sp(V). It is natural to ask how the tensor power representation $mu^{otimes t}$ decomposes. If V is a real vector space, then Howe-Kashiwara-Vergne (HKV) duality asserts that there is a one-one correspondence between the irreducible subrepresentations of Sp(V) and the irreps of an orthogonal group O(t). It is well-known that this duality fails over finite fields. Addressing this situation, Gurevich and Howe have recently assigned a notion of rank to each Sp(V) representation. They show that a variant of HKV duality continues to hold over finite fields, if one restricts attention to subrepresentations of maximal rank. The nature of the rank-deficient components was left open. Here, we show that all rank-deficient Sp(V)-subrepresentations arise from embeddings of lower-order tensor products of $mu$ and $barmu$ into $mu^{otimes t}$. The embeddings live on spaces that have been studied in quantum information theory as tensor powers of self-orthogonal Calderbank-Shor-Steane (CSS) quantum codes. We then find that the irreducible Sp(V) subrepresentations of $mu^{otimes t}$ are labelled by the irreps of orthogonal groups O(r) acting on certain r-dimensional spaces for r <= t. The results hold in odd charachteristic and the stable range t <= 1/2 dim V. Our work has implications for the representation theory of the Clifford group. It can be thought of as a generalization of the known characterization of the invariants of the Clifford group in terms of self-dual codes.