let $G$ be a transitive permutation group acting on $\{1, \ldots, n\}$, and let $d(G)$ be the minimal number of generators of $G$. Is it true, that for $n\rightarrow\infty$ we have $\frac{d(G)\log|G|}{n^2}\rightarrow 0$? If this is true, can you give a complete list of groups with $\frac{d(G)\log |G|}{n^2}\geq \frac{\log 2}{4}$, i.e. groups which are "worse" than $C_2$?

I believe the answer to the first question is yes, because a transitive group on $n$ letters needs $\mathcal{O}(\frac{n}{\sqrt{\log n}})$ generators, thus if $\frac{d(G)\log|G|}{n^2}$ is large, then $|G|>e^{cn\sqrt{\log n}}$. But then $G$ must involve quite large alternating or symmetric sections, which should imply that $G$ is actually quite easy to generate. I guess that the answer to the second question involves only subgroups of $S_4$, although I am not too certain about that.

  • $\begingroup$ It looks as though such a large $G$ would be imprimitive with a few explicit exceptions ( check out results of A. Maroti for example). In that case, one should much better bounds for $d(G)$. $\endgroup$ – Geoff Robinson Dec 16 '15 at 14:36
  • $\begingroup$ @GeoffRobinson I don't completely understand your comment. For primitive permutation groups there is a bound $d(G) = O(\log n)$ so they would not cause problems. The transitive groups known to have the largest $d(G)$ are imprimitive $2$-groups derived from submodules of the permutation module over ${\mathbb F}_2$ for an elementary abelian $2$-group. Of course such groups have a simple exponential bound on their orders, which would be sufficient in this context. $\endgroup$ – Derek Holt Dec 16 '15 at 14:50
  • $\begingroup$ @DerekHolt : I was just thinking that, with very few exceptions, a primitive subgroup of $S_{n}$ would have order less than $e^{cn\sqrt{\log{n}}}$, (it could be doubly transitive, but doubly transitive groups are not a problem here, I think). The OP has reduced to groups this large. As you say, imprimitive groups are manageable. $\endgroup$ – Geoff Robinson Dec 16 '15 at 14:59
  • $\begingroup$ I think Praeger and Saxl proved (without using CFSG) that all primitive groups except for $A_n$ and $S_n$ have order at most $4^n$. But I don't think the problem here is completely straightforward, because you have to handle imprimitive groups with intermediate sized blocks and an alternating group acting on the blocks. $\endgroup$ – Derek Holt Dec 16 '15 at 15:26
  • $\begingroup$ I believe the problem is that a subgroup of a wreath product might behave quite differently from the whole wreath product. I tried to bound the number of generators by retricting the action to one domain of imprimitivity, take generators there, and look at the resulting stabilizers, but ended up in a mess. A possibly easier question would be: If $H\leq G\wr S_k$ projects onto $S_k$ or $A_k$, can you bound $d(H)$ in terms of $d(G)$, is it e.g. true that $d(H)\leq 2d(G)+2$? $\endgroup$ – Jan-Christoph Schlage-Puchta Dec 16 '15 at 15:52

Let $G$ be a permutation group of degree n, and let $r>1$ be the minimal block size of $G$. Also, let $s:=n/r$, so that G may be viewed as a subgroup in the wreath product $R\wr S$, where $R\le Sym(r)$ is primitive, and $S=\pi(G)\le Sym(s)$ is transitive ($\pi$ here denotes projection $G\rightarrow Sym(s)$). Then $$d(G)\le \frac{a(R)bs}{\sqrt{\log_{2}{s}}}+d(S) \text{ ($\ast\ast$})$$ where b is an absolute constant, and $a(R)$ denotes the composition length of R. By a result of Pyber and Guralnick, $a(R) \le C\log_{2}(r)$ for an absolute constant $C$. Also, as you mentioned, $d(S)\le cs/\sqrt{\log_{2}{s}}$, for an absolute constant c. (For information on the constants $b,c$, and $C$, and on the bound at ($\ast\ast$), see http://arxiv.org/abs/1504.07506 .)

Now, we also have $\log{|G|}\le \log{|R\wr S|}\le rs\log{r}+s\log{s}$. This means that your first claim follows when $r>\sqrt{\log{s}}$, for example. Thus, it only remains to deal with the case $r\le \sqrt{\log{s}}$.

As you said, the key seems to be reducing the upper bounds when S is either $Alt(s)$ or $Sym(s)$. However, I think that a bound of the form $d(G)\le c'd(R)+2$ would be difficult to prove in this case, and is probably not true. For example, when $R=C_2$ and $K$ is the intersection of $G$ with the base group of the wreath product, then the number of generators for $K$ as an $S$-group can grow as $bs/\sqrt{\log{s}}$, where b is as above (see Section 3.1 of the paper I mentioned above).

EDIT: @Jan-Christoph Schlage-Puchta The first part of your question, that is, that for a transitive permutation group of degree $n$, $\frac{d(G)\log{|G|}}{n^{2}}$ tends to $0$ as $n$ tends to $\infty$, has now been proved in http://arxiv.org/abs/1601.02561 .

  • $\begingroup$ This is very interesting. The value for $c$ is surprisingly small! $\endgroup$ – Jan-Christoph Schlage-Puchta Dec 17 '15 at 12:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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