From the archive, 10

Here, for the record, are the other papers in the cache I found this week. Apart from preprints of papers which were published, there are five typescripts and a number of handwritten pages. The unpublished typescripts are:

  1. Rosemary A. Bailey and Peter J. Cameron, The eigenvalues of averaged symmetric matrices. [Our first joint paper, rejected and never published. The paper sets the problem of finding the eigenspaces of the n×n matrix obtained by averaging the images of a real symmetric matrix under a transitive group acting on {1,…,n}, and why statisticians want to do this.]
  2. Peter J. Cameron, Yet another generalisation of Fisher’s inequality. [Proved in response to a question from one of my first PhD students at Queen Mary, Mark Whelan. An m-part t-design on a set X of points is a collection of functions from X to {1,…,m} such that the inverse images of each point in all functions have the same size, and the number of functions taking prescribed values on t distinct points depend only on the prescribed values and not on the chosen points. For m = 2, this is equivalent to a complementary pair of t-designs. I show that an m-part 2-design has at least (m−1)v functions, where v is the number of points.]
  3. Peter J. Cameron, Locally projective spaces and the transitivity of parallelism. Submitted to a journal, possibly Math. Z., in 1976; rejected, then abandoned. [A study of geometries with the property that, if three hyperplanes have the property that two of the three intersections are codimension-2 subspaces, then the third is empty or codimension-2.]
  4. Peter J. Cameron, Paired suborbits. [Sims showed that paired subconstituents in a finite transitive permutation group must have a common no-trivial quotient; in my thesis I used his method to prove other results of this sort, and this note extends the ideas further.]
  5. Peter J. Cameron, Automorphism groups of parallelisms. [These are parallelisms of the design of all t-subsets of an n-set, where t divides n. Some of this went into my book on parallelisms.]

