8
$\begingroup$

Let $G \leq {\rm S}_n$ be a finite permutation group, and let $S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed under inversion and which does not contain the identity. The growth function of $G$ with respect to $S$ is the sequence $(a_0, a_1, a_2, \dots)$, where $a_r$ is the number of elements of $G$ which can be written as products of $r$, but no fewer, generators $g_i$. The diameter of $G$ with respect to $S$ is the largest $r$ such that $a_r > 0$.

Question: How hard is it to compute the diameter and the growth function of a given permutation group $G$ of degree $n$? Or more specifically: using current computer technology, is it feasible to do this for any given group $G$ of degree $n \leq 100$ and any given sufficiently small generating set $S$?

The motivation for this question is that while the Schreier-Sims algorithm allows e.g. to compute the order of such groups and to perform element tests instantaneously, even only computing the diameter of the Rubik's Cube Group with respect to its natural generating set was a major effort -- and its growth function is apparently not known in full so far.

My feeling goes in the direction that one can do essentially better, i.e. that it should be possible to find an algorithm for computing diameter and growth function which is by orders of magnitude more efficient than enumerating group elements by brute force. However maybe I am wrong, and somebody can point out reasons why these problems cannot be solved efficiently?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

I just came across this question and, even though I'm a bit late, I thought you might be interested in this reference:

Even, S.; Goldreich, O., The minimum-length generator sequence problem is NP-hard, J. Algorithms 2, 311-313 (1981). ZBL0467.68046.

This asserts that the calculation of the diameter of a Cayley graph of a permutation group is NP-Hard. I don't have access to the article myself but, from what I've read elsewhere, I believe this statement remains true even if you restrict to elementary-abelian 2-groups. (Which seems astonishing to me!)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Perhaps this is not so surprising. There is an old conjecture of Pyber, which a number of people are hoping to settle soon, that the total number of subgroups of $S_n$ is $2^{n^2/16 + o(1)}$, and this is also an upper bound for the number of elementary abelian $2$-subgroups. So this does not quite say that almost all subgroups of $S_n$ are elementary abelian $2$-groups, but it gets close to that. $\endgroup$
    – Derek Holt
    Commented Jan 8, 2019 at 11:47
  • $\begingroup$ @DerekHolt, ah, thanks, that is interesting. $\endgroup$
    – Nick Gill
    Commented Jan 8, 2019 at 11:55
  • $\begingroup$ I should have said that $2^{n^2/16 + o(1)}$ is a lower bound rather than an upper bound for the number of elementary abelian $2$-subgroups of $S_n$ - that estimate is elementary. $\endgroup$
    – Derek Holt
    Commented Jan 8, 2019 at 12:12
3
$\begingroup$

This seems quite difficult, for an example of results (and an indication of the difficulty) see Ganesan's 2011 paper.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the reference. -- Though I don't see that the paper answers the question. The author derives bounds on the diameter of certain Cayley graphs, shows that they are sharp and says that the naive way to evaluate the bounds takes $n!$ times a polynomial operations. Though I have not read everything in full. $\endgroup$
    – Stefan Kohl ♦
    Commented Aug 15, 2013 at 9:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .