{'fraction_non_alphanumeric': 0.0346002621231979, 'fraction_numerical': 0.008125819134993446, 'mean_word_length': 4.226712328767123, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Algorithm to Decompose Permutation Representations of Finite Groups: Polynomial Algebra Approach

We describe an algorithm for splitting a permutation representation of a finite group into irreducible components. 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 element of the algorithm is the calculation of Gr\"obner bases of polynomial ideals. A preliminary implementation of the algorithm splits representations up to dimensions of several thousand. Some examples of computations are given in appendix.


Introduction
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 [1]. We consider here a particular, but important from our point of view [2], case of the problem.
Let G be a permutation group on the set Ω ∼ = {1, . . . , N}. We will denote the action of g ∈ G on i ∈ Ω by i g . To avoid inessential technical complications, we assume that G acts transitively on Ω.
A representation of G in an N-dimensional vector space over a field F by the matrices P(g) with the entries P(g) ij = δ i g j , where δ ij is the Kronecker delta, will be called a permutation representation. Our approach uses the concept of inner product, so we have to exclude vector spaces over finite fields -there are no reasonable inner products for such spaces. Thus, we assume that the permutation representation space is a Hilbert space H N . From a constructive point of view it is sufficient to assume that the base field F is a minimal splitting field of the group G. Such field is a subfield of an m-th cyclotomic field, where m is a certain divisor of the exponent of the group G. The field F , being an abelian extension of the field Q, is a constructive dense subfield of R or C.
An orbit of G on the Cartesian square Ω × Ω is called an orbital [3]. The number of orbitals, called the rank of G, will be denoted by R. Among the orbitals of a transitive group there is one diagonal orbital, ∆ 1 = {(i, i) | i ∈ Ω}, which will always be fixed as the first element in the list of orbitals: {∆ 1 , . . . , ∆ R }. For transitive G there is a natural one-to-one correspondence between the orbitals of G and the orbits of a point stabilizer The G i -orbits are called suborbits and their cardinalities will be called the suborbit lengths.
The invariance condition for a bilinear form A in the Hilbert space H N can be written as the system of equations A = P(g) AP(g −1 ) , g ∈ G. It is easy to verify that in terms of the entries the equations of this system have the form (A) ij = (A) i g j g . Thus, the basis of all invariant bilinear forms is in one-to-one correspondence with the set of orbitals: with each orbital ∆ r ∈ {∆ 1 , . . . , ∆ R } is associated a basis matrix A r of the size N × N with the entries In particular, for the diagonal orbital we have A 1 = 1 N . The matrices form a basis of the centralizer algebra of the representation P. The multiplication table for this basis has the form where C r pq are non-negative integers. The commutativity of the centralizer algebra indicates that the permutation representation P is multiplicity-free.

Algorithm
Let T be a transformation (we can assume that T is a unitary matrix) that splits the permutation representation P into M irreducible components: where U dm is a d m -dimensional irreducible subrepresentation, ⊕ denotes the direct sum of matrices, i.e., A ⊕ B = diag(A, B).
The identity matrix 1 N 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 where B m is defined by the relation The main idea of the algorithm is based on the fact that B m is a projector, i.e., B 2 m = B m . Thus, all B m 's can be obtained as solutions of the equation for the generic invariant form Using the multiplication table (2), we can write the left-hand side of (4) as a set of polynomials and equation (4) takes the form (This is an abbreviation for the set of equations In the basis (1) the projector B m can be represented as where the vector is a solution of equation (6). Since only A 1 has nonzero diagonal elements, we have On the other hand, relation (3) shows that This allows us to fix the coefficient b m,1 : we can exclude the consideration of dimensions that are sums of irreducible ones. The main part of our algorithm is a loop over the possible dimensions d. The loop starts with d = 1 and ends when the sum of irreducible dimensions becomes equal to N. The current d is processed as follows: 1. Substitute d into the set of polynomials: Here m is the number of irreducible components constructed before. Apply the procedure ProcessSingleSolution (described below) to all solutions in (7).
6. If Hd > 0 then we encounter an irreducible component with a multiplicity k > 1. The corresponding component of the centralizer algebra has the form A ⊗ 1 d , where A is an arbitrary k × k matrix, and ⊗ denotes the Kronecker product. The idempotency The complete family of solutions 2 of (8) is a manifold of dimension ⌊k 2 /2⌋ = Hd. Application of Gröbner basis technique for polynomial systems with parameters involves the cumbersome procedure of partitioning the parameter space. To avoid these difficulties, we construct k mutually orthogonal particular solutions of the form (7) and apply to each of them the procedure ProcessSingleSolution.
The input of procedure ProcessSingleSolution is the current irreducible projector B m . The procedure performs the following. 2. Add the orthogonality relations to the idempotency polynomial set (5) This is done in order to exclude from further consideration the subspace of the projector B m .

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 the developed tools for working with polynomials. Our current implementation is a program written in C. The input data for the program is a set of permutations S = {s 1 , . . . , s K } of degree N that generates the group G.
The program 1. computes the basis of the centralizer algebra (1) and its multiplication table (2) 4. generates the code for processing the above constructed polynomial data by the computer algebra system Maple.

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 of low-degree polynomials. As can be seen in Appendix A even a straightforward implementation of the approach can cope with rather large tasks. There are the obvious ways to improve performance: (1) to write in C Gröbner bases algorithms specialized for the problem under consideration, (2) to use a more efficient system of computer algebra, for example, Magma.
Comments. Generators of representations are taken from the Atlas [4].
The results presented below assume the following ordering for the centralizer algebra basis matrices The matrices within the first sublist are ordered by the rule: All timing data were obtained on a PC with 3.30GHz Intel Core i3 2120 CPU.

A.1 462-dimensional representations of M 22
There are three 462-dimensional permutation representations of M 22 , which are distinguished by the letters a, b, c in the Atlas [4].