\documentclass{article}
\usepackage{amsmath,amssymb}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
\newcounter{lecnum}
%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
  \pagestyle{myheadings}
  \thispagestyle{plain}
  \newpage
  \setcounter{lecnum}{#1}
  \setcounter{page}{1}
  \noindent
  \begin{center}
    \framebox{
      \vbox{\vspace{2mm}
        \hbox to 6.28in { {{\bf 18.317~Combinatorics, Probability, and
  Computations on Groups} \hfill #2} }
        \vspace{4mm}
        \hbox to 6.28in { {\Large \hfill Lecture #1  \hfill} }
        \vspace{2mm}
        \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
        \vspace{2mm}}}
  \end{center}
  \markboth{Lecture #1: #2}{Lecture #1: #2}
  \vspace*{4mm}
}

\input{epsf}
%usage: \fig{LABEL}{FIGURE-HEIGHT}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
        \begin{figure}
        \setlength{\epsfysize}{#2}
        \centerline{\epsfbox{#4}}
        \caption{#3} \label{#1}
        \end{figure}
        }

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}}

\def\E#1{{\rm E}[#1]}
\def\i{\hspace*{5mm}}
\newcounter{lineno}
\setcounter{lineno}{0}
\def\n{\addtocounter{lineno}{1} \hbox to 7mm{\hfill \arabic{lineno}:}\hspace{2mm}}
\def\resetn{\setcounter{lineno}{0}}
\def\tqbfk{\tqbf_k^\exists}
\def\ep{\epsilon}
\def\erd{Erd\H{o}s}

\begin{document}
\lecture{3}{12 September 2001}{Igor Pak}{T. Chiang}

\section*{Probabilistic Generation}
In this lecture, we will prove the following Theorem with
contemporary mathematics:
\begin{theorem}{\bf (Dixon)}
\begin{equation}
Pr(\langle\sigma_1, \sigma_2\rangle\mbox{ = $A_n$ or $S_n$ }) \rightarrow \mbox{1 as $n$} \rightarrow \infty.
\end{equation}
\end{theorem}

We first recall that a simple group G is a group with no proper
normal subgroups. Let G be simple; then the following proposition is
valid:

\begin{proposition}
\begin{equation}
\varphi_k (G) \leq 1 - \sum_{M} \frac{1}{[G:M]^k} = 1 - \sum_{M \subset
\mu} \frac{1}{[G:M]^{k-1}},
\end{equation}
where $M$ is a maximal subgroup of $G$ and $\mu$ is the conjugacy
classes of $M$.
\end{proposition}



\begin{proof}
It is clear that $1 - \varphi_k (G) \leq \sum_{M}
\frac{1}{[G:M]^k}$. Now, because $M$ is the maximal subgroup of $G$,
we can define $N_G(M)$ as the maximal subgroup of $G$ such that $M
\triangleleft G$. The only solution must be in the set $\{M, G\}$, and
since $G$ is simple, this implies that $N=M$. Now if we define the
term $M^G = gMg^-1$ as the conjugacy class of $M$, we can readily
verify that $|\{M^G\}| = \frac{|G|}{|N_G(M)|} = [G:M]$.
\end{proof}

\begin{theorem}
{\bf (O'nan -Scott)} \
Let $G \subset S_n$ be primitive. Then $G$ is

A. Affine \\
B. Product Type\\
C. Diagonal Type\\
D. Almost Simple
\end{theorem}
\begin{proof}
Implicit from the Classification of Finite Simple Groups.
\end{proof}


From here we deduce Theorem~1.

\begin{proof}
We begin with some Group Theoretic terminology. First we suppose that
$G \subset S_n$ and that $G = \{\sigma_1 \ldots \sigma_k\}$. We call a
group $G$ - transitive if $\forall i,j \in \{i \ldots n\}$ then there
exists an element $\sigma \in G$ such that $\sigma(i) = j$. Next we
call a group $G$ - primitive if the following occur:

$(R_1)(R_2) \cdots (R_m)$

where $|R_i| = d$ and $n=md$ so that $\forall \sigma \in G; \mbox{ }
\forall i,j \in R_\alpha, \mbox{ there exists } \beta : \sigma(i),
\sigma(j) \in R_\beta$. Now if we use the O'nan-Scott Theorem with
these two facts, we see that the 4 properties of $G$ are exactly the
conjugacy classes which gives us the proof to the theorem.
\end{proof}

We also give another Theorem concerning the number of conjugacy
classes of the maximal subgroups of $S_n$.

\begin{theorem}{\bf (Liebeck-Shalev)} \
The number of conjugacy classes of maximal subgroups of $S_n$ is of
the order: $\frac{n}{2} (1 + O(1))$.
\end{theorem}


From here we can also deduce Theorem~1 :

\begin{proof}
First we preface the proof by noting that the maximal subgroups of
$S_n$ are of the form $S_k \times S_{n-k}$ for $ k \leq
\frac{n}{2}$. First we see that
\begin{eqnarray*}
\varphi_2(A_n) &\geq& 1 - \sum_{M \subset \mu} \frac{1}{[G:M]} \\
&=& 1 - \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor}
\frac{1}{\binom{n}{k}} + O(\frac{1}{e^{cn}}) \\
&=& 1 - \frac{1}{n} + O(\frac{1}{n^2}).
\end{eqnarray*}
\end{proof}

We end this lecture with an example and a corollary.

Suppose that $G = PSL(2,p)$ - simple. Then

\begin{equation}
|G| = \frac{1}{2(p-1)} (p^2-1)(p^2 - p) = \frac{p(p-1)(p+1)}{2}.
\end{equation}

Now if $H$ is a maximal subgroup in $PSL(2,p)$, then $H$ has the form

\begin{equation}
H = \left\{\left(\begin{matrix} a \mbox{   } b \\ 0 \mbox{   } c \end{matrix}\right) : ac = 1\right\}
\end{equation}

Thus $|H| = \frac{p(p-1)}{2}$. So we see that $[G:H] = p+1$ which is
roughly $p$. It was never shown, but is told to be true that the
number of conjugacy classes of maximal subgroups is $\leq 7$ when the
index $\geq p$. Hence $\varphi_2 > 1 - \frac{7}{p}$.

\begin{corollary}
As $p \rightarrow \infty$, \ $\varphi_2\left(PSL(2,p)\right) \rightarrow 1$.
\end{corollary}
\end{document}