2
$\begingroup$

For a finite group $G$, let $\mu(G)$ be the least positive integer $n$ such that $G$ is embedded as a subgroup of the symmetric group on $n$ points. In other words, $\mu(G)$ is the minimal permutation representation degree of $G$.

Note here that $\mu(G)$ is the minimum of $\sum_{i=1}^t |G:H_i|$ over all sets of subgroups $H_1, H_2, \ldots, H_t$ such that $\bigcap_{i=1}^t\mathrm{Core}_G(H_i) = 1$, which is equivalent to $\mathrm{Core}_G(K) = 1$, $K = \bigcap_{i=1}^tH_i$.

My question concerns finding $\mu(G)$ with GAP. There is some functionality available to do this, which is, however, not guaranteed to succeed. Below is a naive routine of mine which makes use of this limited functionality of GAP:

mprd:=function(g)
 local iso,image,small;
  iso:=IsomorphismPermGroup(g);;
  image:=Image(iso);;
  small:=SmallerDegreePermutationRepresentation(image);;
   return NrMovedPoints(Image(small));;
end;;

Asking for mprd(d8), where d8:=DihedralGroup(8);; returns a value of 8, whereas the actual value is 4.

My question is twofold:

  1. When is the above mprd routine guaranteed to succeed finding the correct value of $\mu(G)$? In other words, when is SmallerDegreePermutationRepresentation actually smallest?
  2. What is the fastest way to find the true value of $\mu(G)$ with GAP using just the observation above that it is the minimum of $\sum_{i=1}^t |G:H_i|$ ?

To elaborate a little on the first question. An early paper of Johnson has theoretical arguments to find $\mu(G)$ for certain classes of groups (abelian groups, direct products of groups of coprime orders). Have these arguments been taken into account in the implementation of SmallerDegreePermutationRepresentation?

$\endgroup$
3
+50
$\begingroup$

SmallerDegreePermutationRepresentation aims to find, at limited cost, an isomorphic group in which subsequent calculations will be faster. It is purely a heuristic which, however, can have significant influence on the user experience. The typical case of use is that a prior calculation gave a group in a permutation representation that is far too large -- say you take $M_{12}$ as a subgroup of $\operatorname{Aut}(M_{12})$ which would be double the degree, though absolute numbers are small in this example.

It of course uses some subgroups -- the point stabilizers -- but makes absolutely no attempt to prove minimality of the degree obtained. It also cares more to reduce 100000 to 5000 than to reduce 1017 to 1015, the latter being not really a practical difference.

So the only cases in which I reckon the degree would be minimal are ``obvious'' cases -- cyclic groups of prime power orders, or elementary abelian groups.

The heuristics in SmallerDegreePermutationRepresentation do not use the arguments of the paper you cite (or others) as in general the groups encountered will be unlikely to lie in these particular classes, respectively we do not want to test for these particular cases as we want to minimize the number of calculations in the larger degree permutation group.

If you really want the true value of $\mu$ in arbitrary cases, I suspect you cannot do better in general than to consider all possible collections of subgroups, ordered by sum of the degrees. For that you would have to calculate at least part of the subgroup lattice, though you could start iteratively with maximal subgroups, or factors in a subdirect product decomposition. (The next release of GAP will have a function LowLayerSubgroup that determines subgroups that are $k$-fold maximal for small $k$.) Doing this properly for arbitrary groups is on the level of a decent research article.

PS: If you are a glutton for punishment -- i.e willing to read in German -- you can find a textual description of an early version of the code underlying the routine in section V.2 of my thesis at http://www.math.colostate.edu/~hulpke/paper/prom.ps.gz )

$\endgroup$
  • $\begingroup$ I wonder if it might be beneficial to determine first a "good" range for $\mu(G)$, i.e. $a,b \in \mathbb{N}$ such that $a \leq \mu(G) \leq b$, where $b-a$ is "small". It is possible to find such bounds for $a,b$ "theoretically" (see MR1213975). Maybe it is then easier to pin down the exact value of $\mu(G)$. $\endgroup$ – the_fox Jan 20 '18 at 14:14
  • $\begingroup$ @the_fox If you want to implement a separat function for $\mu$ (which would not be the goal of the SmallerDegree... function) then yes, having some bounds would help. However the bounds you cite are not very tight and require information that is too costly to compute for SmallerDegree... $\endgroup$ – ahulpke Jan 20 '18 at 16:39
  • $\begingroup$ It's not clear to me though: how might one iterate over all subgroups to get the minimum? Even a naive routine would be welcomed. $\endgroup$ – the_fox Jan 28 '18 at 14:25
  • $\begingroup$ @the_fox You store minimal degrees for each factor and then iterate through subgroups, updating degrees of their cores. I have put a quick and dirty implementation at dropbox.com/s/9on2yj0fhxnzave/valuemue.g?dl=0 Let me know if it doesn't behave or you spot bugs. $\endgroup$ – ahulpke Jan 28 '18 at 23:31
  • 1
    $\begingroup$ @the_fox Thanks for pointing this out -- there was a stupid error left that I just fixed. If you encounter other problems, please email me directly, as I think the comments section is not a god place for this. $\endgroup$ – ahulpke Feb 6 '18 at 14:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.