The history of computing

Today, the School of Computer Science at St Andrews put on this year’s Distinguished Lectures. The lecturer was Ursula Martin, and she spoke about the history of computing, or more precisely, “What every computer scientist should know about computer history”.

The lectures were held in the Byre Theatre, the third one in the presence of the Principal, Professor Sally Mapstone, herself a historian. It seems they were compulsory for undergraduates on certain courses; the auditorium was packed, with very few spare seats, despite the fact that relatively few staff from either Computer Science or Maths and Stats were there.

But I want to talk about the contents of the lectures, not the surroundings.

There were three lectures. The first two focussed on important people in the story, Charles Babbage and Ada Lovelace, Alan Turing and Grace Hopper. The third tackled two more nebulous topics: why did Ada Lovelace’s mathematical abilities polarise later commentators to the extent they did, and what happened to the women who were in Britain’s computing business in its early days?

The introductory slide was a “timeline of computing”; Ursula invited us to consider what was missing from it. As she said, the development of computing was certainly not a single and inevitable strand. For example, about the time that Tim Berners-Lee was inventing the World Wide Web, there was a possible rival called Gopher developed at the University of Minnesota. It lost out partly because the University took a hard line on intellectual property rights. But things might have been different …

Charles Babbage and Ada Lovelace

We began with a picture of the Great Exhibition of 1851, the profits of which still fund doctoral and postdoctoral positions. At the time, Britain was the hub of a vast empire. Running an empire requires mathematics, and a lot of calculation, much of which was done using log tables. Babbage wanted to make log tables “as cheap as potatoes”.

So he designed the Difference Engine Number 2, which used 31-digit numbers, and could compute 7th order differences (that is, fit degree 6 polynomials). His description of the Engine amounted to the invention of a hardware description language (in modern terms). He also proposed an Analytical Engine; it never got off the drawing board (or was even completely designed), but it was intended to be a general purpose computer (in the modern sense); it even conformed to von Neumann architecture (a single CPU, instructions and data fetched from memory). It was to be programmed using punched cards, an idea borrowed from weaving.

As is well known, Ada Lovelace wrote a 70-page paper which described how the Analytical Engine would work. Ursula showed us detailed diagrams of how it would solve two simultaneous linear equations, and (more difficult) how it would compute Bernoulli numbers using the recurrence relation (which she derived from the usual formula).

The program solving simultaneous linear equations reminded me very strongly of assembly language programming. You have to choose the register to store every intermediate result. High-level languages free us from those details!

Lovelace and Babbage (especially the former) also speculated more philosophically on the capabilities of the Engine. In Lovelace’s words, “the cards are able to reproduce all the operations which intellect performs in order to attain a determinate result”. On a generous interpretation, this says it can compute anything which can be computed, an idea taken up by Turing.

They also speculated on using the Engine to process non-numerical data. In this connection, Ursula showed us a page from the archives on which Babbage and Lovelace had been doodling about the Königsberg bridges and magic squares. These are two topics associated with Euler. In my mathematical quotes, you will find part of a letter Euler wrote to Carl Ehler, mayor of Danzig, on the Königsberg bridges, denying that this is mathematics (and, by extension, denying that topology is mathematics). So this is conceivably a case in point. I don’t know if there is any information on how the diagram of the bridges would be input to the Engine and what algorithm it would use to solve it. Probably they hadn’t got that far.

Lovelace also says “The machine can do whatever we know how to order it to perform”. In other words, it cannot be creative. Ursula thought this might have been her adopting a safe position in the theological arguments of the time.

In a curious footnote, a slightly cut-down version of the Difference Engine was built by the Swede Per Georg Scheutz, who even sold one to the British government.

Alan Turing and Grace Hopper

Turing quoted Lovelace’s remark about “all operations which intellect performs”. Unlike her, he argued that a human philosopher can do no more than this, and so a machine is just as capable of thinking as a human.

Turing also proposed getting the computer to correct and avoid bugs in a program, a precursor to Tony Hoare’s logic of computation.

Incidentally, it is claimed that Grace Hopper found the first bug; Ursula showed us the entry in the log saying “Moth in relay”.

Turing had a page in the manual of the Manchester computer devoted to getting the computer to play music, later realised (with Christopher Strachey) in a performance of “God save the Queen” and “In the Mood” (shockingly out of tune) which was broadcast on the BBC in the 1950s. Strachey also programmed it to write love poetry; we saw his doodle of a flowchart for this program.

