Splitting Permutation Representations of Finite Groups by Polynomial Algebra Methods

Abstract

An algorithm for splitting permutation representations of a finite group over fields of characteristic zero into irreducible components is described. The algorithm is based on the fact that the components of the invariant inner product in invariant subspaces are operators of projection into these subspaces. An important part of the algorithm is the solution of systems of quadratic equations. A preliminary implementation of the algorithm splits representations up to dimensions of hundreds of thousands. Examples of computations are given in the appendix.

1 Introduction

One of the central problems of group theory and its applications in physics is the decomposition of linear representations of groups into irreducible components. In general, the problem of splitting a module over an associative algebra into irreducible submodules is quite nontrivial. An overview of the algorithmic aspects of this problem can be found in Chap. 7 of [1]. For vector spaces over finite fields, the most efficient is the Las Vegas algorithm¹ called MeatAxe [2]. This algorithm played an important role in solving the problem of classifying finite simple groups. However, the approach used in the MeatAxe is ineffective in characteristic zero, whereas quantum-mechanical problems are formulated just in Hilbert spaces over zero characteristic fields. Our algorithm deals with representations over such fields, and its implementation copes with dimensions up to hundreds of thousands, which is not less than the dimensions achievable for the MeatAxe. The algorithm requires knowledge of the centralizer ring of the considered group representation. In the general case, the calculation of the centralizer ring is a problem of linear algebra, namely, solving matrix equations of the form . For permutation representations, there is an efficient way to compute the centralizer ring, which reduces to constructing the set of orbitals. In addition, permutation representations are fundamental in the sense that any linear representation of a finite group is a subrepresentation of some permutation representation, and we use this fact in some quantum mechanical considerations [3, 4]. Thus, we consider only permutation representations here.

2 Mathematical Preliminaries

Let (or ) be a transitive permutation group on a set . We will denote the action of on by . A representation of in an -dimensional vector space over a field by the matrices with the entries , where is the Kronecker delta, is called a permutation representation. We assume that the permutation representation space is a Hilbert space . We will assume that the base field is a constructive splitting field of the group . In particular, such a field can be a subfield of the th cyclotomic field, where is a suitable divisor of the exponent of . Such a constructive field , being an abelian extension of the field , is a dense subfield of or .

An orbit of on the Cartesian square is called an orbital [5]. The number of orbitals, called the rank of , will be denoted by . An orbital is called self-paired, if , i.e., . Among the orbitals of a transitive group, there is one diagonal orbital, , which will always be fixed as the first element in the list of orbitals: . For transitive action of , there is a natural one-to-one correspondence between the orbitals of and the orbits of a point stabilizer :

$$\begin{aligned} {\varDelta \longleftrightarrow \varSigma _i=\left\{ j\in \varOmega \mid \left( i,j\right) \in \varDelta \right\} .} \end{aligned}$$

The -orbits are called suborbits and their cardinalities will be called the suborbit lengths. Note that .

The invariance condition for a bilinear form in the Hilbert space can be written as the system of equations It is easy to verify that in terms of the entries these equations have the form Thus, the basis of all invariant bilinear forms is in one-to-one correspondence with the set of orbitals: with each orbital is associated a basis matrix of the size with the entries

