Computational group theory, 2

If a group is presented to me (by one of the methods discussed in the preceding post, or as a black box), one of the first things I might want to know is “which group is it?” This presupposes that we have a name for the group.

Now expertise in computational group theory requires a wide-ranging knowledge of traditional group theory as well as a completely different take on it. There are very many groups; in some sense, the extreme cases are p-groups and (nearly) simple groups.

Groups of prime power order

In 2000, the classification and counting of groups of order less than 2000 was announced by Hans Ulrich Besche, Bettina Eick and Eamonn O’Brien. There are 49 910 529 484 of them, of which almost all (approximately 49.5 billion) have order 210 = 1024.

So we could give names to these groups by giving their number in the Besche–Eick–O’Brien catalogue; each group could have a 36-bit name.

Of course, unless we are much cleverer, this method cannot be extended to groups of order 211 or larger powers of 2.

We can compromise. I will stick to the prime 2 here, though the same comments apply to powers of other primes. A group of order 2n has a “power-commutator presentation”: it is generated by elements x1,…xn, with defining relations giving the squares xi2 and the commutators [xi,xj] (for i < j) in terms of the generators. These expressions have a very special form: each is a product, over k running from i+1 to n (for the squares) or max(i,j)+1 to n (for the commutators); and the kth term is either the identity or xk.

The number of expressions for the squares is thus at most (n−1)+…+1+0 = n(n-1)/2 for the squares, and (n−2)+2(n−3)+…+(n−2) = n(n−1)(n−2)/6 for the commutators, or in total (n+1)n(n−1)/6 choices.

So the number of groups of order 2n is at most, roughly, 2(1/6)n3. Moreover, the power-commutator presentation gives us an easily-decodable name for each group, the name having length (n+1)n(n−1)/6.

But there is a problem: not all these groups are different. The actual number of groups of order 2n is asymptotically 2(2/27)n3. (The upper bound was proved by Graham Higman, and the lower bound by Charles Sims.) We don’t have easily decodable names of length about (2/27)n3 for all groups of order n, and we don’t have an efficient way of testing isomorphism for the longer names.

This is mildly shocking, given that “most” groups of order 2n have “φ-class 2″, which means that they can be described in terms of two
vector spaces over GF(2) with dimensions summing to n, together with a bilinear and a quadratic form from one space to the other, the forms related by polarisation. Here is a “simple” problem in linear algebra for which we don’t have a computationally efficient solution!

Nearly simple groups

At the other end of the scale, the non-abelian finite simple groups have short names. There are a small finite number of families of “groups of Lie type”: the classical ones are parametrised by a positive integer (the rank) and a prime power (the field order), while the exceptional groups are parametrised just by a field order. The alternating groups require a single positive integer (the degree), and there are only finitely many sporadic groups.

Even if we include groups which are “nearly simple”, that is simple groups possibly extended a bit in both directions, the description is still fairly simple. This was the hypothesis behind the celebrated ATLAS of Finite Groups. The extending means that we are allowed to have a normal subgroup at the bottom which is contained in the Schur multiplier of the simple group (that is, form a central extension), and we are allowed to have a subgroup of the outer automorphism group at the top. Both the Schur multipliers and the outer automorphism groups of finite simple groups are small and well-understood.

So we might modify our requirement and say: if the group is nearly simple in this sense, give it a name; otherwise, just provide some information about it.

The ground between

Probably, if a group is not “nearly simple”, we would be satisfied with some partial information about it. One thing that might be useful is a composition series for the group, telling us which simple groups go into its construction.

This tells us almost everything in the case of a nearly simple group, and almost nothing in the case of a group of prime power order. Each of the 49.5 billion groups of order 1024 has ten composition factors isomorphic to the cyclic group of order 2.

In some algorithms, such as Sylow subgroups for black box groups, rather than use traditional mathematical methods, we find a composition series first; then produce Sylow subgroups for the composition factors (these are known groups) and piece them together.

Black box groups

Recognising nearly simple groups as permutation groups has a long history. Indeed, my work with John Cannon addressed this question. To show that a group of permutations on n points is Sn or An, for example, it suffices to show that its action is primitive (which is easy), and to find a transposition or 3-cycle in the group (not so easy, but for example if we can find two elements whose supports meet in a single point then their commutator is a 3-cycle).

