The random graph and anti-foundation

Last year, Bea Adam-Day, one of my undergraduate project students, settled a question that had been bugging me for years.

According to the downward Löwenheim–Skolem Theorem of first-order logic (a consequence of the proof of Gödel’s Completeness Theorem), if a first-order theory in a countable language is consistent, then it has a countable model. This means, for example, that if I am interested in permutation groups of infinite degree which have specified numbers of orbits on n-tuples from the domain, or on n-element subsets of the domain, for some or all natural numbers n, then I can restrict my attention to countable groups acting on countable sets, and I don’t have to perplex myself with the mysteries of uncountable sets. (This is because the group axioms, the axioms for a group action, and the statement that in a given action a group has a given finite number of orbits can all be expressed as first-order sentences.)

However, there is a well-known puzzle arising from this theorem, the Skolem paradox. If, as mathematicians hope and most of us believe, the Zermelo–Fraenkel axioms for set theory are consistent (since they form the most common foundation for mathematics), then they have a countable model. How can this be reconciled with Cantor’s theorem (a consequence of ZF) stating that there exist uncountable sets?

This paradox makes one think more carefully about what a model of set theory is, and what uncountability means. A set is uncountable if there is no bijection between it and the set of natural numbers (or any of its initial subsets). A bijection is a special type of function, and a function is a set of ordered pairs with certain properties; an ordered pair is a particular kind of set. (Most usually, the ordered pair (x,y) is defined to be the set {{x},{x,y}}; the precise construction is not important provided it has the property that (x,y) = (u,v) if and only if x = u and y = v.) Moreover, the natural numbers comprise a particular set in the model, constructed in a certain way. Thus, Cantor’s theorem states the existence of a set U for which there does not exist a set of ordered pairs, with first elements in U and second elements in the set of natural numbers, satisfying the conditions to be a bijection.

Informally, we say that an observer outside the model, looking in, will see that U has countably many members, even though there is no set in the model to witness this countability. The resolution of the paradoxes I described here is similar; the collections defined do not constitute sets in the model.

Anyway, this post is not about the Skolem paradox. I went through this to get across the point that the ZF axioms are stated in terms of the membership relation on sets. In other words, a model of ZF is a directed graph, whose vertices are things called “sets”, with a directed edge from x to y if and only if xy. Thus, a countable model is just a countable directed graph, and can be considered from the point of view of graph theory.

One of the most remarkable facts about this is this. For any directed graph, we can form an undirected graph by simply forgetting the directions, replacing an arc xy by an edge {x,y}. If we do this for a countable model of ZF, we obtain the countable random graph! [In other words, Zermelo–Fraenkel set theory is the first-order theory of certain orientations of the random graph.]

I will sketch the argument. How do we recognise the random graph? As I have described in other posts, R is characterised by the Alice’s Restaurant property: given any two finite disjoint sets of vertices U and V, there is a vertex z joined to everything in U and to nothing in V. How do we check this for a countable model of ZF? Try taking the set U as z; it is certainly joined to all the vertices in U, since they are its members. Moreover, it does not contain any vertex in V. But there is a small problem: U itself might be contained in some member of V, in which case it would be joined to this vertex. To avoid this, we simply add to z the set V. Now if some element v of V were joined to z, then either vz, in which case necessarily z = V, so that vv; or zv, which would give a loop vVzv.

Here the gathering of finitely many elements into a set is justified by the Empty Set, Pairing and Union axioms of ZF, while the existence of a set containing itself, or a cycle of length 3 in the membership relation, are both forbidden by the Axiom of Foundation (which, more or less, forbids infinite descending chains in the membership relation). Note that the Axiom of Foundation also ensures that the undirected version of the membership digraph is a simple graph, that is, has no loops or multiple edges (it forbids both xx and xyx).

