\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{6}{21 September 2001}{Igor Pak}{C. Goddard}

\section*{Probabilistic Generation}
In this lecture, we will complete the classical proof for Dixon's theorem on the probabilistic generation of $S_n$, based on the work by \erd\ and Tur\'{a}n.  Reiterating from the previous lectures, here is Dixon's theorem:

\begin{theorem}{\bf (Dixon)}
\label{Dixon}
\[ \Pr(\langle\sigma_1, \sigma_2\rangle = A_n \mbox{ or } S_n) \rightarrow \mbox{1 as $n$} \rightarrow \infty. \]
\end{theorem}

We will use Lemma \ref{Lemma1}, proved last lecture, and Jordan's theorem (Theorem \ref{Jordan}) and combine them with Lemma \ref{Lemma2}, proved here, to prove Dixon's theorem (Theorem \ref{Dixon}) classically.

Thus, Lemma \ref{Lemma1} and Jordan's theorem are merely stated here:

\begin{lemma}{\bf (\erd-Tur\'{a}n)}
\label{Lemma1}
Let $1 \leq a_1 < a_2 < 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{theorem}{\bf (Jordan 1873)}
\label{Jordan}
If $\ G \subset 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}

Now continuing from the previous lecture, we will prove the following lemma.

\begin{lemma}{\bf (\erd-Tur\'{a}n)}
\label{Lemma2}
For a fixed prime $p$ (or prime power),
\[ \Pr (\sigma \in S_n, p \nmid \mathrm{order}(\sigma)) = \prod^{\lfloor \frac{n}{p} \rfloor}_{i=1} \left(1 - \frac{1}{p \cdot i} \right) \]
\end{lemma}

\begin{proof}
Let \[ z_{\lambda} = \frac{n!}{1^{m_1} \, m_1! \, 2^{m_2} \, m_2! \, \ldots} = \mbox{ \# elements in conjugacy class } (\lambda) \]
where $\lambda =  (1^{m_1} 2^{m_2} \ldots)$ and $\sum m_i \cdot i = n $.

Now
\begin{eqnarray*}
1 = \sum_{\lambda \vdash n} \frac{z_{\lambda}}{n!} & = & \mbox{coeff } [t^n]
\prod_{i=1}^{\infty} \left(1 + \frac{t^i}{1! \cdot i} + \frac{t^{2i}}{2! \cdot i^2}
+ \frac{t^{3i}}{3! \cdot i^3} + \ldots\right)  \\
\Pr(\sigma \in S_n, p \nmid \mathrm{order}(\sigma)) & = & \mbox{coeff } [t^n]
\prod_{i=1, \ p \nmid i}^\infty \left(1 + \frac{t^i}{1! \cdot i} + \frac{t^{2i}}{2! \cdot i^2}
+ \frac{t^{3i}}{3! \cdot i^3} + \ldots \right)
\end{eqnarray*}
$ \mbox{Now denote  } \Pi = 1 + \frac{t^i}{1! \cdot i} +
\frac{t^{2i}}{2! \cdot i^2} + \frac{t^{3i}}{3! \cdot i^3} + \ldots $
\begin{eqnarray*}
\mbox{So  } \Pi & = & \prod_{p \nmid i, i = 1}^\infty \exp \left( \frac{t^i}{i} \right) \; (\mbox{since } e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \ldots ) \\
& = & \frac{\prod_{i = 1}^{\infty} \exp \left( \frac{t^i}{i} \right)}{\prod_{\alpha = 1}^{\infty} \exp \left( \frac{t^{p \alpha}}{p \alpha} \right)} \\
& = & \exp \left(\sum_{i = 1}^{\infty} \frac{t^i}{i} - \sum_{\alpha = 1}^{\infty} \frac{t^{\alpha p}}{\alpha p} \right) \\
& = & \exp \left(-\log(1 - t) + \frac{1}{p} \log(1 - t^p) \right) \; (\mbox{using } -\log(1-x) = x + \frac{x^2}{2} + \frac{x^3}{3} + \ldots ) \\
& = & \frac{(1 - t^p)^{\frac{1}{p}}}{1 - t} \\
& = & \frac{1 - t^p}{1 - t} \cdot (1 - t^p)^{\frac{1}{p} - 1} \\
& = & \frac{1 - t^p}{1 - t} \cdot \left(\frac{1}{1 - t^p}\right)^{1 - \frac{1}{p}} \\
& = & (1 + t + \ldots + t^{p - 1}) \cdot \left\{ 1 + \sum_{m = 1}^{\infty} t^{mp} \cdot \left(1 - \frac{1}{p}\right)\left(1 - \frac{1}{2p}\right) \cdot \ldots \cdot \left(1 - \frac{1}{mp}\right) \right\} \\
\end{eqnarray*}
(Note: $(1 + x)^{\alpha} = 1 + \frac{\alpha}{1!} x + \frac{\alpha (\alpha - 1)}{2!} x^2 + \ldots$ )

So to find coeff[$t^n$], take $m = \lfloor \frac{n}{p} \rfloor$ above, and we're done.
\end{proof}

Now we are ready to prove Dixon's theorem (Theorem \ref{Dixon}).

\begin{proof}
$\Pr (\sigma \mbox{ has } p - \mbox{cycle}) \longrightarrow 1 \mbox{  as } n \rightarrow \infty, p < n-2 \;.$

Let $A = \{ \log^2 n < p < n-2, p\ - \mbox{prime} \}$.

Using Lemma \ref{Lemma1},

$\Rightarrow \Pr (\sigma \mbox{ has no } A\ - \mbox{cycles})$ \begin{eqnarray*}
\leq \frac{1}{\sum_{p = \log^2 n}^{n - 2} \frac{1}{p}} & \sim & \frac{1}{\log \log (n - 2) - \log \log (\log^2 n)} \\
& & (\mbox{Using Euler's theorem: } \sum_{p < x} \frac{1}{p} \sim \log \log x ) \\
& \sim & c \cdot (\log \log n)^{-1} \mbox {  where c is a constant }
\end{eqnarray*}
$\Rightarrow  \mbox{ with } \Pr > 1 - \frac{c}{\log \log n} \ ,\; \exists\ p\ - \mbox{cycle with } p \in A \mbox{ for some prime } p\;. $

Now from Lemma \ref{Lemma2}, since $p > \log^2 n$, we have:
\begin{eqnarray*}
& & \Pr(\sigma \ \text{contains exactly one $p$-cycle} \, | \,
\sigma \ \text{contains at least one $p$-cycle})
= \prod_{i = 1}^{n - p} \left( 1 - \frac{1}{p \cdot i} \right) \\
& \qquad & > \exp\left(\sum_{i=1}^{n} \log \left( 1 - \frac{1}{p \cdot i}
\right)\right) = \exp\left(-\sum_{i=1}^{n} \frac{1}{p \cdot i}
+ \mathrm{o}(1) \right)
= \exp \left( \frac{-\log n + \log p + \mathrm{o}(1)}{p} \right)
\\ & \qquad & >  \exp \left(\frac{-\log n}{p}\right) 
 > \exp \left(\frac{-1}{\log n}\right) >  1-\frac{1}{\log n}
\end{eqnarray*}
\end{proof}

Finally, for the $\Pr$ as in  Theorem~1, we obtain
$$\qquad \qquad \qquad \qquad \qquad \qquad
\Pr > \left(1 - \frac{c}{\log \log n}\right)
\left(1-\frac{1}{\log n}\right) \to 1 \ \  \text{as} \ \ n \to
\infty \qquad \qquad \ \qquad \qquad \qquad \qquad  \blacksquare$$
\end{document}