From the archive, 8

Various diaries came to light while I was office-clearing last Christmas, most notably a diary I kept for five months, from December 1986 to May 1987. I had just started work at Queen Mary College (as it was then), and celebrated my new job by applying for a place in the London Marathon; the diary begins on the day the acceptance arrived, and ends the day after the race, in which I ran 2hrs 46mins 59secs and came 957th out of a field of over 20000.

I have just typed it up (it runs to 105 pages, so nobody wants to read it). I found the experience very evocative; apart from the training, and the new job, I was facing commuting from Oxford to London (four hours travel every workday), and doing my share of childminding (the children were 11, 9, and 7 in the time, and all sang in choirs).

The diary records day to day events, running and other injuries, reflections on my running on the past and comparisons with the present, etc.

I ran the London Marathon again the following year; the year after that, I sat on the sofa and watched it on television, and was thoroughly put in my place when I saw Gareth Jones (who was a student with me in Oxford, and at the time did no sport while I ran in the University cross-country team and earned a Full Blue) finish in a time of somewhere round 2hrs 25mins.

The exercise of typing up the diary might inspire me to start running again when I am back in St Andrews; it is in many ways a more attractive place for running than London.

Posted in history | Tagged , | Leave a comment

A letter to the Guardian

Don Braben is one of my heroes. He has a clear-headed but deeply-held belief, with which I agree, that the bureaucracy of modern science gets in the way of getting good science done, at a time when the world needs good clear science more than ever. He was a leader in the (mostly unsuccessful) campaign against “Impact” in the REF.

So I am very happy to be a signatory of a letter published in yesterday’s Guardian on this subject. Here is the text of the letter:

“Science is the belief in the ignorance of experts,” said Richard Feynman in the 1960s. But times change. Before about 1970, academics had access to modest funding they could use freely. Industry was similarly enlightened. Their results included the transistor, the maser-laser, the electronics and telecommunications revolutions, nuclear power, biotechnology and medical diagnostics galore that enriched the lives of virtually everyone; they also boosted 20th-century economic growth.

After 1970, politicians substantially expanded academic sectors. Peer review’s uses allowed the rise of priorities, impact etc, and is now virtually unavoidable. Applicants’ proposals must convince their peers that they serve national policies and are the best possible uses of resources. Success rates are about 25%, and strict rules govern resubmissions. Rejected proposals are usually lost. Industry too has lost its taste for the unpredictable. The 500 major discoveries, almost all initiated before about 1970, challenged mainstream science and would probably be vetoed today. Nowadays, fields where understanding is poor are usually neglected because researchers must convince experts that working in them will be beneficial.

However, small changes would keep science healthy. Some are outlined in Donald Braben’s book, Promoting the Planck Club: How Defiant Youth, Irreverent Researchers and Liberated Universities Can Foster Prosperity Indefinitely. But policies are deeply ingrained. Agencies claiming to support blue-skies research use peer review, of course, discouraging open-ended inquiries and serious challenges to prevailing orthodoxies. Mavericks once played an essential role in research. Indeed, their work defined the 20th century. We must relearn how to support them, and provide new options for an unforeseeable future, both social and economic. We need influential allies. Perhaps Guardian readers could help?

The signatories are: Donald W Braben, University College London; John F Allen, Queen Mary, University of London; William Amos, University of Cambridge; Richard Ball, University of Edinburgh; Tim Birkhead FRS, University of Sheffield; Peter Cameron, Queen Mary, University of London; Richard Cogdell FRS, University of Glasgow; David Colquhoun FRS, University College London; Rod Dowler, Industry Forum, London; Irene Engle, United States Naval Academy, Annapolis; Felipe Fernández-Armesto, University of Notre Dame; Desmond Fitzgerald, Materia Medica; Pat Heslop-Harrison, University of Leicester; Dudley Herschbach, Harvard University, Nobel Laureate; H Jeff Kimble, Caltech, US National Academy of Sciences; Sir Harry Kroto FRS, Florida State University, Tallahassee, Nobel Laureate; James Ladyman, University of Bristol; Nick Lane, University College London; Peter Lawrence FRS, University of Cambridge; Angus MacIntyre FRS, Queen Mary, University of London; John Mattick, Garvan Institute of Medical Research, Sydney; Beatrice Pelloni, University of Reading; Martyn Poliakoff FRS, University of Nottingham; Douglas Randall, University of Missouri; David Ray, Bio Astral Limited; Sir Richard J Roberts FRS, New England Biolabs, Nobel Laureate; Ken Seddon, Queen’s University of Belfast; Colin Self, University of Newcastle; Harry Swinney, University of Texas, US National Academy of Sciences; Claudio Vita-Finzi FBA Natural History Museum.

