\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 }

%The scribe includes the following commands (BR.)
\newcommand{\rg}{\langle \sigma_1, \sigma_2 \rangle}

\begin{document}
\lecture{4}{14 September 2001}{Igor Pak}{Ben Recht}

Even if a paper is famous and written by very famous individuals, that
does not necessarily mean that it is correct.  In this lecture, we
will look at a proof of the probabilistic generation of $S_n$ by
Dixon, based on results of \erd and Turan. Then we discuss the lemmas
which they proved incorrectly in their paper.

Our goal will be to prove

\begin{theorem}
\[
    Pr(\rg \mbox{ = $A_n$ or $S_n$ })\rightarrow 1
    \mbox{ as }n\rightarrow\infty
\]
\end{theorem}

The idea of the proof is a follows.  First we will prove that the
probability that $\rg$ is primitive goes to $1$ as $n$ goes to
infinity.  Next, we can show that the probability that $\rg$ contains
a cycle of length $p$, where $p$ is a prime less than $n-3$ also goes
to 1 as $n$ goes to infinity.  Then the theorem follows immediately by
the following result of Jordan

\begin{theorem}{\bf (Jordan 1873)}
If $G\leq S_n$ is primitive and contains a cycle of length $p$ where
$p$ is a prime less than $n-3$ the $G$ is equal to $A_n$ or $S_n$.
\end{theorem}

The proof of Jordan's theorem can be found in many classic texts on
group theory.

We'll proceed with the following
\begin{lemma}
$Pr(\rg \mbox { is transitive}) = 1 - \frac{1}{n}+O(\frac{1}{n^2})$
\end{lemma}
\begin{proof}
Let $p=Pr(\rg \mbox { is transitive})$.  Then
\begin{eqnarray*}
  1-p & < & \sum_{k=1}^{n/2}\binom{n}{k} Pr(\sigma_1 \mbox{ and } \sigma_2
      \mbox{ fix blocks of size } k \mbox{ and } n-k) \\
      & = & \sum_{k=1}^{n/2}\binom{n}{k} \frac{1}{\binom{n}{k}^2}\\
      & = & \sum_{k=1}^{n/2}\frac{1}{\binom{n}{k}} \\
      & = & \frac{1}{n}+O(\frac{1}{n^2})\\
\end{eqnarray*}
\end{proof}

We'll now prove a result about when $\rg$ is primitive.

\begin{theorem}
$Pr(\rg \mbox{ is imprimitive})=O(\frac{n}{2^{n/4}})$
\end{theorem}
\begin{proof}
The probability that $\sigma$ has a fixed block structure with block
size $d$ ($md=n$) is equal to $\frac{d!^m m!}{n!}$ as we can permute
the blocks and the elements within the blocks.  The number of block
structures with block size $d$ is equal to
\[
    \frac{\binom{n}{d \ldots d}}{m!}=\frac{n!}{d!^m m!}
\,.
\]
Here is is clear that the multinomial coefficient is over $m$ $d$'s.

Now
\begin{eqnarray*}
    Pr(\rg \mbox{ is imprimitive})
        & < & \sum_{d\mid n} \frac{n!}{d!^m m!} \left( \frac{d!^m m!}
          {n!}\right)^2 \\
        & < & \sum_{m=2}^{n/2} \frac{(\frac{n}{m})!^m m!}{n!} \\
        & = & \frac{(n/2)!2^n}{n!}+\ldots+\frac{2! (n/2)!^2}{n!}
\end{eqnarray*}
The last term in this sum is a dominating term, there are $n/2$ such
terms and $\binom{n}{n/2}>2^{n/2}$, thus completing the proof.
\end{proof}

\begin{corollary}
$Pr(\rg \mbox{ is primitive })=1-\frac{1}{n}+O(\frac{1}{n^2})$
\end{corollary}

We now will attempt to prove
\begin{theorem}
Let $\sigma \in S_n$ and $p$ be a prime less than $n-2$.  Then
$Pr(\sigma=\sigma_p\prod_i \gamma_i)$, where $\sigma_p$ is a $p$-cycle
and $\gamma_i$ are $c_i$-cycles with $p \nmid c_i$, goes to $1$ as $n$
goes to infinity.
\end{theorem}

This result will imply Dixon's theorem.  To prove this result, we will
prove the following two lemmas next time.

\begin{lemma}{(\bf \erd-Turan)}  Let $1 \leq a_1 \leq a_2 \leq a_r \leq n$.
Then
\[
    Pr(\sigma\in S_n \mbox{ does not contain any cycles of length } a_i)
    \leq \sum_{i=1}^r\frac{1}{a_i}
\,.
\]
\end{lemma}

\begin{lemma}
Let $\sigma \in S_n$ and $p<n$ be a prime.
Then $Pr(p \nmid \mbox{order}(\sigma))=\prod_{k=1}^{n/p}(1-\frac{1}{pk})$.
\end{lemma}


\erd and Turan published a famous proof of these lemmas.
We will construct correct
proofs in the next lecture.

\end{document}