Recognising black-box groups is a bit more challenging. This problem was addressed for symmetric and alternating groups by Sergey Bratus and Igor Pak in 2000, and other authors have contributed subsequently. The Bratus–Pak paper (perhaps surprisingly at first view, but it makes sense on a moment’s thought) requires Goldbach’s conjecture to prove the correctness of the algorithm (the ternary Goldbach conjecture will do, and indeed the original conjecture has been verified up to values far beyond the dreams of computational group theorists), and some stronger versions of Goldbach’s conjecture are relevant to discussion of its running time. These stronger versions, concerning the number of representations of an even number as the sum of two primes, are derived from heuristics similar to that of Hardy and Littlewood for twin primes, and pose interesting challenges to number theorists.

Sad to say, a controversy has arisen over this. Igor Pak, in a blog post (I will give you the address later, but I cannot tell you what he says since the content of his blog is copyright), has alleged, not only academic malpractice, but racial prejudice and personal immorality by some other mathematicians. Eamonn O’Brien, perhaps the only person not personally involved but having copies of all relevant emails, has posted a document giving some context not present in Pak’s original post. If you read Pak’s version, please read O’Brien’s also. The documents in question are here and here.

Recognition algorithms for other close-to-simple groups have also been given.

From some points of view, matrix groups over finite fields are perhaps the closest concrete groups to black-box groups, and the black-box algorithms are especially relevant to the matrix group recognition project, a long-term project masterminded by Charles Leedham-Green, whose aim is to find names and/or information (including composition series) for groups generated by sets of matrices. The object of the program is to produce code which can be included in the two standard computer algebra packages, Magma and GAP.

Previous

Full text

One of the benefits of the pressure for open access from funding bodies and governments is that academic publishers have opened their archives, and full text is typically available for papers from five years after publication. This is particularly valuable for mathematicians, since an important paper will still have impact long after five years have passed.

I have begun the job of putting links to full text versions of my papers into my publications list. While doing this, I observed that publishers have taken very different attitudes about how this is done. I am using the DOI mechanism wherever possible. There are two different sorts of information that publishers can provide: the actual paper (probably as a PDF file), and publication and citation information.

Here are how three academic publishers do it.

• Oxford University Press have what is certainly the friendliest system I have found. They have attached DOIs to all the papers in their archive. The DOI takes you to a page with two frames, one of which has the PDF of the paper (which can be downloaded directly in Firefox), the other the citation details and information about the journal (which is useful to have available when you download, as you will probably need to label the file appropriately). The two frames have their own URLs, and can be linked to together or separately. Here is an example:
• Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), 1-22; doi: 10.1112/blms/13.1.1
• Springer-Verlag don’t, as far as I can see, use DOIs for this purpose, but have their own SpringerLink system. This gives journal and citation information, with a prominent button for downloading the PDF (but with the slight problem that you cannot then see the citation information while you download). Here is an example:
• Peter J. Cameron, Dual polar spaces, Geometriae Dedicata 12 (1982), 75-85; full text
• Elsevier once again use DOIs, which take you to the citation and journal information page. This has a download button, but almost as prominently a button labelled “Get rights and content”. To my eyes, this looks as if they are reserving the right to withdraw the free download at some future time. Here is an example:

Tiritiri Matangi

Gannets; kokako; takahe; bellbird

On each of my previous trips to Auckland, I have been urged to go to Tiritiri Matangi, an island in the Hauraki Gulf which is now an open wildlife sanctuary. It is a day trip from Auckland, so I didn’t have time on previous rushed trips. But yesterday we made it.

The ferry leaves the quay in Auckland at 9:00 and takes an hour and a quarter (or a bit longer if the sea is rough, as it was yesterday morning). As we arrived at the jetty on the island and disembarked, the rain poured down, and it seemed like a miserable day was in store. But before the ranger had arrived to address us, the rain stopped, and we had blue skies and sunshine for our entire time on the island.

It has been occupied by humans, and farmed (and fought over) for about 700 years. By the 20th century, the tree cover had almost entirely gone, the native birds had mostly left or died out, and the land swarmed with rats. It was decided to try to make it a habitat for threatened endemic birds; so the Department of Conservation took it over, a poison drop cleared it of rats, and the slow work of restitution began.

Ti kouka (cabbage tree); kowhai

A plantation was set up, and 300000 trees (almost all bred from seeds of trees on the island) were planted in ten years. Then birds were re-introduced. The trees provided food for many of the birds, but some of them required holes in mature trees for nesting sites; these will not be available for a long time, so in the interim nest-boxes have been provided. The birds are never threatened by humans, and so are remarkably tame, especially the takahe (related to swamphens, but the size of a small turkey).

