> < ^ From:

^ Subject:

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

> < [top]