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

\def\ZZ{\mathbb{Z}}

\begin{document}
\lecture{2}{10 September 2001}{Igor Pak}{Jason Burns}

\section*{The probability of generating a group, part 2}

Some notation from last time:

Let $G$ be a group.  We will write $\varphi_k(G)$ for the probability that
$k$ random elements of $G$ generate the entire group.  (We assume that
all the elements are chosen independently, and each group element is
equally likely.)  For example, $\varphi_1(G)\neq 0$ if and only if
$G$ is cyclic.

We also define $\ell(G)$ as the length of the longest subgroup chain in G;
that is, $\ell(G)$ is the largest $\ell$ such that
\[ {1} = G_0 \subsetneq G_1 \subsetneq \cdots \subsetneq G_{\ell} = G. \]

Yesterday%
\footnote{Last Friday, actually, but it \emph{feels} like only yesterday.}
we proved that, if $|G|\leq 2r$ (or even if we only have $\ell(G)\leq r$),
then $\varphi_k(G)\geq\varphi_k(\ZZ_2^r)$.

Today, we'll estimate $\varphi_k(\ZZ_2^r)$.  We argued last time that
this was the worst possible case (that is, $\varphi_k(G)\geq \varphi_k(\ZZ_2^r)$
whenever $|G|\leq 2^r$), so this immediately leads to a lower bound for
$\varphi_k(G)$ \dots

\begin{theorem}
Let $G=\ZZ_2^r$.  Then
$\varphi_r(G) > \frac{1}{4}$, $\varphi_{r+1}(G) > \frac{1}{2}$,
and in general $\varphi_{r+j}(G) > 1 - \frac{c}{2^j}$ for some constant $c$.
\end{theorem}

To make our estimate, we'll use two famous identities of Euler (1748):
\[ \prod_{j=1}^\infty(1-z^j) =
   1 + \sum_{m=1}^\infty (-1)^m (z^\frac{m(3m-1)}{2} + z^\frac{m(3m+1)}{2}) \]
and
\[ \prod_{j=0}^\infty \frac{1}{1-tz^j} =
   1 + \sum_{m=1}^\infty  \frac{t^m}{(1-z)(1-z^2)\cdots(1-z^m)}. \]

\subsection*{Proof of Theorem 1}

One way of visualizing $\varphi_k(\ZZ_2^r)$ is as follows.  Consider $\ZZ_2^r$
as an $r$-dimensional vector space over the two-element field $\ZZ_2$.
Then we're asking for the probability that a given set of $k$ vectors
span the whole space of $r$ dimensions.  Or, put in another way,

\[ k \Biggl\{ \underbrace{ \left[ \begin{array}{llll}
      a_1, & a_2, & \cdots, & a_r \\
      b_1, & b_2, & \cdots, & b_r \\
           & \cdots \\
      z_1, & z_2, & \cdots, & z_r
   \end{array} \right]
   }_r     %end underbrace, put `r' underneath
%      \right.
\]

if we make a matrix out of our $k$ vectors, what is the probability that
matrix has rank $r$? --- Just when all $r$ of the columns are independent,
of course.

\[ k \Biggl\{ \underbrace{ \left[ \begin{array}{llll}
      a_1 & a_2 & & a_r \\
      b_1 & b_2 & & b_r \\
      \vdots & \vdots & \vdots  & \vdots \\
      z_1 & z_2 & & z_r
   \end{array} \right]
   }_r     %end underbrace, put `r' underneath
%     \right.
\]

The probability that the first column is nonzero is $(1-\frac{1}{2^k})$.
The probability that the second column is linearly independent of the
first row is $(1-\frac{1}{2^{k-1}})$.  In general, the probability that
the $j$-th column is linearly independent of the previous $j-1$ columns
is $(1-\frac{2^{j-1}}{2^k})$, and hence the probability that all the columns
are linearly independent is
$\varphi_k(\ZZ_2^r) = \prod_{j=1}^r (1-\frac{2^{j-1}}{2^k})$.

Now, we already know that $\ZZ_2^r$ cannot be generated by fewer than
$r$ elements, and indeed $\varphi_k(\ZZ_2^r) = 0$ for $k<r$, according to the
formula we've just derived. How about for $k=r$? Then we have the estimate
\newsavebox{\whattabox}
\sbox{\whattabox}{
  $ \underbrace{ 1-\frac{1}{2^1}-\frac{1}{2^2} }_{ =\frac{1}{4} } +
    \underbrace{ \frac{1}{2^5}+\frac{1}{2^7}-\frac{1}{2^{12}} -
    \frac{1}{2^{15}}+\cdots }_{>0} $
}

\begin{equation*}
\begin{split}
\varphi_r(\ZZ_2^r) & = (1-\frac{1}{2^r})(1-\frac{1}{2^{r-1}})
     \cdots (1-\frac{1}{2}) \\
                & > \prod_{j=1}^\infty (1-\frac{1}{2^j}) \\
                & = \usebox{\whattabox} \\
%    \underbrace{ 1-\frac{1}{2^1}-\frac{1}{2^2} }_{ =\frac{1}{4} } +
%    \underbrace{ \frac{1}{2^5}+\frac{1}{2^7}-\frac{1}{2^12} -
%       \frac{1}{2^15}+\cdots }_{>0}
%    }  \\
                & > \frac{1}{4}.
\end{split}
\end{equation*}

Did you notice how we used one of Euler's famous identities
in the third line?