Grace Hopper did far more than find the first bug. She wrote the first compiler, and designed the business computing language COBOL. More importantly, she realised (as the makers of the Manchester computer did not) that, in order to get businessmen to use computers, you had to do away with symbols, exponents and subscripts, and explain everything in clear plain words.

Other topics

In order to put the timeline of computing in its place, Ursula gave us a timeline of computing in India. The first computer in India was installed in 1955 (before the first computer in Scotland), and the first computer designed and built in India began operating in 1960.

She also showed us some events in the development of the Internet, to show that it was far from a single line of development; there were many other networks around at the time of ARPANET.

But the main focus of the third lecture was on two topics. First was Ada Lovelace’s mathematical education and ability. Apart from an early tutor who told her that the only way to be a mathematician was to memorise everything in the book, her real tutor was Augustus De Morgan, who had a clear idea of her abilities. He described it in terms of a young man with comparable abilities, since a woman could not study at Cambridge in those days. Such a person would never be Senior Wrangler (essentially, succeed in a problem-solving competition), but his grasp of the overall structure could lead to his becoming a very successful research mathematician.

But this comment was seriously misunderstood by later historians, even when they quoted it verbatim, as saying that Lovelace was too bogged down in details to succeed. People who should have known better claimed that she could not have understood what was written in her 70-page paper on the Analytical Engine. Her analysis of the Bernoulli numbers showed that she was no slouch as a mathematician.

A nice story concerns how she got the better of the tutor who had told her to memorise the contents of the book. After studying Pythagoras’ Theorem, she asked him how you would prove a similar theorem in which squares on the sides of the right-angled triangle are replaced by equilateral triangles. He hadn’t the faintest idea; it was not in the book! As Ursula says, either you see this as being very difficult, or you think it is quite simple.

Then she turned to the many women who had been important in the early days of British computing, who are now essentially unknown, written out of the script either by corporate policy (as in the case of the Civil Service, which had separate men’s and women’s career scales in those days) or by individual blindness. She showed us a web page showing the first professor of computing (named) at a university which I won’t name and shame, in front of the university’s new computer (named). There is also a woman sitting at the console, who was not even mentioned in the picture caption. At Ursula’s urging, her name was discovered (not so difficult, in fact) and added to the caption.

Conclusion

Ursula gave us two reasons for studying history:

  • understanding the past helps us grasp the present and think about the future (for example, the problems we are now facing may have arisen before);
  • the stories we tell (or don’t) shape who we are, what we do, and how we are seen.

The web page for the Distinguished Lectures Series is here. I do not know how to find the slides or the reading list. This material may be restricted to students.

Advertisements
Posted in events, history | Tagged , , , , | 3 Comments

Synchronization and all that, 2

The story I told in the last post is not over.

The recent development is that we spotted a mistake in the paper. An easy mistake to make: we had simply used the symbol n in two different places with different meanings, and then proceeded to get them confused.

The fix required arguments considerably longer than the ones we had given. The fact that we were able to fix the proof reasonably quickly shows the power of Delsarte’s ideas for studying association schemes. His thesis (published in the Philips Research Reports in 1973) is the foundation for much subsequent work in both coding theory and combinatorial design theory.

Anyway, in the course of this fix, we discovered that we had left out an example. This doesn’t affect our conjectures, which are asymptotic: they assert that, for fixed k, for large enough n,the symmetric group of degree n acting on k-sets is non-separating if and only if a Steiner system S(t,k,n) exists for some t with 0 < t < n.

The main change is that, for k = 4, “large enough” should mean “at least 10” rather than “at least 9”.

The reason is as follows. Consider the graph whose vertices are the 4-subsets of {1,…,9}, two vertices joined if they intersect in 1 or 3 points. Then the clique number and the chromatic number of this graph are both equal to 9; and hence S9 acting on the 135 vertices of the graph is non-synchronizing (as explained in the preceding post).

I leave as an exercise the proof that the graph has clique number 9. (Your job is to find nine subsets of {1,…9}, each of size 4, and having the property that any two meet in 1 or 3 points.)