There is an interesting story here. Apparently the Australian swamphen reached New Zealand twice, millennia apart. The first arrivals evolved to be large and flightless (because of the absence of predators); the Maori called them takahe. The second arrivals were unable to breed with them and form a different species, the pukako. The latter are very common, but the former were thought to be extinct until a small population was discovered in Fiordland. Some of these were brought to Tiri, where they thrive, and attempt to steal visitors’ lunches.

Our guide for the morning, Steve, was excellent; he was happy to go at our pace, spotted birds that we hadn’t (and occasionally vice versa), and told us many interesting stories about the birds and the island, as we walked up the Wattle Trail (so-called because a few Australian wattle trees provide food for the birds when nothing else is available).

After lunch we took ourselves on a walk, and on the Kawerau Track had a most wonderful experience. We sat on a seat near two bird feeders, and a huge flock of bellbirds entertained us with their ringing song, for a quarter of an hour or so, accompanied by a single tui.

Back on the beach, we looked up to the hill, and three huge birds with very large wingspan came soaring over, scarcely moving or even twitching a wing feather. They shouldn’t have been albatross, which are not seen around here, but I can’t help thinking they were; I was so much reminded of an experience on the Otago peninsula when, after a long wait, I saw a single albatross fly over the hill.

Scots wha hae

… wi’ Wallace bled

Yesterday, the Scots voted to retain their place in the United Kingdom.

Scottish history has been a bloody affair. The battle of Bannockburn took place 700 years ago, and the referendum on Scottish independence was deliberately timed for the anniversary. Indeed, having heard Alex Salmond speak, I have a suspicion that he and his colleagues believe that the battle is still going on; they seem not to have noticed that the world has changed in the intervening time.

The song goes on to say, “Welcome to your gory bed”. I am glad that this will no longer be necessary.

Surely we are better together.

Computational group theory, 1

Computational group theory is the art or science of using a computer to learn something about a group. I was introduced to it by John Cannon in the early 1980s. It seems like a black art to many mathematicians (myself included), and perhaps also to computer scientists, I am not sure. (I mean no disparagement here; “black” is the colour of mystery. See below.) I think there may be several reasons for this.

• First, there are many different ways in which a group may be presented to the computer: by a set of concrete generators (which may be permutations, matrices, or something else entirely); a presentation by generators and relations; as the symmetry group of something; as the homotopy group of some topological space; and so on. These may require very different techniques. For example, given generating permutations on a finite set, we can learn everything about the group in a finite amount of time; but given a presentation, it is undecidable even whether the group is trivial or not.
• What seems easy to a human may be hard for a computer, and vice versa. I can say, “Let p be a prime divisor of the order of G, and let P be a Sylow subgroup of G.” But, even if I know the group order and can factorise it(!), standard proofs of the existence of Sylow subgroups are worse than exponential. It was a huge and somewhat shocking breakthrough when Bill Kantor showed how to find them in polynomial time.
• Randomness plays a big part in computational group theory. Many important algorithms are either Las Vegas (if they run, they give the right answer, but they may fail with small probability), or, even worse, Monte Carlo (which might give the wrong answer with small probability). This is disturbing to mathematicians, even those who entrust their personal and financial details to a system whose security depends on numbers which are “probably prime”.
• There is also a distinction between theorists and practitioners, which was graphically highlighted by Laci Babai at a conference where he referred to them as the “reds” and the “greens” (I cannot now remember which was which). A theorist devises an algorithm which runs in time “soft O of n squared”, with constants depending on something or other, and “soft O” allows an arbitrary power of log n; the practitioners have a program which runs on huge groups in a few seconds or hours when programmed in GAP or Magma and run on such and such a machine.

(In connection with the last point, Dick Lipton and Ken Regan have discussed the concept of galactic algorithms, which are theoretically efficient but will never be run, either because the constants are too large, or because the power of n is too large. They hope that some of these can be brought down to earth in the future.)

The basic things that a computer can do with a group are to multiply group elements, invert an element, and return the identity. This led to the notion of a black box group, where the group elements are represented (not necessarily uniquely) by bit strings of fixed length, and the black box performs these operations in a specified time which may be taken as the unit for measuring the complexity. I remember a talk at the ICM in Kyoto in 1990 in which Babai illustrated this by a picture of a Japanese-style street vending machine, with three slots: you put group element g in the first slot, h in the third, and ¥100 in the third, and the product gh is delivered to you. A black box algorithm will thus run on any finite group in which the basic group operations are computable, and multiplying its complexity by the time taken for a multiplication will give the complexity of the algorithm in the practical situation.

