Simplicity of the projective special linear groups

Theorem If $n \ge 2$ then $PSL_n(q)$ is simple provided $(n,q)$ is not $(2,2)$ or $(2,3)$.
proof: Consider $PSL_n(q)$ acting on $\mathbb P^{n-1}(q)$ for $n \ge 2$ and the exceptions do not occur, then it is primitive since it's 2-transitive and by previous results $SL_n(q)$ is perfect, so since $PSL_n(q)$ is a quotient of that it's perfect too. Take $d \in V^\#$ so that $[d] \in \mathbb P^{n-1}(q)$ let $A$ be the image of $\mathscr T(d)$ in $PSL_n(q)$ applying [???] and taking quotients we see that $A$ is a normal abelian subgroup of the stabilizer $PSL_n(q)_{[d]}$ and it's conjugates generate $PSL_n(q)$ thus the conditions of Iwasawa's lemma are satisfied.

M11

Let $\Delta = \{\delta_1, \delta_2, \delta_3, \delta_4, \delta_5\}$ and let $\Omega$ be the unordered pairs of these. We will use the names:

• 0: $\{\delta_1,\delta_2\}$,  1: $\{\delta_1,\delta_3\}$,  2: $\{\delta_1,\delta_4\}$
• 3: $\{\delta_1,\delta_5\}$,  4: $\{\delta_2,\delta_3\}$,  5: $\{\delta_2,\delta_4\}$
• 6: $\{\delta_2,\delta_5\}$,  7: $\{\delta_3,\delta_4\}$,  8: $\{\delta_3,\delta_5\}$
• 9: $\{\delta_4,\delta_5\}$

Let $G = A_\Delta$ (basically $A_5$) this acts transitively on $\Omega$!

• $a = (\delta_1\;\delta_2)(\delta_3\;\delta_5) = (1\;6)(2\;5)(3\;4)(7\;9)$
• $b = (\delta_1\;\delta_2)(\delta_4\;\delta_5) = (1\;4)(2\;6)(3\;5)(7\;8)$
• $g_2 = (\delta_2\;\delta_3)(\delta_4\;\delta_5) = (0\;1)(2\;3)(5\;8)(6\;7)$
• $g_3 = (\delta_1\;\delta_4)(\delta_2\;\delta_3) = (0\;7)(1\;5)(3\;9)(6\;8)$

you can clearly combine these to take 1 anywhere, which proves transitivity.

The stabilizer of 0 has size $|G_0| = |G|/|\Omega| = 60/10 = 6$ (orbit stabilizer) so $G_0 = \langle a, b \rangle = \{1,a,b,ab,ba,aba=bab\}$ and the $G_0$ orbits are:

• $\{0\}$
• $\{1,2,3,4,5,6\}$
• $\{7,8,9\}$

the double cosets corresponding to these suborbits are represented by $1,g_2$ and $g_3$.

gap> a:=(1,2)(3,5);;b:=(1,2)(4,5);;
gap> DoubleCosets(Group((1,2,3,4,5),(1,2,3)),Group(a,b),Group(a,b));
[ DoubleCoset(Group( [ (1,2)(3,5), (1,2)(4,5) ] ),(),Group( 
    [ (1,2)(3,5), (1,2)(4,5) ] )), 
  DoubleCoset(Group( [ (1,2)(3,5), (1,2)(4,5) ] ),(2,3)(4,5),Group( 
    [ (1,2)(3,5), (1,2)(4,5) ] )), 
  DoubleCoset(Group( [ (1,2)(3,5), (1,2)(4,5) ] ),(1,3)(2,4),Group( 
    [ (1,2)(3,5), (1,2)(4,5) ] )) ]

so take $\infty \not\in \Omega$ and set $\Omega^+ = \Omega \cup \{\infty\}$ then choose $$x = (\infty\;0)(2\;3)(4\;6)(8\;9)$$ then

• $x^2 = 1 \in G_0$
• $a^x = b$ and (since $x$ has order 2) $b^x = a$ so $G_0^x = G_0$.
• $g_2^x = (\infty\;1)(2\;3)(5\;9)(4\;7)=x^{g_2} \in G x G$.
• $g_3^x = (\infty\;7)(1\;5)(2\;8)(4\;9)=x^{g_3} a^b \in G x G$.

Thus $L = \langle G, x \rangle$ is a one point extension. It has order $660 = 11 \cdot 10 \cdot 6$ and is 2-transitive (hence a primitive permutation group). We saw that $G$ ($A_5$) - the stabilizer of $\infty$ in $L$ - is simple so if $L$ had a regular normal subgroup (with a transitive action on the 10+1 points, with all its stabilizers trivial so..) of order 11 which must (by Lagrange) be $C_{11}$. $|N_{S_{11}}(C_{11})| = 110$ (by counting cycles) which is strictly less than 660 so it can't be normal. Therefore by the proposition we have:

Theorem $L$ is simple.

$1$ and $x$ are $(G,G)$-double coset reps in $L$. Take $\omega \not \in \Omega^+$ and form $\Omega^\star = \Omega^+ \cup \{\omega\}$. $$y=(\omega\;\infty)(1\;4)(2\;5)(3\;6)$$ then

• $y^2 = 1 \in G = L_{\infty}$
• $G^y = G$ since $G = \langle a,b,g_2,g_3 \rangle$ and $a^y = a$, $b^y = b$, $g_2^y = g_2^b$, $g_3^y = g_3 a^b$.
• $x^y = y^x a^b \in L y L$

Therefore we have another one point extension $M_{11} = \langle L, y \rangle$, which is 3-transitive of order 7920 acting on 12 points: so it can't have any regular normal subgroup from the corollary as none of these groups have order 12) but since $L$ is simple by the proposition we have:

Theorem $M_{11}$ is simple.

From Jordan's theorem we see that we cannot perform another one point extension.

• Dodecahedral Faces of M_12 

A_n is simple!

Lemma $A_5$ is perfect.
proof: $A_5$ is generated by $(1\;2\;3)$ and $(1\;2\;3\;4\;5)$ both are commutators:

gap> a := (1,5,2);; b := (4,2,3);; a^(-1)*b^(-1)*a*b;
(1,2,3)
gap> a := (1,2,3)*(3,4,5);; b := (1,4,2)*(3,5,2);; a^(-1)*b^(-1)*a*b;
(1,2,3,4,5)

Theorem $A_5$ is simple.
proof: The most basic proof using cycles directly can be found in Goodman.
proof: The conjugacy classes have sizes: 1, 15, 20, 12, 12. No sum of these that includes 1 is a divisor of 60 so there are no normal subgroups (which would necessarily be a union of conjugacy classes).
proof: A perfect group is not solvable, and every smaller group whose order divides $|A_5| = 60$ is solvable so $A_5$ has no normal subgroups (else it would be solvable too!)

gap> List(AllSmallGroups(2), StructureDescription);    
[ "C2" ]
gap> List(AllSmallGroups(2^2), StructureDescription);
[ "C4", "C2 x C2" ]
gap> List(AllSmallGroups(2*3), StructureDescription);
[ "S3", "C6" ]
gap> List(AllSmallGroups(2*5), StructureDescription);
[ "D10", "C10" ]
gap> List(AllSmallGroups(2*3*5), StructureDescription);
[ "C5 x S3", "C3 x D10", "D30", "C30" ]
gap> List(AllSmallGroups(2^2*3), StructureDescription);  
[ "C3 : C4", "C12", "A4", "D12", "C6 x C2" ]
gap> List(AllSmallGroups(2^2*5), StructureDescription);
[ "C5 : C4", "C20", "C5 : C4", "D20", "C10 x C2" ] 

Theorem $A_n$ is simple.
proof: Induction on $n$ with base case $5$. $A_n$ is $n-2$ transitive in the natural action (by the multiple-transitivity section) so for $n > 5$ this action is (at least) 2-transitive so primitive (by primitivity section) which by the powerful corollary about transitivity with regular normal subgroups tells us that a regular normal subgroup would have to be $C_2^2$ in the case of $A_6$ and there isn't one otherwise but $C_2^2$ doesn't have enough elements to be transitive on 6 points so it can't be regular -  so $A_n$ has no regular normal subgroups: therefore by the proposition in that section it's simple.