The fact that the chromatic number is 9 was proved (in different language) by Breach and Street in 1988. They showed that the 4-subsets of a 9-set can be partitioned into 9 copies of the Steiner system S(3,4,8), each omitting one of the nine points. (They called such a configuration an “overlarge set” of Steiner systems, as opposed to a “large set”, where each Steiner system uses all of the points.)

Their proof, as I recall, was in part computational. But a couple of years later, Cheryl Praeger and I were able to give a conceptual proof, based on the remarkable geometric concept of triality, specifically over the field of 2 elements. Here is a brief summary. I restrict to the 2-element field, though much of this works for an arbitrary field.

Consider the quadratic form

x1x2+x3x4+x5x6+x7x8.

It defines a quadric consisting of 135 points of the 7-dimensional projective space over GF(2). The maximal subspaces contained in this quadric are “solids” (3-dimensional subspaces), and fall into two families, where two solids are in the same family if they intersect in a line or are disjoint, and in different families if they intersect in a plane or a point. There are 135 planes in each family. Also there are 1575 lines on the quadric.

Consider the quadric as an incidence structure, where the incidence between points, lines, and solids is inclusion, and two solids are incident if they intersect in a plane. (We regard incidence as a symmetric relation, so that a line is incident with a point if and only if the point is incident with the line.) It turns out that this structure has some additional, unexpected symmetries: we can permute cyclically the sets of points, solids in the first family, and solids in the second family, while preserving the family of lines and the incidence relation. This symmetry is the “triality” map on the quadric.

Now here is a concrete realisation of the quadric. As our 8-dimensional vector space V, we take all the binary words of length 9 with even weight. (These are the words orthogonal to the all-1 word with respect to the usual inner product, so they do form a subspace.) Now it can be shown that the function mapping v to half the weight of v mod 2 (that is, words of weight 0, 4 and 8 map to 0, words of weight 2 and 6 map to 1, in GF(2)) is a quadratic form on V, equivalent under linear transformation to the one given above. The quadric consists of the (9 choose 4)+(9 choose 8)=135 wordds of weight 4 or 8. The 9 words of weight 8 form an ovoid on the quadric, a maximal set of points with no pair lying on a line of the quadric. (The third point on the line joining two points of weight 8 has weight 2.) The stabiliser of the ovoid is the symmetric group S9, so by counting we find that there are 960 ovoids.

Applying the triality map turns an ovoid into a spread, a set of 9 pairwise disjoint solids (necessarily all from the same family) covering each point of the quadric.

Now what does a solid look like in our interpretation? It is a 4-dimensional vector subspace of V, all of whose elements have weight 4 or 8 (since it is contained in the quadric). It is easy to see that such a subspace must consist of the zero vector, a word of weight 8, and 14 words of weight 4 forming the blocks of a S(3,4,8) on the support of the word of weight 8. So each of the 9 solids in a spread contains one of the nine words of weight 8 and 14 of the 126 words of weight 4, and we have our large set of Steiner systems.

Now the classification up to isomorphism is found by writing down two beautiful examples (each with a doubly transitive automorphism group), counting how many copies of each there are (the index of its automorphism group in the symmetric group), and checking that these numbers add up to 1920 (the number of images of ovoids under the triality map and its inverse).

This was presented at the 1988 Italian combinatorics conference in the beautiful town of Ravello, and published in the conference proceedings. The publisher was a small outfit called the Mediterranean Press. I believe I heard a rumour that they were no longer in business. So, with Cheryl’s agreement, I have posted a scan of the paper here. (The paper by Breach and Street is in the Journal of Combinatorial Mathematics and Combinatorial Computing in 1988.)

A final note: this paper is also referred to in my notes On doing geometry in CAYLEY.

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

EKR, Steiner systems, association schemes, and all that

A great number of mathematical problems amount to looking in a large but highly structured graph, and finding a complete or null subgraph of largest possible size there.

For a simple example, consider Latin squares of order n. One of these is an n×n array containing the entries 1,2,…,n, arranged in such a way that the entries in any row or any column are all distinct. So each row is a permutation of the numbers 1,2,…,n (in the nineteenth-century sense, that is, an arrangement of these numbers rather than the operation of rearranging them), and any two of the n permutations defined by all of the rows disagree in all positions. Thus, if we make a graph whose vertices are the permutations, two vertices joined if they agree in at least one position, then a Latin square is the vertex set of a null subgraph of maximum size.

