\documentclass{slides}
\usepackage[landscape,pdftex]{geometry}
\parindent=0pt \parskip=0pt

\usepackage{amssymb,amsmath,amsthm}
\input{../tex/isomath}

%% ================================================================
\newcommand{\Dn}{\mathcal{D}_n}
\newcommand{\Sn}{\mathcal{S}_n}
\newcommand{\An}{\mathcal{A}_n}
\newcommand{\Vf}{\mathcal{V}_4}
\newcommand{\Qe}{\mathcal{Q}_8}
\newcommand*{\pig}[1]{\langle #1 \rangle}

%% ================================================================
\begin{document}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
CONCRETE ABSTRACT ALGEBRA IN PYTHON \\
\vspace{1.0in}
John Kerl \\
University of Arizona \\
Department of Mathematics \\
Software Interest Group \\
April 5, 2006
\end{center}
\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Overview}
\end{center}

\begin{itemize}
\vspace{-0.25in} \item History
\vspace{-0.25in} \item Python basics
\vspace{-0.25in} \item Concrete groups
\vspace{-0.25in} \item Algorithms for abstract groups
\end{itemize}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{History}
\end{center}

SACK:  simple algebra calculator.

Previous version was written in C during a senior-level undergraduate course in
abstract algebra.  Naive algorithms; short feature list.

Imitates Unix \texttt{bc} program:  If the computer can multiply 10981765243
and 76452183109, then it ought to be able to compose the permutations
$(10\;9\;8)(1\;7)(6\;5\;2)(4\;3)$ and $(7\;6)(4\;5)(2\;1\;8\;3)(10\;9)$.

Joubert: ``To teach is to learn twice.''  I wrote SACK from scratch and learned
many things in the process, which I would not had I stuck solely with programs
such as GAP.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Python} \ldots
\end{center}

\ldots is an \textbf{object-oriented} (illustrated by example in this paper)
\textbf{scripting} (not compiled as a separate step, though Perl and Python do
just-in-time compilation) \textbf{language}.

We have many mathematical software tools:  Mathematica, Maple, MATLAB, etc.
Python on the other hand is a \textbf{general-purpose language}.  However, it
is intutive and math-friendly (e.g. lists and complex floating-point numbers).

Sometimes there is no pre-existing tool or library for a particular problem and
we need to program.  Python is good as a first programming language.

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{More information}
\end{center}

These slides are a condensation of:

\texttt{http://math.arizona.edu/{\textasciitilde}kerl/doc/kerl-pyaa.pdf}

For a thorough introduction, see Lutz \& Ascher's \emph{Learning Python}
(O'Reilly 2004), or \texttt{www.python.org}.

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Basics}
\end{center}

Python may be run either \textbf{interactively} (command prompt) or
\textbf{scripted} (put commands in one or more files).

\begin{verbatim}
kerl@gila:pyaa% python
Python 2.2.2 (#1, Feb 24 2003, 19:13:11)
[GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-4)] on linux2
Type "help", "copyright", "credits" or "license" for
more information.
>>> 1+2
3
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
%\textbf{Basics}
\end{center}

Script example:  have a file \texttt{factorial.py}.
\begin{verbatim}
def fact(n): # Here is how you write a comment in Python.
    if (n < 0):
        return 0
    elif (n <= 1):
        return 1
    else:
        return n * fact(n-1)
\end{verbatim}

Then:
\begin{verbatim}
kerl@gila:pyaa% python -i factorial.py
>>> fact(10)
3628800
>>>
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Main points about python}
\end{center}

\begin{itemize}
\vspace{-0.25in}
\item Variables don't need to be declared before use.
\vspace{-0.25in}
\item \textbf{Control structures}, e.g. if-statements, while-loops, for-loops,
etc are indicated purely by \textbf{indentation}, rather than by curly braces
or end-statements as in most other languages.
\vspace{-0.25in}
\item Due largely to these two facts, Python reads like \textbf{pseudocode}:
Python programs often do just what they look like they do, with little
syntactical overhead.
\end{itemize}

