Perth, week 1

The first week of the visit is over. The weather has been quite cold, but it is likely to improve as time goes on. The best day so far was yesterday, when we went to Yanchep National Park and had a very pleasant walk. More on this later.

This week, I gave a colloquium talk on “The random graph and its friends“, and Rosemary a seminar talk on “Circular designs balanced for neighbours at distances one and two“.

In addition, we got started on some research. I will just highlight one of the stories here.

In our first meeting, Michael reported that, after he had talked about derangements in Iran, he had been asked to what extent the derangements in a transitive group determine the group.

Jordan proved in 1872 that a finite transitive permutation group of degree n > 1 necessarily contains a derangement (an element with no fixed points). In fact it contains many derangements: Arjeh Cohen and I proved in 1992 that at least a fraction 1/n of the elements of the group are derangements. But I vaguely remembered seeing, at some time in the distant past, a theorem that said:

Theorem
Let G be a transitive finite permutation group of degree greater than 1, and H the subgroup generated by the derangements in G. Then:

  • H is transitive;
  • H contains all elements of G for which the number of fixed points is different from 1.

Now my memory is not failing too badly: I was able to find a reference, Lemma 6.3 in a paper by H. Zantema, “Integer valued polynomials over a number field”, Manuscripta Math. 40 (1982), 155–203. But, before I did that, I was able to reconstruct the proof, and to add a bit more: with the same hypotheses,

  • G/H acts semiregularly on the H-orbits on ordered pairs of distinct points (equivalently, G1/H1 acts semiregularly on the H1-orbits different from {1}, where the subscript 1 means the stabiliser of the point 1).

In this form we see that Frobenius groups form a special case. In a Frobenius group G, every non-identity element fixes 0 or 1 point; the theorem of Frobenius states that the derangements together with the identity form a normal subgroup H. In this case, H1 is the trivial group, and its orbits are just the points; by definition, G1 permutes them semiregularly. So Frobenius groups give examples with H a proper subgroup of G.

Here is the proof of the theorem. Let π(g) be the number of fixed points of the permutation g. Suppose that the subgroup H generated by the derangements has d orbits.

By the Orbit-Counting Lemma,

∑ {π(g)−1 : gG} = 0,
∑ {π(g)−1 : gH} = (d−1)|H|.

So

∑ {π(g)−1 : gG\H} = −(d−1)|H|.

In this equation, the left-hand side is at least zero (since the only permutations giving negative contributions are the derangements, which are all in H), whereas the right-hand side is at most zero. So both must be zero, from which we conclude that d = 1 and also that all elements with π(g) ≠ 1 are in H.

For the last part, we use a slight variant. Let rG and rH be the permutation ranks of G and H, the numbers of orbits on ordered pairs. Then

∑ {(π(g)−1)2 : gG} = (rG−1)|G|,
∑ {(π(g)−1)2 : gH} = (rH−1)|H|.

Since all elements of G for which the summand is non-zero are in H, the two sums are equal. We conclude that

(rG−1)|G : H| = rH−1,

from which the second part of the theorem follows easily.

There are other examples apart from Frobenius groups. The unique almost-simple doubly transitive group, PΓL(2,8) (degree 28) has the property that its derangements generate PGL(2,8), a subgroup with index 3; the three orbitals are permuted transitively by the field automorphism.

We expect to have substantially more to report on this problem soon!

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

Problems

I have begun the long job of updating my collection of open problems. I would appreciate any help!

My St Andrews problems are here, and are in pretty good shape (there are only 14 of them so this wasn’t a very big job).

However, the many problems I collected at Queen Mary will need more work. The index page to these problems is here.

If you have any information about these problems having been solved, even if you think I already know it, please let me know. Email me at St Andrews with any information you might have. Credit will be given!

Added later And here is a summary of my conjectures (also a bit in need of updating!)

Posted in open problems | Tagged | Leave a comment

Perth spring

I have never been in Perth in the spring before. Previous visits have been in summer or autumn. Last time we were here, nearly eight years ago, the day we left there was a serious bushfire in Kings Park, and we had some difficulty getting from the University to the airport.

