A Frobenius-Schreier-Sims Algorithm to tensor decompose algebras

Ian Holm Kessler, Henry Kvinge, James B. WilsonarXiv 2018 · DOI · arXiv

Abstract

We introduce a decomposition of associative algebras into a tensor product of cyclic modules. This produces a means to encode a basis with logarithmic information and thus extends the reach of calculation with large algebras. Our technique is an analogue to the Schreier-Sims algorithm for permutation groups and is a by-product of Frobenius reciprocity.

Introduction

In computational algebra, determining the dimension or identifying a basis for large associative algebras—such as group algebras or finitely presented algebras—is a notoriously difficult task. For decades, the Schreier-Sims algorithm has been the gold standard for handling large permutation groups by breaking them down into a "stabilizer chain." However, a direct analogue for general algebras has not previously existed.

This paper introduces the Frobenius-Schreier-Sims (FSS) algorithm, a novel method for decomposing large associative algebras into a tensor product of smaller cyclic modules. By bridging the gap between group theory and representation theory, the authors provide a way to compute dimension bounds and encode bases for massive algebras using significantly less information.

Theoretical Foundation: Frobenius Reciprocity

The core breakthrough of this work is the recognition that the classical Schreier-Sims algorithm is a special case of Frobenius Reciprocity, a fundamental tool in representation theory that relates induced and restricted representations. The authors realized that the "Schreier's Lemma" used in group theory is essentially the same formula as the "Frobenius counit." This realization allowed them to generalize a group-theoretic trick into a powerful tool for linear algebra, enabling the extraction of structural information even from "unfaithful" representations (where some algebra elements act as zero on a module).

The FSS Algorithm

The FSS algorithm operates through a sophisticated multi-step process to move from a representation back to the algebra's core structure:

  1. Module Selection: The process begins with an algebra $A$ and an $A$-module $M$.
  2. Submodule Identification: The algorithm uses established tools like the MeatAxe to find a simple submodule $N \leq M$.
  3. Idempotent Lifting: To map information from the representation back to the algebra, the authors use "idempotent lifting" to establish a "frame"—a set of coordinates within the algebra.
  4. Generator Construction: A new set of "Frobenius-Schreier-Sims generators" ($U$) is defined based on a transversal and a section.
  5. Tensor Decomposition: The primary theoretical result (Theorem 1.1) proves that for any semiprimary algebra, there exists a chain of subalgebras such that $A$ is the image of a tensor product of cyclic modules: $$A_0x_1 \otimes \dots \otimes A_{\ell-1}x_\ell \otimes A_\ell \twoheadrightarrow A$$

Empirical Validation and Results

The algorithm was validated using complex algebraic structures as benchmarks rather than traditional datasets:

  • The Dihedral Group ($D_8$): This served as a "toy example" to demonstrate the algorithm's mechanics in a familiar setting.
  • Degenerate Cyclotomic Hecke Algebras: These are central to Lie theory and quantum groups but are often not semisimple, making their dimensions and simple modules hard to calculate. The FSS algorithm successfully identified the underlying structure of induced representations in these cases.

Key Metrics

The algorithm provides a concrete upper bound for the dimension of an algebra: $$\dim A \leq \dim M_1 \cdots \dim M_\ell \cdot \dim A_\ell$$ By decomposing the algebra into a tensor product, the basis can be encoded with logarithmic information, allowing researchers to describe very large spaces using a relatively small set of generators.

Limitations and Future Work

Despite its power, the FSS algorithm faces certain challenges:

  • The Annihilator Problem: If an element of the algebra is in the "annihilator" (acting as zero on the module $M$), the algorithm cannot distinguish it from zero. Consequently, the algorithm provides an upper bound on dimension rather than always providing the exact value.
  • Computational Complexity: While the construction of the data structure is polynomial-time, the number of terms in linear combinations can grow exponentially during the "rewriting" process.
  • The Final Term ($A_\ell$): There remains a "lingering ambiguity" regarding the final term of the chain. Future work is required to better predict when this term simplifies to the base field $K$.

Conclusion

The Frobenius-Schreier-Sims algorithm represents a significant step forward in computational representation theory. By leveraging the relationship between Schreier's Lemma and Frobenius reciprocity, it provides a robust framework for handling non-semisimple algebras and large-scale algebraic structures that were previously computationally inaccessible.

Summary updated

Abstract

We introduce a decomposition of associative algebras into a tensor product of cyclic modules. This produces a means to encode a basis with logarithmic information and thus extends the reach of calculation with large algebras. Our technique is an analogue to the Schreier-Sims algorithm for permutation groups and is a by-product of Frobenius reciprocity.
BibTeX
@misc{kessler2018frobenius,
  author = {Ian Holm Kessler and Henry Kvinge and James B. Wilson},
  title = {{A Frobenius-Schreier-Sims Algorithm to tensor decompose algebras}},
  year = {2018},
  eprint = {1812.03346},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.03346},
}
Figure