\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{18}{22 October 2001}{Igor Pak}{Christopher Malon}

\section*{Testing Solvability and Nilpotence}

\subsection*{How to Reduce Generating Sets}

Let $G = \left< g_1, \ldots, g_k \right>$, and consider
a random subproduct $h = g_1^{\epsilon_1} \cdots g_k^{\epsilon_k}$,
where the $\epsilon_i \in \{ 0, 1 \}$ are chosen independently, uniformly.
Last time, we showed:

\begin{lemma}
If $H < G$ is a proper subgroup, then ${\mathrm Pr} (h \notin H) \geq
\frac{1}{2}$.
\label{lem:main}
\end{lemma}

From the first lecture of the semester, we know that a nonredundant
generating set cannot have more than $\log_2 \vert G \vert$ elements.
Let $L$ be an upper bound on $\log_2 \vert G \vert$, and $c$ be a constant
to be determined.

\begin{theorem}
A set of $cL$ independently chosen random subproducts
$\{ h_1, \ldots, h_{cL} \}$ generates $G$ with high probability.
\end{theorem}

(The cost of forming this generating set is $O(kL)$.)

\begin{proof}
Let $H_i = \left< h_1, \ldots, h_i \right>$.
Either $H_i = G$, or ${\mathrm Pr} (h_{i+1} \notin H_i) \geq \frac{1}{2}$,
by the lemma above.  Let $\tau$ be the first time $i$ when $H_i = G$.
Then $E(\tau) \leq 2L$.  If we take $L$ to be the length of the
maximal subgroup chain, and $c = 4$, then this algorithm succeeds
with probability at least $\frac{1}{2}$, by the Markov inequality.
\end{proof}

The Chernoff bound (stated in lecture 10, October 1)
provides another estimate of the value of $c$ sufficient
to ensure a certain probability of success.  We omit the details.

\subsection*{Commutator Subgroups}

Fix $k = O(\log \vert G \vert)$.

In order to test a black box group for solvability or nilpotence,
we want to construct generators for a commutator group $\left[ G, G \right]$
from generators for $G$.

Suppose $G = \left< g_1, \ldots, g_k \right>$.
$\left[ G, G \right]$ is {\em not} necessarily generated by
the set of $\left[ g_i, g_j \right]$.  For example, a simple
alternating group can be generated by two elements $g_1, g_2$.
Since $\left[ G, G \right]$ is normal in $G$ and $G$ is simple,
$\left[ G, G \right] = G$.  The single element $\left[ g_1, g_2 \right]$
can generate only a cyclic subgroup.

The following {\em is} true:

\begin{theorem}
If $A = \left< a_1, \ldots, a_k \right>$ and
$B = \left< b_1, \ldots, b_m \right>$ are normal subgroups of $G$,
then $\left[ A, B \right]$ is the normal closure of the group
generated by $\left[ a_i, b_j \right]$, $1 \leq i \leq k$,
$1 \leq j \leq m$.
\label{thm:normclo}
\end{theorem}

The {\em normal closure} of a subgroup $H$ of $G$,
denoted ${\left< H \right>}^G$, is the smallest
normal subgroup of $G$ containing $H$.  Since $\left[ A, B \right]$
is normal, it must contain the normal closure of the group generated
by the $\left[ a_i, b_j \right]$.  The equality
given by the theorem wasn't proven in class, but I've sketched the easy
proof at the end of the notes.

\begin{lemma}
Let $H = \left< h_1, \ldots, h_m \right>$ be a subgroup of
$G = \left< g_1, \ldots, g_k \right>$.  Suppose $H \neq {\left< H \right>}^G$.
Then ${\mathrm Pr} (h^g \notin H) \geq \frac{1}{4}$,
where $h$ and $g$ are random subproducts of the given generators
for $H$ and $G$, respectively.
% where $$h^g = {\left( h_1^{\epsilon_1} \cdots h_m^{\epsilon_m} \right)}^{
% g_1^{\alpha_1} \cdots g_k^{\alpha_k}}$$
% and $\epsilon_i, \alpha_i \in \{ 0, 1 \}$ are chosen uniformly,
% independently.
\label{lem:normclo}
\end{lemma}

\begin{proof}
Let $$N_G (H) = \{ g \in G : g H g^{-1} = H \}$$
denote the normalizer of $H$ in $G$.
Since $H \neq {\left< H \right>}^G$, we know $H$ is not normal
in $G$, and $N_G (H) \neq G$.  Let $g$ be a random subproduct
of the generators for $G$.
By Lemma \ref{lem:main},
${\mathrm Pr} (g \notin N_G (H)) \geq \frac{1}{2}$.

