Steiner systems exist, 2

One of the inevitable consequences of getting old is that my brain becomes more and more like a Swiss cheese, and important pieces of information fall through the holes.

So I owe an apology to Michael Braun, Tuvi Etzion, Patric Østergård, Alexander Vardy, and Alfred Wassermann. They proved the existence of non-trivial Steiner systems on vector spaces over finite fields. In my post about the open problems on Steiner systems following Peter Keevash’s breakthrough existence proof, I said,

The problem is a virtually complete lack of examples!

This was code for “I know that someone did something but I am afraid I have forgotten who it was”.

Anyway, in a paper on the arXiv, the authors construct several examples. Alfred Wassermann sent me the link, which is why I remembered I had seen it somewhere, but I failed to remember where.

Anyway, to reiterate: I think that the most significant problem on Steiner systems now facing us is the existence of vector space analogues. We are looking at sets of k-dimensional subspaces of an n-dimensional vector space over a finite field with q elements, with the property that any t-dimensional subspace lies in a unique member of our collection. We require for non-triviality that t < k < n. As in the set case, there are divisibility conditions which are necessary for existence, but we are lacking any really strong existence (or non-existence) theorems.

The only case where anything non-trivial was known is the case t = 1, where the object is known as a spread. The single divisibility condition asserts that k must divide n; this condition is also sufficient, as the following construction shows. Take a vector space of dimension n/k over the field with qk elements; now B is the collection of 1-dimensional subspaces. This is trivial, but we obtain a non-trivial example by restricting scalars to the field with q elements, when the dimensions of the space and the subspaces are multiplied by k. Considerations from projective geometry show that these are the only examples in the case where n/k > 2; but if n/k = 2, there are many other examples, corresponding to affine translation planes of order qk (the lines are the cosets of the distinguished subspaces).

Anyway, Braun et al. have made the first crack in the wall, with several examples having n = 13, k = 3, t = 2, and q = 2.

Posted in exposition | Tagged , , | Leave a comment

A sun dog

I’ve been fascinated by sky phenomena for some time; when out walking, I always keep an eye on the sky. Some years ago, on a train on the West Coast Main Line in the Lake District, I was treated to a very fine solar halo which lasted for nearly half an hour. (Nobody else in the carriage seemed in the least interested.)

The northern light in St Andrews is a great delight; we get lovely cloud effects, colourful sunrises and sunsets. But last week there was a special treat: one of the most brilliant sun dogs (parhelia) I have ever seen. And I didn’t even have to stir outside my house to see it.

The picture doesn’t really do it justice, though.

A sun dog

Posted in geography | Tagged , , | Leave a comment

Tools for mathematicians

Over the weekend, in connection with a research project on semigroups (which I will write about shortly), I needed to know the distribution of the size of the image of a random mapping from the set {1,…,n} to itself.

I was at home in St Andrews, without access to the University’s journal and MathSciNet subscriptions. I thought it would be in the 800+ page Analytic Combinatorics by Flajolet and Sedgewick; but my copy of the book was in London. However, I had the PDF of the book on my laptop. (I don’t know how they did it, but the authors got Cambridge University Press to agree that the published version of the book could be given away free!)

So I looked in there. First problem: do they call them functions, maps, mappings, transformations, or something else? I searched all likely index entries and found nothing. So I decided to look for the formula which I believed to be correct for the mean of the distribution. But how do you search a PDF file for a mathematical formula? YOu can try; sometimes it will work, at other times it won’t.

So in the end I drew a blank. I’ve been too busy this week to get back to this.

In principle, searching for formulae is a chancy business, since the same formula can use different variables, and present a very different appearance to a search engine. In this case, the mean should be (1-1/e)n (the distribution is top-heavy, unlike the binomial coefficients), and e and n are fairly standard, so it should be possible.

I think there is a serious problem here, if anyone is thinking about tools to help mathematicians use the internet in their research.

Posted in doing mathematics | Tagged , | 7 Comments

A small calculation

Yesterday, a competitor in the London marathon collapsed and died. The event warranted a headline on the BBC news. The article pointed out that someone collapsed and died two years ago.

Now, of course, running a marathon puts a huge strain on competitors; but these people should be fitter than average. So how surprising are these statistics?

A very small calculation, taking the average lifetime of a person to be 70 years, the average marathon time to be 5 hours, and the number of competitors 36000, shows that the expected number of ordinary people who would die during the equivalent period of ordinary life would be just over 1/4.

So it seems that the answer is, not at all surprising.

I did a similar calculation at about the time I ran the London marathon for the first time. The number then was very similar.

Posted in Uncategorized | Tagged | 4 Comments

Real v recreational mathematics

A footnote to my report on Persi Diaconis’ lecture on Martin Gardner.

Persi challenged us to consider the question: Is there a sharp division between “real” mathematics and “recreational” mathematics, and if so, where does it come?

G. H. Hardy clearly thought that there was. He acknowledges that a chess puzzle is mathematics, but clearly distinguishes it from what he and his colleagues do.

Persi took a different view. Telling his own personal story, he explained how he learned to do a perfect riffle shuffle. This involves taking a pack with an even number of cards, dividing it by a cut into two equal packets, and precisely interleaving them so that cards from the two packets alternate. There are two kinds of perfect shuffles: the out-shuffle leaves the top card of the original pack on top, while the in-shuffle places it second, below the top card from the bottom packet.

Persi explained how, once he had learned how to perform perfect shuffles, he was led naturally to the question of how many shuffles are required to return the cards to their original order. For a regular pack of cards, eight out-shuffles or 52 in-shuffles are required.