$$\begin{aligned} {\left( \mathcal {A}_{r}\right) _{\displaystyle {}ij} = {\left\{ \begin{array}{ll} 1, &{}\text {if}\,\,\left( i,j\right) \in \varDelta _r,\\ 0, &{}\text {if}\,\,\left( i,j\right) \notin \varDelta _r. \end{array}\right. }} \end{aligned}$$

It is clear that the matrix of a self-paired orbital is symmetric. For the diagonal orbital, we have . The matrices

$$\begin{aligned} {\mathcal {A}_{1},\mathcal {A}_{2},\ldots ,\mathcal {A}_{\mathrm {R}}} \end{aligned}$$

(1)

form a basis of the centralizer ring (or centralizer algebra) of the representation . The multiplication table for this basis has the form

$$\begin{aligned} {\mathcal {A}_{p}\mathcal {A}_{q}=\sum _{r=1}^{\mathrm {R}}C_{pq}^r\mathcal {A}_{r},} \end{aligned}$$

(2)

where are non-negative integers. The commutativity of the centralizer ring indicates that the permutation representation is multiplicity-free.

3 Algorithm

Let be a transformation (we can assume that is a unitary matrix) that splits the permutation representation into irreducible components:

$$\begin{aligned} {T^{-1}\mathrm {P}\!\left( g\right) T=1\oplus \mathsf {U}_{\!d_2}\!\left( g\right) \oplus \cdots \oplus \mathsf {U}_{\!d_m}\!\left( g\right) \oplus \cdots \oplus \mathsf {U}_{\!d_M}\!\left( g\right) ,} \end{aligned}$$

where is a -dimensional irreducible subrepresentation, denotes the direct sum of matrices, i.e., .

The identity matrix is the standard inner product in any orthonormal basis. In the splitting basis, we have the following decomposition of the standard inner product

The inverse image of this decomposition in the original permutation basis has the form

(3)

where is defined by the relation

(4)

The set contains complete information about irreducible decomposition of the representation . In particular, the transformation matrix can be obtained from the linear system

The main idea of the algorithm is based on the fact that ’s form a complete set of orthogonal projectors, i.e., in addition to the completeness (3), we have the idempotency

$$\begin{aligned} {\mathcal {B}_{m}^2=\mathcal {B}_{m}} \end{aligned}$$

(5)

and the mutual orthogonality

(6)

It follows from (4) that

$$\begin{aligned} {{{\mathrm{tr}}}\mathcal {B}_{m}=d_{m}.} \end{aligned}$$

(7)

We see that all ’s can be obtained as solutions of the equation

(8)

for the generic invariant form

$$\begin{aligned} {X=x_1\mathcal {A}_{1}+\cdots +x_\mathrm {R}\mathcal {A}_{\mathrm {R}}.} \end{aligned}$$

Using the multiplication table (2), we can write the left-hand side of (8) as a set of polynomials (we will call them idempotency polynomials)

$$\begin{aligned} {E\!\left( x_1,\ldots ,x_\mathrm {R}\right) =\left\{ E_1\!\left( x_1,\ldots ,x_\mathrm {R}\right) ,\ldots ,E_\mathrm {R}\!\left( x_1,\ldots ,x_\mathrm {R}\right) \right\} } \end{aligned}$$

(9)

and Eq. (8) can be written symbolically as

$$\begin{aligned} {E\!\left( x_1,\ldots ,x_\mathrm {R}\right) =0.} \end{aligned}$$

(10)

Each polynomial in (9) has the structure , where is a homogeneous quadratic polynomial in the indeterminates .

In the basis (1), the projector can be represented as

$$\begin{aligned} {\mathcal {B}_{m}=b_{m,1}\mathcal {A}_{1}+b_{m,2}\mathcal {A}_{2}+\cdots +b_{m,\mathrm {R}}\mathcal {A}_{\mathrm {R}},} \end{aligned}$$

where the vector ${~B_m=\left[ b_{m,1},\ldots ,b_{m,\mathrm {R}}\right] ~}$ is a solution of Eq. (10).

Since only has nonzero diagonal elements, we have

$$\begin{aligned} {{{\mathrm{tr}}}\mathcal {B}_{m}=b_{m,1}\mathsf {N}.} \end{aligned}$$

Combining this with (7) we can fix the coefficient :

$$\begin{aligned} {b_{m,1}=d_m/\mathsf {N}.} \end{aligned}$$

Thus, the only relevant values of in (10) are for some ’s from the interval . Any relevant natural number is either an irreducible dimension or a sum of such dimensions. Using the orthogonality condition (6) for the irreducible projectors, we can exclude the consideration of dimensions that are sums of irreducible ones. The generic orthogonality condition can be written as

$$\begin{aligned} {BX=0,} \end{aligned}$$

(11)

where Equation (11) is a system of linear equations for the indeterminates with the parameters . Again, using the multiplication table (2), we can write the left-hand side of (11) as a system of bilinear forms, which we denote by

$$\begin{aligned} {O\!\left( b_1,\ldots ,b_\mathrm {R};x_1,\ldots ,x_\mathrm {R}\right) } \end{aligned}$$

(12)

and call orthogonality polynomials.

The core part of the algorithm is a loop on dimensions that starts with and ends when the sum of irreducible dimensions becomes equal to .

The current is processed as follows.

• We solve² the system of equations

• If the system is incompatible, then go to the next .

• If describes a zero-dimensional ideal, then we have (including ) different -dimensional irreducible subrepresentations.

• If the polynomial ideal has dimension , then we encounter an irreducible component with a multiplicity . The corresponding component of the centralizer algebra has the form , where is an arbitrary matrix, and denotes the Kronecker product. The idempotency condition implies The complete family of solutions of this equation³ is a manifold of dimension In this case, we select, by a somewhat arbitrary procedure, convenient mutually orthogonal representatives in the family of equivalent subrepresentations.

• In any case, if at the moment we have a solution , we append to the list of irreducible projectors, and exclude from the further consideration the corresponding invariant subspace by adding the linear orthogonality polynomials to the polynomial system:

  $$\begin{aligned} {E\!\left( x_1,x_2,\ldots ,x_\mathrm {R}\right) \leftarrow {}E\!\left( x_1,x_2,\ldots ,x_\mathrm {R}\right) \cup \left\{ \mathcal {B}_{m}X\right\} .} \end{aligned}$$

• After processing all ’s of dimension , go to the next .

4 Implementation

Our approach involves some widely used methods of polynomial computer algebra. Therefore, it is reasonable, at least for the preliminary experience, to take advantage of computer algebra systems with developed tools for working with polynomials.

The complete algorithm is implemented by two procedures, the pseudocodes of which are given below.

• 1. The procedure PreparePolynomialData is a program written in C. The input data for this program is a set of permutations of that generates the group The program computes the basis of the centralizer ring and its multiplication table, constructs the idempotency and orthogonality polynomials, and generates the code of the procedure SplitRepresentation that processes the polynomial data. The main parameter that determines the run time for PreparePolynomialData is the dimension of the representation. The example in Sect. A.3 shows that the PC implementation copes with a dimension of about one hundred thousand in a time of about one hour.

• 2. The procedure SplitRepresentation implements the above described loop on dimensions that splits the representation of the group into irreducible components. It is generated by the C program PreparePolynomialData. Currently, the code is generated in the Maple 2017.3 language, and the polynomial equations are processed by the Maple implementation of the Gröbner bases algorithms. The run time for SplitRepresentation depends mainly on the rank of the representation. Problems of rank take about hours on a PC.

Comments on the procedure SplitRepresentation:

• The procedure NextRelevantDimension can be implemented in different ways, depending on the available information about the group and the representation:

  • The simplest implementation is “”.

  • The implementation “repeat ” is about faster than the simplest one. In fact, the size of the group is always known.

  • Knowledge of the character decomposition provides the most efficient loop on dimensions. Sometimes this information is available. Actually, computing the character decomposition is much easier than computing the decomposition of the representation.

• The procedures SolveAlgebraicSystem and NumberOfFreeParameters involve the polynomial algebra functions available in the computer algebra system used. At present, we use the Maple implementation of Gröbner basis techniques.

• The PickBestSolution procedure is applied in the case of nontrivial multiplicity of the irreducible component. It selects a particular solution in the parametric set of solutions. Currently, the choice of solutions with zero values of parameters is used. Such an oversimplified approach sometimes leads to “ugly roots” that go beyond the “natural” splitting field. This can be illustrated by the example of a -dimensional representation of the Held group whose decomposition into irreducible components is given in Sect. A.2. The decomposition contains a -dimensional irreducible component of multiplicity two. Representatives of this component obtained by the simple version of PickBestSolution contain irrationality and expressions), which belongs to the quadratic field , while the representation in question splits over the “much smaller” field . Therefore, the PickBestSolution procedure requires improvement using strategies that lead to minimal extensions of the field .