The Axiom of Foundation was initially seen as an important part of avoiding the paradoxes of set theory such as Russell’s Paradox concerning the set of all sets which are not members of themselves. (Russell’s Paradox can be expressed, more positively, as saying that there does not exist a set A which consists precisely of those sets which are not members of themselves. Now if there were a “universal” set S containing all sets, then Russell’s set would be {xS:xx}, whose existence would follow from the Axiom of Selection; so no such universal set can exist. In the motivation for ZF, we imagine the sets being constructed in stages, each stage containing sets built out of those which have already been constructed; the universal set would have to appear at the very last stage, but there is no last stage! This construction by stages has as a consequence that no infinite descending chain of sets can occur (there would have to be a first stage at which such a set arose …), and indeed has a consequence the standard formulation of the Axiom of Foundation.)

Incidentally, this approach shows why a model of ZF set theory has no symmetry. If there were an automorphism which didn’t fix everything, there would be a set moved by the automorphism appearing at the earliest possible stage; but this set is uniquely determined by its members (by the Axiom of Extension), all of which are fixed. This perhaps makes it even more remarkable that, by undirecting the adjacency relation in such an asymmetric graph, we obtain a graph with the huge amount of symmetry that the random graph possesses.

[This is not right, see comment below.]

However, there have been calls to examine alternative axiom systems not using this axiom, with a view to modelling recursive processes in computer science (among other possible applications). An “anti-foundation axiom” was introduced by Peter Aczel, and anti-foundational set theory is discussed in detail in the book Vicious Circles by Barwise and Moss. They denote by ZFA the Zermelo–Fraenkel system in which the axiom of foundation is replaced by the anti-foundation axiom. There is a relative consistency result stating that, if ZF is consistent, so is ZFA: the proof starts from a model of ZF and constructs a model of ZFA by adjoining solutions to certain sets of equations.

My question was: What do we get if we take a countable model of ZFA (as a directed graph) and symmetrise the membership relation?

Bea studying AFA

(The picture above is a self-portrait of Bea Adam-Day studying the Anti-Foundation Axiom; it is homage to the picture La reproduction interdite by René Magritte, used on the cover of the book by Barwise and Moss.)

Since a model of AFA can (and indeed does) contain loops and double edges, there are several ways we could interpret this question.

  • We could keep loops, or ignore them.
  • We could keep double edges, or ignore them.
  • We could even keep loops and double edges and ignore single edges.

It is not at all clear, in any case, whether we obtain a unique and highly symmetric graph like the random graph, or we just get a mess!

After quite a struggle, Bea managed to figure out what we get if we undirect the membership relation keeping loops but not double edges (in other words, putting a single undirected edge {x,y} when xy, whether or not yx). The graph we get is the random graph with loops, the graph we obtain with probability 1 if we toss a coin repeatedly to decide, not only which pairs of vertices are joined by edges, but which single vertices carry loops. There is a unique countable graph, defined by a similar “Alice’s restaurant property” (requiring that, given U and V, there is a witnessing vertex without a loop and another one with a loop). It is homogeneous, and universal for finite or countable graphs with loops but no multiple edges. Like the random graph, it is highly symmetric.

The proof follows the outline suggested earlier; but this time we have no Axiom of Foundation to invoke. Instead, the Anti-Foundation Axiom is consructive in nature, asserting that sets with certain properties exist; and in the other direction we use the failure of Russell’s Paradox. Pushing our earlier argument one step further, given a positive integer k, there is no set which consists precisely of all k-element sets (if there were, its union would be the “universal set”, since every set is a member of a k-element set); so, given any set whatsoever, there is a k-element set which it does not contain.

Inspired by this, I looked at one further case. What happens if we keep loops and double edges but throw away single edges? In other words, we put an edge {x,y} if both xy and yx hold. This time, no homogeneity result holds (indeed, the graph is not countably categorical), but it is not without structure. It has infinitely many finite connected components; indeed, any finite connected graph with loops occurs infinitely often as a connected component of our double-edge graph. The graph has at least one infinite component as well.

A preprint containing these results has just appeared on the arXiv.

Advertisements
Posted in doing mathematics, exposition | Tagged , , , | 3 Comments

Outer automorphisms

I have just put on the arXiv a paper I wrote with Sam Tarzi ten years ago. I want to say here something about the context, the contents of the paper, and the reason for posting it now.

Outer automorphisms of a group are automorphisms which are not induced by conjugation by elements of the group itself.