So, for example, if your groups consist of permutations on n symbols, you can encode elements as bit strings of length n log n and apply black box algorithms to learn about your group. But you probably wouldn’t do that. Given a permutation, it is easy to compute its cycle lengths; their least common multiple is the order of the element. Given a set of elements, the Screier–Sims algorithm, and various refinements, efficiently give a canonical form for elements, the group order, and a membership test.

A compromise is provided by various sorts of “grey boxes” which provide a bit more information, for example the orders of group elements.

Next

Posted in exposition | | 1 Comment

A celebration of diversity

Today, the University of Auckland put on a morning meeting entitled Excellence in Mathematics: A Celebration of Diversity.

As the program (which is here) makes clear, it is actually a celebration of female mathematicians, and in particular the recent Fields medal for Maryam Mirzakhani.

As you know, I am not generally in favour of singling out any group of mathematicians, be they women, Jews, French citizens, combinatorialists, or whatever (all these four groups have been singled out, some with more serious consequences than others – and you can certainly think of many more examples), nor of Fields medals (most of which reward great contributions but which always have a hint of fashion or politics about them). However, I am very much in favour of celebrating mathematics by talking about our successful practitioners.

The speakers in this celebration were all women with one exception. No woman could be found here to talk about Mirzakhani’s work, so Marston Conder stepped up to the plate, and did a very fine job.

Spaces and hyperspaces

One thing that drives mathematicians is the urge to classify, to understand the members of a large diverse collection. I have seen grown mathematicians quail at the notion of moduli spaces, but the basic idea is simple. We are trying to understand a collection of spaces; we regard our spaces as points in a “hyperspace”, and give structure to the hyperspace which reflects properties of the constituent spaces.

If I want to appreciate the diversity of the New Zealand landscape, the best way is to travel around it observing. Similarly, one basic way to organise and explore our hyperspace is to wander around it, which implies some geometric notion of paths or at least of nearness. Indeed, once I was invited to speak at a conference for János Bolyai’s 200th anniversary; I had the idea of regarding Steiner triple systems on more than 9 points as a particular kind of discrete hyperbolic space, and taking a random walk through it (using a variant of the Jacobson–Matthews random walk for Latin squares).

Another unifying principle is that of an equivalence relation. If we don’t need to distinguish among equivalent spaces, we can regard the points of our hyperspace as equivalence classes of spaces. For a simple example, suppose we want to consider graphs up to isomorphism. The corresponding hyperspace supports various structures, such as a probability measure or a complete metric. Paradoxically, we find that, using either of these structures, there is a single point of the space (the random graph) which makes up almost all the space (its complement is a null and meagre set). Moreover, small moves from the random graph don’t get us away from this point.

It may be that our spaces have various numerical invariants or “moduli”, which can be regarded as “coordinates in hyperspace”. Hence the name “moduli space”.

Here is a very simple example. Consider the space of all normed real vector spaces of dimension 2. What does the corresponding hyperspace look like? Such a vector space is defined by a positive definite quadratic form ax2+bxy+cy2 in two variables. So each point of hyperspace has three coordinates (a,b,c), where b2 < ac and a > 0. So the corresponding hyperspace is the region of 3-dimensional space defined by these two inequalities.

Things are more complicated if we take our spaces over the rational numbers or the integers rather than the real numbers. Then we find ourselves doing number theory, following in the footsteps of Gauss. Indeed, another of this year’s Fields medallists, Manjul Bhargava, works on this …

Moduli spaces

What follows will not be very precise, and certainly I (rather than Marston) am to blame for any inaccuracies.

A Riemann surface is a closed orientable surface with a complex analytic structure imposed on it. The geometry allows one to talk about geodesics on the surface. It is known that the number of closed geodesics of length at most L grows exponentially, about eL/L to be precise.

One of Mirzakhani’s achievements was to show that the number of non-intersecting closed geodesics grows only polynomially, like c.L6g−6, where g is the genus (the number of holes) of the surface.

For this she used the moduli space for Riemann surfaces of genus g. Since there is only one (topological) closed orientable surface of genus g, as in the vector space example the hyperspace for such surfaces is the set of all complex structures on the fixed topological surface. This hyperspace can be parametrised by 6g−6 parameters, called moduli; so the hyperspace is “moduli space”.

What Mirzakhani did, very much simplified, was to show a remarkable connection between volume calculations in moduli space and counting closed geodesics on a Riemann surface corresponding to a point in the space.