Please put your suggestions, stories, and ideas about how such people can be supported outside the funding mainstream here; I will make sure they get heard.

Posted in maybe politics, Uncategorized | Tagged , , , | 1 Comment

Combinatorics in Scotland, group theory in Portugal

I never really wanted to retire. For various reasons which no longer matter, I decided to retire from my position at Queen Mary, University of London, on turning 65 two years ago. I hoped that I would find enough to do to keep me busy, and I have not been disappointed!

Indeed, I have substantially overdone things, and yesterday began teaching my fourth course this year …

Combinatorics in Scotland

This semester I have been teaching a course on Advanced Combinatorics at St Andrews. When they asked me for a syllabus for such a course, I provided three (roughly, one on enumeration, one on finite geometry, and one on group actions), and suggested that one of them could be approved and I would teach that. Instead, they approved all three, so I had to decide which one to teach (and I have the option of teaching the other two in successive years).

So this year it is enumeration. I felt fairly secure, having taught a much briefer course on enumeration at the London Taught Course Centre last semester. But, inevitably, this course is turning out a bit different. Something about the set-up encourages me to ramble on, and tell stories, about Paul Erdős, or Alan Sokal, or someone else. I spent much longer on basics of formal power series, since the class seemed to be well prepared in Analysis, and needed convincing that it really didn’t matter if the series converge or not. (My answer to that is in two parts: the good news is that it doesn’t matter, since the formal power series form a ring in which various other operations, such as substitution, infinite sums and products, and differentiation, all work fine (sometimes under specified conditions), and our manipulations are valid in this setting without the need for convergence; the good news, on the other hand, is that any identity between convergent power series expressed in terms of these operations is also valid in the setting of formal power series, so we can just read off from Analysis all properties of, for example, the exponential and logarithm functions that we need.)

I varied enumeration with a small dose of combinatorics of subsets early on, basically Ramsey’s theorem and Steiner systems, the second giving the opportunity to mention Peter Keevash’s result. (These are two topics where some of the formulae involve binomial coefficients, which had been discussed in the first part of the course.)

In fact, it has not quite gone as I expected. We have talked about subsets but not yet about partitions or permutations; we haven’t done any asymptotics yet, or group actions, or unimodality, and probably several of these topics are not going to get in. Yet I included things like the counting proof of the existence of finite fields, and the inclusion-exclusion formula for the chromatic polynomial of a graph; and if time permits I will do Richard Borcherds’ wonderful proof of Jacobi’s Triple Product Identity by counting states of Dirac electrons.

We are about three-quarters of the way through the course now. It is Spring break, so I have a couple of weeks to get myself ahead and produce the last few instalments of notes.

Group theory in Portugal

Meanwhile, João Araújo persuaded me to teach a course on Group Theory at the Open University in Portugal. The course started yesterday; little has happened yet apart from the students starting to introduce themselves. Already it is clear that I am not very competent with the Moodle interface (well, I did know that already – of course in St Andrews, the first thing I did was to make a course web page!), but I have two competent pairs of hands on the spot to catch me if I fall.

I like the idea of teaching open university students. If one can make invidious comparisons, they are on the whole more committed and enthusiastic than regular university students, since they are making very big sacrifices to study in their own time. I am, of course, a bit nervous that, being quite far away and not speaking their native tongue, I will give them a less good course than they deserve.

But so far, I am fairly happy with the notes I have produced. I started off knowing that there were certain things that should be put in, but after a while I came to see that putting in the things that I would like to be put in would work better. Group theory is a very technical subject; I am trying to give them an overview of the things I am interested in (of course, this means quite a big dose of group actions) without getting too bogged down. So, for example, I will cover doubly transitive groups but may not get on to saying much about primitive groups. (With doubly transitive groups, you get quite quickly to some pretty things.)

Many of these students have a strong background in computers, either a first degree or a job in IT, and several of them are skilful programmers. Maybe I will be able to set them some projects with real content, and get some good stuff done!

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

Note on infinity

A common caricature of the view of the mediaeval scholastics is that they wondered whether the number of angels who can dance on the head of a pin is infinite or not. In fact, this calumny was invented much later.

But another common view is that, after Aristotle told people that it was forbidden to think about completed infinities, nobody did so until Cantor broke the barrier.

I don’t think there was ever a time when people didn’t think about infinity. So I was interested to discover the metaphysical poet John Donne, in his poem Love’s Growth, perplexed by the question whether it is possible to make an infinite set bigger by adding something to it:

Methinks I lied all winter, when I swore
My love was infinite, if spring make it more.

Posted in mathematics and ..., Uncategorized | Tagged , | 2 Comments

Bayes again

It is always a pleasure to read David Colquhoun’s posts.

The most recent explains a simple statistical point that still escapes many health adminisitrators (and others). He describes two tests for Alzheimer’s disease. The first (which I will discuss) is actually a test for mild cognitive impairment (MCI), “a condition that may, but often isn’t, a precursor of Alzheimer’s disease”. This condition has prevalence 1% in the population; the new test has specificity 95% (so only 5% probability of a false positive) and sensitivity 80% (so 20% probability of a false negative). With the help of a tree diagram, he calculates that if the test were used for screening (as is proposed, apparently), 86% of people testing positive would not have the disease.

He is righteously (and rightly) indignant that everything from the journal’s press release to NHS Choices seems to ignore this, which as he says makes the test “worse than useless”.

This is a simple application of Bayes’ Theorem. I taught Probability to the first-year maths students for many years, and calculations like this were a standard example that I used.

How many times do you think Colquhoun mentioned Thomas Bayes (or Richard Price) in his article?

So this post is really a musing on the vagaries of fame in mathematics.

Posted in mathematics and ..., the Web, Uncategorized | Tagged , , , , , , | Leave a comment

Spring break

Off for Spring break

It’s a bit of a jolt, working in a country which, as a result of the extreme violence of the wars of religion, does not recognise Good Friday. I don’t think I ever taught on Good Friday before, but this term, I will do so.

By way of compensation, we have two weeks off now for Spring Break. Everyone leaves St Andrews, mostly dragging huge heavy suitcases, for a couple of weeks. I am going south, hopefully to see my newest grandson.

Posted in history | Tagged | Leave a comment

Steiner systems

Following Peter Keevash’s asymptotic existence proof for Steiner systems, does anything remain to be done? I would say yes, it certainly does; here are a few thoughts about the open problems in this area.

Existence

We are looking for a Steiner system S(t,k,n): that is, n points, blocks of size k, any t points in a unique block, with t < k < n. There are some divisibility conditions which are necessary for existence, and Keevash’s theorem asserts that they are also sufficient for large enough n, for fixed t and k. But that leaves a big hole.

The existence theorem was proved for t = 2 in the early 1970s by Richard Wilson, whose lower bounds for existence are not absurdly large, but still probably not best possible.

(Keevash does not give explicit lower bounds for n in terms of t and k. It would be interesting to know what order of magnitude can be obtained from his method.)

The general problem is:

Find necessary and sufficient conditions on the parameters for the existence of a Steiner system.

It is too much to expect a general solution to this problem, so we restrict to some special cases which have been interesting to geometers and combinatorialists.

For which q does there exist a projective plane of order q, that is, a Steiner system with t = 2, k = q+1, n = q2+q+1?

This is one of the most celebrated problems in finite mathematics. We know that projective planes exist when q is a prime power. The Bruck–Ryser theorem shows that they do not exist if q is congruent to 1 or 2 (mod 4) and q is not the sum of two squares. A huge computation by Clement Lam and colleagues shows that there is no projective plane of order 10. And that is the sum total of our knowledge. The last result, though very special, destroys the extreme optimists’ conjecture, that the Bruck–Ryser condition is necessary and sufficient.

The extreme pessimists’ conjecture, on the other hand, that projective planes exist only for prime power orders, is still open. A related conjecture, also still open, is that there is a unique projective plane of prime order, the classical one over the field of integers mod p. The rationale behind these conjectures is that, despite two centuries of effort, all the projective planes we know are coordinatised by algebraic systems of some sort (fields, or things obtained by twisting the multiplication in a field, or vector spaces over fields), and perhaps that is all there is. Moreover, the field of prime order cannot be twisted.

The existence of a projective plane is equivalent to that of an affine plane, a Steiner system with t = 2, k = q, n = q2. However, other interesting geometric objects are still undecided, such as inversive planes, with t = 3, k = q+1, n = q2+1.

Another interesting family satisfying the divisibility conditions has k = t+1, n = 2t+2, where t+2 is prime. These exist for t = 3 and t = 5 (both very famous designs with large automorphism groups), but not for t = 9.

Enumeration

An even harder question than existence is enumeration: how many Steiner systems with given parameters are there? Of course this is more general since a system exists if and only if the number is non-zero.

