Association schemes for diagonal groups

Sean Eberhard commented on my posts on diagonal groups (see here and here). He is correct; there is an association scheme preserved by the full diagonal group with n factors in the socle; it is non-trivial if n > 2. The details take a few pages to write out but the basic idea is completely fine.

This shows that an AS-free group (one which does not preserve a non-trivial association scheme) must be either 2-homogeneous or almost simple. Clearly every 2-homogeneous group is AS-free; there are almost simple examples, but they are rather strange and no pattern has emerged thus far.

I hope a preprint will go on the arXiv sometime soon. But you read it first here (in Sean’s comments over the last few days).

Posted in open problems | Tagged , , , | 1 Comment

London Combinatorics Colloquia 2019

In London last week for the two combinatorics colloquia, at Queen Mary and LSE. The weather was unusually grey and rainy; it seems in retrospect that it is almost always fine and sunny for this event, but I know that this is a trick of memory.

Two days, with six talks on each day; as usual I will only say a bit about my favourites.

The first talk on Wednesday at Queen Mary was by Péter Pál Pach, on Polynomial Schur’s Theorem. The Schur’s theorem here is the one that says, if you colour the natural numbers with finitely many colours, there is necessarily a monochromatic solution of the equation x+y = z. His talk was about the related equation x+y = p(z), where p is a polynomial. He described the case p(z) = z2 in detail; in this case, a pointer to what follows, the statement is true for two colours but false for three or more. In general, there is one case which is easily dispatched, typefied by the polynomial p(z) = 2z2+1; the right-hand side is always odd, so if we colour the even numbers red and the odd numbers blue, there is no monochromatic solution. Excluding this and related things, the same result holds: true for two colours, false for three or more.

Julia Wolf gave a talk which made some interesting connections, about an “additive combinatorics” version of the regularity lemma. The bounds which appear in the regularity lemma are very large (tower functions, as Gowers showed). But there is a graph called the “half graph” such that excluding it makes the proof easy and the bounds polynomial. The graph has vertices xi and yi for 1 ≤ i ≤ k, with xi joined to yj if and only if i ≤ j. This (and its infinite analogue) is a familiar object in parts of combinatorics and model theory; it is the case which must be excluded to get a Ramsey theorem for bipartite graphs, and its exclusion gives what model theorists call k-stability. To get nice results for subsets of finite abelian groups, you have to exclude the half-graph from the “additive Cayley graph” of the group, whose vertices are group elements, joined if their sum lies in the special subset. Julia and her collaborators proved strong results under this hypothesis, at which point the model theorists (including Anand Pillay) got into the act, and there was a race between the two groups.

In the afternoon, a rather low-key but very entertaining talk from Keith Ball. He began by exhibiting the Hadamard matrix of order 4, normalised so that its first row is positive. Any other row has two +s and two −s. The positions of the +s and the −s in the rows give a 1-factorisation of K4. So Keith asked: for which normalised Hadamard matrices of order n (a multiple of 4) is there a 1-factorisation of Kn with a bijection between 1-factors and rows after the first such that the two ends of each edge in the 1-factor have the same entry in the corresponding row? And (different question) for which normalised Hadamard matrices is there a 1-factorisation with a bijection between 1-factors and rows sso that the two ends of each edge in the 1-factor have opposite entries in the corresponding row? He conjectures that it is always so. He showed us the proof of the conjecture for Sylvester matrices (which he called “Walsh matrices”), and certain Paley matrices (the prime p has to have the property that 2 is the square of a primitive root).

His proof for Sylvester was by induction; to get from one to the next you take the Kronecker product with the Hadamard matrix of order 2. I wondered whether the property would be preserved by arbitrary Kronecker products of Hadamard matrices. After the talk, Natalie Behague assured me that it was so, and showed me the simple proof.

The next day, at LSE, I will describe just two of the six talks. The first, by Dhruv Mubayi, was my favourite of the whole two days. He talked about classical Ramsey numbers: colour the k-sets of an N-set red and blue; how large does N have to be to guarantee either a s-set with all subsets red, or a n-set with all subsets blue? He was particularly interested in the “off-diagonal” case where k and s are fixed, and n grows. Typically, upper and lower bounds are known, and they are tower functions of heights k and k−1 respectively. He surveyed the state of the art on this.