One down, two to go.
For $\varphi_{r+1}(\ZZ_2^r)$, we just mimic the previous argument.
\begin{equation*}
\begin{split}
  \varphi_{r+1}(\ZZ_2^r) & = (1-\frac{1}{2^{r+1}})(1-\frac{1}{2^r})
                \cdots (1-\frac{1}{2^2}) \\
            & > \prod_{j=2}^\infty (1-\frac{1}{2^j}) \\
            & = (1-\frac{1}{2})^{-1} \prod_{j=1}^\infty (1-\frac{1}{2^j}) \\
            & = 2 \prod_{j=1}^\infty (1-\frac{1}{2^j}) \\
            & > 2 \cdot \frac{1}{4} \\
            & = \frac{1}{2}.
\end{split}
\end{equation*}

We'll use a different estimate for the general case.

\begin{equation*}
\begin{split}
  \varphi_{r+k}(\ZZ_2^r) & = (1-\frac{1}{2^{r+k}}) (1-\frac{1}{2^{r+k-1}})
              \cdots (1-\frac{1}{2^{k+1}}) \\
            & > \prod_{j=1}^\infty (1-tz^j) \qquad
              \text{ (let $t=\frac{1}{2^k}$ and $z=\frac{1}{2}$) } \\
            & = ( 1+\sum_{m=1}^\infty
              \frac{t^m}{(1-z)(1-z^2)\cdots(1-z^m)} )^{-1}
\end{split}
\end{equation*}

Now, to get a lower bound on this, we need an upper bound on the
quantity in parentheses.  The denominator of the sum might look familiar
--- it's just $\varphi_m(\ZZ_2^m) = (1-z)(1-z^2)\cdots(1-z^m)$,
which we already determined was at least $\frac{1}{4}$.

\begin{equation*}
\begin{split}
  1+\sum_{m=1}^\infty \frac{t^m}{\varphi_m(\ZZ_2^m)}
            & < 1+4\sum_{m=1}^\infty t^m \\
            & < 1+4\frac{t}{1-t} \\
            & = 1+4\frac{\frac{1}{2^k}}{1-\frac{1}{2^k}} \\
            & < 1+4\frac{\frac{1}{2^k}}{\frac{1}{2}} \\
            & = 1+\frac{8}{2^k} \\
\end{split}
\end{equation*}

Hence
\[ \varphi_{r+k}(\ZZ_2^r) > \frac{1}{1+\frac{8}{2^k}} > 1-\frac{8}{2^k}.\]
You can, of course, make a better estimate.

\subsection*{Random Group Processes:  Loose Ends}

We can turn this around, and ask what the probability is that the
elements we pick \emph{don't} generate a group.
Let $\delta(t) = 1 - \varphi_t(G)$, where $G$ is (as usual) a finite group.
Obviously $\delta(t+1)\leq\delta(t)$, and in general $\delta(t+s)\leq
\delta(t)\delta(s)$ since we're picking each element independently.
So $\delta$ is submultiplicative, it decays exponentially%
\footnote{The exponent turns out to be the smallest index of a proper
subgroup of $G$.}, and
if you've been paying attention you should be able to estimate when
$\delta$ first drops below~$\frac{1}{2}$.

Yet another way of posing this question, as you may recall from last
lecture, is to ask how many elements we have to pick to generate $G$.
Recall that we defined the \emph{stopping time} $\tau$ to be the
number of elements we have to pick, one at a time, to generate $G$.
Of course, it depends on which elements we pick, but we can estimate it.

\begin{proposition}
$E(\tau)=\sum_{\tau=0}^\infty \delta(\tau)$.
\end{proposition}

\begin{proof}
$\sum_{t=0}^\infty \delta(t) = \sum_{t=0}^\infty \Pr(\tau > t)
  = \sum_{t=0}^\infty t \cdot \Pr(\tau=t) = E(t)$.
\end{proof}

We know $E(\tau)$ in terms of $\delta$, and we know $\delta$ in terms of
$\varphi_k(G)$, and we have the estimate $\varphi_{k+r}(G) > 1 - \frac{8}{2^k}$
from above.  So we can estimate $E(\tau)$:

\begin{corollary}
For any group $G$, $E(\tau) \leq \ell(G)+C$, where $C$ is a constant.
\end{corollary}

\begin{proof}
The worst possible case for a given $r=\ell(G)$ is $\ZZ_2^r$, and in
that case, $\varphi_{k+r}(H) > 1-\frac{8}{2^k}$, as we proved earlier today.
So $\delta_{m+k}(G)$ is less than $\frac{8}{2^k}$, and
$E(\tau) < r + \sum_{k+1}^\infty \frac{8}{2^k} = r + 8$.
\end{proof}

\subsection*{Next time \ldots}

Babai proved that two random elements of $S_n$ generate either $A_n$ or
$S_n$, with probability $1 - \frac{1}{n} + O(\frac{1}{n^2})$%
\footnote{Dixon proved the weaker result $1 - O(\frac{1}{(\log\log n)^2})$.}.

Tomorrow we'll prove that, using classification of the finite simple groups.

(Where does the $\frac{1}{n}$ come from?, you may ask.  Well, let's suppose
that the two permutations never mix some of the $n$ elements --- that they
permute $k$ elements, and the other $n-k$ separately.  Specifically, if they
both fix a point, that gives rise to our $\frac{1}{n}$ term.  (Only one pair
in $n^2$ fixes a given point under both permutations --- but there are $n$
points to choose from.  Hence $\frac{1}{n}$.))

\end{document}