4.1 Comparison with the Magma Implementation of the MeatAxe

The Magma database contains a -dimensional permutation representation of the exceptional group of Lie type . The decomposition into irreducible components of this representation over the field is given in [6] as an illustration of the possibilities of the MeatAxe.

The application of our algorithm to this problem shows that in the characteristic zero, the considered representation is split over the field . The calculation produces the following data:

Rank: . Suborbit lengths:

Time C: s. Time Maple: s.

Magma failed to split the -dimensional representation over the field due to memory exhaustion after long computation, but we can simulate to some extent the case of characteristic zero, using a field of a characteristic that does not divide . The smallest such field is .

Below is the session of the corresponding Magma V2.21-1 computation on a computer with two Intel Xeon E5410 2.33 GHz CPUs (time is given in seconds).

5 Conclusion

The algorithm described here is based on the use of methods of polynomial algebra, which are considered algorithmically difficult. However, our approach leads to a small number (in typical cases) of low-degree polynomials. Recall that the idempotency system (9) is a set of square polynomials. Calculations of Gröbner bases in Maple on PC are limited in practice to . Among the permutation representations available in the Atlas [7], (i.e., ) have ranks . As can be seen in Appendix A, even a straightforward implementation of the approach can cope with rather large tasks. The data presented in the appendix shows that the most restrictive parameter for the Maple part of the implementation is the rank of representations, i.e., the number of polynomial indeterminates. A possible way to improve performance is to try to develop specialized algorithms that take into account the very special type of polynomial equations that arise in the problem instead of the universal Gröbner basis methods.