But his real interest was a refinement, due to Erdős and Hajnal, which introduces a new parameter t, between 1 and {s choose k}. The question is, how large does N have to be to guarantee either a s-set containing at least t red k-sets, or an n-set all of whose k-subsets are blue? Erdős and Hajnal conjectured that there are “threshold” values for t, at which the value of N jumps from polynomial to exponential, and from exponential to double exponential, and so on for each possible order of the tower. Dhruv and his colleagues have shown the existence of the first threshold, and found its precise value. Dhruv explained very clearly how this is a complicated mixture of randomness and induction, and neither part can be left out.

The other talk that impressed me was by Johannes Carmesin. He started off by telling us, or reminding us, about Kuratowski’s theorem: a graph is planar if and only if it has no K5 or K3,3 minor. It was not until 2006 that Lovász thought to ask about higher-dimensional analogues. Johannes interprets this as asking what are the obstructions to embedding a 2-dimensional simplicial complex into 3-space. He developed a theory of “space minors” for 2-dimensional complexes, rather more complicated than graph minors, and gave an excluded minor characterisation of embeddability in 3-space for a simply connected, locally 3-connected 2-complex. One remarkable feature of the theorem is the proof. You show that if the excluded minors don’t occur, then you can embed the complex in a simply connected 3-dimensional manifold. Now you use Perelman’s solution to the Poincaré conjecture: this manifold must be a 3-sphere, and you are done. And there is much more beside. He also has generalisations of Whitney’s theorems, matroid interpretations of everything, and so on. I don’t usually enjoy topology, but this was a very nice talk!

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

A virtual colloquium

I feel a bit nervous about advertising this.

This Thursday, 25 April, I am for the first time ever giving a virtual colloquium. The Northeast Combinatorics Network (that’s Northeast North America, for pedants) have an occasional Virtual Combinatorics Colloquium, and I will be speaking at 2pm Eastern Time (19.00 British Summer Time). When I consider all the things that might go wrong, and the distance my words and pictures have to travel, I am not filled with confidence …

So wish me well, and join if you feel so inclined.

Posted in events | Tagged , , | 4 Comments

Mary Queen of Scots Way

Walking is very popular now. To meet the demand, many new named long-distance paths have been created. I wrote earlier about my proposed X to Y walk, which I fully intended to do when I retired, but I haven’t quite managed to retire yet.

We try to do a substantial walk at least once a week, though when things are busy it doesn’t always happen. But last weekend, with the weather nicer on Saturday than Sunday, we caught a bus to Yetts o’ Muckhart. (The St Andrews to Stirling bus stops there, but doesn’t run on Sundays). We walked up a busy unpleasant road to Glendevon, and then through a beautiful pass in the Ochil Hills to Dollar, where we spent some time in the remarkable Glen Dollar around Castle Campbell.

Consulting the map afterwards, we saw that we had done a section of a path, the Mary Queen of Scots Way (which seems to be fairly recent, though their Web page is undated – Mary is in the public eye at the moment so such a path seems very natural even though it doesn’t go to either her birthplace or the place on Loch Leven where she was imprisoned and forced to abdicate), from Glendevon to Dollar.

Further research using the route descriptions on the website, together with the excellent mapping on the Long Distance Walkers Association website, showed that in fact I had walked several sections of it before. In 1995, after the British Combinatorial Conference in Stirling, Carol Whitehead and I took a bus to Callendar and walked from there to Dunblane; but I really don’t remember which route we took, so not sure if it agreed with the MQoSW. Then in 2002, on holiday in Tarbet on Loch Lomond, we walked from Arrochar to Inveruglas along Glen Loin, and then took the ferry to Inversnaid: this is the first stretch of the MQoSW. Then, in Fife, the Way coincides almost exactly with the Fife Pilgrim Way from St Andrews to Clatto Reservoir; and I have walked from Burnside, along Glen Vale, over Harperleas Reservoir and the Lomond Hills, and down Maspie Den to Falkland.

