\documentclass{article}
\usepackage{/usr/local/noweb/src/tex/noweb}
\begin{document}
\title{The Andrews-Curtis Conjecture}
\author{Gilbert Baumslag, Bruno Buchberger, Timothy Daly}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{The Problem}
We are designing this program to work with the exact presentation:
\begin{verbatim}
  G = < a , b ; abaBAB , AAbbb >
\end{verbatim}
where lower case letters are generators and uppercase letters are
their inverses. This presentation is known to be trivial. That is,
it is known to be exactly:
\begin{verbatim}
  F = < a , b ; >
\end{verbatim}
We are given 12 transformations. Each transformation specifies a
way to rewrite the two relators. If the first relator is called {\bf x},
its inverse is {\bf X},
the second relator is called {\bf y}, 
and its inverse is {\bf Y}
then we have the Andrews-Curtis Transformations:
\begin{list}{}
\item {\bf T1}: {\tt x -> xy ; y -> y}
\item {\bf T2}: {\tt x -> X ; y -> y}
\item {\bf T3}: {\tt x -> axA ; y -> y}
\item {\bf T4}: {\tt x -> x ; y -> yx}
\item {\bf T5}: {\tt x -> x ; y -> Y}
\item {\bf T6}: {\tt x -> x ; y -> ayA}
\item {\bf T7}: {\tt x -> bxB ; y -> y}
\item {\bf T8}: {\tt x -> x ; y -> byB}
\item {\bf T9}:  {\tt x -> Axa ; y -> y}
\item {\bf T10}: {\tt x -> x ; y -> Aya}
\item {\bf T11}: {\tt x -> Bxb ; y -> y}
\item {\bf T12}: {\tt x -> x ; y -> Byb}
\end{list}
\section{The Representation}
In order to implement these transformations we keep both relators
in one structure we call a {\bf tuple}. In this implementation a
{\bf tuple} is representated as a lisp cons cell. The car of the
cell is a string representing the first relator. The cdr of the
cell is a string representing the second relator. 

Each of the twelve transformation functions takes this pair of 
relators and returns a new pair containing the transformation.
This generates a lot of cons cells.

A more efficient, but not yet implemented, implementation will be to
destructively modify the tuple and reuse the cons cell. A further 
optimization is to keep a pool of strings of a given length and
reuse the string storage. This is future work. 

\subsection{The inverse function {\sl inv}}
We need to be able to calculate the inverse of a 
given generator. So the inverse of 'a' is 'A', 'A' is 'a', 
'b' is 'B' and 'B' is 'b'. This function, given a string composed
of generators rewrites the string by reversing the string and doing
a generator by generator replacement.

