[GAP Forum] functions work wih conjugacy class

[Thomas Breuer]

Dear GAP Forum,

Azhvan Sanna had recently sent several messages concerning computations
with characters of sporadic simple groups in GAP.
The latest of these messages (appended below) describes the background,
which is roughly the following.

- The *aim* is to compute, for any sporadic simple group G and a three-element
  generating set X for G, the eigenvalues of the associated Cayley graph.

- The first *idea* is that we may split the regular representation of G into
  the direct sum of its \chi-homogeneous components,
  for the irreducible characters \chi of G,
  and thus it suffices to compute the eigenvalues of the smaller matrices.
  (Note that the adjacency matrix of the Cayley graph is the sum of the images
  of the generators in X under the regular representation of G.)

- The *approach* is then to observe that the sum of the i-th powers of the
  eigenvalues of the submatrix for the character \chi equals the value of
  \chi at the group algebra element ( \sum_{x \in X} )^i.
  If one knows these values for i up to \chi(1) then one can compute the
  eigenvalues themselves.
  For computing the desired character value, one may expand the i-th power
  of the sum over X as the sum of all ordered i-tuples over X,
  compute the character values of all summands and them sum them up.

This works for small groups,
but runs forever if the character degree is not very small.
For example, consider the sporadic simple Janko group J_1.
Its smallest nontrivial character degree is 56.
For |X| = 3 and i = 56, one gets 3^56 summands, which is more than 10^26.
So this approach is not feasible,
and Azhvan's question for a better way of computing the character value
is reasonable.

Concerning this question,
one can say at least that with purely character-theoretic methods,
in general one cannot compute the distribution of the summands to conjugacy
classes of G.
This follows from the fact that this distribution depends on the choice of
the generators inside their conjugacy class;
so it is impossible to avoid computations with group elements.

(The situation would be different if the generating set X would be a
conjugacy class of G.  In this situation, the powers of the sum over X
is a linear combination of class sums, which can be described in terms of
character values.
As a rule of thumb, if a problem is not invariant under conjugacy then
it is not likely that purely character-theoretic methods can solve it.)

Besides the problem to compute the character values in question,
I think that also the computation of the eigenvalues from the \chi(1)
polynomial equations is not ``pretty simple'',
because one has to consider character degrees \chi(1) of magnitude at least
the square root of |G|, divided by the number of conjugacy classes of G.
So the sketched approach really works for simple groups only if they are
small.

All the best,
Thomas

P.S.:
The computation of \chi( ( \sum_{x \in X} )^i ) can be performed easily
if a *representation* affording \chi is known.
Namely, one can evaluate the generators in this representation,
add the resulting matrices, raise this matrix to the i-th power,
and then take the trace.
For the Janko group J_1 mentioned above, the rational irreducible
representations are available in the Atlas of Group Representations,
for example via the GAP package AtlasRep,
so the first step of the sketched approach can be done for J_1.


> This was my unsolved question: 
> I want to calculate all eigenvalues of cubic cayley graphs associate
> with sporadic simple group. So if G denote one of 26 sporadic simple
> group, and X a set of generators with 3 elements, one "a" of order 2,
> and the other "b" and "b^-1" of order greater than 2. then Cay(G,X) is
> a cubic Cayley graph. and by a well-know formula for computing
> eigenvalues of cayley graphs, we have: for each
> 
> "Xi" in Irr(G)
> of degree n, we have n eigenvalues L_1, L_2,...,L_n each of them has
> multiplicity n ( so in total this character "Xi" of
> 
> degree n gives us "n^2" eigenvalues of our graph). and we can compute them by Newton-Waring identities and following fact that 
> 
> for t from 1 to n we have (L_1)^t + (L_2)^t + ... +(L_n)^t =  Sum {Xi (x_1.x_2....x_t)} where sum is over the value of "Xi" on 
> 
> the all product of t elemnts from our generator set X.
> 
> Using
> this I will find a polynomial of degree n and roots give me the
> eigenvalues, instead of determaining the characterestic polynomial of a
> matrix of order |G| which for sporadic simple group this number is huge
> and also finding their roots!
> 
> As you see, I need to calculate
> this for every character in Irr(G), and evalute them in all t-product
> of  elements of generator set.
> 
> I know this will involve lots of calculation as  mentioned it to me by Thomas Breuer. Because of the special case  here, I am just having a generator set of 3 elements, I would like to know is it any function to calculate for generator "a" and "b"  and conjugacy class "C" the number "n_{t,C}(a,b)" which calculates the number of t-products( products of length t of a,a^-1, b, b^-1) of a and b which belongs to the Conjugacy class "C" for t runs from 1 to max{ deg(Xi) | "Xi" runs over Irr(G)}?
> Because after this point most of calculations above are pretty simple.