Skip to main content
fixed a typo and added half a sentence of explanation
Source Link

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 $d(G)\log |G|\geq \frac{\log 2}{4n^2}$$\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.

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 $d(G)\log |G|\geq \frac{\log 2}{4n^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.

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.

edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 285
Source Link

Can a large transitive permutation group need many generators?

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 $d(G)\log |G|\geq \frac{\log 2}{4n^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.