A Examples of Computations

• Generators of representations are taken from the section “Sporadic groups” of the Atlas [7].

• For a group

  • denotes the Schur multiplier, the nd homology group ,

  • denotes the outer automorphism group of ,

  • denotes a covering group of , a central extension of by .

• The results presented below assume the following ordering for the centralizer ring basis matrices

  

  The matrices within the first sublist are ordered by the rule: if , where . The same rule is applied to the first elements of the pairs of asymmetric matrices.

• Representations are denoted by their dimensions in bold (possibly with some signs added to distinguish different representations of the same dimension). Permutation representations are underlined. Multiple subrepresentations are underbraced in the decompositions.

• We omit the irreducible projectors related to the trivial subrepresentation: these projectors have the standard form .

• All timing data refer to a PC with 3.30 GHz Intel Core i3 2120 CPU.

1.1 A.1 Higman–Sims Group

Main properties:

$\varvec{11200}$-dimensional Representation of $\varvec{2.HS}$ 

Rank: . Suborbit lengths:

Time C: s. Time Maple: h min s.

1.2 A.2 Held Group

Main properties:

 

$\varvec{29155}$-dimensional Representation of ${\varvec{He}}$ 

Rank: . Suborbit lengths: .

$$\begin{aligned} \mathcal {B}_{\mathbf {4352}} =&\frac{256}{1715}\left( \mathcal {A}_{1}+\frac{1}{8}\mathcal {A}_{2}+\frac{7}{768}\mathcal {A}_{3}-\frac{5}{576}\mathcal {A}_{4}-\frac{7}{128}\mathcal {A}_{6}-\frac{1}{48}\mathcal {A}_{7} \right. \\ {}&\left. \qquad \quad -\frac{1}{18}\mathcal {A}_{8}+\frac{1}{576}\mathcal {A}_{9}+\frac{1}{576}\mathcal {A}_{10}-\frac{1}{192}\mathcal {A}_{11}-\frac{1}{192}\mathcal {A}_{12} \right) \\ \mathcal {B}_{\mathbf {7650}} =&\frac{90}{343}\left( \mathcal {A}_{1}-\frac{1}{20}\mathcal {A}_{2}+\frac{1}{120}\mathcal {A}_{4}-\frac{7}{360}\mathcal {A}_{5}-\frac{1}{90}\mathcal {A}_{7}+\frac{1}{10}\mathcal {A}_{8}+\frac{1}{240}\mathcal {A}_{9} \right. \\ {}&\left. \qquad \quad +\frac{1}{240}\mathcal {A}_{10}-\frac{1}{80}\mathcal {A}_{11}-\frac{1}{80}\mathcal {A}_{12} \right) \\ \mathcal {B}_{\mathbf {11900}} =&\frac{20}{49}\left( \mathcal {A}_{1}-\frac{1}{20}\mathcal {A}_{2}-\frac{1}{720}\mathcal {A}_{4}+\frac{1}{120}\mathcal {A}_{7} -\frac{1}{18}\mathcal {A}_{8}-\frac{1}{180}\mathcal {A}_{9}-\frac{1}{180}\mathcal {A}_{10} \right. \\ {}&\left. \qquad \quad +\frac{1}{60}\mathcal {A}_{11}+\frac{1}{60}\mathcal {A}_{12} \right) \end{aligned}$$

Time C: s. Time Maple: s.

1.3 A.3 Suzuki Group

Main properties:

 

$\varvec{65520}$-dimensional Representation of $\varvec{2.Suz}$ 

Rank: . Suborbit lengths: .

$$\begin{aligned}&\mathbf {\underline{65520}}\cong \mathbf {1}\oplus \mathbf {143}\oplus \mathbf {364_\alpha }\oplus \mathbf {364_\beta }\oplus \overline{\mathbf {364_\beta }}\oplus \mathbf {5940}\oplus \mathbf {12012}\oplus \mathbf {14300}\\&\quad \quad \quad \quad \,\,\,\,\, \oplus \mathbf {16016}\oplus \overline{\mathbf {16016}} \end{aligned}$$