• math.pugetsound.edu/~ddrake/pdf/size-of-conjugacy-class-symmetric-group.pdf
• http://groupprops.subwiki.org/wiki/Alternating_group:A5
• http://www.math.uiowa.edu/~goodman/algebrabook.dir/algebrabook.html

Iwasawa's lemma

Lemma (Iwasawa) If $(G,\Omega)$ is a primitive permutation group with $G$ perfect and for some $\alpha \in \Omega$, $G_\alpha$ has a normal abelian subgroup $A$ whose conjugates generate $G$, then $G$ is simple.
proof: Suppose $1 \not = N \unlhd G$, we will gradually show that $N$ must be the whole group. By primitivity $N$ is transitive on $\Omega$ and $G_\alpha$ is a maximal subgroup, so $N \not \le G_\alpha$ and $N G_\alpha = G$. Any $g$ may be written $n x$ for some $n \in N$, $x \in G_\alpha$ so $A^g = A^{nx} = A^x \le AN$ and these conjugates cover the whole group so $AN = G$. Now $G/N \simeq A/(A \cap N)$ is abelian, but $G$ is perfect so $N = G$.

Projective Spaces and Groups

We aim to "fix" the following two issues: GL and SL are not 2-transitive because they can't linearly dependent vectors to linearly independent ones. SL is not simple (even though it's perfect) because it has a center. Let $V=V_n(q)$ and $n \ge 2$ throughout.

We define an equivalence relation $R$ on $V^\#$ by $vRw$ iff $v = \lambda w$ for some nonzero $\lambda \in \mathbb F_q$.

Definition We then have the projective space $\mathbb P(V)$ of projective vectors. Write $\mathbb P^{n-1}(q)$.

