An excursion

Ruapehu

Last weekend, as I mentioned, we took a long weekend and did some travelling, at the kind invitation of Hans Hockey.

On Saturday morning we took the bus to Hamilton. Hans met us at the bus station, drove us round the lake, and took us to the jetty for a lunch cruise on the Waikato river. After that, we had a leisurely stroll round the Hamilton Gardens, one of my favourite places: it features beautifully executed gardens from various places and periods including Japanese meditation garden, Chinese scholar’s garden, West Coast modernist garden, and Italian renaissance garden.

Hamilton Gardens

It was the 50th anniversary of the University of Waikato, and we went to the Staff Revue, a pantomime of Little Red PhD Hood and the Wicked Librarian, interspersed with musical interludes, mostly music from 1964 (my first year as a university student and a great year for music!)

The next morning we drove with Hans’ family to their house in Taupo. In the afternoon we climbed the 1088 metre Mt Tauhara, overlooking the lake. We soothed tired muscles with a dip in the hot mineral waters.

Tauhara

On Sunday, we drove to Napier. The spectacular mountain views were somewhat wasted on us, as for most of the drive we had rain and fog.

Napier was flattened by an earthquake and fires in 1931, but was quickly rebuilt, mostly in the Art Deco style popular at the time. Much of the Art Deco survives and is one of the town’s claims to fame now. Unfortunately, our views of this were also hampered by the pouring rain. After sightseeing, while Hans and family visited his sister, we drove back to Taupo.

Napier

The next morning, the clouds over Taupo finally cleared and gave us the view at the top of this post, of Ruapehu seen across Lake Taupo. This vast lake takes up part of the caldera of a huge volcano that erupted in about 200AD, possibly affecting climate and crops over much of the northern hemisphere.

We drove back to Hamilton and went to the University of Waikato, where our host was Nick Cavenagh. We had lunch with the mathematicians and statisticians, and then gave back-to-back talks, before catching the bus back to Auckland.

Posted in geography | Tagged , , , , , , | Leave a comment

Picture of an isomorphism

We spent a very busy and enjoyable weekend with Hans Hockey, a statistician who lives in Hamilton, and his family.

When we arrived, Hans showed me a picture he had taken, of the 81 SET cards laid out on a table in an arrangement with a number of remarkable properties, which I describe here. It turns out that it is a picture of an isomorphism between the SET pack and the Sudoku grid.

SET

The game SET is played with a pack of 81 cards. Each card carries a picture
with four attributes, each with three possible values:

  • the number of copies of a symbol may be 1, 2 or 3;
  • the colour of the symbol may be red, green or purple;
  • the shape of the symbol may be diamond, oval, or “squiggle”;
  • the shading of the symbol may be hollow, line shaded, or solid.

A set of three cards is a SET if the values of each attribute are either all the same or all different. It is easy to see that any two cards are contained in a unique SET; so the cards and SETs form a Steiner triple system of order 81.

A SET  Another SET

Coordinatisation

Label the three values of each attribute with the three elements 0, 1, 2 of the field GF(3) (the integers modulo 3). The labelling is arbitrary, although it is natural to label the number of symbols with its value modulo 3. Thus each card is identified by a 4-tuple of elements of GF(3).

The 4-dimensional affine space over GF(3) is defined as follows: the points are the vectors of a 4-dimensional vector space over GF(3); lines, planes and 3-spaces are cosets (translates) of subspaces of dimension 1, 2, 3 respectively of the vector space.

For example, a line has the form {0,b,2b}+a = {a,a+b,a+2b}, where a and b are vectors and b ≠ 0. Observe that

  • The three points in a line sum to 0 (using the fact that 3a = 3b = 0); and conversely, three points which sum to 0 form a line of the affine space.
  • In GF(3), three elements sum to 0 if and only if they are either all equal or all distinct.

As a corollary of the last two statements, we see that three cards form a SET if and only if their coordinates form a line in the affine space. So we have identified the Steiner system formed by the SET cards with the points and lines of the affine space.

Planes and 3-spaces

Three points of the affine space which do not form a line “generate” a plane. (If the three points are x,y,z, then the plane is the translate by x of the vector subspace spanned by yx and zx.)

The structure of the 9-point affine plane over GF(3) is most easily shown by arranging the points in a 3×3 array, so that the rows and columns of the array are lines. The other lines can be described as the sets of three positions corresponding to the six terms in the expansion of a 3×3 determinant: that is, each set has one point in each row and one in each column, and the six possible such sets form the remaining lines. In particular, the two diagonals of the square are lines.

This can be realised by SET cards as shown.

A plane

In a similar way, four points, with no three collinear and not contained in a plane, generate a 3-space, which could be imagined by going into the third spatial dimension and stacking three planes one above the other. Then the vertical and diagonal lines containing three points, one from each plane, are also affine lines; but there are others too, which become harder to imagime.