So this weekend we decided to walk from Falkland to Clatto Reservoir to plug one gap, and then carry on along the Waterless Way to Ceres. The number 64 bus, which does a guided tour of north-east Fife, calls at both these places, and indeed the same driver who took us to Falkland picked us up in Ceres and recognised us.

The path is not waymarked, but with a combination of the route description and the LDWA map I had been able to copy the line onto our OS map, and we were never in any danger of getting lost.

I had expected the stretch across the very flat Howe of Fife to be rather boring, but in fact the path went through some very nice woodland with the trees coming into leaf, and masses of spring flowers blooming uncluding violets, celandines, dandelines, bluebells, primroses and forget-me-nots. We saw a nuthatch walking around up and down the trunks of trees (the RSPB distribution map says they don’t occur this far north, but probably climate change is responsible for this). Then, on the next stretch of farmland, we saw no fewer then eleven hares in the fields.

Hares near Kingskettle

Butterflies (peacocks and tortoiseshell) had emerged and were basking in the sun on the path or flying their complicated courtship dances. At Clatto reservoir, there were tufted ducks and swans on the lake, and when we stopped for a snack we saw two roe deer running across the field and stopping to feed.

One technical word of warning for anyone trying this path. The website describes it as “easy”, and mostly it is: but between Clatto Farm and the reservoir it goes along a boggy river bottom without a path or a way to cross the two fences encountered. You would do much better to turn off the path at the cottages just before Clatto Farm, where a short link takes you over the burn on a wooden bridge and up the other side to join the Fife Pilgrim Way, which is a good (and waymarked) path.

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

A talk by Stephen Senn

I’ve just heard a nice talk by Stephen Senn, entitled “In search of lost infinities. What is the ‘n’ in big data?”

The moral was that, in clinical trials and observational trials, everyone assumes that more data mean more accurate estimates; but, if you have not thought carefully about the model, and even sometimes if you have (because of unavoidable effects) this is not so, the variance of the difference between estimates may not tend to zero as the number of observations tends to infinity. This is especially the case with using historical data.

Somewhat technical, but you can read at least part of it here.

Perhaps best of all, he had some very nice one-liners. My favourite was this:

Being a statistician means never having to say you’re certain.

Posted in Uncategorized | Tagged , | Leave a comment

Fair games and Artin’s conjecture

A few years ago I described Persi Diaconis’ response to G. H. Hardy’s claim that there is a real dividing line between real and recreational mathematics. (See the report here.) This led from Persi’s first experiments in card shuffling to Artin’s conjecture on primitive roots modulo a prime and on beyond that to the generalised Riemann hypothesis.