There are four language features which make Python ideal for abstract algebra:
\textbf{lists}, \textbf{operator overloading}, \textbf{run-time binding}, and
\textbf{modules}.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Lists}
\end{center}

Python has a flexible \textbf{list} type with the following features:

\begin{itemize}

\vspace{-0.25in} \item \textbf{Indexed}, e.g. they can be treated as
arrays (note: zero-based).

\vspace{-0.25in} \item \textbf{Nested}, e.g. they can be used for
matrices, or higher-dimensional arrays.  Useful for representing
cosets, direct products, etc.

\vspace{-0.25in} \item \textbf{Heterogeneous}, e.g. the first
element of a list can be a number, the second a string, the third a sublist,
etc.  Ee.g. matrices:  each list element is an array, all of the same length;
list of conjugacy classes:  not all the same length.

\end{itemize}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Zero-based indexing and bounds checking:
\begin{verbatim}
>>> mylist=[1,2,3]
>>> mylist[0]
1
>>> mylist[1]
2
>>> mylist[2]
3
>>> mylist[3]
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
IndexError: list index out of range
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

List heterogeneity:

\begin{verbatim}
>>> mylist=["hello", 3, [2,3,4]]
>>>
>>> mylist[0]
'hello'
>>> mylist[1]
3
>>> mylist[2]
[2, 3, 4]
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Iteration:

Often we want to loop over the elements of a list:

\begin{verbatim}
>>> mylist=[0,2,4,6]
>>> for element in mylist:
...    print element

0
2
4
6
\end{verbatim}

\begin{verbatim}
>>> for i in range(0, 4):
...    print i**2,
...
0 1 4 9
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Operator overloading}
\end{center}

Example:  modular addition (representation of cyclic group on $n$ elements.)

We want to be able to use this in the following way:
\begin{verbatim}
a = modadd_t(5, 11)
b = modadd_t(8, 11)
c = a * b
print c
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
Implementation:

\begin{verbatim}
class modadd_t:
    def __init__(self, residue, modulus):
        self.residue = residue % modulus
        self.modulus = modulus
    # Use "*" for addition.  Seems weird, but groups
    # are abstracted multiplicatively in SACK.
    def __mul__(a,b):
        if (a.modulus != b.modulus):
            print "Mixed moduli %d, %d" % (a, b)
            sys.exit(1)
        c = modadd_t(a.residue + b.residue, a.modulus)
        return c
    ...
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Run-time binding}
\end{center}

Above we saw a \texttt{modadd\_t} data type.  Suppose there are others,
e.g. \texttt{dih\_t} for elements of the dihedral group $\mathcal{D}_n$,
etc.

\begin{verbatim}
    a = modadd_t(2, 5);      d=modadd_t(3, 5)
    b = dih_t(2, 0, 8);      e=dih_t(3, 1, 8)
    c = pmt_t([0 3 1 2], 4); f=pm_t([3 2 0 1], 4)
    X = [a,b,c];             Y = [d,e,f]
    Z = [X[0]*Y[0], X[1]*Y[1], X[2]*Y[2]]
\end{verbatim}

More generally, we can make functions which operate on lists of objects,
and the functions we write don't need to know anything ahead of time about
the data types of those objects.  As long as the objects can be multiplied
using the * operator, our code will work just fine.  This is the essence
of abstraction.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Modules}
\end{center}

See the paper for info; not presented in the slides.