If a group G naturally occurs as a permutation group, then its automorphism group contains as a subgroup those automorphisms which are induced by conjugations in the symmetric group. If this subgroup is the entire automorphism group, then we can understand the outer automorphisms by looking just within the symmetric group. What I am concerned with here is whether or not this condition holds.

For the symmetric group, we have the remarkable Schreier–Ulam theorem: if n is any cardinal number, finite or infinite, except 6, then the symmetric group on n letters has no outer automorphisms. The exception, which I have described here, arguably is the key to understanding many sporadic phenomena in group theory and beyond. For example, the existence of an outer automorphism of S6 means that this group acts in two different ways on sets of size 6; taking the union of two such sets, we can enlarge the group to the Mathieu group M12. This group also has an outer automorphism not induced by permutations, and so has two actions on sets of size 12, which similarly give rise to the large Mathieu group M24.

As I described here, there is no similar phenomenon for transformation semigroups. The automorphism group of the full transformation semigroup on any set is the symmetric group on that set (a theorem of Sullivan, and maybe others); and this extends to various “large” subsemigroups, in particular, those whose units form a synchronizing permutation group. It is conjectured that it extends to subsemigroups whose units form a primitive permutation group; we took our first steps towards this in the paper just cited.

Now to the paper with Sam Tarzi. To warm up, consider the random graph R (discussed here). Let G be the automorphism group of R, which we regard as a permutation group on R. Now G has an outer automorphism induced by a permutation. For R is isomorphic to its complement, and a permutation inducing such an isomorphism must be an automorphism of G (since the group preserving R is identical with the group preserving the complement of R). Now it is possible to show, using results of Hrushovski and of Hodges and others, the following facts:

  • The outer automorphism group of G has order 2; that is, any automorphism of G is induced by a permutation of the vertex set of R, which is either an automorphism or an anti-automorphism of R.
  • The automorphism group of G does not split over G; in other words, there is no subgroup H such that GH = Aut(G) and GH = 1.

The second fact is very easy to show. Suppose that such a subgroup H exists. Then the non-identity element h of H would be an isomorphism from R to its complement whose square is the identity. Take a 2-cycle of h. This is fixed, as a set, by h; so if it is an edge, then its image is also an edge, and similarly for non-edge. But this contradicts the fact that h interchanges edges with non-edges.

