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?

  • $\begingroup$ My memory, from conversations with people who compute character tables, is that this is regarded as a potentially difficult problem. $\endgroup$ – Derek Holt Jun 23 '13 at 18:27
  • $\begingroup$ @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? $\endgroup$ – DKal Jun 23 '13 at 19:40
  • $\begingroup$ 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. $\endgroup$ – Derek Holt Jun 24 '13 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.