So yesterday, of course, we went walking in Kings Park. One of our leaflets describes Kings Park as the largest city park in the world; Wikipedia is more modest, calling it “one of the largest inned-city parks”. It is less than half the size of Richmond Park in London, and just over half the size of the Adelaide parklands. But size isn’t everything; Kings Park is a wonderful place.

Western Australia is famous for its wildflowers, at their best in the spring; Kings Park has a good selection of these:

Posted in geography | 1 Comment

Farewell Adelaide

Rainbow lorikeets

We move on to the next stage of the trip, from Adelaide to Perth.

This was only my second visit to Adelaide. I intended to have a holiday, in the hope of seeing off the last vestiges of shingles. I did quite well: walking in the Adelaide Hills (Black Hill, Mt Lofty, and Waite where I saw the rainbow lorikeets above), the Park Lands all round the city, the River Torrens Linear Park, and the beach from the mouth of the Torrens down to Glenelg; the State Library, Art Gallery, Zoo, Botanic Gardens, and Central Markets; Port Adelaide, with the Maritime and Railway Museums and a walk to Semaphore and Outer Harbor; and a weekend in Robe with stops in various places including two spots on the Coorong. Some eating and drinking of course. Even some mathematics, which I hope to write about soon, though there are still a few bugs to be ironed out.

But I am not sure about throwing off the shingles. Things seem to move much more slowly. I can spend a morning writing a couple of references now, and this wears me out so that I get little done in the afternoon. Things are improving but so slowly.

So if you are waiting for me to do something, bear with me a little longer.

Anyway, we are now in Perth, and the real work is about to begin …

Posted in Uncategorized | Tagged , | 1 Comment

An award

There is, I believe, a great resource for mathematicians called MathOverflow. I have never made much use of it. I am not quite sure why, but I think it is because of the competitive aspect: give a good answer, earn points. More and more as I get older, I do mathematics because I enjoy it, and tell people about it because I enjoy that too.

So, with a little unease, I note here that this blog has been voted number 50 in the Feedspot top 100 mathematics blogs:

Click on the icon to see the full list.

Posted in the Web | Tagged , | 5 Comments

Baudin in South Australia, 3

At the weekend we saw an exhibition about Baudin’s voyage at the South Australian Maritime Museum in Port Adelaide. After that, and some more reading, I have a conjectured answer to my question about why Baudin named so many features of the coast after mathematicians.

In brief, my conjecture is: he didn’t!

Baudin died in Île de France (Mauritius) in 1803, on the way home from his expedition. He died of tuberculosis: this is not a disease which normally strikes you down quickly, so I guess he must have been ill during the voyage, which makes his achievement all the more striking, as well as perhaps explaining his gloominess in various parts of his journal.

Baudin kept, not only a ship’s log, but also a “fair copy” book which includes illustrations by two artists (whom he had brought along as gunners) of things seen on the voyage. (This amazing book was in the exhibition; unfortunately it was in a glass case and we were not allowed to turn the pages.) However, after his death, publication of the account and charts of the voyage was taken over by François Péron, and after his death in 1810, by Louis Freycinet. Péron was the zoologist on the expedition, and Freycinet captained one of the ships in the latter part of the expedition. Both men disliked Baudin, and wrote him out of the story; his name is only mentioned once in Péron’s account. Pages were torn out of Baudin’s book to illustrate their account.

They also made wholesale changes to the names Baudin gave to his discoveries. I told in my previous post on Baudin of his misadventure in the gulf now named St Vincent. He wrote,

I gave this gulf the name of Golfe de la Mauvaise because of the fatigue it caused the whole crew.

In a brown-nosing gesture of stunning brazenness, Péron called it Golfe de Josephine on his chart, and the other (larger) gulf Golfe de Bonaparte; he named this whole tract of country Terre Napoléon.

The exhibition had numerous examples of charts from Baudin’s voyage where names had been deleted and replaced (in another hand) by different names.

Péron’s was the first complete map of Australia to be published. Flinders, on his way home from his circumnavigation, stopped in Mauritius, where he was placed under house arrest by the governor and held there for six and a half years. (So much for “Les savants n’ont aucun ennemi chez un peuple libre.”) Baudin’s log and fair copy book have only just been published in French, having appeared slightly earlier in English translation.