$$\begin{aligned} \mathcal {B}_{\mathbf {143}} =&\frac{11}{5040}\left( \mathcal {A}_{1}+\mathcal {A}_{2}+\frac{2}{11}\mathcal {A}_{3}-\frac{1}{11}\mathcal {A}_{4}+\frac{2}{11}\mathcal {A}_{5}-\frac{1}{11}\mathcal {A}_{6}+\frac{3}{11}\mathcal {A}_{9}+\frac{3}{11}\mathcal {A}_{10} \right) \\ \mathcal {B}_{\mathbf {364_\alpha }} =&\frac{1}{180}\left( \mathcal {A}_{1}+\mathcal {A}_{2}+\frac{1}{16}\mathcal {A}_{3}+\frac{1}{6}\mathcal {A}_{4}+\frac{1}{16}\mathcal {A}_{5}-\frac{1}{24}\mathcal {A}_{6}-\frac{1}{144}\mathcal {A}_{7}-\frac{1}{144}\mathcal {A}_{8} \right. \\ {}&\left. \qquad \quad -\frac{1}{9}\mathcal {A}_{9}-\frac{1}{9}\mathcal {A}_{10} \right) \\ \mathcal {B}_{\mathbf {364_\beta }} =&\frac{1}{180}\left( \mathcal {A}_{1}-\mathcal {A}_{2}-\frac{1}{8}\mathcal {A}_{3}+\frac{1}{8}\mathcal {A}_{5}+\mathrm {\mathbf {i}}\frac{\sqrt{3}}{72}\mathcal {A}_{7}-\mathrm {\mathbf {i}}\frac{\sqrt{3}}{72}\mathcal {A}_{8} \right. \\ {}&\left. \qquad \quad +\mathrm {\mathbf {i}}\frac{\sqrt{3}}{9}\mathcal {A}_{9}-\mathrm {\mathbf {i}}\frac{\sqrt{3}}{9}\mathcal {A}_{10} \right) \\ \mathcal {B}_{\mathbf {5940}} =&\frac{33}{364}\left( \mathcal {A}_{1}+\mathcal {A}_{2}+\frac{1}{352}\mathcal {A}_{3}+\frac{1}{66}\mathcal {A}_{4}+\frac{1}{352}\mathcal {A}_{5}+\frac{1}{66}\mathcal {A}_{6}-\frac{7}{864}\mathcal {A}_{7} \right. \\ {}&\left. \qquad \quad -\frac{7}{864}\mathcal {A}_{8}+\frac{1}{27}\mathcal {A}_{9}+\frac{1}{27}\mathcal {A}_{10} \right) \\ \end{aligned}$$

$$\begin{aligned} \mathcal {B}_{\mathbf {12012}} =&\frac{11}{60}\left( \mathcal {A}_{1}+\mathcal {A}_{2}+\frac{1}{88}\mathcal {A}_{3}-\frac{1}{66}\mathcal {A}_{4}+\frac{1}{88}\mathcal {A}_{5}+\frac{1}{264}\mathcal {A}_{6}-\frac{1}{33}\mathcal {A}_{9}-\frac{1}{33}\mathcal {A}_{10} \right) \\ \mathcal {B}_{\mathbf {14300}} =&\frac{55}{252}\left( \mathcal {A}_{1}+\mathcal {A}_{2}-\frac{5}{352}\mathcal {A}_{3}+\frac{1}{330}\mathcal {A}_{4}-\frac{5}{352}\mathcal {A}_{5}-\frac{1}{132}\mathcal {A}_{6}+\frac{1}{288}\mathcal {A}_{7} \right. \\ {}&\left. \qquad \quad +\frac{1}{288}\mathcal {A}_{8}+\frac{1}{99}\mathcal {A}_{9}+\frac{1}{99}\mathcal {A}_{10} \right) \\ \mathcal {B}_{\mathbf {16016}} =&\frac{11}{45}\left( \mathcal {A}_{1}-\mathcal {A}_{2}+\frac{1}{352}\mathcal {A}_{3}-\frac{1}{352}\mathcal {A}_{5}-\mathrm {\mathbf {i}}\frac{\sqrt{3}}{288}\mathcal {A}_{7}+\mathrm {\mathbf {i}}\frac{\sqrt{3}}{288}\mathcal {A}_{8} \right. \\ {}&\left. \qquad \quad +\mathrm {\mathbf {i}}\frac{\sqrt{3}}{99}\mathcal {A}_{9}-\mathrm {\mathbf {i}}\frac{\sqrt{3}}{99}\mathcal {A}_{10} \right) \end{aligned}$$

