Mike's home
Academic history
Recent Articles
Old Articles
Theory group
My bookmarks
My blog
I was a lazy child (and grew into a lazy adult). I got by at school with the minimum possible effort and now most of my geographical, historical, and scientific knowledge derives from much later years when I realised what I had been missing. Despite my laziness I threw myself into things that caught my interest and these early enthusiasms were fairly typically mathematical. When I was about 11 I read some science fiction by W. E. Johns (better known as the creator of Biggles). One of these books had a table of data about the planets: their solar distance, day length, diameter etc. and I found this completely fascinating. For a year or two I read as much astronomy as I could get my hands on. The vastness of the universe compared to our infinitesimal place within it has been a source of wonder to me all my life.
A year or so later my enthusiasm turned to Chess. Again I read dozens of books on chess tactics and strategy, played through the games of the 19th century and early 20th century masters, played correspondence chess, and joined my school chess club (in which I continued until leaving school even though the initial zeal waned upon my reaching a rather late puberty). I still have little notebooks, written in red fountain pen ink, of games by heros such as Paul Morphy and Adolf Anderssen. In my early thirties I returned to chess, this time as a player for the Cardiff Chess Club, and became reasonably capable at its higher levels. Ultimately however the devastation of losing games made me give it up and I eventually turned to Bridge:- a new problem every 7 minutes rather than the all or nothing battle over a chessboard against a grim opponent.
I didn't shine particularly at Mathematics until I was about 16 but there was a formative experience when I was 13. In the summer holidays I found myself one day bored and at a loose end. So bored in fact that I picked up the mathematics textbook that we used at school. At that point in my education we had been taught a little algebra: nothing more complicated than the solution of linear and quadratic equations in one variable. I found myself reading the chapter on linear equations in two variables and learnt how to solve them. The result was that next term, when we covered this topic in mathematics lessons, I shone - a rare experience but one which my teachers took note of and which made me realise that I quite liked this subject.
In those days pupils from the grammar schools took a very prescribed set of subjects until O Levels at around age 15 and my school entered me for 9 subjects. Somewhat to my amazement I passed them all. My Mathematics mark was my highest mark, though still not a very distinguished one. Still Mathematics was my favourite subject, indeed the only subject that I had any enthusiasm for. So, on entering the sixth form, it was a pleasure to be able to concentrate on a much narrower ranger of subjects: Mathematics, Further Mathematics and Physics (the last being the least of evils). Nevertheless it took at least a term before I was finally convinced that I was beginning a life-long romance.
One of the most important influences in those early sixth form days was the books of Martin Gardner. I found them an easy read, took much pleasure in constructing models such as regular solids and hexaflexagons and looked forward to each new collection from Gardner's Scientific American columns. An even greater influence was another popular work: E T Bell's Men of Mathematics. Bell gave me a historical perspective on almost three thousand years of mathematical endeavour, entertained me with anecdotes of the great mathematicians and gave me a skeletal understanding of the great strands of mathematical thought. Perhaps most significant however was that Bell made me begin to think for the first time of the timelessness of Mathematics, its independence of culture, and its universal truth, so much more compelling than the wishy-washy triteness of so-called religious truth which I had involuntarily imbibed as a choirboy from the age of 8 onwards. These books were the beginning of a reading spree of popular mathematics books that have been a regular part of my life ever since.
In my formal mathematics education my sixth form years were the years when I became a `serious' mathematician also. I do not mean that I showed great promise as a brilliant researcher but I did have excellent teachers – Edward Ramsden most of all – who drummed into me the calculus and all the other paraphenalia of A level Mathematics. Ramsden was disorganised, sometimes vague but with a tremendous enthusiasm for his subject that extended well beyond the formal syllabus. In extra periods in the lunch hour and in the occasional afternoon at his house he taught me projective geometry which gave me my first exposure to axiomatic systems and prepared me for the Oxford Entrance exam.
In 1964 I went up to read Mathematics at The Queen's College, Oxford. I was not a particularly social young man and, although I had longed to leave home, I found myself fairly lonely. Nor did I find the mathematics easy. But by that time I had formed the ambition to be a university mathematician - and a pure mathematician at that - and so I worked diligently. So diligently in fact that I missed out almost completely on the swinging sixties when so many of my contemporaries were feeling their sexual oats. Well, maybe it only seemed like that because in those days it was not easy for a male student in Oxford to meet women, the balance of the sexes at the university being 12 to 1. But no doubt in other parts of the land my counterparts were having a whale of a time.
My time at Oxford was greatly influenced by Peter Neumann. Peter had just been appointed to a position at Queen's (where he was to serve for almost 50 years). He was the son of famous mathematical parents and taught me the majority of my pure mathematics as well as becoming a life-long friend. After I graduated with my BA I went on to become Peter's doctoral student and I presented my D Phil thesis in 1970.
My doctoral work was on varieties of groups, a subject on which Peter and his parents Bernhard and Hanna had published extensively. At that time it was almost the Neumann family business (as well as an interest of the Savilian Professor of Geometry, Graham Higman who also supervised me for a short time when Peter was away). Hanna had just published a research monograph on the subject in whose preparation Peter had played a significant part.
Both Peter and Graham had wide interests in algebra. Indeed the 1960s were a heyday for algebra with the beginning of Gorenstein's project to classify the finite simple groups. So, while I was not able to contribute to that project myself, there was a huge number of lectures on group theory and representation theory going on and, although D.Phil. students were not required to study beyond their narrow thesis problem, I greatly enjoyed getting as much algebra into my head as I could.
In an alternative universe I could have become a career researcher specialising in varieties of groups as this was a very active area in the 1960s and I had become steeped in it. But two events frustrated this once desired outcome. The first was that the central question of the area was resolved in 1970 and the subject never regained its cachet. The second was much more personally significant: I failed to get a lectureship in Pure Mathematics. The 1960s had been golden years for young mathematicians in the UK; the creation of several new universities had made it possible for any moderately able young PhD graduate to walk into a lectureship. But those days were just ending and my research track record was not sufficiently impressive. Instead there occurred one of those accidental events that can change a life.
In early 1970, after a few rejections for applications for jobs in pure mathematics, I saw a small announcement on the notice board of the Oxford Mathematical Institute: the Computer Centre at University College, Cardiff was recruiting a lecturer and its director was D H McLain, a computational group theorist. At that time very few universities had departments of Computer Science and opinion was divided on whether it was even a respectable subject. Those within the subject had the advantage of being better able to imagine the potential of computers but, academically, it consisted of little more than programming and numerical analysis. This was hardly the mainstream stuff of a mathematics degree and, at Oxford, it was not even possible to study it as an undergraduate.
However it had happened that, at school, Geoffrey Cooke, the director of the Leeds University Computing Laboratory had given a talk to our Mathematics Society. Cooke offered me a summer job in the Laboratory and, in those generous days, required nothing from me beyond that I learn Pegasus Autocode and write a small program to find quadratic factors of a polynomial. A couple of years later I had another job there and this time I learned Algol 60. A few more years on I had a summer job at the UK Atomic Energy Labs in Harwell where (in a retrograde step) I was set to implement some tasks in Fortran. So, by the time I was reading the Cardiff advertisement, I was, for those days, reasonably experienced as a programmer and I thus had the confidence to apply for the job at Cardiff. As it turned out there wasn't very much competition and I began my adult employment in October 1970.
Within a term it began to look as though I had made a great mistake. Cardiff itself was a pleasant enough city, my teaching duties were not especially onerous, and I enjoyed the challenge of learning new subjects. However my research agenda had been to form a collaboration with McLain and scale the heights of the newly emerging computational group theory. This had started promisingly enough and I had invented an algorithm that became widely used in that community. But towards the end of my first term in Cardiff, McLain announced that he was leaving and my ambitions suffered a severe setback.
For a few days I wondered whether I should seek my fortunes back in some mathematics department although quite how was unclear. However I soon learnt that McLain's successor was to be Robert Churchhouse a number theorist from the Atlas Computing Laboratory. Bob was charged with the job of founding an academic computing department at Cardiff and he was determined that its research speciality should be the application of computers to mathematics, pure mathematics especially. So, at the beginning of 1971, I became a member of the new department of Computing Mathematics together with one other lecturer and Bob as professor.
The department began to construct a degree programme and so, for the first few years, my academic life was in two compartments: learning the standard fare of a 1970s degree in computer science and preparing lectures for it, and researching in algebra. I realised that I was lucky to have a boss who was sympathetic to pure mathematical research but regretted that I did not have colleagues with whom I could discuss my work. The teaching side was certainly a challenge. I was keen to be involved in the parts of the curriculum that were closest to mathematics and so I diligently studied the new algorithms that had appeared in the 1960s for automatic parsing of computer programs (and thereby learnt about the theory of compiler construction) and into automata theory (just at about the same time that the famous P=NP conjecture was being formulated). I taught literally dozens of course on compilers in my time at Cardiff but, sadly, teaching automata theory had to wait for the next decade.
In research it was obvious that varieties of groups were not approachable by computer means and so, thanking the time I had spent as a doctoral student learning more widely, I turned to permutation groups. At the time permutation groups were very topical in computational group theory and it was not long before I hit upon a little niche in the theory of doubly transitive but not doubly primitive groups. I found this first of all in an influential paper of Sims on computing with permutation groups but the investigations soon took me far away from computational considerations.
By 1975 (and after a very enjoyable sabbatical leave at McGill University) the steam began to run out of my permutation group research and I searched for new areas. Cardiff was not the hotbed of research that Oxford had been but it nevertheless offered several opportunities for learning new topics. Jim Wiegold's group in the Pure Mathematics department was quite active and there were many seminars by Jim, John Lennox and Chris Houghton. While I enjoyed these they did not really give me an entrée into a new area and so I began to sit in on honours and graduate level lecture courses. From Frank Dunstan and John Reynolds in the Statistics department I learnt basic statistics and probability theory (amazingly not the standard fare it is nowadays in mathematics degrees), stochastic processes and operational research. Again, I found these very interesting but couldn't think how to relate them to my previous research expertise. Luckily there was another course which I attended - one on computer algorithms and given by Nelson Stephens - and that set me going on a research area that lasted almost 10 years.
Nelson Stephens was a number theorist who had been attracted to Cardiff in 1973 by Bob Churchhouse. He was a former student of Bryan Birch who had taught me number theory at Oxford and, on my return from McGill, Nelson and I quickly became good friends. In 1975 he gave a series of lectures to our Masters students, largely working through some of the chapters of a recently published book that presented some new algorithms that went far beyond the classical numerical analysis algorithms I had previously known. Two topics in particular from those lectures were to influence my research very much. The first was the fast algorithm for computing the finite Fourier transform. I recognised that this was the cyclic group specialisation of a more general transform valid for any group and found some fast algorithms for this general transform in special cases. Later I realised that I had not been the first to have some of these insights but my paper attracted some attention nevertheless. The second topic was the ingenious algorithm of Volker Strassen to multiply two matrices in fewer steps than had previously been possible. It seemed to me then that matrix multiplication (which was known to be connected to many other linear algebraic problems, and some problems beyond this area) was the problem of the decade.
My idea for attacking the matrix multiplication problem was to try to embed it as part of group algebra multiplication and use the ideas I had had for the fast Fourier transform. This ultimately failed (Jim Eves at Newcastle revived the idea about 30 years later, also unsuccessfully). But my investigations led me to study families of bilinear forms, a setting in which matrix multiplication could be presented. This was a much more fruitful area and together with Nelson (and later my research student Sherrianne Lloyd) I produced a stream of papers. This established a small reputation for me, sufficient to be invited to work with Strassen himself (an invitation I had to decline).
This work was definitely within theoretical Computer Science but it soon led to work that wasn't - just as my work in computational group theory had led away from computational problems to pure mathematics. Indeed, this morphing of research from computer science to pure mathematics has been a recurring theme of my career and I count myself lucky that none of my employers have objected to this. This time it led to linear algebra (because bilinear forms can be represented as matrices). The problem that arose quite naturally from the computation of bilinear forms was to classify vector spaces of matrices where every matrix had bounded rank. This led to several years of great fun lasting into my early years at Carleton. I still regard this work as among my best even if it has not been so widely cited.
After a decade at Cardiff I was becoming frustrated at my career prospects. In those days there was a quota on the proportion of staff that could be in promoted positions and, to my jaded eyes, it seemed that promotions were being made according to age. In 1982 therefore I moved to Canada, to the newly created School of Computer Science at Carleton University in Ottawa. I knew Carleton well from a 9 month sabbatical in 1981 and was well aware how different the environment was going to be. Ottawa was known as the “Silicon Valley of the North” because of its many hi-tech companies. Skilled computer professionals were in high demand and consequently we had many very talented students. Larger classes, and a more rigorous curriculum than at Cardiff, created a much more demanding teaching schedule and I found myself working harder than at almost any time in my life. However the rewards were great: salaries were more than double UK academic salaries, I was promoted to full professor in 1983, and NSERC operating grants were giving me more money than my limited theoretician's spending power could accommodate.
In the first few years there my research was still fueled by the linear algebra projects I had brought from Cardiff. These in themselves perhaps would not have been much appreciated by my new computer science colleagues and I was lucky that one of them grew into a problem that I could claim was properly computational. The problem that I solved was to determine, by a provably optimal algorithm, whether two sets of points in 3-dimensional space were congruent (in the good old Euclidean geometry sense). My paper on this algorithm was much less deep than most of the things I had published previously but, coming in the early days of Computational Geometry and Computer Graphics, it had much more impact. However, once this paper was written I was once again casting around for new problems and new areas and in 1984 I once again had a slice of luck.
The two colleagues in Computer Science who I related to most were Nicola Santoro and Jörg Sack. They could hardly have been more different: Nicola a laissez-faire Italian, Jörg an ambitious German. I was to work with them on many different topics. In early 1984 they and their visitor Thomas Strothotte outlined to me a new data structure (now called a min-max heap) that generalised the heap structure to allow it to represent double-ended priority queues. The original idea had been Nicola's but Jörg and Thomas had worked with him to iron out bugs. I was very taken with their ideas and was soon able to suggest a related structure that also allowed medians to be computed efficiently. Our paper on the topic has become my most highly cited paper.
In the course of trying to pin down exactly how close our min-max heap algorithms were to optimal I had become aware that counting the linear extensions of a related poset was important. This insight didn't help for the min-max heap problem but it did get me interested in algorithms to count linear extensions in general. For the rest of my time at Carleton this allowed me to publish a number of rather slight papers on this and closely related problems. By and large my decade at Carleton produced many more papers than my decade in Cardiff but they were much shallower . Partly this was because of the “publish or perish” pressures caused by the crude measures that funding bodies have to use when allocating grants but, in my case, I think there was another reason. As the years were going by I was becoming more and more removed from my Oxford and early Cardiff days when it was possible to study research areas at very great depth. Indeed it would hardly be possible to do significant research in algebra without a huge technical knowledge of what previous scholars had amassed over a century or more. My research had been moving steadily away from this long historical tradition into newer areas where problems could be posed and solved without needing much prior technical knowledge.
I regretted this drift away from the ancient roots of mathematics towards shallower more topical problems. This regret was compounded through my not having direct contact with the academic mathematical community because I worked in a computer science department; and, in particular, I was sorry that I couldn't teach algebra, number theory, or any of the flagship subjects of pure mathematics. Nevertheless research was continuing to bring much personal satisfaction, particularly when it offered opportunities to dip a little into classical mathematics.
One such opportunity was offered to me by Nicola Santoro and Jorge Urrutia (from the University of Ottawa). They had stumbled upon a problem raised by radio engineers trying to allocate radio stations within a limited spectrum. The mathematical formulation of the problem was find sets of integers all of whose pairwise differences were distinct. They had some preliminary ideas and I was delighted when I discovered that finite projective planes offered very much superior solutions.
However, a far more exciting project which eventually brought me right back to the algebra and representation theory of my doctoral days arose directly from my shallow work on linear extensions. There is a collection of posets defined by sequences in which each term is in some fixed relation (greater or less than) to the next. Their sets of linear extensions form an algebra in a remarkable way, still so astounding to me that I bring it to the attention of any mathematical acquaintance who may not know it. This algebra had first of all been discovered by Louis Solomon in the 1970s but he had written in such a style that the result was not noticed by researchers beyond his field. Indeed, so unnoticed was the paper that a number of special cases were subsequently proved and published in the 1980s. My first contribution to this topic was to reprove Solomon's theorem in a more direct way bringing out (or so it seems to me) the remarkable nature of the result. On my sabbatical in 1998/89 in Oxford, working once again with Peter Neumann, I proved some results about the representation theory of Solomon's algebra. I still find it bizarre that there was such a connection from data structures, via posets, to a structure that, in its most general form, concerns root systems of Coxeter groups.
Descent algebras require a group theorist to visualise permutations somewhat differently to how they appear in permutation group theory: as sequences rather than as mappings. In the later part of the 1980s I had gradually become more familiar with this sequential viewpoint, learning about some of the beautiful results discovered by 19th century combinatorialists. One highpoint of this old work was a wonderful theorem of André which connects so-called up-down permutations to the trigonometric sec and tan functions. I reproved this theorem and thereby found a very easy way to compute the coefficients in the Taylor expansions of sec x and tan x.
Considerations such as this eventually reminded me about a result I'd seen in the books of Donald Knuth – about the permutations that could be sorted by a stack – and so one day in early 1992 I began to play around with permutations and priority queues. After a few hours of calculation I had counted the number of permutation pairs of length 4 that could be the input and output from a priority queue. There were 125. Idly I wondered whether this could be a special case of the formula (n+1)n-1. This was very thin evidence on which to speculate but a little more calculation revealed that the formula seemed to hold for n=1,2,3,4. Armed with this evidence I proved it in general a few days later.
This very lucky event proved to be enormously influential for it eventually led me to the area of permutation patterns that has been my main research area for the remainder of my research life. The journey was not immediate. To begin with I explored a number of related results about priority queues. This reinforced for me the ideas that Knuth had originated about permutation containment. These ideas had largely been unknown to the combinatorial community and it now seemed to me that permutation containment would support a host of questions that generalised the ones originally posed by Knuth.
A few months after this I moved to St Andrews. I knew exactly what I wanted to research: the application of permutation containment ideas to data types. Among my new colleagues there were none with the theoretical bent of Nelson, Jörg and Nicola but I had been given some start-up money and with it I hired Louise Walker as research assistant. Louise was a group theorist but was prepared to come to grips with my new problems and we made considerable progress – enough that when I acquired a research student, Dominic Tulley, I felt confident enough of the area's potential to set him to work on it. Louise left in 1996 and Dominic completed in 1997 but by then I felt the area was becoming very rich and that it was time to begin developing a more formal framework rather than continuing to solve special problems.
I had had limited success in interesting the computer scientists at St Andrews in my work and so in 1998 and again in 1999 I gave some lectures to the local pure mathematicians on my results. In the audience was a young mathematician called Nik Ruskǔc. Nik was a brilliant and energetic Serbian who had arrived in St Andrews at more or less the same time as me and had greatly contributed to the research of the algebra group. By 1998 he had begun his swift ascent up the career ladder of St Andrews academia and was apparently looking for some new research areas. He and his new research student Max Murphy were very taken with one of the problems I had presented - to do with the permutations that could be sorted by two stacks in series - and together we managed to solve it. Max subsequently went on to write a brilliant thesis in which he presented many ideas that foreshadowed later results of other people. But for me the major benefit was getting to know Nik as a person and as a mathematician.
Nik is not the mathematical stereotype - a reclusive awkward genius with time only for his equations. He is warm, family-oriented, has a marvellous sense of humour and on top of all of those personal qualities his mathematical enthusiasm knows no bounds. He has inspired a generation of students and young colleagues at St Andrews and become my closest friend. It was only just in time that I came to know him well for in early 2000 I left St Andrews for Otago University in New Zealand. In the years that followed Nik visited many times, sometimes with his family, and we developed a close mathematical relationship along with our close friendship.
Otago was a very different place to St Andrews but I loved the New Zealand countryside and the uncrowded streets of Dunedin. I knew that I would have to work hard to develop a mathematical presence for I was now in a Computer Science department with no other refugee mathematicians as colleagues. I therefore made contacts with the pure mathematicians led by Derek Holton and formed a small Theory of Computing Research Group. Although we had occasional computer science members the core of the group was myself, Derek, Robert Aldred and Michael Albert. I began to teach them my ideas about permutation patterns and found them very ready to listen. By far the most energetic of my new colleagues was Michael Albert.
Michael is a Canadian, a Waterloo graduate and former Rhodes scholar. He had worked at Carnegie-Mellon for several years and then, through no fault of his own, landed up at Otago as a teaching fellow in Mathematics, a position for which he was absurdly over-qualified. Towards the end of my first semester at Otago I was delighted to seize the chance to have him appointed to a lectureship in Computer Science and, within a few years, he rose to become Associate Professor. In my endeavours to raise the international profile of my research area Michael was a superb lieutenant. Together we organised the first International Conference on Permutation Patterns, wrote many papers together, and developed a network of colleagues many of whom visited us over the years.
Increasingly since the mid 1980s I had begun to move away from the singly-authored paper model that had been the norm for mathematicians of my generation and nowadays I rarely write without at least one co-author. Partly this change is because my personal energies and mathematical abilities have lessened as I aged but that is not the whole story.
Since the early 1980's universities have taken research more and more seriously and there are significant career penalties for those who cleave to the old model of the disinterested scholar, content to think mathematics purely for his own intellectual satisfaction. The pressure to form research collaborations and to publish prolificly is very real. Many of my colleagues regret the passing of those gentler days but my own view has always been that we must recognise that we suck upon the public purse and for that a price has justly to be paid. When I began my academic career there were still members of university departments who remembered (and fondly recalled) a university system where a tiny minority only could go to university. But after the second world war and throughout the 1960s, 1970s and 1980s the tertiary education sector went through massive expansion. Most of us now working in the system owe our jobs to this expansion: it is just too naive to think that we should be able to behave as though we were characters in a C P Snow novel about 1930s Cambridge University.
I have no doubt that much mathematics published nowadays would not have been considered deserving of publication 40 years ago but that does not mean that it should not be published today. We are working in a much bigger academic environment and those whose research contribution is minor are nevertheless playing an important role in supporting the whole enterprise.
Mirroring this change in how research is conducted is an arguably more important companion change: the much greater numbers of students who graduate every year – approaching around half of all young people. To say, as Kingsley Amis apparently said, “More means worse” misses the point. Universities are now a social resource, funded by enlightened states, to raise the education and skill levels of the voters in their societies. We do not any longer educate our students to become only the next captains of our industries, civil service, and research laboratories. Nowadays our remit is much wider:- to give our students knowledge, thinking skills and communication skills so that they can play their parts in our societies to their fullest potential.
Around the beginning of 2007 I went through a low personal period after which I never properly regained the zest I had always previously had for mathematics. I was still publishing at about the same rate but I knew that my abilities to lead my colleagues was declining. In my collaborative work I had always been the partner who posed the problem at hand and I had almost always solved the lion's share of it. I did not become a passenger in research teams but I no longer played the leading role. Mathematics has a reputation for being a young person's subject and there are many professional mathematicians whose research career finishes in their middle years. I had certainly been lucky in being able to carry on productively for so long but I recognised that my research life was coming to an end. In 2010 I took the decision to begin a phased retirement and at the end of 2012 I retired permanently.