Assume $g \notin N_G (H)$.  Then $H^g \cap H$ is a proper subgroup
of $H$.  Let $h$ be a random subproduct in $H$.
Then
$$h^g = {\left( h_1^{\epsilon_1} \cdots h_m^{\epsilon_m} \right)}^g
= {(h_1^g)}^{\epsilon_1} \cdots {(h_m^g)}^{\epsilon_m}$$
is a random subproduct on $H^g = \left< h_1^g, \ldots, h_m^g \right>$.
Over $h$, ${\mathrm Pr} (h^g \notin H) = {\mathrm Pr} (h^g \notin H^g \cap H)
\geq \frac{1}{2}$, again by Lemma \ref{lem:main}.
Over $h$ and $g$,
${\mathrm Pr} (h^g \notin H) \geq \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
\end{proof}

Our algorithm to construct a generating set for $\left[ A, B \right]$
proceeds as follows.  Let $V_0$ be the group generated by
all $\left[ a_i, b_j \right]$.
For each $r > 0$, form $V_r$ by adding the element
$v^g$ to the set of generators for $V_{r-1}$, where $v$ is a random
subproduct of the generators for $V_{r-1}$ and $g$ is a random
subproduct of the generators for $G$.  Then $V_{cL} = \left[ G, G \right]$
with high probability, by Theorem \ref{thm:normclo},
Lemma \ref{lem:normclo}, and the Markov Inequality.

To test whether a black box group is solvable,
we just take its commutator repeatedly, using the algorithm above:
$$G \rightarrow \left[ G, G \right] \rightarrow \left[ \left[ G, G \right],
\left[ G, G \right] \right] \rightarrow \cdots$$
We keep doing this for as many iterations as the longest possible subgroup
chain in $G$ (logarithmic in the size of $G$, which is given).
We answer that it is solvable (with high probability) if all the generators
are equal to the identity at the end of the algorithm.  Otherwise,
we say that it is not solvable (with certainty).

If we follow the algorithm literally, the number of generators we are
considering will blow up as we take more commutators.
To avoid this, we apply the generating set reduction algorithm from
the beginning of the lecture.  Thus, we can test for solvability
in polynomial time in $k$ and $\log_2 \vert G \vert$.

Similarly, we can test whether a group is nilpotent, by
considering commutators of the form
$$G \rightarrow \left[ G, G \right] \rightarrow \left[ G, \left[G, G \right]
\right] \rightarrow \cdots \mbox{  .}$$

\subsection*{Appendix}

To prove Theorem \ref{thm:normclo}, we show that if $N < G$ is
a normal subgroup containing all $\left[ a_i, b_j \right]$,
then it contains $\left[ A, B \right]$.
The proof can be broken into two lemmas:

\begin{lemma}
$N$ contains all $\left[ a_i^{\pm 1}, b_j^{\pm 1} \right]$.
\end{lemma}

\begin{proof}
Observing that $\left[ x, y \right] = {\left[ y, x \right]}^{-1}$,
we obtain
\begin{eqnarray*}
\left[ a_i^{-1}, b_j \right] & = &
a_i^{-1} {\left[ a_i, b_j \right]}^{-1} a_i \\
\left[ a_i, b_j^{-1} \right] & = &
b_j^{-1} {\left[ a_i, b_j \right]}^{-1} b_j \\
\left[ a_i^{-1}, b_j^{-1} \right] & = &
b_j^{-1} a_i^{-1} \left[ a_i, b_j \right] a_i b_j
\end{eqnarray*}
\end{proof}

\begin{lemma}
Let $N < G$ be normal.
If $x, y, z \in G$ and $\left[ x, z \right], \left[ y, z \right] \in N$,
then $\left[xy, z \right] \in N$.
\end{lemma}
\begin{proof}
\begin{eqnarray*}
\left[ xy, z \right] & = & x y z y^{-1} x^{-1} z^{-1} \\
& = & x (y z y^{-1} z^{-1} ) z x^{-1} z^{-1} \\
& = & x (y z y^{-1} z^{-1} ) x^{-1} x z x^{-1} z^{-1} \\
& = & (x \left[ y, z \right] x^{-1}) (\left[ x, z \right])
\end{eqnarray*}
\end{proof}

The theorem follows by considering expansions of arbitrary elements
of $A$ and $B$ in terms of the $a_i$ and $b_j$, and applying the two lemmas.

\end{document}