Her work has led to a much more detailed understanding of how moduli spaces look. In particular, closed geodesics on moduli space (the natural next step) have remarkable regularity properties, resembling that of dynamics on homogeneous spaces, even though the moduli spaces themselves are far from homogeneous.

Marston also told us a bit about Maryam Mirzakhani herself. For example, she likes to doodle when she is thinking about something; the doodling keeps her engaged. I find the same thing.

Other talks

I enjoyed Hinke Osinga’s talk. Probably anyone who walks in the mountains has thought about watersheds, the phenomenon where raindrops falling on either side of an invisible line in the mountains will end in the sea possibly thousands of kilometres apart. (I went to school a stone’s throw from just such a watershed.) Now there is an object called the Lorenz surface, which plays a similar role for trajectories of solutions to the chaotic Lorenz equation. The dynamics on the surface itself is simple; there is one attracting fixed point, at the origin. But just off the surface, trajectories have very different behaviour depending which side they are on; and the surface is dense in space, explaining the enormously complicated behaviour of the system. Hinke first devised crochet instructions for producing a model of the surface, and then worked with an artist who produced a hammered steel model. (Think of the surface growing outward, parametrised by the time to reach the origin. The sculpture consists of a band between successive “circles”, and has a remarkable shape, smooth in parts, intricately convoluted in others.)

The other talks were mostly applied. (Perhaps making art out of the Lorenz surface is applied maths?) Gill Dobbie talked about big data, which is currently in the trough of disillusion after the wave of hype in the Gartner hype cycle for emerging technologies. Rosemary talked about her work with ecologists, and how after converting them to her viewpoint (even getting Hasse diagrams and a picture of the Fano plane published in biology journals) found that she had to question some of her own assumptions about which design is best. Tava Olsen talked about operations management, and Cather Simpson on how to use femtosecond lasers in real industrial processes. One thing I got from this talk is that, for things like artists’ pigments, the shorter the relaxation time of the molecule after excitation by a photon, the greater the long-term stability of the pigment. Having all that energy hanging about in the molecule is very destructive, as she said like a child who has been binging on chocolate let loose in a china shop: get it out as soon as possible!

Summing up

Maybe you want to learn about the beautiful landscape of New Zealand. There is no real substitute for going there, travelling about, and experiencing it first-hand. But maybe that is too expensive, or the travel is dangerous, or you are too busy (or you can’t get a visa) – then what do you do?

You could invite people from different parts of New Zealand to come and tell you about their area. With skill, they could convey something of its essence.

That was the strategy here, and worked successfully, making an entertaining and instructive morning.

Open access and metrics: the Ball committee report

I mentioned this report in an earlier post; I am grateful to John Ball for directing me to the report on the web (here; the press release is here).

The overall conclusions are clear. The ICSU goals for open access are that the scientific record should be

• free of financial barriers for any researcher to contribute to;
• free of financial barriers for any user to access immediately on publication;
• made available without restriction on reuse for any purpose, subject to proper attribution;
• quality-assured and published in a timely manner; and
• archived and made available in perpetuity.

These goals and their implication are discussed in detail in the report, which I urge you to read. Some related complications discussed include availability of data (this is very important in science but less so in mathematics); copyright issues; and legitimate constraints on open access (the report says “openness should be the norm which is deviated from only with good reason”).

The reason why bibliometrics are also in the title is that these are used in research evaluation, often in a rather crude way which will have to change as publication norms change. The panel says,

Metrics used as an aid to the evaluation of research and researchers should help promote open access and open science … If the full potential of open access to science is to be realised, new metrics will be required that incentivise open-access approaches and value research outputs that go beyond traditional journal publications.

Good news to colleagues whose outputs are, for example, widely used computing packages, or web-based information sources.

On another issue of serious concern to mathematicians, the report says,

The goals of open access advocated above can be satisfied … only if robust procedures are in place to ensure that those who do not have the means to pay for publication or access, or who are not affiliated to recognized institutions, are not disadvantaged.

All in all, it is good that some people with some influence are aware of our concerns.

In my view, there is one very important thing missing from the report. Part of an academic’s job has always been external activities: refereeing, both of papers and of grant proposals; editing; work for learned societies and their subcommittees; running information-rich websites; and so on. Since a lot of this relates to publication, and the burden is likely to increase when it is recognised that diamond access is the best way to go, this is closer to the subject of the report than might first appear. It would have been good to have seen a statement that university management should recognise these activities as part of our job, and should reward them (and adjust other loads) appropriately.