%When you write a Python program, you can put everything in one file.
%Alternatively, you can place certain items in separate files.  For example,
%suppose you have some often-used routines which will be used by many different
%scripts.  A factorial routine is a good example of this.  We can create
%a file named \texttt{fact\_m.py} with the following contents:
%
%\begin{verbatim}
%def fact(n):
%    if (n < 0):
%        return 0
%    value = 1
%    while (n > 0):
%        value = value * n
%        n -= 1
%    return value
%\end{verbatim}
%
%The trailing \texttt{\_m} is, again, my convention:  it stands for
%\emph{module}.  Another program can use this routine by doing two things: (1)
%import the module; (2) call the routine with module name, dot, function name.
%For example:
%
%\begin{verbatim}
%import fact_m
%x = fact_m.fact(20)
%\end{verbatim}
%
%Side note: The implementation of \texttt{fact} shown at the beginning of this
%document was \textbf{recursive}, since it called itself.  The implementation
%shown just above is \textbf{iterative}, since it loops.  This is akin to the
%difference between defining $n!$ recursively via
%$$ n! =
%    \left\{ \begin{array}{ll}
%    n \cdot (n-1)!, & n > 0\\
%    1 & n = 0
%    \end{array} \right.
%$$
%versus iteratively by
%$$ n! = \prod_{k=1}^n k.$$
%
%Above I noted that the \texttt{inv()} method is spelled the same for all data
%types, so that I can invert any element \texttt{a} of any group using
%\texttt{a.inv()}.  Likewise, for group-fill functions below, several modules
%will have a function named \texttt{get\_elements()}.  This way, we can put the
%name of a desired group into a variable called, say, \texttt{group\_name}, then
%get the contents by invoking \texttt{group\_name.get\_elements()}.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Concrete groups}
\end{center}

We already saw \texttt{modadd\_t}.  Here we'll look at \texttt{dih\_t}.

Dihedral groups (symmetries of plane $n$-gons) could have been
implemented as subgroups of $\mathcal{S}_n$.  In fact, \emph{all} these small
finite groups could be done this way.  The point is that by implementing
specific data types, we obtain more user-friendly input-output representations.

There are two levels of software needed for each group: (1) routines to deal
with individual group elements, and (2) routines to construct a list of all the
elements of a group.

\end{slide}

%% ----------------------------------------------------------------
%\begin{slide}
%\begin{center}
%\textbf{$\Vf$ and $\Qe$}
%\end{center}
%
%For the Klein-four group, we observe that $\Vf \cong \Z_2 \times \Z_2$.  It
%takes two bits to represent a Klein-four element.  Addition mod 2 is done using
%the XOR operation, which is written with a caret.
%
%\begin{verbatim}
%class v4_t:
%    def __init__(self, argcode):
%        self.code = argcode & 3
%    def __eq__(a,b):
%        return (a.code == b.code)
%    def __ne__(a,b):
%        return not (a == b)
%    def __mul__(a,b):
%        c = v4_t(a.code ^ b.code)
%        return c
%    def inv(a):
%        c = v4_t(a.code)
%        return c
%    def __str__(self):
%        if (self.code == 0):
%            return "e"
%        elif (self.code == 1):
%            return "a"
%        elif (self.code == 2):
%            return "b"
%        elif (self.code == 3):
%            return "c"
%        else:
%            raise IOError
%\end{verbatim}
%
%The unit quaternions are similar, except a lookup table is used to define the
%arithmetic operation.
%
%\begin{verbatim}
%quatu_mul_table = [
%    # 1 -1  i -i  j -j  k -k
%    [ 0, 1, 2, 3, 4, 5, 6, 7 ], #  1
%    [ 1, 0, 3, 2, 5, 4, 7, 6 ], # -1
%    [ 2, 3, 1, 0, 6, 7, 5, 4 ], #  i
%    [ 3, 2, 0, 1, 7, 6, 4, 5 ], # -i
%    [ 4, 5, 7, 6, 1, 0, 2, 3 ], #  j
%    [ 5, 4, 6, 7, 0, 1, 3, 2 ], # -j
%    [ 6, 7, 4, 5, 3, 2, 1, 0 ], #  k
%    [ 7, 6, 5, 4, 2, 3, 0, 1 ], # -k
%]
%\end{verbatim}
%
%\begin{verbatim}
%    ...
%    def __mul__(a,b):
%        c = quatu_t(quatu_mul_table[a.code][b.code]);
%        return c
%    ...
%\end{verbatim}
%
%The remaining unit-quaternion methods are similar to their Klein-four
%counterparts.
%\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Dihedral groups}
\end{center}