Five points, with no three collinear, no four coplanar, and not lying in a 3-space, generate the entire geometry.

Laying out the SET cards

We’ve seen how to lay out nine cards forming a plane.

Now choose one of the 72 remaining cards and put it next to the plane, in row 1 and column 4. Then we can fill in three rows of nine cards each to form a 3-space. For example, positions (1,1), (1,4) and (1,7) must form a SET, which determines the card in position (1,7).

Finally, choose one of the 54 remaining cards, and place it in row 4 and column 1. Now similar rules determine the position of every card in the pack. We end up with a layout which might look like this:

The complete layout

The layout has various other properties. For example, the central card in the centre square and any two cards in diametrically opposite positions always form a SET.

The Sudoku grid

The 9×9 layout can be matched up with the Sudoku grid. Details are in a paper by Rosemary Bailey, Robert Connelly and me in the American Mathematical Monthly 115 (2008), 383–404.

We coordinatise the grid with four coordinates, each taking values 0, 1 or 2, as follows. The first coordinate describes which “fat row” of three 3×3 squares the chosen cell lies in; the second tells which row within that fat row it is in; the third and fourth coordinate describe the same for columns.

We use this coordinatisation, together with properties of the affine and projective spaces and other discrete structures such as Hamming codes, to give a complete description of symmetric Sudoku, a variant of Sudoku invented by Connelly and independently by Vaughan Jones.

If we regard the coordinates as lying in GF(3), we see that the rows, columns and subsquares of the Sudoku grid are affine planes. Indeed, they are defined by equations of the form

  • x1 = a, x2 = b (for rows);
  • x3 = c, x4 = d (for columns);
  • x1 = e, x3 = f (for subsquares).

Thus, our picture above of the SET cards layout is really a picture of an isomorphism between the SET pack and the Sudoku grid, as claimed.

The five cards in positions (1,1), (1,2), (1,4), (2,1) and (4,1) determine everything. (In the Sudoku numbering these are 0000, 0001, 0010, 0100 and 1000, so the origin and the standard basis for the vector space.)

So now look at the cards in these positions, and suppose that you have chosen the numbering of attributes so that their Set coordinates are a, b, c, d, e. (Each of these is a 4-tuple, regarded as a vector in the 4-dimensional vector space.) Then the card in position with Sudoku coordinates wxyz is the one with Set coordinates a+z(ba)+y(ca)+x(da)+w(ea) – this is the linear function which takes the values a, b, c, d, e on the five points given.

In particular, if the cards in these five positions have Set coordinates equal to their Sudoku coordinates 0000, 0001, etc., then every card in the layout will have its Set coordinates equal to its Sudoku coordinates.

Counting

There are 81 choices of the first card to go in the top right position, then 80 choices of the card to put to its right, 78 for the card beneath it (the unique card forming a set with the first two is excluded), 72 for the card in position (1,4), and 54 for the card in position (4,1). So the total number of arrangements of the pack is 81.80.78.72.54 = 1965150720, a large number but tiny by comparison with the total number 81! of orderings of the pack. The chance of producing this layout at random is vanishingly small.

Some of the arrangements are special. For example, all the cards having a particular value of a particular attribute form a 3-space. So we could arrange the cards so that the first three rows are red, the next three green, and the last three purple, for example.

Magic squares

It fairly often happens that the nine cards of an affine plane, laid out in a 3×3 array, form a magic square: the number of symbols in any row, column or diagonal is 6. This is because, of the 1080 lines (SETs), 729 have the property that the numbers are all different. So often we will end up with a plane in which all but three of the lines have all the numbers different. If we lay this plane out so that the main diagonal has the three cards bearing 2 symbols each, we will have a magic square as required. In fact, of the 81.80.78 = 505440 plane layouts, 27.26.54.2 = 75816 will be magic squares of this form. [A magic square must have one of the two diagonals having two symbols on its cards. Assuming it is the principal diagonal, there are 27.26 ways to choose two cards with two symbols, and 54 ways to choose a card with a different number of symbols for position (1,2): this determines the plane.]

There is another, slightly silly, kind of magic square: those in which every card carries two symbols. There are 27.26.24 = 16848 of these, giving
altogether 92664 magic squares, or 11/60 of the total number of planes.

Posted in exposition | Tagged , , , , , | Leave a comment

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 lower bound was proved by Graham Higman, and the upper 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 academic malpractice or something. 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

Posted in exposition | Tagged , , , , | 1 Comment

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:
Posted in publishing | Tagged , , , , , , | 5 Comments

Tiritiri Matangi

Birds on Tiri
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.

Trees on Tiri
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.

Posted in geography | Tagged , , , , , , | Leave a comment

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.

Posted in history | Tagged | Leave a comment

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 | Tagged , , , , | 1 Comment