12
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 at 15:52

1 Answer 1

Reset to default
11
$\begingroup$

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 .

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is very interesting. The value for $c$ is surprisingly small! $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Dec 17, 2015 at 12:56

You must log in to answer this question.

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