\documentclass[10pt,notitlepage]{article}
\usepackage{amsmath,graphicx,amssymb,color,hyperref}

\paperwidth 210mm
\paperheight 297mm
\textwidth 210mm
\textheight 297mm
\oddsidemargin -1in
\evensidemargin \oddsidemargin
\topmargin -1.7in
\headheight 0in
\headsep 0in
\footskip 0in
\parindent 0in
\setlength{\topsep}{0pt}
\pagestyle{empty}

\def\bbR{{\mathbb R}}

\def\talkurl{{\url{http://www.math.toronto.edu/~drorbn/Talks/Cambridge-1301/}}}

\def\TheProblem{{\raisebox{3mm}{\parbox[t]{3in}{
  {\color{red}The Problem.} Let $G=\langle g_1,\ldots,g_\alpha\rangle$ be
  a subgroup of $S_n$, with $n=O(100)$. Before you die, understand $G$:
  \par\noindent 1. Compute $|G|$.
  \par\noindent 2. Given $\sigma\in S_n$, decide if $\sigma\in G$.
  \par\noindent 3. Write a $\sigma\in G$ in terms of $g_1,\ldots,g_\alpha$.
  \par\noindent 4. Produce {\em random} elements of $G$.
}}}}

\def\GaussianElimination{{\raisebox{2mm}{\parbox[t]{3in}{
  {\color{red}The Commutative Analog.} Let
  $V=\operatorname{span}(v_1,\ldots,v_\alpha)$ be a subspace of
  $\bbR^n$. Before you die, understand $V$.
  \par\noindent {\color{red}Solution: Gaussian Elimination. }
  Prepare an empty table,
}}}}

\def\FeedVectors{{\raisebox{2mm}{\parbox[t]{4.5in}{
  {\color{red}Feed $v_1,\ldots,v_\alpha$ in order.} To feed a non-zero
  $v$, find its pivotal position $i$.
  \par\noindent 1.\ If box $i$ is empty, put $v$ there.
  \par\noindent 2.\ If box $i$ is occupied, find a combination $v'$ of $v$
  and $u_i$ that eliminates the pivot, and feed $v'$.
}}}}

\def\SeeAlso{{\raisebox{0mm}{\ \parbox[t]{1.4in}{\scriptsize
  See also {\em Permutation Group Algorithms} by \'A.\ Seress, {\em
  Efficient Representation of Perm Groups} by D.\ Knuth.
}}}}

\def\FeedGenerators{{\raisebox{2mm}{\parbox[t]{4.5in}{
{\color{red}Feed $g_1,\ldots,g_\alpha$ in order.} To feed a non-identity
$\sigma$, find its pivotal position $i$ and let $j:=\sigma(i)$.
\par\noindent 1. If box $(i,j)$ is empty, put $\sigma$ there.
\par\noindent 2. If box $(i,j)$ contains $\sigma_{i,j}$, feed
  $\sigma':=\sigma_{i,j}^{-1}\sigma$.
\par\noindent {\color{red}The Twist.} When done, for every occupied
$(i,j)$ and $(k,l)$, feed $\sigma_{i,j}\sigma_{k,l}$. Repeat until the
table stops changing.

\par\noindent {\color{red}Claim 1.} The process stops in our lifetimes,
after at most $O(n^6)$ operations. Call the resulting table $T$.

\par\noindent {\color{red}Claim 2.} Every $\sigma_{i,j}$ in $T$ is in $G$.

\par\noindent {\color{red}Claim 3.} Anything fed in $T$ is now a monotone
product in $T$:
\vskip -8mm
\[ f\text{ was fed }\Rightarrow\ 
  f\in M_1\!:=\!\left\{
    \sigma_{1,j_1}\sigma_{2,j_2}\cdots\sigma_{n,j_n}
    \colon \forall i, j_i\geq i\ \&\ \sigma_{i,j_i}\in T
  \right\}
\]
}}}}

\def\Claims{{\raisebox{2mm}{\parbox[t]{3.8in}{
{\color{red}Claim 4.} If two monotone products are equal,
\vskip -5mm
\[
  \sigma_{1,j_1}\cdots\sigma_{n,j_n} = \sigma_{1,j'_1}\cdots\sigma_{n,j'_n},
\]
\vskip -2mm
then all the indices that appear in them are equal, $\forall i,\ j_i=j'_i$.

{\color{red}Claim 5.} Let $M_k$ denote the set of monotone products in $T$
starting in column $k$:
\vskip -8mm
\[
  M_k:=\left\{
    \sigma_{k,j_k}\cdots\sigma_{n,j_n}
    \colon \forall i\geq k, j_i\geq i\text{ and }\sigma_{i,j_i}\in T
  \right\}.
\]
\vskip -2mm
then for every $k$, $M_kM_k\subset M_k$ (and so each $M_k$ is a
subgroup of $G$).

\par\noindent {\color{red}Proof.} By backwards induction. Clearly
$M_nM_n\subset M_n$. Now assume that $M_5M_5\subset M_5$ and show that
$M_4M_4\subset M_4$. Start with $\sigma_{8,j}M_4\subset M_4$:
\vskip -3mm
\[ \sigma_{8,j}(\sigma_{4,j_4}M_5)
  \overset{1}{=}(\sigma_{8,j}\sigma_{4,j_4})M_5
  \overset{2}{\subset}M_4M_5 \]
\vskip -2mm
\[ \overset{3}{=}
  \sigma_{4,j_4'}(M_5M_5)
  \overset{4}{\subset}\sigma_{4,j_4'}M_5\subset M_4 \]
\vskip -1mm
(1: associativity, 2: thank the twist, 3: associativity and tracing
$i_4$, 4: induction).
Now the general case
\vskip -4mm
\[ (\sigma_{4,j'_4}\sigma_{5,j'_5}\cdots)
  (\sigma_{4,j_4}\sigma_{5,j_5}\cdots) \]
\vskip -1mm
falls like a chain of dominos.

{\color{red}Theorem.} $G=M_1$ and we have achieved our goals.
}}}}

\def\Enter{{\fbox{\sl Enter}}}

\def\result{\parbox{1.5in}{
\[ 43,252,003,274,489,856,000 \]
\[ = \frac{8!\,3^8\,12!\,2^{12}}{12} \]
}}

\begin{document}\begin{center}
\null\vfill
\scalebox{0.92}{\input{NCGE.pstex_t}}
\vfill\null
\end{center}
\end{document}

\endinput