Now the paper that Sam Tarzi and I wrote concerns a slightly more general situation. We replace R by Rm, the randomly m-coloured complete graph. (Similar to R, if we take a palette of m colours, and for each edge of the complete graph on a countable set we apply a random colour to it, then we obtain an object isomorphic to Rm with probability 1. If m = 2 and the colours are “solid” and “transparent”, then the edges coloured with the solid colour form the random graph.

Let Gm be the automorphism group of Rm. (We assume that m > 1.) Our theorem has three parts.

  • The automorphism group of Gm is induced by permutations of the vertices; so the outer automorphism group is isomorphic to the symmetric group Sm.
  • The automorphism group splits over Gm if and only if m is odd.
  • If m is even and not divisible by 8, then the smallest supplement of Gm in its automorphism group (a subgroup H such that GmH = Aut(Gm)) has order 2·m! (that is, just twice that of a hypothetical complement).

(For m = 2, this means that the random graph has an anti-automorphism which is a permutation of order 4.)

A corollary is that the groups Gm are pairwise non-isomorphic, since they have different outer automorphism groups. (John Truss showed that all these groups are simple.)

There is an interesting unsolved problem here: what happens if m is divisible by 8? Is there a finite supplement, and if so, what is the smallest such?

Anyway, we wrote up this result, which I think is nice, and submitted the paper to a journal (not by any means a top journal). They very quickly rejected it, and for one reason or another we never got round to re-submitting it.

But there was a preprint on my web page at Queen Mary. This was found by Greg Cherlin, who talked at my birthday conference in Lisbon on a very wide generalisation inspired by this. I described it briefly here. So I decided to put the paper on the arXiv, where it now resides for the foreseeable future. If Greg or anyone else needs to refer to it, the arXiv is less likely to disappear than my Queen Mary webpage. Also, someone might be inspired to look at the paper and tackle the unsolved problem above.

Greg Cherlin in Lisbon

Posted in exposition, open problems | Tagged , , | 2 Comments

Wiles and Langlands

One of the best things that pops regularly into my pigeonhole is the European Mathematical Society Newsletter. The current issue, number 104, is particularly rich in interesting articles.

For example, there is the transcript of a talk by Christian Krattenthaler (without the musical interludes, sad to say) on “Mathematics AND Music?”. He avoids many of the usual clichés about the relationship between these two disciplines, and defends the thesis

Both Mathematics AND Music are food for the soul AND the brain.

It may be difficult to explain to the non-mathematician that there is soul in mathematics; Christian refers them to the moving moment in the BBC documentary on Fermat’s Last Theorem when Andrew Wiles describes how he finally overcame the difficulties in the proof.

This brings me to the article I really want to talk about: Henri Darmon on “Andrew Wiles’ Marvellous Proof”, in which he explains the relationship between what Wiles did and the Langlands programme, which he describes as “the imposing, ambitious edifice of results and conjectures that has come to dominate the number theorist’s view of the world”. He gives a “beginner’s tour” of the Langlands programme, first excusing his own shortcomings. I want to say a bit about this, but his shortcomings are insignificant compared to mine! I shall also be much briefer, and refer you to the article.

The context is the solution of Diophantine equations, solutions of a polynomial equation in several variables over the integers (or maybe the rational numbers). But rather than tackle this head-on, we first count solutions over the finite field of order pr. (These are the Galois fields, constructed and proved unique by Galois.) For fixed p and varying r, we get an infinite sequence of numbers, which can be represented by a zeta function. Dwork and Deligne proved two remarkable facts about such zeta-functions: first, they are rational functions whose numerators and denominators are independent of the prime p (if a few bad primes are avoided), and second, the reciprocals of their roots are powers of √p. The last is the Riemann hypothesis over function fields, part of the work for which Deligne won the Abel prize.

The new developments involve allowing p to vary. For degree 2 equations in a single variable, the relationship between different primes is precisely described by Gauss’ quadratic reciprocity law. For higher degrees, things get a bit more complicated. We must combine the local zeta functions into a single global zeta function, and show that it is a modular form, in the sense that it is transformed in a very simple manner by linear fractional transformations of its argument.

This brings us to the Shimura–Taniyama conjecture, stating (more or less) that the zeta function of an elliptic curve is a modular form of weight 2. This is what Wiles proved (in the semistable case) and which led, by earlier work of Frey and Ribet, to a proof of Fermat’s Last Theorem. (The semistability assumption was later removed.)

So what does this have to do with Langlands? We have to look at Galois representations, linear representations of the Galois group of the algebraic numbers over the rationals (more precisely, of quotients corresponding to extensions of the rationals unramified outside a finite set S of primes). One can define a zeta function of such a representation; work of Weil, Grothendieck and others shows that, if the diophantine equation has good reduction outside S, then its zeta function is the quotient of the zeta functions of two such Galois representations. Now representations can be decomposed into irreducible representations, and the corresponding zeta functions multiply; so we can look at irreducible representations. Now there are notions of “modular” and “geometric” for Galois representations (the latter corresponding to realisation in an étale cohomology group, as the representations involved in zeta functions of diophantine equations do); the “main conjecture of the Langlands programme” states:

All geometric Galois representations are modular.

One of the main ingredients of Wiles’ work is a lifting theorem allowing the proof of this under suitable (local-to-global) hypotheses.

One detail I have not mentioned is the connection of the Dedekind eta-function with the generating function for the partition numbers, which featured in the work of Ramanujan; Darmon says it “plays a starring role alongside Jeremy Irons and Dev Patel in a recent film about the life of Srinivasa Ramanujan”.

Which brings me back to Krattenthaler’s article. In explaining how mathematics, like music, can contain humour, he outlines the proof of “Ramanujan’s most beautiful theorem”, the statement that the number of partitions of 5n+4 is always divisible by 5. For this, a certain amount of detail about q-series and Jacobi’s triple product formula is required before we get to the punchline of the joke!

The message from all this is that there is are deep-level correspondences between some superficially very different parts of mathematics!

I do urge you to read these articles yourself. Better, why not join the European Mathematical Society and get the Newsletter?

Posted in exposition, mathematics and ..., Uncategorized | Tagged , , , | 2 Comments

Mike O’Nan

I just heard the news that Mike O’Nan died on Monday.

I never knew him well, but I know for sure that his name will not be forgotten: a sporadic simple group, a theorem about maximal subgroups of symmetric groups (depending on a result on the socle of a primitive permutation group) that he proved simultaneously with Leonard Scott, a technique for showing non-existence of sharply 2-transitive subsets of certain 2-transitive groups …

Posted in Uncategorized | Tagged | Leave a comment

All kinds of mathematics: workshop and conclusion

Conference photograph

The final day of the conference was devoted to a satellite workshop on “Symmetry in finite and infinite structures”. The morning was a solo performance by Laci Babai, in which he explained in detail his quasi-polynomial algorithm for graph isomorphism. In the afternoon there were short contributed talks by participants, at which I had to make invidious choices and miss many talks I wanted to hear. I did listen to Milan Stehlík using root systems in statistics (in quite a different way from my one venture into this), and also celebrating the fact that, in New Zealand, the Maori have succeeded in having the Whanganui River declared a legal entity (with the rights, duties and liabilities of such) after 140 years. Then Shayo Olukoya introduced us to the rational group (homeomorphisms of Cantor space induced by transducers acting on strings) and some of its subgroups; Fatma Al-Kharousi gave us some combinatorics related to semigroups of order-preserving maps of a finite set; Justine Falque described nearly complete work to show that if the number of orbits on n-sets of an oligomorphic permutation group is polynomially bounded, then the orbit algebra is finitely generated, and so the orbit-counting sequence is polynomial on residue classes; Shichang Song showed that the automorphism group of Philip Hall’s universal locally finite group has ample generics; and Wilf Wilson talked about algorithms for finding maximal subsemigroups, which will be included in the Semigroups package for GAP. What a feast!

Altogether an amazing conference, certainly one of the most memorable experiences of my life. You can see the short film that was made to open the conference; if you watch, you will see João Araújo’s sense of humour shining through. Thank you, João, for this, and for so much else you contributed to the conference, and to your many kindnesses to me over the last ten years; the theorems, the crazy trips all over Portugal, and much more! (João is my equal top coauthor; we have ten papers published or in press, even though the first one only appeared in 2013.) And thank you to all the other organisers as well: Teresa Oliveira (Aberta), Mário Edmundo (Lisboa), Maria Elisa Fernandes (Aveiro), Gracinda Gomes (Lisboa), Ana Paula Santana (Coimbra), and Ivan Yudin (Coimbra). I hope that everyone who was there took away good memories and good new mathematics to think about and work on.

As I said in my talk, in seventy years time I want these problems solved!

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

All kinds of mathematics, 4

The fourth day began with a talk by László Babai on his quasi-polynomial algorithm for graph isomorphism. Two longer and more detailed accounts were scheduled for the workshop; this talk gave the context, and an important lemma which underlies the proof.

Then Cheryl Praeger talked about work with Stephen Glasby, Kyle Ross, and Gabriel Verret on the composition length of a primitive permutation group of degree n. Laci Pyber had outlined a c log n bound, but Cheryl and her coauthors have made this precise, finding the best possible constant c (which turns out to be 8/3) and determining the groups which meet this bound. I suggest an exercise for anyone interested: find a good bound for the composition length of a 2-transitive group – this will be much easier! In the discussion, the result that João and I found last year for the number of generators of a 2-transitive group (namely 2) was recalled. I still find it hard to believe that nobody noticed this before!

Francesco Matucci told us about hyperbolic groups (those for which a Cayley graph is δ-hyperbolic in the sense of Gromov), and presented a theorem which has as a corollary that torsion-free hyperbolic groups embed in the rational group (the group of maps of Cantor space generated by transducers acting on infinite strings).

Dugald Macpherson came next. He and his colleagues have been investigating very wide model-theoretic generalisations of the Hasse–Weil estimates for definable sets over finite fields. Depending on whether the approximations are exact or approximate, very different results are obtained.

Michael Giudici and his colleagues have been investigating semiprimitive permutation groups, those in which every non-trivial normal subgroup is either transitive or semiregular. This condition is very relevant to things related to the Weiss conjecture, which Pablo Spiga discussed. The role of minimal normal subgroups and the socle is taken by plinths for such a group (minimal transitive normal subgroups); remarkably, they have good control over these.

Ben Steinberg’s talk was about random walks on a module M over a finite ring R, where the transitions are affine maps of the form x → ax+b. Here, a is not required to be a unit, so the maps may be non-invertible. For example, if R is the 2-element field, the steps are random translations or jumps to random points. He uses the representation theory of semigroups (the subject of his recent book) to work out the eigenvalues of the transition matrix.

Wolfram Bentz told us about permutation groups, transformation semigroups, and graphs; at least this was material which I knew about, although there were probably others who didn’t.

Misha Volkov gave a very nice talk about completely reachable automata, those for which every non-empty subset of the states is the image of some composition of transitions. Clearly the semigroup generated by such an automaton has size at least 2n−1, where n is the number of states. This is a much stronger condition than synchronization, and Misha was able to use binary trees to construct and characterise such automata.

The day, and the conference proper, ended with my talk; you can find the slides in the usual place.

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

All kinds of mathematics, 3

Wednesday morning’s first speaker was Bob Gray, who told us about his quest, with Igor Dolinka, on a semigroup analogue for Philip Hall’s countable universal homogeneous locally finite group. He started with a clear introduction to Hall’s group. For semigroups, it turns out that no such example can exist; said otherwise, a countable universal locally finite semigroup cannot be homogeneous. So how homogeneous can it be? If the automorphism group of such a semigroup acts transitively on the copies of the finite semigroup S it contains, then S must be an amalgamation base; they call a semigroup maximally homogeneous if the converse holds. There is a unique such semigroup which is a limit of full transformation semigroups (as Hall’s group is a limit of symmetric groups, though the analogue of Hall’s construction fails). It has lots of nice properties; for example, its Graham–Houghton graph is the universal homogeneous graph with bipartition.

Bob started by talking about some of my books and papers which have influenced him. A reminder that any piece of writing, once it leaves the writer’s desk, has a life of its own.

Then António Malheiro told us about the plactic monoid (connected to Young tableaux) and some generalisations, the hypoplactic monoid (related to ribbon tableaux) and the Sylvester monoid (related to binary search trees). He was interested in finding analogues of Kashiwara chrystal bases for these objects.

James Mitchell spoke about semigroups generated by digraphs (where we regard a directed arc (ab) as a rank n−1 idempotent which maps a to b and fixes everything else. He surveyed many old and new results about these semigroups, and remarked that unlike many types of transformation semigroup the correlation of properties between semigroup and digraph is very close. There are connections with sliding-block puzzles (indeed, he quoted the work of Richard Wilson on these). Sliding-block puzzles are more usually represented by a groupoid than a semigroup; there must be connections!

Alexander Hulpke has new code for computing interval lattices in a group G (essentially, all subgroups between H and G for some subgroup H and their inclusions), which is much faster than the current GAP code. I am sure I will find a use for this code, which will be included in GAP 4.9 (hopefully before the end of the year).

And finally Peter Mayr talked about counting finite (universal) algebras up to term equivalence. He introduced the class of algebras with few subpowers (the number of subalgebras of An grows only exponentially with n rather than doubly exponentially, and showed us that such algebras are finitely related, have a polynomial time solution for the constraint satisfaction problem, and various other nice properties.

After lunch, we left for the excursion. First we went to the National Gallery, where the highlights included a polyptych of the generation of Henry the Navigator and the following generation of Portuguese royalty whose interpretation is very controversial, and a wonderful Hieronymus Bosch triptych. I also passed an old acquaintance whom my colleagues will certainly recognise:

St Andrew

Then to the Ajuda palace gardens, where we had a very enjoyable dinner in a tent in the garden, interspersed with some embarrassing recollections (which, fortunately, were not recorded), and so home.

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