Péron further irritated the English by preparing a secret report on the military defences of Sydney, to encourage a French attack on the colony. In fact most of his information was readily available, and in the event Napoleon declined to attack New South Wales, preferring to plan to invade England instead. Moreover, Flinders’ detention in Mauritius backfired. During his time there, he learned much about the island’s defences, which he passed (possibly under duress) to the British authorities, who proceeded to attack and capture the island.

So what about the imaginary capes Fermat and Monge, on the Coorong?

As I explained last time, Baudin passed quickly along this stretch of coast, seeing only sandhills and heavy surf. He saw that the waves were breaking far from the shore, and inferred that the sea was shallow; so he kept his distance. My guess is that he inferred the presence of small capes from high ground behind the sandhills, but did not name them. Péron and Freycinet, who explain in several places that features were named after eminent savants, may have seen these projections on Baudin’s chart and decided to name them when they prepared their own.

So has Baudin’s name been completely eliminated from the coastline he charted?

Not completely. In Guichen Bay, the following is recorded in his log for 17 Germinal, Year 10 (7 April 1802):

At half past nine coasting the land a league off, I had the lead heaved. I thought we might be in 15 fathoms at that distance, but we found only 10. Had the depth not decreased to 8 and even 6 fathoms, we would have held our course without there being any sign of so sudden a diminution. But in bearing away to head further out to sea, we were quite amazed to see a rock at water-level which we had not noticed until then and which even the look-out men had not sighted. In order to double it, we were obliged to steer South-West with no noticeable increase in the depth. This rock (over which the sea breaks strongly) is surrounded by reefs and appears to be joined to the mainland by a chain of rocks which leaves no hope of a passage, even though the channel is more than a league across. To the North of the rock lie two smaller ones and a reef running North-North-West. We passed this danger at a distance of 1 1/2 leagues in 15 fathoms, rounding it on its western side. Future navigators would be wise to be on their guard against it on account of its distance from the mainland.

When he met Flinders in Encounter Bay a few days later, he told Flinders about this rock. When Flinders reached it, he named it Baudin’s Rocks. Subsequently it was officially re-named Godfrey’s Island, but locals still call it by the name Flinders gave it. (My host Margaret Emery, who spent much of her childhood at Mt Benson, knew it only as Baudin’s Rocks. She once tried to reach it in a small boat, but was unable to land.)

You can just see Baudin’s rocks in this picture.

Baudin's Rocks

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

Arrays

This post is about things called triple arrays, and some variants. I was visited by Tomas Nilson last semester, and we have just posted a paper on the arXiv. This is a subject with a quite extraordinary history; Rosemary will tell the story in her talk next July at the British Combinatorial Conference in Strathclyde, so I won’t steal her thunder here, just tell about the objects themselves as if they had no history.

Suppose we have an m×n array in which each cell contains a letter from a set of size b. Here are some conditions that the array may satisfy, with names often used in the statistics literature.

  1. Each letter occurs a constant number k of times, where bk = mn. (The array is equireplicate.)
  2. No letter occurs more than once in a row or a column. (The array is binary.)
  3. The number of letters common to two rows is constant. (The design of rows and letters is balanced.)
  4. The number of letters common to two columns is constant. (The design of columns and letters is balanced.)
  5. The number of letters common to a row and a column is constant. (The design has adjusted orthogonality.)

In the literature, an array satisfying all five conditions is called a triple array, while one satisfying conditions (1)–(4) is called a double array. We propose the term sesqui-array for an array satisfying (1)–(3) and (5): the prefix “sesqui” means “one-and-a-half”, and of the last three conditions, we require adjusted orthogonality and half of the two balance conditions required for a triple array. (Of course, many other terms are used in the literature for various combinations of these conditions!)

Agrawal’s conjecture

It has been proved several times that a triple array with m rows, n columns, and b symbols, satisfies b ≥ m+n−1. It is called extremal if equality holds here.

