Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to classify groups G such that G is a finite group of permutations, acting on the set {1,2,...,n} and for each $A\subseteq \lbrace 1,2,\ldots,n\rbrace$, the stabilizer $G_0\subset G$ of $A$ acts transitively on $A$. Can you say "something"? First I thought that G has to be at least the whole alternating group $A_n$, but then I checked that for example the image of the exotic embedding of $S_5$ into $S_6$ has this property as well.. Thanks, Peter

share|improve this question
1  
Looks like $G$ must be transitive on the subsets of size $k$, for any $k \le n$. I imagine such groups have been classified, but can't think of a reference off the top of my head. –  Colin Reid Aug 2 '11 at 18:06
    
Done :-) –  Peter Franek Jun 4 '12 at 12:08

2 Answers 2

up vote 9 down vote accepted

Let $A$ denote the set of all integers except $i$. Since $G_A$ is transitive, it follows that there exists an element $\sigma \in G$ that fixes $i$ and sends any fixed $j \ne i$ to some $k \ne i$. From this one quickly deduces that $G$ is $2$-transitive, and hence primitive.

Choose a prime $p$ such that $n-3 \ge p > n/2$ (by a modification of Chebyshev's proof of Bertrand's postulate, this is true whenever $n \ge 8$). Let $B = \{1,2, \ldots, p\}$. Since the stabilizer $G_B \subset G$ of $B$ acts transitively on $B$, by the orbit-stabilizer theorem, $G_B$ (and hence $G$) has an element of order $p$. Since $n-p < p$, it follows that $G$ contains a $p$-cycle. But a well known theorem of Jordan says that any primitive permutation group containing a $p$ cycle for $p \le n-3$ is the symmetric or alternating group.

This leaves $n \le 7$. Note that since $G_A$ acts transitively for any $A$, it follows that $|G|$ is divisible by $|A|$.

For $n = 1$, $2$, and $3$, $G$ has to be $S_n$ (easy). For $n = 4$ and $5$, $|G|$ must be divisible by $12$ and $60$ respectively. So $G = A_n$ or $S_n$ in these cases. Yet both $A_n$ and $S_n$ satisfy the defining condition when $n \ge 4$. For $n = 7$, $|G|$ must be divisible by $420$. The only primitive subgroups of $S_7$ with order divisible by $420$ are $A_7$ and $S_7$. This leaves $n = 6$, where $|G|$ is divisible by $60$. It follows that $G$ could possibly be $A_5$, $S_5$, $A_6$, or $S_6$. The latter two groups work. The group $S_5$ with its natural embedding (stabilizing one point) does not work, because it does not act transitively on the full set $\{1,2,\ldots,6\}$. The same remark applies to the standard embedding of $A_5$. It suffices, then, to check the exotic actions of $A_5$ and $S_5$. Here is a "computation free" argument.

This exotic action of $S_5$ on $6$ points is realized by the action of $\mathrm{PGL}_2(\mathbf{F}_5)$ on the projective line over $\mathbf{F}_5$. The action of $\mathrm{PGL}_2(\mathbf{F}_5)$ is sharply $3$-transitive, and the action of $A_5 = \mathrm{PSL}_2(\mathbf{F}_5)$ is $2$-transitive. It follows that both groups satisfy the conditions for $|A| = 1$ and $|A| = 2$. The first group satisfies the condition for $|A| = 3$ since it is $3$-transitive. Suppose that $|A| = 5$. Then we may assume by transitivity that $A = \mathbf{F}_5 = \mathbf{P}^1(\mathbf{F}_5) \setminus \{\infty\}$. Both groups act transitively on this set via the element $z \mapsto z + 1$. Finally, let $|A| = 4$. Since both groups are $2$-transitive, we may assume that $A = \mathbf{F}^{\times}_5 = \mathbf{P}^1(\mathbf{F}_5) \setminus \{0,\infty\}$. The subgroup of elements of $\mathrm{PGL}_2(\mathbf{F}_5)$ which fix $0$ and $\infty$ are of the form $z \mapsto a z$ for $a \in \mathbf{F}^{\times}_5$, which acts transitively. The set of elements of $\mathrm{PGL}_2(\mathbf{F}_5)$ which send $0$ to $\infty$ and $\infty$ to $0$ are of the form $z \mapsto a/z$ for $a \in \mathbf{F}^{\times}_5$. Yet the corresponding elements in $\mathrm{PSL}_2(\mathbf{F}_5)$ are of the form $z \mapsto a^2 z$ and $z \mapsto a^2/z$, which does not act transitively since it only sends quadratic residues to quadratic residues. Thus the complete list of such groups is:

(i) $G = S_n$ for $n \le 3$.

(ii) $G = A_n$, $S_n$ for $n \ge 4$.

(iii) $G = \mathrm{PGL}_2(\mathbf{F}_5) = S_5$ when $n = 6$.

share|improve this answer
    
Thank you very much, great! I am suprised that the $S_5\subset S_6$ is the "only exception". Peter –  Peter Franek Aug 3 '11 at 7:54
    
Dear Jordan, thanks again for your solution. Meanwhile, I've written a paper in game theory where I use your result. I would be pleased if you would agree to be a coauthor (otherwise, I will cite mathoverflow). However, I couldn't find any contact to you. Could you write me please to peter.franek at gmail? Best regards! Peter –  Peter Franek Apr 11 '12 at 16:21

I found the following article online which I think essentially answers your question (following on from my comment):

http://deepblue.lib.umich.edu/handle/2027.42/46299

share|improve this answer
    
Thanks! Peter .. –  Peter Franek Aug 3 '11 at 8:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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