There are also some handwritten papers:

  1. Three things I wrote as an undergraduate: one takes the set of unordered n-tuples over some mathematical structure (ordered set, field, metric space) and explores giving it a related structure; one considers the set of 2×2 real matrices commuting with a given matrix and attempts to mimic the structure of the complex numbers; the third takes the set {1,2,…,mn}, partitions it into m sets of size n, takes the product of the numbers in each set and adds these products, and asks: what is the minimum value?
  2. Three different constructions starting from a Hadamard matrix of order n and producing symmetric Hadamard matrices of order n2 with constant diagonal and constant row and column sums.
  3. A generalisation of the outer automorphism of M12: take a pair of 3-designs, in each of which the complement of a block is a block, and there are correspondences between pairs of points in one design and complementary pairs of blocks in the other.
  4. Subsets of projective planes having a constant size intersection with every secant.
  5. Yet more generalisations of Fisher’s inequality, some of which got into my BCC papers in 1973 and 1977. One document considers designs in vector spaces; the other, designs in association schemes.
  6. Some characterisations of 2-arc transitive graphs (if they have enough quadrangles, they are known: this grew out of my thesis, but unlike there, it did not assume vertex-primitivity.
  7. Relations between paired subconstituents of transitive permutation groups. (Sims showed that they must have a common no-trivial quotient; in my thesis I used his method to prove other results of this sort, and this note extends the ideas further.)
  8. A paper with Peter Neumann characterising the permutation groups which are 3/2-transitive on the k-subsets of the domain, for some k: the groups S7 and A7 are the only examples.

The most interesting to me are the undergraduate pieces, since it might seem as if a lot of the mathematics I did grew from considering the structure of the set of k-subsets of an n-set.

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

From the archive, 9

Looking for a book yesterday, I turned up a file of old papers. One of them I think deserves an afterlife, so I re-typed it and here it is.

First, the background.

Let A be an n×n matrix. The permanent of A is calculated in a similar way to the determinant (as a sum over permutations), but without the alternating signs. In other words, for each matching from rows to columns, take the n elements of the matrix picked out by the matching (those whose row and column numbers are matched), and multiply them; then sum the results over all n! matchings.

Unlike the determinant, which can be computed with O(n3) arithmetic operations, the permanent (despite its simpler definition) is hard to compute, indeed it is #P-hard. However, it is important, since it counts various things of interest. In the special case where the entries of A are all 0 or 1, the term corresponding to a matching is 1 if all the corresponding matrix entries are 1, and is 0 otherwise. So, regarding such a matrix as describing a bipartite graph (whose vertices are the rows and columns, with an edge wherever there is a 1 in the matrix), the permanent of A is the number of matchings (sets of n disjoint edges) in the graph.

A square matrix is said to be doubly stochastic if its entries are all non-negative and its row and column sums are all 1. The reason for the name is that a non-negative matrix with row sums 1 can be regarded as the transition matrix of a Markov chain with n states; the column sum condition essentially means that we can run the Markov chain backwards.

A permutation matrix (a (0,1)-matrix with a single 1 in each row or column) is doubly stochastic (though the Markov chain is not stochastic at all, but completely deterministic!); its permanent is 1. The matrix with every entry 1/n is also doubly stochastic (and represents a Markov chain which forgets where it came from after 1 step), and has permanent n!/nn.

In 1926, van der Waerden conjectured that the permanent of a doubly stochastic n×n matrix is at least n!/nn, with equality holding only for the constant matrix. This conjecture was proved in 1979 or 1980 independently by Egorychev and Falikman. However, it is less remembered that, in 1979, Bang and Friedland independently gave the slightly weaker lower bound 1/en. (I would like to pay tribute to Jack van Lint, who told me about these results.)

I had been thinking about Latin squares, Steiner triple systems, and what I then called “edge-parallelisms” (or 1-factorisations of complete graphs). These three have many things in common, including a Markov chain (proved for Latin squares but still conjectural in the other cases) for choosing one uniformly at random. Subsequently I invented the notion of a “generalised t-design” and remarked that these objects are the generalised 2-designs with block size 3 and λ = 1.

There were at the time upper and lower bounds for the numbers of such objects on n points. It was known by many people at the time that a proof of the van der Waerden conjecture would improve the lower bounds so that they would be much closer to the upper bounds. Indeed, the logarithms of the upper and lower bounds would be asymptotically equal, and would be cn2 log n, where c is 1 for Latin squares, 1/6 for Steiner triple systems, and 1/2 for edge-parallelisms.

Now it was clear to me in 1979 that the result of Bang and Friedland was good enough to have the same effect. Moreover, I saw that the upper bound for the number of objects having some non-trivial symmetry would be asymptotically smaller than the lower bound for the total number of objects. Hence:

Theorem Almost all Latin squares, Steiner triple systems, and edge-parallelisms have trivial automorphism group (in the sense that the proportion of such objects of admissible order having a non-trivial automorphism tends to 0 as n tends to infinity).

I thought this was an interesting result, and typed it up. But before I could submit it, or even properly check it, Laci Babai published the result for Steiner triple systems, and so I abandoned my manuscript.

Laci knows of its existence, and over the years has urged me to make it public. I was previously unable to do so since I couldn’t put my hands on it. But now I have found it, so I am happy to put it on the web (for the sake of history, not with any intention of claiming credit retrospectively).

Of course I don’t remember exactly when I wrote this. But the fact that I cite Bang and Friedland but not Egorychev and Falikman indicates that it was in the very small time gap between the appearance of these two pairs of papers, so in 1979 or 1980.

I have typed the manuscript “as is”. Apart from correcting one confusing misprint, and adopting LaTeX conventions such as numbering theorems and lemmas, it is an exact copy of the original (modulo the inevitable typos). In particular, I have not checked the mathematics; while typing it out I thought that the argument in the case of edge-parallelisms is not quite right. I think it can probably be put right.

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

Donald’s design

In 1982, Donald Preece published a remarkable design (a “double Youden rectangle”) which he had recently constructed. The design is a layout of an ordinary pack of playing cards, with properties described below.

I discussed this design before here.

Donald was so pleased with his design that he stuck playing cards to a thick card and mounted them (with commentary) in a frame, so they could be displayed in the foyer of a mathematics department.

This never happened. But the mathematics building at Queen Mary is being refurbished, and as part of clearing Donald’s papers from the emeritus staff offices, I found the original (which, you will note, is slightly different from the version he published).

Below is a photograph of the design. I have been unable to make the commentary legible, so I have put it in the text around the picture.


A “BALANCED DESIGN”

Donald's design

  1. Each value A, 2, 3, …, 10, J, Q, K appears once in each row.
  2. Each suit appears in each column.
  3. Each pair of the values A, 2, 3, …, 10, J, Q, K occurs together in just one column.
  4. Each row has 3 cards of each of 3 suits, and 4 cards of the other suit.

Design obtained by D. A. PREECE (Rothamsted Statistics Department) and published in 1982.

This arrangement of cards is a possible design for an experiment on fruit trees.
Each card corresponds to a “plot” of trees, the plots being in 4 rows and 13 columns.

The values A, 2, 3, …, 10, J, Q, K represent 13 treatments from a first set, and the suits represent 4 treatments from a second set.

Posted in Uncategorized | Tagged , , , | 1 Comment

Mathematics, poetry and beauty

Comparing mathematics with poetry is an infinitely rich game. For every opinion you express, there is an equally valid counter-opinion. Contrasted to Hilbert’s dismissal of a student who had left mathematics for poetry, “I always thought he didn’t have enough imagination for mathematics”, someone said to me recently that the early death of Schubert was a greater tragedy than that of Galois, since what Galois could have achieved would sooner or later be done by someone else, whereas Schubert’s potential was lost forever.

So it isn’t so surprising that a book by Ron Aharoni, newly translated into English, doesn’t come to a definite conclusion one way or the other. The best we can do in a book entitled Mathematics, Poetry and Beauty is to give many examples of beautiful mathematics and beautiful poetry and discuss what the similarities and differences are.

Ron Aharoni is a mathematician whose field is combinatorics. He has collaboration distance 2 from me (we are both co-authors of Paul Erdős). I hadn’t heard from him for a while. In the book he explains that he made a deliberate move from university to elementary school.

Many, though not all, of his examples of poetry are taken from Israeli poets. I don’t know whether Hebrew is a particularly good language for poetry, but some of these poets pack many layers of meaning into a few words. But other poets appear, including Johann Wolfgang von Goethe, John Donne, Emily Dickinson, Federico Garcia Lorca, Constantine Cafavy, William Carlos Williams, and Matsuo Basho.

Here is an example of the argument. Displacement is a mechanism which, according to Freud, occurs in almost every area of human thought. By focussing on a subsidiary idea, the main message slips through almost unnoticed, although it may be too painful to face directly. Aharoni suggests that this is a technique used by poets for diving inside themselves, and for mathematicians stuck on a problem who look at a seemingly irrelevant detail in the hope of a breakthrough. He gives several examples, both poetic and mathematical.

One of his telling comparisons, expanded over four chapters, is that both a poem and a mathematical proof constitute a game of ping-pong between the abstract and the concrete. A poem can have several such switches in a few lines, as in this example “Written in pencil in the sealed railway-car” by Dan Pagis (translated by Stephen Mitchell):

Here in this carload
I am Eve
with my son Abel
if you see my older boy
Cain son of Adam
tell him that I …

In mathematics, both finding a proof and (if you are kind to your readers) presenting it involve frequent shifts of focus between logical argument and examples. But Aharoni’s conclusion is

… the heart of the poem is given to the concrete, and it is in this direction that the poem goes. This is the diametric opposite of the ping-pong of mathematics, in which the last shot is always towards the abstract.

It is also true that, as he remarks, in many published proofs (most notoriously, those of Gauss, the “fox who effaces his tracks in the sand with his tail”, according to Abel), all traces of the concrete are covered and only the shots to the abstract remain.

This points to another important difference. A finished poem can convey its beauty to any open-minded reader; knowledge of the poet’s biography often gets in the way. But the beauty in mathematics lies in the experience of the discovery of the proof; this can be reproduced to some extent in a reader who follows the argument carefully, but does not reside in the published proof, and still less in the statement of the theorem (in most cases).

And on the same theme, Aharoni invites us to watch the mathematician and the poet at work. The striking secret he reveals is that the mathematician spends most of his time staring into space.

Both poets (as many thinkers have observed) and mathematicians are concerned, not with ever more florid invention, but with the truth. It seems like a different kind of truth. Poets remind us of things we already know. But almost every mathematician, no matter which side they take on the “discovered or invented” question, are in their ordinary work Platonists, and act as if that their mental constructions are “out there”. However, the means they have for diving inside themselves, described in detail by Hadamard in his book, and divided into four stages (preparation, incubation, illumination, and verification) go well beyond the subjective ways that poets operate.

There is much more thought-provoking material in the book, many more dimensions on which mathematics and poetry can be compared. The chapter titles give some indication, including “The miracle of order”, “The power of the oblique”, “Reality or imagination”, “Unexpected combinations”, “Symmetry”, “Content and husk”, and “Change”.

Posted in mathematics and ... | Tagged , , , , | 7 Comments

Two chairs occupied

The School of Mathematics and Statistics welcomes two new professors who have taken up established chairs: the Regius professor (one of only one or two Regius chairs in mathematics in the UK until two years ago – the information on Wikipedia is inconsistent) is Igor Rivin, and the Gregory professor is Mark Chaplain.

Both have come across the water to join us, but very different amounts of water: Mark from across the Tay, and Igor from across the Atlantic.

We look forward to working with them both.

Posted in Uncategorized | Tagged , , | Leave a comment

Computer blues

No, not a grumble: a story with a happy ending.

Back in 2008, when the Asus eee-pc notebook came out, I got one of the first. I have written elsewhere about how it was indispensible on my Forder tour of New Zealand, and for various other things. This was a nice machine: built to be used by small children, it was as near to indestructible as a common computer can be, built to be thrown around the room. No disk drive, no moving parts. However, this was also a drawback: it had 2Gb of memory which had to function as RAM and RAMdisk. So not feasible to install TeX on it. You could increase the storage by putting a card in the slot. Also, it ran Xandros (a version of Linux), heavily disguised, rather than Windows, and CTRL-ALT-T would produce a terminal window.

I have a very good Acer laptop now, but it is a bit bulky for taking to conferences, and quite infeasible for taking on a walk. So I decided to try to get a more up-to-date notebook.

Amazon offered me one, via their Marketplace associates, a company called BlueAnteater. I think this company comes out well from this story, although there was a glitch. First they emailed me to say that the machine had failed its test; they could offer me another (with Windows) or my money back. I said I didn’t want Windows, so they came back with an offer to install the flavour of Linux of my choice. I opted for Ubuntu.

The machine came very promptly indeed, and straight out of the box it seemed to work fine. As the company had promised, it was a pleasing shade of dark blue. It had 2Gb RAM and 130Gb hard disk, and had Windows and Ubuntu 13.10 installed.

But of course, I needed to install a few more things, most notably TeX, GAP, and Dropbox.

I am the sort of person who sits watching the screen while TeX installs. I noticed that some program I had never heard of, which seemed to have nothing to do with TeX, was not installed properly. Like a hole in a tooth, this seemed to provoke the downloader to return often to this program, without any progress. So when it had finished, and it offered me the chance to install upgrades, I took it.

Unfortunately, the download failed – maybe I did something wrong, who knows? – and I was left with a computer that hung after I had entered my password.

I feel unreasonably pleased by the fact that I didn’t immediately panic and phone the company or send the machine back. I slept on it, and the next day (the wet Sunday of the bank holiday weekend) I had a plan.

I went online with my other computer and found how to make a Ubuntu boot USB stick, which I then did. Putting this into the notebook, it booted into a cut-down Ubuntu, and one of the options it offered was a complete re-installation of Ubuntu 14.04, overwriting everything. I thought this was the safest course, so accepted. Added advantage: the Windows partition was reclaimed, so more usable space on the disk.

From then, everything proceeded flawlessly. Ubuntu installed, then my essential programmes installed. This would probably not have been feasible a year ago, but they have upgraded the connections in this little corner of north-east Fife to fibre-optic, and in the mornings I can get download speeds of 1.5Mb/sec, so it didn’t even take too long. Synchronizing Dropbox, however, took rather longer, as I have over 40Gb there now. (I tried to forestall this by loading the Dropbox folder from a recent backup. Not sure whether this saved any time at all.) On Tuesday I put eduroam on and got it working.

The re-install also allowed me to give the computer a more meaningful name. All three of my current machines are named after mathematicians who have influenced me: Erdős, Seidel, and Higman.

So now I have a machine which is both a fully usable computer and a portable notebook/organiser.

Incidentally, I can’t find BlueAnteater on Google (it offers me various cartoons such as “Snuffle my blue-nosed friend” or a meat packing company in Broxbourne instead), so this is an indirect way of giving them a feedback comment.

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

Open Studios North Fife

Over the Bank Holiday weekend (yes, Scotland does observe Labour Day, though not Good Friday or Easter Monday), artists and makers of north Fife opened their studios. We visited a few. Saturday was the Farmers’ Market and we just managed to get out in the afternoon to a couple of local artists. Sunday was a washout, rain all day. But Monday was a beautiful Spring day, and so we went to see a cluster of studios in Cupar and a couple just a little way out of the town in Foodieash.

Open Studios

The artists here are Keith Proven, Katy McKidd Stevenson, Jonathan Dowling, Vicky Coull, Siv MacArthur and Roderick Gauld.

As always with this kind of event, I am amazed at the amount of creative talent and imagination lurking behind doors of suburban houses and country cottages.

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