Indeed, there is only one general case in which results exist. Richard Wilson showed that the number of Steiner triple systems (t = 2, k = 3) of admissible order n is about ncn2. More precisely, the logarithm of this number is asymptotically (n2 log n)/6. This number is so much larger than n! that it makes little difference whether we account for isomorphisms between different systems or not.

Apart from this, all that is known are enumerations for particular values of the parameters, most notably the result of Østergård and Kaski that the number of Steiner triple systems on a set of 19 points (up to isomorphism) is 11084874829.

Any general non-trivial upper or lower bounds would be welcome …

Automorphisms

A consequence of Wilson’s enumeration result, proved by László Babai, is that almost all Steiner triple systems have no automorphisms apart from the identity. Even this is unknown for any other parameter values, though it may well be true for any fixed t and k as n → ∞.

On the other hand, “highly symmetric” Steiner systems will not exist in general. We know, from the classification of finite simple groups, that there are no 6-transitive groups apart from the symmetric and alternating groups. This means that the known highly symmetric examples, let us say the S(t,k,n) systems admitting t-transitive automorphism groups, are very special and precious and should be cherished.

Random choice

Here the situation is even worse.

Jacobson and Matthews gave a Markov chain for Latin squares which converged to the uniform distribution. There is an obvious modification of this which applies to Steiner triple systems, but (despite heroic efforts by Andrew Drizen in his PhD thesis) we do not even know whether it is connected in general!

Large sets and resolutions

If the necessary conditions for the existence of a Steiner triple system are satisfied, and if in addition the number of blocks of such a system divides the number of all k-subsets of the point set, then we can ask:

Can the set of all k-subsets of the point set be partitioned into Steiner systems?

A set of Steiner systems using each k-set exactly once is called a large set. Luc Teirlinck showed that large sets of Steiner triple systems exist for all orders except n = 7, where the non-existence goes back to Cayley (who showed that one cannot find more than two distinct systems in this case).

A resolution of a Steiner system is a partition of the block set into “resolution classes”, each of which partitions the point set. Do resolvable systems exist whenever the necessary conditions are satisfied and k divides n? This was proved for Steiner triple systems by Ray-Chaudhuri and Wilson, thereby answering a question posed by Kirkman in the 1840s.

A question which generalises both of the above is the following. Suppose that both of the parameter sets (t,k,n) and (s,k,n) are admissible, where s < t. Does there exist a S(t,k,n) whose block set can be partitioned into subsets each forming an S(s,k,n)?

Universal algebra

It is well known that Steiner triple systems give rise to two types of quasigroups or loops: we take the “product” of two points to be the third point on the block containing it, and use one of two possible strategies for the product of a point with itself. Algebraic properties such as associativity or the Moufang law for these structures translate into geometric or combinatorial properties for the Steiner triple systems.

Ganter, Quackenbush, and others extended this to other kinds of Steiner systems, but apparently came up against a natural boundary to the techniques quite soon. It may be that there are no surprises lurking here.

Steiner systems in vector spaces

I think that this is the most important area to attack next.

We can alter the definition of Steiner system by replacing “set” and “subset” by “vector space” and “subspace” (over a given finite field GF(q)). In other words, we have a collection of k-dimensional subspaces over an n-dimensional vector space over GF(q) with the property that any t-dimensional subspace lies in a unique subspace in our collection.

This is in a sense part of a programme instigated by Jacques Tits, which regards the combinatorics of sets and subsets (and other things) as “projective geometry over the field with one element“. Many areas of combinatorics can be “extended” to larger fields. Sometimes the theorems are known (e.g. the analogue of Ramsey’s theorem, due to Graham and Rothschild, uses the Hales–Jewett theorem); others, such as Steiner systems, still await progress.

The problem is a virtually complete lack of examples!

Perfect matroid designs

A common generalisation of Steiner systems over sets and vector spaces is the area of “perfect matroid designs”. These are matroids where the cardinality of a flat depends only on its rank.

Michel Deza popularised the problem (which also arose in some early work of mine) of finding a perfect matroid design of rank 4 on 183 points, where the lines have three points and the planes have 21 points. Each plane is a Steiner triple system of order 21; and the quotient by a point is a projective plane of order 9. These designs are still unknown. Indeed, very few examples of perfect matroid designs are known, even though they are beautiful structures with many interesting properties.

t-designs

Peter Keevash also proved the asymptotic existence of t-designs, where each set of t points lies in exactly λ blocks (rather than exactly one block). Everything said so far can be generalised to t-designs. Most of the problems are wide open!

Posted in mathematics, open problems | Tagged , , , , , | 2 Comments