8
$\begingroup$

Background. Mazorchuk and I were interested in computing the minimum faithful degree of a linear representation of a finite semigroup over the complex feld in this paper. One particular aspect we considered was algorithmic. The algorithm we present is as follows:

  • Since the minimum faithful degree of $S$ is at most $|S|$ it suffices to check for each $d< |S|$ whether $S$ has a faithful representation of degree $d$.
  • The statement "$S$ has a faithful representation of degree $d$" belongs to the first order (in fact existential) theory of $\mathbb C$.
  • The existential theory of $\mathbb C$ is decidable.

    • The existensial theory of $\mathbb C$ is known to lie between NP and PSPACE and if GRH is true the upper bound is closer to NP.

    I don't have any idea of another approach for semigroups, but for groups one has the following alternative approach.

  • A minimum degree faithful representation is multiplicity-free.
  • The kernel of a representation is the intersection of the kernels of its irreducible constituents.
  • The kernel of an irreducible representation can be read off the character table.
  • The character table is computable.

    • So one can compute all dimensions and kernels of multiplicity-free reps to find a winner. I have no idea on the complexity of computing the character table or of the remainder of the algorithm given the table.

    Question.

      (a) Which of the above algorithms for computing the minimum faithful degree of a group is more efficient?
      (b) What is the time complexity of computing the minimum faithful degree of a finite group?

    Let us assume that groups are given by their multiplication table.

    Improve this question
    $\endgroup$
    7
    • 2
      $\begingroup$ You can find the character table in polynomial time, according to mathoverflow.net/questions/45560/… $\endgroup$
      – Mariano Suárez-Álvarez
      Commented Jan 18, 2012 at 7:12
    • 1
      $\begingroup$ (Once you have the character table you need to solve an instance of the minimal set cover problem, though, which is NP-hard; the size of the input is the number of conjugacy classes, which is much smaller than the size of the group, so this might not be enough to ruin the P-ness of the computating of the table) $\endgroup$
      – Mariano Suárez-Álvarez
      Commented Jan 18, 2012 at 7:29
    • $\begingroup$ Are there useful bounds for the quotient (minimum faithful degree)/$|G|$? $\endgroup$
      – Mariano Suárez-Álvarez
      Commented Jan 18, 2012 at 7:38
    • $\begingroup$ @Mariano, thanks for the comments. I assumed getting the character table was fast since GAP does it well but still I have no idea how quickly one can find the cover. For abelian groups one can trivially find the minimum faithful degree, it is the minimal number of generators which has been discussed on MO before. In general the number of conjugacy classes can be 1/4 the size of the group, although usually it is smaller. $\endgroup$
      – Benjamin Steinberg
      Commented Jan 18, 2012 at 14:21
    • 2
      $\begingroup$ The problem of finding the minimal degree faithful permutation representation of a finite group presents similar difficulties. For practical purposes, you might be content with a reasonably low degree solution, but it can be hard to prove that your solution is actually minimal. What would be interesting would be to find (families of) examples in which your problem seemed to be hard. $\endgroup$
      – Derek Holt
      Commented Jan 18, 2012 at 21:01

    0

    Reset to default

    You must log in to answer this question.

    Browse other questions tagged .