The dihedral group $\Dn$ is here taken to be the symmetry group
on a plane $n$-gon.  It has order $2n$ and is given by the following
presentation:
$$ \Dn = \pig{\rho, \phi \;|\; \rho^n = \phi^2 = 1, \phi\rho = \rho^{n-1}\phi}.$$
From the presentation, the element $\rho$ (\emph{rho} for \emph{rotate}) has
order $n$; the element $\phi$ (\emph{phi} for \emph{flip}) has order 2.
Furthermore, repeated use of the final relation enables any element of
$\Dn$ to be put into the form $\rho^i\phi^j$ for $i=0, 1, 2, \ldots, n-1$
and $j=0, 1$.  Thus, given two elements $\rho^i\phi^j$ and $\rho^k\phi^\ell$
of $\Dn$, we obtain the product
\begin{eqnarray*}
    j=0: &\quad \rho^i \rho^k \phi^\ell &= \rho^{i+k} \phi^\ell\\
    j=1: &\quad \rho^i \phi \rho^k \phi^\ell &= \rho^{i-k} \phi^{\ell+1}
\end{eqnarray*}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

As with the cyclic group, the modulus $n$ is carried around in each element of
the group.  The group operation may be implemented as follows.

As with the modular-addition data type, we reduce the exponent of $\rho$ mod
$n$ at construction time, and likewise we reduce the exponent of $\phi$ mod 2,
to obtain unique representatives.  This permits the \texttt{\_\_eq\_\_} and
\texttt{\_\_ne\_\_} methods to do exact comparisons.
\begin{verbatim}
class dih_t:
    def __init__(self, argrot, argflip, argn):
        self.n    = argn
        self.rot  = argrot  % self.n
        self.flip = argflip & 1
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

\begin{verbatim}
    def __eq__(a,b):
        return ((a.rot == b.rot) and (a.flip == b.flip))
    def __ne__(a,b):
        return not (a == b)
    def __mul__(a,b):
        if (a.n != b.n):
            raise RuntimeError
        if (a.flip):
            crot = a.rot - b.rot
        else:
            crot = a.rot + b.rot
        c = dih_t(crot, a.flip ^ b.flip, a.n)
        return c
    ...
\end{verbatim}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Fill routines}
\end{center}

Loop over exponents on $\rho$, namely
$0$ to $n-1$, and flip exponents $0$ to $1$:

\begin{verbatim}
def get_elements(params_string):
    n = dih_tm.params_from_string(params_string)
    elts = []
    for i in range(0, n):
        for j in range(0, 2):
            elt = dih_tm.dih_t(i, j, n)
            elts.append(elt)
    return elts
\end{verbatim}


\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Algorithms for abstract groups}
\end{center}

Now that we can do arithmetic on group elements, and now that we can obtain
groups, we can do \textbf{abstract} computations on various \textbf{concrete}
groups.  Thanks to Python's heterogeneous lists, operator overloading, and
run-time binding, we can write some very straightforward code to do this.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Data structures}
\end{center}

Groups are represented simply as lists of elements.

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Set routines}
\end{center}

A few self-explanatory set-related routines:

\begin{verbatim}
def element_of(x, S):
    for a in S:
        if (a == x):
            return 1
    return 0
def subset_of(T, S):
    for t in T:
        if (not element_of(t, S)):
            return 0
    return 1
def set_append_unique(S, x):
    if (not element_of(x, S)):
        S.append(x)
\end{verbatim}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Group axioms}
\end{center}