I am pleased to be able to report another application of Artin’s conjecture, or at least of the special case of Artin’s conjecture which asserts that there are infinitely many prime numbers p such that 2 is a primitive root mod p (that is, the multiplicative order of 2 in the integers mod p is p−1.

It is pleasant to report that the same end point can be reached from an entirely different start, in game theory (which, despite its title, has some claim to be regarded as “real mathematics” itself). The context is n-player simple games in the sense of von Neumann and Morgenstern, those where the structure of the game is determined completely by knowledge of the winning coalitions, those sets of players which by cooperating can completely defeat their opponents. Obviously a superset of a winning coalition is a winning coalition, and the complement of a winning coalition is a “losing coalition”.

Isbell had the idea that, to ensure the game is fair, we could require a group of automorphisms of the up-set of winning coalitions which acts transitively on the set of players. For which n does such a fair game exist? Isbell showed that it was necessary and sufficient that there exists a transitive permutation group on the set of n players which contains no fixed-point-free element of 2-power order. For, if such an element exists, then it maps some subset to its complement, and so cannot preserve a simple game. Conversely, if there is a group containing no such element, the subsets of size n/2 fall into complementary orbits; choosing one of each pair to be winning coalitions, together with all sets of size larger than n/2, gives a fair simple game.

Isbell conjectured that, if the 2-part of n is sufficiently large compared to the odd part, then any transitive permutation group of degree n should contain a fixed-point-free 2-element, and hence no fair game on n players can exist. This conjecture is still unproven well over 50 years later, and is one of the conjectures I would most like to see resolved.

Any transitive group of 2-power degree contains a fixed-point-free 2-element (choose an element in the centre of a Sylow 2-subgroup). For a simple example, take n = 4. It is readily checked that there are two types of winning coalitions of two players: all those containing a fixed player A, or all those not containing a fixed player Z. Clearly A or Z plays a special role in this case; players are not all alike.

In investigating this conjecture, I was led to the following problem (you can ponder the exact link if you like, but it is not immediately relevant to what follows). Suppose that n is odd. Let V be the vector space of all n-tuples over the 2-element field F. What is the largest codimension of a subgroup W of V with the property that the cyclic shifts of W cover V?

It is not hard to see that we lose nothing by replacing V by its codimension-1 subspace consisting of all vectors containing an even number of ones. In this case, if n is greater than 3, there is always a subspace of codimension at least 2 which is cyclically covering. For any vector in this space has an odd number of zeros, and hence a run of zeros of odd length, and so contains a run 000 or 101; thus some cyclic shift of it lies in the subspace defined by the equations x1 = x3, x2 = 0. I wondered whether the maximum codimension tends to infinity with n, or whether the value 2 is attained infinitely often.

I posed this problem some time ago at the British Combinatorial Conference. Nothing happened until very recently, but now there are two preprints on it available. David Ellis and his student William Raynaud generalised it considerably, replacing F by an arbitrary finite field, n by an arbitrary integer, and the cyclic shift by an arbitrary transitive group. See arXiv 1810.03485.

But I really want to draw attention to a different paper, by James Aaronson, Carla Groenland and Tom Johnston from Oxford. In a 34-page paper arXiv 1903.10613, they show that, if n is an odd prime and 2 a primitive root mod n, then the maximum codimension is indeed 2. So they answer my original question, conditional on the Artin conjecture!

I will not attempt to summarise their proof, other than to say it is a clever mixture of algebraic and graph-theoretic argument. I certainly have not had time to read it carefully. But I am delighted, and in part feel vindicated that I was not able to do this myself; it is clearly harder than the simple statement suggests.

Posted in exposition, mathematics, open problems | Tagged , , , , | Leave a comment

Atiyah memorial day

On Saturday, we went to the memorial event for Michael Atiyah, held in the magnificent Playfair Library in the University of Edinburgh’s Old College buildings. (Not named after John Playfair, Professor of Mathematics in Edinburgh and responsible for Playfair’s Axiom, a form of the Parallel Postulate in Euclidean geometry.)

The first speaker was Nigel Hitchin, who made an attempt to explain the Atiyah–Singer Index Theorem to us. He began with Euler’s polyhedral formula VE+F = 2, on which the left-hand side is an alternating sum of combinatorial data and the right-hand side a topological invariant of the sphere. Using cohomology, the numbers on the left can be replaced by dimensions of vector spaces (the spaces of functions on vertices, edges and faces); then, using K-theory (another subject in which Atiyah played an important part), these can be replaced by vector spaces of differential forms. Applications include the 28 bitangents to the plane quartic (where Atiyah was proud of the theorem that a real quartic with no real points has exactly four real bitangents), and the structure of topological insulators.

Jean-Pierre Bourgignon, speaking by video link, told us something of Atiyah’s presence in mathematical physics, involving spinors and the Dirac operator, and something of his role in the setting up of the European Mathematical Society, of which he was individual member number one.

The other two speakers, Nick Manton and José Figueroa-O’Farrell, talked about physics rather than maths. Manton told us about work he and his students and colleagues had done on skyrmions, inspired by Michael Atiyah (but not directly Atiyah’s work). Figueroa-O’Farrell told us that Atiyah’s influence on Ed Witten had healed the divorce between maths and physics pointed to by Freeman Dyson in the 1970s, and claimed that now physics had an enormous influence on maths (an overstatement in my opinion, backed up by the statement that the Jones polynomial at a certain root of unity appears in the work of Witten).

After lunch, there were more personal recollections from a variety of people including Lord Mackay of Clashfern, the eminent lawyer and former Lord Chancellor, who had been a student of mathematics with Atiyah and had remained a close friend all his life; and William Duncan, former CEO of the Royal Society of Edinburgh, who had worked closely with Atiyah during his presidency.

Posted in Uncategorized | Tagged , , , , , | 2 Comments