I propose to speak about a class of graphs which includes some which give a context, in this way, to two big theorems of combinatorial mathematics: the construction of Steiner systems, and the Erdős–Ko–Rado theorem. Considering the whole class of graphs leads us to a conjecture which would extend (in some sense) both of these big results.

I’ll conclude with an even more general context for this, the theory of association schemes.

Steiner systems

The Lady’s and Gentleman’s Diary in 1844 published a problem which proved too difficult for its readers, and indeed was not solved for more than a century and a half. The problem was posed by the Editor, Wesley Woolhouse, and ran as follows:

Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them, shall be repeated in any other.

We assume that q < p < n to make things interesting. But for my purposes later on, I will change notation, and use k and t instead of p and q.

There is an upper bound, C(n,t)/C(k,t), where C denotes the binomial coefficient. For the numerator is the number of subsets of size t; in a collection of combinations satisfying the problem, each combination contains C(k,t) of them, and there is no overlap. But, without giving a construction, it is not clear whether this upper bound can be attained (and indeed it cannot always be).

In the next issue, he specialised to the case k = 3, t = 2; that is, we are looking for a collection of 3-element subsets of {1,2,…,n}, with the property that no two meet in more than one point. In terms of our original formulation, if we make a graph whose vertices are the 3-element subsets, two subsets joined if they meet in two points, we are looking for the largest null subgraph of such a graph. The upper bound mentioned above reduces to n(n−1)/6, and it is easy to show that it cannot be attained unless n is congruent to 1 or 3 (mod 6). [This is an instance of what I shall call the divisibility conditions.] Thomas Penyngton Kirkman, rector of Croft in Lancashire, gave a proof that, if this is satisfied, then a set of n(n−1)/6 triples with the required property can be found. In such a system, any two points are contained in exactly one of the distinguished triples.

Such configurations are now called Steiner triple systems, even though Steiner didn’t pose the problem of their existence until six years after Kirkman had solved it! An article by Norman Biggs and Robin Wilson in Combinatorics: Ancient and Modern (Oxford University Press 2013) untangles some of the history.

Kirkman clearly found that his job as a clergyman didn’t use all his energy; as well as this, he worked on group theory, knot theory, and polyhedra, and was elected Fellow of the Royal Society in 1857.

In general, a configuration meeting the bound in Woolhouse’s original problem is called a Steiner system, and denoted by S(t,k,n). In the years from 1847 to 2014, a number of specific examples were found, none having t larger than 5. (Examples of S(5,6,12) and S(5,8,24) were found in the first half of the twentieth century; they are associated with the sporadic simple groups found by Émile Mathieu.) Then in 2014, Peter Keevash announced a proof that, for any k and t, if n satisfies the relevant divisibility conditions and n is “sufficiently large” (in terms of k and t), then a Steiner system S(t,k,n) exists.

Since Keevash’s work, at least one further proof has been given. But nobody knows exactly how large n has to be (except in special cases).

The Erdős–Ko–Rado Theorem

A collection of k-element subsets of a set of n points is called an intersecting family if any two of its members have a point in common. More generally, it is tintersecting if any two of its members have at least t points in common.

The question, What is the largest t-intersecting family of k-subsets of an n-set?, was tackled by Paul Erdős, Chao Ko, and Richard Rado in 1938. To understand what they did, first consider how you can obtain a large family. If we fix an element of the n-set, say 1, and take all the k subsets which contain 1, then clearly we get an intersecting family of size C(n−1,k−1). Indeed, if we choose all the subsets containing all of 1,2,…,t, we obtain a t-intersecting family of size C(nt,kt).

EKR, as I shall call them, showed that, provided n is sufficiently large (in terms of k and t), we cannot do better. Indeed, for intersecting families, this bound holds as long as n > 2k; and, if n > 2k+1, then the only families attaining the bound are those consisting of all the k-sets containing some fixed element.

Although this theorem was proved in 1938, it was not published until 1961. Paul Erdős said subsequently,

One of the reasons for the delay was that at the time there was relatively little interest in combinatorics. Also in 1938, Ko returned to China, I went to Princeton, and Rado stayed in England.

This result can also be put into our general framework. As we did before, form the graph whose vertices are the k-subsets of our n-set, two vertices joined if they have at least t points in common. We saw that Steiner systems come from null subgraphs of largest possible size; EKR families are complete subgraphs of largest possible size.