Consider the number 52. If we number the cards in their initial order from 1 to 52, the perfect in-shuffle takes card k to position 2k, where the numbers are taken modulo 53: thus, card 1 goes to position 2, and card 27 (the top of the second packet) to position 1. Now it happens that 53 is a prime and 2 is a primitive root mod 53, so that the powers of 2 run through all the non-zero numbers mod 53. This explains why 52 shuffles are required; 252 = 1 (mod 53), but no smaller power satisfies this.

This argument works in general; the order of the perfect in-shuffle of an even number n of cards is the order of 2 mod n+1. So the maximum possible order is n, which is realised if and only if n+1 is a prime and 2 is a primitive root of this prime.

Does this happen infinitely open? The Artin conjecture, one of the biggest unsolved problems in mathematics, asserts that it does. The conjecture is open, but has been proved assuming the generalized Riemann hypothesis, an even bigger unsolved problem.

So “recreational” mathematics leads us directly into something which even Hardy was unable to solve!

A fascinating question which fell outside the remit of the lecture is to determine the structure of the group generated by the two perfect shuffles (as permutations of the cards). This was solved by Persi Diaconis, Ron Graham and Bill Kantor in 1983. The most fascinating item in the list is for n = 24, where the group is an extension of an elementary abelian group of order 211 by the Mathieu group M12.

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

66th British Mathematical Colloquium

By the time you read this, the BMC at Queen Mary will be over, or almost over.

Due to circumstances more-or-less outside my control, I was only able to attend the first half-day. I heard the plenary lecture by Cédric Villani, the Google lecture, and the public lecture on Martin Gardner by Persi Diaconis. But I also had plenty of opportunity to talk to old friends, and to hear the news that this meeting reversed the trend of recent years and was the biggest BMC ever, with over 300 delegates. My colleagues, especially Ivan Tomašić, had done an absolutely marvellous job of getting the show on the road, with a stunning list of invited speakers. There was a real buzz on the first day, and I hope it continued throughout the meeting.

I will say a little about the one event in which I had some part, the public lecture. When the BMC business meeting in 2011 accepted the invitation to meet at Queen Mary this year, I looked for something to celebrate, and found the ideal subject: this year is Martin Gardner’s 100th anniversary. He died four years ago, but his memory is certainly alive.

Martin Gardner was a mathematical magician. I mean this in two senses. First, there is a connection between mathematics and magic; many magic tricks are based on a piece of mathematics, and some areas of mathematics lend themselves readily to the creation of mathematical tricks. But second (and for me, far more important), Gardner could take the straw of everyday objects or events, and spin solid gold mathematics out of it, as he showed many times in his famous Scientific American column.

So my next thought is that the person to speak about this should also be a mathematical magician in both those senses. The obvious person who sprang to mind was Persi Diaconis. As an added bonus, Persi had known Martin Gardner very well over a long period. The moment he agreed to come and give a public lecture was when I was sure that the meeting would be a success.

Persi Diaconis on Martin Gardner

The lecture was held in the recently refurbished Great Hall of the People’s Palace in the East End of London, now part of QMUL. The hall had a capacity of 750, and the event was “sold out” (tickets were actually free), so many Martin Gardner fans had come expecting a treat. And what a beautiful lecture it was. Persi set out to show us the kind of person Martin was, and did this mostly by telling stories. The audience, many of whom had come under the spell of Martin Gardner, were privileged to be able to feel they knew him much better at the end.

For me, the most poignant story was one Persi told in answer to the last question. Apparently, Martin Gardner, on being asked by a publisher (the son of his publisher at the time, in fact) whether he had any books which could be considered, answered that he had in his desk drawer a novel he had written some time earlier. It was duly brought out, and Persi described how Martin had been eagerly anticipating its reception by the critics, and even speculating that this could be the break that would get him off the treadmill of writing about mathematical diversions. Stop and think for a moment what a disaster that would have been! In the end, the book was largely ignored by the critics and the book-buying public, and Gardner continued doing what he did so well. Persi’s comment was, “I’m a mathematician, and if I ever try to be anything else, I hope someone throws a pie in my face”.

Persi did one of Martin Gardner’s best-known magic tricks for us. He got Ursula Martin to be his assistant, and invited her to answer three questions about a “random” card, where she was allowed to lie to any or all of the questions; he still correctly. Mathematically, it shouldn’t work, and I didn’t speak to anyone afterwards who figured out how it was done (or if they did, they were keeping quiet).

Anyway, I am allowed to use a much-misused word and say that the audience had been treated to a unique experience; Persi announced afterwards that he would almost certainly never give that lecture again. How fortunate we were to be there!

Posted in events | Tagged , | 6 Comments

On either side

We are currently spending quite a lot of time on the East Coast line between Kings Cross and Leuchars. Max kindly gave us a book called On Either Side, a facsimile of a publication by the London and North Eastern Railway in 1939, giving their passengers information about places and things of interest near the railway line (many of them visible from the train).

Apart from the great deal of interesting information, it has the charm of a publication from a different age. Here are a few things it points out:

  • “Sandy is supposed to have been one of the leading Roman stations.” [And you didn't know that the Romans had built the British railway network?]
  • “No half dozen words can possibly give expression to the innumerable charms of the Yorkshire Dales.” [Presumably even a countable infinity of words would not suffice.]
  • “Birnham Hill. The wood which formerly covered its slopes is celebrated in Macbeth. The Hill is much more sparsely wooded to-day.” [Readers of Macbeth know the reason for this.]
  • “The ruined buildings across the Spey are the Ruthven Barracks, built in 1718 to overawe the Highlanders, and destroyed by them in 1746.” [So the Barracks failed in their purpose.]
Posted in geography, history | Tagged , , , , | Leave a comment