\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage[dvips]{color}

\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\rhd{\supset}
\def\qed{\thinspace\nobreak \vrule width 7pt height 5.5pt depth 1.5pt}

\begin{document}
\lecture{15}{15 October 2001}{Igor Pak}{Fumei Lam}

\section*{Hall Bases}

\begin{definition} Let $H$ be an abelian $p$-group.  A set $B = \{ b_1.
b_2, \ldots b_r \} \subseteq H$ is a Hall basis if \\ $\forall h \in H,
\ \exists \, \alpha_1, \alpha_2, \ldots \alpha_r \in \{ 0, 1, \ldots p-1
\}$ such that $h = b_1^{\alpha_1}b_2^{\alpha_2}\ldots b_r^{\alpha_r}$.
\end{definition}

The following lemma shows that for a Hall basis $B$, the distribution of
$B^{\overline{\alpha}}$ over $\overline{\alpha}$ is uniform in $H$.

\begin{lemma} If $B = \{ b_1, b_2, \ldots b_r \}$ is a Hall basis in $H$,
then $$ Pr_{\overline{\alpha}} ( b_1^{\alpha_1}b_2^{\alpha_2}\ldots
b_r^{\alpha_r} = h ) = \frac{1}{\vert H \vert} \ \ \forall \, h \in H$$
\end{lemma}

\begin{proof} Consider $H$ as a vector space.  Since $B$ is a Hall basis,
it is a spanning set and contains a basis, say $b_1, b_2, \ldots b_k$.
Then for uniform $\alpha_i \in \{ 0, 1, \ldots p-1 \}$ , we have

$$ \underbrace{ b_1^{\alpha_1} b_2^{\alpha_2} \ldots b_k^{\alpha_k}
}_{\mbox{uniform in $H$}}  b_{k+1}^{\alpha_{k+1}}
b_{k+2}^{\alpha_{k+2}} \ldots b_r^{\alpha_r}, $$

\noindent which is uniform in $H$.

\end{proof}


\vspace{3ex}

Recall that $G$ is nilpotent if some $G_l$ in the lower central series

$$G = G_0 \rhd G_1 \rhd G_2 \rhd G_3 \rhd \cdots \rhd G_l = \{1\}$$

\noindent is the identity element (where $G_i = [ G_{i-1}, G ]$ for $i =
1, 2, 3 \ldots$).

Let $H_i = G_{i-1} / G_i $ and let $\gamma_i: G_{i-1} \rightarrow H_i$
denote the standard map of $G_{i-1}$ onto the cosets of $G_i$.  From last
time, if $\psi_i : H_i \rightarrow G_{i-1}$ is a map such that
$\gamma_i(\psi_i(h)) = h$ for all $h \in H$, then we have the following
lemma.

\begin{lemma} For $h_i$ uniform in $H_i$ and $g_i$ uniform in $G_{i}$,
$\psi(h_i)g_i$ is uniform in $G_{i-1}$. \end{lemma}

\vspace{2ex}

In what follows, we will assume $G$ is nilpotent with $G = G_0 \rhd G_1
\rhd G_2 \rhd \ldots \rhd G_l = \{ 1 \}.$

\newpage

\begin{definition} Let $\overline{B} = (B_1, B_2, \ldots B_l)$, $B_i
\subset G_{i-1}$.  $\overline{B}$ is a Hall basis if $\gamma_i(B_{i+1})$
is a Hall basis of $H_{i+1}$ for all $i = 0, 1, \ldots l-1$.
\end{definition}

\begin{lemma} Let $\overline{B} = (B_1, B_2, \ldots B_l), B_i = \{
b_{i_1}, b_{i_2}, \ldots b_{i_{r_i}} \}$, and suppose $\alpha_{ij}$ is
uniform in $\{ 0, 1, \ldots p-1 \}$.  Then

$$g = \prod_{i= 1,2, \ldots l}^{\rightarrow} \prod_{j = 1, 2, \ldots
r_i}^{\rightarrow} b_{ij}^{\alpha_{ij}}$$

\noindent is uniform in $G$, where $\prod\limits_{i = 1,
2, \ldots l}^{\rightarrow} $ denotes the product in the order $1,2 \ldots
l$.

