Rereading what I have written yesterday in answer to Bill Haloupek's
letter, I realize that I have perhaps not taken enough notice of his
last and most direct question:

>There is a saying, "you can lead a student to a computer, but you
can't make him think." Can we? At the undergraduate level? And with
non-math majors?

Well, here is a suggestion that one might try, though I must admit
that I haven't.

Give them the task to compute all subgroups of a permutation group
that is given by a set of generators (i.e. to compute the subgroup
lattice, but that concept need not be mentioned at that level). That
is very concrete and does so far only need the notion of a group, a
subgroup, and of a generating set.

Prove to them the criterion that a subset of a group is a subgroup iff
with any two elements a and b it contains a*b^-1 and let them write a
program just using that. This will be hopelessly inefficient ( of
course - but it is what once upon a time a very renowned group
theorist suggested to me as much simpler than what I had done!)

Next prove to them Lagrange's theorem. So we need not check all
subsets! Progress! Unfortunately still very inefficient.

Remind of the concept of generating sets and apply it to finding
subgroups. We will need a fast way to generate a subgroup. Invent
Dimino's algorithm (this brings you close to the idea of an orbit,
maybe this is a nice point for a little deviation about that concept).

Next: How to store a subgroup. List of all elements? Long! Moreover
membership test if used more often is a problem. Invent the idea of
storing by a characteristic function, that is by a bitstring! On the
set of all elements of the whole group? Possible! Better: On the set
of cyclic subgroups of prime power order. By now you will have needed
some idea of how a cyclic subgroup works. However by now you have
already arrived at the data structure that is actually used in GAP
(and Cayley).

Then return to the idea of using generating sets. Maybe using
lexicographical order? Not so bad, has been a serious and published
proposal in the early sixties, write some programs. Trouble is that
so many subgroups are found over and over again, and this is noticed
only after a good chunk of them has been regenerated. Really one
should know beforehand which to generate.

Now you need a bit more theory: normal subgroups, normalizer, factor
groups, (composition series), soluble groups, not really Jordan
Hoelder, although having it does not hurt, but you may also first have
the program and then use it to 'observe' the truth of JH. Having
these concepts, now invent the 'cyclic extension method' for soluble
groups and actually implement it, using either a brute force method
for the normalizer or (maybe after that) a much more efficient black
box for it that you find in GAP.

Maybe you now want to ask if all finite groups are soluble, perhaps
you can prove the simplicity of A5 or even An, n>4. This will now
have a very concrete meaning to the students.

All this can be done using the commodities of a system like GAP, i.e.
not worrying about storage management, having arithmetic for integers
and also for permutations and even lists and bitlists ready to use.

What you reach is pretty close to the actual implementation of the
subgroup lattice in GAP, which still follows in many ways the idea of
my own very first program of 1959 except that it is now so much easier
to write it.

The philosophy of the whole proposal is to let the students
*experience* that group theoretical concepts are not there to annoy
them but to make concrete complex structures accessible. "Think
before programming!" Perhaps even computer science majors may get the
message. And at the end they can throw a pair of generators for M11
into GAP and have some idea how it works that the subgroup lattice
comes out.

The first chapters of Greg Butler's book "Fundamental Agorithms for
Permutation Groups" contain descriptions of all the methods that occur
above. However: I have used the book in a proseminar last year, i.e. I
let the (first year-) students give talks on its content. That was a
flop. Reporting about all the (sometimes over-) explicit countings of
operations in algorithms got very boring. I do not recommend to try
that. Rather use the book yourself but hide it from the students (at
least until the end of the course) and let them 'invent' these ideas
(of course you will have to drop a suggestion now and then and have to
prove some theorems) and let them *do* the algorithms rather than
speak about them.

I would be most interested to hear if somebody tries something like
that.

Apologises to those of you who would like to see other things
discussed in the forum. This will be my last on the topic for a while.

Joachim Neubueser