Extremal triple arrays are closely connected with square 2-designs, or symmetric BIBDs (in a different language). One of these consists of V points and V blocks, any block containing K points and any point lying in K blocks, such that any two blocks intersect in Λ points and any two points are contained in Λ blocks. (I use capitals to distinguish from the lower-case symbols for the array parameters.)

From any extremal triple array, we can construct a square 2-design as follows:

  • the points of the design are symbols indexing the m rows and n columns of the array;
  • the blocks are the b symbols of the array together with one new symbol ∞;
  • the block ∞ is incident with all the row symbols and none of the column symbols;
  • the block corresponding to a symbol x contains the row symbols for the rows not containing x and the column symbols for the columns containing x.

The properties of the design are easily checked.

Does the construction reverse? That is, can we construct a triple array from a square 2-design with a distinguished block? Agrawal knew that this was not possible for the smallest square designs (the Fano plane and its complement), and conjectured that it is possible in any other case. Various people have given algorithms which claim to produce the array from the design, but nobody has succeeded in proving that the algorithms always work, or indeed that the construction is always possible.

This is a kind of Sudoku puzzle. Given the design, consider the m×n array, with m = K and n = VK, whose rows are indexed by the points of a block B and columns by the points not in B. In the cell in row i and column j, we have to put a symbol for a block which is not incident with point i but is incident with point j. So put the set consisting of all such symbols in this cell. Now our job is to choose an array of distinct representatives for this array of sets; that is, choose one element from the set in each cell such that the chosen elements in any row are all distinct, and the chosen elements in any column are also distinct.

Motivated by this precise problem, Dima Fon-Der-Flaass proved that the general existence problem for an array of distinct representatives for an array of sets is NP-complete. Of course this says nothing about the design problem, since these instances may be easier than the general case!

Here, for example, is the array of sets arising from the Fano plane. You are invited to tackle the easy exercise of showing that it has no ADR.

An ADR puzzle

Difference sets

Suppose that the square design arises from a difference set D of cardinality K in a group G of order V. (This is the case that Tomas and I consider.) This means that every non-identity element of G can be expressed in exactly Λ ways in the form xy−1 with x and y distinct elements of D. The blocks of the design are the right translates of D.

Now we can produce an array of non-identity group elements by taking D to index the rows and G\D the columns, with x,y entry xy−1. Is this a triple array?

We show in the paper that it is always a double array; if the group G is abelian, it is a triple array if and only if −1 is a multiplier of D, that is, the set of inverses of elements of D is a translate of D. This gives new examples of triple arrays.

We also searched for triple arrays from non-abelian groups. Using a computer, we showed that there are none arising from our construction in non-abelian groups of orders 16 or 36.

Biplanes

A biplane is a square 2-design with Λ = 2.

In an attempt to test Agrawal’s conjecture for biplanes, we gave a construction which always produces a sesqui-array, and gave sufficient conditions for it to give a triple array.

This uses the notion of Hussain chains, a convenient representation of a biplane. Let B be a block of a biplane. Any other block meets B in two points, and any pair of points lie in just one further block; so we can represent the other blocks by pairs of points of B. How do we represent the remaining points? If q is a point outside B, then let H(q) be the graph with vertices the points of B, and edges the pairs representing the blocks containing q. It is easy to see that H(q) is a union of cyles. Moreover,

  • two intersecting pairs of vertices are edges in a unique Hussain chain;
  • two disjoint pairs of vertices are edges in exactly two Hussain chains;
  • two distinct Hussain chains share exactly two edges.

Now we build an array as follows:

  • the rows are indexed by the points of B, and the columns by the points outside B;
  • the symbols are indexed by the 2-element subsets of B;
  • in row p and column q, we put {x,y} if x and y are the neighbours of p in H(q).

As stated above, this is always a sesqui-array. It is a triple array if every Hussain chain (for the given choice of block) is a union of 3-cycles.

The biplanes possessing a block with this property are:

  • the “nicest” biplane on 16 points (any block will do, and the Hussain chains are all the graphs consisting of two 3-cycles);
  • one particular biplane on 37 points (the Hussain chains are the cycles of elements of order 3 in PSL(2,8)).
Posted in exposition | Tagged , , , , , , | Leave a comment