For a subspace $U \subseteq V$ the set of equivalence classes (projective vectors) $[U]$ (the image of $U^\#$) is a subspace of $\mathbb P(V)$ so it inherits geometric structure. The dimension of $[U]$ is the dimension of $U$ minus 1. A point is a class $[v]$ for some vector $v$, and a line is the projective class of a 2D subspace.

Given $g \in GL(V)$, $v \in V^\#$ and $\lambda \in \mathbb F_q^\#$ we have $(\lambda v)g = \lambda (vg) \in [vg]$ so we can (well) define an action by $[v]g = [vg]$. In this way $GL(V)$ and $SL(V)$ act on $\mathbb P(V)$, but not faithfully.

Lemma Let $G$ be $GL(V)$ or $SL(V)$, the kernel of the action of $G$ on $\mathbb P(V)$ is $Z(G)$.
proof: From the previous post we have seen what $Z(G)$ is: scalar multiples of the identity. If $gs = 1$ then clearly $g$ acts trivially on $\mathbb P(V)$. Conversely if $g \in GL(V)$ is in the kernel of the action then $[vg]=[v]$ for all $[v] \in \mathbb P(V)$, then for every vector $V$ we have $v g = \lambda_v v$ for some $\lambda_v \in \mathbb F^\#$ and the proof concludes in the same way as before.

Definition The projective general linear group and projective special linear group are defined by $PGL(V) = GL(V)/Z(GL(V))$ and $PSL(V) = SL(V)/Z(SL(V))$. They have faithful action on $\mathbb P(V)$. (Note: PSL might not be a subgroup of PGL anymore).

We call $[g] \in PGL$ or $PSL$ the image (???) if $g \in GL$ or $SL$ if $[v][g] = [vg]$ for $v\in \mathbb P(V)$. $PGL_n(q)$ and $PSL_n(q)$ act on $\mathbb P^{n-1}(q)$ by the order calculations in the previous post we find $|PGL_n(q)| = q^{n(n-1)/2}\prod_{i=2}^n(q^i-1)$ and $|PSL_n(q)| = \frac{q^{n(n-1)/2}}{(n,q-1)}\prod_{i=2}^n(q^i-1)$. Thus $|PGL_2(q)| = (q+1)q(q-1)$.

Proposition The permutation group $PGL_2(q)$ is sharply 3-transitive on $\mathbb P^1(q)$.
proof: For $g = \begin{pmatrix}a & b \\ c & d\end{pmatrix} \in GL_2(q)$ and $v \in V_2(q)^\#$, $vg = (a \lambda_1 + c \lambda_2, b \lambda_1 + d \lambda_2)$. These work out exactly as the mobius transformations when regarding $\mathbb P^1(q)$ as $\mathbb F_q \cup \{\infty\}$. We have already shown this one point extension is genrated by the mobius transforms!

Proposition Both $PGL(V)$ and $PSL(V)$ act 2-transitively on $\mathbb P(V)$.
proof: Given $([e_1],[e_2])$, $([e'_1],[e'_2])$ distinct then extend to a basis and find a map between them (why doesn't this work for all n-transitivity?)

Transvections

Assume $n \ge 2$ throughout,

Definition A linear functional on $V$ is a linear map from $V$ to $\mathbb F_q$. The set of these is the dual space $V^*$. Given $f \in V^*$ write $V_f$ for the kernel of $f$, if $f \not = 0$ then $V_f$ is a subspace of dimension $n-1$ (any such space of codimension 1 we call a hyperplane).

Lemma If you have $f,f' \in V$ with the same hyperplane then there exists $\lambda$ such that $f' = \lambda f$.
proof: The result is clear if $V_f=V$ assume not so $f,f'\not = 0$. Take $v \in V \setminus V_f$ (i.e. not in the common hyperplane) so $vf, vf' \not = 0$ and put $\lambda = (vf')(vf)^{-1}$ then $f' - \lambda f \in V^*$ and its kernel is contained in $\langle V_f, v \rangle = V$ so it equals zero.

Definition A linear automorphism $\tau \in GL(V)$ is called a transvection with direction $d \in V^\#$ if $\tau$ fixes $d$ and $$v \tau - v$$ is a scalar multiple of $v$ for all $v$.

Clearly $1$ is a transvection of any direction.

Lemma If $\tau$ is a transvection with direction $d$ then the vectorspace $\operatorname{fix}(\tau)$ is a hyperplane containing $d$.
proof: Define $f : V \to \mathbb F_q$ by $(vf)d = v \tau - v$ i.e. $f$ is that scalar multiple which a transvection defines. Since $\tau$ is linear $f \in V^*$. The result is clear for $\tau = 1$ and if not $f \not = 0$ so $d \in \operatorname{fix}(\tau) = V_f$.

Corollary Any transvection can be written as $\tau_{f,d}$ mapping $v$ to $v + (vf)d$ for some $f \in V^*$, $d \in (V_f)^\#$.

Lemma For $f,f' \in V^*$, $d \in V^\#$, $g \in GL(V)$ we have

• $\tau_{f,g}^g = \tau_{g^{-1}\circ f,dg}$
• $\tau_{f,d} \tau_{f',d} = \tau_{f+f',d}$

proof: first we need to check $(dg)(g^{-1} \circ f) = 0$ and $d(f+f')=0$ for the notation to be meaningful. Now the results follow by computation.

Definition For a direction $d \in V^\#$ set $\mathscr T(d) = \{\tau_{f,d}|f \in V^*, d \in V_f\}$ and $\mathscr T$ the union over all directions (all transvections).

Proposition $\mathscr T^\#$ is a single conjugacy class in $GL(V)$ and lies in $SL(V)$. If $n\ge 3$ then $\mathscr T^\#$ is a single conjugacy class in $SL(V)$.
proof: By the calculation lemma previous, we know that $\mathscr T^\#$ is closed under conjugation. Let $\tau_{f,d},\tau_{f',d'} \in \mathscr T^\#$ and write $e_1=d,e'_1=d'$ then take bases $e_1,\ldots,e_{n-1}$ and $e'_1,\ldots,e'_{n-1}$ of the hyperplanes $V_f,V_{f'}$, choose $e_n,e'_n$ such that $e_n f = e_n' f' = 1$. Now we have bases for $V$ so there is a GL map $g$ from one to the other.
For $i < n$ we have $e'_i(g^{-1} \circ f) = e_i f = 0$ so $V_{g^{-1} \circ f}$ is the space spanned by $\langle e'_1,\ldots,e'_{n-1} \rangle = V_{f'}$ so they are scalar multiples of each other, let $\lambda$ be such that $f' = \lambda (g^{-1} \circ f)$ and $$1 = e'_n f' = \lambda e'_n (g^{-1} \circ f) = \lambda e_n f = \lambda$$ so since $dg = d'$ it follows that $\tau_{f,d}^g = \tau_{f',d}$!
If they are all conjugate they all have the same determinant $\delta$, now $\det(\tau_{f,d}\tau_{f',d}) = \det(\tau_{f+f',d})$ so $\delta^2 = \delta$ proves they lie in $SL$.
For $n \ge 3$ we can use the $\mu$ trick as before to get them in $SL$.

Proposition If $d \in V^\#$ then $\mathscr T(d)$ is an abelian normal subgroup of the stabilizer $SL(V)_d$; $\mathscr T(d)$ are all conjugates in $SL(V)$.
proof: Certainly elements of $\mathscr T(d)$ stabilize $d$, by the computational lemma before we see that it is an abelian group (commutative and closed, therefore has identity and inverses). If $g \in SL(V)$ with $dg=d$ then $\mathscr T(d)^g = \mathscr T(d)$ (by the previous) so $\mathscr T(d) \unlhd SL(V)_d$. Given $d,d' \in V^\#$ by the transitivity lemma (that requires dimension > 1) exists $g \in SL(V)$ which takes $d$ to $d'$ then $\mathscr T(d)^g = \mathscr T(d')$.

Proposition The set $\mathscr T$ generates $SL(V)$.
proof: Elementary matrices.

Definition A group if perfect if $G' = G$. This is equivalent to there being no nontrivial abelian quotients: Clearly if $G/[G,G] \not = 1$ then $G\not = [G,G]$. Conversely if $G/N \simeq A = \{Ng\}$ then we always have $Ngg' = Ng'g$ i.e. there is some $n$ such that $gg' = ng'g$. So every commutator $[g,g']$ is an element of $N$.

Proposition If $n \ge 2$ the group $SL_n(q)$ is perfect provided $(n,q)$ isn't $(2,2)$ or $(2,3)$.
proof: We just need to show that each $\tau \in \mathscr T^\#$ is a commutator since that set generates our group. If $\tau$ has direction $d$ take some $\sigma \in \mathscr T(d)^\#$ not equal to $\tau^{-1}$, then $\sigma \tau \in \mathscr T(d)^\#$ so there is a $g \in SL_n(q)$ that conjugates $\sigma \tau = \sigma^g$, whence $\tau = \sigma^{-1} g^{-1} \sigma g= [\sigma,g]$.
For $n=2$ we will use $2 \times 2$ matrices directly, in some basis $\tau = \begin{pmatrix} 1 & \gamma \\ 0 & 1 \end{pmatrix}$ (nonzero $\gamma$), now for any nonzero $\lambda$ and $\mu \in \mathbb F_q$ we have $$\begin{pmatrix} \lambda & 0 \\ 0 & \lambda^{-1} \end{pmatrix}\begin{pmatrix} 1 & \mu \\ 0 & 1 \end{pmatrix}\begin{pmatrix} \lambda^{-1} & 0 \\ 0 & \lambda \end{pmatrix}\begin{pmatrix} 1 & -\mu \\ 0 & 1 \end{pmatrix}=\begin{pmatrix} 1 & \mu(\lambda^2-1) \\ 0 & 1 \end{pmatrix}$$ so for $q>3$ take $\lambda \not = 0,1,-1$ then $\lambda^2-1\not = 0$ so let $\mu = \gamma(\lambda^2-1)^{-1}$.

Proposition

• $Z(GL(V)) = \{\lambda 1 | \lambda \in \mathbb F_q^\# \}$
• $Z(SL(V)) = \{\lambda 1 | \lambda \in \mathbb F_q^\#, \lambda^n = 1\}$

proof: Certainly these are contained in the center, suppose $g \in Z(GL(V))$ or $Z(SL(V))$ then for each nonzero vector $d \in V^\#$ take a transvection $\tau_{f,d} \in \mathscr T(d)$, this should be unaffected by conjugation but we know $\tau_{f,d}^g = \tau_{g^{-1} \circ f,dg}$ so $dg = \lambda_d d$. Then $$\lambda_d d + \lambda_v d = (d+v)g = \lambda_{d+v}(d+v) = \lambda_{d+v}d + \lambda_{d+v}v$$ so $\lambda_d = \lambda_v = \lambda$ and $g = \lambda \cdot I$. For $SL$ we also require $\det(g) = \lambda^n = 1$. This tells us that $Z(GL_n(q)) \simeq \mathbb F_q^\#$ and $Z(SL_n(q)) \simeq C_{(n,q-1)}$.

Finite Fields and Finite Vector Spaces

Definition An Affine transformation of $\mathbb F_q$ is a map $f_{a,b}$ taking $\lambda$ to $a \lambda + b$ where $a \in \mathbb F_q^\#$ is nonzero. The group of such maps is called $A(\mathbb F_q)$.

Proposition $A(\mathbb F_q)$ is sharply 2-transitive of order $q(q-1)$.
proof: Let $\alpha,\beta$ distinct, the system of equations $\alpha = a 0 + b$, $\beta = a 1 + b$ has a unique solution.

Corollary By a general lemma about sharply 2-transitive groups this group must have a regular characteristic subgroup, this group is $\{f_1,b|b\in\mathbb F_q\}$.

Proposition $A(\mathbb F_q)$ has a one point extension which is sharply $3$-transitive of degree $q+1$.
proof: This is a straightforward application of the one point extension theorem, adjoin $\infty$ to $\mathbb F_q$ and define $x$ on $\mathbb F_q \cup \{\infty\}$ to swap $0$ and $\infty$ and invert all other elements $\lambda x = \lambda^{-1}$. Clearly $x^2=1$. Let $G_0 = \{f_{a,0}\mid a \in \mathbb F_q^\# \}$ and note $f_{a,0}^x$ fixes $0$ and $\infty$ while for $\lambda \in \mathbb F_q^\#$ we $f_{a,0}^x = f_{a^{-1},0}$ so $G_0^x = G_0$. Finally a system for the double cosets is given by just $1$ and any other element e.g. $f = f_{-1,1}$ will do (so $\lambda f = 1 - \lambda$ and $f^2=1$). We see that $xf$ acts on the $\infty, 1, 0$ by cycling them and for the remaining elements $\lambda (xf)^3 = 1 - \frac{1}{1-\frac{1}{\lambda}}=\lambda$ and (apparently...) $x^f = f^x \in GxG$ so we have a one point extension.

Definition $V_n(q)$ is the $n$-dimensional vector space over $\mathbb F_q$, clearly $|V_n(q)|=q^n$.

Definition If $V$  is a vector space then a linear automorphism of $V$ is a bijective linear map $V \to V$. The group of these is called the general linear group $GL(V)$ or $GL_n(q)$ when $V=V_n(q)$.

Definition The special linear group $SL(V)$ of linear automorphisms of determinant 1.

Lemma If $V$ is a vector space over $\mathbb F_q$ then $SL(V)$ is a normal subgroup of $GL(V)$ and the index is $q-1$: $|GL(V):SL(V)|=q-1$.
proof: SL is just the kernel of the surjective determinant map from GL to $\mathbb F_q^\times$. As a consequence $GL/SL \simeq \mathbb F_q^\#$ so $|GL:SL| = q-1$.

Lemma The group $GL(V)$ acts transitively on $V^\#$ and if the dimension of $V$ is $> 1$ the same is true of $SL(V)$.
proof: Take two nonzero vectors $e_1,f_1$ then to get a map between them choose bases $e_1,\ldots,e_n$ and $f_1,\ldots,f_n$ this gives $g \in GL(V)$ mapping between them. If $n > 1$, since we don't necessarily have $\det(g)=1$ let $\det(g)=\mu$ and replace $e_n$ by $\mu^{-1} e_n$. Now $g'$ mapping between these bases has determinant $1$. (did I get this right?)

Proposition $$|GL_n(q)| = q^{n(n-1)/2} \prod_{i=1}^n (q^i-1)$$ and $$|SL_n(q)| = q^{n(n-1)/2} \prod_{i=2}^n (q^i-1).$$
proof: $GL_n(q)$ acts regularly on ordered bases of $V_n(q)$, so the size of $GL_n(q)$ is equal to the number of ordered bases: $q^n-1$ choices for the first element, and having chosen $e_1,\ldots,e_i$ (which spans a $q^i$ sized space) already there are $q^n-q^i$ choices for the next. The size of $SL$ comes from the lemma before the previous.

Sharply t-transitive groups

Sharply transitive groups are the smallest possible transitive groups, given $t \in \mathbb N$ a $t$-transitive group $G$ is called sharply t-transitive if $G_{\alpha_1 \alpha_2 \ldots \alpha_t} = 1$ for distinct $\alpha$s. Equivalently, there is exactly one group element that takes $(\alpha_1,\cdots,\alpha_t)$ to any other triple of distinct symbols.

Theorem If $G$ is a $t$-transitive group of degree $n$ (i.e. it acts on $n$ symbols) then it is sharply $t$-transitive iff $|G| = n (n-1)\cdots(n-t-1)$.
proof: For $t=1$ this is the regular action. For $t+1$ any $G_\alpha$ will be $t$-transitive and $|G|=n|G_\alpha|$ since the orbit of $\alpha$ is the whole of $\Omega$, conversely every stabilizer $G_\alpha$ will have the same order - and there are $n$ of them so each $|G_\alpha| = |G|/n$ is $t-1$-transitive so $G$ is $t$-transitive.

Example $S_n$ is sharply $n$-transitive in the natural actions, it is also $n-1$-sharply transitive. Note this isn't a contradiction from the group order result because $|G|=|G|\cdot 1$. Intuitively what's happening is if we choose exactly where $n-1$ symbols go, then it's already decided where the last one must go.

Proposition If $G$ is sharply $2$-transitive of degree $n$ then $G$ has a regular characteristic subgroup which is an elementary abelian $p$-group for some prime $p$ (so $n$ is power of $p$).
proof: Given $G$, let $K$ be the union of the fixed point free elements and 1. We will show it is a group. Since for any distinct $\alpha,\beta \in \Omega$, $G_\alpha \cap G_\beta = G_{\alpha \beta} = 1$ so $G$ is the disjoint union $K \sqcup \bigsqcup_{\alpha \in \Omega} G_\alpha^\#$, $|G_\alpha^\#| = \frac{|G|}{n}-1$ (using $n = |G|/|G_\alpha|$ from the orbit-stab. theorem) so $|K|=n$. Take $\alpha,\beta \in \Omega$ distinct and choose $k \in K^\#$ such that $\alpha k \not = \alpha$. As $G$ is $2$-transitive there exists $g \in G_\alpha$ with $(\alpha h) g = \beta$ then $h^g$ has the same order and fixedpoints as $h$ i.e. none, therefore its in $K$, and $\alpha k^g = \beta$ so $K$ is a transitive "set". For any $\alpha \in \Omega$ the map $K \to \Omega$ given by $k \mapsto \alpha k$ is surjective and hence bijective. Now take take distinct $x,y \in K$ we know $\alpha x \not = \alpha y$ so $\alpha x y^{-1} \not = \alpha$ for all $\alpha$, so $x y^{-1} \in K$. This proves $K$ a subgroup!
Given $k \in K^\#$ all its cycles on $\Omega$ must all have the same length since otherwise some non-identity power of $k$ would have fixed points. So the order of $k$ divides $n$. Similarly for elements of $G_\alpha^\#$ the same argument tells us all its cycles on $\Omega \setminus \{\alpha\}$ have the same length, so its order divides $n-1$. Hence $K$ consists of the elements of $G$ of order dividing $n$ - a property preserved by conjugation - therefore it's a characteristic subgroup. By the corollary from the section on regular normal subgroups it is an elementary abelian $p$-group.

One-point extensions

Reversing the idea of a point stabilizer Let $(G,\Omega)$ be a transitive permutation group, take a point $\omega \not\in \Omega$ and form $\Omega^+ = \Omega \cup \{\omega\}$, extend the action by $\omega g = \omega$ for all $g \in G$:

Definition A one-point extensionof $(G,\Omega)$ is a transitive permutation group $(G^+,\Omega^+)$ with $(G^+)_\omega = G$

By the stabilizer-orbit theorem $|G_+| = |G|(|\Omega|+1)$. If $G^+$ is $t$-transitive then G is $(t-1)$-transitive.

Example $S_n$ and $A_n$ have one point extensions $S_{n+1}$ and $A_{n+1}$.
Non-example $D_8$ doesn't have one by Sylow theory.

Take $\alpha \in \Omega$, we know the rank $r$ of $G$ equal to the number of double cosets in $G$. For $g_1,\ldots,g_r \in G$ we have a complete representation of the double coset system iff $\alpha g_1,\ldots,\alpha g_r$ is a complete set of representatives of $G_\alpha$-orbits. wlog take $g_1 = 1$, if $(G^+,\Omega^+)$ is a one point extension of $(G,\Omega)$ then it is 2-transitive so it has a primitive action and hence the point stabilizer $G$ is a maximal subgroup of $G^+$: for any $x \in G^+ \setminus G$ we must have $\langle x, G \rangle = G^+$. We can wlog choose $x$ to interchange $\alpha$ and $\omega$.

Theorem Let $(G,\Omega)$ be a transitive permutation group of rank $r$ for $\alpha \in \Omega$, let $g_1=1,g_2\ldots,g_r$ be a complete set of representatives of the double coset system. Take $\omega \not\in \Omega$ and form $\Omega^+ = \Omega \cup \{\omega\}$. Take $x \in S_{(\Omega^+)}$ (so some permutation from the symmetric group) with $\alpha x = \omega$, $\omega x = \alpha$ and set $G^+ = \langle x, G \rangle$ then $(G^+,\Omega^+)$ is a one point extension iff:

1. $x^2 \in G_\alpha$
2. $(G_\alpha)^x = G_\alpha$
3. $g_i^x \in GxG$ for all $i > 1$.

proof: ($\Rightarrow$) (1) definition of $x$ (2) easy (3) As $x \not\in G$ the 2-transitivity of $G^+$ means that $G^+ = G \cup GxG$ (any permutation that can't be done with $g$ can be done with $x$ in the middle), for $2 \le i \le r$ we have $g_i \in G\setminus G_\alpha$ so $\omega g_i^x = \alpha g_i x \not = \alpha x = \omega$ thus $g_i^x \not \in (G^+)_\omega = G$ so $g_i^x \in GxG$. ($\Leftarrow$) Set $H=G \cup GxG$as a set, we will show its a group $H \le S_{\Omega^+}$, to show it's a group we need $HH = H = H^{-1}$. Since $G^{-1}= G$ and $(gxg')^{-1} = g'^{-1} x (x^2)^{-1} g^{-1} \in GxG$ . By (2) $x G_\alpha x= G_\alpha$ so for $i \ge 2$ we have $$x G_\alpha g_i G_\alpha x = G_\alpha (x g_i x) G_\alpha = G_\alpha x^2 g_i^x G_\alpha \subseteq GxG$$ so $$xGx = xG_\alpha x \cup \bigcup_{i=2}^r x G_\alpha g_i G_\alpha x \subseteq G_\alpha \cup GxG \subseteq H.$$ Now $HH = G \cup GxG \cup GxGxG \subseteq H \cup GHG = H$, we have shown it's a group! Now $G^+ = \langle G,x\rangle = H$ and for all $g,g'$ take $\omega (g x g') = \omega x g' = \alpha g' \not = \omega$ so $(G^+)\omega = G$.

Multiple-transitivity

Consider actions of rank 2 (meaning that there are two suborbits of $G_\alpha$), $\Omega \setminus \{\alpha\}$ forms a single $G_\alpha$ orbit (because one its other orbit is $\alpha G_\alpha = \{\alpha\}$). $G$ acts on $\Omega^2$ non-transitively because $g(\beta,\beta) = (\gamma,\gamma)$ but if we define the diagonal $Delta = \{(\beta,\beta)\in \Omega\}$ this is a single orbit due to transitivity and so $\Omega^2 \setminus \Delta$ is the interesting part:

Lemma The action of $G$ on $\Omega$ is of rank 2 iff $\Omega^2 \setminus \Delta$ is a single orbit.
proof: If the action has rank 2 then let $(\beta_1,\beta_2), (\gamma_1,\gamma_2)$ lie off the diagonal and pick $x,y \in G$ such that $\alpha x = \beta_1$, $\alpha y = \gamma_1$ then neither of $\beta_2 x^{-1}$ and $\gamma y^{-1}$ are equal to $\alpha$ (otherwise $\beta_1 = \beta_2$ or $\gamma_1 = \gamma_2$) so there exists $h \in G_\alpha$ which maps one to the other $\beta_2 x^{-1} h = \gamma_2 y^{-1}$. Let $g = x^{-1} h y$ and compute $$(\beta_1,\beta_2) g = (\gamma_1,\gamma_2).$$
In the other direction if  $\Omega^2 \setminus \Delta$ is a single orbit the action is at least 2 (since we can fix any one element $\beta$ in the first component and map any other element $\gamma$ not equal to beta to any other element not equal to beta). So suppose the rank were larger than 2, then pick $\beta,\gamma$ in different $G_\alpha$ orbits of $\Omega \setminus \{\alpha\}$ and take $(\alpha,\beta), (\alpha,\gamma) \Omega^2 \setminus \Delta$ there's clearly no way to map from one to the other.

We can generalize this to $\Omega^t$ for any natural $t \le |\Omega|$. Again $\Delta = \{(\alpha,\alpha,\ldots)\}$ is a single orbit, but the interesting part is $\Omega^{(t)} = \{(\alpha_1,\alpha_2,\ldots)|\alpha_i \not = \alpha_j\}$.

Definition The action of $G$ on $\Omega$ is $t$-transitive if the induced action on $\Omega^{(t)}$ is transitive. This is equivalent to saying it can simultaneously map any $t$ distinct points to any other $t$ distinct points.

Lemma In terms of cosets, a group action is 2-transitive iff $G = G_\alpha \cup G_\alpha g G_\alpha$ for any $g \setminus G_\alpha$.
proof:  We saw previous that double cosets correspond to suborbits, write $G_\alpha = G_\alpha 1 G_\alpha$ to see this is the same as rank 2.

Lemma The action of $G$ on $\Omega$ is $t$-transitive iff the action of $G_\alpha$ on $\Omega \setminus \{\alpha\}$ is $(t-1)$-transitive.
proof: write this out.

Corollary If $G$ acts $t$-transitively on $\Omega$ and $|\Omega|=n$ then $|G|$ is divisible by $n(n-1)\cdots(n-t+1)$. WHICH THEOREM DOES THIS DEPEND ON? CHECK OTHER BOOK

Theorem In the natural action $S_n$ is $n$-transitive while $A_n$ is $n-2$ transitive and not $n-1$ transitive.
proof: This is obvious from the fact $S_n$ contains every permutation. For $A_n$ we use induction: it clearly holds for $A_3$. For $n \ge 3$ the stabilizer of any point of $A_n$ is $A_{n-1}$ so by the lemma we complete the induction.

Regular Normal Subgroups and Semidirect Products

Let $G$ act transitively on $\Omega$ throughout. We shall be concerned with the case where $G$ has a regular normal subgroup $K$, meaning that $K \unlhd G$ acts transitively on $\Omega$ and the stabilizer $K_\alpha$ is trivial for every $\alpha$ (this is the regular action, it's equivalent to the action on the cosets $1 g$).

Lemma If $G$ acts transitively on $\Omega$ with regular normal subgroup $K$ choose $\alpha \in \Omega$ the action of $G_\alpha$ on $K$ by conjugation is equivalent to its action on $\Omega$ with $1 \in K$ corresponding to $\alpha \in \Omega$.
proof: Define $\theta : K \to \Omega$ by $k \mapsto \alpha k$. This is a bijection since $K$ is regular. We just need to show that the two actions are equivalent: $$(k \theta) g = \alpha k g = \alpha g k^g = \alpha k^g = k^g \theta.$$

If $G$ is multiply transitive and has a regular normal subgroup $K$ the subgroup $G_\alpha$ is transitive on $\Omega \setminus \{\alpha\}$ and hence $K^\# = K \setminus \{1\}$ as conjugation is an automorphism of a group, this means in particular that the group $K$ ???? automorphisms ?????? ff

Lemma An automorphism preserves the order of a group element.
proof: Let $\theta : G \to G$ be an automorphism and $g$ have order $n$, then $(\theta g)^i \not = 1$ for any $0 < i < n$ since if it did $\theta(g^i) = 1$ implies that $g^i = 1$.

Proposition Let $K$ be a group then

1. If $\operatorname{Aut} K$ acts transitively on $K^\#$ then $K$ is elementary abelian
2. If $\operatorname{Aut} K$ is 2-transitive on $K^\#$ then either $K \simeq C_2^s$ or $C_3$
3. If $\operatorname{Aut} K$ is 3-transitive on $K^\#$ then $K \simeq C_2^2$
4. $\operatorname{Aut} K$ is not 4-transitive.

 proof: (1) Since automorphisms preserve the order of elements all elements must have the same order, and that order must be a prime otherwise there would be elements with smaller order, by Cauchy's theorem we can say this is a $p$-group and so $Z(K)$ is non-trivial. In fact we know $Z(K) \operatorname{char} G$ (because the center is preserved by conjugation) now any automorphism of $K$ fixes a characteristic subgroup like $Z(K)$ so for transitivity to be possible $Z(K)=K$. This implies $K$ is abelian and therefore a direct product of cyclic groups, which we know must all be $C_p$!
(2) Since 2-transitivity implies primitivity of the action we define a relation on $K^\#$ that is an $\operatorname{Aut} K$-congruence: $k R k'$ if $k=k'$ or $k^{-1} = k'$. Clearly this is an equivalence relation preserved by the action hence by primitivity it must be the equality relation (implying $k^{-1} = k$ so the group is $C_2^s$) or the entire relation (implying every two non-identity elements are equal or inverse so the group will be $C_3$).
(3) If the group is further 3-transitive, then it's impossible that it's $C_3$: That's too small! Take some $k \in K^\#$ and consider the stabilizer $(\operatorname{Aut} K)_k$ which is 2-transitive hence primitive so again let's define a congruence on it $k_1 R k_2$ if $k_2 = k_1$ or $k_2 = k k_1$ - meaning that $k_1$,$k_2$ "differ by $k$" - this can't be the equality relation since that would imply $k=1$ so it's the universal relation implying $K \simeq C_2^2$.
(3)  This is impossible again because the group is too small.

Corollary Suppose $G$ acts $t$-transitively on $\Omega$ with a regular normal subgroup $K$ so $|\Omega| = |K|$ then

1. If $t=2$ then $K \simeq C_p^s$
2. If $t=3$ then $K \simeq C_2^s$ or $C_3$
3. If $t=4$ then $K \simeq C_2^2$
4. $t < 5$

Proposition If $(G,\Omega)$ is a primitive permutation group such that some $G_\alpha$ is simple (therefore all $G_\alpha$ are simple) then either $G$ is simple or has a regular normal subgroup.
proof: Suppose $G$ is not simple, then there's a $K$ such that $1 \not = K \lhd G$. In that case $K \cap G_\alpha \unlhd G_\alpha$ is simple so $K \cap G_\alpha = 1$ or $K \cap G_\alpha = G_\alpha$ but $K$ is transitive by a corollary on primitive permutation groups and $G_\alpha$ is a maximal subgroup by another corollary so we cannot have $G_\alpha \le K$ (certainly $G_\alpha < K$ can't happen, and if $G = G_\alpha$ then \alpha $g G_\alpha = \alpha g$ so $G_\alpha = G_\beta = \ldots = G$ contradiction). Then $K \cap G_\alpha = 1$ so $K$ is regular because it's a normal subgroup which we showed acts transitively and also it has the regular action because we saw that $K_\alpha = 1$.

Definition Let $H,K$ be groups with a homomorphism $\theta : H \to \operatorname Aut K$. For $k \in K$, $h \in H$ write $k^h$ short for $k^{h \theta}$. Then the semidirect product $K \rtimes H$ is defined as the group $K \times H$ with binary operation:
$$(k_1,h_1)(k_2,h_2) = (k_1 k_2^{h_1^{-1}},h_1h_2).$$
proof: prove this is a group

Define subgroups of the semidirect product $\tilde{K} = \{(k,1)\}$ and $\tilde{H} = \{(1,h)\}$ then $\tilde{K} \le K \rtimes H$, $\tilde{H} \le K \rtimes H$, $\tilde K \cap \tilde H = 1$,,$\tilde K \tilde H = K \rtimes H$ and $\tilde K \unlhd K \rtimes H$ but we don't know that $\tilde H \unlhd K \rtimes H$. This is an "external" construction of the semidirect product. We also have an internal one. An extension $G$ of $K$ by $H$ is such that $K \lhd G$, $G/K \simeq H$ i.e. the short exact sequence $$1 \longrightarrow K \longrightarrow G \longrightarrow H \longrightarrow 1$$ in which case we write $G = K . H$, the $.$ is "neutral" meaning that it doesn't really tell you how the group has been extended.

Definition if we have a s.e.s. like above with $K \unlhd G$, $K \cap H = 1$ and $KH=G$ we call $G$ a split extension of $K$ by $H$ and write $G = K:H$.

Theorem If $G$ is a split ext then define $\theta : H \to \operatorname{Aut} K$ by $k^{h \theta} = k^h$. Then $G \simeq K \rtimes H$.

Corollary If $G$ is transitive on $\Omega$ with a regular normal subgroup then $G = K : G_\alpha$.

Primitivity

The section is about decomposing group actions, assume $\Omega$ transitive.

Definition A non-empty set $\Gamma \subseteq \Omega$ is called a block if for all $g \in G$ either $\Gamma g = \Gamma$ or $\Gamma g \cap \Gamma = \{\}$. If $\Gamma$ is a block then the set $\Sigma = \Sigma(\Gamma) = \{\Gamma g \mid g \in G\}$ of all translates of $\Gamma$ is a block system.

Lemma A block system partitions $\Omega$. proof: Let $\alpha \in \Gamma$ and $\beta \in \Omega$ then $\beta = \alpha g$ for some $g$ so $\beta \in \Gamma g$ and the blocks cover $\Omega$. If $\Gamma g \cap \Gamma h$ is non-empty then $\Gamma gh^{-1} = \Gamma$ so $\Gamma g = \Gamma h$.

Definition A $G$-congruence is an equivalence relation $R$ on $\Omega$ such that $\alpha R \beta$ implies $\alpha g R \beta g$.

Definition If $R$ is a $G$-congruence then the $R$-equiv classes form a block system and conversely if $\Gamma$ is a block we define $R$ by $\alpha R \beta$ iff $\alpha,\beta \in \Gamma g$.
proof: easy

The trivial $G$-congruences are the equality relation and the one induced by the block $\Omega$.

Definition The (transitive) action on $\Omega$ is called imprimitive if there is a non-trivial $G$-congruence. If there are no non-trivial $G$-congruences an action is primitive.

Proposition Let $\alpha \in \Omega$, write $B(\alpha)$ for the set of blocks containing $\alpha$ and $S(\alpha)$ for the set of subgroups containing $G_\alpha$.

• There are mutually inverse bijections $\Psi : B(\alpha) \to S(\alpha)$ and $\Phi : S(\alpha) \to B(\alpha)$ defined by $\Gamma \Psi = G_{\Gamma}$, $H \Phi = \alpha H$.
• For $\Gamma,\Gamma' \in B(\alpha)$ we have $\Gamma \subseteq \Gamma'$ iff $\Gamma \Psi \le \Gamma' \Psi$.

proof: long.

Corollary The action of $G$ on $\Omega$ is primitive iff each $G_\alpha$ is a maximal subgroup.

Proposition If the action of $G$ on $\Omega$ is 2-transitive then it is primitive.
proof: If the action is 2-trans take $\alpha \in \Omega$. Suppose $\Gamma$ is a block containing $\alpha$ with $|\Gamma| > 1$. Take $\beta \in \Gamma \setminus \{\alpha\}$ then for any $\beta' \in \Omega \setminus \{\alpha\}$ there exists $g \in G_\alpha$ with $\beta g = \beta'$. As $\alpha \in \Gamma g \cap \Gamma$ we must have $\Gamma g = \Gamma$ so $\beta' \in \Gamma$ and hence $\Gamma = \Omega$. So $\alpha$ lies in no nontrivial block.

Note: The converse is not true, you can have imprimitive actions that aren't 2-transitive.

Proposition If $N \unlhd G$ the set of $N$-orbits in $\Omega$ is a block system.
proof:  Let $\Gamma$ be an $N$-orbit, If $g \in G$ with $\Gamma g \cap \Gamma \not = \{\}$ let $\alpha \in \Gamma g \cap \Gamma$ so $\alpha = \beta g$ with $\beta \in \Gamma$ then $\Gamma = \alpha N = \beta N$. So $\Gamma g = \beta N g = \beta g N = \alpha N = \Gamma$.

Corollary If $G$ is a primitive permutation group (no non-identity elements fix all elements of $\Omega$) and $1 \not = N \unlhd G$ then $N$ acts transitively.
proof: Since $1 \not = N$ there is an $N$ orbit of size > 1 so by the previous theorem it gives a block system, by primitivity it's the whole of $\Omega$, so $N$ must act transitively.

Suborbits and double-cosets

Throughout we will assume that $G$ acts transitively on $\Omega$. The idea motivating this section is that since each orbit is conjugate, what freedom remains when we pick some fixed $\alpha$ and consider $G_\alpha$ (The stabilizer of $\alpha$)?

Since $G_\alpha$ is not just a subset of $G$ but in fact a subgroup, the action of $G$ on $\Omega$ induces an action of $G_\alpha$ on $\Omega$.

Definition The orbits of $G_\alpha$ on $\Omega$ (by this induced action) are called suborbits, their sizes are called subdegrees and the rank is how many there are.


Recall the orbit/stabilizer theorem:

• $\alpha G = \{ \alpha g \in \Omega | g \in G\}$
• $G_\alpha = \{g \in G | \alpha g = \alpha \}$
• Since $\alpha g = \alpha g'$ iff $gg'^{-1} \in G_{\alpha}$ iff $G_\alpha g = G_\alpha g'$ the bijection $\alpha g \mapsto G_\alpha g$ is well defined, it also respects the group action.

By transitivity every element $\beta \in \Omega$ can be written as $\alpha g$ for some $g$, in fact $\{\beta\} = \alpha G_\alpha g$ so elements of $\Omega$ are in bijection with the right cosets $\{G_\alpha g| g \in G\}$.

Suborbits of $G_\alpha$ are the orbits $\beta G_\alpha$ which are thus in bijection with the double cosets $G_\alpha g G_\alpha$.

We call these $(G_\alpha,G_\alpha)$-double cosets and they partition the group. The size of a double coset divided by $|G_\alpha|$ gives the subdegree (similar to Lagrange's theorem).

Lemma The rank of the action of $G$ is $\frac{1}{|G|} \sum_{g \in G} |\operatorname{fix}(g)|^2$.
proof: Apply Burnside's lemma to the action of $G_\alpha$ on $\Omega$ to get $$\frac{|\Omega|}{|G|}\sum_{g \in G_\alpha} |\operatorname{fix}(g)|$$ since $|G_\alpha| = \frac{|G|}{|\Omega|}$ now sum over all $\alpha$ to get $$\frac{1}{|G|}\sum_{\alpha \in \Omega} \sum_{g \in G_\alpha} |\operatorname{fix}(g)| = \frac{1}{|G|}\sum_{g \in G} \sum_{\alpha \in \operatorname{fix}(g)} |\operatorname{fix}(g)|.$$

Definition Let $\alpha,\beta \in \Omega$. The 2-point stabilizer $G_{\alpha,\beta}$ is $G_\alpha \cap G_\beta$.
Definition The pointwise stabilizer of a set of points $\Gamma \subseteq \Omega$, $G_{(\Gamma)}$ is $bigcap_{\gamma \in \Gamma} G_\gamma$.
Definition The setwise stabilizer $G_{\Gamma} = \{ g \in G | \Gamma_g = \Gamma \}$.

Lemma Given $\beta \in \Omega$ the subdegree corresponding to $\beta$ is $|G_\alpha : G_{\alpha,\beta}|$.
proof: In the action of $G_\alpha$ on the suborbit $\beta G_\alpha$ the stab. of $\beta$ is $G_\alpha \cap G_\beta$. The result follows from orb/stab theorem.

Definition If $G_\alpha = 1$ the action is regular and has rank $|\Omega|$

Permutation groups: Burnsides Lemma and the Fixed point free theorem

Definition If $G$ acts on $\Omega$ and $g \in G$ then the fixed point set $\operatorname{fix}(g)$ is $\{\alpha \in \Omega | \alpha g = \alpha \}$. If $\operatorname{fix}(g) = \{\}$ then $g$ is FPF (fixed point free).

Lemma ("Burnsides lemma" except it was actually proved by Frobenius) If $G$ acts on $\Omega$ then the number of orbits is $$\frac{1}{|G|}\sum_{g \in G}|\operatorname{fix}(g)|.$$
proof: Consider the set $S = \{(\alpha,g) \in \Omega\times G | \alpha g = \alpha \}$. We shall count it in two different ways:
First given $\alpha$, consider the number of ways it can occur as the first component of the pair: that's just $|G_\alpha|$ the size of its stabilizer, from the fact $|G_{\alpha g}| = |G_{\alpha}^g| = |G_\alpha|$ proved in the previous post we get that the contribution to $S$ from the orbit is $\alpha G$ is $|G_\alpha| |\alpha G| = |G|$ therefore $|S| = |G| \cdot \text{number of orbits}$.
Secondly given $g$, consider the number of ways it can occur as the second component of the pair: that's just $\operatorname{fix}(g)$.
Putting these together gives the formula.

Corollary If $G$ acts transitively on $\Omega$ (and $|\Omega| > 1$) some element of $g$ is fixed point free. proof: There is only 1 orbit, so the average number (over $G$) of elements fixed is 1.. but the identity has $|G|$ fixed points - every element!

Permutation groups: actions, orbit and stabilizer

Notation backwards notation: $(1\,2\,3)(1\,3\,2\,4) = (1\,4)$

Notation $(2\,4)^{(1\,2\,4\,5\,3)}=(2\,5)$, in general $\sigma^{\pi}$ sends $i \pi \mapsto i \sigma \pi$ so you can compute these by hand.

 Definition A permutation group is a finite set $\Omega$ and a group of permutations (that is, bijections $\Omega \to \Omega$). We'll write $S_{\Omega}$ for the group of all permutations on a set. The degree of a permutation group is the cardinality $|\Omega|$.

Notation Let $\alpha \in \Omega$ then $\alpha g$ for the image of $\alpha$ through $g$. Group homomorphisms are written after elements too.

Definition If $G$ acts on two sets $\Omega$ and $\Omega'$ then the actions are equivalent if there is a bijection $\theta$ between them such that $$\forall g \in G, \forall \alpha \in \Omega,\,(\alpha \theta) g = (\alpha g) \theta.$$

Definition We write $\alpha G = \{\alpha g | g \in G \}$ for the orbit of $G$ containing $\alpha$.

Definition We write $G_{\alpha} = \{g \in G | \alpha g = \alpha \}$ for the stabilizer of $\alpha$.

Definition A group action is transitive if $\Omega$ is a single orbit.

Definition The kernel of the action is $G_{(\Omega)} = \{g \in G| \forall \alpha \in \Omega, \alpha g = \alpha \}$. Clearly $G \to S_{(\Omega)}$ defined by $g \mapsto (\alpha \mapsto \alpha g)$ is a homomorphism with kernel $G_{(\Omega)}$, this $G/G_{(\Omega)}$ can be identified with its image in $S_{\Omega}$ giving a permutation group $(G/G_{(\Omega)},\Omega)$.

Definition An action is said to be faithful if the kernel is trivial.

Definition The core of $H$ in $G$ is $H_G = \bigcap_{x \in G}H^x$, this is the largest normal subgroup of $G$ contained in $H$.

Examples
(i) If $(G,\Omega)$ is a permutation gp and $G$ acts on $\Omega$ faithfully this is called the natural action.
(ii) If $H \le G$ we have an action of $G$ on the set $(G:H)$ of right cosets of $H$ in $G$ by $(Hx)g = H(xg)$. This is called a coset action and if $H=1$ it is the regular action. The kernel of the regular action is the core: We have $g \in G_{(\Omega)}$ iff $\forall x, Hxg = Hx$ iff $\forall x, xgx^{-1} \in H$ iff $\forall x, g \in H^x$.
(iii) The action of $G$ on $(G:H)$ given by $Hx \in \Omega$ is clearly transitive. The stabilizer of $H$ is $H$ while that of $Hx$ is $\{g \in G | Hxg = Hx \} = H^x$.

Lemma If $G$ acts on $\Omega$, given $g \in G$ and $\alpha \in \Omega$ we have $G_{\alpha g} = G_{\alpha}^g$.
proof: $x \in G_{\alpha g}$ iff $\alpha g x = \alpha g$ iff $\alpha g x g^{-1} = \alpha$ iff  $x \in G_{\alpha}^g$.

Theorem (orbit stabilizer) If $G$ acts on $\Omega$ and $\alpha \in \Omega$ then the actions of $G$ on $\alpha G$ and $(G:G_\alpha)$ are equivalent.
proof: given $g,h \in G$, $\alpha g = \alpha h$ iff $gh^{-1} \in G_{\alpha}$ iff $G_{\alpha} g = G_{\alpha} h$. Thus $\theta = \alpha g \mapsto G_{\alpha} g$ is a well defined bijection, and it respects the action since $((\alpha g) \theta)x = G_\alpha g x = ((\alpha g ) x) \theta$.

Corollary Any transitive action is equivalent to a coset action.

Corollary $$|G| = |G_\alpha| |\alpha_G|.$$ (because $|\alpha G| = |(G:G_\alpha)|$ by the theorem and $|G| = |G_\alpha||(G:G_\alpha)|$ is a triviality just write it down).

Sylow bases - Structural character of Solvable groups

Notation Let $p'$ denote the set of all primes other than $p$.

Let $G = p^a m$ with $p \not | m$, a Sylow $p$-subgroup $P$ has order $p^a$ whereas a Hall $p'$-subgroup $H$ of $G$ has order $m$. $H \cap P = 1$ and so $|G|=|H||P|$ and $G=HP$.

Lemma If $H,K \le G$ and $|G:H|,|G:K|$ are coprime then $|G:H \cap K| = |G:H||G:K|$ (note, this doesn't assume normality).
proof: Put $a=|G:H|$, $b=|G:K|$, $c=|G:H \cap K|$. Since $|G:H \cap K|=|G:H||H:H\cap K|$ we have $a|c$ and similarly $b|c$ thus $ab|c$. In the other direction we may define a map $$(H \cap K) x \mapsto (Hx,Kx) : \{\text{cosets of }H \cap K\} \to \{\text{cosets of }H\}\times\{\text{cosets of }K\}$$ this is well defined since $(H \cap K) x = (H \cap K) y$ iff $xy^{-1} \in H$ and $K$ iff $Hx=Hy$ and $Kx = Ky$. Since this map is injective $c \le ab$.

Definition Let $G$ be a group whose order factors into powers of primes $p_1, \ldots, p_k$. A Sylow basis for $G$ is a collection of Sylow subgroups $P_1,\ldots,P_k$ such that for all $i$, $P_i$ is a Sylow $p_i$-subgroup and for all $i,j$ $P_i P_j = P_j P_i$.

Any product of a subset of the Sylow basis will give a Hall $\pi$-subgroup and you can get a Hall $\pi$-subgroup for any $\pi$ this way.

Definition Two Sylow bases $P$ and $B$ are said to be conjugate when there exists a single $g$ such that forall $i$, $P_i = B_i^g$.

Theorem (Hall - 1937) If $G$ is solvable then it has a Sylow basis and any two such bases are conjugate.
proof: (Existence) Let $G$ be a solvable group and write $|G| = p_1^{a_1}\cdots p_k^{a_k}$, let $S = \{1,\ldots,k\}$. For each $i \in S$ let $Q_i$ be a Hall $p_i'$-subgroup so $|G:Q_i| = p_i^{a_i}$ by the previous theorem of Hall. Given any $T \subseteq S$ the intersection $\bigcap_{t \in T} Q_t$ is a Hall $\pi$-subgroup (for the appropriate $\pi = \{p_j | j \in S \setminus T \}$). In particular $P_i = \bigcap_{t \not = i} Q_t$ is a Hall $\{p_i\}$-subgroup (A Sylow $p_i$-subgroup) of $G$. To see that this gives a basis take $i,j \in S$ not equal and $P_i \cap P_j = 1$ by coprimality, therefore we have (considered as sets) $|P_i P_j| = |P_i||P_j| = |P_j P_i|$. Write $T = S \setminus \{p_i,p_j\}$ then $\bigcap_{t \in T} Q_t$ is a group that contains $P_i$ and $P_j$ hence $P_i P_j$ and $P_j P_i$ but $|\bigcap_{t \in T} Q_t| = p_i^{a_i} p_j^{a_j}$ as it's a Hall $\pi$-group!
(Uniqueness up to conjugacy) Let $B_1,\ldots,B_k$ be any other Sylow basis for $G$ with (by renumbering) $|B_i|=|P_i|$. For $t in S$ form the Hall $p_t'$-subgroup $C_t = \Pi_{i \not = t}B_i$. Instead of showing each $B_i$ is conjugate to $P_i$, we show that each $Q_i$ is conjugate to $C_i$ then deduce that. Let $d$ be the number of $t$ such that $C_t \not = Q_t$, and we prove by induction on $d$ that there exists some $g$ such that for every $t$, $C_t = Q_t^g$: the base case $d=0$ is trivial. Assume (by renumbering if necessary) that $C_t = Q_t$ for all $t > d$. Write $H = \bigcap_{t > d}Q_t$ by the uniqueness up to conjugacy of Hall $\pi$-subgroups for solvable groups there exists $x$ such that $C_d = Q_d^x$, since $Q_d$ contains each $P_i$ except $P_d$ - which lies in $H$ - $G = Q_d H$ and so $x = gh$ for some $g \in Q_d$, $h \in H$. Now $C_d = Q_d^{gh} = Q_d^h$ and for $t < d$ $C_t = Q_t = Q_t^h$ so there are at most $d-1$ values of $t$ (the $t < d$) such that $C_t \not = Q_t$ therefore we have by induction $z \in G$ such that $\forall t$, $C_t = (Q_t^h)^z = Q_t^{hz}$.
Finally for all $i$, $$B_i = \bigcap_{t \not = i}C_i = \bigcap_{t \not = i}Q_i^g = P_i^g.$$

Hall's Theorem

Definition For $\pi$ a set of primes, a $\pi$-group is a group whose orders is a product of prime powers taken from $\pi$.

Definition A Hall $\pi$-subgroup $H$ is a $\pi$-subgroup of $G$ where the index $|G:H|$ is a product of primes not from $\pi$.

Theorem (Hall - 1928) Let $G$ be a solvable group and $\pi$ a set of primes then

1. $G$ has a Hall $\pi$-subgroup.
2. Any two Hall $\pi$-subgroups are conjugate.
3. Any $\pi$-subgroup of $G$ is contained in a Hall $\pi$-subgroup.

proof: We will show by induction on $|G|$ that:

• (a) $G$ has a $\pi$-subgroup $H$
• (b) Any $\pi$-subgroup $L$ of $G$ is contained in a conjugate of $H$.

 (b) implies (2) and (a,b) together imply (1) since any Sylow $p$-subgroup is a $\pi$-subgroup (when $p \in \pi$) we can ensure that the order $|G:H|$ has no powers of $p$ in it.

The base case is trivial. Let $|G| = mn$ where $m$ is a product of powers of primes from $\pi$ and $n$ contains no primes from $\pi$. The case $m=1$ is trivial. We split the proof into two cases:

(Case A.a) There is a minimal normal subgroup $M$ with order dividing $m$. By earlier results $M$ is elementary abelian and a $p$-group for some $p$. Write $|M| = p^a$ so that $|G/M| = m_1 n$ where $m_1 = \frac{m}{p^a}$. By induction $G/M$ has a subgroup - which by isomorphism theorems, is of the form $H/M$ - with order $m_1$; then $H$ is a subgroup of $G$ with order $m$ this proves part (a).
(Case A.b) Given a $\pi$-subgroup $L$ we have $L M \le G$ (since $L$ is a $\pi$-group and $M$ is normal in $G$ todo: make sure this is right) and by isomorphism theorems $LM/M \simeq L/(L \cap M)$ so $LM/M$ is a $\pi$-subgroup of $G/M$. By induction it lies in some conjugate of $H/M$, say $L M/M \le (H/M)^{Mg} = H^g/M$ and so we have $L \le LM \le H^g$ gving (b).

(Case B) In this case there does not exist a minimal normal subgroup of order dividing $m$. Let $M$ be an minimal normal subgroup then it's elementary abelian and it must be a $q$-group for some prime $q | n$ (i.e. $q$ is a prime not in $\pi$). Write $|M|=q^b$ so $|G/M| = \frac{mn}{q^b} = mn_1$ with $n_1 = \frac{n}{q^b}$ and we split this into two more cases:

(Case Bi.a) Assume $n_1 > 1$, then by induction $G/M$ has a subgroup $K/M$ of order $m$ (because the index $|G/M:K/M|$ is $n_1$), $|K| = mq^b < mn$ so by induction again $K$ has a $\pi$-subgroup $H$ of order $m$ as required for (a)
(Case Bi.b) Given $L$ as before $LM/M$ is a $\pi$-subgroup of $G/M$ so by induction it lies in some conjugate of $K/M$, say $LM/M \le (K/M)^{Mg} = K^g/M$ then $L^{g-1}$ is a $pi$-subgroup of $K$ so by induction it lies in some conjugate of $H$, say $L^{g^{-1}} \le H^k$ whence $L \le H^{k g^{-1}}$ as required for (b).

(Case Bii.) The final case is when $G$ has no minimal normal subgroups of order dividing $m$ and $n_1=1$ (refer back to Case B for definition of $n_1$). Let $N/M$ be a minimal normal subgroup of $G/M$ then we know it is an elementary abelian $p$-group for some $p|m$, say $|N/M| = p^a$ then $N \unlhd G$ and $|N| = p^a q^b$.
Let $P$ be a Sylow $p$-subgroup of $N$ and write $H=N_G(P)$ by the Frattini argument $G=HN$ since $N=PM$ and $P\le H$ so $G=HPM=HM$. Let $J = H \cap M$ then $J \unlhd HM = G$ by minimality of $M$ we must have $J=1$ or $J=M$:
(Case Bii.J=M) This case is easily disposed of. $H \cap M = M$ so $M \le H$ so $G = HM = H = N_G(P)$ so $P \unlhd G$ (by normalizer facts) and some subgroup of $P$ is then a minimal normal subgroup of of $G$ whose order does divide $m$, contradiction.
(Case Bii.J=1.a) In this case $|H \cap M| = 1$ and thus $mq^b = |G| = |H||M| = q^b |H|$ so $|H| = m$ giving (a).
(Case Bii.J=1.b) Given $L$ we have (and we can form this because $M$ is a $q$ group and $L$ is a $p$-group) $LM = LM \cap G = LM \cap HM = (LM \cap H)M$ (by the ABC lemma). Now $LM \cap H$ is a $\pi$-subgroup of $LM$ and $$|LM:LM\cap H| = |(LM\cap H)M|/|LM\cap H| = |M|/|LM \cap H \cap M| = |M|$$ therefore it is in fact a Hall $\pi$-subgroup so if $LM<G$ we are done by induction. It only remains to deal with the case where $LM=G$: in this case since $L \cap M = 1$ by coprime orders, $|G|=|L||M|$ implying $|L| = m$. Since $M \le N$ (since $M \unlhd N$ from the fact the quotient makes sense) $LN = G$ and thus $|L \cap N| = |L||N|/|G| = p^a$ so by Sylow's theorem $L \cap N$ is conjugate to $P$ ($L = P^n$ for some $n \in N$). $L \cap N \unlhd L$ since $N \unlhd G$ so $$L \le N_G(L \cap N) = N_G(P^n) = N_G(P)^n = H^n$$ giving (b).

Thus we have (a) and (b) for all groups, this implies (i) and (ii). For (iii) let $K$ be any Hall $\pi$-subgroup of $G$ by (b) we know that $K \le H^g$ for some $g \in G$, since $|H|=|K|$, $K=H^g$.