Time C: min s. Time Maple: s.

$\varvec{98280}$-dimensional Representation of $\varvec{3.Suz}$ 

Rank: . Suborbit lengths: .

$$\begin{aligned}&\mathbf {\underline{98280}}\cong \mathbf {1}\oplus \mathbf {78}\oplus \overline{\mathbf {78}}\oplus \mathbf {143}\oplus \mathbf {364}\oplus \mathbf {1365}\oplus \overline{\mathbf {1365}}\oplus \mathbf {4290}\oplus \overline{\mathbf {4290}}\\&\quad \quad \quad \,\,\,\;\;\, \oplus \mathbf {5940}\oplus \mathbf {12012}\oplus \mathbf {14300}\oplus \mathbf {27027}\oplus \overline{\mathbf {27027}} \end{aligned}$$

$$\begin{aligned} \mathcal {B}_{\mathbf {5940}} =&\frac{11}{182}\left( \mathcal {A}_{1}-\frac{7}{864}\mathcal {A}_{2}+\frac{1}{66}\mathcal {A}_{3}+\frac{1}{27}\mathcal {A}_{4}+\frac{1}{66}\mathcal {A}_{5}+\frac{1}{352}\mathcal {A}_{6}-\frac{7}{864}\mathcal {A}_{7} \right. \\ {}&\left. \quad \quad -\frac{7}{864}\mathcal {A}_{8}+\frac{1}{352}\mathcal {A}_{9}+\frac{1}{352}\mathcal {A}_{10}+\frac{1}{27}\mathcal {A}_{11}+\frac{1}{27}\mathcal {A}_{12}+\mathcal {A}_{13}+\mathcal {A}_{14} \right) \\ \mathcal {B}_{\mathbf {12012}} =&\frac{11}{90}\left( \mathcal {A}_{1}-\frac{1}{66}\mathcal {A}_{3}-\frac{1}{33}\mathcal {A}_{4}+\frac{1}{264}\mathcal {A}_{5}+\frac{1}{88}\mathcal {A}_{6}+\frac{1}{88}\mathcal {A}_{9} \right. \\ {}&\left. \quad \quad \; +\frac{1}{88}\mathcal {A}_{10}-\frac{1}{33}\mathcal {A}_{11}-\frac{1}{33}\mathcal {A}_{12}+\mathcal {A}_{13}+\mathcal {A}_{14} \right) \\ \mathcal {B}_{\mathbf {14300}} =&\frac{55}{378}\left( \mathcal {A}_{1}+\frac{1}{288}\mathcal {A}_{2}+\frac{1}{330}\mathcal {A}_{3}+\frac{1}{99}\mathcal {A}_{4}-\frac{1}{132}\mathcal {A}_{5}-\frac{5}{352}\mathcal {A}_{6}+\frac{1}{288}\mathcal {A}_{7} \right. \\ {}&\left. \quad \quad \; +\frac{1}{288}\mathcal {A}_{8}-\frac{5}{352}\mathcal {A}_{9}-\frac{5}{352}\mathcal {A}_{10}+\frac{1}{99}\mathcal {A}_{11}+\frac{1}{99}\mathcal {A}_{12}+\mathcal {A}_{13}+\mathcal {A}_{14} \right) \\ \mathcal {B}_{\mathbf {27027}} =&\frac{11}{40}\left( \mathcal {A}_{1}-\frac{1}{432}\mathcal {A}_{2}+\frac{1}{297}\mathcal {A}_{4}-\frac{1}{176}\mathcal {A}_{6}-\frac{\mathsf {r}_{}}{432}\mathcal {A}_{7}-\frac{\mathsf {r}_{}^2}{432}\mathcal {A}_{8} \right. \\ {}&\left. \quad \quad \quad -\frac{\mathsf {r}_{}}{176}\mathcal {A}_{9}-\frac{\mathsf {r}_{}^2}{176}\mathcal {A}_{10}+\frac{\mathsf {r}_{}^2}{297}\mathcal {A}_{11}+\frac{\mathsf {r}_{}}{297}\mathcal {A}_{12}+\mathsf {r}_{}\mathcal {A}_{13}+\mathsf {r}_{}^2\mathcal {A}_{14} \right) \end{aligned}$$

is the basic primitive rd root of unity.

Time C: min s. Time Maple: min s.