Enumeration of Integral Table Algebras of ranks 4 and 5

by

Allen Herman
(Department of Mathematics and Statistics, University of Regina, Canada)
and
Thomas Stanley
(University of Saskatchewan, Canada).

First update: July 15, 2017. Latest update: July 17, 2017.

Acknowledgements

This project was supported by NSERC's USRA and Discovery Grant programs. Computing facilities were provided by the Laboratory of Computational Discovery at the University of Regina, and our programming was done using the Computer Algebra Program GAP: Groups, Algorithms, and Programming.

The Project

The goal of the project was to create a database of integral table algebras of ranks 4 and 5 with order up to 100 up to exact isomorphism. (For ranks 2 and 3 general formulas were already available, see below.) The database entries are the standard integral table algebra bases of rank r recorded as a list of matrices in the left regular represenation of the algebra:
b = { b[0],b[1],...b[r-1] } , and the entries of these matrices are the nonnegative integers b[i][k][j] when b[i] b[j] = SUMk b[i][k][j] b[k] . The first basis element b[0] is always the r x r identity matrix. The degree map of the algebra corresponds to the row sum on these basis matrices. As noncommutative rank 5 table algebras cannot be integral, all of these integral table algebras are commutative.
Our database was generated by an algorithm that searched for nonnegative integral solutions to the polynomial equations that define the variety for the given rank and involution type. The details of the approach, as well as the number of integral table algebras found for each order appear in our preprint. Lists of standard integral table bases are provided for each rank, involution type, and order in a GAP-friendly format, and each list is accompanied by GAP functions supplying the source code for generating the list in GAP. For each rank and involution type, the source code file includes some additional functions concerning properties interesting to those studying table algebras:
DegreesOfTA(b); - the list of degrees of elements in the standard basis (note that the sum of these degrees is the order of the table algebra),
FirstEigenmatrixofTA(b); - the character table, (b is one table algebra basis from our database), the algorithm we use depends on the rank and will fail to return the character table in noncyclotomic or very large cyclotomic situations,
ClosedSubsetsOfTA(b); - gives the subsets S of [1..r] for which {b[i]: i in S} is a closed subset of the table algebra, FusionsOfTA(b); - gives the partitions P of [1..r] for which {d[k] = SUMi in P[k] b[i] } is the basis of a fusion subalgebra of the table algebra (note that we do not require that [1] be a singleton of the partition so the quotient table algebras of the original can be determined from this fusion list),
SecondEigenmatrixofTA(b); - the second eigenmatrix, calculated from the first eigenmatrix as nC^(-1), MultiplicitiesOfTA(b); - the list of multiplicities of the table algebra calculated as the degrees coming from the second eigenmatrix.
Warning: In cases where the entries of the first eigenmatrix are not contained in a cyclotomic field the first eigenmatrix function returns "Not cyclotomic", along with an irreducible polynomial factor of one of the minimal polynomials of the basis elements and an identification the nonabelian Galois group of its splitting field. In these cases our functions for the multiplicities and second eigenmatrix will not work.

Rank 2: Integral table algebras of rank 2 and order n+1 are represented by the adjacency matrices of complete graphs of order n+1. Each basis b = { b[0],b[1] } has structure constants determined by
b[1]2 = n b[0] + (n-1) b[1].

Rank 3, asymmetric: b = { b[0], b[1], b[1]* }. Integrality requires the nonidentity basis elements to have odd degree 2u+1, so the order is n = 4u+3 and the structure constants are given by
b[1]2 = u b[1] + (u+1) b[1]*
b[1] b[1]* = (2u+1)b[0] + u b[1] + u b[1]*

Rank 3, symmetric: b = { b[0], b[1], b[2] }. The nonidentity basis elements have degrees k and l, and the basis is determined by one further independent parameter u. The product b[1]b[2] = b[2]b[1] = u b[1] + v b[2] and the parameter v must satisfy the further restriction kl = ku + vl. The structure constants of the standard basis are given by
b[1] b[2] = b[2]b[1] = ub[1]+vb[2]
b[1]2 = k b[0] + (k-u-1) b[1] + (k-v) b[2]
b[2]2 = l b[0] + (l-u) b[1] + (l-v-1) b[2]
Note that these table algebras are always P-polynomial. They are realized as association schemes if and only if b[1] is the adjacency matrix of a strongly regular graph.

Rank 4, asymmetric: b = { b[0], b[1], b[2], b[2]* }. The ideal corresponding to the variety is generated by 7 polynomials in 8 variables. Our source code will generate the list of standard bases up to order 100 in just a few seconds, readers are welcome to attempt higher orders with our program. The source code and additional database functions are provided here: Rank 4 Asymmetric. To generate the list of standard bases of integral table algebras of order n for this rank and involution type, read our source code file into GAP and type the command gap> ITAsRnk4AOrder(n); (A similar approach can be applied to use our source code files in the other cases.)

Rank 4, symmetric: b = { b[0], b[1], b[2], b[3] }. The ideal corresponding to the variety is generated by 10 polynomials in 12 variables. Our source code generates the list of standard bases up to order 100 in about an hour, readers are welcome to attempt higher orders with our program. The source code and additional database functions are provided here: Rank 4 Symmetric.

Rank 5, 2 asymmetric pairs: b = { b[0], b[1], b[1]*, b[2], b[2]* }. We were able to reduce our defining set of polynomials for the variety to a collection of 64 polynomials in 18 variables. It turns out that all integral table algebras of this rank and involution type have order n=4k+1 for some positive integer k. Our source code will generate the list of standard bases up to order 100 in about an hour, readers are welcome to attempt higher orders with our program. The source code and additional database functions are provided here: Rank 5, Two Asymmetric Pairs.

Rank 5, 1 asymmetric pair: b = { b[0], b[1], b[2], b[3], b[3]* }. We were able to reduce our defining set of polynomials for the variety to a collection of 54 polynomials in 19 variables. Our source code will generate the list of standard bases up to order 100 in about a day, readers are welcome to attempt higher orders with our program. The source code and additional database functions are provided here: Rank 5, One Asymmetric Pair.

Rank 5, symmetric: b = { b[0], b[1], b[2], b[3], b[4] }. We were able to reduce our defining set of polynomials for the variety to a collection of 45 polynomials in 28 variables. Our source code generated the list of standard bases up to order 90 in about a month on the LCD machine, and we completed orders 91 to 100 done in parallel, each of these orders took up to three days. There are almost 10,000 of these with order 100. The source code and additional database functions are provided here: Rank 5, Symmetric. A .zip archive of our rank 5 symmetric integral table algebras database (with with actual file size 1.09 MB) can be obtained by downloading: Rank 5 symmetric: Order up to 100
To load the database in GAP, unzip the database, upload the ITAsRnk5SDBFunctions.txt file to your GAP directory, then start GAP and type gap> Read("ITAsRnk5SDB.txt");