Peter Keevash at IMS

Peter Keevash at IMS

This picture (courtesy of Sebi Cioabă) shows Peter Keevash with the diagram which illustrates the proof strategy for his theorem. Perhaps it will be helpful, especially to those who heard the lecture (or similar lectures elsewhere).

Thanks Sebi!

Posted in exposition | Tagged , | Leave a comment

The end of the conference

Singapore flowers

The last day of the conference was over. Here are a couple of closing remarks. We have certainly heard an amazing collection of talks over the last week!

I didn’t yet mention the other short course, given by Simeon Ball and Aart Blokhuis, on the polynomial method in finite geometry. Among other things, they showed us four different ways to get bounds for a set of points in a projective or affine space meeting every hyperplane in at least (or at most) a certain number of points: one based on polynomials over the finite field of the geometry, one over the complex numbers, one over the p-adic numbers, and one using the resultant. But there was a lot of detail, and I didn’t even attempt to take detailed notes. I hope the slides will be made available at some point!

The highlight of my advanced combinatorics course in St Andrews this year was the construction and characterisation of the strongly regular graphs associated with non-singular quadratic forms over the field GF(2). These featured in the talks by Alice Hui (who is using Godsil–McKay switching to find other graphs cospectral with them, and Sebi Cioabă (together with lots more in a packed programme). Peter Sin also talked about cospectral graphs, more precisely, an infinite number of pairs of graphs which (unlike Alice’s) have the same spectrum and the same Smith normal form. These are the Paley and Peisert graphs on q vertices, where q is the square of a prime congruent to 3 (mod 4). These have a common description. The subgroup of index 4 in the multiplicative group has 4 cosets with a cyclic structure. Taking the first and third cosets in cyclic order gives the Paley graph, the first and second give the Peisert graph.

Dirk Hachenberger was counting elements of a finite field which are both primitive (i.e. generate the multiplicative group) and normal (an element is normal if it and its conjugates under the Frobenius map span the field as vector space over the base field). Remarkably, it was only proved in 1992 by Lenstra and Schoof that primitive normal elements exist, but Dirk has lower bounds for the number, and it seems that, at least for extensions of large degree of a fixed base field, almost all primitive elements are normal.

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

Keevash on triangle decompositions

Today Peter Keevash finished four and a half hours of lectures on his latest improvement of his result on the existence of designs.

I have heard him talk on this before, but in a one-hour talk he had time to outline the strategy of the proof without going into much detail. That was not the case here, and he gave a riveting account of the many complications that had to be faced on the way to the theorem. Also, he has a much more general theorem now, but he chose to concentrate on one special case, which actually bears the same relationship to the new general theorem as does Kirkman’s construction of “Steiner triple systems” does to Keevash’s earlier theorem on the existence of t-designs for all t. If that sounds like I am belittling what he did, this is absolutely not the case, as will be clear to everyone there; rather, it covered many of the complexities of the general proof but kept the exposition within reasonable bounds.

Here I propose to give his four-point outline of the proof, and then describe some of the complexities of the four steps. But first I will say how the new theorem is much more general than the old one.

A t-(v,k,λ) design is a collection of k-sets of a v-set which cover every t-set exactly λ times; in other words, a partition of the hyperedges of the λ-fold complete t-hypergraph on v points into copies of the complete t-hypergraph on k points. In particular, a Steiner triple system is a partition of the edge set of the complete graph into triangles. The new results extend this from partitioning the edges of a complete uniform hypergraph to a much wider class of hypergraphs. The notation would become near to uncontrollable if he had talked about this proof; so instead he showed us how to partition the edges of a suitable graph into triangles.

The conditions on the graph are:

  • It should be “tridivisible”, that is, the number of edges should be divisible by 3, and all the vertex degrees should be even (these are the familiar necessary conditions)
  • The edge density should be at least some constant δ.
  • The graph should satisfy a strengthening of a property that the random graph has, which he called “typical”. Typicality takes two parameters c (a small positive real number) and h (a small positive integer), and asserts that the number of common neighbours of any set of at most h vertices should be between (1−c) and (1+c) times the expected number in a random graph with the same edge density. Peter showed us a proof with h = 16, but at the end indicated why h = 2 will suffice. (This is stronger than being random or pseudorandom: in those cases, only most sets of vertices are required to satisfy the condition, some larger deviations are permitted.)

The four steps in the proof are, briefly, the following:

  1. First, set aside a collection of triangles, called the template, for use at the end.
  2. Next, use the Rödl nibble argument to cover almost all of the remaining edges by triangles. The ones left over form the leave.
  3. Put the edges of the leave into triangles using some edges from the template triangles (which have then been used twice). The edges used for this form the spill.
  4. Finally, fix the twice-covered edges by finding a two sets A and B of triangles, where the spill together with the edges in A form the same set as the edges in B, and the triangles of B are template triangles; swap the spill and A for B.

(Added later: here is a picture (by Sebi Cioabă) illustrating the steps.)

Now just a brief note on the steps.

Step 1: randomly embed the set of n vertices of the graph into an elementary abelian 2-group of size a little larger than n (precisely, between two and four times n. Then the template consists of all the triangles xyz for which x+y+z = 0 in the abelian group.

Using concentration results (specifically, Azuma’s inequality), one shows that the graph formed by the edges of the template triangles is itself dense and typical, and the vertex degrees are not too large.

Step 2: The original Rödl nibble doesn’t quite work. The version needed, due to Frankl and Rödl, Pippenger, and Spencer, which gives a near-perfect matching in a hypergraph under suitable conditions. The hypergraph used as as vertices the edges of G not in template triangles, and as edges the sets of three edges of G forming a triangle. A near-perfect matching is a set of triangles covering most of the edges, as required.

Step 3: The edges of the leave (not covered in Step 2) are completed to triangles using edges from the template, ensuring that the pairs of edges used don’t overlap. This is done by a random greedy algorithm. If it were not for the disjointness condition, the choices would be independent, and the algorithm easy to analyse; the correct version turns out to be a fairly small perturbation of this. In this way, it is shown that the algorithm succeeds, and that no vertices of high degree are created.

Since “random greedy” is very important in Step 4, Peter covered this in considerable detail.

Step 4: The final fix. The basic idea here is that of an integral design (with multiplicities −1, 0, and 1, as in the work of Graver and Jurkat and of Wilson. But the context is a little different, since the spill edges must be dealt with, and so the work has to be done again from scratch.

Using typicality, it is possible to show that the “bad” edges can be embedded into subgraphs where a “switch” replaces the triangles by good ones. However, we have to be careful to get, not just triangles made of template edges, but actual template triangles! This is where the algebraic structure comes in.

Typicality, worked to the limit, shows that we can choose the configurations so that a new triangle xyz is embedded into an octahedron whose other vertices are x+y, y+z, and z+x (in the abelian group). Now the eight faces fall into two sets of four, the first containing xyz, and the second consisting of triangles like xy(x+y) (in the abelian group) which are indeed template triangles. This is done by using more care choosing the configurations mentioned in the preceding paragraph, so that each of these triangles sits inside such an octahedron. The configurations become sufficiently complicated that apparently the typicality condition is required for as many as 16 vertices. But, as Peter explained, typicality for sets of two vertices implies that the condition holds for almost all sets of 3, …, 16 vertices, and this is enough for the random greedy algorithm to get to work on.

A tour de force!

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

Green on derangements

I have to mention Ben Green again. Yesterday he gave a lovely colloquium talk on a problem I had cracked my head against some years ago without much success.

As usual with derangements, the story begins with a classical result: the probability that a random permutation of n points has no fixed points is very close to 1/e.

How many permutations fix no subset of size k of the domain? In other words, what is the proportion of derangements in the action of the symmetric group Sn on k-sets? For fixed k, this tends to a limit p(k). (This is an easy consequence of Goncharev’s theorem that the joint distribution of the number of cycles of lengths 1, 2, …, k tends to independent Poisson random variables with parameters 1, 1/2, …, 1/k.

But what is the function p(k)? This is the question that Ben and his collaborators Sean Eberhard and Kevin Ford have tackled. It is bounded above and below by constants times k−0.086…(log k)−3/2. The mysterious constant is 1−(1+log log 2)/log 2.

There is a context for this. Łuczak and Pyber showed that the only primitive actions of the symmetric groups for which the proportion of derangements does not tend to zero are those on k-sets for fixed k; their bounds were improved by Diaconis, Fulman and Guralnick, who proved much else besides, including the limiting distribution in the above case.

Ben went on to describe some fascinating connections with the number of divisors of an integer; but I have no time to talk about this now.

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

More graphs

NUS fish

John Bamberg is reporting on New Directions in Combinatorics on SymOmega (his report on Day 1 is here), so I will not even attempt to be comprehensive, but will just pick some plums.

Not very long ago, I reported the story of Graham Higman’s lecture to the LMS on his result that “the unknown Moore graph” on 3250 vertices could not be vertex-transitive. I had no idea what was about to happen …

Yesterday, Stefaan De Winter gave a talk on partial difference sets in abelian groups. He began with a result of Benson from 1970, giving a divisibility condition which is necessary for the existence of a certain kind of automorphism of a generalized quadrangle. He went on to mention extensions to partial geometries, partial quadrangles, and who knows what, before describing his own work, which applied this technique to partial difference sets in abelian group, leading to the nonexistence of all but two parameter sets on a list of “small” open cases. (The two remaining would each live in a group of order 216.)

But I am afraid I did not follow too closely, since I was sitting there slightly stunned. Benson’s formula included as a parameter the number a(g) of points p of the geometry for which p and its image under g are collinear.

Just such a formula, using just such a parameter, was at the heart of Higman’s proof, and was the reason why he could get further than Michael Aschbacher, who had proved that this unknown Moore graph couldn’t have a rank 3 group. (Careful analysis shows that there are two possible structures for an involution acting on such a graph; one was eliminated by Higman’s condition and the other is an odd permutation. The result follows easily from that.)

But the result is a special case of something more general. My first thought was, “Didn’t Norman Biggs prove that?” It may be that he did, I can’t at the moment find a reference. But I did find where to look for the general result. It, and Higman’s application, are on pages 89–91 of my book on Permutation Groups. The context is association schemes; here is a brief summary.

Automorphisms of association schemes

An association scheme is a collection of relations R1,…,Rr on an n-element set X with the properties

  • the relations partition X×X;
  • equality is one of the relations, say R1;
  • each relation is symmetric;
  • the span (over the real numbers) of the relation matrices A1,…,Ar is closed under multiplication.

It follows that the matrices in the fourth condition commute. Indeed, the second and third conditions can be weakened to say that the set of matrices is commutative and closed under transposition, and the complex numbers used in the fourth condition; this is a commutative coherent configuration, and everything below works equally well for this wider class.

The matrices are simultaneously diagonalisable, and so have r pairwise orthogonal common eigenspaces. Let E1,…Er be the orthogonal projections onto these eigenspaces. Then the Es form another basis for the span of the As. Let P be the change of basis matrix expressing the As in terms of the Es (its (i,j) entry is the jth eigenvalue of Ai), and Q the change of basis matrix in the other direction, expressing the Es in terms of the As.

Now an automorphism of the association scheme (in the strong sense, fixing all the relations) leaves the eigenspaces invariant, and so induces a linear map on each eigenspace. Thus the permutation representation of the automorphism group is decomposed into representations on these eigenspaces. It is easy to compute the character of the jth representation: its value on an automorphism g is a linear combination of the numbers ai(g), the number of points x for which (x,xg) satisfies the ith relation), and the coefficients are given by the entries of Q.

Once we have a formula for the character, various conditions can be deduced; these can all be regarded as necessary conditions for the existence of an association scheme with an automorphism of the appropriate type. For example,

  • Any character value is an algebraic integer (indeed, lies in a cyclotomic field), and so if rational it is an integer. Applying this to the identity automorphism gives the usual “integrality conditions” for the existence of an association scheme.
  • The inner product of characters, for example this character with the trivial character, or with itself, must be non-negative integers.

So Stefaan has added to to the stock of applications of this technique. Surely there must be many others?

A final question: does anyone have more information about the history of this technique? Did Benson invent it? (I have little doubt that Higman discovered it independently, but I don’t know the date; I think his lecture was in the late 1970s or early 1980s.)

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

Caps in AG(n,3)

For the past week and a half I have done little but mark exam papers. At some point during this, I looked at Tim Gowers’ blog, and read that a very significant improvement had very recently been made on the bound for the size of a cap in affine space over the field GF(3) of three elements. Tim claimed that “the papers are so short, and the ideas so transparent”, that I was tempted to read them, but decided to put off reading what he said until I had time to do it properly.

Then on Saturday I flew one-third of the way round the world, to the meeting on New directions in combinatorics at the Institute for Mathematical Sciences of the National University of Singapore. The meeting started at 9am yesterday; by 9.40, I had seen the entire proof (apart from a messy calculation I will mention below), and by 9.50 the outline of a slightly different proof, all thanks to a beautiful talk by the first speaker, Ben Green.

IMS, NUS, Singapore

A cap in a finite geometry is a set of points with the property that no three are collinear; thus it is simply a higher-dimensional version of an arc, and the name is intended to suggest this. Caps have been studied for some time in finite geometry, and many beautiful examples exist, including Hill’s 56-point example in PG(5,3) which forms half of the elliptic quadric. Not so much attention was paid to asymptotics, though.

Consider caps in AG(n,3), the affine space over GF(3) (the vector space without a distinguished origin). It has the lovely property that a line is just a set of three vectors which add up to 0. (In general a line consists of all points of the form a+tb, where a and b are fixed and t runs through the field; the fact that 1+1+1 = 0+1+2 = 0 shows that this is equivalent to the sum-0 property.

A curious point of terminology. Finite geometers always called these objects caps. But people in additive combinatorics seem to have re-named them “capsets”. I shall be conservative and stick to my heritage.

Clearly a cap cannot be larger than 3n. The set of all vectors with coordinates 0 and 1 only is a cap of size 2n. So it is not unreasonable to assume that the largest cap has size about cn for some constant c. But before two weeks ago, nothing much better than Roy Meshulam’s upper bound of c.3n/n was known. (Roy’s proof uses discrete harmonic analysis, aka characters of finite abelian groups.) But now the bound has been brought down to about 2.756n, by Ellenberg and Gijswijt (independently), by adapting a brilliant lemma from a slightly different context by Croot, Lev and Pach.

Let F denote the field GF(3). Every function from Fn to F is uniquely representable by a cube-free polynomial in n variables over F. Such a polynomial is a linear combination of monomials, each of which is a product of terms xik for k taking the values 0, 1 or 2. The degree of a random monomial is thus the sum of <in random variables each taking the value 0, 1 or 2 with equal probability, and so the expected degree is n, [corrected from earlier version] and the probability that the degree differs from this by a linear amount is exponentially small.

The precise statement of the theorem is that the size of a cap is bounded by 3D, where D is the dimension of the space of cubefree polynomials of degree 2n/3. A long and messy calculation is required to show that D is about 2.756n, but hopefully you now believe that it is at least exponentially smaller than 3n.

The proof involves two results, of which Ben gave complete proofs.

The first says that a set A in the affine space which has size larger than 3D contains a subset of size at least |A|−D which is the support of a polynomial of degree at most 4n/3. The proof is just linear algebra.

The second, the Croot–Lev–Pach principle, is also just linear algebra. It says that if p is a cubefree polynomial of degree d, B and C two subsets, and M the |B|×|C| matrix with (b,c) entry p(b+c), then the rank of M is at most twice the degree of the space of polynomials of degree d/2. It really is a great idea, and depends on the fact that row rank is equal to column rank!

The relevance of this to caps is obvious. If we have a large cap, the first result gives us a still large cap which supports a polynomial; the values of this polynomial on b, c, and b+c cannot all be non-zero.

I won’t give more detail. You should have been there!

As a pointer to the future, Ben mentioned at the end of this exposition a result which he only learned on Sunday when he saw it on Facebook. Time for we old dinosaurs to trundle off to bed …

Posted in Uncategorized | Tagged , , , , , , , , | 6 Comments

More groups

The title reminds me of the occasion when my academic grandfather lectured to the London Mathematical Society on “Moore graphs”. Unfortunately, someone got it wrong, and his lecture was billed as “More graphs”.

But here I really do mean what I wrote.

The function gnu(n) (for Group NUmber) is the number of groups of order n (up to isomorphism). It is an extremely irregular function. It is known up to 2047, and of all the groups of these orders, more than 99% have order 1024. The number is about 5×1010, which is itself dwarfed by the number of groups of the next order 2048, which is about 1.77×1015. However, it is an important function, and precise values are very much needed, as well as providing a computational challenge to existing algorithms and computing facilities. See this article for comments and elaborations.

Now Alexander Konovalov has set up a crowdsourcing project, the “Gnu Project“, to calculate further values of the function, filling in some gaps in the presently known values. He has made available a GAP package to enable anyone to contribute. (The GAP website is here, in case you need to download this free computational system for algebra and discrete mathematics.) According to Alexander, a forthcoming release of GAP will be optimized so as to steamroll over problems of this type.

GAP road roller

Instructions for getting and using the package and contributing to the database are provided. Take a look, and lend a hand!

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