\end{lemma}

\begin{proof} Note that since $\overline{B}$ is a Hall basis, $g$ can be
written as $g = g_1 g_2 \ldots g_l$ with $g_i \in G_{i-1}$ and $h_i =
\gamma_i(g_i)$ uniform in $H_i$.

Since $H_l = G_{l-1}$, $h_l = \gamma_l(g_l) = g_l$ is uniform in
$G_{l-1}$.  Furthermore, $h_{l-1} = \gamma_{l-1}(g_{l-1})$ is uniform in
$H_{l-1}$ and by the previous lemma, this implies $g_{l-1}g_l$ is uniform
in $G_{l-2}$.  Continuing by induction, we obtain $g = g_1 g_2 \ldots g_l$
is uniform in $G_0 = G$.  \end{proof}

In fact, the lemma remains true even if we remove the restriction on the
product order of the $b_{ij}$, as we will show in the following theorem.

\begin{definition} Let $\Lambda = \{ (i,j): i = 1, 2, \ldots l, j = 1,
2, \ldots r_i \}$.  A word $w$ in $b_{ij}, (i,j) \in \Lambda$ is complete
if $b_{ij}$ occurs in $w$ for all $(i,j) \in \Lambda$. \end{definition}

\begin{theorem}  If $\overline{B}$ is a Hall basis and $w$ is a complete
word, then $w^{\overline{\alpha}}$ is uniform in $G$.
\end{theorem}

\begin{proof} First, consider all the elements $b_{l*} \in B_l$ in $w$.
Since $B_l \subseteq G_{l-1}$, and $G_{l-1}$ is contained in the center of
$G$, each element $b_{l*}$ commutes with all other elements in the word
$w$ and we can express $w$ as

$$w = * * \cdots *
\underbrace{\fbox{\phantom{hello}}}_{B_l}.$$

Now, observe that if $a \in B_i, b \in B_j$, then $ab \in ba [a^{-1},
b^{-1}]$ with $[a^{-1}, b^{-1}] \in G_c$ for some $c > i,j$.  So we can
move all the elements $b_{l-1*} \in B_{l-1}$ in $w$ to the right and write
$w$ in the form

$$w = * * \cdots * \underbrace{\fbox{\phantom{hello}}}_{B_{l-1}}
\fcolorbox[gray]{1}{.5}{\phantom{hi}}
\underbrace{\fbox{\phantom{hello}}}_{B_l},$$

\noindent where the shaded box represents a product of terms in $G_{l-1}$
accumulated by commuting the elements $b_{l-1*}$.

\newpage

Continuing in this way, we obtain

$$w = \underbrace{\fbox{\phantom{hello}}}_{B_1}
\fcolorbox[gray]{1}{.5}{\phantom{hi}}
\underbrace{\fbox{\phantom{hello}}}_{B_2}
\ldots
\fcolorbox[gray]{1}{.5}{\phantom{hi}}
\underbrace{\fbox{\phantom{hello}}}_{B_{l-1}}
\fcolorbox[gray]{1}{.5}{\phantom{hi}}
\underbrace{\fbox{\phantom{hello}}}_{B_l}.$$

Since each of the products in $B_i$ corresponds to a uniform element in
$H_i$ under $\gamma_i$, we have

$$w =
\underbrace{
    \fbox{\phantom{hello}}
    \hspace{.3ex}
    \fcolorbox[gray]{1}{.5}{\phantom{hi}}
    \hspace{.2ex}
    \fbox{\phantom{hello}}
    \ldots \ldots
    \underbrace{
        \fcolorbox[gray]{1}{.5}{\phantom{hi}}
        \hspace{.4ex}
        \fbox{\phantom{hello}} \hspace*{-1.5ex}
        \underbrace{ \fcolorbox[gray]{1}{.5}{\phantom{hi}}
                 \hspace{.4ex}
                 \fbox{\phantom{hello}}
               }_{ \text{uniform in $G_{l-1}$} }
          }_{ \text{uniform in $G_{l-2}$} }
    }_{ \text{uniform in $G_0 = G$} },$$

proving the theorem.

\end{proof}


\end{document}