Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that you are given two finite groups, for example, via their Cayley tables.

One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this is a result of Babai and Rònyai from 1990.

It is well-known that the character table does not determine the group (e.g. $Q_8$ and $D_4$ are non-isomorphic groups with the same character table), nevertheless, I am interested in the following:

Question: Is there an efficient way to check whether two character tables are the same?

share|improve this question
My memory, from conversations with people who compute character tables, is that this is regarded as a potentially difficult problem. –  Derek Holt Jun 23 '13 at 18:27
@DerekHolt, I suspect that that this is indeed the situation. Can you be more specific though, when is this problem hard? are there families for which there is a polynomial time algorithm to check this? –  DKal Jun 23 '13 at 19:40
I don't know of any specific results in this direction. It will clearly only be hard if there are large numbers of characters having the same degrees, or large numbers of conjugacy classes of the same size. –  Derek Holt Jun 24 '13 at 19:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.