It is easy to check whether an array of elements is in fact a group:

\begin{verbatim}
def is_group(G):
    if (not is_closed(G)):
        return 0
    if (not is_associative(G)):
        return 0
    if (not has_unique_id(G)):
        return 0
    if (not has_inverses(G)):
        return 0
    return 1
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Here is the associativity-checking routine; the others are similar.  As well,
the is-abelian routine follows the same pattern.

\begin{verbatim}
def is_associative(G):
    for a in G:
        for b in G:
            ab = a * b
            for c in G:
                bc = b * c
                ab_c = ab * c
                a_bc = a * bc
                if (ab_c != a_bc):
                    return 0
    return 1
\end{verbatim}
\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Orders}
\end{center}

Order of a group:  \texttt{len(G)}.  Order of an element:

\begin{verbatim}
def get_order(x):
    xp = x * x
    k = 2
    while (1):
        if (xp == x):
            return k-1
        xp = xp * x
        k = k + 1
    return 0
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

There is a trick here: We could require that the group's identity $e$ be passed
in as a separate argument, then find the minimal positive exponent $j$ such
that $x^j=e$.  Instead, we can find the minimal positive exponent $k$ such that
$x^k=x$, then return $k-1$.

This routine permits another pair of concepts to be implemented easily:

\begin{itemize}
\vspace{-0.25in}
\item Maximal element order:  For each element $x$ of the group $G$, compute
the element order of $x$.  Take the maximum of all these.
\vspace{-0.25in}
\item Cyclicity:  Compute the maximal element order.  Test it for equality
against the group order.
\end{itemize}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Example:
\begin{verbatim}
kerl@gila:pyaa% sack s:6 order .
720
kerl@gila:pyaa% sack a:6 order .
360
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Example:
\begin{verbatim}
kerl@gila:pyaa% sack a:4 orders .
0,1,2,3 1
0,2,3,1 3
0,3,1,2 3
1,0,3,2 2
1,2,0,3 3
1,3,2,0 3
2,0,1,3 3
2,1,3,0 3
2,3,0,1 2
3,0,2,1 3
3,1,0,2 3
3,2,1,0 2
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Cayley table}
\end{center}

Printing a Cayley table uses the fact that Python's \texttt{print} statement
writes a carriage return unless its arguments are followed by a comma.  The key
point here is that due to run-time binding, Python invokes the
\texttt{\_\_str\_\_} method appropriate to each object in the list.

\begin{verbatim}
def print_cayley_table(G):
    for a in G:
        for b in G:
            c = a*b
            print c,
        print
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Example:

\begin{verbatim}
kerl@gila:pyaa% sack q8 caytbl .
 1 -1  i -i  j -j  k -k
-1  1 -i  i -j  j -k  k
 i -i -1  1  k -k -j  j
-i  i  1 -1 -k  k  j -j
 j -j -k  k -1  1  i -i
-j  j  k -k  1 -1 -i  i
 k -k  j -j -i  i -1  1
-k  k -j  j  i -i  1 -1
\end{verbatim}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Cosets}
\end{center}

A routine to compute left cosets:
\begin{verbatim}
def left_cosets(G, H):
    oG = len(G)
    oH = len(H)
    iGH = oG / oH
    ... (error-checking here: does |H| divide |G|?)
    GH = []
    for g in G:
        gHe = range(0, oH) # Make a list of length |H|
        for j in range(0, oH):
            gHe[j] = g * H[j]
        gH = coset(gHe)
        set_append_unique(GH, gH)
    return GH
\end{verbatim}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Direct products}
\end{center}

A SACK tuple is just an object containing a list of elements.  Multiplication
(overloaded multiplication operator!) of two such objects is done elementwise.

\begin{verbatim}
class tuple:
    def __init__(self, slots):
        self.slots = copy.copy(slots)
    def __mul__(a,b):
        n = len(a.slots)
        c = tuple(a.slots)
        for i in range(0, n):
            c.slots[i] = a.slots[i] * b.slots[i]
        return c
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Given that, it is straightforward to construct the direct product of two given
groups:

\begin{verbatim}
def direct_product(G1, G2):
    n1 = len(G1)
    n2 = len(G2)
    n3 = n1 * n2
    G3 = []
    for i in range(0, n1):
        for j in range(0, n2):
            G3.append(tuple([G1[i], G2[j]]))
    return G3
\end{verbatim}

\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Nilpotency and solvability}
\end{center}

The basic ingredient is the \textbf{commutator}:
$$[x,y] = xyx^{-1}y^{-1}.$$

\begin{verbatim}
def commutator(x, y):
    return x * y * x.inv() * y.inv()
\end{verbatim}

\textbf{Closing} a finite group, given generators:
since our groups are finite, we need only to compute closure with respect to
addition, not inversion.  (In a finite group, the inverse of any element is
obtained by raising it to a sufficiently high postiive exponent.)
Idea:
(1) Remember the size of the set.  (2) Add all pairwise products to
the set, if they are not already there.  (3) Repeat steps 1 and 2 until no more
elements are added.

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

\begin{verbatim}
def close_group(G):
    while (1):
        n = len(G)
        for i in range(0, n):
            x = G[i]
            for j in range(0, n):
                y = G[j]
                xy = x * y
                yx = y * x
                set_append_unique(G, xy)
                set_append_unique(G, yx)
        if (len(G) == n):
            return 
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Usual characterization of nilpotency is via ascending central series.  Grove's
\emph{Algebra} offers a more convenient characterization of nilpotency: Define
$$[G,H] = \pig{[g,h] : g \in G, h \in H}.$$ Define $$ L_1=[G,G]
\quad\textrm{and} \quad L_{k+1} = [G, L_k], k > 1.$$ Then $G$ is nilpotent iff
$L_n(G)=\{1\}$ for some $n$.

\begin{verbatim}
def nilbracket(G, Gi):
    G2 = []
    for a in G:
        for b in Gi:
            set_append_unique(G2, commutator(a, b))
    close_group(G2)
    return G2
\end{verbatim}

\end{slide}
%% ----------------------------------------------------------------
\begin{slide}
Compute $L_k$ for successively higher $k$, looping until $|L_{k+1}| = |L_k|$;
$G$ is nilpotent iff that stable size is 1.
\begin{verbatim}
def is_nilpotent(G):
    Gp = copy.copy(G)
    while (1):
        Gpp = nilbracket(G,Gp)
        oGp  = len(Gp)
        oGpp = len(Gpp)
        if (oGpp == 1):
            return 1
        if (oGp == oGpp):
            return 0
        Gp = Gpp
\end{verbatim}
The routines for derived subgroup and solvability follow the same pattern.
\end{slide}
%% ----------------------------------------------------------------
\begin{slide}

Examples:
\begin{verbatim}
kerl@gila:pyaa% sack d:3 solvable .
  solvable
kerl@gila:pyaa% sack d:4 solvable .
  solvable
kerl@gila:pyaa% sack d:2 nilpotent .
  nilpotent
kerl@gila:pyaa% sack d:3 nilpotent .
  non-nilpotent 
kerl@gila:pyaa% sack d:4 nilpotent .
  nilpotent 
kerl@gila:pyaa% sack d:6 nilpotent .
  non-nilpotent 
kerl@gila:pyaa% sack d:16 nilpotent .
  nilpotent
\end{verbatim}
\end{slide}

%% ----------------------------------------------------------------
\begin{slide}
\begin{center}
\textbf{Further directions}
\end{center}

The software sketched here involves groups written multiplicatively.  However,
in Python one may overload any arithmetic operators, so there is no reason one
cannot write similar software to deal with rings, fields, linear algebra,
tensor products, and so on.

\end{slide}

%% ================================================================
\end{document}