<<inv>>=
(defun inv (word)
 "given a word, construct its inverse"
 (let ((result (reverse word)))
  (dotimes (i (length result))
   (setf (elt result i)
    (cond
     ((eq (elt result i) #\a) #\A)
     ((eq (elt result i) #\b) #\B)
     ((eq (elt result i) #\A) #\a)
     ((eq (elt result i) #\B) #\b))))
  result))

@
\subsection{The pinch function {\sl pinch}}
We need to elide generators which are concatenated to their inverse.
So the combinations 'aA', 'Aa', 'bB' and 'Bb' disappear from the string.
We stack the first generator in the string and then compare it with
the second generator. If the next element is an inverse we pop the
generator from the stack. Otherwise, we push the next generator from
the string and continue the process.

For words of length 0 or 1 there can be no pinching so we simply 
return the word.

Note that this operation constructs a new word. An optimization is to
make the word process destructive to save space. This is not yet 
implemented.
<<pinch>>=
(defun pinch (word)
 "given a word pinch out all inverse elements"
 (let ((stack nil) (wlen (- (length word) 1)))
  (if (> wlen 0)
   (progn
    (push (elt word 0) stack)
    (dotimes (i wlen) 
     (cond
      ((and (eq (first stack) #\a) (eq (elt word (+ i 1)) #\A)) (pop stack))
      ((and (eq (first stack) #\A) (eq (elt word (+ i 1)) #\a)) (pop stack))
      ((and (eq (first stack) #\b) (eq (elt word (+ i 1)) #\B)) (pop stack))
      ((and (eq (first stack) #\B) (eq (elt word (+ i 1)) #\b)) (pop stack))
      (t (push (elt word (+ i 1)) stack))))
    (concatenate 'string (reverse stack)))
    word)))
@
\subsection{The Andrews-Curtis Transformation functions}
These transformations have been rewritten. One optimization is that
each transformation used to construct a new cons cell. We eliminate
this waste by reusing the cons cell. The [[rplaca]] function replaces
the first element of the [[cons]] cell (known as the [[car]]) "in place". 
Similarly, the [[rplacd]] function replaces the second element of the
[[cons]] cell (known as the [[cdr]]) "in place". This optimization
saves both space because we allocate less memory, and time because
we don't have to reclaim memory we never use.
\subsubsection{{\tt T1: x -> xy ; y -> y}}
\begin{verbatim}
(defun t1 (tuple)
 "x -> xy ; y -> y"
  (cons 
    (pinch (concatenate 'string (car tuple) (cdr tuple)))
    (cdr tuple)))
\end{verbatim}
<<t1>>=
(defun t1 (tuple)
 "x -> xy ; y -> y"
  (rplaca tuple (pinch (concatenate 'string (car tuple) (cdr tuple)))))

@
\subsubsection{{\tt T2: x -> X ; y -> y }}
\begin{verbatim}
(defun t2 (tuple)
 "x -> X ; y -> y"
 (cons 
   (inv (car tuple))
   (cdr tuple)))
\end{verbatim}
<<t2>>=
(defun t2 (tuple)
 "x -> X ; y -> y"
 (rplaca tuple (inv (car tuple))))

@
\subsubsection{{\tt T3: x -> axA ; y -> y}}
\begin{verbatim}
(defun t3 (tuple)
 "x -> axA ; y -> y"
 (cons 
   (pinch (concatenate 'string "a" (car tuple) "A"))
   (cdr tuple)))
\end{verbatim}
<<t3>>=
(defun t3 (tuple)
 "x -> axA ; y -> y"
 (rplaca tuple (pinch (concatenate 'string "a" (car tuple) "A"))))

@
\subsubsection{{\tt T4: x -> x ; y -> yx}}
\begin{verbatim}
(defun t4 (tuple)
 "x -> x ; y -> yx"
 (cons
  (car tuple)
  (pinch (concatenate 'string (cdr tuple) (car tuple)))))
\end{verbatim}
<<t4>>=
(defun t4 (tuple)
 "x -> x ; y -> yx"
  (rplacd tuple (pinch (concatenate 'string (cdr tuple) (car tuple)))))

@
\subsubsection{{\tt T5: x -> x ; y -> Y}}
\begin{verbatim}
(defun t5 (tuple)
 "x -> x ; y -> Y"
 (cons
  (car tuple)
  (inv (cdr tuple))))
\end{verbatim}
<<t5>>=
(defun t5 (tuple)
 "x -> x ; y -> Y"
 (rplacd tuple (inv (cdr tuple))))

@
\subsubsection{{\tt T6: x -> x ; y -> ayA}}
\begin{verbatim}
(defun t6 (tuple)
 "x -> x ; y -> ayA"
 (cons
  (car tuple)
  (pinch (concatenate 'string "a" (cdr tuple) "A"))))
\end{verbatim}
<<t6>>=
(defun t6 (tuple)
 "x -> x ; y -> ayA"
 (rplacd tuple (pinch (concatenate 'string "a" (cdr tuple) "A"))))

@
\subsubsection{{\tt T7: x -> bxB ; y -> y}}
\begin{verbatim}
(defun t7 (tuple)
 "x -> bxB ; y -> y"
 (cons
  (pinch (concatenate 'string "b" (car tuple) "B"))
  (cdr tuple)))
\end{verbatim}
<<t7>>=
(defun t7 (tuple)
 "x -> bxB ; y -> y"
 (rplaca tuple (pinch (concatenate 'string "b" (car tuple) "B"))))

@
\subsubsection{{\tt T8: x -> x ; y -> byB}}
\begin{verbatim}
(defun t8 (tuple)
 "x -> x ; y -> byB"
 (cons
  (car tuple)
  (pinch (concatenate 'string "b" (cdr tuple) "B"))))
\end{verbatim}
<<t8>>=
(defun t8 (tuple)
 "x -> x ; y -> byB"
 (rplacd tuple (pinch (concatenate 'string "b" (cdr tuple) "B"))))

@
\subsubsection{{\tt T9: x -> Axa ; y -> y}}
\begin{verbatim}
(defun t9 (tuple)
 "x -> Axa ; y -> y"
 (cons
  (pinch (concatenate 'string "A" (car tuple) "a"))
  (cdr tuple)))
\end{verbatim}
<<t9>>=
(defun t9 (tuple)
 "x -> Axa ; y -> y"
 (rplaca tuple (pinch (concatenate 'string "A" (car tuple) "a"))))

@
\subsubsection{{\tt T10: x -> x ; y -> Aya}}
\begin{verbatim}
(defun t10 (tuple)
 "x -> x ; y -> Aya"
 (cons
  (car tuple)
  (pinch (concatenate 'string "A" (cdr tuple) "a"))))
\end{verbatim}
<<t10>>=
(defun t10 (tuple)
 "x -> x ; y -> Aya"
 (rplacd tuple (pinch (concatenate 'string "A" (cdr tuple) "a"))))

@
\subsubsection{{\tt T11: x -> Bxb ; y -> y}}
\begin{verbatim}
(defun t11 (tuple)
 "x -> Bxb ; y -> y"
 (cons
  (pinch (concatenate 'string "B" (car tuple) "b"))
  (cdr tuple)))
\end{verbatim}
<<t11>>=
(defun t11 (tuple)
 "x -> Bxb ; y -> y"
 (rplaca tuple (pinch (concatenate 'string "B" (car tuple) "b"))))

@
\subsubsection{{\tt T12: x -> x ; y -> Byb}}
\begin{verbatim}
(defun t12 (tuple)
 "x -> x ; y -> Byb"
 (cons
  (car tuple)
  (pinch (concatenate 'string "B" (cdr tuple) "b"))))
\end{verbatim}
<<t12>>=
(defun t12 (tuple)
 "x -> x ; y -> Byb"
 (rplacd tuple (pinch (concatenate 'string "B" (cdr tuple) "b"))))

@
<<*>>=
<<pinch>>
<<inv>>
<<t1>>
<<t2>>
<<t3>>
<<t4>>
<<t5>>
<<t6>>
<<t7>>
<<t8>>
<<t9>>
<<t10>>
<<t11>>
<<t12>>
@
\section{First Steps}
\subsection{Apply each transformation}
If we create a tuple from the two relators thus:
<<setq>>=
(setq r (cons "abaBAB" "AAbbb"))

@
and call each transformation on {\bf r} thus:
<<dolist>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12)) 
  (print (list x (funcall x r))))

@
we get the results:
\begin{verbatim}
(T1 ("abaBABAAbbb" . "AAbbb")) 
(T2 ("babABA" . "AAbbb")) 
(T3 ("aabaBABA" . "AAbbb")) 
(T4 ("abaBAB" . "AAbbbabaBAB")) 
(T5 ("abaBAB" . "BBBaa")) 
(T6 ("abaBAB" . "AbbbA")) 
(T7 ("babaBABB" . "AAbbb")) 
(T8 ("abaBAB" . "bAAbb")) 
(T9 ("baBABa" . "AAbbb")) 
(T10 ("abaBAB" . "AAAbbba")) 
(T11 ("BabaBA" . "AAbbb")) 
(T12 ("abaBAB" . "BAAbbbb")) 
\end{verbatim}

\subsection{Compose T1 with all}
<<composeT1>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12)) 
  (print (list 't1 (list x (t1 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T1 (T1 ("abaBABAAbbbAAbbb" . "AAbbb"))) 
(T1 (T2 ("babABAAAbbb" . "AAbbb"))) 
(T1 (T3 ("aabaBABAAAbbb" . "AAbbb"))) 
(T1 (T4 ("abaBABAAbbbabaBAB" . "AAbbbabaBAB"))) 
(T1 (T5 ("abaBABBBBaa" . "BBBaa"))) 
(T1 (T6 ("abaBABAbbbA" . "AbbbA"))) 
(T1 (T7 ("babaBABBAAbbb" . "AAbbb"))) 
(T1 (T8 ("abaBAAAbb" . "bAAbb"))) 
(T1 (T9 ("baBABAbbb" . "AAbbb"))) 
(T1 (T10 ("abaBABAAAbbba" . "AAAbbba"))) 
(T1 (T11 ("BabaBAAAbbb" . "AAbbb"))) 
(T1 (T12 ("abaBABBAAbbbb" . "BAAbbbb"))) 
\end{verbatim}

\subsection{Compose T2 with all}
<<composeT2>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't2 (list x (t2 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T2 (T1 ("BBBaababABA" . "AAbbb"))) 
(T2 (T2 ("abaBAB" . "AAbbb"))) 
(T2 (T3 ("ababABAA" . "AAbbb"))) 
(T2 (T4 ("babABA" . "AAbbbabaBAB"))) 
(T2 (T5 ("babABA" . "BBBaa"))) 
(T2 (T6 ("babABA" . "AbbbA"))) 
(T2 (T7 ("bbabABAB" . "AAbbb"))) 
(T2 (T8 ("babABA" . "bAAbb"))) 
(T2 (T9 ("AbabAB" . "AAbbb"))) 
(T2 (T10 ("babABA" . "AAAbbba"))) 
(T2 (T11 ("abABAb" . "AAbbb"))) 
(T2 (T12 ("babABA" . "BAAbbbb"))) 
\end{verbatim}

\subsection{Compose T3 with all}
<<composeT3>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't3 (list x (t3 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T3 (T1 ("aabaBABAAbbbA" . "AAbbb"))) 
(T3 (T2 ("ababABAA" . "AAbbb"))) 
(T3 (T3 ("aaabaBABAA" . "AAbbb"))) 
(T3 (T4 ("aabaBABA" . "AAbbbabaBAB"))) 
(T3 (T5 ("aabaBABA" . "BBBaa"))) 
(T3 (T6 ("aabaBABA" . "AbbbA"))) 
(T3 (T7 ("ababaBABBA" . "AAbbb"))) 
(T3 (T8 ("aabaBABA" . "bAAbb"))) 
(T3 (T9 ("abaBAB" . "AAbbb"))) 
(T3 (T10 ("aabaBABA" . "AAAbbba"))) 
(T3 (T11 ("aBabaBAA" . "AAbbb"))) 
(T3 (T12 ("aabaBABA" . "BAAbbbb"))) 

\end{verbatim}

\subsection{Compose T4 with all}
<<composeT4>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't4 (list x (t4 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T4 (T1 ("abaBABAAbbb" . "AAbbbabaBABAAbbb"))) 
(T4 (T2 ("babABA" . "AAbbbbabABA"))) 
(T4 (T3 ("aabaBABA" . "AAbbbaabaBABA"))) 
(T4 (T4 ("abaBAB" . "AAbbbabaBABabaBAB"))) 
(T4 (T5 ("abaBAB" . "BBBaaabaBAB"))) 
(T4 (T6 ("abaBAB" . "AbbbbaBAB"))) 
(T4 (T7 ("babaBABB" . "AAbbbbabaBABB"))) 
(T4 (T8 ("abaBAB" . "bAAbbabaBAB"))) 
(T4 (T9 ("baBABa" . "AAbbbbaBABa"))) 
(T4 (T10 ("abaBAB" . "AAAbbbaabaBAB"))) 
(T4 (T11 ("BabaBA" . "AAbbabaBA"))) 
(T4 (T12 ("abaBAB" . "BAAbbbbabaBAB"))) 

\end{verbatim}
\subsection{Compose T5 with all}
<<composeT5>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't5 (list x (t5 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T5 (T1 ("abaBABAAbbb" . "BBBaa"))) 
(T5 (T2 ("babABA" . "BBBaa"))) 
(T5 (T3 ("aabaBABA" . "BBBaa"))) 
(T5 (T4 ("abaBAB" . "babABABBBaa"))) 
(T5 (T5 ("abaBAB" . "AAbbb"))) 
(T5 (T6 ("abaBAB" . "aBBBa"))) 
(T5 (T7 ("babaBABB" . "BBBaa"))) 
(T5 (T8 ("abaBAB" . "BBaaB"))) 
(T5 (T9 ("baBABa" . "BBBaa"))) 
(T5 (T10 ("abaBAB" . "ABBBaaa"))) 
(T5 (T11 ("BabaBA" . "BBBaa"))) 
(T5 (T12 ("abaBAB" . "BBBBaab"))) 

\end{verbatim}
\subsection{Compose T6 with all}
<<composeT6>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't6 (list x (t6 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T6 (T1 ("abaBABAAbbb" . "AbbbA"))) 
(T6 (T2 ("babABA" . "AbbbA"))) 
(T6 (T3 ("aabaBABA" . "AbbbA"))) 
(T6 (T4 ("abaBAB" . "AbbbabaBABA"))) 
(T6 (T5 ("abaBAB" . "aBBBa"))) 
(T6 (T6 ("abaBAB" . "bbbAA"))) 
(T6 (T7 ("babaBABB" . "AbbbA"))) 
(T6 (T8 ("abaBAB" . "abAAbbA"))) 
(T6 (T9 ("baBABa" . "AbbbA"))) 
(T6 (T10 ("abaBAB" . "AAbbb"))) 
(T6 (T11 ("BabaBA" . "AbbbA"))) 
(T6 (T12 ("abaBAB" . "aBAAbbbbA"))) 

\end{verbatim}
\subsection{Compose T7 with all}
<<composeT7>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't7 (list x (t7 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T7 (T1 ("babaBABAAbb" . "AAbbb"))) 
(T7 (T2 ("bbabABAB" . "AAbbb"))) 
(T7 (T3 ("baabaBABAB" . "AAbbb"))) 
(T7 (T4 ("babaBABB" . "AAbbbabaBAB"))) 
(T7 (T5 ("babaBABB" . "BBBaa"))) 
(T7 (T6 ("babaBABB" . "AbbbA"))) 
(T7 (T7 ("bbabaBABBB" . "AAbbb"))) 
(T7 (T8 ("babaBABB" . "bAAbb"))) 
(T7 (T9 ("bbaBABaB" . "AAbbb"))) 
(T7 (T10 ("babaBABB" . "AAAbbba"))) 
(T7 (T11 ("abaBAB" . "AAbbb"))) 
(T7 (T12 ("babaBABB" . "BAAbbbb"))) 

\end{verbatim}
\subsection{Compose T8 with all}
<<composeT8>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't8 (list x (t8 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T8 (T1 ("abaBABAAbbb" . "bAAbb"))) 
(T8 (T2 ("babABA" . "bAAbb"))) 
(T8 (T3 ("aabaBABA" . "bAAbb"))) 
(T8 (T4 ("abaBAB" . "bAAbbbabaBABB"))) 
(T8 (T5 ("abaBAB" . "BBaaB"))) 
(T8 (T6 ("abaBAB" . "bAbbbAB"))) 
(T8 (T7 ("babaBABB" . "bAAbb"))) 
(T8 (T8 ("abaBAB" . "bbAAb"))) 
(T8 (T9 ("baBABa" . "bAAbb"))) 
(T8 (T10 ("abaBAB" . "bAAAbbbaB"))) 
(T8 (T11 ("BabaBA" . "bAAbb"))) 
(T8 (T12 ("abaBAB" . "AAbbb"))) 

\end{verbatim}
\subsection{Compose T9 with all}
<<composeT9>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't9 (list x (t9 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T9 (T1 ("baBABAAbbba" . "AAbbb"))) 
(T9 (T2 ("AbabAB" . "AAbbb"))) 
(T9 (T3 ("abaBAB" . "AAbbb"))) 
(T9 (T4 ("baBABa" . "AAbbbabaBAB"))) 
(T9 (T5 ("baBABa" . "BBBaa"))) 
(T9 (T6 ("baBABa" . "AbbbA"))) 
(T9 (T7 ("AbabaBABBa" . "AAbbb"))) 
(T9 (T8 ("baBABa" . "bAAbb"))) 
(T9 (T9 ("AbaBABaa" . "AAbbb"))) 
(T9 (T10 ("baBABa" . "AAAbbba"))) 
(T9 (T11 ("ABabaB" . "AAbbb"))) 
(T9 (T12 ("baBABa" . "BAAbbbb"))) 

\end{verbatim}
\subsection{Compose T10 with all}
<<composeT10>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't10 (list x (t10 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T10 (T1 ("abaBABAAbbb" . "AAAbbba"))) 
(T10 (T2 ("babABA" . "AAAbbba"))) 
(T10 (T3 ("aabaBABA" . "AAAbbba"))) 
(T10 (T4 ("abaBAB" . "AAAbbbabaBABa"))) 
(T10 (T5 ("abaBAB" . "ABBBaaa"))) 
(T10 (T6 ("abaBAB" . "AAbbb"))) 
(T10 (T7 ("babaBABB" . "AAAbbba"))) 
(T10 (T8 ("abaBAB" . "AbAAbba"))) 
(T10 (T9 ("baBABa" . "AAAbbba"))) 
(T10 (T10 ("abaBAB" . "AAAAbbbaa"))) 
(T10 (T11 ("BabaBA" . "AAAbbba"))) 
(T10 (T12 ("abaBAB" . "ABAAbbbba"))) 

\end{verbatim}
\subsection{Compose T11 with all}
<<composeT11>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't11 (list x (t11 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T11 (T1 ("BabaBABAAbbbb" . "AAbbb"))) 
(T11 (T2 ("abABAb" . "AAbbb"))) 
(T11 (T3 ("BaabaBABAb" . "AAbbb"))) 
(T11 (T4 ("BabaBA" . "AAbbbabaBAB"))) 
(T11 (T5 ("BabaBA" . "BBBaa"))) 
(T11 (T6 ("BabaBA" . "AbbbA"))) 
(T11 (T7 ("abaBAB" . "AAbbb"))) 
(T11 (T8 ("BabaBA" . "bAAbb"))) 
(T11 (T9 ("aBABab" . "AAbbb"))) 
(T11 (T10 ("BabaBA" . "AAAbbba"))) 
(T11 (T11 ("BBabaBAb" . "AAbbb"))) 
(T11 (T12 ("BabaBA" . "BAAbbbb"))) 

\end{verbatim}
\subsection{Compose T12 with all}
<<composeT12>>=
(dolist (x '(t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12))
   (print (list 't12 (list x (t12 (funcall x r))))))

@
We get the results:
\begin{verbatim}
(T12 (T1 ("abaBABAAbbb" . "BAAbbbb"))) 
(T12 (T2 ("babABA" . "BAAbbbb"))) 
(T12 (T3 ("aabaBABA" . "BAAbbbb"))) 
(T12 (T4 ("abaBAB" . "BAAbbbabaBA"))) 
(T12 (T5 ("abaBAB" . "BBBBaab"))) 
(T12 (T6 ("abaBAB" . "BAbbbAb"))) 
(T12 (T7 ("babaBABB" . "BAAbbbb"))) 
(T12 (T8 ("abaBAB" . "AAbbb"))) 
(T12 (T9 ("baBABa" . "BAAbbbb"))) 
(T12 (T10 ("abaBAB" . "BAAAbbbab"))) 
(T12 (T11 ("BabaBA" . "BAAbbbb"))) 
(T12 (T12 ("abaBAB" . "BBAAbbbbb"))) 

\end{verbatim}
\section{A Matrix Representation}
Given the group
\begin{verbatim}
  G = < a , b ; abaBAB , AAbbb >
\end{verbatim}
we can consider the case where the generators are given by 
$2{\rm\ x\ }2$ matrices with symbolic entries. So we allow
\[
a=\left[
\begin{array}{cc}
c & d\\
e & f
\end{array}
\right]
{\rm\ and\ }
b=\left[
\begin{array}{cc}
g & h\\
i & j
\end{array}
\right]
\]
and their inverses are:
\[
A=
\left[
\begin{array}{cc}
{f \over {{c \  f} -{d \  e}}} & -{d \over {{c \  f} -{d \  e}}} \\ 
-{e \over {{c \  f} -{d \  e}}} & {c \over {{c \  f} -{d \  e}}} 
\end{array}
\right]
{\rm\ and\ }
B=
\left[
\begin{array}{cc}
{j \over {{g \  j} -{h \  i}}} & -{h \over {{g \  j} -{h \  i}}} \\ 
-{i \over {{g \  j} -{h \  i}}} & {g \over {{g \  j} -{h \  i}}} 
\end{array}
\right]
\]
then by simple multiplication we know that the relators are:
\[
\begin{array}{ccl}
{\rm abaBAB} & = &
\left[
\begin{array}{cc}
c & d\\
e & f
\end{array}
\right]
\left[
\begin{array}{cc}
g & h \\ 
i & j 
\end{array}
\right]
\left[
\begin{array}{cc}
c & d\\
e & f
\end{array}
\right]\\
& &
\left[
\begin{array}{cc}
{j \over {{g \  j} -{h \  i}}} & -{h \over {{g \  j} -{h \  i}}} \\ 
-{i \over {{g \  j} -{h \  i}}} & {g \over {{g \  j} -{h \  i}}} 
\end{array}
\right]
\left[
\begin{array}{cc}
{f \over {{c \  f} -{d \  e}}} & -{d \over {{c \  f} -{d \  e}}} \\ 
-{e \over {{c \  f} -{d \  e}}} & {c \over {{c \  f} -{d \  e}}} 
\end{array}
\right]\\
& &
\left[
\begin{array}{cc}
{j \over {{g \  j} -{h \  i}}} & -{h \over {{g \  j} -{h \  i}}} \\ 
-{i \over {{g \  j} -{h \  i}}} & {g \over {{g \  j} -{h \  i}}} 
\end{array}
\right]
\end{array}
\]
and 
\[
\begin{array}{ccl}
{\rm\ AAbbb\ }& = &
\left[
\begin{array}{cc}
{f \over {{c \  f} -{d \  e}}} & -{d \over {{c \  f} -{d \  e}}} \\ 
-{e \over {{c \  f} -{d \  e}}} & {c \over {{c \  f} -{d \  e}}} 
\end{array}
\right]
\left[
\begin{array}{cc}
{f \over {{c \  f} -{d \  e}}} & -{d \over {{c \  f} -{d \  e}}} \\ 
-{e \over {{c \  f} -{d \  e}}} & {c \over {{c \  f} -{d \  e}}} 
\end{array}
\right]\\
& &
\left[
\begin{array}{cc}
g & h \\ 
i & j 
\end{array}
\right]
\left[
\begin{array}{cc}
g & h \\ 
i & j 
\end{array}
\right]
\left[
\begin{array}{cc}
g & h \\ 
i & j 
\end{array}
\right]
\end{array}
\]
or, in fully expanded form
\[
{\rm\ abaBAB\ }=
\left[
\begin{array}{cc}
{{{d \  e \  f \  {j \sp 3}}+{{\left( {{\left( -{d \  {f \sp 2}}+{c \  d \  
f}+{{d \sp 2} \  e} 
\right)}
\  i}+{{\left( {c \  e \  f}+{d \  {e \sp 2}} 
\right)}
\  h}+{{\left( -{d \  e}+{c \sp 2} 
\right)}
\  f \  g} 
\right)}
\  {j \sp 2}}+{{\left( {{\left( -{2 \  {d \sp 2} \  f}+{c \  {d \sp 2}} 
\right)}
\  {i \sp 2}}+{{\left( {{\left( -{c \  {f \sp 2}}+{3 \  c \  d \  e} 
\right)}
\  h}+{{\left( -{2 \  c \  d \  f} -{{d \sp 2} \  e}+{{c \sp 2} \  d} 
\right)}
\  g} 
\right)}
\  i}+{c \  {e \sp 2} \  {h \sp 2}}+{{\left( -{c \  e \  f}+{{c \sp 2} \  e} 
\right)}
\  g \  h} -{c \  d \  e \  {g \sp 2}} 
\right)}
\  j} -{{d \sp 3} \  {i \sp 3}}+{{\left( {{\left( -{c \  d \  f}+{{c \sp 2} \  
d} 
\right)}
\  h} -{2 \  c \  {d \sp 2} \  g} 
\right)}
\  {i \sp 2}}+{{\left( {{c \sp 2} \  e \  {h \sp 2}}+{{\left( -{{c \sp 2} \  
f}+{c \sp 3} 
\right)}
\  g \  h} -{{c \sp 2} \  d \  {g \sp 2}} 
\right)}
\  i}} \over {{{\left( {c \  f} -{d \  e} 
\right)}
\  {g \sp 2} \  {j \sp 2}}+{{\left( -{2 \  c \  f}+{2 \  d \  e} 
\right)}
\  g \  h \  i \  j}+{{\left( {c \  f} -{d \  e} 
\right)}
\  {h \sp 2} \  {i \sp 2}}}} & {{{{\left( -{d \  e \  f \  h} -{{d \sp 2} \  
e \  g} 
\right)}
\  {j \sp 2}}+{{\left( {{\left( {{\left( {d \  {f \sp 2}} -{c \  d \  f} 
\right)}
\  h}+{{\left( {{d \sp 2} \  f} -{c \  {d \sp 2}} 
\right)}
\  g} 
\right)}
\  i}+{{\left( -{c \  e \  f} -{d \  {e \sp 2}} 
\right)}
\  {h \sp 2}}+{{\left( {{\left( {d \  e} -{c \sp 2} 
\right)}
\  f} -{2 \  c \  d \  e} 
\right)}
\  g \  h}+{{\left( {c \  d \  f} -{{c \sp 2} \  d} 
\right)}
\  {g \sp 2}} 
\right)}
\  j}+{{\left( {{d \sp 2} \  f \  h}+{{d \sp 3} \  g} 
\right)}
\  {i \sp 2}}+{{\left( {{\left( {c \  {f \sp 2}} -{c \  d \  e} 
\right)}
\  {h \sp 2}}+{{\left( {2 \  c \  d \  f}+{{d \sp 2} \  e} -{{c \sp 2} \  d} 
\right)}
\  g \  h}+{2 \  c \  {d \sp 2} \  {g \sp 2}} 
\right)}
\  i} -{c \  {e \sp 2} \  {h \sp 3}}+{{\left( {c \  e \  f} -{2 \  {c \sp 2} 
\  e} 
\right)}
\  g \  {h \sp 2}}+{{\left( {{c \sp 2} \  f}+{c \  d \  e} -{c \sp 3} 
\right)}
\  {g \sp 2} \  h}+{{c \sp 2} \  d \  {g \sp 3}}} \over {{{\left( {c \  f} 
-{d \  e} 
\right)}
\  {g \sp 2} \  {j \sp 2}}+{{\left( -{2 \  c \  f}+{2 \  d \  e} 
\right)}
\  g \  h \  i \  j}+{{\left( {c \  f} -{d \  e} 
\right)}
\  {h \sp 2} \  {i \sp 2}}}} \\ 
{{{e \  {f \sp 2} \  {j \sp 3}}+{{\left( {{\left( -{f \sp 3}+{c \  {f \sp 
2}}+{d \  e \  f} 
\right)}
\  i}+{2 \  {e \sp 2} \  f \  h}+{{\left( -{e \  {f \sp 2}}+{c \  e \  f} 
\right)}
\  g} 
\right)}
\  {j \sp 2}}+{{\left( {{\left( -{2 \  d \  {f \sp 2}}+{c \  d \  f} 
\right)}
\  {i \sp 2}}+{{\left( {{\left( -{e \  {f \sp 2}}+{2 \  c \  e \  f}+{d \  {e 
\sp 2}} 
\right)}
\  h}+{{\left( -{c \  {f \sp 2}} -{2 \  d \  e \  f}+{c \  d \  e} 
\right)}
\  g} 
\right)}
\  i}+{{e \sp 3} \  {h \sp 2}}+{{\left( -{{e \sp 2} \  f}+{c \  {e \sp 2}} 
\right)}
\  g \  h} -{d \  {e \sp 2} \  {g \sp 2}} 
\right)}
\  j} -{{d \sp 2} \  f \  {i \sp 3}}+{{\left( {{\left( -{d \  e}+{c \sp 2} 
\right)}
\  f \  h}+{{\left( -{c \  d \  f} -{{d \sp 2} \  e} 
\right)}
\  g} 
\right)}
\  {i \sp 2}}+{{\left( {c \  {e \sp 2} \  {h \sp 2}}+{{\left( -{c \  e \  
f}+{{c \sp 2} \  e} 
\right)}
\  g \  h} -{c \  d \  e \  {g \sp 2}} 
\right)}
\  i}} \over {{{\left( {c \  f} -{d \  e} 
\right)}
\  {g \sp 2} \  {j \sp 2}}+{{\left( -{2 \  c \  f}+{2 \  d \  e} 
\right)}
\  g \  h \  i \  j}+{{\left( {c \  f} -{d \  e} 
\right)}
\  {h \sp 2} \  {i \sp 2}}}} & {{{{\left( -{e \  {f \sp 2} \  h} -{d \  e \  
f \  g} 
\right)}
\  {j \sp 2}}+{{\left( {{\left( {{\left( {f \sp 3} -{c \  {f \sp 2}} 
\right)}
\  h}+{{\left( {d \  {f \sp 2}} -{c \  d \  f} 
\right)}
\  g} 
\right)}
\  i} -{2 \  {e \sp 2} \  f \  {h \sp 2}}+{{\left( {e \  {f \sp 2}} -{2 \  c 
\  e \  f} -{d \  {e \sp 2}} 
\right)}
\  g \  h}+{{\left( {c \  {f \sp 2}} -{c \  d \  e} 
\right)}
\  {g \sp 2}} 
\right)}
\  j}+{{\left( {d \  {f \sp 2} \  h}+{{d \sp 2} \  f \  g} 
\right)}
\  {i \sp 2}}+{{\left( {{\left( {e \  {f \sp 2}} -{c \  e \  f} 
\right)}
\  {h \sp 2}}+{{\left( {3 \  d \  e} -{c \sp 2} 
\right)}
\  f \  g \  h}+{{\left( {c \  d \  f}+{{d \sp 2} \  e} 
\right)}
\  {g \sp 2}} 
\right)}
\  i} -{{e \sp 3} \  {h \sp 3}}+{{\left( {{e \sp 2} \  f} -{2 \  c \  {e \sp 
2}} 
\right)}
\  g \  {h \sp 2}}+{{\left( {c \  e \  f}+{d \  {e \sp 2}} -{{c \sp 2} \  e} 
\right)}
\  {g \sp 2} \  h}+{c \  d \  e \  {g \sp 3}}} \over {{{\left( {c \  f} -{d \  
e} 
\right)}
\  {g \sp 2} \  {j \sp 2}}+{{\left( -{2 \  c \  f}+{2 \  d \  e} 
\right)}
\  g \  h \  i \  j}+{{\left( {c \  f} -{d \  e} 
\right)}
\  {h \sp 2} \  {i \sp 2}}}} 
\end{array}
\right]
\]
and
\[
{\rm\ AAbbb\ }=
\left[
\begin{array}{cc}
{
\begin{array}{l}
{{\left( -{d \  f} -{c \  d} \right)}\  i \  {j \sp 2}}+\\
{{\left( {
{\left( {f \sp 2}+{d \  e} \right)}
\  h}+{
{\left( -{d \  f} -{c \  d} \right)}
\  g} 
\right)}\  i \  j}+\\
{{\left( -{d \  f} -{c \  d} \right)}\  h \  {i \sp 2}}+\\
{{\left( {
{\left( {2 \  {f \sp 2}}+{2 \  d \  e} \right)}\  g \  h}+
{{\left( -{d \  f} -{c \  d} \right)}\  {g \sp 2}} 
\right)}\  i}+\\
{{\left( {f \sp 2}+{d \  e} \right)}\  {g \sp 3}}
\end{array}
\over 
{{{c \sp 2} \  {f \sp 2}} -{2 \  c \  d \  e \  f}+{{d 
\sp 2} \  {e \sp 2}}}} & 
{{{
{\left( -{d \  f} -{c \  d} \right)}
\  {j \sp 3}}+{
{\left( {f \sp 2}+{d \  e} \right)}
\  h \  {j \sp 2}}+{
{\left( {
{\left( -{2 \  d \  f} -{2 \  c \  d} \right)}
\  h \  i}+{
{\left( {f \sp 2}+{d \  e} \right)}
\  g \  h} 
\right)}
\  j}+{
{\left( {{\left( {f \sp 2}+{d \  e} \right)}
\  {h \sp 2}}+{{\left( -{d \  f} -{c \  d} 
\right)}
\  g \  h} 
\right)}
\  i}+{
{\left( {f \sp 2}+{d \  e} \right)}
\  {g \sp 2} \  h}} 
\over 
{{{c \sp 2} \  {f \sp 2}} -{2 \  c \  d \  e \  f}+
{{d \sp 2} \  {e \sp 2}}}} \\ 
{{{
{\left( {d \  e}+{c \sp 2} \right)}
\  i \  {j \sp 2}}+{
{\left( {{\left( -{e \  f} -{c \  e} \right)}
\  h}+{
{\left( {d \  e}+{c \sp 2} \right)}
\  g} 
\right)}
\  i \  j}+{
{\left( {d \  e}+{c \sp 2} \right)}
\  h \  {i \sp 2}}+{
{\left( {{\left( -{2 \  e \  f} -{2 \  c \  e} \right)}
\  g \  h}+{
{\left( {d \  e}+{c \sp 2} \right)}
\  {g \sp 2}} 
\right)}
\  i}+{
{\left( -{e \  f} -{c \  e} \right)}
\  {g \sp 3}}} 
\over {{{c \sp 2} \  {f \sp 2}} -{2 \  c \  d \  e \  f}+
{{d \sp 2} \  {e \sp 2}}}} & 
{{{
{\left( {d \  e}+{c \sp 2} \right)}
\  {j \sp 3}}+{
{\left( -{e \  f} -{c \  e} \right)}
\  h \  {j \sp 2}}+{
{\left( {
{\left( {2 \  d \  e}+{2 \  {c \sp 2}} \right)}
\  h \  i}+{
{\left( -{e \  f} -{c \  e} \right)}
\  g \  h} 
\right)}
\  j}+{
{\left( {{\left( -{e \  f} -{c \  e} \right)}
\  {h \sp 2}}+{
{\left( {d \  e}+{c \sp 2} \right)}
\  g \  h} 
\right)}
\  i}+{
{\left( -{e \  f} -{c \  e} \right)}
\  {g \sp 2} \  h}} 
\over 
{{{c \sp 2} \  {f \sp 2}} -{2 \  c \  d \  e \  f}+
{{d \sp 2} \  {e \sp 2}}}} 
\end{array}
\right]
\]
\eject
\section{Multiplicative Invariants of Special 2-Complexes}
\noindent
{\sl Multiplicative Invariants of Special 2-Complexes \cite{5}}\\
{\bf John Rosson}(Portland State)\\
{\bf ABSTRACT}

This dissertation constructs total invariants to distinguish between
simple homotopy classes of simply connected 2-complexes. Frank Quinn
developed multiplicative invariants of 2 dimensional CW-complexes
(2-complexes) by using concepts from Topological Quantum Field
Theory. One motivation for this dissertation was to get invariants
that could survive stabilization and therefore potentially distinguish
Andrews-Curtis classes of 2-complexes. Such invariants would help
resolve the well known Andrews Curtis Conjecture that no nontrivial
Andrews Curtis Classes exist.

In this dissertation we follow Quinn's philosophy, but from the top
down. We first construct a canonical decomposition of a special
2-complex. Second, we introduce a category of algebraic objects,
called a double semigroup, which allows free constructions and
quotients. Next, we build a particular double semigroup whose elements
are a complete set of invariants for homeomorphism classes of special
2-complexes. Finally, we construct a double semigroup whose elements
are a complete set of Andrews Curtis invariants.
 
\begin{verbatim}
Tuesday, June 11, 2002

DISSERTATION COMMITTEE

M. Paul Latiolais, Chairman

Andrew M. Fraser

Joyce O’Halloran

Serge Preston
Erik Bodegom, Graduate Studies Rep.
\end{verbatim}
\vskip 0.5cm
\section{This Week's Finds in Mathematical Physics}
\noindent
{\sl This Week's Finds in Mathematical Physics (Week 23)\cite{4}}\\
{\bf John Baez}(University of Califonia Riverside)\\

I will soon revert to my older style, in which I list piles of new
papers as they accumulate on my desk. This time, though, I want to
describe Frank Quinn's work on the Andrews-Curtis conjecture using
topological quantum field theories (TQFTs), as promised. Then, if
you'll pardon me, I'll list the contents of a book I've just finished
editing. It is such a relief to be done that I cannot resist.

So -
\begin{list}{}
\item Topological quantum invariants and the Andrews-Curtis conjecture
(Progress report), by Frank Quinn, preprint, Sept. 1993.
\item Lectures on axiomatic topological quantum field theory, by Frank
Quinn, to appear in the proceedings of the Park City Geometry Institute.
\item On the Andrews-Curtis conjecture and related problems, by Wolfgang
Metzler, in Combinatorial Methods in Topology and Algebraic
Geometry, Contemporary Mathematics 44, AMS, 1985.
\end{list}

Last week I described - in a pretty sketchy way - how the 4-color
theorem and the Beraha conjecture are related to TQFTs. These can be
regarded as two very hard problems in 2-dimensional topology - one
solved by a mixture of cleverness and extreme brute force, the other
still open. There is another hard problem in 2-dimensional topology
called the Andrews-Curtis conjecture, which Quinn is working on using
TQFT methods, which I'll talk about this time. I don't know too much
about this stuff, so I hope any experts out there will correct my
inevitable mistakes.

Actually, this conjecture is easiest to describe in a purely algebraic
way, so I'll start there. Hopefully most of you know the concept of a
"presentation" of a group in terms of generators and relations. For
example, the group $Z_n$ (integers mod n) has the presentation
$<x|x^n>$. This means, roughly, that we form all products of the
"generator" x and its inverse, and then mod out by the "relation" 
$x^n= 1$. A bit more interesting is the dihedral group $D_n$ of symmetries of
a regular n-gon, counting rotations and reflections, with presentation
$<x, y|x^n, y^2, (xy)^2>$. Here $x$ corresponds to a clockwise rotation by
$1/n$-th of a turn, and $y$ corresponds to a reflection.

A group always has lots of different presentations, so a natural
problem is to decide whether two different presentations give the same
group (or, strictly speaking, isomorphic groups). It'd be nice to have
an algorithm for deciding this question. But it's a famous result of
mathematical logic that there is no such algorithm!

If two presentations give the same group, one can get from one to the
other by a sequence of the following easy steps, called Tietze moves:

\begin{list}{}
\item Throw in an extra new generator $x$ together with the extra new
relation $xg^{-1}$ where $g$ is a product of the previous generators and
their inverses.
\item 
\item The inverse of 1) - remove a generator $x$ together with the relation
$xg^{-1}$, if possible (the relation $xg^{-1}$ needs to be there!).  
\item Throw in a new relation that's a consequence of existing relations.
\item The inverse of 2) - remove a relation that's a consequence of other
relations.
\end{list}

So if one has two presentations and wants to see if they give same
group, you could always set up a program that blindly tries using
these Tietze moves in all possible ways to transform one presentation
into the other. If they are the same it'll eventually catch on! But if
they're not it'll chug on forever. There's no algorithmic way to tell
*when* it should give up and admit the two presentations give
different groups! - which is why we say there is no "decision
procedure" for this problem.

In one form, the Andrews-Curtis conjecture goes as follows. Remember
that the trivial group is the group with just the identity element; it
has a presentation $<x|x>$. Suppose we have some other "balanced"
presentation of the trivial group, that is a presentation with just as
many generators as relations: $<x_1,\ldots,x_n|r_1,\ldots,r_n>$. Then the
conjecture is that it can be reduced to the presentation $<x|x>$ by a
sequence of the following moves that keep the presentation balanced:

\begin{list}{}
\item Throw in an extra new generator $x$ together with the extra new
relation $x$.
\item The inverse of 1.
\item Permute the relations
\item Change $r_1$ to $r_1^{-1}$
\item Change $r_1$ to $r_1r_2$
\item Change $r_1$ to $gr_1g^{-1}$ for any $g$.
\end{list}

The experts seem to think this conjecture is probably false - but
nobody has disproved it. Metzler lists a few presentations of the
trivial group that might be counterexamples: nobody has ever found a
way to use moves 1-6 to boil them down to the presentation
$<x|x>$. For example,

$<a, b|b^5a^{-4}, aba(bab)^{-1}>$.

Try it!

The Andrews-Curtis conjecture is interesting mainly for its
implications in topology. When they first stated their conjecture they
noted a number of topological consequences, and the referee of the
paper noted one more. For example, it would shed some light on the
Poincare conjecture (although not settle it) as follows. Recall that
the Poincare conjecture says every 3-dimensional manifold homotopic to
a 3-sphere is homeomorphic to a 3-sphere. The Andrews-Curtis
conjecture implies that if the Poincare conjecture is false, any
counterexample can in fact be embedded (topologically) in $R^4$!

It was the referee (does anyone know who that was) who noted that the
Andrews-Curtis conjecture can be formulated in terms of "CW
complexes." This is how Quinn thinks about it, so I suppose I should
say what those are.

A 0-complex is simply a set of points given the discrete topology. We
call the points "0-cells." To get a 1-complex, we take a set of
"1-cells," that is, closed unit intervals, and glue their ends on to
the 0-cells in any way we want. In other words, we get a graph,
possibly with some edges having both ends at the same vertex. To get a
2-complex, we take a set of "2-cells," that is, 2-dimensional closed
disks, and glue their boundaries onto our 1-complex by any continuous
map. And so on, with the "n-cells" being just copies of the closed
unit ball in $R^n$.

CW complexes were invented by J. H. C. Whitehead in 1949 and are a key
tool in algebraic topology. (The word "CW," by the way, seems to come
from "closure-finite" and "weak" -- as in "weak topology.") They are a
nice class of topological spaces since on the one hand, being built up
by gluing simple pieces together, one can really understand them, and
on the other hand, they are actually quite general. In fact, if one is
interested in the usual invariants studied in algebraic topology
(homology and cohomology groups, homotopy groups and the like), CW
complexes are pretty much good enough. More precisely, Whitehead
proved a "CW approximation theorem" saying that any halfway decent
topological space (i.e., any "compactly generated" space) is "weakly
homotopy equivalent" to a CW complex. I won't burden you with the
definitions here; I learned this stuff once upon a time from

\begin{verbatim}
4) Elements of Homotopy Theory, by George W. Whitehead,
   Springer-Verlag, Berlin, 1978. ISBN 0-387-90336-4
\end{verbatim}

Anyway, the Andrews-Curtis conjecture can be thought of as being about
2-complexes. In fact, a group presentation can be regarded as
instructions for building up a 2-complex -- start with a point, glue
on 1-cells, one for each generator (obtaining a "bouquet of circles")
and then glue on 2-cells, one for each relation, attaching their
boundaries to the 1-cells in the manner presecribed by the
relation. This 2-complex will have fundamental group equal to the
group given by the presentation. The moves 1-6 above can be thought
of as operations on these 2-complexes. So one can translate the
Andrews-Curtis conjecture into a statement about 2-complexes. And at
this point I guess I'm going to start getting more technical...

One topological statement of the Andrews-Curtis conjecture is that "if
two 2-complexes are simply equivalent then one can be 2-deformed to
the other." I don't understand this as well as I want, so I won't
explain it; instead, I'll briefly explain the (weaker?) version
corresponding more closely to the algebraic statement above, namely
"if X is a contractible 2-complex, it can be 2-deformed to a point."
Being "contractible" means that as far as homotopy theory goes X is
just like a point. (E.g., the unit disk is contractible, while the
circle is not.) And a "2-deformation" roughly means a sequence of
moves consisting of adding or deleting 1-cells or 2-cells in a way
that doesn't affect things as far as homotopy goes, or doing
homotopies of attaching maps of 2-cells. The interesting thing about
these formulations of the Andrews-Curtis conjecture is that their
analogs for $n > 2$ are true and in fact were shown by J H C Whitehead
in 1939!

Quinn's goal is to cook up invariants of 2-complexes that might detect
counterexamples to the Andrews-Curtis conjecture, i.e., invariants
under 2-deformation. He wants to do it using 1+1-dimensional TQFTs of
a sort that assign vector spaces to 1-complexes and linear maps to
2-complexes. Traditionally, TQFTs assign vector spaces to n-manifolds
and linear maps to $(n+1)$-manifolds. Quinn calls his TQFTs "modular"
because they have a lot of formal similarities to the kind of TQFTs
that come up in string theory (where the modular group reigns
supreme). He gives a thorough axiomatic description of modular TQFTs
in his lecture notes, and this is actually the most fascinating aspect
for me, more so than the Andrews-Curtis conjecture per se, since it
bears on physics.

The problem with coming up with an TQFT invariant that can catch
counterexamples to the Andrews-Curtis conjecture is an interesting
"stabilization" property that 2-complexes have. Namely, if two
2-complexes are simply equivalent, one can can wedge them both with
some large number k of 2-spheres and get complexes which are
2-deformable to each other. It turns out that this means we want to
find a TQFT such that $Z(S^2)^k = 0$. And so Quinn considers TQFTs
based, not on the complex numbers, but on integers mod p.

A TQFT of his sort amounts to finding a symmetric tensor category of
vector spaces and an object A in this category with some special
properties corresponding to the fact that it is the vector space
corresponding to the unit interval $[0,1]$, which is the basic 1-complex
from which one can build up more fancy ones. The kind of category he
uses has been described by:

\begin{verbatim}
5) S. Gelfand and D. Kazhdan, Examples of tensor categories,
   Invent. Math. 109 (1992) 595-617.
\end{verbatim}

It is formed by starting with the category of representations of an
algebraic group in characteristic p, and then making a semisimple
category out of this in a manner strongly reminiscent of what they do
in the theory of quantum groups at roots of unity. (See "week5" for a
bit more about this.) The object A is taken to be the sum of one copy
of each irreducible representation. (Again, this is strikingly
reminiscent, and no doubt based on, what occurs in the physics of the
Wess-Zumino-Witten model, where quantum groups at roots of unity play
the role a finite group is playing here.)

So, to round off a long story, Quinn and Ivelini Bobtcheva are
currently engaged in some rather massive computer calculations in
order to actually explicitly obtain the data necessary to calculate in
the TQFTs of this form. They have been looking at the groups $SL(2)$,
$SL(3)$, $Sp(4)$ and $G_2$ over $Z_p$, where p is small (up to 19 for the
$SL(2)$ case). They are finding some interesting stuff just by
calculating the TQFT invariants of the 2-complexes corresponding to
the presentations $<x|x^n>$. (Note that $n = 0$ gives a space that's a
wedge of a circle and $S^2$, while $n = 1$ gives a disk.) Namely, they are
finding periodicity in $n$.

But they haven't found any counterexamples to the Andrews-Curtis
conjecture yet!

\begin{verbatim}
6) Knots and Quantum Gravity, ed. John Baez, 
   Oxford University Press (to appear).
\end{verbatim}

This is the proceedings of a workshop held at U.C. Riverside; a large
percentage of the papers contain new results. Let me simply list them:

\begin{verbatim}
The Loop Formulation of Gauge Theory and Gravity, by Renate Loll
\end{verbatim}

\begin{verbatim}
Representation Theory of Analytic Holonomy C* Algebras, by Abhay
Ashtekar and Jerzy Lewandowski 
\end{verbatim}

\begin{verbatim}
The Gauss Linking Number in Quantum Gravity, 
by Rodolfo Gambini and Jorge Pullin 
(currently available as gr-qc/9310025)
\end{verbatim}

\begin{verbatim}
Vassiliev Invariants and the Loop States in Quantum Gravity, 
by Louis H. Kauffman (soon to be on gr-qc)
\end{verbatim}

\begin{verbatim}
Geometric Structures and Loop Variables in 
(2+1)-Dimensional Gravity,
by Steven Carlip (currently available as gr-qc/9309020)
\end{verbatim}

\begin{verbatim}
From Chern-Simons to WZW via Path Integrals, by Dana S. Fine
\end{verbatim}

\begin{verbatim}
Topological Field Theory as the Key to Quantum Gravity, 
by Louis Crane (currently available as hep-th/9308126)
\end{verbatim}

\begin{verbatim}
Strings, Loops, Knots and Gauge Fields, by John Baez (currently
available as hep-th/9309067)
\end{verbatim}

\begin{verbatim}
BF Theories and 2-knots, 
by Paolo Cotta-Ramusino and Maurizio Martellini
\end{verbatim}

\begin{verbatim}
Knotted Surfaces, Braid Movies, and Beyond, 
by J. Scott Carter and Masahico Saito 
\end{verbatim}
\vskip 0.5cm
\section{A potential smooth counterexample in dimension 4\ldots}
\noindent
{\sl A potential smooth counterexample in dimension 4
to the Poincare conjecture, the Schonflies conjecture,
and the Andrew-Curtis conjecture\cite{3}}\\
{\bf Selman Akbulut and R. Kirby}\\
\vskip 0.5cm
\section{Canada Research Chair in Combinatorial Algebra}
\noindent
{\sl Canada Research Chair in Combinatorial Algebra\cite{2}}\\
{\bf Alexei Miasnikov}(McGill)\\
A second focus of Dr. Miasnikov’s program is to find a counterexample
to the Andrews-Curtis Conjecture, which holds that every balanced
presentation of a trivial group can be transformed into the standard
presentation by a finite sequence of elementary
transformations. Dr. Miasnikov posits that the Andrews-Curtis
Conjecture is false, and his proposed goal is to find a counterexample
in a finite quotient using computational methods.
\vskip 0.5cm
\section{Balanced presentations of the trivial group on\ldots}
\noindent
{\sl Balanced presentations of the trivial group on two generators and
the Andrews-Curtis conjecture\cite{7}}\\
{\bf Alexei D. Miasnikov and Alexei G. Myasnikov}(City College of New York)

Title: Balanced presentations of the trivial group on two generators
and the Andrews-Curtis conjecture

\begin{verbatim}
Authors: Alexei D. Miasnikov, Alexei G. Myasnikov
Categories: GR Group Theory
Math Subject Class: 20E05, 20F05, 
                    68T05 (Primary), 
                    57M05,57M20. (Secondary)
Journal reference: In W.Kantor and A.Seress,editors, 
                   Groups and Computation III, volume 23, 
                   (2001) 257-263, Berlin
Comments: 7 pages, no figures
\end{verbatim}

{\bf Abstract}: The Andrews-Curtis conjecture states that every balanced
presentation of the trivial group can be reduced to the standard
one by a sequence of the elementary Nielsen transformations and
conjugations. In this paper we describe all balanced presentations
of the trivial group on two generators and with the total length
of relators $<= 12$. We show that all these presentations satisfy
the Andrews-Curtis conjecture.

\begin{verbatim}
From: Alexei Miasnikov <alex@groups.sci.ccny.cuny.edu>
Date: Mon, 21 Apr 2003 21:01:49 GMT (11kb)

@article{math.GR/0304305,
 title = {{Balanced presentations of the trivial group on two
     generators and the Andrews-Curtis conjecture}},
 author = {Alexei D. Miasnikov and Alexei G. Myasnikov},
 journal = {In W. Kantor and A. Seress,editors, 
            Groups and Computation III, volume},
 volume = 23,
 year = 2001,
 pages = {257--263},
 eprint = {arXiv:math.GR/0304305}}

\end{verbatim}
\vskip 0.5cm
\section{Genetic algorithms and the Andrews-Curtis conjecture}
\noindent
{\sl Genetic algorithms and the Andrews-Curtis conjecture\cite{6}}\\
{\bf Alexei D. Miasnikov}(City College of New York)\\

Title: Genetic algorithms and the Andrews-Curtis conjecture

\begin{verbatim}
Author: Alexei D. Miasnikov
Categories: GR Group Theory
Math Subject Class: 20E05, 20F05, 68T05 (Primary) 57M05,57M20
Journal reference: 
International Journal of Algebra and Computation,
Vol. 9 No. 6, (1999) 671-686 Comments: 19 pages
\end{verbatim}

{\bf Abstract}: The Andrews-Curtis conjecture claims that every balanced
presentation of the trivial group can be transformed into the
trivial presentation by a finite sequence of "elementary
transformations" which are Nielsen transformations together with
an arbitrary conjugation of a relator. It is believed that the
Andrews-Curtis conjecture is false; however, not so many possible
counterexamples are known. It is not a trivial matter to verify
whether the conjecture holds for a given balanced presentation or
not. The purpose of this paper is to describe some
non-deterministic methods, called Genetic Algorithms, designed to
test the validity of the Andrews-Curtis conjecture. Using such
algorithm we have been able to prove that all known (to us)
balanced presentations of the trivial group where the total length
of the relators is at most 12 satisfy the conjecture. In
particular, the Andrews-Curtis conjecture holds for the
presentation $<x,y|x y x = y x y, x^2 = y^3>$ which was one of the
well known potential counterexamples.

\begin{verbatim}
From: Alexei Miasnikov <alex@groups.sci.ccny.cuny.edu>
Date: Mon, 21 Apr 2003 21:07:18 GMT (13kb)

@misc{math.GR/0304306,
 title = 
   {{Genetic algorithms and the Andrews-Curtis conjecture}},
 author = {Alexei D. Miasnikov},
 howpublished = 
   {International Journal of Algebra and Computation, 
    Vol. 9 No. 6, (1999) 671-686},
  eprint = {arXiv:math.GR/0304306}}
\end{verbatim}
\vskip 0.5cm
\section{A remark on the stable Andrews-Curtis conjecture}
\noindent
{\sl A remark on the stable Andrews-Curtis conjecture\cite{1}}\\
{\bf Andrew Casson} (Yale)\\
The stable Andrews-Curtis conjecture in combinatorial group theory is
equivalent to the conjecture that every finite contractible 2-complex
can be reduced to a single point by elementary expansions and
collapses through complexes of dimension at most 3. In group-theoretic
terms, this means that every presentation of the trivial group with
equal numbers of generators and relators can be simplified to standard
form by elementary moves corresponding to "addition of cells" or
"handle-slides", together with "stabilization" moves that increase or
decrease the number of generators (and relators). The role of the
stabilization moves is unclear; conceivably any presentation that can
be simplified using the full set of moves can also be simplified
without stabilization. I will discuss several equivalent forms of the
conjecture, and present (rather weak) evidence that presentations can
be "improved" by stabilization.
\vskip 0.5cm
\noindent
\section{Algebraic Geometry over Groups}
{\sl Algebraic Geometry over Groups\cite{8}}\\
{\bf Gilbert Baumslag, A. Myasnikov and V. Remeslennikov}\\
2000/01 The Andrews-Curtis conjecture, a problem on locally finite
groups, some aspects of Grigorchuk groups, and the paper 'Algebraic
Geometry over Groups' by G. Baumslag, A. Myasnikov, and
V. Remeslennikov which appeared in J. Algebra 219 (1999).
\vskip 0.5cm
2000/01 The Andrews-Curtis conjecture, a problem on locally finite groups, some aspects of Grigorchuk groups, and the paper 'Algebraic Geometry over Groups' by G. Baumslag, A. Myasnikov, and V. Remeslennikov which appeared in J. Algebra 219 (1999).
\vskip 0.5cm
Algebraic Geometry over Groups I. Algebraic Sets and Ideal Theory

Gilbert Baumslag,  Alexei Myasnikovb, and Vladimir Remeslennikovc

Received 8 January 1999.  Available online 10 April 2002.

Abstract

The object of this paper, which is the first in a series of three, is
to lay the foundations of the theory of ideals and algebraic sets over
groups.

References
\begin{verbatim}
AL. L. Auslander, 
On a problem of Philip Hall. 
Ann. of Math. (2) 86
(1967), pp. 112–116. MathSciNet

BH. H. Bass, 
Groups acting on non-archimedian trees. 
Arboreal Group Theory (1991), pp. 69–130.

BB. B. Baumslag, 
Residually free groups. 
Proc. London Math. Soc. 17 (1967), 
pp. 402–418. MathSciNet

BG. G. Baumslag, 
On generalized free products. Math. Z. 7 (1962),
pp. 423–438. MathSciNet

BMR1. G. Baumslag, A. Myasnikov and V. Remeslennikov, 
Residually hyperbolic groups and approximation theorems 
for extensions of centralizers. 
Proc. Inst. Appl. Math Russian Acad. Sci. 24 (1996),
pp. 3–37.

BMR2. G. Baumslag, A. Myasnikov, and, V. Remeslennikov, 
Discriminating completions of hyperbolic groups, 
submitted for publication.

BMRO. G. Baumslag, A. Myasnikov and V. Roman\'kov, 
Two theorems about equationally Noetherian groups. 
J. Algebra 194 (1997), pp. 654–664. 
Abstract | Abstract + References | PDF (176 K) | MathSciNet

BR. R. Bryant, The verbal topology of a group. 
J. Algebra 48 (1977), pp. 340–346. MathSciNet

CK. C. C. Chang and H. J. Keisler. 
Model Theory, 
North-Holland, New York (1973).

CE. L. P. Comerford and C. C. Edmunds, 
Quadratic equations over free groups and free products. 
J. Algebra 68 (1981), pp. 276–297. MathSciNet

FGMRS. B. Fine, A. M. Gaglione, A. Miasnikov, 
G. Rosenberger and D. Spellman, 
A classification of fully residual free groups of 
rank three or less. 
J. Algebra 200 (1998), pp. 571–605. Abstract | Abstract
+ References | PDF (355 K) | MathSciNet

GK. R. I. Grigorchuk and P. F. Kurchanov, 
Some questions of group theory related to geometry. 
Itogi Nauki i Techniki, Sovremennye
Problemy Matematiki, Fundamental'nye Napravlenia, VINITI,
58Encyclopedia of Mathematical Sciences (1990).

GV. V. Guba, 
Equivalence of infinite systems of equations in 
free groups and semigroups to finite subsystems. 
Mat. Zametki 40 (1986),
pp. 321–324.

HR. R. Hartshorne. 
Algebraic Geometry, 
Springer-Verlag, New York (1977).

HZ. E. Hrushovski and B. Zilber, 
Zariski geometries. 
J. Amer. Math. Soc. 9 (1996), pp. 1–56. MathSciNet

KMS. A. Karrass, W. Magnus and D. Solitar, 
Elements of finite order in groups with 
a single defining relation. 
Comm. Pure Appl. Math. 13 (1960), pp. 458–466.

KM. O. Kharlampovich and A. Myasnikov, 
Irreducible affine varieties over a free group. 
I: irreducibility of quadratic equations and 
Nullstellensatz. J. Algebra 200 (1998), pp. 472–516. 
Abstract | Abstract + References | PDF (445 K) | MathSciNet

KM. O. Kharlampovich and A. Myasnikov, 
Irreducible affine varieties over a free group. 
II: systems in triangular quasi-quadratic form and
description of residually free groups. 
J. Algebra 200 (1988), pp. 517–570.

LR1. R. C. Lyndon, 
The equation a2b2 = c2 in free groups. 
Michigan Math. J. 6 (1959), pp. 155–164. MathSciNet

LR2. R. C. Lyndon, 
Groups with parametric exponents. 
Trans. Amer. Math. Soc. 96 (1960), pp. 518–533. MathSciNet

LR3. R. C. Lyndon, 
Equation in free groups. 
Trans. Amer. Math. Soc. 96 (1960), pp. 445–457. MathSciNet

MKS. W. Magnus, A. Karrass and D. Solitar. 
Combinatorial Group Theory:
Presentations of Groups in Terms of Generators and Relations,
Wiley-Interscience, New York/London/Sydney (1966).

MG. G. S. Makanin, 
Decidability of the universal and positive theories
of a free group. 
Izv. Akad. Nauk SSSR Ser. Math. 48 (1985), pp. 735–749.

MR1. A. G. Myasnikov and V. N. Remeslennikov, 
Exponential groups I:
Foundations of the theory and tensor completion. 
Siberian Math. J. 35 (1994), pp. 1106–1118.

MR2. A. G. Myasnikov and V. N. Remeslennikov, 
Exponential groups II:
Extensions of centralizers and tensor completion of
CSA-groups. 
Internat. J. Algebra Comput. 6 (1996),
pp. 687–711. MathSciNet

PB. B. Plotkin, 
Varieties of algebras and algebraic varieties. 
Categories of algebraic varieties, 
Hebrew University, Jerusalem, 1996, preprint.

RA1. A. Razborov, 
On systems of equations in a free group. 
Math. USSR-Izv. 25 (1985), pp. 115–162.

RA2. A. Razborov, 
On systems of equations in a free group,
Ph.D. thesis, Steklov Math. Institute, Moscow, 1987.

RV1. V. N. Remeslennikov, 
E-free groups. 
Siberian Math. J. 30 (1989), pp. 153–157.

RV2. V. N. Remeslennikov, 
Matrix representation of finitely generated 
metabelian groups. 
Algebra i Logika 8 (1969), pp. 72–76.

SW. W. R. Scott, 
Algebraically closed groups. 
Proc. Amer. Math. Soc. 2 (1951), pp. 118–212.

SM. M. P. Schutzenberger, 
Sur l'equation a2th = b2 + mc2 + p dans un group libre. 
C.R. Acad. Sci. Paris 248 (1959), pp. 2435–2436. MathSciNet

SJ. J. Stallings, 
Finiteness properties of matrix representations. 
Ann. of Math. 124 (1986), pp. 337–346. MathSciNet

WB. B. A. F. Wehrfritz. 
Infinite Linear Groups, 
Springer-Verlag, New York/Heidelberg/Berlin (1973).

\end{verbatim}
\vskip 0.5cm
\section{Representation theory, topological field theory, and\ldots}
\noindent
{\sl Representation theory, topological field theory, and the 
Andrews-Curtis conjecture\cite{9}}\\
{\bf Frank Quinn}\\
\begin{verbatim}

Title: Representation theory, topological field theory, 
       and the Andrews-Curtis conjecture

Author: Frank Quinn
Categories: (QA Quantum Algebra; GR Group Theory)
Comments: 7 pages. 
ADMIN NOTE: source file was garbled, partially salvaged 19Feb2001
\end{verbatim}

{\bf Abstract}: We pose a representation-theoretic question motivated by
an attempt to resolve the Andrews-Curtis conjecture. Roughly, is
there a triangular Hopf algebra with a collection of self-dual
irreducible representations $V_i$ so that the product of any two
decomposes as a sum of copies of the $V_i$, and 
$\sum ({\rm\ rank\ }V_i)^2=0$? 
This data can be used to construct a `topological
quantum field theory' on 2-complexes which stands a good chance of
detecting counterexamples to the conjecture.

\begin{verbatim}
From: Frank Quinn <quinn@math.vt.edu>
Date: Thu, 13 Feb 1992 14:42 EDT (7kb)
Revised: Fri, 14 Feb 1992 14:32 EDT

@misc{hep-th/9202044,
  title = {{Representation theory, topological field theory, 
            and the Andrews-Curtis conjecture}},
  author = {Frank Quinn},
  eprint = {arXiv:hep-th/9202044}}

\end{verbatim}
\section{The Makefile}
<<Makefile>>=
NOTANGLE=/usr/local/bin/NOTANGLE
NOWEAVE=/usr/local/bin/NOWEAVE

all: ACConjecture.dvi ACConjecture.lisp
	@echo 3 done

Makefile: ACConjecture.pamphlet
	@echo 4 making Makefile
	@${NOTANGLE} -t8 -RMakefile ACConjecture.pamphlet >Makefile

ACConjecture.dvi: ACConjecture.pamphlet
	@echo 1 making ACConjecture.dvi
	@${NOWEAVE} -delay ACConjecture.pamphlet >ACConjecture.tex
	@latex ACConjecture.tex
	@latex ACConjecture.tex

ACConjecture.lisp: ACConjecture.pamphlet
	@echo 2 making ACConjecture.lisp
	@${NOTANGLE} ACConjecture.pamphlet >ACConjecture.lisp

@
\begin{thebibliography}{99}
\bibitem{1} Casson, Andrew,\\
{\sl ``A remark on the stable Andrews-Curtis conjecture''},\\
{\bf ``http://www.math.yale.edu/users/yair/topsem/casson\_abs.html''}
\bibitem{2} Miasnikov, Alexei,\\
{\sl ``Canada Research Chair in Combinatorial Algebra''},\\
{\bf ``http://www.chairs.gc.ca''}
\bibitem{3} Akbulut, Selman; Kirby, R.,\\
{\sl ``A potential smooth counterexample in dimension 4
to the Poincare conjecture, the Schonflies conjecture,
and the Andrew-Curtis conjecture''},\\
{\bf ``http://www.mth.msu.edu/~akbulut/vita/vita.html''},\\
Topology 24, no. 4 (1985), 375-390.
\bibitem{4} Baez, John,\\
{\sl ``This Week's Finds in Mathematical Physics (Week 23)''},\\
{\bf ``http://math.ucr.edu/home/baez/week23.html''}
\bibitem{5} Rosson, John,\\
{\sl ``Multiplicative Invariants of Special 2-Complexes''},\\
{\bf ``http://www.sysc.pdx.edu/newabstracts/abstract-rosson.htm''}
\bibitem{6} Miasnikov, Alexei,\\
{\sl ``Genetic algorithms and the Andrews-Curtis conjecture''},\\
{\bf ``http://front.math.ucdavis.edu/math.GR/0304306''}
\bibitem{7} Miasnikov, Alexei D.; Myasnikov, Alexei G.\\
{\sl ``Balanced presentations of the trivial group on two generators and
the Andrews-Curtis conjecture},\\
{\bf ``http://front.math.ucdavis.edu/math.GR/0304305''}
\bibitem{8} Baumslag, Gilbert, Myasnikov, A. and Remeslennikov,\\
{\sl ``Algebraic Geometry over Groups''},\\
{\bf ``http://front.math.ucdavis.edu/math.GR/0304305''}
Journal of Algebra Volume 219, Issue 1 , 1 September 1999, Pages 16-79
\bibitem{9} Quinn, Frank\\
{\sl ``Representation theory, topological field theory, and the 
Andrews-Curtis conjecture''},\\
{\bf ``http://front.math.ucdavis.edu/hep-th/9202044''}
\end{thebibliography}
\end{document}