Comparison

However, there is an interesting contrast. In the case of Steiner systems, the bound is easy to establish, but a very complicated construction is required to build systems meeting the bound. In the EKR case, construction of the large systems is easy, but the proof that no larger family is possible is what requires the work!

Another thing to notice is that the product of the two bounds is

C(nt,ktC(n,t)/C(k,t) = C(n,k)

(a short exercise with binomial coefficients). The right hand side is the number of vertices of the graph. This reminds us of a property which symmetric graphs have:

If a graph on n vertices has automorphism group acting transitively on the vertices, then the product of the sizes of the largest complete and null subgraphs does not exceed the number of vertices of the graph.

This is a slightly more difficult exercise; it uses double counting, and two facts:

  • if a group G acts transitively on n points, then the number of elements of G mapping x to y is |G|/n (a consequence of Lagrange’s Theorem;
  • a complete and a null subgraph cannot have more than one vertex in common.

Now the graph in our example has C(n,k) vertices, and the symmetric group Sn acts transitively on the vertex set. This goes some way to “explaining” the relation between the two bounds, and also suggests that algebra has some part to play here.

(This is a small plug for a new book, Erdős–Ko–Rado Theorems: Algebraic Approaches, by Chris Godsil and Karen Meagher, recently published in the Cambridge Advanced Mathematics series.)

Thus Keevash’s Theorem says that, for this graph, if n is sufficiently large in terms of k and t, then the product of the sizes of the largest complete and null subgraphs of the graph is equal to the number of vertices if and only if the divisibility conditions are satisfied.

Generalisation

We can define a more general class of graphs whose vertices are the k-subsets of an n-set. All these graphs have the property that adjacency of vertices depends only on the size of the intersection of the subsets, and all of them admit the symmetric group acting vertex-transitively.

Let I be a subset of {0,1,…k−1}. We form a graph GI on the vertex set by letting two subsets be declared adjacent if the size of their intersection is an element of the set I. In the case where I = ∅ or I = {0,1,…k−1}, the graph GI is the null graph or the complete graph, respectively; we ignore these cases. Also we note that if I and J are complementary subsets of {0,1,…k−1}, then the graphs GI and GJ are complements of each other (the edges of one are the non-edges of the other). So we have (2k−2)/2 = 2k−1−1 complementary pairs of “interesting” graphs.

Among these graphs, those for which I = {t,…k−1} play a special role, as we have seen; the largest possible null subgraphs of these are Steiner systems, and the largest possible complete subgraphs are EKR families. Thanks to the theorems of EKR and Keevash, we know that, for n sufficiently large, the product of the sizes of the largest complete and null subgraphs in these graphs is equal to the number of vertices.

Here is the big conjecture, which appears in a paper of mine with Mohammed Aljohani and John Bamberg, accepted for publication in Portugaliae Mathematica in the last week of September this year:

There is a function F on the natural numbers such that, given k and n, if n ≥ F(k) and the graph GI defined above has the property that the product of the sizes of the largest complete and null subgraphs is equal to the number of vertices, then I or its complement is equal to {t,…k−1} for some value of t, and the divisibility conditions for a Steiner system S(t,k,n) are satisfied.

This was previously known for k = 2 and k = 3; in the paper, among other things, we prove it for k = 4, by a method which seems likely to generalise to larger values. Unfortunately, of course, the number of graphs we have to consider grows exponentially with k, as we saw.

The graph GI has the property that its edge set is the disjoint union of the edge sets of the graphs G{i} for i ∈ I. These graphs make up an association scheme. This means that their adjacency matrices commute and that their span over the real numbers is an algebra (that is, closed under multiplication).

Association schemes are very interesting combinatorial objects, with applications in group theory, computation, statistics, and elsewhere. But I will forbear to describe them further here, except to note that they provide a context for the problems described here, and asking similar questions in other association schemes leads to challenging research problems. Indeed, there are a number of inequalities for the sizes of complete and null subgraphs in terms of the eigenvalues of the matrices in the association scheme; and there are ways of computing these eigenvalues from counting information about the association scheme. In particular, the result that says that the product of complete and null graph sizes in any union of graphs in the association scheme is at most the number of points, irrespective if the scheme has any symmetry or not: transitivity on vertices is not necessary in this case.

An example

Although we conjecture that things are orderly when n is large, there are many fascinating examples not following this pattern for smaller n. Here is an example.

The Fano plane

The picture shows the famous Fano plane: seven points with seven 3-subsets, any two meeting in exactly one point. So it is a Steiner triple system S(2,3,7) (whose triples are called lines), and is also a complete subgraph of G{1}. Our general inequality that the product of complete and null subgraph sizes is at most the number of points shows that a null subgraph of G{1} has size at most 5.

There are null subgraphs of size 5: the EKR sets (all triples containing two given points give examples). But there are others with a completely different structures. Consider, for example, any line of the Fano plane together with the four 3-sets disjoint from it. Any two of these five sets meet in 0 or 2 points. (In the picture, 135, 137, 157, 357 and 246 is an example.)

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

Carnival of Mathematics

The Carnival of Mathematics, a monthly blogging round-up, will be hosted on the CoDiMa site in October. (It travels round various mathematics blogs but is coordinated by Katie at The Aperiodical.)

My contribution to the carnival is a piece called “EKR, Steiner systems, association schemes, and all that”, which will be posted here shortly.

Posted in events, the Web | Tagged , | Leave a comment

Remarkable forgeries?

In my pigeonhole at Queen Mary recently, I found an unsolicited copy of a book with the title Meetings with Remarkable Forgeries, by M. J. Harper. According to the cover blurb, it is a debunking of Christopher de Hamel’s Meetings with Remarkable Manuscripts, about which I said something here. Perhaps the publishers sent it to me because of my post about the earlier book.

In fact, it is not quite what the cover says. The blurb ends up by saying “The author has bigger fish he wants to fry”, and indeed on the first page of the text he mentions “my long-term goal of getting the universities abolished”, which hardly endears him to me. I must say that, on the strength of this book, universities needn’t start quaking in their boots just yet.

De Hamel describes twelve manuscripts, of which only two are claimed to be forgeries by Harper, the Gospels of St Augustine and the Book of Kells. In particular, the Leiden Aratea, on which I commented, doesn’t draw his fire, even though de Hamel describes its production by what might count as an earlier version (at the court of Charlemagne) of the production lines Harper regards as being responsible for forging other early manuscripts: he starts with an admission that mediaeval monks copied manuscripts, and while we find something wrong with this, they clearly did not. (Before the printing press, copying was essential to ensure wide circulation.) Indeed, it often happened that the copy was a finer manuscript than the original, in which case it appears they felt no compunction to carefully preserve the original.

Anyway, Harper claims that the two manuscripts I mentioned are both “forgeries”, produced in Durham in the twelfth century. He describes the Benedictine order as the “Thomas Cook of their day”, arranging itineraries for pilgrims, and as a profitable sideline, producing “ancient” manuscripts for the pilgrims to see on their journeys. He claims that Durham was an important centre of this manuscript production. The secular clergy of Durham cathedral were replaced by Benedictine monks in the twelfth century, and the Bishop of Durham ensured that he was master of the County Palatine, and that the Sheriff of Northumberland had no authority in Durham.

The other reason for the monks to forge “ancient” gospel books was to record the charters documenting their claim to various properties. Certainly, mediaeval monks transcribed legal documents of this sort into spare pages in gospel books. I used to have a lovely book on the history of Eynsham Abbey (alas, I can no longer find it) which describes such practices. Presumably something written in a gospel book was less likely to be challenged than if it was on a loose piece of vellum in the abbot’s study.

Harper claims that there is no archaeological evidence of early monasteries on either Iona or Holy Island. I have never been to Iona. It is true that there is nothing old to see on Holy Island. I am not sure what this proves. Harper’s claim is that St Cuthbert’s Gospels and the Lindisfarne Gospels could not have been produced there.

Another manuscript in his sights is the Llandeilo Gospels, claimed to be an ancient Welsh book, produced in Llandeilo, but according to Harper produced in another forgery factory, this time in Lichfield. He takes issue with the usual derivation of the name “Llandeilo” as the place of St Teilo, and instead interprets it as “an enclosure where dung was spread”.

The Wikipedia article for “llan” confirms that “[t]he various forms of the word are cognate with English land and lawn and presumably initially denoted a specially cleared and enclosed area of land.” But it adds, “In late antiquity, it came to be applied particularly to the sanctified land occupied by communities of Christian converts”, and goes on to add that nearly all of the 630 placenames in Wales containing this element “have some connection with a local patron saint.”

Perhaps Harper wants to close down Wikipedia as well as the universities?

Harper grumbles at the Welsh writing Llanfair for “St Mary’s parish” as being unable to spell the name of the second most important person in the world, but I believe that this is actually a correct translation. Welsh declines the beginning, rather than the end, of a word: Merthyr Mawr, but Fforest Fawr. I wonder what experts on mediaeval Welsh make of all this?

As befits one with such a hatred of scholars, his book has no table of contents and no bibliography. He quotes various things from other books, but with the exception of de Hamel’s book, he doesn’t tell us what these are. (Fortunately he does have an index, without which I would have had a much harder job writing this account.)

By way of light relief, here is a crossword clue which you should easily be able to solve:

Giggling troll follows Clancy, Larry, Billy and Peggy who howl, wrongly
disturbing a place in Wales (58)

Posted in history | Tagged , , , , | 1 Comment

Summer school at Marienheide

Summer school

Last week, I was lecturing at a summer school in Franz Dohrmann Haus, a very pleasant conference centre in the small town of Marienheide, not far from Köln. Apart from a walk on Wednesday afternoon, I didn’t get much exercise, and the food was excellent and plentiful (including fresh figs for breakfast), so I am sure I have come back a kilogram or two heavier. (Table tennis was available, but the students preferred to play bizarre card games, occasionally involving physical assaults of various kinds.)

There were various jobs I was hoping to do, but the wi-fi in the place was totally inadequate, so that it was impossible to upload or send anything bigger than a small textfile. This had the effect of keeping us focussed on the mathematics.

The topic of the summer school was permutation groups. The main speakers, apart from me, were Cheryl Praeger, Csaba Schneider, and Pablo Spiga. As you might expect, we were very much focussed on finite permutation groups, and in particular, on groups which were at least quasiprimitive but not 2-transitive; and the O’Nan–Scott Theorem played a big part in the proceedings.

Cheryl talked about quasiprimitive permutation groups. For example, she explained how, for s ≥ 2, a connected non-bipartite s-arc transitive graph has a quotient which is also s-arc transitive with the same valency, and its automorphism group is quasiprimitive on vertices. (This means that every non-identity normal subgroup is transitive. This condition is implied by primitivity, but is strictly weaker; for example, every transitive action of a simple group is quasiprimitive.)

Cheryl then described her extension of the O’Nan–Scott Theorem to quasiprimitive groups. Of the eight cases in Kovács’ version of the theorem, in several of them the group is necessarily primitive, and in most of the others the conclusions are almost identical with those in the usual version. The exception is the product action case, where the group may have an invariant partition so that it acts on the parts as a primitive group of product action type, but the intersction of the socle with the point stabiliser is a subdirect product (rather than a direct product) of factors coming from the base group.

Purely by chance, she was explaining the pioneering work of Tutte on arc-transitivity; I happened to be wearing a t-shirt with Adrian Bondy’s photo of Tutte on the back, so I stood up and exhibited it (to a round of applause).

Following this, she described progress (or lack of it) on dealing with these cases for s arc transitive graphs.

Previously, she had described distance-transitive graphs, and given Derek Smith’s description of the ways in which the automorphism group of such a graph can be imprimitive, and how to reduce to the primitive case.

Csaba and Pablo both talked about aspects of the O’Nan–Scott Theorem. Pablo had to leave after three days, so only gave four lectures. He took us through the theorem, and described some consequences. One of these was an impressive new theorem which asserts that, with known exceptions (basically the large groups, subgroups of the wreath product of the symmetric group of degree n on k-sets with some transitive group of degree l containing the socle (An)l), every element of such a group is a “regular” permutation, one which has a cycle of length equal to its order.

Pablo’s other application was to a conjecture of Richard Weiss made nearly 40 years ago. It asserts that if a finite graph is connected and vertex-transitive, and the vertex stabiliser acts primitively on its neighbours, then the order of the vertex stabiliser is bounded by a function of the valency. (This is related to the Sims conjecture.) He proved it for twisted wreath products as an illustration of the techniques.

Csaba’s focus was on what I call “non-basic groups”, those which preserve a Cartesian decomposition of the domain. Such a decomposition is a collection of partitions with the property that, given an arbitrary choice of one part from each partition, there is a unique point in the intersection of those parts. (The points can be identified with all words of length l over an alphabet A, and the ith partition divides the words according to their entries in the ith coordinate. He and Cheryl are writing a book about this; a prelimiary version is available on his website.

He spoke about how to recognise when a group preserves a Cartesian decomposition, and how to find the identification if it is. He showed us that the only almost simple groups which preserve a Cartesian decomposition have socle A6, M12, or Sp(4,2a).

(In fact, I have GAP code for checking this, which I wrote in connection to the road closure problem, which (to my great surprise) seems to be competitive with other methods, but which is still capable of significant improvement.)

In his final lecture, he spoke about twisted wreath products. Primitive groups with a unique minimal normal subgroup which is non-abelian and acts regularly are necessarily of this form; this case was omitted from the first versions of the O’Nan–Scott Theorem, but Aschbacher and Scott, and Kovács, pointed out that examples do exist. The twisted wreath product construction was already known; it was probably discovered by B. H. Neumann, and is dealt with in Suzuki’s book. Csaba explained the necessary and sufficient conditions for a twisted wreath product to be a primitive permutation group. (The smallest example is a semi-direct product of (A5)6 by A6, and is a permutation group of degree 606; so it is unlikely to arise in a computational problem for a few years yet.

My lectures were about permutation group problems arising from transformation semigroups; in particular, what are the conditions on a permutation group G if the semigroup generated by G and f has some nice property (such as synchronizing, regular, or idempotent-generated apart from the group G) for all non-permutations f, or all in some restricted class (such as all of rank k, or all with image a prescribed set of size k). The resulting conditions are typically equivalent to or closely related to primitivity if k = 2, or to higher degrees of homogeneity for larger values. So I was interested in groups slightly higher in the hierarchy than my fellow lecturers, for the most part.

In addition, there was a lecture by Tomasz Popiel, on results he found with his Perth colleagues on generalized polygons with point-primitive groups. They use the O’Nan–Scott methodology, together with some nice new results on fixed point ratios of primitive groups of various types. Tomasz asked for help in obtaining similar results in the twisted wreath product case (which has not yet succumbed to their analysis).

The lecturers also posed exercises for the students to work (and gave solutions to them), and there was also a problem session, which will be written up in due course.

Misty morning

The weather at the start of the week was not so good. When we started out on the walk (round two local lakes, about 17km) on Wednesday afternoon, we could hardly see where we were going at the start; but by the time we returned, it had become a beautiful afternoon. The next day was so nice that we moved outside for the problem session. The lecture room had two large blackboards, each a triptych which could be folded out to give lots of board space, or closed to give some additional space for results that would be needed later; they were on rollers, and so it was possible to move one, and enough chairs, outside.

Problem session

Course material (including exercises) is available here.

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

London Mathematical Society Newsletter

The first issue of the revamped LMS newsletter, edited by Iain Moffatt, reached me a little while ago.

The first obvious difference is that it has gone from A5 to A4 format, the same as the newsletters of the European Mathematical Society and the Institute for Mathematics and its Applications.

A lot of content hasn’t changed, though now on the larger pages it is laid out more spaciously: news, reports of meetings, Council diary, forthcoming Society meetings and other events, book reviews, obituaries. But along with that there are a couple of longer features: Béla Bollobás on Bill Tutte’s centenary, Andrew Granville on a “panopoly” of proofs that there are infinitely many primes (which has non-empty intersection with the first chapter of Proofs from the Book, not surprisingly), and an article by Elizabeth Quaglia on how to ensure efficient performance of networks to download requests while keeping the requests confidential.

A new feature is “micro/nano-theses”, designed to highlight new results by young researchers. In this issue, Matthew Burfitt tells us about “Free loop cohomology of homogeneous spaces”. We also have the first two in a series of “Success stories in mathematics”, which will hopefully showcase what great careers are available to mathematicians.

The Newsletter is not entirely free of misprints. It corrects several in the last issue (including a garbling of Ramanujan’s famous equation 103+93 = 123+13), but manages to miss out completely the accented letter in the name Erdős.

But definitely a change for the better. Well done Iain and his team!

The Newsletter is available on-line at https://www.lms.ac.uk/publications/lms-newsletter .

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