3

I want to ask how does GAP calculate the irreps? I guess the answer is that GAP realizes groups as permutation groups (or sometimes linear groups), then there is some efficient algorithm for permutation groups.

Does such an algorithm exist? If so, what is the algorithm called? What is the asymptotic behavior of the complexity. Does it work if we replace $\mathbb{C}$ with a finite field of characteristic dividing the group order (I assume it can, because GAP can calculate modular characters as well, but is it the same algorithm?)

(It took me 30 seconds to compute the character table of a group of order $24200$.)

FunctionOfX
  • 960
  • 1
    Please explain more clearly what input you supply for the calculation, as well as what output is required. – hardmath Jun 27 '17 at 15:36
  • Well, my input is just a group, and I want a character table as an output. – FunctionOfX Jun 27 '17 at 16:09
  • How would I input a group into GAP? – hardmath Jun 27 '17 at 16:22
  • The method may depend on the input, so I support the suggestion by @hardmath. See also https://math.stackexchange.com/questions/947945/finding-code-of-a-function-in-gap-packages/954537#954537 and links there. – Olexandr Konovalov Jun 27 '17 at 17:19
  • I would add that GAP is open source software, so that we can in principle discover the algorithm behind any particular function calls there. – hardmath Jun 27 '17 at 17:26
  • 1
    I think the answer to this question is much too complicated for this forum. You could write a book on the topic. But the methods used for finite fields are generally different from characteristic $0$. Over ${\mathbb C}$ you would generally start from the character table. But over finite fields, you would be more likely to calculate the represenations directly using the algorithm popularly known as the MeatAxe. – Derek Holt Jun 27 '17 at 19:06

1 Answers1

9

Assuming you have a finite group and you ask for the calculation of irreducible characters over $\mathbb C$, GAP will as default method use the Dixon-Schneider algorithm: [MR1075426, Schneider, Gerhard J. A. Dixon's character table algorithm revisited. J. Symbolic Comput. 9 (1990), no. 5-6, 601–606.] (If the group is nilpotent the Baum/Clausen algorithm is used.)

This is inherently a method in the space of class functions without constructing actual representations.

As for asymptotic behavior, the runtime for all algorithms for ordinary character tables that I am aware of is dominated by the identification of conjugacy classes in which given elements lie. The cost of this depends very much on the group (e.g. it is trivial in the full symmetric group). While it behaves well in practice it often builds fundamentally on a backtrack search that scales exponential in e.g. the permutation degree.

(The second most expensive task then is linear algebra in the space of class functions.)

For modular characters the methods are very different and (as Derek Holt wrote) much harder -- in general it is necessary to construct the actual representations first.

ahulpke
  • 18,416
  • 1
  • 21
  • 38